1、下列关于数据项和数据元素的叙述中，正确的是 单选题 1分

2、下列关于抽象数据类型的叙述中，正确的是 单选题 1分

3、设有初始为空的栈S，入栈序列是f，e，d，c，b，a，出栈序列是d，e，a，b，c，f，则需要为S分配的空间大小至少是 单选题 1分

4、 单选题 1分

5、采用行优先压缩存储方式保存6行6列对称矩阵A的上三角部分，每个元素占2个单元，若A中第一个元素au的存储地址是10，则元素a34的存储地址是 单选题 1分

6、已知广义表L=（（（1，i），h），（x，i，a，o）），下列运算中，结果得到h的是 单选题 1分

7、下列关于二叉树的叙述中，错误的是 单选题 1分

8、若二叉树的前序遍历序列是ABCD，中序遍历序列是ACDB，则其后序遍历序列是 单选题 1分

9、对下图进行广度优先搜索遍历，正确的遍历序列是 单选题 1分

10、关于图G的深度优先生成树T1与广度优先生成树T2，下列叙述中正确的是 单选题 1分

11、对n个记录进行排序，最坏情况下，时间复杂度不是O(n2)的排序方法是 单选题 1分

12、下列排序方法中，不宜在链表上实现的是 单选题 1分

13、若元素序列11，13，15，7，8，9，23，2，5是采用下列排序算法之一得到的第2趟排序后的结果，则该排序算法是 单选题 1分

14、在长度为n（n>100）的有序线性表中进行二分查找，查找成功时，查找长度不多于4的关键字个数是 单选题 1分

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

16、非空的带头结点的单循环链表中，终端结点的指针域指向的是链表的（ ） 填空题 2分

17、已知循环队列存储在一维数组A[0..n-1]中，头指针是front，尾指针是rear，初始时front的值和rear的值均是0，则第1个入队元素存储在数组中存储位置的下标是 填空题 2分

18、将中缀表达式9-（2+4*7）转换为后缀表达式的结果是 填空题 2分

19、广义表G=（27，G）的深度是（ ） 填空题 2分

20、具有n（n=1）个结点的二叉树，采用二叉链表存储，空指针域的个数是（ ） 填空题 2分

21、两个无向连通图均含有10个顶点，它们之间的边数差最大是（ ） 填空题 2分

22、有向图G存在拓扑序列的条件是（ ） 填空题 2分

23、若用C语言的数组A保存含n（n=10）个元素的大根堆，则第3大元素在A中的下标最大是（ ） 填空题 2分

24、分块查找又称为（ ） 填空题 2分

25、非空的3阶B树中，每个非根结点中含有的关键字个数最少是（ ） 填空题 2分

26、链栈为什么不必设置头结点？ 简答题 5分

27、已知字符集（a，b，c，d，e）中各字符出现的频次分别为2，3，6，8，10，对字符集进行哈夫曼编码，字符a的编码是000，字符e的编码是11，则其余3个字符的编码分别是什么？ 简答题 5分

28、设有向图G如题28图所示，给出图G的邻接矩阵。 简答题 5分

29、设有关键字16，15，32，11，6，30，将它们依次保存在哈希表（长度为7的一维数组）中，哈希函数为H（k）=k mod 7，采用线性探查法解决冲突。已知关键字16已放置在数组下标为2的位置。请画出哈希表。 简答题 5分

30、程序f30（）创建了一个带头结点的含n（n=3）个数据结点的单链表L，L前两个数据结点中的data值均为1，从第3个结点开始，结点的data值是其前两个结点data值之和。请在空白处填上适当内容将算法补充完整。 简答题 5分

31、已知图的邻接矩阵表示的存储结构定义如下，算法f31（）统计图中各顶点的度，并返回最大度数。请在空白处填上适当内容将算法补充完整。 简答题 5分

32、已知二叉排序树结点的数据类型定义及二叉排序树的某个算法f32（）如下。 简答题 10分

33、阅读程序，并回答下列问题 简答题 10分

34、设n个整数存放在数组A中，请编写函数f34（int A[]，int n），将所有奇数调整到所有偶数之前。 简答题 15分