【考研类试卷】计算机专业基础综合（查找）-试卷1及答案解析.doc

《【考研类试卷】计算机专业基础综合（查找）-试卷1及答案解析.doc》由会员分享，可在线阅读，更多相关《【考研类试卷】计算机专业基础综合（查找）-试卷1及答案解析.doc（15页珍藏版）》请在麦多课文档分享上搜索。

1、计算机专业基础综合（查找）-试卷 1及答案解析(总分：94.00，做题时间：90 分钟)一、单项选择题(总题数：25，分数：50.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.若查找每个记录的概率均等，则在具有 n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度 ASL为( )。（分数：2.00）A.(n1)2B.n2C.(n+1)2D.n3.顺序查找法适用于查找顺序存储或链式存储的线性表二分法查找只适用于查找顺序存储的有序表，平均比较次数为( )。在此假定 N为线性表中结点数，且每次查拔都是成功的。（分数

2、：2.00）A.N+1B.2log 2 NC.log 2 ND.N24.顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( )在此假定 N为线性表中结点数，且每次查拔都是成功的。（分数：2.00）A.N+1B.2log 2 NC.log 2 ND.N25.适用于折半查找的表的存储方式及元素排列要求为( )。（分数：2.00）A.链接方式存储，元素无序B.链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序6.具有 12个关键字的有序表，折半查找的平均查找长度为( )。（分数：2.00）A.31B.4C.25D.57.折半查找的时间复杂性为( )。（分数：2.

3、00）A.O(n 2 )B.O(n)C.O(nlog 2 n)D.O(log 2 n)8.当采用分块查找时，数据的组织方式为( )。（分数：2.00）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D.数据分成若干块，每块(除最后一块外)中数据个数需相同9.下面函数的功能是实现分块查找，空白处应该添加的内容是( )。 int BlkSearch(int*nz，int key，int block，int BLK，int len) int i； bl

4、ock=block-1； if(1enlen)BLK=len； for(i=block*BLK；iA.nzi=keyB.nzi=BLKC.nzi=blockD.nzi=010.二叉查找树的查找效率与二叉树的( )有关。（分数：2.00）A.高度B.结点的多少C.树形D.结点的位置11.二叉查找树的查找效率，在( )时其查找效率最低。（分数：2.00）A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂12.在一棵高度为 h的理想平衡二叉树中，最少含有( )个结点，最多含有( )个结点。（分数：2.00）A.2 h 2 h-1B.2 h-1 2 hC.2 h +1 2 h 一 1D.2 h-1

5、2 h 一 113.分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是( )。（分数：2.00）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)14.关于 B-树，下列说法中不正确的是( )。（分数：2.00）A.B-树是一种查找树B.所有的叶结点具有相同的高度C.2-3树中，所有非叶子结点有 1或者 3个孩子结点D.通常情况下，B-树不是二叉树15.在含有 15个结点的平衡二叉树上，查找关键字为 28(

6、存在该结点)的结点，则依次比较的关键字有可能是( )。（分数：2.00）A.30，36B.38，48，28C.48，18，38，28D.60，30，50，40，38，3616.下面关于 m阶 B树的说法中，正确的是( )。 每个结点至少有两棵非空子树。 树中每个结点至多有 m-1个关键字。 所有叶子在同一层上。 当插入一个数据项引起 B树结点分裂后，树长高一层。（分数：2.00）A.B.C.D.17.下面关于 B和 B+树的叙述中，不正确的是( )。（分数：2.00）A.B树和 B+树都是平衡的多又树B.B树和 B+树都可用于文件的索引结构C.B树和 B+树都能有效地支持顺序检索D.B树和 B

7、+树都能有效地支持随机检索18.m阶 B-树是一棵( )。（分数：2.00）A.m叉排序树B.m 叉平衡排序树C.m-1叉平衡排序树D.m+1叉平衡排序树19.若对有 18个元素的有序表做二分查找，则查找 A3的比较序列的下标为( )。（分数：2.00）A.1，2，3B.9，4，2，3C.10，5，3D.9，2，320.有一个有序表1，3，9，12，32，41，45，62，75，77，82，95，100，当用二分查找法查找值为 82的结点时，经( )次比较后查找成功。（分数：2.00）A.1B.2C.4D.821.采用分块查找时，若线性表中共有 625个元素，查找每个元素的概率相同，假设采用顺

8、序查找来确定结点所在的块，则每块分为( )个结点最佳。（分数：2.00）A.9B.25C.6D.62522.在有 n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为( )。（分数：2.00）A.O(n)B.O(log 2 n)C.O(nlog 2 n)D.O(n 2 )23.对包含 n个关键码的散列表进行检索，平均检索长度为( )。（分数：2.00）A.O(log 2 n)B.O(n)C.O(nlog 2 n)D.不直接依赖于 n24.在散列表上，每个地址单元所链接的同义词表的( )。（分数：2.00）A.键值相同B.元素值相同C.散列地址相同D.含义相同25.设哈希表

9、长 m=14，哈希函数日(key)=key mod 11。表中已有 4个结点 addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空，如用二次探测再散列法处理冲突，则关键字为 49的结点的地址是( )。（分数：2.00）A.8B.3C.5D.9二、综合应用题(总题数：20，分数：44.00)26.综合应用题 41-47小题。_27.请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用 llinkrlink法存储。（分数：2.00）_某个任务的数据模型可以抽象为给定的 k个集合：S 1 ，S 2 ，S k 。其中 S i (1ik 中的元素个数

10、不定。在处理数据过程中将会涉及元素的查找和新元素的插入两种操作，查找和插入时用一个二元组(i，x)来规定一个元素，i 是集合的序号，x 是元素值。设计一种恰当的数据结构来存储这 k个集合的元素，并能高效地实现所要求的查找和插入操作。（分数：4.00）(1).构造数据结构，并且说明选择的理由。（分数：2.00）_(2).若一组数据模型为 S 1 =102，17，48，162，S 2 =17，84，05，S 3 =48，42，36，27，51，39，待插入的元素二元组为(2，112)和(1，53)，按你的设计思想画出插入元素前后的数据结构状态。（分数：2.00）_假设 K 1 ，K N 是 n个关

11、键词，试解答：（分数：4.00）(1).试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为 K 1 ，K 2 ，K n 时，用算法建立一棵以 LLINKRLINK链接表示的二叉查找树。（分数：2.00）_(2).设计一个算法，打印出该二叉查找树的嵌套括号表示结构。假定该二叉查找树的嵌套括号表示结构为B(A，D(C，E)。（分数：2.00）_28.写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设删除结点由指针 p所指，其双亲结点由指针 f所指，并假设被删除结点是其双亲结点的右孩子。描述上述算法。（分数：2.00）_29.已知二叉树排序树中某结点指针 p，其双亲结点

12、指针为 fp，p 为 fp的左孩子。试编写算法，删除 p所指结点。（分数：2.00）_30.二叉排序树采用二叉链表存储。写一个算法，删除结点值是 X的结点。要求删除该结点后，此树仍然是一棵二叉排序树，并且高度没有增长(注意：可不考虑被删除的结点是根的情况)。（分数：2.00）_31.设记录 R 1 ，R 2 ，R n 按关键字值从小到大顺序存储在数组 r1n中，在 rn+1处设立一个监督哨，其关键字值为+。试写一查找给定关键字 k的算法，并画出此查找过程的判定树，求出在等概率情况下查找成功时的平均查找长度。（分数：2.00）_32.给出折半查找的递归算法，并给出算法时间复杂度分析。（分数：2.

13、00）_33.键树(Trie)，又称数字查找树，它是一棵度大于等于 2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。请用类 C语言或类 PASCAL语言编写一个在键树 T上查找关键字等于给定值 KEP的记录的算法。若查找成功，返回指向该记录的指针；否则返回空指针。（分数：2.00）_34.写出从哈希表中删除关键字为 K的一个记录的算法。设哈希函数为 H，解决冲突的方法为链地址法。（分数：2.00）_35.用 C语言或 PASCAL编写一用链接表(Linked List)解决冲突的哈希表插入函数。（分数：2.00）_36.在用除余法作为散列函数线性探测解决冲突的散列

14、表中，写一删除关键字的算法，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不至于断裂。（分数：2.00）_37.设排序二叉树中结点的结构由三个域构成：数据域 data，指向左儿子结点的指针域 left，指向右儿子结点的指针域 right。 设 data域为正整数，该二又树树根结点地址为 T。现给出一个正整数 x。请编写非递归程序，实现将 data域的值小于等于 x的结点全部删除。（分数：2.00）_38.已知二叉树 T的结点形式为(llink，data，count，rlink)，在树中查找值为 X的结点，若找到，则记数(count)加 1；否则，作为一个新结点插入树中，插入后仍

15、为二叉排序树，写出其非递归算法。（分数：2.00）_39.假设一棵平衡二叉树的每个结点都标明了平衡因子 b，试设计一个算法，求平衡二叉树的高度。（分数：2.00）_设从键盘输入一个整数的序列：n，a 1 ，a 2 ，a n ，其中 n表示连续输入整数的个数。（分数：4.00）(1).试编写一程序按整数值建立一个二叉排序树。（分数：2.00）_(2).在(1)的基础上将此二叉树上的各整数按降序写入一磁盘文件中。（分数：2.00）_40.设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空、右子树非空的结点的数据域的值。（分数：2.00）_

16、41.在单链表中，每个结点含有 5个正整型的数据元素(若最后一个结点的数据元素不满 5个，以值 0充)，试编写一算法查找值为 n(n0)的数据元素所在的结点指针以及在该结点中的序号，若链表中不存在该数据元素则返回空指针。（分数：2.00）_42.编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，且查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。（分数：2.00）_计算机专业基础综合（查找）-试卷 1答案解析(总分：94.00，做题时间：90 分钟)一、单项选择题(总题数：25，分数：50.00)1.单项选

17、择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_解析：2.若查找每个记录的概率均等，则在具有 n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度 ASL为( )。（分数：2.00）A.(n1)2B.n2C.(n+1)2 D.n解析：解析：此题考查的知识点是顺序查找长度 ASL的计算。假设表长度为 n，那么查找第 i个数据元素需进行 n一 i+1次比较，即 C i =n一 i+l。又假设查找每个数据元素的概率相等，即 P i =1n，则顺序查找算法的平均查找长度为： 3.顺序查找法适用于查找顺序存储或链式存储的线性表二分法查找只适

18、用于查找顺序存储的有序表，平均比较次数为( )。在此假定 N为线性表中结点数，且每次查拔都是成功的。（分数：2.00）A.N+1B.2log 2 NC.log 2 N D.N2解析：解析：此题考查的知识点是各类查找算法的比较次数计算。顺序查找法用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败，其 ASL=(n+1)2，即查找成功时的平均比较次数约为表长的一半。应选 C。4.顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( )在此假定 N为线性表中结点数，且每次查拔都是成功的。（分数：2.00）A.N+1B.2log 2 NC.log 2 ND.N2 解析：解析：二分

19、法查找过程可用一个称为判定树的二叉树描述，由于判定树的叶子结点所在层次之差最多为 1，故 n个结点的判定树的深度与 n个结点的完全二叉树的深度相等，均为log 2 n+1。这样，折半查找成功时，关键字比较次数最多不超过log 2 n+1。所以，应选择 D。5.适用于折半查找的表的存储方式及元素排列要求为( )。（分数：2.00）A.链接方式存储，元素无序B.链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序 解析：解析：此题考查的知识点是折半查找的特点。折半查找要求顺序存储且元素有序，所以应选 D。6.具有 12个关键字的有序表，折半查找的平均查找长度为( )。（分数：

20、2.00）A.31 B.4C.25D.5解析：解析：此题考查的知识点是折半查找的思想。把关键字按完全二叉树的形式画出查找树，按结点高度计算比较次数。12 个结点可以画出高度为 4的完全二又树，1 层 1个结点比较 1次，2 层 2个结点比较2次，3 层 4个结点比较 3次，4 层 5个结点比较 4次，371231，应选 A。7.折半查找的时间复杂性为( )。（分数：2.00）A.O(n 2 )B.O(n)C.O(nlog 2 n)D.O(log 2 n) 解析：解析：此题考查的知识点是折半查找的效率。其查找效率与比较次数有关，折半查找成功时，关键字比较次数最多不超过log 2 n+1，所以其效

21、率为 O(log 2 n)，应选 D。8.当采用分块查找时，数据的组织方式为( )。（分数：2.00）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块 C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D.数据分成若干块，每块(除最后一块外)中数据个数需相同解析：解析：分块查找是将数据分成若干块，块间有序，块内不必有序。9.下面函数的功能是实现分块查找，空白处应该添加的内容是( )。 int BlkSearch(int*nz，int key，int block，int BLK，int len)

22、int i； block=block-1； if(1enlen)BLK=len； for(i=block*BLK；iA.nzi=key B.nzi=BLKC.nzi=blockD.nzi=0解析：解析：如果当前的值与所查找关键字相等，则完成查找。10.二叉查找树的查找效率与二叉树的( )有关。（分数：2.00）A.高度B.结点的多少C.树形 D.结点的位置解析：解析：二叉查找树的查找效率与树形有关，当结点呈单枝树排列时效率最低。11.二叉查找树的查找效率，在( )时其查找效率最低。（分数：2.00）A.结点太多B.完全二叉树C.呈单枝树 D.结点太复杂解析：12.在一棵高度为 h的理想平衡二叉

23、树中，最少含有( )个结点，最多含有( )个结点。（分数：2.00）A.2 h 2 h-1B.2 h-1 2 hC.2 h +1 2 h 一 1D.2 h-1 2 h 一 1 解析：解析：由平衡二叉树的特性可知，一棵高度为 h的理想平衡二叉树中，含有结点数最少的情形是：前 h一 1层为满二叉树，第 h层只有一个结点，因而结点总数为(2 h-1 一 1)+1=2 h-1 。 含有结点数最多的情形是：该树是一棵高度为的满二叉树，因而结点总数为 2 h-1 。 13.分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是( )。（分数：2.00）A.(100，80，90，60，120，1

24、10，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)解析：解析：分别根据给出的序列构建平衡二叉树，得出 C与其他不同。14.关于 B-树，下列说法中不正确的是( )。（分数：2.00）A.B-树是一种查找树B.所有的叶结点具有相同的高度C.2-3树中，所有非叶子结点有 1或者 3个孩子结点 D.通常情况下，B-树不是二叉树解析：解析：B-树定义如下： 一棵 m阶 B-树，或者是空树，或者是满足以下性质的 m叉树： (1)根结点或者是叶子，或者至少有两棵子树，至多有

25、 m棵子树。 (2)除根结点外，所有非终端结点至少有m2棵子树，至多有 m棵子树。 (3)所有叶子结点都在树的同一层上。 (4)每个结点应包含如下信 息：(n，A 2 ，K 1 ，A 1 ，K 2 ，A 2 ，K n ，A n )。 其中： K i (1in)是关键字，且 KK i+1 (1in一 1)； A i (i=0，1，n)为指向孩子结点的指针，且 A i-1 所指向的子树中所有结点的关键字都小于K i ，A i 所指向的子树中所有结点的关键字都大于 K i 。 n 是结点中关键字的个数，且m2一1nm 一 1，n+1 为子树的棵数。15.在含有 15个结点的平衡二叉树上，查找关键字为

26、 28(存在该结点)的结点，则依次比较的关键字有可能是( )。（分数：2.00）A.30，36B.38，48，28C.48，18，38，28 D.60，30，50，40，38，36解析：解析：设 N i 表示深度为 h的平衡二叉树中含有的最少结点数，有： N 0 =0，N 1 =1，N 2 =2； 计算的公式为： N h =N h-1 +N h-2 +1； N 3 =N 2 +N 1 +1=4； N 4 =N 3 +N 2 +1=7； N 5 =N 4 +N 3 +1=12； N 6 =N 5 +N 4 +1=2015。 也就是说，高度为 6的平衡二叉树最少有 20个结点，因此 15个结点的平

27、衡二叉树的高度为 5，而最小叶子结点的层数为 3，所以选项 D错误。 选项 A在查找 30后，指针应该指向左孩子，而不是右孩子；选项 B与选项 A存在同样的问题，因而选项 A、B 错误。而选项 C的查找路径如下图所示： 16.下面关于 m阶 B树的说法中，正确的是( )。 每个结点至少有两棵非空子树。 树中每个结点至多有 m-1个关键字。 所有叶子在同一层上。 当插入一个数据项引起 B树结点分裂后，树长高一层。（分数：2.00）A.B.C.D. 解析：解析：根据 B树定义可知只有正确。17.下面关于 B和 B+树的叙述中，不正确的是( )。（分数：2.00）A.B树和 B+树都是平衡的多又树B

28、.B树和 B+树都可用于文件的索引结构C.B树和 B+树都能有效地支持顺序检索 D.B树和 B+树都能有效地支持随机检索解析：解析：此题考查的知识点是 B-树和 B+树的定义。B-树定义见第 11题，B+树是应文件系统所需而发展出的一种 B-树的变形树。一棵 m阶的 B+树和 m阶的 B-树的差异在于： (1)有 n棵子树的结点中含有 n个关键字。 (2)所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。 (3)所有的非终端结点可以看成是索引部分，结点中仅含其子树(根结点)中的最大(或最小)关键字。通常在 B+树上有两个头指针，

29、一个指向根结点，一个指向关键字最小的叶子结点。所以 B+树能有效地支持随机检索和顺序检索。显然应选 C。18.m阶 B-树是一棵( )。（分数：2.00）A.m叉排序树B.m 叉平衡排序树 C.m-1叉平衡排序树D.m+1叉平衡排序树解析：解析：此题考查的知识点是 m阶 B-树的定义。B-树是一种平衡的多路排序树，m 阶即 m叉。应选B。19.若对有 18个元素的有序表做二分查找，则查找 A3的比较序列的下标为( )。（分数：2.00）A.1，2，3B.9，4，2，3C.10，5，3D.9，2，3 解析：解析：二分查找判定树如下图所示，查找 A3的比较序列的下标为 9，4，2，3，本题选 D。

30、20.有一个有序表1，3，9，12，32，41，45，62，75，77，82，95，100，当用二分查找法查找值为 82的结点时，经( )次比较后查找成功。（分数：2.00）A.1B.2C.4 D.8解析：解析：n=13，R11=82，第 1次与 R(1+13)2=7=45 比较，第 2次与 R(8+13)2=10=77 比较，第 3次与 R(11+13)2=12=95 比较，第 4次与 R(10+12)2=11=85 比较时成功，总共比较 4次。21.采用分块查找时，若线性表中共有 625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，则每块分为( )个结点最佳。（分数：

31、2.00）A.9B.25 C.6D.625解析：解析：分块查找时最佳块数为22.在有 n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为( )。（分数：2.00）A.O(n)B.O(log 2 n) C.O(nlog 2 n)D.O(n 2 )解析：解析：有 n个结点且为完全二叉树的二叉排序树的高度为 log 2 n。23.对包含 n个关键码的散列表进行检索，平均检索长度为( )。（分数：2.00）A.O(log 2 n)B.O(n)C.O(nlog 2 n)D.不直接依赖于 n 解析：解析：对散列表进行检索，平均检索长度仅与装填因子 有关，而与关键字个数 n无关。24

32、.在散列表上，每个地址单元所链接的同义词表的( )。（分数：2.00）A.键值相同B.元素值相同C.散列地址相同 D.含义相同解析：解析：由同义词的定义可知本题答案为 C。25.设哈希表长 m=14，哈希函数日(key)=key mod 11。表中已有 4个结点 addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空，如用二次探测再散列法处理冲突，则关键字为 49的结点的地址是( )。（分数：2.00）A.8B.3C.5D.9 解析：解析：addr(49)=49 mod 11=5，冲突；h1=(5+1*1)mod 11=6，仍冲突；h2=(5+2*

33、2)mod11=9，所以本题答案为 D。二、综合应用题(总题数：20，分数：44.00)26.综合应用题 41-47小题。_解析：27.请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用 llinkrlink法存储。（分数：2.00）_正确答案：(正确答案：根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量 pre(初值为 null)和全局变量 flag，初值为true。若非二叉排序树，则置 flag为 false。 #define true 1 #define：false 0 typedef struct node

34、 datatype data； stmct node * llink，*rlink； * BTree； void JudgeBST(BTree t，int flag) 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由 flag得出结论 if(t!=null if(p-lchild=null) 被删结点无左子树 if(f 一lchild=p)f一lchild：p-rchild；将被删结点的右子树接到其双亲上 else f 一rchild=p-rehild； elseq=P；S=P-lchild； 被删结点有左子树 while(S-rchild!=null) 查左子树中最右下的结点(中序最

35、后结点) q=s；s=s 一rchild； P-key=s-key； 结点值用其左子树最右下的结点的值代替 if(q=P)P 一lchild=s-lchild； 被删结点左子树的根结点无右子女 else q-rchild=s-lchild； s 是被删结点左子树中序序列最后一个结点 free(s)； )解析：31.设记录 R 1 ，R 2 ，R n 按关键字值从小到大顺序存储在数组 r1n中，在 rn+1处设立一个监督哨，其关键字值为+。试写一查找给定关键字 k的算法，并画出此查找过程的判定树，求出在等概率情况下查找成功时的平均查找长度。（分数：2.00）_正确答案：(正确答案：intSear

36、ch(rectype r，int n，keytype k) 在 n个关键字从小到大排列的顺序表中，查找关键字为 k的结点 rn+1key=MAXINT； 在高端设置监视哨 int i=1； while(rikey解析：32.给出折半查找的递归算法，并给出算法时间复杂度分析。（分数：2.00）_正确答案：(正确答案：int BinSrch(rectype r，int k，low，high) 在长为 n的有序表中查找关键字 k，若查找成功，返回 k所在位置，查找失败返回 0 if(lowk)return(BinSrch(r，k，mid+1，high)； else return(BinSrch(r，

37、k，low，mid-1)； l else return 0： 查找失败 算法时间复杂度为 O(log 2 n)。)解析：33.键树(Trie)，又称数字查找树，它是一棵度大于等于 2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。请用类 C语言或类 PASCAL语言编写一个在键树 T上查找关键字等于给定值 KEP的记录的算法。若查找成功，返回指向该记录的指针；否则返回空指针。（分数：2.00）_正确答案：(正确答案：在 Trie树上查找给定值 KEY的过程如下：沿和给定值相应的指针向下，直至叶子结点，若叶子中的关键字和 KEY相等，则查找成功；若分支结点中和给定值相

38、应的指针为空，或叶子结点中的关键字和给定值不等，则查找不成功。 typedef enumLEAF，BRANCHNodeKind； 结点种类叶子，分支 typedef struct TrieNode NodeKind kind； unionstructKeyType K；Record* infoptrIf； Dr 子结点 structTrieNode*ptr27；int nunbh： 分支结点 ； TrieNode，*TrieTree； 键树类型 Record * SearchTrie(TrieTree T，KeyType KEY) 在 Trie树 T中查找关键字等于 K的记录 for(P=T，

39、i=0； 对 KEY的每个字符逐个查找 P 此处 null代表散列表初始化时的空值 switch(Hsi=k) case true;del(HS，i，j，K)；breaki case false;di=l；j=(i+di)m； m 为表长 while(Hsj!=null if(P 一datarlink： else P=p-llink； if(!P) 无值为 x的结点，插入之 P：(BiTNode*) malloc(sizeof(BiTNode)； p-data=X；p-llink=null；p-rlink=null； if(f-dataX) f-llink=P； else f-rlink=p； else P 一count+； 查询成功，值域为 X的结点的 count增 1 )解析：39.假设一棵平衡二叉树的每个结点都标明了平衡因子 b，试设计一个算法，求平衡二叉树的高度。（分数：2.00）_正确答案：(正确答案：因为二叉树各结点已标明了平衡因子 b，故从根结点开始记树的层次。根结点的层次为 1，每下一层，层次加 1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子 b为 0时，任选左右一分支向下查找，若 b不为 0，则沿左(当