全国硕士研究生入学统一考试-数据结构习题集

Houjiuming

2009年全国硕士研究生入学统一考试

计算机科学与技术学科联考 计算机学科专业基础综合

考试大纲 教育部考试中心

中国学位与研究生教育学会工科工作委员会

目 录

I. 考查目标

II. 考试形式和试卷结构考查范围 III. 考查范围

数据结构 计算机组成原理 操作系统 计算机网络 IV.

试题示例

Ⅰ.考查目标

计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的概念、基本原理和方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。

Ⅱ.考试形式和试卷结构

一、试卷满分及考试时间

本试卷满分为150分，考试时间为180分钟 二、答题方式 答题方式为闭卷、笔试 三、试卷内容结构 数据结构 45分

- 1 -

计算机组成原理 45分 操作系统 35分 计算机网络 25分 四、试卷题型结构

单项选择题 80分（40小题，每小题2分） 综合应用题 70分

2009年全国硕士研究生入学统一考试

Ⅲ.考查范围

数据结构

【考查目标】

1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。

2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 3.能够选择合适的数据结构和方法进行问题求解。

一、线性表

（一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用

二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用 （五）特殊矩阵的压缩存储

- 2 -

三、树与二叉树 （一）树的概念 （二）二叉树

1.二叉树的定义及其主要特征

2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历

4.线索二叉树的基本概念和构造 5.二叉排序树 6.平衡二叉树 （三）树、森林 1.书的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 （四）树的应用 1.等价类问题

2.哈夫曼（Huffman）树和哈夫曼编码

四、 图 （一） 图的概念

（二） 图的存储及基本操作 1.邻接矩阵法 2.邻接表法 （三）图的遍历 1. 深度优先搜索 2. 广度优先搜索

（四）图的基本应用及其复杂度分析 1. 最小（代价）生成树 2. 最短路径 3. 拓扑排序

- 3 -

4. 关键路径 五、查找

（一）查找的基本概念 （二）顺序查找法 （三）折半查找法 （四） B-树

（五）散列（Hash）表及其查找 （六）查找算法的分析及应用

六、内部排序 （一）排序的基本概念 （二）插入排序 1.直接插入排序 2.折半插入排序

（三）气泡排序（bubble sort） （四）简单选择排序 （五）希尔排序（shell sort） （六）快速排序 （七）堆排序

（八）二路归并排序（merge sort） （九）基数排序

（十）各种内部排序算法的比较 （十一）内部排序算法的应用

Ⅳ．试题示例

一、单项选择题：1~40小题，每小题2分，共80分。在每小题给出的四个选项中， 请选出一项最符合题目要求的。 试题示例：

- 4 -

1、 下列排序算法中，时间复杂度为O（nlog2n）且占用额外空间最少的是 Ａ．堆排序 C．快速排序

2、 下列序列中，满足堆定义的是

A．（100，86，48，73，35，39，42，57，66，21） B．（12，70，33，65，24，56，48，92，86，33） C．（103，97，56，38，66，23，42，12，30，52，6，26） D．（5，56，20，23，40，38，29，61，35，76，28，100）

二、综合应用题：41~47小题，共70分。 试题示例：

41．（10分）设无向图G=（V，E），其中V={1，2，3，4，5}，E={（1，2，4），（2，5，5），（1，3，2），（2，4，4），（3，4，1），（4，5，3），（1，5，8）}，每条边由一个三元组表示，三元组中前两个元素为与该边关联的顶点，第三个元素为该边的权。请写出图G中从顶点1到其余各点的了短路径的求解过程。要求列出最短路径上的顶点，并计算路径长度。

42.(15分)已知一棵二叉树采用二叉链表存储,结点构造为:

LeftChild Data RightChild ,root指向根结点。现定义二叉树中结点X0 的根路径为从根结点到X0 结点的一条路径，请编写算法输出该二叉树中最长的根路径（多条最长根路径中只输出一条即可。算法可使用C或C + +或JAVA语言实现）。

Ｂ．起泡排序 D．希尔排序

- 5 -

第 1 章 绪论

一、单选题

1、在数据结构中，从逻辑上可以把数据结构分成

A、动态结构和静态结构

