北京邮电大学数据结构期末考试试题(A 卷) 一． 1． （A）。 A.23415 单项选择题（2 分/题） 一个栈的输入序列为 12345，则下列序列中是栈的输出序列的是 B.54132 C.31245 D.14253 设循环队列中数组的下标范围是 1~n，其头尾指针分别为 f 和 r，则 2． 其元素个数为（D）。 A.r-f B.r-f+1 C.(r-f) mod n +1 D.(r-f+n) mod n 3． 二叉树在线索化后，仍不能有效求解的问题是（D）。 C.中序线索二叉树中求中序前驱 D. 后序线索二叉树 B. 中序线索二叉树中求中序后 A.先序线索二叉树中求先序后继 继 中求后序后继 4． A.O(n) 求最短路径的 FLOYD 算法的时间复杂度为（D）。 B.O(n+e) C.O(n2) D.O(n3) 5． 一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（B）。 A.0 6． 在起始地址为 1000 的连续的内存单元中，则元素 A[5,5]的地址为（A）。 数组 A[1..5,1..6]的每个元素占 5 个单元，将其按行优先顺序存储 D.不确定 B.1 C.2 A.1140 B.1145 C.1120 D.1125 7． 而最多的是（A）。 在下列排序算法中，在待排序的数据表已经为有序时，花费时间反 B.希尔排序 C.冒泡排 D.堆排序 对有 18 个元素的有序表做折半查找，则查找 A[3]的比较序列的下 A.快速排序 序 8． 标依次为（C）。 A.1-2-3 B.9-5-2-3 C.9-5-3 D. 9-4-2-3 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位 9． 置上的是（D）。 A.堆排序 序 10． 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点 为 A，并已知 A 的左孩子的平衡因子为-1，右孩子的平衡因子为 0，则做（B）型 D.直接插入排序 B.冒泡排序 C.快速排 

调整以使其平衡。 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）棵不同形态的树。