数据结构模拟题壹_原题

一、选择题(共20分，共10题，每题2分)

1. 对于顺序存储的线性表，访问某个元素和增加一个元素的时间复杂度()。

A．O(n), O(n)B．O(n), O(1)C．O(1), O(n)D．O(1), O(1)

2. 若链表中的常用操作是在最后一个节点之后插入一个节点和删除最后一个节点，则采用()存储方法最节省运算时间。A．单链表 B．循环双链表

C．循环单链表 D．带尾指针的循环单链表

3. 队列的先进先出特性是指()。

A．最后插入队列中的元素总是最后被删除

B．当同时进行插入删除操作时，总是插入操作优先

C．每当有删除操作时，总要先做一次插入操作

D．每次从队列中删除的总是最早插入的元素

4. 设有一个空栈，栈顶指针为1000H(十六进制)，每个元素需要2个单位的存储空间，则执行PUSH，PUSH，POP，PUSH，POP，PUSH，POP，PUSH操作后，栈顶指针值为()。A．1002H B．1003H C．1004H D．1005H

5. 一个栈的入栈序列是{1,2,3,4,5}，则栈不可能的输出序列是()。

A．{5,4,3,2,1}B．{4,5,3,2,1}C．{4,3,5,1,2}D．{1,2,3,4,5}

6. 下列说法中，正确的是()。

A．二叉树是度为2的树 B．二叉树不存在度大于2的节点C．二叉树是有序树 D．二叉树中每个节点的度均为2

7. 建立线索二叉树的目的是()。

A．方便查找节点的前驱和后继 B．方便二叉树删除和插入C．方便查找某节点的双亲 D．使二叉树的遍历结果唯一

8. 无向图中，所有顶点的度数之和等于所有边数的()倍。A．1/2B．1C．2D．4

9. 静态查找和动态查找的根本区别在于()。

A．它们的逻辑结构不一样 B．施加在其上的操作不同C．所包含的数据元素类型不一样 D．存储实现不一样

10. 关于排序，下列说法正确的是()。

A．稳定排序优于不稳定的排序方法，稳定排序效率较高B．不同的排序方法进行排序，得到的排序结果可能不同C．在链表上无法实现排序方法

D．在排序表上实现的排序方法在链表上也可以实现

二、填空题(共10分，共10题，每空1分)

1.按照二叉树的定义，具有3个节点的二叉树有 种。

2.具有10个顶点的无向连通图最少有 条边，最多则

有 条边。

3.在含有n个结点的二叉排序树中查找一个关键码，最多

进行 次比较。4.在堆排序、快速排序和归并排序中，若只从存储空间考

虑，则应首先选取 方法，其次选取 方

法，最后选取 方法。

5.有n个顶点的有向图至多有 条弧，有n个顶点

的强连通有向图至少有 条弧。

6.从时间复杂度方面考虑，在带权的无向图中求最小生成

树，Prim算法适合 图。

三、简答题(共20分，共4题，每题5分)

1. 单链表设置头节点的作用是什么？

2. 若频繁地对一个线性表进行插入和删除操作，选用什么存储结构比较好？为什么？

3. 简述顺序队列假溢出的避免方法及队列满和空的判定条件。

4. 简述什么是递归程序？递归程序的优、缺点是什么？递归程序在执行时，应借助于什么来完成？递归程序的入口语句、出口语句一般用什么语句实现？

四、算法原理题(共30分，共6题，每题5分)

1. 将关键字序列(7、8、1、2、13、28)散列存储到散列列表中，散列表的存储空间是一个下标从0开始到6的一个一维数组。散列函数为：()mod7

H key key

，处理冲突采用线性探测再散列法。①请画出所构造的散列表；②分别计算等概率情况下，查找成功的平均查找长度。

2. 给定输入元素的序列为{20,35,40,15,30}。请根据输入序列构造排序二叉树。

3. 某字符串S中共有8种字符，各种字符出现的次数分别为2次、1次、4次、5次、7次、3次、4次和9次。对该字符串进行0/1哈夫曼前缀编码，问该字符串的编码至少有多少位？

4. 如图中所示A、B、C、D、E、F、G、H所构成8顶点无向图，求出从A出发的广度优先生成树。

5. 如图中所示A、B、C、D、E所构成5顶点有向图。请绘制

它的逆邻接表。

6. 给定下图AOV网，求它的拓扑排序序列，并用标号法计算

其关键路径。

V1

( 111, , )

五、算法设计题(共20分，共2题，每题10分)

1. 设计算法实现将单链表就地逆置。C语言实现。

2. 二叉排序树通常采用二叉链表存储，请写出交换左右子树的

算法。C语言实现。