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

数据结构（本）模拟卷1
一、填空题（共10题，每题1分，共10分）图的深度优先遍历类似于树的遍历。（1分）
★标准答案：1,先序；有向图G用邻接矩'阵存储，其第i行的所有元素之和等于顶点i的o
（1分）★标准答案：1.出度；
1. 具有n个顶点的有向图最多有条边。（1分）★标准答案：1. n （n-1）;
2. 设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左
子树，有个结点只有非空右子树。（1分）★标准答案：1. 500;2. 499;3. 1;4. 0;
3. 图的广度优先遍历类似于树的遍历。（1分）★标准答案：1.层次；
4. 有8个结点的无向图最多有条边。（1分）★标准答案：1.28;
5. 由树转换为二叉树，其根节点的右子树总是o （1分）★标准答案：1.为空；
6. 设有两个串p和q,求q在p中首次出现的位置的运算称作
（1分）★标准答案：1.子串定位；
7. 己知二维数组A[20][10]采用行序为主方式存储，每个元素占2个存储单元,并且A[l（）][5]的存储地址是100（）,则A[18][9]的存储地址是o
（1分）★标准答案：1. 1168;
8. 队列是一种先进先出的线性表，允许插入的一端称为。（1分）★标准答案：1.队尾；
二、单选题（共10题，每题2分，共20分）判断线索二叉树中某结点p没有左孩子的条件是（）。（2分）
A. p!=nullB.p->lchild!=nullC.p->ltag=0D.p->ltag=l
★标准答案：D在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。（2 分）
A. nn-1
B. n/2n+1
★标准答案：B在长度为n的顺序表中的第i (14寸1+1)个位置上插入一个元素，元素的移 动次数为()。(2分)
A. n-i+1 B.n-iC.i D.i-1
★标准答案：A在顺序表(3,6,8,10,12,15,16,18,21,25,30)中,用折半法查找关键码值11, 所需的关键码比较次数为()次。(2分)
A.2B.3C.4D.5★标准答案：C
1. 广义表 A=(()),则表尾 GetTail(A)为()。(2 分)A.)B.(()) C.空表 D.(
★标准答案：C己知二叉树的中序序列为DBGEAFC,后序序列为DGEBFCA,则先序序列 为()。(2分)
A.BDEGACF B.ABDEGCF C.BDEAGCF D.ADBGEFC★标准答案：B
2. 设有1000个无序元素，希望用较快速度挑选出其中前10个最大元素，采用
()方法最好。(2分)直接插入排序
A. 堆排序快速排序
B. 归并排序★标准答案：B
3. 已知一个图共有n个顶点，e条边，用邻接矩阵表示，要删除所有从第i个 结点出发的边，在其时间复杂度为()。(2分)O(n)
A. O(nA2)O(n+e)
B. O(n*e)★标准答案：B
4. 如果二叉树中某结点p->rtag=O,则在对该二叉树按照某种次序进行线索化时, 该指针域指向该结点的()。(2分)A.左孩子B.右孩子
C.遍历前驱 D.遍历后继★标准答案：B
1(). GetTail [GetHead [GetTail【((a,b),(c,d))】】】===()(2 分)A. (d) B.d C.(a,b)D.(a)
★标准答案：A三、问答题（共4题，每题5分，共20分）
1. 简述什么是树的定义。（5分）★标准答案：树是结点的有限集合，它有0个或1个根结点，记为T。其余的 结点分成为m （m>0）个有0个或1个互不相交的集合Tl, T2, Tm,每 个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（l<i<m）o 一个结点的子结点个数为该结点的度。
2. 简述什么是深度。（5分）★标准答案：树中所有结点的度的最大值。
3. 写出下列程序段的输出结果。
void inain()(Queue Q; InitQueue (Q);
Char x='c'; 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);prinlf(y); }; printf(x);｝（5 分）
★标准答案：输出为“char”。
4. 在哈希表中，发生冲突的可能性与哪些因素有关？为什么？ （5分）★标准答案：主要与哈希函数、装填因子a有关。如果用哈希函数计算的地址 分布均匀，则冲突的可能性较小。在哈希存储中，装填因子a的值越大，则发 生冲突的可能性就越大 ；a的值越小，则发生冲突的可能性就越小。
四、计算题（共3题海题10分，共30分）已知某通讯系统使用8种字符，其概率分布分别为：0.06, 0.28, 0.07, （）.08,
0.14, 0.22, 0.03, 0.12,试设计其哈夫曼编码。（10分）★标准答案：哈夫曼不唯一，其对应编码也不唯一，写对即可得分。
1. 设关键字的输入顺序为：56, 20, 62, 17, 40, 100。请写出生成的二叉排 序树及其中序遍历序列。（10分）★标准答案:

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

如下图所示:

(1)画出该图的邻接表表示；<2)写出从顶点a出发的深度优先遍历序列和广度优先遍历序列。(io分)
★标准答案：
五、算法设计题(共2题海题1()分，共20分)设A、B是两个单链表，其表中元素递增有序，写一算法将A、B归并成一 个有序的单链表C, C也是递增有序的。(1()分)
★标准答案：void merge(Linklist A , Linklist B, Linklist C ) (Listnode *p,*q,*r; C=A; p=A->ncxt; q=B->next; r=C; whilc(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; i-p; p=p->next; while (q!=null) (r->next= q; i-q; q=q->next; free(B);设计一递归算法，将以二叉链表为存储结构的二叉树中的叶子结点全部删除。 二叉排序树的存储结构如下：(1()分)
★标准答案：void cout.node (BSTree T) / *T 为树根指针{ if (T) ( if ((T->lchild=NULL) & (T->rchild==NULL) Free(T); / 删除度为 0 的结点; count_node(T->lchild); /递归删除左子树中度为0的结点数 count_nodc(T->rchild); /递归删除右子树中度为0的结点数