B、紧凑结构和非紧凑结构 D、内部结构和外部结构

C、线性结构和非线性结构 2、算法分析的两个主要方面是

A、空间复杂性和时间复杂性 C、可读性和文档性

B、正确性和简明性

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

3、数据的不可分割的最小单位是

A、结点

B、数据元素

C、数据项

D、数据对象

4、在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为

A、规则

B、集合

C、结构

D、运算

5、与程序运行时间有关的因素主要有以下四方面，其中与算法关系密切的是

A、问题的规模

B、机器代码质量的优劣 D、语句的执行次数

C、机器执行速度 二、判断题

1、数据结构是带有结构的数据元素的集合。 2、程序越短，运行的时间就越少。 3、处理同一问题的算法是唯一的。

4、一个完整算法可以没有输入，但必须有输出。 三、填空题

1、______________是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 2、______________结构的数据元素之间存在一对多的关系。

3、数据结构的形式化定义为 (D，S)，其中 D 是______________的有限集，S 是 D 上关系的有限集。

4、数据结构在计算机中的______________称为存储结构。

5、数据元素之间的关系在计算机中有两种不同的表示方法：顺序映象和非顺序映象，由此

- 6 -

得到两种不同的存储结构是______________存储结构和______________存储结构。 6、一个算法具有五个特性：______________、______________、______________、有零个或多个输入、有一个或多个输出。

7、评价一个算法的好坏应该从算法的正确性、可读性、___________和_________________等几方面进行。 四、解答题

1、设n为正整数。试确定下列各程序段中前置以记号@的语句的频度： ⑴ i=1；

k=0； while (i<=n-1) {

@ k+=10*i； i++； } ⑵ i=1；

k=0； do {

@ k+=10*i； i++； } while (i<=n-1)； ⑶ i=1；

k=0； while (i<=n-1) { i++； @ k+=10*i； } ⑷ k=0；

for (i=1；i<=n；i++) {

for (j=i；j<=n；j++) @ k++；

- 7 -

}

