数据结构典中典的题

一、绪论

二、线性表

设有一个12×12的对称矩阵M，将其上三角部分的元素mi, j（1≤i≤j≤12）按行优先存入C语言的一维数组  N中，元素m6, 6在N中的下标是 

A．50		B．51 		C．55		D．66 

答案：
A 

三、栈与队列

现有队列Q与栈S，初始时Q中的元素依次是1, 2, 3, 4, 5, 6（1在队头），S为空。若仅允许下列3种操作：①出队并输出出队元素；②出队并将出队元素人栈；③出栈并输出出栈元素,则不能得到的输出序列是
A．1,2,5,6,4,3 		B．2,3,4,5,6,1		C．3,4,5,6,1,2		D．6,5,4,3,2,1  

答案：
C 

四、树与二叉树

若将一棵树 T 转化为对应的二叉树 BT，则下列对 BT 的遍历中，其编历序列与 T 的后根
遍历序列相同的是______ 
A．先序遍历	B．中序遍历	C．后序遍历	D．按层遍历 

对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点，则 n 的值
是______ 
A．56	B．57	C．58	D．60

在任意一棵非空平衡二叉树（AVL 树）T 1 中，删除某结点 v 之后形成平衡二叉树 T 2 ，再
将 v 插入 T 2 形成平衡二叉树 T 3 。下列关于 T 1 与 T 3 的叙述中，正确的是______ 
（I）若 v 是 T 1 的叶结点，则 T 1 与 T 3 可能不相同 
（II）若 v 不是 T 1 的叶结点，则 T 1 与 T 3 一定不相同 
（III）若 v 不是 T 1 的叶结点，则 T 1 与 T 3 一定相同 
A．仅Ⅰ	 B．仅Ⅱ 	C．仅Ⅰ、Ⅱ	D．仅Ⅰ、Ⅲ 

设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。若T有k个叶结点，则T的结点总数是______
A．2k-1 		B．2k 		C．??^2 		D．2^?? ? 1 

已知字符集{a, b, c, d, e, f}，若各字符出现的次数分别为  6, 3, 8, 2, 10, 4，则对应字符集中 
各字符的哈夫曼编码可能是______

A．00,1011,01,1010,11,100 
B．00,100,110,000,0010,01
C．10,1011,11,0011,00,010
D．0011,10,11,0010,01,000

已知二叉排序树如下图所示，元素之间应满足的大小关系是______。

答案：
B C A A A

五、图

六、查找

七、排序

选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是 
Ⅰ．数据的规模 	Ⅱ．数据的存储方式 
Ⅲ．算法的稳定性 Ⅳ．数据的初始状态 
A．仅Ⅲ 	 B．仅Ⅰ、Ⅱ 	C．仅Ⅱ、Ⅲ、Ⅳ	D．Ⅰ、Ⅱ、Ⅲ、Ⅳ 

排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中， 
不可能是快速排序第二趟结果的是
A．5，2，16，12，28，60，32，72 
B．2，16，5，28，12，60，32，72 
C．2，12，16，5，28，32，72，60 
D．5，2，12，28，16，32，72，60 

设外存上有 120 个初始归并段，进行 12 路归并时，为实现最佳归并，需要补充的虚段 
个数是 
A．1		B．2 	C．3		 D．4 

 答案： 
 D D B

数据结构典中典的题