数据结构_模拟测验题全部(带答案).doc

题型：
填空题 （10题，每空1分，10分）
判断+改错 (5-10题，每题1-2分，10-20分)
选择题 （15-20题，每题1分，15-20分）
综合题 （5-7个大题，共35-40分）
程序题 （2-3题，共10-15分）

综合题
二叉树的顺序存储，前、中、后、层序遍历方法
已知二叉树的前(后)序+中序遍历，画二叉树
给定一个权值集合，画哈夫曼树，求哈夫曼编码
图的邻接矩阵和邻接表存储、广度和深度遍历方法
Prim算法和Kruskal算法求无向带权图的最小生成树
给定待排序的数据序列，写出直接插入排序、希尔排序、直接选择排序、堆排序、
冒泡排序、快速排序的排序过程
二叉排序树的建立
哈希表的建立

程序题
求带头结点的单链表长的算法 (显示单链表所有元素)
在单链表中查找内容为x的结点的算法
在带头结点head的单链表的结点a之后插入新元素x
删除单链表的第i个结点
直接插入排序
直接选择排序
冒泡排序
二分查找

单元测验1
一．判断题
（ㄨ）（1）数据的逻辑结构和数据的存储结构是相同的。
（ㄨ）（2）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。
（√）（3）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。
（√）（4）数据的存储结构是数据的逻辑结构的存储映像。
（ㄨ）（5）数据的逻辑结构是依赖于计算机的。
（√）（6）算法是对解题方法和步骤的描述。
二．填空题
1．数据有逻辑结构和存储结构两种结构。
2. 数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。
3．树形结构和图形结构合称为非线性结构。
4．数据的存储结构又叫物理结构。
5．数据的存储结构形式包括：顺序存储和链式存储
6．线性结构中的元素之间存在一对一的关系。
7．树形结构中的元素之间存在一对多的关系，
8．图形结构的元素之间存在多对多的关系。
9．数据结构主要研究数据的逻辑结构、存储结构和 二者之间的相互运算 三个方面的内容。
10．一个算法的时间复杂度是 问题规模 的函数。
11．若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为O（nlog2n）。
12．若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为O（n2）。
三．选择题
1．数据结构通常是研究数据的（ D ）及它们之间的相互联系。
A.联系与逻辑 B.存储和抽象 C.联系和抽象 D.存储结构和逻辑结构
2．数据在计算机内存储时，数据元素在存储器内相对位置可以表示元素之间的逻辑关系，称为（D）。
A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构
3．链接存储的存储结构所占存储空间（A）。
A．分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针
B．只有一部分，存放结点值
C．只有一部分，存储表示结点间关系的指针
D．分两部分，一部分存放结点值，另一部分存放结点所占单元数
4．在数据结构中，与所使用的计算机无关的是（B）
A.物理结构 B.逻辑结构 C.存储结构 D.逻辑和存储结构
5．算法能正确的实现预定功能的特性称为（A）
A.正确性B.易读性C.健壮性D.高效性
6．算法在发生非法操作时可以作出处理的特性称为（B）
A.正确性 B.健壮性 C.易读性D.高效性
7．下列时间复杂度中最坏的是（A）
A.O（n2）B.O（log2n）C.O（n）D.O（1）
8. 算法分析的两个主要方面是（C）。
A.可读性和文档性B.正确性和简明性C.空间复杂性和时间复杂性D.数据复杂性和程序复杂性
四．分析下面各程序段的时间复杂度
（1）s=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
s= s+B[i][j];
（2）for  (i=0;i<n;i++)
for  (j=0;i<n;j++)
c[i][j]=i+j;