2、阅读以下算法： void fun(int n) {

int i，j，k，s，x； for (s=0，i=0；i

j=n； x=0； while (i

printf(\，x=%d\\n\，s，x)； }

⑴分析算法中语句“s++；”的执行次数； ⑵分析算法中语句“x+=2；”的执行次数； ⑶分析算法的时间复杂度。

五、算法设计题

编程实现课本例1-7所描述的抽象数据类型Triplet，并完成以下功能，要求有菜单提示： ⑴初始化三元组为 (100，200，300)； ⑵获取第二个元素值并输出； ⑶置第三个元素值为 150； ⑷获取第三个元素值并输出； ⑸获取最大元素值并输出； ⑹获取最小元素值并输出； ⑺撤销三元组。

- 8 -

第2章 线性表

一、单选题 1．线性表是( ) 。

(A) 一个有限序列，可以为空 (B) 一个有限序列，不能为空 (C) 一个无限序列，可以为空 (D) 一个无序序列，不能为空 2．线性表采用链式存储时，其地址( ) 。

(A) 必须是连续的 (B) 部分地址必须是连续的 (C) 一定是不连续的 (D) 连续与否均可以 3．与顺序表相比，用链表实现线性表的优点是（ ）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同 4．线性表的静态链表结构与顺序存储结构相比优点是( )。 (A)所有的操作算法实现简单 (B)便于随机存取 (C)便于插入和删除 (D)便于利用零散的存储器空间 5．循环链表的主要优点是( ) 。 (A)不在需要头指针了

(B)已知某个结点的位置后，能够容易找到他的直接前趋 (C)在进行插入、删除运算时，能更好的保证链表不断开 (D)从表中的任意结点出发都能扫描到整个链表 6．下面关于线性表的叙述错误的是( )。

(A) 线性表采用顺序存储，必须占用一片地址连续的单元 (B) 线性表采用顺序存储，便于进行插入和删除操作 (C) 线性表采用链式存储，不必占用一片地址连续的单元 (D) 线性表采用链式存储，不便于进行插入和删除操作； 7．假设双链表结点的类型如下： typedef struct linknode { int data ; //数据域

struct linknode *llink;//指向前趋结点的指针域 struct linknode *rlink;//指向后继结点的指针域

- 9 -

} bnode

现将一个q 所指新结点作为非空双向链表中的p 所指结点的前趋结点插入到该双链表中，能正确完成此要求的语句段是( )。

(A) q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q (B) p->llink=q;q->rlink=p；p->llink->rlink=q;q->llink=p->llink (C) q->llink=p->rlink;q->rlink=p;p->link->rlink=q;p->llink=q (D) 以上都不对

8. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是： （A）110 （B）108 （C）100 （D）120

9. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是( ) （A） 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B） 在第i个结点后插入一个新结点（1≤i≤n） （C） 删除第i个结点（1≤i≤n） （D） 将n个结点从小到大排序 10. 链式存储结构所占存储空间（ ）

（A） 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B） 只有一部分，存放结点值

（C） 只有一部分，存储表示结点间关系的指针

（D） 分两部分，一部分存放结点值，另一部分存放结点所占单元数

11. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。 (A) 单链表 (B) 仅有头指针的单循环链表 (C) 双链表 (D) 仅有尾指针的单循环链表

12. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ） （A）n （B）2n-1 （C）2n （D）n-1

13． 线性表L在以下哪种情况下适用于使用链式结构实现（ ） （A）需经常修改L中的结点值 （B）需不断对L进行删除插入 （C）L中含有大量的结点 （D）L中结点结构复杂

14．在一个单链表L中，若要删除由指针q所指向结点的后继结点，则执行（ ）。

- 10 -

（A） p=q->next; p->next=q->next （B） p=q->next; q->next=p （C） p=q->next; q->next; q->next=q （D） q->next=q=->next->next; q->next=q;

15． 在非空双向循环链表中，在由q所指的结点后面插入一个由p所指的结点的过程是依次执行：p->Llink=q,p->Rlink=q->Rlink,q->Rlink=p，（ ）。(括号中应该填上一条赋值语句) （A） q->Llink=p （B） q->Rlink->Llink=p （C） p->Rlink->Llink=p （D） p->Llink->Llink=p

二、判断题

1．线性表的逻辑顺序与存储顺序总是一致的。 2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

4．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 5．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。 6．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。 7．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

8. 如果没有提供指针类型的语言，就无法构造链式结构。

9. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。

10. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 11. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 12. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 13. 在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。 14. 一个循环链表可以由所给定的头指针或者尾指针唯一确定。 三、填空题

1．线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接______外，其他结

- 11 -

点有且仅有一个直接______;除终端结点没有直接______外，其它结点有且仅有一个直接______.

2．线性表的顺序存储结构通过________来直接反映数据元素之间的逻辑关系，而链式存储结构则通过_______间接反映数据元素之间的逻辑关系。

3．线性表的常见链式存储结构有________、________和________。

4．对于长度为n的非空线性表，插入或者删除一个数据元素的操作的时间复杂度为_______。 5．在一个单链表中指针p所指结点之后插入一个由指针s所指结点，应执行s->next=________;和p->next=_____________的操作。

6．在一个单链表中删除指针p所指结点（若存在），则需要修改指针的操作是_______。 7．对于一个长度为n的非空顺序表，删除它的第i个数据元素时，需要移动_____个其他数据元素。

8．在以H为头指针的带表头结点的单循环链表中，链表为空的条件为 。 9.在单链表中，每个结点包含有两个域，一个叫 域，另一个叫 域。

10.在下面数组a中存储着一个静态链表，表头指针为a[0].next，则该线性表为 。

a

0

1

2

3

4

5 6

7

8

data next 4 60 56 42 38 3 7 6 2 74 25 0 1 11．一元多项式f(x) =9x10-3x7+6x-5的单链表表示是____________。 四、解答题

1．何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 2．简述带头结点和不带头结点的单链表的区别。

3．说明在顺序表中实现插入操作和删除操作时为什么必须移动数据元素，以及插入操作和删除操作各自移动数据元素的方向？

4．在单链表和双向链表中，能否从当前结点出发访问到任一结点？ 5. 设有多项式

A(x)=7+3x+9x8+5x17 B(x)=8x+22x7-9x8

(1) 用单链表给出A(x)的存储表示。（画出单链表示意图） (2) 用单链表给出B(x)的存储表示。（画出单链表示意图）

- 12 -

(3) 以上述两个单链表为基础，通过插入和删除等运算得出A(x)+B(x)的存储表示，使其

存储空间覆盖A(x)和B(x)的存储空间。（画出单链表示意图）

五、算法设计题

1．长度为n的递增有序顺序表，请写一的算法，将x插入到顺序表的中，并保持该表的有序性。

2．试写实现顺序表的就地逆置的算法，即利用原表的存储空间将线性表（a1,a2,…,an）逆置成（an,an-1,…,a1） 3．对单链表实现就地逆置。

4．试写一个高效算法，删除单链表中所有大于min且小于max的元素（若表中存在这样的元素）同时释放被删除结点的空间，并分析你的算法的时间复杂度（min和max是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）

5. 已知数组A[1..n]的元素类型为整型。设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为o(n)。

6. 有两个按数据元素值递增有序排列的线性表A和B。编写算法将A表和B表归并成一个按元素值递增有序（即非递减有序，允许值相同）排列的线性表C，并要求利用原表(即A表和B表的)结点空间存放表C。（请分A，B均以顺序表作存储结构和A，B均以单链表作存储结构，这两种情况写算法）。

7. 假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作存储结构。编写算法将A表和B表归并成一个按元素值递减有序（相同值元素只保留一个）排列的线性表C，并要求利用原表(即A表和B表的)结点空间存放表C。

8. 已知一单链表中的数据元素含有三个字符(即:字母字符、数字字符和其它字符)。试编写算法，构造三个循环链表，使每个循环链表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间(头结点可另辟空间)。

9. 已知两个单链表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B的交集C，要求C同样以元素递增的单链表形式存储。

- 13 -

第 3 章 栈、队列和数组

一、单选题

1. 栈中元素的进出原则是( )。

(A) 先进先出 (B)后进先出 (C)栈空则进 (D)栈满则出 2. 栈的插入与删除操作在( )进行。

(A) 栈顶 (B) 栈底 (C) 任意位置 (D) 指定位置

3 .若让元素1，2，3依次进栈，则出栈次序不可能出现（ ）种情况。 （A） 3，2，1 （B） 2，1，3 （C） 3，1，2 （D） 1，3，2

4. 若用一个大小为6 的数组来实现循环队列，且当rear和front的值分别为O和3。当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（ ） （A） l和5 （B） 2和4 （C） 4和2 （D） 5和l 5．一般情况下，将递归算法转换成等价的非递增归算法应该设置( )。 （A）堆栈 （B）队列 （C）堆栈或队列 （D）数组 6．链栈与顺序栈相比，有一个比较明显的优点即 （ ） （A）插入操作更方便 （B）通常不会出现栈满的情况 （C）不会出现栈空的情况 （D）删除操作更方便

7．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队为指针，则执行出队操作的语句为（ ）

(A) front=front+1 (B) front=（front+1）%m (C) rear=(rear+1)%m (D) front=(front+1)%(m+1)

8. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，

则pi为

（A）i （B）n=i （C）n-i+1 （D）不确定

9. 设有一顺序栈T，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是（ ）

（A）2 （B）3 （C） 5 （D）6

10．数组Ｑ［n］用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n，计算队列中元素的公式为

- 14 -

（A）r－f （B）（n＋f－r）% n （C）n＋r－f （D）（n＋r－f）% n 11．中缀表达式A-(B+C/D)*E的后缀形式是（ ） (A) AB-C+D/E* (B) ABC+D/-E* (C) ABCD/E*+- (D) ABCD/+E*-

12．一个算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )。 (A) -A+B*C/DE (B) A+B*CD/E (C) -＋*ABC/DE (D) -＋A*BC/DE

13.循环队列A[0..m-1]存放其元素，用front和rear分别表示队头和队尾，则循环队列满的条件是（ ）。

（A）（Q.rear+1）%m==Q.front (B) Q.rear==Q.front+1 (C) Q.rear+1==Q.front (D) Q.rear==Q.front

14.解决计算机主机和打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个（ ）结构

（A）栈 （B）队列 （C）线性表 （D）数组 15.假设顺序栈的定义为： typedef struct {

selemtype *base; /* 栈底指针*/ selemtype *top; /* 栈顶指针*/

int stacksize; /* 当前已分配的存储空间,以元素为单位*/ }sqstack;

变量st的类型为sqstack，则栈st为空的判断条件为（ ）。 （A）st.base == NULL （B） st.top == st.stacksize （C） st.top-st.base>= st.stacksize （D） st.top == st.base

16．对于以行序为主序的存储结构来说，在数组A[c1···d1，c2···d2]中，c1和d1分别为数组A的第一个下标的上、下界，c2…d2分别为第二个下标的上、下界，每个数据元素占K个存储单元，二维数组中任一元素A[i,j]的存储位置可由( )式确定. (A) Loc[i,j]=[( d2-c2+1)(i- c1)+(j- c2)]*k

(B) Loc[i,j]=loc[c1, c2]+[( d2- c2+1)(i- c1)+(j- c2)]*k (C) Loc{i,j}=A[c1, c2]+[( d2- c2+1)(i- c1)+(j- c2)]*k (D) Loc[i,j]=loc[0,0]+[( d2- c2+1)(i- c1)=(j- c2)]*k

- 15 -

2、 一个图采取以下结构，完成下列遍历算法。

void BFSTraverse(Graph G, Status (*Visit)(int v)) { for (v=0; v

visited[v] = FALSE; //初始化访问标志 InitQueue(Q); // 置空的辅助队列Q for ( v=0; v

if ( ) { // v 尚未访问

visited[v] = TRUE; Visit(v); // 访问u EnQueue(Q, v); // v入队列 while (!QueueEmpty(Q)) {

DeQueue(Q, u); // 队头元素出队并置为u

for(w=FirstAdjVex(G, u); w>=0; w=NextAdjVex(G,u,w)) if ( ! visited[w]) { visited[w]= ; Visit(w);

EnQueue(Q, w); // 访问的顶点w入队列

} // if

} // while

} //if } // BFSTraverse

3、编程实现：用邻接表的存储方法创建一个图。 4、编程实现：对3题建立的图进行深度优先搜索。

- 31 -

第 9 章 查找

一、单选题

1、静态查找表与动态查找表两者的根本差别在于 A、逻辑结构不同 B、 存储实现不同 C、施加的操作不同 D、 数据元素的类型不同

2、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 Ａ、n

B、n/2 C、(n+1)/2 D、(n-1)/2

。

。

。

3、对线性表进行二分查找时，要求线性表必须 A、以顺序方式存储

B、以链式方式存储

C、以顺序方式存储，且结点按关键字有序排序 D、以链式方式存储，且结点按关键字有序排序

4、在表长为n的顺序表中进行顺序查找，在查找不成功时，与关键字比较的次数为 。

A、n B、1 C、 n+1 D、n-1

5、对于有序表（2，5，7，11，22，45，49，62，71，77，90，93，120），折半查找值为90的结点时，经过 比较后查找成功。

A、 1 B、 2 C、4 D、5 6.快速排序在最坏情况下的时间复杂度是( )。 A、O(log2n) B、O(nlog2n) C、O(n2) D、O(n3)

7、如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用 查找方法。

A、分块 B、顺序 C、二分 D、散列

8、有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情 况下查找成功所需的平均比较次数为

。

A、35／12 B、37／12 C、39／12 D、43／12 9、当采用分块查找时，数据的组织方式为 A、数据分为若干块，每块内数据有序

B、数据分为若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）

- 32 -

。

的数据组成索引块

C、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D、数据分为若干块，每块（除最后一块外）中数据个数需相同 10.在排序过程中，键值比较的次数与初始序列的排列顺序无关的是()。 A、直接插入排序和快速排序 B、直接插入排序和归并排序 C、直接选择排序和归并排序 D、快速排序和归并排序和归并排

11、从键盘依次输入关键字的值：t,u,r,b,o,p,a,s,c,l。建立二叉排序树，则先序遍历序列为 。

A、 abcloprstu B、 alcpobsrut C、 trbaoclpsu D、 trubsaocpl

12、设有一组记录的关键字为{19，24，23，1，68，20，84，27，55，11，10，79}，用链地址法构造哈希表，哈希函数为H(KEY)=KEY MOD 13 ,哈希地址为1的链中有 个记录。

A、1 B、2 C、3 D、4

13、在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的健值

。

A、一定都是同义词 B、 一定都不是同义词 C、都相同 D 、健值不一定有序的顺序表

14、设哈希表长为14，哈希函数为H(key)= key mod 11,表中已经有4个结点：addr(14)=3, addr(38)=5, addr(61)=6, addr(85)=8,其余地址为空,用线性探测再散列法解决冲突，关键字为49的结点的地址为 。

A、7 B、3 C、5 D、 4

15、设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经

次比较后查找成功。

A、2 B、 3 C、 4 D、 12

16、已知一采用开放地址法解决Hash表冲突，要从此Hash表中删除一个记录，正确的做法是

。

A、将该元素所在的存储单元清空。 B、将该元素用一个特殊的元素代替

C、将与该元素有相同Hash地址的后继元素顺次前移一个位置。 D、用与该元素有相同Hash地址的最后插入表中的元素替代。

- 33 -

17、以下说法错误的是 。

A、数字分析法对健值的各位进行分析，选择分布较均匀的若干位组成散列地址。 B、除余法选择一个适当的正整数p,以p除健值以所得的余数作为散列地址。 C、平方取中法以健值平方的中间几位作为散列地址。

D、基数转换法将健值看成另一种进制的数再转换成原来进制的数，然后选择其中几位作为散列地址。

18、下面关于B-树和B+树的叙述中，不正确的是 。

A、B-树和B+树都是平衡的多叉树 B、B-树和B+树都可用于文件的索引结构 C、B-树和B+树都能有效地支持顺序检索 D、B-树和B+树都能有效地支持随机检索 19、下列关于m阶B-树的说法错误的是 。

A、根结点至多有m棵子树。 B、 所欲叶子都在同一层 C、非叶子结点至少有m/2(m为偶数)或m/2+1（m为奇数）棵子树 D、根结点中的数据都是有序的。

20、一棵3阶B-树中含有2047个关键字，包含叶结点层，该树的最大深度为 A、11 B、12 C、13 D、 14

21、一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有 个结点。

。

A、2k-1-1 B、 2k-1 C、2k-1+1 D、2k-1

22、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是 。

A、 (100,80,90,60,120,110,130) B 、(100,120,110,130,80,60,90) C 、(100,60,80,90,120,110,130) D 、(100,80,60,90,120,130,110)

23、设二叉排序树中关键字由1至1000的整数构成,现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树上查到的序列？ A、2，252，401，398，330，344，397，363； B、924，220，911，244，898，258，362，363； C、925，202，911，240 ，912，245，363；

D、2，399，387，219，266，382，381，278，363。

- 34 -

24、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作 A 、LL B、 LR C、 RL D、 RR

二、判断题

1、n个数放在一维数组中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。

2、若散列表的装填因子小于1，则可避免碰撞的产生。 3、哈希表的平均查找长度与处理冲突的方法无关。 4、对无序表用折半法查找比顺序查找法快。

5、在二叉排序树中插入一个新结点，总是插入到叶节点下面。

6、平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。

7、对两棵具有相同关键字而形状不同的二叉排序树，按中序遍历得到的序列却是一致的。 8、完全二叉树肯定是平衡二叉树

9、在9阶B-树中，除叶子以外的任意结点的分支数介于5和9之间。

10、如果完全二叉树从根结点开始按层次遍历的序列为1，2，3，4，5，6，7，则该完全二叉树是二叉排序树。

11、m阶B-树的任何一个结点的左右子树高度都相等。

12、设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。 13、对给定的关键字集合,以不同的次序插入初始为空的树中,将得到同一棵二叉排序树。 三、填空题

1． 动态查找表和静态查找表的重要区别在于前者包含有 后者不包含这两种运算。

2．对n个记录的表中进行折半查找，最大比较次数是 。

和 运算，而

型调整以使其平衡。

3．顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为 次；当使用监视哨时，若查找失败，则比较关键字的次数为

。

4．已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用二分法查找90时，需

次查找成功，查找47时需 次成功，查找100时，需 次才能确定不成功。

- 35 -

本文来源：https://www.bwwdw.com/article/juxx.html