1、计算机专业基础综合（查找）模拟试卷 2 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 若查找每个记录的概率均等，则在具有凡个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度 ASL 为( )。（A）(n 一 1)2（B） n2（C） (n+1)2（D）n2 顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( (1) )，二分法查找只适用于查找顺序存储的有序表，平均比较次数为( (2) )。在此假定 N 为线性表中结点数，且每次查找都是成功的。（A）N+1 N 2（B） 2log2
2、N Nlog2N（C） N2 log 2N（D）N Nlog 23 适用于折半查找的表的存储方式及元素排列要求为( )。（A）链接方式存储，元素无序（B）链接方式存储，元素有序（C）顺序方式存储，元素无序（D）顺序方式存储，元素有序4 具有 12 个关键字的有序表，折半查找的平均查找长度为( )。（A）31（B） 4（C） 25（D）55 折半查找的时间复杂性为( )。（A）O(n 2)（B） O(n)（C） O(nlog2n)（D）O(log 2n)6 当采用分块查找时，数据的组织方式为( )。（A）数据分成若干块，每块内数据有序（B）数据分成若干块，每块内数据不必有序，但块间必须有序，每块
3、内最大(或最小)的数据组成索引块（C）数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块（D）数据分成若干块，每块(除最后一块外)中数据个数需相同7 下面函数的功能是实现分块查找，空白处应该添加的内容是( )。int BlkSearch(int*nz，int key，int block ，int BLK，int len)int i；block=block-1；if(lenlen)BLK=len；for(i=block*BLK；i (1) )有关，在( (2) )时其查找效率最低。（A）高度 结点太多（B）树形 呈单枝树（C）结点的多少 完全二叉树（D）结点的位置 结点太复杂9
4、 在一棵高度为 h 的理想平衡二叉树中，最少含有( )个结点，最多含有( )个结点。（A）2 h 2h-1（B） 2h 一 1 2h（C） 2h+1 2h 一 1（D）2 h-1 2h 一 110 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是( )。（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)11 关于 B-树，下列说法中不正确的是( )。（A）B-树是一种查找树（B）所有的叶结
5、点具有相同的高度（C） 2-3 树中，所有非叶子结点有 1 或者 3 个孩子结点（D）通常情况下，B 一树不是二叉树12 在含有 15 个结点的平衡二叉树上，查找关键字为 28(存在该结点)的结点，则依次比较的关键字有可能是( )。（A）30，36（B） 38，48，28（C） 48，18，38，98（D）60，30，50，40，38，3613 下面关于 m 阶 B 树的说法中，正确的是( )。每个结点至少有两棵非空子树。树中每个结点至多有 m-1 个关键字。所有叶子在同一层上。当插入一个数据项引起 B 树结点分裂后，树长高一层。（A）（B） （C） （D）14 下面关于 B 和 B+树的叙述
6、中，不正确的是( )。（A）B 树和 B+树都是平衡的多叉树（B） B 树和 B+树都可用于文件的索引结构（C） B 树和 B+树都能有效地支持顺序检索（D）B 树和 B+树都能有效地支持随机检索15 m 阶 B 一树是一棵( )。（A）m 叉排序树（B） m 叉平衡排序树（C） m1 叉平衡排序树（D）m+1 叉平衡排序树16 若对有 18 个元素的有序表做二分查找，则查找 A3的比较序列的下标为( )。（A）1，2，3（B） 9，4，2，3（C） 10，5，3（D）9，2，317 有一个有序表1，3， 9，12，32，41，45，62，75，77，82，95，100 ，当用二分查找法查找值
7、为 82 的结点时，经( )次比较后查找成功。（A）1（B） 2（C） 4（D）818 采用分块查找时，若线性表中共有 625 个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，则每块分为( )个结点最佳。（A）9（B） 25（C） 6（D）62519 在有 n 个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为( ) 。（A）O(n)（B） O(log2n)（C） O(nlog2n)（D）O(n 2)20 对包含 n 个关键码的散列表进行检索，平均检索长度为( )。（A）O(log 2n)（B） O(n)（C） O(nlog2n)（D）不直接依赖于 n
8、21 在散列表上，每个地址单元所链接的同义词表的( )。（A）键值相同（B）元素值相同（C）散列地址相同（D）含义相同22 设哈希表长 m=14，哈希函数 H(key)=key mod 11。表中已有 4 个结点 addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空，如用二次探测再散列法处理冲突，则关键字为 49 的结点的地址是( )。（A）8（B） 3（C） 5（D）9二、综合应用题41-47 小题，共 70 分。23 请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用 llink-rlink法存储。24 某个任务的数据模型可以抽象为给
9、定的 k 个集合：S 1，S 2，S k。其中Si(1ik)中的元素个数不定。在处理数据过程中将会涉及元素的查找和新元素的插入两种操作，查找和插入时用一个二元组(i，x)来规定一个元素，i 是集合的序号，x 是元素值。设计一种恰当的数据结构来存储这 k 个集合的元素，并能高效地实现所要求的查找和插入操作。 (1)构造数据结构，并且说明选择的理由。 (2)若一组数据模型为 S1=102，1 7，48，162，S 2=17，84，05，S3=48，4 2，36， 27，51，39，待插入的元素二元组为(2，112)和(1， 53) ，按你的设计思想画出插入元素前后的数据结构状态。25 假设 K1，
10、K n 是 n 个关键词，试解答： (1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为 K1，K 2，K n，时，用算法建立一棵以 LLINKRLJNK 链接表示的二叉查找树。 (2)设计一个算法，打印出该二叉查找树的嵌套括号表示结构。假定该二叉查找树的嵌套括号表示结构为B(A，D(C，E)。26 写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设删除结点由指针 p 所指，其双亲结点由指针 f 所指，并假设被删除结点是其双亲结点的右孩子。描述上述算法。27 已知二叉树排序树中某结点指针 p，其双亲结点指针为 fp，p 为 fp 的左孩子。试编写算法，删除 p
11、 所指结点。28 二叉排序树采用二叉链表存储。写一个算法，删除结点值是 X 的结点。要求删除该结点后，此树仍然是一棵二叉排序树，并且高度没有增长(注意：可不考虑被删除的结点是根的情况)。29 设记录 R1，R 2，R n 按关键字值从小到大顺序存储在数组 r1n中，在rn+1处设立一个监督哨，其关键字值为+。试写一查找给定关键字 k 的算法，并画出此查找过程的判定树，求出在等概率情况下查找成功时的平均查找长度。30 给出折半查找的递归算法，并给出算法时间复杂度分析。31 键树(Trie) ，又称数字查找树，它是一棵度大于等于 2 的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关
12、键字的符号。请用类 C 语言或类PASCAL 语言编写一个在键树 T 上查找关键字等于给定值 KEY 的记录的算法。若查找成功，返回指向该记录的指针；否则返回空指针。32 写出从哈希表中删除关键字为 K 的一个记录的算法。设哈希函数为 H，解决冲突的方法为链地址法。33 用 C 语言或 PASCAL 编写一用链接表(Linked List)解决冲突的哈希表插入函数。34 在用除余法作为散列函数线性探测解决冲突的散列表中，写一删除关键字的算法，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不至于断裂。35 设排序二叉树中结点的结构由三个域构成：数据域 data，指向左儿子结点的指
13、针域 left，指向右儿子结点的指针域 right。设 data 域为正整数，该二叉树树根结点地址为 T。现给出个正整数 x。请编写非递归程序，实现将 data 域的值小于等于 x 的结点全部删除。36 已知二叉树 T 的结点形式为(llink，data，count，rlink)，在树中查找值为 X 的结点，若找到，则记数(count) 加 l；否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。37 假设一棵平衡二叉树的每个结点都标明了平衡因子 b，试设计一个算法，求平衡二叉树的高度。38 设从键盘输入一个整数的序列：n，a 1，a 2， an，其中 n 表示连续输入整数的
14、个数。 (1)试编写一程序按整数值建立一个二叉排序树。 (2)在(1)的基础上将此二叉树上的各整数按降序写入一磁盘文件中。39 设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空、右子树非空的结点的数据域的值。40 在单链表中，每个结点含有 5 个正整型的数据元素(若最后一个结点的数据元素不满 5 个，以值 0 充)，试编写一算法查找值为 n(n0)的数据元素所在的结点指针以及在该结点中的序号，若链表中不存在该数据元素则返回空指针。41 编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值
15、，且查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。计算机专业基础综合（查找）模拟试卷 2 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 此题考查的知识点是顺序查找长度 ASL 的计算。假设表长度为 n，那么查找第 i 个数据元素需进行 ni+1 次比较，即 Ci=ni+l。又假设查找每个数据元素的概率相等，即 Pi=1n，则顺序查找算法的平均查找长度为： 所以应选 C。【知识模块】 查找2 【正确答案】 C【试题解析】 此题考查的知识点是
16、各类查找算法的比较次数计算。顺序查找法用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败，其ASL=(n+1) 2，即查找成功时的平均比较次数约为表长的一半。 二分法查找过程可用一个称为判定树的二叉树描述，由于判定树的叶子结点所在层次之差最多为1，故 n 个结点的判定树的深度与 n 个结点的完全二叉树的深度相等，均为 log2n+1。这样，折半查找成功时，关键字比较次数最多不超过log 2n+1。所以 C。【知识模块】 查找3 【正确答案】 D【试题解析】 此题考查的知识点是折半查找的特点。折半查找要求顺序存储且元素有序，所以应选 D。【知识模块】 查找4 【正确答案】 A【试题解析
17、】 此题考查的知识点是折半查找的思想。把关键字按完全二叉树的形式画出查找树，按结点高度计算比较次数。12 个结点可以画出高度为 4 的完全二叉树，1 层 1 个结点比较 1 次，2 层 2 个结点比较 2 次，3 层 4 个结点比较 3 次，4层 5 个结点比较 4 次，371231，应选 A。【知识模块】 查找5 【正确答案】 D【试题解析】 此题考查的知识点是折半查找的效率。其查找效率与比较次数有关，折半查找成功时，关键字比较次数最多不超过log 2n+1，所以其效率为 O(log2n)，应选 D。【知识模块】 查找6 【正确答案】 B【试题解析】 分块查找是将数据分成若干块，块间有序，块
18、内不必有序。【知识模块】 查找7 【正确答案】 A【试题解析】 如果当前的值与所查找关键字相等，则完成查找。【知识模块】 查找8 【正确答案】 B【试题解析】 二叉查找树的查找效率与树形有关，当结点呈单枝树排列时效率最低。【知识模块】 查找9 【正确答案】 D【试题解析】 由平衡二叉树的特性可知，一棵高度为 h 的理想平衡二叉树中，含有结点数最少的情形是：前 h 一 1 层为满二叉树，第 h 层只有一个结点，因而结点总数为(2 h-1 一 1)+1=2h-1。 含有结点数最多的情形是：该树是一棵高度为 h 的满二叉树，因而结点总数为 2h 一 1。 【知识模块】 查找10 【正确答案】 C【试
19、题解析】 分别根据给出的序列构建平衡二叉树，得出 C 与其他不同。【知识模块】 查找11 【正确答案】 C【试题解析】 B-树定义如下： 一棵 m 阶 B-树，或者是空树，或者是满足以下性质的 m 叉树： (1)根结点或者是叶子，或者至少有两棵子树，至多有 m 棵子树。 (2)除根结点外，所有非终端结点至少有 棵子树，至多有 m 棵子树。 (3)所有叶子结点都在树的同一层上。 (4)每个结点应包含如下信息：(n，A 0，K 1，A 1，K 2，A 2，K nAn)。其中： K i(1in)是关键字，且Ki+1(1in 一 1)； A i(i=0，1，n)为指向孩子结点的指针，且 Ai-1 所指
20、向的子树中所有结点的关键字都小于 Ki，A i 所指向的子树中所有结点的关键字都大于K。 n 是结点中关键字的个数，且 n+1 为子树的棵数。【知识模块】 查找12 【正确答案】 C【试题解析】 设 Ni 表示深度为 h 的平衡二叉树中含有的最少结点数，有： N0=0， N1=1， N2=2； 计算的公式为： N h=Nh-1+Nh-2+1； N 3=N2+N1+1=4； N4=N3+N2+1=7； N 5=N4+N3+1=12； N 6=N5+N4+1=2015。 也就是说，高度为 6 的平衡二叉树最少有 20 个结点，因此 15 个结点的平衡二叉树的高度为 5，而最小叶子结点的层数为 3，
21、所以选项 D 错误。 选项 A 在查找 30 后，指针应该指向左孩子，而不是右孩子；选项 B 与选项 A 存在同样的问题，因而选项 A、B错误。而选项 C 的查找路径如下图所示： 【知识模块】 查找13 【正确答案】 D【试题解析】 根据 B 树定义可知只有正确。【知识模块】 查找14 【正确答案】 C【试题解析】 此题考查的知识点是 B 一树和 B+树的定义。B 一树定义见第 11 题，B+树是应文件系统所需而发展出的一种 B 一树的变形树。一棵 m 阶的 B+树和 m阶的 B 一树的差异在于：(1)有 n 棵子树的结点中含有 n 个关键字。(2)所有的叶子结点中包含了全部关键字的信息，及指
22、向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。(3)所有的非终端结点可以看成是索引部分，结点中仅含其子树(根结点)中的最大(或最小) 关键字。通常在 B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。所以 B+树能有效地支持随机检索和顺序检索。显然应选 C。【知识模块】 查找15 【正确答案】 B【试题解析】 此题考查的知识点是 m 阶 B 一树的定义。B 一树是一种平衡的多路排序树，m 阶即 m 叉。应选 B。【知识模块】 查找16 【正确答案】 D【试题解析】 二分查找判定树如下图所示，查找 A3的比较序列的下标为9，4，2，3，本题选 D。 【
23、知识模块】 查找17 【正确答案】 C【试题解析】 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 次。【知识模块】 查找18 【正确答案】 B【试题解析】 分块查找时最佳块数为【知识模块】 查找19 【正确答案】 B【试题解析】 有 n 个结点且为完全二叉树的二叉排序树的高度为 log2n。【知识模块】 查找20 【正确答案】 D【试题解析】 对散列表进行检索，平均检索长度仅与装填因子 有关，而与关键
24、字个数 n 无关。【知识模块】 查找21 【正确答案】 C【试题解析】 由同义词的定义可知本题答案为 C。【知识模块】 查找22 【正确答案】 D【试题解析】 addr(49)=49 mod 11=5，冲突；h1=(5+1*1)mod 11=6，仍冲突；h2：(5+2*2)mod11=9 ，所以本题答案为 D。【知识模块】 查找二、综合应用题41-47 小题，共 70 分。23 【正确答案】 根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量 pre(初值为 null)和全局变量 flag，初值为 true。若非二叉排序树，
25、则置 flag 为 false。#deftne true 1#define false 0typedet struct nodedatatype data；struet：node*llink ，*rlink ：*BTree；void JudgeBSq(BTree t，int flag)判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由 flag 得出结论if(t!=null&flag)JudgeBST(t 一llink，flag) ； 中序遍历左子树if(pre=null)pre=t； 中序遍历的第一个结点不必判断else if(pre 一datadata)pre=t； 前驱指针指向当前
26、结点else flag=false： 不是二叉排序树JudgeBST(t 一rlink ，flag)； 中序遍历右子树本题的另一算法是依照定义，二叉排序树的左右子树都是二叉排序树，根结点的值大于左子树中所有值而小于右子树中所有值，即根结点大于左子树的最大值而小于右子树的最小值。算法如下：int JudgeBST(BTree t)判断二叉树 t 是否是二叉排序树，若是，返回 true，否则，返回 falseif(t=null)return true：if(JudgeBST(t 一llink)&JudgeBST(t 一rlink) 若左右子树均为二叉排序树m=max(t 一llink)；n=min
27、(t 一rlink)； 左子树中最大值和右子树中最小值return(t 一datam&t 一datarlink!=null)p=p 一rlink；return p 一data；int min(BTree p) 求二叉树右子树的最小值if(p=null)return maxint； 返回机器最大整数elsewhile(p 一llink!=null)p=p 一rlink ；return p 一data；【知识模块】 查找24 【正确答案】 借助于分块查找思想，在建立数据顺序表的同时，建立一索引表。数据表中按 k 个集合分块(元素个数不一定相等)，索引表中有两个域，一是各集合最后一个元素在数据表中的
28、位置(一维数组中的下标)，二是集合的个数(k)。实现数据运算时，根据给定的二元组(i，x)，首先在索引表中找到集合 i 的位置，然后在数据表中查找 x。查到 x，则查找成功，返回 x 在数据表中的位置，否则查找失败。若要插入，则将数据表中的数据后移，插入 x，同时修改索引表。 typedef structdatatype data；rectype； typedef struct int a； a 数组容量够大，存储各集合最后一个数 据在数据表中的下标 int k； 集合个数 index； int SetSearch_Insert(reetype R，index id，datatype x，in
29、t i) 数据表 R，查找第 i个集合的元素 x，若查找成功，返回其位置， 否则将其插入第 i 个集合 if(iidk) printf(“ 无第d 个集合n”，i)；exit(0)； if(i=1)first=0； first 指向第 i 个集合在数据表的首址 else first=idai1+1； last=idai； last 是第i 个集合在数据表中的末址 for(j=first；jidAi；j 一一) 查找失败，将 x 插入数据表 Rj+1=Rj； 元素后移 Rj+1=x ； 将 x 插入到原第 i 个集合最后一个元素之后 for(j=i ； jk；j+)idaj+； 修改索引表中各集
30、合最后一个元素的下标 由于各集合元素个数不等，各块长度不等且块间无序，索引表中用数组表示，数组中元素值是各集合最后一个元素在数据表中的下标。按本算法插入(2，1 1 2) 和 (1，53)，数据表前后状态如下： 插入前，索引表中 a 数组的内容是 3，6，12，插入后修改为 4，8，14。【知识模块】 查找25 【正确答案】 (1)非递归建立二叉排序树，在二叉排序树上插入的结点都是叶子结点。typedef struct nodeElemtype data；struct node*LLINK，*RLINK；node*BTree；void Create_BST(BiTree bst，datatyp
31、e K，int n)以存储在数组 K 中的 n 个关键字，建立一棵初始为空的二叉排序树int i；BiTree p，f ；for(i=1；idataRLINK； f 是 p 的双亲else if(p 一dataKi)f=p；p=p 一LLINK；s=(BiTree)malloc(sizeof(BNode) ；申请结点空间s 一data=Ki；s-LLINK=null；s-RLINK=null；if(f=null)bst=s： 根结点else if(s 一datadata)f 一LLINK=s ； 左子女else f 一RLINK=s； 右子树根结点的值大于等于根结点的值(2)本题要求输出遍历二
32、叉排序树的嵌套括号表示。其算法思想是，若二叉排序树非空，则输出根结点，再输出其左右子树。在输出其左右子树前，要输出左括号，在输出其右子树前要输出逗号，在输出其右子树后要输出右括号，在左右子树均空情况下，则不输出括号。void Print(BiTree t) 以嵌套括号表示结构打印二叉排序树if(t!=null)printf(t 一data)； 打印根结点值if(t 一LLINK|t 一LLINK) ； 左子女和右子女中至少有一个不空printf(“(”)； 输出左括号Print(t 一LLINK)； 输出左子树的嵌套括号表示if(t 一RLINK)printf(“，”)； 若右子树不空，输出逗
33、号Print(t 一RLINK)； 输出右子树的嵌套括号表示printf(“)”)； 输出右括号【知识模块】 查找26 【正确答案】 void Delete(BSTree t，p) 在二叉排序树 t 中，删除 f 所指结点的右孩子(由 p 所指向)if(p 一lchild=null)f 一rchild=p 一rchild ；free(p)；p 无左子女else ffj p 左子树中的最大值代替 p 结点的值q=p 一 lchild；s=q：while(q 一rchild) s=q；q=q 一rchild； 查 P 左子树中序序列最右结点if(s=p 一lchild) p 左子树的根结点无右子女
34、p 一 data=s 一data；p 一lchild=s 一lchild；free(s) ；elsep 一data=q 一data；s 一rchild=q 一lchild；free(q)；【知识模块】 查找27 【正确答案】 本题用被删结点右子树中最小值(中序遍历第一个)结点代替被删结点。void Delete(BSTree bst， p，fo)在二叉排序树 bst 上，删除 fo 所指结点的左子女(由 p 所指向)jf(!p 一lchild)fo 一lchild=p 一rchild；free(p)； p 无左子女else if(!p 一rchild)fo 一lchild=p 一lchild
35、； free(p)； p 无右子女else p 有左子女和右子女q=p 一rchild；s=q； 用 p 右子树中的最小值代替 p 结点的值while(q 一lchild)s=q；q=q 一lchild ； 查 p 右子树中序序列最左结点if(s=p 一rchild) p 右子树的根结点无左子女p 一 data=s 一data；p 一rchild=s-rchild；frees)；elsep 一data=q 一data；s 一lchild=q-rchild；free(q)；【知识模块】 查找28 【正确答案】 在二叉排序树上删除结点，首先要查找该结点。查找成功后，若该结点无左子树，则可直接将其右
36、子树的根结点接到其双亲结点上；若该结点有左子树，则将其左子树中按中序遍历的最后一个结点代替该结点，从而不增加树的高度。void Delete(BSTree bst， keytype x) 在二叉排序树 bst 上，删除其关键字为X 的结点BSTree f，p=bst ：while(P&p 一key!=X) 查找值为 X 的结点if(p 一keyX)f=p；p=p 一lchild；elsef=p；p=p 一rchild；if(p=null)printf(“无关键字为 X 的结点n”) ； exit(0)；if(p-lchild=null) 被删结点无左子树if(f 一lchild=p)f-lch
37、ild=p-rchild ；将被删结点的右子树接到其双亲上else f-rchild=p-rchild；elseq=p；s=p-lehild； 被删结点有左子树while(s 一rchild!=null) 查左子树中最右下的结点(中序最后结点)q=s；s=s 一rchild；p 一key=s-key： 结点值用其左子树最右下的结点的值代替if(q=p)p 一lchild=s-lchild； 被删结点左子树的根结点无右子女else q 一rchild=s 一lchild ； s 是被删结点左子树中序序列最后一个结点free(s)；【知识模块】 查找29 【正确答案】 intSearch(rect
38、ype r ，int n，keytype k)在 n 个关键字从小到大排列的顺序表中，查找关键字为 k 的结点rn+1key=MAXINT； 在高端设置监视哨int i=1；while(rikeykind=BRANCH&ibhptrord(KEYchi)，+i)； ord 求字符在字母表中的序号 if(P&P 一kind=LEAF&P 一lfK=KEY)return P 一Ifinfoptr； 查找成功 else return null； 【知识模块】 查找32 【正确答案】 用链地址法解决冲突的哈希表是一个指针数组，数组分量均是指向单链表的指针，(第 i 个)单链表结点有两个域，一个是哈希地
39、址为 i 的关键字，另一个是指向同义词结点的指针。删除算法与单链表上删除算法类似。typedef struct nodekeytype key；struct node *next；HSNode *HSList；typedef struct node *HLK；void Delete(HLK HT，keytype K)用链地址法解决冲突，从哈希表中删去关键字为 K 的记录int i=H(K)； 用哈希函数确定关键字 K 的哈希地址if(HTi=null)printf(“无被删除记录n”)；exit(0)；HLK p，q i p=Hi；q=p： p 指向当前记录(关键字)，q 是 p 的前驱whi
40、le(p&p 一key!=k)q=p ；p=p 一next；if(p=null)printf(“无被删除记录”) ；exit(0) ；if(q=Hi)HTi=HTinext；flee(p)； 被删除关键字是链表中第一个结点elseq 一next=p 一next；free(P)；【知识模块】 查找33 【正确答案】 本题仍用上面已定义的存储结构。首先计算关键字 K 的哈希地址，若该哈希地址的头指针为空，则直接插入；否则，先在该链表上查找，若查找失败，则插入链表；若查找成功，则不再插入。typedef struct nodekeytype key；struct node *next；HSNode
41、*HSList；typedef struet node *=HLK；void Insert(HLK HT，keytype K) 用链接表解决冲突的哈希表插入函数i=H(K)； 计算关键字 K 的哈希地址if(HTi=null) 关键字 K 所在链表为空 s=(HSNode*)malloc(sizeof(HSNode)；s 一key=k；s-next=HTi；HTi=s；else 在链表中查询关键字 Kp=HTi；while(p&p 一key!=k)p=p 一next；if(!p) 链表中无关键字 K，应该插入s=(HSNode*)malloc(sizeof(HSNode)；s 一next=HT
42、i；HTi=s； 插入后成为哈希地址为 i 的链表中的第一个结点【知识模块】 查找34 【正确答案】 首先计算关键字的散列地址，若该地址为空，则空操作；若该地址有关键字，但与给定值不等，则用解决冲突的方法去查找给定值；若该地址有关键字且与给定值相等，则执行删除。题目要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不断裂。由于用线性探测解决冲突，设被删除元素的散列地址为 i，则其余 m1(m 为表长)个位置均可能是同义词。查找同义词的操作直到碰到空地址或循环一圈回到 i 才能结束。为了提高算法效率，减少数据移动，应将最后一个同义词前移填充被删除关键字。void HsDelete(r
43、ectype HS，K)在以除余法为散列函数线性探测解决冲突的散列表 HS 中，删除关键字 Kint i=K P： 以造表所用的除余法计算关键字 K 的散列地址if(Hsi=null)printf(“散列表中无被删关键字”) ；exit(0)； 此处 null 代表散列表初始化时的空值switch(Hsi=k)case true：del(HS，i，j，K)；break；case false：di=1； j=(i+di)m； m 为表长while(Hsj!=null&Hsj!=K&j!=i) 查找关键字 Kdi=di+1：j=(i+di) m；if(HSj=K)del(HS，i，j，K)；els
44、eprintf(“散列表中无被删关键字”)；exit(0)； switchvoid del(rectype HS，in i，int j，rectype K)在散列表 HS 中，删除关键字 K，K 的散列地址是 i，因解决冲突而将其物理地置于表中位置 j。算法查找关键字 K 的同义词，将其最后一个同义词移到位置 j，并将其同义词的位置置空di=1；last=j ；x=(j+di) m； 探测地址序列，last 记 K 的最后一个同义词的位置while(x!=i) 可能要探测一圈if(HSx=null)break； 探测到空位置，结束探测else if(HSxP=i)last=x； 关键字 K 的
45、同义词di=di+1；x=(j+di) m； 取下一地址探测Hsj=HSlast；HSlast=nuu； 将哈希地址 last 的关键字移到哈希地址 j算法讨论：由于用线性探测解决冲突，可能发生“二次聚集”( 两个第一哈希地址不同的记录争夺同一后继哈希地址)。像上面这样处理后，对于哈希地址为 i 的记录没有问题了，但由于将地址 j 置空，有可能截断了其他记录的探测通路。最明显的是哈希地址为 j 的记录就查不到了。解决的办法是继续调整，直到当前哈希表中的每个记录的查找都是正确的为止。这里不再深入讨论。【知识模块】 查找35 【正确答案】 利用二叉排序树的性质，从根结点开始查找，若根结点的值小于等
46、于 x，则根结点及其左子树均应删除，然后以右子树的根结点为树根，重新开始查找。若根结点的值大于 x，则顺左子树向下查找，直到某结点的值小于等于 x，则该结点及其左子树均应删除。下面设计一查找算法，确定被删除子树的根结点，再设计一删除算法，删除以被删结点为根的子树。typedef struct nodeint data；struct node *left， *right；BiTNode，*BSTree；void DelTree(BSTree r) 非递归删除以 r 为根的二叉排序树BSTree S； 栈，容量足够大，栈中元素是二叉排序树结点的指针BSTree p；int top=0；while(r!=null|top0)while(r!=null)S+top=r；r=r-left ； 沿左分支向下if(top0) 退栈，沿栈顶结点的右子树向下删除，释放被删除结点空间p=Stop 一一；r=p 一right ；free(p) ； DelTreevoid DeleteAllx(BSTree T，int x) 在二叉排序树 T 中，删除所有小于等于x 的结点BSTree =pT，q；while(T&T-dataright ；p 一right=null；DelTree(p)； 删除二叉树 P，删除持续到 ”根”结点值大于 x 或 T 为空树为止i