单元测验2
一．判断题
（√）（1）在线性表的链式存取结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。
（×）（3）顺序存储方式的优点是存储密度大，插入、删除效率高。
（×）（4）链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
（√）（5）线性表采用顺序存储，必须占用一片连续的存储单元 。
（×）（6）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
二．填空题
1．顺序表相对于链表的优点是：   节省存储   和随机存取。
2．链表相对于顺序表的优点有插入、删除方便；缺点是存储密度   小   。
3．在一个长度为n的顺序表中删除第i个元素，要移动   n-i   个元素。  
4．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快速度存取线性表中的元素时，应采用  顺序  存储结构
5．在线性表的链接存储中，元素之间的逻辑关系是通过   指针  决定的。
6．对一个需要经常进行插入和删除操作的线性表，采用  链接  存储结构为宜。
三．选择题
1．单链表的存储密度（  C  ）。
A． 大于1             B． 等于1           C．小于1              D． 不能确定
2．已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（  A  ）。
A． B+(i-1)*m         B．B+i*m            C． B-i*m             D． B+(i+1)*m
3．在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为（  B  ）。
A．O（1）             B．O（n）           C．O（n2）            D．O（log2n）
4．下面关于线性表的叙述中，错误的是（  B  ）关系。
A．顺序表必须占一片地址连续的存储单元  B．链表可以随机存取任一元素
C．链表不必占用一片地址连续的存储单元  D．顺序表可以随机存取任一元素
5．链表不具备的特点是（ C ）。
A ．插入删除时不需移动元素                          B．不必事先估计存储空间
C．随机访问             D．所需空间与线性表成正比
6．用链式存储结构存储的线性表，其优点是（  B  ）。
A． 便于随机存取                        B．便于插入和删除
C． 花费的存储空间比顺序表少                     D． 数据元素的物理顺序与逻辑顺序相同

四．程序填空
1、求带头结点的单链表长的算法：
int f ( linknode *head, int n)
{
P=head; n=0;
While (P->next!=NULL)
{
;
;
}
return n;
}

2、在单链表中查找内容为x的结点的算法：
Node * Lsearch ( linknode *head, char x)
{
P=head;
while (P->next!=NULL && P->data!= x )
;
if ( )
printf ( " 没有找到! \n");
else
return P; /*找到，返回结点指针*/
}
3、在带头结点head的单链表的结点a之后插入新元素x：
struct Node
{
Char data;
Node *next;
};

void ListInsert (Node *head, Char x)
{
node *p,*s;
p=head->next;
while (p!=NULL) && ( p->data!=a )
;
if (p= =NULL)
printf ( " 不存在结点a，无法插入! \n");
else
{
s= ;
s->data= ;
_ ___;
_  _ _ __;
}
}

单元测验3
一．判断题
（√）（1）栈是运算受限制的线性表。
（√）（2）在栈空的情况下，不能作出栈操作，否则产生下溢出。
（ㄨ）（3）栈一定是顺序存储的线性结构。
（√）（4）栈的特点是“后进先出”。
（√）（5）链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。
（ㄨ）（6）一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。
二．填空题
1．在栈结构中，允许插入、删除的一端称为   栈顶   。
2．在一个链栈中，若栈顶指针等于NULL，则表示  栈空  。
3．已知顺序栈S，在对S进行出栈操作之前首先要判断  栈是否空  。
4．从一个栈删除元素时，首先取出栈顶元素，然后再移动  栈顶指针   。
5. 顺序栈用data[n]存储数据，栈顶指针是top, 则值为x的元素入栈的操作是_ data[top]=x；top++；

三．选择题
1．设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的站台，下列不可能的出站顺序为 (  B  )
A．1234     B．1423        C．1324       D．1243
2．顺序栈存储空间的实现使用（  B  ）存储栈元素。
A．链表      B．数组        C．循环链表    D．变量
3．如果以链表作为栈的存储结构，则出栈操作时（  B  ）
A．必须判别栈是否满         B．必须判别栈是否空
C．必须判别栈元素类型       D．队栈可不做任何判别
4．一个栈的入栈次序ABCDE，则栈的不可能的输出序列是 (  D  )。
A．EDCBA      B．DECBA        C．ABCDE         D．DCEAB
5、栈与一般线性表的区别在于 (  C   )。
A．数据元素的类型不同           B．数据元素的个数不同
C．操作是否受限制           D．逻辑结构不同

Head
A
a0

B

D
/\
C

6．带头结点的链栈LS的示意图如下，栈顶元素是（  A  ）

