北京邮电大学数据结构期末考试试题

北京邮电大学数据结构期末考试试题

北京邮电大学数据结构期末考试试题(A卷)

一．单项选择题（2分/题）

1．一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（A）。

A.23415 B.54132 C.31245 D.14253

2． 设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（D）。

A.r-f B.r-f+1 C.(r-f) mod n +1 D.(r-f+n) mod n

3． 二叉树在线索化后，仍不能有效求解的问题是（D）。

A.先序线索二叉树中求先序后继 B. 中序线索二叉树中求中序后继 C.中序线索二叉树中求中序前驱 D. 后序线索二叉树中求后序后继

4． 求最短路径的FLOYD算法的时间复杂度为（D）。

A.O(n) B.O(n+e) C.O(n2) D.O(n3)

5． 一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（B）。

A.0 B.1 C.2 D.不确定

6． 数组A[1..5,1..6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为（A）。

A.1140 B.1145 C.1120 D.1125

7． 在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是（A）。

A.快速排序 B.希尔排序 C.冒泡排序 D.堆排序

8． 对有18个元素的有序表做折半查找，则查找A[3]的比较序列的下标依次为（C）。

A.1-2-3 B.9-5-2-3 C.9-5-3 D. 9-4-2-3

9． 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（D）。

A.堆排序 B.冒泡排序 C.快速排序 D.直接插入排序

10． 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则做（B）型调整以使其平衡。

A.LL B.LR C.RL D.RR

二． 判断题（1分/题）

1.线性表的长度是线性表所占用的存储空间的大小。 F

2.双循环链表中，任意一结点的后继指针均指向其逻辑后继。F

3.在对链队列做出队操作时，不会改变front指针的值。F

4.如果两个串含有相同的字符，则说它们相等。F

5.如果二叉树中某结点的度为1，则说该结点只有一棵子树。T

北京邮电大学数据结构期末考试试题

6.已知一棵树的先序序列和后序序列，一定能构造出该树。F

7.图G的一棵最小代价生成树的代价未必小于G的其它任何一棵生成树的代价。T

8.图G的拓扑序列唯一，则其弧数必为n-1（其中n为顶点数）。F

9.对一个堆按层次遍历，不一定能得到一个有序序列。T

10.直接选择排序算法满足：其时间复杂度不受数据的初始特性影响，为O(n2)。T

三． 填空题（2分/空）

1．已知完全二叉树的第8层有8个结点，则其叶子结点数是（68）。68+8-4

2．将下三角矩阵A[1..8,1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7,5]的地址是（1100）。

3．有n个顶点的强连通有向图G至少有（n）条弧。

4．有n个结点并且其高度为n的二叉树的数目是（2^（n-1））。

5．高度为8的平衡二叉树的结点数至少是（54）。

6．3个结点可构成（5）棵不同形态的树。

（以上是部分题目和答案，其他题目会在近期献上）