北京邮电大学数据结构期末考试试题(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）棵不同形态的树。
北京邮电大学数据结构期末考试试题(A卷)