A．A         B．B              C．C            D．D
单元测验4
一．判断题
（√）（1）队列是限制在两端进行操作的线性表。
（√）（2）判断顺序队列为空的标准是头指针和尾指针均指向同一个结点。
（×）（3）在循环链队列中无溢出现象。
（×）（4）栈和队列都是顺序存储的线性结构。
（×）（5）在队列中允许删除的一端称为队尾。
（×）（6）顺序队列和顺序循环队列的队满和队空的判断条件是一样的。
二．填空题
1．在队列中存取数据应遵从的原则是   先进先出   。
2．在队列中，允许插入的一端称为   队尾   。
3．对于队列，只能在  队首  删除元素。
4．解决顺序队列“假溢出”的方法是采用   循环队列   。
5．顺序队列的队头指针为front，队尾指针为rear，则队空的条件为   front == rear    。
6．在一个链队列中，若队头指针与队尾指针的值相同，则表示该队列为  空   。
7．区分循环队列的满与空，有三种方法，它们是_设计数器_____、_设标志位_____和__少用一个存储空间____。
8. 循环队列存储在数组A[m]中，则入队时的操作为rear=(rear+1) % m
9．设顺序循环队列的队头指示器front指向队头元素，队尾指示器rear指向队尾元素后的一个空闲元素，队列的最大空间为M，则用牺牲一个存储单元区分队列满与空时，队满标志为    front==(rear+1)% M   。
10. 已知链队列的头尾指针分别是Q->front和Q->rear，则将值x入队的操作序列是p = (LQNode *)malloc(sizeof(LQNode))； p->data=x; p->next=NULL；
Q->rear->next=p；Q->rear = p；

三．选择题
1．同一队列内各元素的类型(  A  )。
A．必须一致        B．不能一致      C．不限制         D．可以不一致
2．队列是一个( D  )线性表结构。
A．不加限制的      B．推广了的       C．非     D．加了限制的
3．四个元素按：A，B，C，D顺序连续进队Q，执行一次出队操作后，队头元素是（  C  ）。
A． D                     B． C C． B                     D． A
4．若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为 (  B  )。
A．5和1        B．4和2         C．2和4             D．1和5
5．以下属于队列的操作有(  D  )。
A．在队首插入元素                   B．删除值最小的元素
C．按元素的大小排序                    D．判断是否还有元素
6. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( C )。
A． 6 B. 4 C. 3 D. 2

单元测验5

一、选择题

1. 若对n阶对称矩阵A (行下标和列下标范围均为1…n)，将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［0..(n(n+1))/2-1］中，则在B中确定aij（i<j）的位置k的关系为 ( B )。
A. i*(i-1)/2+j-1 B. j*(j-1)/2+i-1 C. i*(i+1)/2+j D. j*(j+1)/2+i

2. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ B ）。
A. 808 B. 818 C. 1010 D. 1020

3. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( B )。
A. BA+141 B. BA+180 C. BA+222 D. BA+225

4. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行优先存储，元素A[8,5]的起始地址与当A按列优先存储时的元素（ B ）的起始地址相同。设每个字符占一个字节。
A. A[8,5] B. A[3,10] C. A[5,8] D. A[0,9]

5. 设有一个10阶的对称矩阵A，采用压缩存储方式存储于一维数组va中，a11为第一元素，其存储下标序号为1，则a85的下标序号为（ B ）。
A. 13 B. 33 C. 18 D. 40

6. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ B ）。
A. 60 B. 66 C. 18000 D. 33

单元测验6

一．判断题
（√）（1）二叉树的前序遍历中，任意一个结点均处于其孩子结点的前面。
（√）（2）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。
（√）（3）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。
（√）（4）具有n个叶子结点的哈夫曼树共有2n-1个结点。
二．填空题
1．在树中，一个结点所拥有的子树数称为该结点的   度    。
2．度为零的结点称为    叶    结点。
3．由一棵二叉树的前序序列和    中序    序列可唯一确定这棵二叉树。
4．哈夫曼树是带权路径长度    最小   的二叉树。
5．已知完全二叉树的第8层有8个结点（根结点计为第1层），则其叶结点数是   68    。
6．三个结点可以组成  2  种不同形态的树。
7．将一棵完全二叉树按层次从0开始编号，对于为5的结点，该结点左孩子的编号为：  11  。
8．结点最少的二叉树是   空二叉树   。
9．对于二叉树来说，第5层上至多有   16   个结点。
10．深度为5的二叉树至多有    31  个结点。
三．选择题
1．树最适合用来表示（  B  ）。
A．有序数据元素                        B．元素之间有分支层次的关系
C．元素之间无联系的数据                D． 无序数据元素
2．前序为A，B，C的二叉树共有（  A  ）种。
A．5                           B．4                        C．3                          D．2
3．根据二叉树的定义，具有3个结点的二叉树有（  C  ）种树型。
A．3                           B．4                           C．5                            D．6

