华东理工大学网教数据结构（本）1期末复习题及参考答案

数据结构（本）模拟卷1

一、填空题（共10题海题1分，共10分）

1.图的深度优先遍历类似于树的遍历。（1分）

★标准答案：1.先序；

2.有向盲G用邻接矩’阵存储，其第i行的所有元素之和等于顶点i的o

（1分）

★标准答案：1.出度；

3.具有n个顶点的有向图最多有条边。（1分）

★标准答案：1.n（n-1）;

4.设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶

子结点，有个度为2的结点，有个结点只有非空左

子树，有个结点只有非空右子树。（1分）

★标准答案：1.500;2.499;3.1;4.0;

5.图的广度优先遍历类似于树的遍历。（1分）

★标准答案：L层次；

6.有8个结点的无向图最多有条边。（1分）

★标准答案：1.28;

7.由树转换为二叉树，其根节点的右子树总是。（1分）

★标准答案：1.为空；

8.设有两个串p和q,求q在p中首次出现的位置的运算称作

（1分）

★标准答案：1.子串定位；

9.已知二维数组A[20][10]采用行序为主方式存储，每个元素占2个存储单元，

并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是。

（1分）

★标准答案：1.1168;

10.队列是一种先进先出的线性表，允许插入的一端称为。（1分）

★标准答案：1.队尾；

二、单选题（共10题海题2分，共20分）

1.判断线索二叉树中某结点p没有左孩子的条件是（）。（2分）

A.p!=nullB.p->lchild!=null

C.p->ltag=0D.p->ltag=l

★标准答案：D

2.在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。（2

分）

A.n

B.n-1

C.n/2

D.n+1

★标准答案：B

3.在长度为n的顺序表中的第i(iSign+l)个位置上插入一个元素，元素的移

动次数为()。(2分)

A.n-i+1B.n-i

C.iD.i-1

★标准答案：A

4.在顺序表(3,6,8,10,12,15,16,18,21,25,30)中,用折半法查找关键码值11,

所需的关键码比较次数为O次。(2分)

A.2B.3C.4D.5

★标准答案：C

5,广义表A=(()),则表尾GetTail(A)为()。(2分)

A.)B.(())C.空表D.(

★标准答案：C

6.已知二叉树的中序序列为DBGEAFC,后序序歹U为DGEBFCA,则先序序列

为。。(2分)

A.BDEGACFB.ABDEGCFC.BDEAGCFD.ADBGEFC

★标准答案：B

7.设有1000个无序元素，希望用较快速度挑选出其中前10个最大元素，采用

()方法最好。(2分)

A.直接插入排序

B.堆排序

C.快速排序

D.归并排序

★标准答案：B

8.已知一个图共有n个顶点，e条边，用邻接矩阵表示，要删除所有从第i个

结点出发的边，在其时间复杂度为()。(2分)

A.O(n)

B.O(nA2)

C.O(n+e)

D.O(n*e)

★标准答案：B

9.如果二叉树中某结点p->rtag=O,则在对该二叉树按照某种次序进行线索化时,

该指针域指向该结点的()。(2分)

A.左孩子B.右孩子

C.遍历前驱D.遍历后继

★标准答案：B

10.GetTail[GetHead[GetTail[((a,b),(c,d))]]]===()(2分)

A.(d)B.dC.(a,b)D.(a)

★标准答案：A

三、问答题(共4题，每题5分洪20分)

1.简述什么是树的定义。(5分)

★标准答案：树是结点的有限集合，它有。个或1个根结点，记为T。其余的

结点分成为m(m>0)个有0个或1个互不相交的集合Tl,T2,…，Tm,每

个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点(IgiWm)。

一个结点的子结点个数为该结点的度。

2.简述什么是深度。(5分)

★标准答案：树中所有结点的度的最大值。

3.写出下列程序段的输出结果。

voidmain()

{QueueQ;InitQueue(Q);

Charx='e';y='c';

EnQueue(Q,'h')；EnQueue(Q,'r')；EnQueue(Q,y);

DeQueue(Q,x);EnQueue(Q,x);

DeQueue(Q,x);EnQueue(Q,'a')；

While(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);};

printf(x);

}(5分)

★标准答案：输出为“char”。

4.在哈希表中，发生冲突的可能性与哪些因素有关？为什么？(5分)

★标准答案：主要与哈希函数、装填因子a有关。如果用哈希函数计算的地址

分布均匀，则冲突的可能性较小。在哈希存储中，装填因子a的值越大，则发

生冲突的可能性就越大；a的值越小，则发生冲突的可能性就越小。

四、计算题(共3题，每题10分洪30分)

1.已知某通讯系统使用8种字符，其概率分布分别为：0.06,0.28,0.07,0.08,

0.14,0.22,0.03,0.12,试设计其哈夫曼编码。(10分)

★标准答案：哈夫曼不唯一，其对应编码也不唯一，写对即可得分。

2.设关键字的输入顺序为：56,20,62,17,40,100。请写出生成的二叉排

序树及其中序遍历序列。(10分)

★标准答案:1740100,/中序遍历序列:17,20,40,56,62,100.

如下图所示:

(1)画出该图的邻接表表示；

3.(2)写出从顶点a出发的深度优先遍历序列和广度优先遍历序列。(io分)

★标准答案：

五、算法设计题(共2题，每题10分洪20分)

1.设A、B是两个单链表，其表中元素递增有序，写一算法将A、B归并成一

个有序的单链表C,C也是递增有序的。(10分)

★标准答案:voidmerge(LinklistA,LinklistB,LinklistC){Listnode*p,*q,*r;

C=A;p=A->next;q=B->next;r=C;while(p!=null&q!=null)〃尾插法创建C链表

if(p->data<=q->data){r->next=p;r=p;p=p->next;else{r->next=q;r=q;q=q->next;

while(p!=null){r->next=p;r=p;p=p->next;while(q!=null){r->next=q;r=q;

q=q->next;free(B);

2.设计一递归算法，将以二叉链表为存储结构的二叉树中的叶子结点全部删除。

二叉排序树的存储结构如下：(10分)

★标准答案：voidcout_node(BSTreeT)/*T为