1、线性表是一种由n个数据元素组成的数据结构，n的取值是 单选题 2分

2、在一个单链表中，已知q所指结点是p所指结点的后继结点，若在p和q之间插入s所指结点，则正确的操作是 单选题 2分

3、下列选项中，不宜通过找求解的问题是 单选题 2分

4、设栈S的输入序列为1，2，3，4，5，则下列选项中不可能是S的输出序列的是 单选题 2分

5、使用一个大小为6的数组保存循环队列Q。若从Q中出队两个元素，并入队一个元素，此时队尾rear和队头front的值分别为2和4，则在执行这三个操作之前rear和front的值分别是 单选题 2分

6、设二维数组M有3行4列，按行优先的方式存储，每个元素占6个存储单元。第1个元素的存储地址为100，则M[2][2]的存储地址为 单选题 2分

7、设n阶方阵M是对称矩阵，采用压缩存储方式将M中的元素保存在一维数组B中，则下列选项中，正确的是 单选题 2分

8、已知完全二叉树T的第4层有5个叶结点，则T的结点个数最多是 单选题 2分

9、在一棵非空二叉树的后序遍历序列中，所有列在根结点前面的是 单选题 2分

10、若对题10图所示的无向图进行深度优先搜索遍历，则下列选项中正确的追历序列 单选题 2分

11、对题11图所示的有向图进行拓扑排序。下列选项中能够得到的拓扑序列是 单选题 2分

12、已知数据序列（8，9，10，4，5，6，20，1，2）是某种排序算法第一越排序后得到的结果，则该算法可能是 单选题 2分

13、下列选项中，每一趟都能选出一个元素放在其最终位置上，且不稳定的接序算法是 单选题 2分

14、对有序表（1，9，12，41，62，77，82，95，100）采用二分查找方法查找值82，查找过程中关键字的比较次数是 单选题 2分

15、将下列数据依次插入到初始为空的二叉排序树中，能得到高度最小的二叉排序树的序列是 单选题 2分

16、线性表的存储方式中，能够随机存取表中任一元素的存储结构是（ ）。 填空题 2分

17、用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342的出栈顺序，相应的S、X操作串为（ ）。 填空题 2分

18、若广义表L的深度是0，则L一定是（ ）。 填空题 2分

19、广义表（（a，b），（c，d），e）的表尾是（ ）。 填空题 2分

20、利用二叉树中的空指针域，使之指向结点在某种遍历次序下的前趋或后继结点，此时域中的内容称为（ ）。 填空题 2分

21、若用n个带权字符构造哈夫曼树T，则T中结点的总数是（ ）。 填空题 2分

22、设连通带权图G中有n个顶点，使用普里姆算法构造G的最小生成树T，T中含有的边数是（ ）。 填空题 2分

23、要使n个记录的关键字序列k1，k2，......，kn，成为小根堆，关键字之间必须满足的关系是（  ）。 填空题 2分

24、索引顺序查找是一种将顺序查找和二分查找思想结合在一起的查找方法，又称（ ）。 填空题 2分

25、5阶B树T中，除根结点之外每个结点中所含关键字个数最少是（ ）。 填空题 2分

26、设稀疏矩阵M如下所示。矩阵的行列下标均从1开始。请画出M按行优先存储的三元组表。 简答题 5分

27、已知二叉树T的前序遍历序列是A，B，C，D，E，L，M，O，N，中序遍历序列是C，B，E，D，A，M，O，L，N，请画出T。 简答题 5分

28、已知有向带权图G如题28图所示。请回答下列问题。（1）给出图G的邻接矩阵。（2）求出G中从源点A到其余各顶点的最短路径。要求根据迪杰斯特拉算法的求解过程依次给出各条路径，包括路径上经过的顶点及其长度。 简答题 5分

29、设有关键字序列（65，23，31，26，7，91，53，15，72，52），散列函数为H（key）=key%11，将关键字依次放入表长为11的散列表H中，采用线性探测法处理冲突。请回答下列问题。（1）画出构造的散列表，并给出查找每个关键字的探查次数。（2）求散列表的平均查找长度ASL。 简答题 5分

30、 简答题 5分

31、 简答题 5分

32、 简答题 5分

33、 简答题 5分

34、 简答题 10分