4．将一棵有80个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为0，则编号为38的结点的右孩子编号为（  C  ）。
A．76                         B．77                      C．78                       D．79
5．用5个权值{3, 2, 4, 5, 1}构造的哈夫曼树的带权路径长度是（  B  ）。
Ａ．32             Ｂ．33              Ｃ．34              Ｄ．15
6．在树结构中，若结点B有3个兄弟，A是B的父亲结点，则A的度为为（  B ）。
A．3               B．4              C．5                  D．6
7．下列陈述正确的是（  C  ）。
A．二叉树是度为2的有序树           B．二叉树中结点只有一个孩子时无左右之分
C．二叉树中最多只有两棵子树，且有左右子树之分         D．二叉树中必有度为2的结点
8．某二叉树的前序遍历序列为：DABCEFG，中序遍历序列为：BACDFGE，则层次遍历序列为（  C  ）。
A． BCAGFED        B．ABCDEFG           C．DAEBCFG        D．BCAEFGD

四．应用题
1、某二叉树的结点数据采用顺序存储，其结构如下（其中，“/\”表示结点为空）：
0
1
2
3
4
5
6
7
8
9
A
B
C
/\
D
E
F
/\
/\
G

请画出该二叉树，并分别写出按前序、中序、后序、层序遍历的结点序列。

2、 已知一棵二叉树的中序遍历结点序列为 BFDGAEHC，后序遍历结点序列为FGDBHECA。
请画出此二叉树，并写出该树的前序遍历结点序列。

3、给定一个权集W={4，5，7，8，6，12，18}，试画出相应的哈夫曼树，并计算其带权路径长度WPL。

单元测验7
一．判断题
（ㄨ）（1）在无向图中，（V1，V2）与（V2，V1）是两条不同的边。
（ㄨ）（2）邻接表只能用于有向图的存储。
（√）（3）一个图的邻接矩阵表示是唯一的。
（ㄨ）（4）有向图不能进行广度优先遍历。
（√）（5）若一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。
二．填空题
1．图有：邻接矩阵和   邻接表   等常用存储方式。
2．图的遍历有：   深度优先搜索  和广度优先搜索等方法。
3．图的邻接矩阵表示法是表示  __顶点____之间相邻关系的矩阵。
4．有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的  __出度____。
5．有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点i的   入度   。
6．设有一稀疏图G，则G采用  _邻接表____存储比较节省空间。
7．设有一稠密图G，则G采用  _邻接矩阵____存储比较节省空间。
8．n个顶点的有向完全图有    n（n-1）   条边。
9．对于具有n个顶点的图，其生成树有且仅有  n-1  条边。
10．无向图的邻接矩阵一定是    对称    矩阵。
三．选择题 
1．在下列表示方法中，（  D  ）是有向图边的表示方法。
A．（1，2）     B．（1，2>         C．<1，2）        D．<1，2>
2． 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的(  B  )倍。
A．1/2                B. 1                C.  2              D.  4
3． 对于一个具有n个顶点的无向图的边数最多有（  B  ）。
A．n                  B．n（n-1）/2         C．n（n-1）      D．2n
4．在一个具有n个顶点的无向图中，要连通全部顶点至少需要（  B ）条边。
A．n                  B．n-1              C．n+1            D．n/2
5． 有8个结点的有向完全图有(  C  )条边。
A．14                 B. 28               C. 56              D. 112
6． 无向图顶点v的度是关联于该顶点（  B  ）的数目。
A．顶点               B．边               C．序号            D．下标
7．有n个顶点的无向图的邻接矩阵是用（  B  ）数组存储。
A．一维               B．n行n列          C．任意行n列      D．n行任意列
8．在一个具有n个顶点e条边的图中，所有顶点的度数之和等于（  C  ）。
A．e              B． n              C．2e              D．2n
四．应用题
1． 根据如下无向图
（1） 画出该图的邻接矩阵和邻接表
（2） 并分别给出该图邻接矩阵下的深度优先搜索遍历和广度优先搜索遍历的结点序列。

