数据结构期末考试题30
汪国真-张君钰
：
考
号
密
封
：
姓
名
装
订
：
业
专
线
：
级
班
信息技术学院2006-2007学年第二学期期末考试
5．已知二叉树中叶子数为50，共有一个孩子的结点数为30，则总结点数为________。
数据结构 试卷30（适用班级： ）
6．在左右子树均不空的先序线索二叉树中，空链域的数目是________。
（答题时间：120分钟，满分：100分）
7．在二叉链表中判断某指针P所指结点为叶子结点的条件是________。
题 号
第一部分 第二部分 第三部分 第四部分 总 分 核分人
8．直接选择排序算法在最好情况下所作的交换元素的次数为________。
得 分
9．下列排序算法中，占用辅助空间最多的是________。
（堆排序，希尔排序，快速排序，归并排序）
得 分
10．一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个______________
评卷人
得 分
一、判断题（10分，每题1分）
评卷人
1.对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该
图的每个顶点。（ ）
三、选择题（20分，每题2分）
2.在索引顺序表上实
现分块查找，在等概率查找情况下，其平均查找长度不公与表的个数
１．在有n个叶子结点的哈夫曼树中
，其结点总数为（ ）。
有关，而且与每一块中的元素个数有关。（ ）
A．不确定
B．2n C．2n+1 D．2n-1
3.只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（ ）
2．下列序列中，（ ）是执行第一趟快速排序得到的序列（排序的关键字类型是字符串）。
4.图G的最小生成树的代价一定小于其他生成树的代价。（ ）
A．[da,ax,eb,de,bb]ff[ha,gc]
B．[cd,eb,ax,da]ff[ha,gc,bb]
5.已知一棵树的先序序列和后序序列，一定能构造出该树。（ ）
C．[gc,ax,eb,cd,bb]ff[da,ha]
D．[ax,bb,cd,da]ff[eb,gc,ha]
6.对一个堆按层次遍历，不一定能得到一个有序序列。（ ）
3．若线性表最常用的操作是存取第i个元素及其前趋的值，则采用（ ）存储方式节省时间。
7.设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定
A．单链
表 B．双链表 C．单循环链表 D．顺序表
是叶子结点。（ ）
4．下列排序算法中
，时间复杂度不受数据初始状态影响，恒为O（nlog
2
n）的是（ ）。
8.任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条。（ ）
A．堆排序 B．冒泡排序 C．直接选择排序 D．快速排序
9.删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（ ）
5．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
10.快速排序是排序算法中最快的一种。（ ）
A．空或只有一个结点
B．高度等于其结点数
得 分
C．任一结点无左孩子 D．任一结点无右孩子
评卷人
6．下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（ ）。
A．堆排序 C．直接插入排序 B．冒泡排序 D．快速排序
二、填空题（20分，每空2分）
7．二叉数在线索化后，仍不能有效求解的问题是（
）。
1．取出广义表A=（（X，Y，Z），（A，B，C，D））中的原子B的函数是________。
A．先序线索二叉树中求先序后继 B．中序线索二叉树中求中序后继
2．在有序表A[1.
.20]中，中，采用二分查找算法查找元素值等于A[12]的元素，所比较过
C．中序线索二叉树中
求中序前驱 D．后序线索二叉树中求后序后继
元素的下标依次为________。
8．
在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左
3．若某串的长
度小于一个常数，则采用________存储方式最节省空间。
孩子的平衡因子为-1，右孩子的平衡因子为0，则应作（ ）型调整以使其平衡。
4．在有n个顶点的有向图中，每个顶点的度最大可达________。
A．LL
B．LR C．RL D．RR
第 1 页 共 3 页
9．快速排序算法在最好情况下的时间复杂度为（ ）。
A．O(n)
B．O(n
2
) C．O(nlog
2
n)
D．O(log
2
n)
3、已知一棵三阶的B-
树如下图所示，假定依次删除关键字46，24，52，8请画出每次删除结
点后树的情况：(6分)
10．已知数据表A中每个元素距其最终位置不远，则采用（ ）排序算法最省时间。
A．堆排序
得 分
评卷人
B．插入排序 C．直接选择排序 D．快速排序
四、应用题（30分，每题6分）
1．设散函数H（k）=k%11，给定键值序列为13，
41，15，44，6，68，12，25，38，64，试
画出相应的散列表，并求在等概率下成功查
找时的平均查找长度。（6分）
2．求出下面图中顶点1到其余顶点的最短路径。（6分）
4、什么是赫夫曼（Huffman）树？有一
组数值14、21、32、15、28，画出赫夫曼树，并计算
其WPL。（6分）
5、已知
一组键值序列为(41，66，73，52，40，37，65，43)，试采用快速排序法对该组序列
作升序排序，并给出每一趟的排序结果。（6分）
第 2 页 共 3 页
得 分
评卷人
五、程序题（20分）
1．编写一个算法交换
单链表中P所指向的位置和其后续位置上的两个结点，HEAD指向该链
表的表头，P指向该链表中的某
一结点。（10分）
2．假设二叉树采用链接存储结构进行存储，ROOT指向根结点，P
所指结点为任一给定的结
点，编写一个求出从根结点到这所指结点之间路径的算法。（10分）
第 3 页 共 3 页
：
考
号
密
封
：
姓
名
装
订
：
业
专
线
：
级
班
信息技术学院2006-2007学年第二学期期末考试
5．已知二叉树中叶子数为50，共有一个孩子的结点数为30，则总结点数为________。
数据结构 试卷30（适用班级： ）
6．在左右子树均不空的先序线索二叉树中，空链域的数目是________。
（答题时间：120分钟，满分：100分）
7．在二叉链表中判断某指针P所指结点为叶子结点的条件是________。
题 号
第一部分 第二部分 第三部分 第四部分 总 分 核分人
8．直接选择排序算法在最好情况下所作的交换元素的次数为________。
得 分
9．下列排序算法中，占用辅助空间最多的是________。
（堆排序，希尔排序，快速排序，归并排序）
得 分
10．一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个______________
评卷人
得 分
一、判断题（10分，每题1分）
评卷人
1.对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该
图的每个顶点。（ ）
三、选择题（20分，每题2分）
2.在索引顺序表上实
现分块查找，在等概率查找情况下，其平均查找长度不公与表的个数
１．在有n个叶子结点的哈夫曼树中
，其结点总数为（ ）。
有关，而且与每一块中的元素个数有关。（ ）
A．不确定
B．2n C．2n+1 D．2n-1
3.只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（ ）
2．下列序列中，（ ）是执行第一趟快速排序得到的序列（排序的关键字类型是字符串）。
4.图G的最小生成树的代价一定小于其他生成树的代价。（ ）
A．[da,ax,eb,de,bb]ff[ha,gc]
B．[cd,eb,ax,da]ff[ha,gc,bb]
5.已知一棵树的先序序列和后序序列，一定能构造出该树。（ ）
C．[gc,ax,eb,cd,bb]ff[da,ha]
D．[ax,bb,cd,da]ff[eb,gc,ha]
6.对一个堆按层次遍历，不一定能得到一个有序序列。（ ）
3．若线性表最常用的操作是存取第i个元素及其前趋的值，则采用（ ）存储方式节省时间。
7.设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定
A．单链
表 B．双链表 C．单循环链表 D．顺序表
是叶子结点。（ ）
4．下列排序算法中
，时间复杂度不受数据初始状态影响，恒为O（nlog
2
n）的是（ ）。
8.任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条。（ ）
A．堆排序 B．冒泡排序 C．直接选择排序 D．快速排序
9.删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（ ）
5．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
10.快速排序是排序算法中最快的一种。（ ）
A．空或只有一个结点
B．高度等于其结点数
得 分
C．任一结点无左孩子 D．任一结点无右孩子
评卷人
6．下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（ ）。
A．堆排序 C．直接插入排序 B．冒泡排序 D．快速排序
二、填空题（20分，每空2分）
7．二叉数在线索化后，仍不能有效求解的问题是（
）。
1．取出广义表A=（（X，Y，Z），（A，B，C，D））中的原子B的函数是________。
A．先序线索二叉树中求先序后继 B．中序线索二叉树中求中序后继
2．在有序表A[1.
.20]中，中，采用二分查找算法查找元素值等于A[12]的元素，所比较过
C．中序线索二叉树中
求中序前驱 D．后序线索二叉树中求后序后继
元素的下标依次为________。
8．
在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左
3．若某串的长
度小于一个常数，则采用________存储方式最节省空间。
孩子的平衡因子为-1，右孩子的平衡因子为0，则应作（ ）型调整以使其平衡。
4．在有n个顶点的有向图中，每个顶点的度最大可达________。
A．LL
B．LR C．RL D．RR
第 1 页 共 3 页
9．快速排序算法在最好情况下的时间复杂度为（ ）。
A．O(n)
B．O(n
2
) C．O(nlog
2
n)
D．O(log
2
n)
3、已知一棵三阶的B-
树如下图所示，假定依次删除关键字46，24，52，8请画出每次删除结
点后树的情况：(6分)
10．已知数据表A中每个元素距其最终位置不远，则采用（ ）排序算法最省时间。
A．堆排序
得 分
评卷人
B．插入排序 C．直接选择排序 D．快速排序
四、应用题（30分，每题6分）
1．设散函数H（k）=k%11，给定键值序列为13，
41，15，44，6，68，12，25，38，64，试
画出相应的散列表，并求在等概率下成功查
找时的平均查找长度。（6分）
2．求出下面图中顶点1到其余顶点的最短路径。（6分）
4、什么是赫夫曼（Huffman）树？有一
组数值14、21、32、15、28，画出赫夫曼树，并计算
其WPL。（6分）
5、已知
一组键值序列为(41，66，73，52，40，37，65，43)，试采用快速排序法对该组序列
作升序排序，并给出每一趟的排序结果。（6分）
第 2 页 共 3 页
得 分
评卷人
五、程序题（20分）
1．编写一个算法交换
单链表中P所指向的位置和其后续位置上的两个结点，HEAD指向该链
表的表头，P指向该链表中的某
一结点。（10分）
2．假设二叉树采用链接存储结构进行存储，ROOT指向根结点，P
所指结点为任一给定的结
点，编写一个求出从根结点到这所指结点之间路径的算法。（10分）
第 3 页 共 3 页