数据结构模拟题(开卷)

《数据结构》模拟题（补）

一． 单项选择题

1. 在线性表的下列存储结构中，读取元素花费时间最少的是【 】。

A．单链表

B．双链表

C．顺序表

D．循环链表

2. 设计一个判定表达式中左、右括号是否配对出现的算法，采用【 】数据结构最佳。

A．集合

B．线性表

C．队列

D．栈

3. n个结点的线索二叉树上含有的线索数为【 】。

A．2n

B．n-1

C．n

D．n+1

4. 设广义表D=(a,(b,c)),则tail(D）=【 】。

A．b,c B．(b,c) C．((b,c)) D．c 5. 由4个结点可以构造出【 】种不同的二叉树。

A．12

B．13

C．14

D．15

6. 在栈中，出栈操作的时间复杂度为【 】。

A．O(1)

B．O(n)

C．O(log2n)

D．O(n)

2

7. 假设Q[0..len-1]表示循环队列，f为队头指针，r为队尾指针，则进队操作语句是【 】。

A．f=f+1

B．r=r+1

C．f=(f+1)%len D．r=(r+1)%len

8. 一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【 】。

A．n*n

B．n*n/2

C．n*(n+1)/2

D．(n+1)*(n+1)/2

9. 队列操作的原则是【 】。

A．进优于出

B．出优于进

C．先进先出

D．后进先出

10. 下列数据结构中，【 】是非线性数据结构。

A．栈

B．串

C．队列

D．树

11. 两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【 】。

A．p==q

B．q->next=p C．p->next=q D．p->next=q->next

12. 数组A中，每个元素的长度为4个字节，行下标i从1到5，列下标j从1到4，从首

地址SA开始连续存放在存储器内，该数组按行存放时，元素A[3][2]的起始地址为【 】。 A．SA+20

B．SA+36

C．SA+40

D．SA+45

13. 已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1，

则第i个结点的地址为【 】。 A．d1+(i-1)*m

B．d1+i*m

C．d1+(i+1)m D．d1-i*m

14. 分析下列算法suanfa1(n)的时间复杂度是【 】。 void suanfa1(int n) { int i,j,x=1； for(i=0；i第1页（共6页）

中国地质大学（北京）继续教育学院 2016年03课程考试

for(j=0；jA．O(2n)

B．O(2)

n

C．O(n)

2

D．O(n+2)

2

15. 将一个A[1..10,1..10]的三对角矩阵，按行优先存入一维数组B[1,30]中，A中元素

a[6,5]在B数组中的位置i为【 】。 A．15

B．16

C．55

D．65

16. 深度为6的二叉树最多有【 】个结点。

A．62

B．63

C．

C．65

17. 由3个结点可以构造出【 】种不同的二叉树。

A．2

B．3

C．4

D．5

18. 栈的插入和删除操作在【 】进行。

A．栈顶

B．栈底

C．指定位置

D．随机位置

19. 数组A中，每个元素的长度为3个字节，行下标i从1到5，列下标j从1到4，从首

地址SA开始连续存放在存储器内，该数组占用的字节数为【 】。 A．20

B．60

C．80

D．120

20. 下面语句的时间复杂度为【 】。

s=0;

for(i=1;i<=n;i++) s=s+i;

A．O(n)

B．O(n) C．O(5) D．O(n)

5

n

2

21. 二叉树中，叶子的数组等于【 】。

A．度为2的结点数加1 C．度为2的结点数

B．度为2的结点数减1 D．度为2的结点数的两倍

22. 数制转换的算法，采用【 】数据结构最佳。

A．集合

B．线性表

C．队列

D．栈

23. 线性表采用链式存储时，其地址是【 】。

A．必须是连续的

B．一定是不连续的 D．连续或不连续都可以

C．部分地址必须是连续的

24. 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为【 】。

A．物理结构

B．逻辑结构 D．链式存储结构

C．顺序存储结构

25. 两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【 】。

A．p==q

B．q->next=p D．p->next=q

第2页（共6页）

C．p->next=q->next

中国地质大学（北京）继续教育学院 2016年03课程考试

26. 线性表在【 】时, 宜用顺序表作存储结构。

A．经常随机存取

B．经常作插入、删除 D．经常作动态增减

C．无足够连续存储空间

二、 判断题

1. 【 】二叉排序树中每个结点的关键字值大于其左非空孩子（若存在的话）的关键

字值，且小于其右非空孩子（若存在的话）结点的关键字值。

2. 【 】算法必须具备的5个特征是：有穷性、确定性、可行性、有0或多个输入量，

至少有1个输出量。

3. 【 】完全二叉树的某结点若没有左孩子，则它必是叶子结点。 4. 【 】哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。 5. 【 】空栈就是所有元素都为0的栈。

6. 【 】在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表

是一种随机存取结构。

7. 【 】n*n对称矩阵经过压缩存储后占用的存储单元是原来的1/2。 8. 【 】一个栈的输入序列是12345，则栈的输出序列可以是312。

9. 【 】对于一个非空二叉树，它的根节点作为第一层，则第i层上最多能有2个

结点。

10. 【 】稀疏矩阵压缩存储后，必会失去随机存取功能。 11. 【 】完全二叉树中，若一个结点没有左孩子，则它必是树叶。

12. 【 】用带表头结点的单链表表示队列，则判断队列为空的标准是头指针和尾指针

均指向同一个结点。

13. 【 】做进栈运算时应先判别,栈是否为空。 14. 【 】广义表中原子个数即为广义表的长度。

三、 填空题

1. 数据结构包含四种基本结构，它们是集合、【 1 】、树形结构、【 2 】。

2. 二叉树的深度为k的二叉树最多有【 3 】个结点，其中第i层最多有【 4 】个结点。 3. n个结点的完全二叉树，使用一维数组t存储结点元素的值，假设t[i]存储第i个结点，

那么t[i]的双亲是【 5 】，左小孩是【 6 】，右小孩是t[2*i+1]。

4. 由权值分别为11,8,6,2,5的叶子结点生成一颗哈夫曼树，它的带权路径长度为【 7 】。 5. 若串s=\"hello\"，其子串个数是【 8 】。

6. 将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结

点的编号为1。编号为24的结点X的左孩子编号为【 9 】，右孩子编号为【 10 】。 7. 长度为n的单链表链接在长度为m的单链表之后的算法时间复杂度为【 11 】。

第3页（共6页）

i-1

中国地质大学（北京）继续教育学院 2016年03课程考试

8. WPL(T)指的是树的【 12 】，即每个叶子的权与根到该叶子的路径长度的乘积之和。 9. 深度为k且有【 13 】个结点的二叉树称为满二叉树。 10. 3层完全二叉树至少有【 14 】个结点。

四、简答题

1. 画出二叉树的5种基本形态。

2. 线性表的顺序存储结构相比链式存储结构，有什么优缺点？适用于什么情况的存储？ 3. 已知一颗非空二叉树，按前序遍历的结果是ACBGDEHFJI，按中序遍历的结果是

CGBAHEDJFI，请画出该二叉树，并写出后序遍历的序列结果。

4. 若比较频繁的对一个线性表进行插入和删除操作，该线性表适合采用哪种存储结构？为 5. 简述二叉排序树（二叉查找树）的定义及特点。

参： 一．单项选择题 1 C 11 A 21 A 二．判断题 1 √ 8 × 三．填空题

1 线性结构 2 图状结构 3 2-1 k2 A 12 A 22 D 3 D 13 B 23 D 4 C 14 B 24 C 5 B 15 C 25 D 6 D 16 B 26 A 7 C 17 D 8 C 18 A 9 C 19 B 10 B 20 A 2 × 9 √ 3 × 10 √ 4 √ 11 √ 5 √ 12 √ 6 √ 13 × 7 × 14 × 4 2 i-15 t[i/2] 第4页（共6页）

中国地质大学（北京）继续教育学院 2016年03课程考试

6 t[2*i] 11 O(n) 四、简答题

7 32 12 带权路径长度 8 15 13 2-1 k9 48 14 4 10 49 1. 画出二叉树的5种基本形态。

2. 线性表的顺序存储结构相比链式存储结构，有什么优缺点？适用于什么情况的存储？

优点：1）是一种随机存储结构，存取任何元素的时间是一个常数，速度快；2）结构简单，逻辑上相邻的元素在物理上也是相邻的；3）不使用指针，节省存储空间。

缺点：1）插入和删除元素要移动大量元素，消耗大量时间；2）需要一个连续的存储空

间；3）插入元素可能发生“溢出”；4）自由区中的存储空间不能被其他数据占用（共享）。 适用于经常用于检索、存取元素，但是插入和删除元素操作较少的情况。

3. 已知一颗非空二叉树，按前序遍历的结果是ACBGDEHFJI，按中序遍历的结果是

CGBAHEDJFI，请画出该二叉树，并写出后序遍历的序列结果。 二叉树：

后序遍历的结果是GBCHEJIFDA

4.若比较频繁的对一个线性表进行插入和删除操作，该线性表适合采用哪种存储结构？为什

第5页（共6页）

中国地质大学（北京）继续教育学院 2016年03课程考试

么？时间复杂度是多少？

链式存储结构。

因为链式存储的线性表，插入和删除操作只需要改变指针，时间复杂度为O（1），而采用顺序存储结构的线性表插入和删除涉及到数据的大量移动，时间复杂度为O（n）。 5.简述二叉排序树（二叉查找树）的定义及特点。

定义：如果二叉树的任一结点大于其非空左子树的所有节点，而小于等于其非空右子树的所有结点，则这棵二叉树称为二叉排序树。

特点：对一颗二叉排序树进行中序排序，所得的结点序列一定是递增有序的。

第6页（共6页）