数据结构与算法模拟卷(1)(2)(3)

浙江大学远程教育学院试卷

模拟考卷（1）

1. 下列算法的时间复杂性是O(n)。 sum = 0;

for(i=n; i>=0; i--) for(j=0; j

2. 在n个元素的顺序表中删除第i个元素，需要移动n-i个元素。 3. 线性表就是每个元素都有唯一的前驱元素和唯一的后继元素。 4. 判断顺序储存下堆栈s是空的条件是s.top==0。 5. 队列中输出元素的次序总是和输入元素的次序一致。 6. 空字符串就是长度为0的字符串。 7. n(n>0)个结点的树有n-1条边。

8. 二叉树中第3层结点数至多是4个结点。

9. 若用双亲表示法存储树，则无法找到结点的所有孩子结点。 10. 满二叉树一定是完全二叉树，反之亦然。 11. 5个顶点的无向图最多可能有20条边。 12. 连通图的连通分量就是它自己。

13. 有向图各顶点入度之和就等于边的数量。 14. 不连通的图不能用深度优先遍历各个顶点。 15. 图的生成树包含了图的全部顶点。 16. 一般来说，二分查找比顺序查找快。

17. n(n>0)个结点的二叉排序树至多有log2n层。 18. 对二叉树进行中序遍历得到的序列一定有序表。 19. 二叉排序树一般用于查找某个元素。

20. 序列｛12, 23, 15, 24, 26, 14, 16, 30, 27｝是一个堆。

2

1. 算法分析的目的是分析算法的效率以求改进，算法分析的两个主要方面是 __________ 。

第 1 页(共6页)

A空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性

D.数据复杂性和程序复杂性

2. 判定一个循环队列QU(最多元素为m)为空队列的条件是___________。

A.QU->front==QU->rear B.QU->front!=-QU->rear

C.QU->front==(QU->rear+1)% m D.QU->front!=(QU->rear+1)% m

3.在一个单链表中，已知p所指结点不是最后结点，在p之后插入s所指结点，则执行 _____ 。

A. s->next = p; p->next=s; B. s->next = p->next; p->next = s; C. s->next = p->next; p = s; D. p->next = s; s->next = p;

4. 数组A中，每个元素的长度为4个字节，行下标i从1到8，列下标j从1到10，从首地 址100开始连续存放在存储器内，存放该数组至少需要的单元素是 ____________________ 。

A. 80 B. 180 C. 320 D. 420 5. 在下列叙述中，正确的是 _____________ 。

A. 数据的逻辑结构要考虑数据元素本身的内容

B. 不同类型的数据元素可以归类到同一的逻辑结构中 C. 数据元素之间的关联关系在数据的逻辑结构中体现 D. 数据元素是数据不可分割的最小标识单位

6. 将递归算法转换成对应的非递归算法时,通常需要使用 ____________ 。

A.栈 B.队列 C链表 D树

7. 按照二叉树的定义，具有2个及2个以下结点的二叉树有_______________种。 A. 2 B. 3 C. 4 D. 5

8. 已知一有向图的邻接表存储结构如图所示

（a）根据有向图的深度优先遍历算法，从v1顶点出发，所得到的顶点序列是___________。 A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5 C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2

（b）根据有向图的宽度优先遍历算法，从v1顶点出发，所得到的顶点序列是___________。 A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5 C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v2

10.如果某二叉树的前序为stuwv，中序为uwtvs，那么该二叉树的后序___________ 。

A. uwvts B. vwuts C. wutsv D. wuvts

11. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要___________ 条边。

第 2 页(共6页)

A. n B. n+1 C. n/2 D. n-1

12. 串是一种特殊的线性表，其特殊性体现在 _____________。

A.只能顺序存储 B.数据元素是一个字符 C.可以链接存储 D.数据元素可以是多个字符

13. 在循环双链表的p所指结点之后插入s所指结点的操作是_________________ 。

A. p->right=s;s->left=p;p->right->left=s;s->right=p->right; B. p->right=s;p->right->left=s;s->left=p;s->right=p->right; C. s->left=p;s->right=p->right;p->right=s;p->right->left=s; D. s->left=p;s->right=p->right; p->right->left=s;p->right=s;

14. 快速排序方法在___________情况下最不利于发挥其长处。

A. 要排序的数据量太大 B. 要排序的数据中含有多个值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数

15. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是_______________。 A. 插入排序 B.选择排序 C.快速排序 D. 归并排序

16. 用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下，则采用的排序方法是_______________。 （1）25，84，21，47，15，27，68，35，20 （2）20，15，21，25，47，27，68，35，84 （3）15，20，21，25，35，27，47，68，84 （4）15，20，21，25，27，35，47，68，84

A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序 17．关于图的邻接矩阵，下列结论 _____________是正确的。

A. 有向图的邻接矩阵总是不对称的 B. 无向图的邻接矩阵总是不对称的

C. 有向图的邻接矩阵可以是对称的，也可以是不对称的 D. 无向图的邻接矩阵可以是不对称的，也可以是对称的 18. 在长度为n 的双链表中某结点（已知其地址）之前，插入一个新结点的时间复杂度是_________。

2

A. O(n) B. O(1) C. O(log2n) D. O(n)

19. 给定字符串 “this_is_a_string”，如果用一个字节存储一个字符，那么存储这个串需要_______(a)位存储空间，而用Huffman 编码，则只需要____________________(b)位存储空间。

A. 36 B. 49 C. 70 D. 128

第 3 页(共6页)

四、综合计算简答题（共 5 小题，共 27 分）

1. 举出树结构的两个应用实例，并说明树的某个操作对应在实例中的意义。( 5 分)

2. 判断序列（16，19，10，15，4，23，36，20）是否为（小顶）堆？为什么？如果不是，请按照建立堆的思想把它调整为堆，并用图表示建堆的过程。( 6 分)

第 4 页(共6页)