【东南大学 1992 五（18分）】
64. 在数轴上有N个彼此相临不交的区间，每个区间下界上界都是整数。N个区间顺序为1-N。要查找给定的X落入的区间号，
您认为应怎样组织数据结构，选择什么方法最快，简述原因。 【西北大学 2000 二、4 (5分)】
65. 有一个长度为12的有序表，按对半查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数是
多少？【吉林大学 2001 一、 1 (3分)】
66. 若对一个线性表进行折半查找，该线性表应满足什么条件？【北京航空航天大学 1998 一、8 （4分）】 67. 在查找和排序算法中，监视哨的作用是什么？【长沙铁道学院 1997 三、3 (3分)】
68. 长度为255的有序表采用分块查找，块的大小应取多少？【首都经贸大学 1997 一、1 （4分）】
69. 用分块查找法，有2000项的表分成多少块最理想？每块的理想长度是多少？若每块长度为25 ，平均查找长度是多少？
【厦门大学 1999 三、2】
70. 设有n个值不同的元素存于顺序结构中，试问：你能否用比（2n-3）少的比较次数选出这n个元素中的最大值和最小值？若能，请说明是如何实现的；在最坏情况下，至少要进行多少次比较。【西安电子科技大学 1996 四 （10分）】 71. 对有14个元素的有序表A[1…14]作折半查找，当比较到A[4]时算法结束。被比较元素除A[4]外，还有哪几个？
【燕山大学 2000 一、2 （1分）】 72. 解答下面的问题
（1）画出在递增有序表A[1..21]中进行折半查找的判定树。
（2）当实现插入排序过程时，可以用折半查找来确定第I个元素在前I-1个元素中的可能插入位置，这样做能否改善插入排序的时间复杂度？为什么？
（3）折半查找的平均查找长度是多少？【西安电子科技大学2000计应用 八 （10分）】
73. 设有一组数据black,blue,green,purple,red,white,yellow，它们的查找概率分别为0.10,0.08,0.12,0.05,0.20,0.25,0.20。 试以它们的查找概率为权值，构造一棵次优查找树，并计算其查找成功的平均查找长度。【清华大学 1997 七 （12分）】 74. 假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题：
(1).画出描述折半查找过程的判定树； (2).若查找元素54，需依次与那些元素比较? (3).若查找元素90，需依次与那些元素比较?
(4).假定每个元素的查找概率相等，求查找成功时的平均查找长度。【华中理工大学 1999 二 (10分)】
75. 在分析二叉查找树性能时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点i所在层次为Li，那么查找失败到达失败结点时所作的数据比较次数是多少？【清华大学 1999 一、4 （2分）】
76. 设有五个数据do，for，if,repeat，while，它们排在一个有序表中，其查找概率分别为p1 =0.2, p2=0.15，p3=0.1，p4=0.03，
p5=0.01。而查找它们之间不存在数据的概率分别为q0=0.2,q1=0.15,q2=0.1,q3=0.03,q4=0.02,q5=0.01。 do for if repeat while
q0 p1 q1 p2 q2 p3 q3 p4 q4 p5 q5
(1) 试画出对该有序表采用顺序查找时的判定树和采用折半查找时的判定树。（6分）
(2) 分别计算顺序查找时的查找成功和不成功的平均查找长度，以及折半查找时的查找成功和不成功的平均查找长度。（4分） (3) 判定是顺序查找好？还是折半查找好？（2分） 【清华大学 1999年 二 （12分）】
77. 顺序检索，二分检索，哈希（散列）检索的时间分别为O(n),O(log2n),O(1)。既然有了高效的检索方法，为什么低效的方法还不放弃？【北京邮电大学 1993 一、2 (5分)】
五、 算法设计题
1．请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。
【北京大学 1998 三、2 （5分）】
类似本题的另外叙述有：
（1）试写一个判别给定二叉树是否为二叉排序树的算法。【中山大学 1994 五 (12分)】
（2）某二叉树采用链接存储，其结点结构是：（lc,data,rc）。 lc和rc分别是指向左子树根和右子树根的指针域。data为结点数据域。试写出判断该二叉树是否为二叉排序树的算法（不许另设空间，但可以设一些辅助指针）。设二叉排序树左子树每个结点值<根结点值，右子树每个结点的值≥根结点的值。二叉树是递归定义的。按此定义写出判断某二叉树是否为二叉排序树的算法。【北京邮电大学 1993 四 （20分）】
(3) 编写判定给定的二叉树是否是二叉排序树的函数。【南京大学 2000】
2．某个任务的数据模型可以抽象为给定的K个集合：S1，S2，…，Sk。其中Si(1<=i<=k)中的元素个数不定。在处理数据过程中将会涉及到元素的查找和新元素的插入两种操作，查找和插入时用一个二元组（i,x）来规定一个元素，i是集合的序号，x是元素值。设计一种恰当的数据结构来存储这k个集合的元素，并能高效的实现所要求的查找和插入操作。
（1）借助Pascal的数据类型来构造和描述你所选定的数据结构，并且说明选择的理由；
（2） 若一组数据模型为S1={10.2, 1.7, 4.8, 16.2 }, S2={1.7, 8.4, 0.5 }, S3={4.8, 4.2, 3.6, 2.7, 5.1, 3.9 }, 待插入的元素二元组为(2, 11.2 )和(1, 5.3 ), 按你的设计思想画出插入元素前后的数据结构状态。
【北京工业大学 1995 七 (20分)】 3．假设K1，…，Kn是n个关键词，试解答：
(1) 试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn时，用算法建立一棵以LLINK / RLINK 链接表示的二叉查找树。
(2) 设计一个算法，打印出该二叉查找树的嵌套括号表示结构。例如，K1=B，K2=A，K3=D，K4=C，K5=E，则用二叉查找树的插入算法建立的二叉查找树为：
该二叉查找树的嵌套括号表示结构为：B（A，D（C，E）） 【吉林大学 1995 六 (14分)】
4. 写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设删除结点由指针p所指，其双亲结点由指针f所指，并假设被删除结点是其双亲结点的右孩子。用类PASCAL（或C）语言将上述算法写为过程形式。 【南开大学 1998 七 (16分)】
5. 已知二叉树排序树中某结点指针p,其双亲结点指针为fp,p为fp的左孩子，试编写算法，删除p所指结点。
【北京轻工业学院 1998 五 （12分）】
6．二叉排序树采用二叉链表存储。写一个算法，删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树，并且高度没有增长（注：可不考虑被删除的结点是根的情况）。【中科院软件所 1999 七、1（8分）】
7. 设记录R1,R2,…,Rn按关键字值从小到大顺序存储在数组r[1..n]中,在r[n+1]处设立一个监督哨,其关键字值为+∞; 试写一查找给定关键字k 的算法;并画出此查找过程的判定树,求出在等概率情况下查找成功时的平均查找长度。 【武汉交通科技大学 1996 四、2 (16分)】
8．试编写算法，在根结点指针为t的m-阶B树上查找关键字k,返回记录(pt,i,tag).若查找成功，则特征位tag=1,等于k的关键字即为指针pt所指结点中的第i个关键字；若查找不成功，则特征位tag=0，等于k的关键字应插入到指针pt所指结点中第i个和第i+1个关键字之间。简化B-树存储结构如下所示：
type mblink=↑mbnode mbnode=record keynum:integer; parent:mblink;
key:array[1..m] of keytp {关键字} ptr:array [0..m] of mblink end;
result=record pt:mblink; i:integer; tag:(0..1) end;
（注：所用语言C, PASCAL等都可使用编制算法。若算法不用类PASCAL描述，要给出相应语言的结构描述。题目中给出的结构说明可供参考，也可自行给出）【北京轻工业学院 1997 八 （10分）】
9. 元素集合已存入整型数组A[1..n]中，试写出依次取A中各值A[i](1<=i<=n)构造一棵二叉排序树T的非递归算法：CSBT(T,A)
【北京科技大学 2000 八、2】
10．给出折半查找的递归算法，并给出算法时间复杂度性分析。【河南大学 1998 五（5分）】
类似本题的另外叙述有：
（1）写出折半查找的算法，并要求它返回整型值i，当查找成功时，返回查找位置，查找不成功时返回0。 【山东师范大学 2000 二、3 （12分） 2001 二、4（10分）】
11．请用类C或用类PASCAL语言编写算法：键树，又称数字查找树。它是一棵度为>=2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。编写一个在键（TIRE）树T上查找关键字等于给定值KEY的记录的算法。若查找成功，返回指向该记录的指针；否则返回空指针。【上海大学 2002 七、2 （10分）】
12．写出从哈希表中删除关键字为K的一个记录的算法，设哈希函数为H，解决冲突的方法为链地址法。
【上海交通大学 1999 五 (12分)】
13．用PASCAL或C编写一用链接表（LINKED LIST）解决冲突的哈希表插入函数。【浙江大学 1996 七 (8分 )】
14．在用除余法作为散列函数、线性探测解决冲突的散列表中，写一删除关键字的算法，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不致于断裂。【中科院计算所 2000 八 （15分）】 15．设排序二叉树中结点的结构为下述三个域构成:
data: 给出结点数据的值；left: 给出本结点的左儿子结点的地址；right: 给出本结点的右儿子结点的地址
设data 域为正整数，该二叉树树根结点地址为T。 现给出一个正整数x。请编写非递归程序，实现将data域的值小于等于x的结点全部删除掉。【上海交通大学 2000 十一 (12分)】
16．已知二叉树T的结点形式为(llink, data,count,rlink,),在树中查找值为X的结点，若找到，则记数（count）加1；否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。【中山大学 1999数 三 (10分)】 17．假设一棵平衡二叉树的每个结点都标明了平衡因子b,试设计一个算法，求平衡二叉树的高度。
【燕山大学 2001 四、3 （8分）】
18．设从键盘输入一个整数的序列：n,a1,a2，…，an,其中n表示连续输入整数的个数。（10分）。 （1）试编写一程序按整数值建立一个二叉排序树（单考生做）。
（2）在（1）基础上将此二叉树上的各整数按降序写入一磁盘文件中（统考生做）。【南京航空航天大学 1998 十（10分）】 19． 设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。【北方交通大学 1998 七 （20分）】
20．在单链表中，每个结点含有5个正整型的数据元素若（最后一个结点的数据元素不满5个，以值0充），试编写一算法查找值为n（n>0）的数据元素所在的结点指针以及在该结点中的序号，若链表中不存在该数据元素则返回空指针。
【北京邮电大学 2001 五、1 （10分）】
21．编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。 【清华大学 1995 七（20分）】
22. 在二叉排序树的结构中，有些数据元素值可能是相同的 ，设计一个算法实现按递增有序打印结点的数据域，要求相同的数据元素仅输出一个，算法还应能报出最后被滤掉，而未输出的数据元素个数，对如图所示的二叉排序树，输出为：10，12，13，15，18，21，27，35，42．滤掉3个元素。【北京工业大学 1995 六 (18分)】
23．已知二叉排序树采用二叉链表存储结构，根结点的指针为T，链结点的结构为（lchild,data,rchild），其中lchild、rchild分别指向该结点左、右孩子的指针（当孩子结点不存在时，相应指针域为null）,data域存放结点的数据信息。请写出递归算法，从小到大输出二叉排序树中所有数据值>=x的结点的数据。要求先找到第一个满足条件的结点后再依次输出其他满足条件的结点。【北京航空航天大学 1996】 24. 设二叉排序树的存储结构为：
TYPE tree=^node； node=RECORD
key: keytype; size:int;
lchild, rchild, parents: tree； END;
一个结点x^的size域的值是以该结点为根的子树中结点的总数（包括x^本身）。例如，下图中x所指结点的sixe值为4。设树高为h，试写一时间为O(h)的算法Rank(T:tree;x:^node)返回x所指结点在二叉排序树T的中序序列里的排序序号，即：求x^结点是根为T的二叉排序树中第几个最小元素。例如，下图x所指结点是树T中第11个最小元素。（提示：你可利用size值和双亲指针parents）【中科院软件所 1997 四(12分)】【中国科学技术大学 1997】
17/12 14/7 10/4 16/2 14/1 T 21/4 22/1 x 19/2 key 7/2 12/1 9/1 20/1 25． 已知某哈希表HT的装填因子小于1，哈希函数H(key)为关键字的第一个字母在字母表中的序号。
（1） （2）
处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。 处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。【西北大学 2001】
size 26． 有一个100*100的稀疏矩阵，其中1%的元素为非零元素，现要求用哈希表作存储结构。
（1）请你设计一个哈希表
（2）请写一个对你所设计的哈希表中给定行值和列值存取矩阵元素的算法；并对你的算法所需时间和用一维数组（每个分量存放一个非零元素的行值，列值，和元素值）作存储结构时存取元素的算法（注：此算法不需要写出，仅需说明存取的方法和所用时间）进行比较。【北方交通大学 1994 六 （16分）】
27．将一组数据元素按哈希函数H（key）散列到哈希表HT（0:m）中，用线性探测法处理冲突（H（key）+1、H（key）+2、…、H（key）-1），假设空单元用EMPTY表示，删除操作是将哈希表中结点标志位从INUSE标记为DELETED，试写出该散列表的查找、插入和删除三个基本操作算法。【北京邮电大学 2001 五、2 （10分）】
28. 设给定关键字输入序列为（100，90，120，60，78，35，42，31，15）用散列法散列0-10的地址区间。要求设计一合理的散列函数；冲突时用链表法解决，写出散列算法，并构造出散列表，在等概率查找情况下查找成功的平均查找长度是多少？
【东北大学 1996 四 (12分)】
类似本题的另外叙述有：
(1) 已知输入关键字序列为（100,90,120,60,78,35,42,31,15）地址区间为０～１１。设计一个哈希表函数把上述关键字散到０～１１中，画出散列表（冲突用线性探测法）；写出查找算法，计算在等概率情况下查找成功的平均查找长度。
【东北大学 1997 五 (15分)】
29. 已知顺序表中有m个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到O(m).
【清华大学 1994 八 （15分）】