2． 分别用普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法画出构造该无向带权图最小生成树的过程。

单元测验8
一．判断题
（ㄨ）（1）如果某种排序算法不稳定，则该排序方法就没有实际应用价值。
（√）（2）对n个记录的进行快速排序，所需要的平均时间是O（nlog2n）。
（ㄨ）（3）堆排序所需的时间与待排序的记录个数无关。
（√）（4）当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。
（√）（5）对快速排序来说，初始序列为递增有序或递减有序都是最坏情况。
（√）（6）采用希尔方法排序时，若关键字的排列杂乱无序，则效率较高。
二．填空题
1．大多数排序算法都有两个基本的操作：   比较   和移动。
2．对n个关键字进行冒泡排序，时间复杂度为   O（n2）   。
3．快速排序在最坏情况下的时间复杂度是   O（n2）   。
4．在排序前，关键字值相等的不同记录，排序后相对位置保持   不变   的排序方法，称为稳定的排序方法。
5．当增量为1时，该趟希尔排序与   直接插入   排序基本一致。
6．第一趟排序后，序列中键值最大的记录交换到最后的排序算法是    冒泡排序    。
7．依次将待排序的每个记录插入到一个有序已排序序列中的排序方法称为    插入    排序。
8．对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较   3   次。
9．两个序列分别为： L1={25，57，48，37，92，86，12，33}
L2={25，37，33，12，48，57，86，92}。
用冒泡排序法对L1和L2进行排序，交换次数较少的是序列：   L2    。
10．对一组记录（54，35，96，21，12，72，60，44，80）进行直接选择排序时，第四次选择和交换后，未排序记录是   54，72，60，96，80   。

三．选择题  
1．排序是根据（  A  ）的大小重新安排各元素的顺序。
A．关键字          B．数组            C．元素件          D．结点
2．排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法，称为 (  B  )。
A．插入排序        B．选择排序        C．希尔排序        D. 快速排序
3．每次把待排序方的区间划分为左、右两个区间，其中左区间中元素的值不大于基准元素的值，右区间中元素的值不小于基准元素的值，此种排序方法叫做（  D ）。
A．冒泡排序        B．堆排序          C．希尔排序        D.快速排序
4．快速排序在（  C  ）情况下最易发挥其长处。
A．待排序的数据中含有多个相同的关键字 B．待排序的数据已基本有序
C．待排序的数据完全无序               D．待排序的数据中最大值与最小值相差悬殊
5．直接插入排序的方法是从第（  B  ）个元素开始，插入到前边适当位置的排序方法。
A．1               B．2               C．3               D．n
6．堆的形状是一棵（  C  ）。
A．二叉排序树      B．满二叉树        C．完全二叉树      D．任意二叉树
7．内排序是指在排序的整个过程中，全部数据都在计算机的（  A  ）中完成的排序。
A．内存            B．外存            C．内存和外存      D．寄存器
8．下述几种排序方法中，平均时间复杂度最小的是（  A  ）。
A．希尔排序        B．直接插入排序        C．冒泡排序        D．直接选择排序
9．对n个数据进行快速排序，在最坏情况下，算法的时间复杂度是（  B  ）。
A．O(n)             B．O(n2)            C．O(nlog2n)        D．O(n3)
10．冒泡排序的方法对n个数据进行排序，第一趟排序共需要比较（  C  ）次。
A．1                B．2                C．n-1             D．n
11．用直接插入排序法对下面的四个序列进行由小到大的排序，元素比较次数最少的是（  B  ）。
A，94，32，40，90，80，46，21，69       B．21，32，46，40，80，69，90，94
C．32，40，21，46，69，94，90，80       D．90，69，80，46，21，32，94，40
12． 一个数据序列的关键字为：（46，79，56，38，40，84），采用快速排序，并以第一个数为基准得到第一次划分的结果为：（   C   ）
A．（38，40，46，56，79，84）          B．（40，38，46，79，56，84）
C．（40，38，46，56，79，84）           D．（40，38，46，79，56，84）
四．应用题 
1． 已知数据序列{80，18，9，90，27，75，42，69}，试写出采用冒泡排序（从小到大）算法排序时，每一趟排序的结果。

