数据结构期末测验

数据结构期末测验

1.使用双链表存储线性表，其优点是可以()［单选题］*

A.提高查找速度

B.更方便数据的插入和删除

C.节约存储空间

D很快回收存储空间

2.下面几种算法时间复杂度中，时间复杂度最高的是()。［单选题］*

A.O(nlog2n)

B.O(n2)

C.O(n)

D.0(2n)(正确答案)

3.线性表(al,a2,…,an)以链接方式存储时，若指针指向头结点，则访问第i个元

素的时间复杂度为(”单选题］*

A.0⑴

B.O(1)

C.O(n)(正确答案)

D.O(i-1)

4.串是一种()［单选题］*

A.链式存储的线性结构

B.链式存储的非线性结构

C.限制元素类型的线性结构

D.限制存取点的非线性结构

5.设顺序线性表中有n个数据元素，则删除表中第i个（从1开始计数）元素需要

移动（）个元素。［单选题］*

A.n-i（正确答案）

B.n+1-i

C.n-1-i

D.i

6.从19个元素中查找其中某个元素，如果最多进行5次元素之间的比较，则采用

的查找方法只可能是（）。［单选题］*

A.折半查找,箜案।

B.分块查找

C.顺序查找

D渚R不可能

7.在含有12个结点的平衡二叉树上，查找关键字为35（存在该结点）的结点，则

依次比较的关键字有可能是（）。［单选题］*

A.46,36,18,20,28,35

B.47,37,18,27,36

C.27,48,39,43,37

D.15,45,25,351确答案）

8.一个递增表为RO.11］,采用折半查找方法，在某次成功查找到指定的记录时，

以下0是可能的记录比较序列。［单选题］*

A.R[0],R[5]、R[2]

B.RfOKR[6]、Rf9]

C.R[5]、R[8],RflOl

D.R[5]XR[2]sR[4]

9.当采用分块查找时，数据的组织方式为（）。［单选题］*

A.数据分成若干块，每块内数据有序

B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最

小）的数据组成索引块

C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块

D.数据分成若干块，每块中的数据个数必须相同

10.设待查找元素为47,且已存入变量k中，如果在查找过程中，和k进行比较的

元素依次是47、32、46、25、47,则所采用的查找方法（）。［单选题］*

A.是一种错误的方法

B.可能是分块查找弓答案）

C.可能是顺序查找

D.可能是折半查找

H.用n个关键字构造的一棵二叉排序树，经过i次关键字比较成功找到的元素个

数最多为（）。［单选题］*

A.i

B.2i

C.2i-1（正确答案）

D.2i-1

12.对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是

（）o［单选题］*

A.95,22,91,24,94,71正确答案）

B.92,20,91,34,88,35

C.21,89,77,29,36,38

D.12,25,71,68,33,34

13.以下关于哈希查找的叙述中错误的是（）。［单选题］*

A.用拉链法解决冲突易引起堆积现象

B.用线性探测法解决冲突易引起堆积现象

C.哈希函数选得好可以减少冲突现象

D.哈希函数H（k）=kMODp,p通常取小于等于表长的素数

14.一棵高度为h的并且只有h个结点的二叉树，采用顺序存储结构存放在R［l..n］

中，则n应该至少是（）o［单选题］*

A.2h

B.2h-1

C.2h-1（正确答案）

D.2h

15.一棵哈夫曼树中共有199个结点，它用于（）个字符的编码。［单选题］*

A.99

B.100（正确答案）

C.101

D.199

16设哈夫曼编码的长度不超过4,若已对两个字符编码为1和01,则最多还可对

（）个字符编码。［单选题］*

A.2

B.3

C.4-:确答窠）

D.5

17.有一棵含有8