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

数据结构（本）_202203模拟卷2
一、填空题（共10题，每题1分，共10分）树是结点的有限集合，它有根结点，记为T。其余的
结点分成为m （m>0）个（1分）★标准答案：1.0个或1个;2.互不相交;3.父结点;4.结点的度；
1. 堆排序通常采用存储结构。（1分）★标准答案：1 .顺序；
2. 队列是一种先进先出的线性表，允许插入的一端称为o （1分）★标准答案：1.队尾；
3. 假设用循环单链表实现队列，若队列非空，且队尾指针为R,则将新结点S加 入 队 列 时， 需 执 行 下 面 语 句：
O （ 1 分）
★标准答案：1. S->next=R->next;2.
R->next=S;3. R=S;

5.在哈希存储中，装
填因子 a的值越大，
则

；a的值越小，
则

_0（ 1 分）
★标准答案：1.发生冲突的可能性就越大;2.发生冲突的可能性就越小；
6. 广义表（（a,b）,c,d）的表头是 ,表尾是。（ 1 分）
★标准答案：1. （a, b）;2. （c,d）;若一个算法中的语句频度之和为T（n） =100n+4nlogn+5n&,则该算法的
时间复杂度为o （1分）★标准答案：1.0 （nA2）;
7. 一棵高度为h的满二叉树共有个终端结点。
（1分）★标准答案：1.2"h-l）;
8. 具有n个顶点的有向图最多有条边。（1分）★标准答案：1. n （n-1）;
9. 哈希表的查找效率主要取决于哈希表造表时选取的和O （］分）
★标准答案：1.哈希函数;2.处理冲突的方法；二、单选题（共10题，每题2分，共20分）
1. 在一棵二叉树的二叉链表中，空指针域数的个数为（）。（2分）n B.n一1C.n+1 D.2n
★标准答案：C在具有n个单元的循环队列中，队列满时共有（）个元素。（2分）
A. n-1 B.n C.2nD.无法确定★标准答案：A
2. 判断线索二叉树中某结点p没有左孩子的条件是（）。（2分）A.p!=nullB.p->lchild!=null
C.p->ltag=OD.p->ltag=l★标准答案：D
3. 设有1000个无序元素，希望用较快速度挑选出其中前10个最大元素，采用 （）方法最好。（2分）直接插入排序
A. 堆排序快速排序
B. 归并排序★标准答案：B
4. 已知一个图共有n个顶点，c条边，用邻接矩阵表示，要删除所有从第i个 结点出发的边，在其时间复杂度为（）。（2分）O（n）
A. O（nA2）O（n+e）
B. O（n*e）★标准答案：B
5. 在顺序表（3,6,8,10,12,15,16,18,21,25,30）中,用折半法查找关键码值11,所需的关键码比较次数为（）次。（2分）
A.2B.3C.4D.5★标准答案：C
6. 图的广度优先遍历类似于树的（）遍历。（2分）A.先序B.中序
C.后序D.层次★标准答案：D
7. 线性表L在（）情况下适用于使用链式结构实现。（2分）A.需经常修改L中的结点值B.需不断对L进行删除插入
C. L中含有大量的结点D. L中结点结构复杂★标准答案：B
8. 向一个有115个元素的顺序表中插入一个新元素并保持原来顺序不变，平均 要移动（）个元素。（2分）A.15C.115D.116
★标准答案：B顺序栈初始化的条件是栈顶指针top的值为（）。（2分）
A.-l B.O C.MAXSIZE D.任意值★标准答案：A 三、问答题（共4题，每题5分，共20分）
1. 简述什么是深度。（5分）★标准答案：树中所有结点的度的最大值。
2. 简述什么是树的定义。（5分）★标准答案：树是结点的有限集合，它有0个或1个根结点，记为T。其余的 结点分成为m （m>0）个有0个或1个互不相交的集合Tl, T2, Tm,每 个集合乂都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（l<i<m）o 一个结点的子结点个数为该结点的度。
3. 简述线性数据结构与非线性数据结构的区别。（5分）★标准答案：线性数据结构中数据的关系只有一种，每个结点元素的直接前驱 和直接后继是唯一的；非线性数据结构中数据的关系可以有两种或者多种，每 个结点元素的直接前驱和直接后继是不唯一的。
4. 在哈希表中，发生冲突的可能性与哪些因素有关？为什么？ （5分）★标准答案：主要与哈希函数、装填因子a有关。如果用哈希函数计算的地址 分布均匀，则冲突的可能性较小。在哈希存储中，装填因子a的值越大，则发 生冲突的可能性就越大 ；a的值越小，则发生冲突的可能性就越小。
四、计算题（共3题，每题1（）分，共3（）分）设关键字的输入顺序为：56, 20, 62, 17, 40, 100。请写出生成的二叉排 序树及其中序遍历序列。（10分）
★标准答案：17 40100 , /中序遍历序列:17, 20, 40, 56, 62, 100.
已知一个无向图的顶点集为{a, b, c, d}o其邻接矩阵如下所示：
a 何 1 1 1 'b10 11
c110 1
（1）画出该图的图形；<2）根据邻接矩阵从顶点a出发的深度优先遍历序列和广度优先遍历序列。（10
分）★标准答案：
1. 己知某通讯系统使用8种字符，其概率分布分别为：0.06, 0.28, 0.07, 0.08,0.14, 0.22, 0.03, 0.12,试设计其哈夫曼编码。（10分）
★标准答案：哈夫曼不唯一，其对应编码也不唯一，写对即可得分。
五、算法设计题（共2题，每题1（）分，共20分）设计一递归算法，在以二叉链表为存储结构的二叉树中，统计二叉树中叶子
结点的个数。(1()分)★标准答案：BSTNode *temp; Void Change(BSTree T) / *T 为树根指针( if (T->lchild!=null) || (T->rchild !=null) ( ( temp= T->lchild; T->lchild= T->rchild; T->rchild=temp; count_leaf(T->lchild); / 递归求左子树的叶子结点数 count_lcaf(T->rchild); /递归求右子树的叶子结点数
1. 设计一递归算法，实现在二又链表为存储结构的二又树中交换每个结点的左 孩子和右孩子。
二叉链表存储结构如下：
typedef struct node{int data;
struct node *lchild, *rchild;)BitNodc» * BiTree;
(10 分)★标准答案：BSTNode 气emp; Void Change(BSTree T) / 叮 为树根指针{ if (T->lchild!=null) || (T->rchild !=null) ( ( temp= T->lchiId; T->lchild= T->rchild; T->rchild=temp; counl_leaf(T->lchild); / 递归求左子树的叶子结点数 count」eaf(T->rchild); /递归求右子树的叶子结点数