2． 已知数据序列{40，63，11，84，35，93，58，39}，试写出采用直接选择排序（从小到大）每一趟排序结果。

3．  已知数据序列{12，2，16，30，28，10，17，20}，写出希尔排序（从小到大）每一趟（设d=4,2,1）的排序结果。

4． 已知数据序列{10，1，15，18，7，15}，试写出采用快速排序（从小到大）每一趟排序的结果。

5． 已知数据序列{18，17，60，40，07，32，73，65}，试写出采用直接插入排序（从小到大）每一趟排序结果。

五．程序填空  
1． 直接选择排序

2、直接插入排序

3、冒泡排序

单元测验9
一．判断题
（√）（1）二分查找法要求待查表的关键字值必须有序。
（ㄨ）（2）对有序表而言采用二分查找总比采用顺序查找法速度快。
（ㄨ）（3）在二叉排序树中，根结点的值都小于孩子结点的值。
（√）（4）哈希表是一种将关键字转换为存储地址的存储方法。
（√）（5）哈希法的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。
（ㄨ）（6）在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点的相应的指针域置空即可。
二．填空题
1．在分块查找方法中，首先查找   索引表   ，然后再查找相应的块。
2．顺序查找、二分查找、分块查找都属于    静态    查找。
3．对于长度为n的线性表，若进行顺序查找，则时间复杂度为   O（n）  。
4．对于长度为n的线性表，若采用二分查找，则时间复杂度为：   O（log2n）  。
5．在关键字序列（7，10，12，18，28，36，45，92）中，用二分查找法查找关键字92，要比较
   4 次才找到。
6．对二叉排序树进行查找的方法是用待查的值与根结点的键值进行比较，若比根结点小，则继续在   左   子树中查找。
7．二叉排序树是一种    动态   查找表。
8．哈希法既是一种存储方法，又是一种    查找    方法。
9．设哈希函数H(k)和键值k1，k2，若k1≠k2，且H（k1）=H（k2），则称这种现象为  哈希冲突  。
10．处理冲突的两类主要方法是开放定址法和   链表法   。
11．在哈希函数H(key)=key % P中，P一般应取    质数    。
12．在查找过程中有插入元素或删除元素操作的，称为    动态   查找。
三．选择题
1．对线性表进行二分查找时，要求线性表必须 （  B ）。
A．以顺序方式存储                      B．以顺序方式存储，且结点按关键字有序排序
C．以链接方式存储                      D．以链接方式存储，且结点按关键字有序排序
2．衡量查找算法效率的主要标准是（  C ）。
A．元素个数        B. 所需的存储量     C．平均查找长度     D．算法难易程度
3．有一个有序顺序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为
82的结点时，(  C  )次比较后查找成功。
A．2               B．3                C．4                 D．5
4．下列（  D  ）不是利用查找表中数据元素的关系进行查找的方法。
A．顺序表的查找                           B．有序顺序表的查找       
C.  二叉排序树的查找                          D．哈希查找 
5．在查找过程中，若同时还要做增加、删除工作，这种查找称为（  C  ）。
A．静态查找          B. 内查找          C．动态查找         D．外查找
6．已知8个元素为{34，76，45，18，26，54，92，65}，按照依次插入结点的方法生成一棵二叉排序树，最后两层上结点的总数为（  B  ）。
A．1                B．2                C. 3                D．4
7．下列那种查找方法不属于静态查找（  D  ）。
A．顺序查找                                 B. 二分查找
C．分块查找                                 D．二叉排序树
8．设哈希表长n=14，哈希函数H（k）=k％11。表中已有4个结点： H(15)=4, H(38)=5, H(61)=6, H(84)=7,其余地址为空。如用线性探查法处理哈希冲突，关键字为49的结点的地址是（  A  ）。
A．8               B．3                 C．5                   D．9
四．应用题
1． 在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4。
（1） 画出此二叉排序树
（2） 写出此二叉排序树的中序遍历序列

2． 给定结点的关键