1、下列数据结构中，逻辑结构不同的是 单选题 2分

2、将l6个数据元素的线性表按顺序存储方式存储在数组中，若第一个元素的存储地址是l000，第6个元素的存储地址是1040，则最后一个元素的存储地址是 单选题 2分

3、设栈的初始状态为空，元素1，2，3，4，5依次入栈，不能得到的出栈序列是 单选题 2分

4、设指针变量P指向非空单链表中的结点，next是结点的指针域，则判断P所指结点为尾结点前一个结点的逻辑表达式中，正确的是 单选题 2分

5、已知广义表LS=(((a，b，c)，d)，(e，(fg，(h i)))，LS的深度是 单选题 2分

6、已知一棵完全二叉树T的第5层上共有5个叶结点，则T中叶结点个数最少是 单选题 2分

7、已知二叉树T的前序遍历序列为a，b，c，e，d，中序遍历序列为C，e，b，d，a，则T的后序遍历序列为 单选题 2分

8、有向图G有玎个顶点和e条边，G保存在邻接矩阵M中，M中0与1的个数差是 单选题 2分

9、有向图G中所有顶点的度数之和是24，则G中弧的数量是 单选题 2分

10、设有向图G含有n个顶点、e条边，使用邻接表存储。对G进行深度优先搜索遍历算法的时间复杂度是 单选题 2分

11、对数据序列(26，14，17，12，7，4，3)采用二路归并排序进行升序排序，两趟排序后，得到的排序结果为 单选题 2分

12、下列选项中，不稳定的排序方法是 单选题 2分

13、一组记录的关键字为(35，48，47，23，44，88)，利用堆排序算法进行降序排序，建立的初始堆为 单选题 2分

14、一棵二叉排序树中，关键字n所在结点是关键字m所在结点的孩子，则 单选题 2分

15、设敖列表长m=16，散列函数H(key)=key％15。表中已保存4个关键字：addr(18)=3，addr(35)=5，addr(51)=6，addr(22)=7，其余地址均为开放地址。存储关键字36时存在冲突，采用线性探测法来处理。则查找关键字36时的探查次数是 单选题 2分

16、数据项是具有独立含义的（ ）标识单位。 填空题 2分

17、指针P和q分别指向单链表L中的两个相邻结点，即q->next=P。若要在q所指结点后插入指针r所指结点，则执行的语句是r->ne处=p；（ ）。 填空题 2分

18、递归算法设计中的最小子问题称为递归的（ ）。 填空题 2分

19、广义表((a，b)，(c，d)，e，(f (g,h)))的表尾是（ ）。 填空题 2分

20、已知二叉树的前序遍历序列和后序遍历序列，则对应的二叉树（ ）确定。 填空题 2分

21、如果有向无环图G中仅有一个顶点的入度为0，若要求G的拓扑序列不唯一，则G中必须存在一个出度至少为（ ）的顶点。 填空题 2分

22、将森林T转换为一棵二叉树T1，在T中结点A是结点B的右邻的兄弟(下一个兄弟)，则在T1中，A是B的（ ）结点。 填空题 2分

23、对含玎个元素的数据序列采用快速排序算法进行排序，平均时间复杂度是（ ）。 填空题 2分

24、散列存储中，常用的解决冲突的方法有开放地址法和（ ）两大类。 填空题 2分

25、假设顺序存储的有序表R含有8个关键字，进行二分查找时，平均查找长度为（ ）。 填空题 2分

26、设电文字符集是{el，e2，e3，e4，e5)，各字符出现的次数分别为{36，l3，26，l8，23}。现要为该字符集设计哈夫曼编码。请回答下列问题。    (1)给出构造的哈夫曼树。    (2)给出各字符的哈夫曼编码。    (3)计算电文编码总长。 简答题 5分

27、已知图G采用邻接矩阵存储，邻接矩阵如题27图所示。(1)根据邻接矩阵画出图G。(2)根据图G写出从顶点A开始图G的1个深度优先搜索遍历序列。(3)根据图G写出从顶点A开始图G的1个广度优先搜索遍历序列。 简答题 5分

28、有数据序列(12，l7，O5，l0，20，24，45，ll，l0，l2)，使用希尔排序方法将其排成升序序列。请回答下列问题。 (1)分别写出增量为3和1的希尔排序结果。 (2)计算第一趟希尔排序中数据元素之间的总交换次数(两个(a)元素之间的交换记l次)。 简答题 5分

29、设有二叉排序树T如题29图所示。现需在T中删除结点e，请回答下列问题。       (1)画出删除后的二叉排序树(仅需画出一棵)。    (2)在你实现的删除过程中，指针域更新的次数是多少? 简答题 5分

30、顺序表类型定义如下： 简答题 5分

31、 简答题 5分

32、 简答题 10分

33、 简答题 10分