爱华网（一）单项选择题
1. 在二维数组中，每个数组元素同时处于（ c ）个向量中。
A.0B.1C.2D. n
2. 已知单链表A长度为m，单链表B长度为n，它们分别由表头指针所指向，若将B整体连接到A的末尾，其时间复杂度应为（A）。
A.O(1)B.O(m)C. O(n)D.O(m+n)
3. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为(A )。
A. front ==rearB. front != NULL
C. rear != NULLD.front == NULL
4. 若让元素1,2,3依次进栈，则出栈次序不可能出现(c )种情况。
A.3,2,1B.2,1,3C.3,1,2D. 1,3,2
5. 图的广度优先搜索类似于树的（D ）遍历。
A. 先根B.中根C. 后根D. 层次
6. 下面程序段的时间复杂度为( c )。
for(int i=0;i<m; i++)
for(int j=0;j<n; j++) a[i][j] = i*j;
A.O(m2)B.O(n2)C. O(m*n)D.O(m+n)
7. 设有两个串t和p，求p在t中首次出现的位置的运算叫做（B ）。
A.求子串B.模式匹配C. 串替换D.串连接
8 利用双向链表作线性表的存储结构的优点是（B ）。
A.便于单向进行插入和删除的操作B. 便于双向进行插入和删除的操作
C.节省空间D. 便于销毁结构释放空间
9. 设链式栈中结点的结构为（data,link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行(C)操作。
A.top->link=s;B. s->link=top->link;top->link=s;
C. s->link=top;top=s;D. s->link=top; top=top->link;
10. 一棵具有35个结点的完全二叉树的高度为( B )。假定空树的高度为-1。
A.5B.6C.7D. 8
11. 一个有n个顶点和n条边的无向图一定是(A ) 的。
A．连通B．不连通C．无回路D．有回路
12. 在一个长度为n的顺序表的任一位置插入一个新元素的时间复杂度为（ A ）。
A.O(n)B.O(n/2)C.O(1)D. O(n2)
13. 已知广义表为A((a,b,c),(d,e,f))，从A中取出原子e的运算是（ D ）。
A．Tail(Head(A))B．Head(Tail(A))
C．Head(Tail(Head(Tail(A))))D．Head(Head(Tail(Tail(A))))
14. 在一棵树的静态双亲表示中，每个存储结点包含(B )个域。
A1B2C3D 4
15. 有向图中的一个顶点的度数等于该顶点的( C )。
A．入度B．出度
C．入度与出度之和D．(入度+出度)/２
16. 与邻接矩阵相比，邻接表更适合于存储( A )。
A．无向图B．连通图C．稀疏图D．稠密图
17. 较快的数据搜索方法是（ B）搜索方法。
A.顺序B. 折半C.单链D. 散列
18. 在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于（ C ）引起的。
A.同义词之间发生冲突B. 非同义词之间发生冲突
C.同义词之间或非同义词之间发生冲突D. 散列表“溢出”
19. 根据n个元素建立一个有序单链表的时间复杂度为（B ）。
A.O(1)B. O(n)C.O(n2)D.O(nlog2n)
20. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为( D )。
A.front+1==rearB. rear+1==front
C.front==0D. front==rear
21. 假定一棵二叉树的第i层上有3i个结点，则第i+1层上最多有(B )个结点。
A.3iB.6iC.9iD. 2i
22. 对于具有e条边的无向图，它的邻接表中共有( C)个边结点。
A．e-1B．e+1C．2eD．3e
23. 图的深度优先搜索遍历类似于树的（A ）次序遍历。
A.先根B.中根C.后根D. 层次
24．栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列?( C)
A.E、D、C、B、A、FB.B、C、E、F、A、D
C.C、B、E、D、A、FD. A、D、F、E、B、C
25．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为：(A )
A. 98B.99C.50D.48
26. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是：(C )
A.{21、25、5、17、9、23、30}
B. {25、23、30、17、21、5、9}
C.{21、9、17、30、25、23、5}
D. {5、9、17、21、23、25、30}
27．对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为(C )
A.顺序表B. 用头指针表示的单循环链表
C.用尾指针表示的单循环链表D. 单链表
28．假设以第一个元素为分界元素，对字符序列（Q, H, C, Y, P, A, M, S, R,D, F, X）进行快速排序，则第一次划分的结果是：(C )
A. (A, C, D, F, H, M, P, Q, R, S, X,Y)
B. (A, F, H, C, D, P, M, Q, R, S, Y,X)
C. (F, H, C, D, P, A, M, Q, R, S, Y,X)
D. (P, A, M, F, H, C, D, Q, S, Y, R, X)
29．下面是三个关于有向图运算的叙述：( )
（1）求有向图结点的拓扑序列，其结果必定是唯一的
（2）求两个指向结点间的最短路径，其结果必定是唯一的
（3）求AOE网的关键路径，其结果必定是唯一的
其中哪个（些）是正确的？(D)
A.只有（1）B.（1）和（2）C.都正确D. 都不正确
30．若进栈序列为a,b, c，则通过入出栈操作可能得到的a, b, c的不同排列个数为: ( B )
A.4B.5C.6D. 7
31. 以下关于广义表的叙述中,正确的是：(A )
A. 广义表是由0个或多个单元素或子表构成的有限序列
B. 广义表至少有一个元素是子表
C.广义表不能递归定义
D) 广义表不能为空表
32. 排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？(D)
A. 堆排序 B.直接插入排序 C.快速排序 D.冒泡排序
33． 已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：( B )
A.将邻接矩阵的第i行删除B. 将邻接矩阵的第i行元素全部置为0
C.将邻接矩阵的第i列删除D. 将邻接矩阵的第i列元素全部置为0
34． 有一个含头结点的双向循环链表，头指针为head, 则其为空的条件是：( C)
A.head->priro==NULLB. head->next==NULL
C.head->next==headD. head->next-> priro==NULL
35. 在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30)中，用折半法查找关键码值11，所需的关键码比较次数为：(C)
A.2B.3C.4D. 5
36. 以下哪一个不是队列的基本运算？( B )
A.从队尾插入一个新元素B. 从队列中删除第i个元素
C.判断一个队列是否为空D. 读取队头元素的值
37．对包含n个元素的哈希表进行查找，平均查找长度为：( D )
A.O(log2n)B.O(n)C.O(nlog2n)D 不直接依赖于n
38．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为：()
A.48B. 49 C.50 D. 51
39．某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为：( C)
A.3B.2C.4D. 5
40．下面C 是顺序存储结构的优点。
A. 存储密度大 B. 插入运算方便
C. 查找方便D.适合各种逻辑结构的存储表示
41．下面关于串的叙述中，B是不正确的。
A.串是字符的有限序列B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储
42．B 的邻接矩阵是对称矩阵。
A. 有向图B.无向图C.AOV网D. AOE网
43．用链式方式存储的队列，在进行删除运算时，A。
A.仅修改头指针B. 仅修改尾指针
C.头、尾指针都要修改D. 头、尾指针可能都要修改
44．二叉树的先序遍历和中序遍历如下，则该二叉树右子树的树根是C。
先序序列：EFHIGJK中序序列：HFIEJKG
A.EB.FC.GD. H
45．下面 D方法可以判断出一个有向图中是否有环。
A.深度优先遍历B.拓朴排序C. 求最短路径D.求关键路径
46．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为A排序法。
A.插入B.选择C.冒泡D. 都不是
47．一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是C。
A. edcbaB.decbaC. dceab D.abcde
48．n个节点的完全二叉树，编号为i的节点是叶子结点的条件是D。
A. i<n B.2*i<=nC.2*i+1>nD. 2*i>n
49．向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动B
个元素。
A. 64.5 B.64 C.63 D. 65
50．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行D 。
A. q->next=p->next;p->next=q;B. p->next=q->next; q=p;
C. p->next=p->next;q->next=q;D. p->next=q->next;q->nxet=p;
51．对一个满二叉树，m个树叶，n个结点，深度为h，则有D。
A. n=h+mB.h+m=2nC. m=h-1 D.n=2h-1
52．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是B。
A. 选择排序 B.冒泡排序 C.插入排序 D. 希尔排序
53．用链式方式存储的队列，在进行插入运算时，B。
A.仅修改头指针B. 仅修改尾指针
C.头、尾指针都要修改D. 头、尾指针可能都要修改
54．在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）插入一个新元素时，需要从后向前依次后移C个元素。
A.n-iB.n-i-1C.n-i+1D. i
55．一个栈的入栈序列是12345，则栈的不可能的输出序列是B。
A. 23415 B.54132C. 23145 D. 15432
56．5个顶点的有向图最多有B条弧。
A.5B.20C.4D. 25
57．假定一个链队的队首和队尾指针分别为f--ront和rear，则判断队空的条件为A 。
A.front==rearB.front!=NULL
C.rear!=NULLD. front==NULL
58．若某线性表中最常用的操作是提取第i个元素及找第i个元素的前驱元素，则采用（D ）存储方式最省时间。
A.单链表B.双链表C.单向循环链表 D.顺序表
59．将含有100个结点的完全二叉树从根开始自上向下，每层从左到右依次编号，且设根结点的编号为1，则编号69的结点的双亲的编号为（A ）。
A.34B.35C.33D. 无法确定
60. 单循环链表的主要优点是（ D ）。
A. 不再需要头指针了
B. 已知某结点的位置后，很容易找到其前驱
C. 在进行插入、删除运算时，能更好地保证链表不断开
D. 从表中任一结点出发都能扫描到整个链表
61. 一个栈的入栈顺序是1、2、3、4、5，则此栈不可能的输出顺序为（ C ）。
A.5、4、3、2、1B. 4、5、3、2、1
C.4、3、5、1、2D. 1、2、3、4、5
62. 串是一种特殊的线性表，其特殊性表现在（ B）。
A.可以顺序存储B.数据元素是一个字符
C可以链式存储D.数据元素是多个字符
63. n个顶点的无向图中最多有（ A ）条边。
A.n(n-1)/2 B.n(n-1)C. n(n+1)D.n(n+1)/2
64. 6个顶点的无向图中，至少有（ A ）条边才能保证是一个连通图。
A.5B.6C.7D.8
65．若某线性表中最常用的操作是删除第1个元素，则不宜采用（D）存储方式。
A.单链表B.双链表C.单向循环链表 D.顺序表
66．在一棵完全二叉树的顺序存储方式中，若编号i的结点有右孩子，则其右孩子的编号为（C ）。
A.2iB.2i-1C.2i+1D. i/2
67.按照二叉树的定义，具有3个结点的二叉树有（C ）种不同形态。
A.3B.4C.5D. 6
68. 在长为n的顺序表中，删除第i个元素(1≤i≤n+1)需要向前移动（A ）个元素。
A.n-iB. n-i+1C.n-i-1D.i
69. 一个队的入队顺序是1、2、3、4、5，则此队的出队顺序为（D）。
A. 5、4、3、2、1B.4、5、3、2、1
C.4、3、5、1、2D. 1、2、3、4、5
70. 栈是一种特殊的线性表，其特殊性表现在（B）。
A.可以顺序存储B.只能从端点进行插入和删除
C.可以链式存储D. 可以在任何位置进行插入和删除
71. 一棵二叉树中，第k层上最多有（D ）个结点。
A.2kB.2k-1C.2kD.2k-1
72. 一棵有18个结点的二叉树，其高度最小为（B ）层。
A.4B.5C.6D. 18
73.有向图中，所有顶点入度和是所有顶点出度和的（B ）倍。
A.0.5B.1C.2D.4
（二）填空题
1.数据元素之间存在的相互关系称为结构 。
2.数据结构从逻辑上分为存储结构和 逻辑结构。
3.线性表的顺序存储结构称为顺序表。
4.所有插入在表的一端进行，而所有删除在表的另一端进行的线性表称为队列。
5.深度为h的二叉树,最少有1个结点。
6.折半查找要求待查表为 有序表。
7.n个记录按其关键字大小递增或递减的次序排列起来的过程称为排序。
8.存储数据时,不仅要存储数据元素的 表示 ,还要存储元素之间的相互关系 。
．将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT（X）的编号为_24 ___。
10、一个字符串相等的充要条件是位置相等和长度相等。
11、在有向图的邻接表和逆邻接表表示中，每个顶点的边链表中分别链接着该顶点的所有表节点和_ 表头结点。
11、在一个长度为n 的顺序表中向第i 个元素（0<i≤n+1）之前插入一个新元素时，需要向后移动_n-i+1个元素。
12、_队列是只允许在表的一端进行插入，而在另一端进行删除的线性表。
13、设主串T＝“abxxyxyxxbaa”,模式串P＝“xyxx”则第_6次匹配成功。
14、在一棵二叉树中，第5层上的结点数最多为_16。（根的层次为1）
15、假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组中，其中B［0］存储矩阵中第1个元素a1,1，则B[31] 中存放的元素是_a38。
16、有n个结点的二叉链表中，其中空的指针域为n+1，指向孩子的指针个数为_n。
17、二叉树后序遍历的顺序是ABCDE，则该二叉树的根结点是_E。
18、对于一个具有n 个顶点和e条边的无向图，若采用邻接表表示，则整个邻接表中的结点总数是_2e 。
19、在单链表上难以实现的排序方法有_堆排序和_直接插入排序。
20、_哈希 查找法的平均查找长度与元素个数n无关。
21、在有n个元素的顺序表的任意位置插入一个元素所需移动结点的平均次数为_n/2。
22、_栈是插入和删除元素都在表的同一端进行的线性表。
23、广义表L＝（a,b,c,L）,则其长度为_4。
24、在树中，除跟结点外，其他结点都有且只有一个_前驱结点。
26、在串s=“structure”中，以t 为首字符的子串有_11个。
27、广度优先搜索遍历类似于树的按_层序遍历的过程。
28、已知一棵完全二叉树中共有768个结点为，则该树中共有_383个叶子结点。
29、在有序表（12,24,36,48,60,72,84）中二分查找关键字72时所需进行的关键字比较次数为_2 。
30、两个长度分别m和n（m>n）的排好序的表归并成一个排好序的表，至少要进行_n*m次键值比较。通常从四个方面评价算法的质量：_正确性_、_可读性__、_健壮性___和__算法效率__。
31、一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为___n_____。
32、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有_2n_个指针域，其中有__n-1__个指针域是存放了地址，有_____n+1__________个指针是空指针。
33、对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有__e__个和___2e_____个。
34、在一个具有n个顶点的无向完全图中，包含有___n(n-1)/2__条边，在一个具有n个顶点的有向完全图中，包含有___n(n-1)_____条边。
35、36.在快速排序、堆排序、归并排序中，__快速__排序是稳定的。
36、37.中序遍历二叉排序树所得到的序列是___递增有序____序列。
38.快速排序的最坏时间复杂度为____o(n2)__，平均时间复杂度为____o(nlong2n)______。
39.设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为__80、75、50、56、63、44、31、38__________。
40．数据的物理结构主要包括__顺序存储结构__和____链式存储结构____两种情况。
41.设一棵完全二叉树中有500个结点，则该二叉树的深度为____9____；若用二叉链表作为该完全二叉树的存储结构，则共有_____501___个空指针域。
42、设输入序列为1、2、3，则经过栈的作用后可以得到___5__种不同的输出序列。
43、设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的_出度___，第i列上所有元素之和等于顶点i的__入度__。设哈夫曼树中共有n个结点，则该哈夫曼树中有__1个或0个____个度数为1的结点。
44、设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为_______e=2d__。
45、__中序___遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。
46、设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较___7___次就可以断定数据元素X是否在查找表中。
47、不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为_____0(n)___。
48、设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为__I/2____，右孩子结点的编号为____2i+1____。
49、设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为__5、16、71、23、72、94、73_______。
50、设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为1、4、2、3_。
51、下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。
struct record{int key; int others;};
int hashsqsearch(struct record hashtable[ ],int k)
{
int i,j; j=i=k % p;
while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=(j+1_)%m; if (i==j) return(-1);}
if (__hashtable[j].key ==k__ ) return(j);else return(-1);
}
52、下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。
typedef struct node{int key; struct node *lchild; struct node*rchild;}bitree;
bitree *bstsearch(bitree *t, intk)
{
if (t==0 ) return(0);else while (t!=0)
if (t->key==k)___ return(t)_____; else if(t->key>k)t=t->lchild; else___ t=t->rchild_____;
}
53、设有n个无序的记录关键字，则直接插入排序的时间复杂度为_o(n2)_______，快速排序的平均时间复杂度为_o(nlong2n)____。
54、设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为___ _llink->next=rlink________（设结点中的两个指针域分别为llink和rlink）。根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为____3_______。
55、深度为k的完全二叉树中最少有____ 2k-1____个结点。
56、设初始记录关键字序列为(K1，K2，…，Kn)，则用筛选法思想建堆必须从第__n/2_个元素开始进行筛选。
59、设哈夫曼树中共有99个结点，则该树中有____50_个叶子结点；若采用二叉链表作为存储结构，则该树中有__100_个空指针域。
60、设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储_m_个队列元素；当前实际存储___m-1__个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。
61、设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中__n-i+1_个数据元素；删除第i个位置上的数据元素需要移动表中___n-i__个元素。
62、设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速排序结果为__19、18、16、20、30、22___。
63、设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建成的初始堆为_(30、20、22、16、18、19)___。
64、设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数___等于___第i列上非0元素的个数（填等于，大于或小于）。
65、设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为___BDCA___。
66、设散列函数H(k)=k modp，解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0。
typedef struct node {int key; struct node *next;} lklist;
void createlkhash(lklist *hashtable[ ])
{
int i,k; lklist *s;
for(i=0;i<m;i++)___ hashtable[i]=0______;
for(i=0;i<n;i++)
{
s=(lklist *)malloc(sizeof(lklist));s->key=a[i];
k=a[i] % p; s->next=hashtable[k];_____hashtable[k]=s __________;
}
}
三、应用题主要考点
1、二叉树的遍历与恢复（即已知二叉树对其遍历、已知遍历序列恢复二叉树）、哈夫曼树的构造
2、图的存储结构（邻接矩阵、邻接表）、图的应用（最小生成树、拓扑排序）
3、各种查找方法（二叉排序树、散列表、平均查找长度）
4、各种排序方法
四、算法设计题主要考点
1、线性表的简单算法(顺序表和单链表的基本运算)。
顺序表算法：
Int listinsert(sqlist &l,int I,elemtypee)//插入元素
{int j;
{if(i<1||i>l.length)
Return 0;
i--;
for(j=l.length;j<I;j--)
l.data[j]=l.data[j-1];
l.data[i]=e;
l.length++;
return};
E=l.data[i-1];
Retrun 1;}
Int listinsert(sqlist &l,int I,elemtype&e)//删除元素
{int j;
{if(i<1||i>l.length)
Return 0;
i--;
e=l,data[i];
for(j=I;j<l.length-1;j++)
l.data[j]=l.data[j+1];
l.length--;
return 1};
链表算法：
voidcreatelistf(linklist*&l,elemtype a[],int n)
{ linklist *s;int I;
L=(linklist*)malloc(sizeof(linklist));//创建头结点
L→next=null;
For(i=0;i<n;i++)
{s= (linklist*)malloc(sizeof(linklist));//创建新结点
s→data=a[i];
s→next=l→next;
l→next=s;
}
}
删除结点的关键点是:
如果删除A后的节点B,假设P为指向A的指针
p→next=p→next→next
2、二叉树的简单应用算法(如二叉树的遍历、求二叉树的高度、二叉树中叶子节点数等)
二叉树的遍历（递归算法）
先序：
Void preorder(btnode *b)
{if (b!=bull)
{printf(“%c”,b→data);//访问根结点
Preorder(b→lchild);
Preorder(b→rchild);}}
中序：
Void inorder(btnode *b)
{if (b!=bull)
{inorder(b→lchild);
printf(“%c”,b→data);//访问根结点
inorder(b→rchild);}}
中序：
Void posrorder(btnode *b)
{if (b!=bull)
{posrorder(b→lchild);
posrorder(b→rchild);
printf(“%c”,b→data);//访问根结点
}}
3、查找算法（顺序查找、二分查找）。
顺序查找：
Int seqsearch(seqlist r,intn,keytype k)
{
Int i=0;
While(i<n&&r[i].key!=k)i++;
If(i>=n)
Return -1;
Else
Return I;
}
二分查找法：
Int binsearch(seqlist r,intn,keytype k)
{int i=0,j=n-1,m;
While(i<j)
{m=(i+j)/2;
If(r[i].key==k)
Return m;
If(r[i].key>k)
J=m-1;
Else
I=m+1;
}
Return -1;}
4、排序算法（如插入、交换、选择排序等）。
直接插入排序法：
Void insertsort(sqlist r[],int i)
{int I,j;
Sqlist tmp;
For(i=1;i<n,i++)
{tmp=a[i];
J=i-1;
While(j>=0&&tmp.key<r[j].key)//元素后移，以腾出一个位置插入tmp
(r[j+1]=r[j];
j--;
}
R[j+1]=tmp；//在J+1位置处插入tmp即r[i]
}}
快速排序法：
Void quicksort(sqlistr[],int s ,int t)
{int i=s,j=t;
Sqlist tmp;
If(s<t)//区间内至少存在一个元素的情况
{tmp=r[s]; //用区间的第一个记录作为基准
While(i!=j)//从区间两端交替向中间扫描，直至I=J为止
{while(j>i&&r[j].key>tmp.key)//从右向左扫描，找第一个关键字小于tmp.key的r[j]
j--;
if(i<j) //表示找到这样的r[j]，则r[i]和r[j]交换
{r[i]=r[j];
I++;
}
While(i<j&&r[j].key<tmp.key) //从右向左扫描，找第一个关键字大于tmp.key的r[j]
I++;
If(i<j) //表示找到这样的r[j]，则r[i]和r[j]交换
{r[j]=r[i];
J--;
}
}
R[i]=tmp;
Quicksort(r,s,i-1); //对左区进行递归排序
Quicksort(r,i+1,t)；//对右区进行递归排序
}}
