计算机专业基础综合数据结构(查找)-试卷1

(总分：88.00，做题时间：90分钟)

一、 单项选择题(总题数：23，分数：48.00)

1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

__________________________________________________________________________________________ 解析：

2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。 （分数：2.00） A.(n一1)／2 B.n／2

C.(n+1)／2 √ D.n

解析：解析：此题考查的知识点是顺序查找长度ASL的计算。假设表长度为n，那么查找第i个数据元素需进行n—i+1次比较，即C i =n一i+1。又假设查找每个数据元素的概率相等，即P i =1／n，则顺序查找算法的平均查找长度为： 所以应选C。

顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( (1) )，二分法查找只适用于查找顺序存储的有序表，平均比较次数为( (2) )。在此假定Ⅳ为线性表中结点数，且每次查找都是成功的。（分数：4.00）

(1).(1)（分数：2.00） A.N+1 B.2log 2 N C.log 2 N D.N／2 √ 解析：

(2).(2)（分数：2.00） A.N+1 B.2log 2 N C.log 2 N √ D.N／2

解析：解析：此题考查的知识点是各类查找算法的比较次数计算。顺序查找法用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败，其ASL=(n+1)／2，即查找成功时的平均比较次数约为表长的一半。 二分法查找过程可用一个称为判定树的二叉树描述，由于判定树的叶子结点所在层次之差最多为1，故n个结点的判定树的深度与n个结点的完全二叉树的深度相等，均为[log 2 n]+1。这样，折半查找成功时，关键字比较次数最多不超过[log 2 n]+1。所以，(1)应选择D，(2)应选C。 3.适用于折半查找的表的存储方式及元素排列要求为( )。 （分数：2.00）

A.链接方式存储，元素无序 B.链接方式存储，元素有序 C.顺序方式存储，元素无序 D.顺序方式存储，元素有序 √

解析：解析：此题考查的知识点是折半查找的特点。折半查找要求顺序存储且元素有序，所以应选D。 4.具有12个关键字的有序表，折半查找的平均查找长度为( )。 （分数：2.00） A.3．1 √ B.4

C.2．5 D.5

解析：解析：此题考查的知识点是折半查找的思想。把关键字按完全二叉树的形式画出查找树，按结点高度计算比较次数。12个结点可以画出高度为4的完全二叉树，1层1个结点比较1次，2层2个结点比较2次，3层4个结点比较3次，4层5个结点比较4次，37／12≈3．1，应选A。 5.折半查找的时间复杂性为( )。 （分数：2.00） A.O(n ) B.O(n) C.O(nlog 2 n) D.O(log 2 n) √

解析：解析：此题考查的知识点是折半查找的效率。其查找效率与比较次数有关，折半查找成功时，关键字比较次数最多不超过[log 2 n]+1，所以其效率为O(log 2 n)，应选D。 6.当采用分块查找时，数据的组织方式为( )。 （分数：2.00）

A.数据分成若干块，每块内数据有序

B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块 √ C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块 D.数据分成若干块，每块(除最后一块外)中数据个数需相同

解析：解析：分块查找是将数据分成若干块，块间有序，块内不必有序。

7.下面函数的功能是实现分块查找，空白处应该添加的内容是( )。 int BlkSearch(int*nz，mt key，int block，int BLK，int len) { int i； block=block-1； if(len＜=0) { puts(”表为空!．”)： return 0： } if(BLKd＞len)BLK=len； for(i=block*BLK；i＜(block+1)*BLK&&nz[i]!=0；i++) { if( ) { printf(”找到第％d个数是％d＼n”，i，key)； return 0： } }printf(”＼n”)； printf(”查找结束＼n”)； return 0； } （分数：2.00） A.nz[i]==key √ B.nz[i]==BLK C.nz[i]==block D.nz[i]==0

解析：解析：如果当前的值与所查找关键字相等，则完成查找。

二叉查找树的查找效率与二叉树的( (1) )有关，在( (2) )时其查找效率最低。（分数：4.00） (1).(1)（分数：2.00） A.高度 B.结点的多少 C.树形 √ D.结点的位置 解析：

(2).(2)（分数：2.00） A.结点太多 B.完全二叉树 C.呈单枝树 √ D.结点太复杂

解析：解析：二叉查找树的查找效率与树形有关，当结点呈单枝树排列时效率最低。 8.在一棵高度为九的理想平衡二叉树中，最少含有( )个结点，最多含有( )个结点。 （分数：2.00） A.2 2 B.2 一1 2 C.2 +1 2 一1

h

h

h

h

h

h-12

D.2 2 一1 √

解析：解析：由平衡二叉树的特性可知，一棵高度为h的理想平衡二叉树中，含有结点数最少的情形是：前h一1层为满二叉树，第h层只有一个结点，因而结点总数为(2 一1)+1=2 。 最多的情形是：该树是一棵高度为h的满二叉树，因而结点总数为2 一1。 9.分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是( )。 （分数：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)

解析：解析：分别根据给出的序列构建平衡二又树，得出c与其他不同。 10.关于B一树，下列说法中不正确的是( )。 （分数：2.00） A.B一树是一种查找树

B.所有的叶结点具有相同的高度

C.2-3树中，所有非叶子结点有1或者3个孩子结点 √ D.通常情况下，B一树不是二叉树

解析：解析：B一树定义如下： 一棵m阶B一树，或者是空树，或者是满足以下性质的m叉树： (1)根结点或者是叶子，或者至少有两棵子树，至多有m棵子树。 (2)除根结点外，所有非终端结点至少有[m／2]棵子树，至多有m棵子树。 (3)所有叶子结点都在树的同一层上。 (4)每个结点应包含如下信息：(n，A ，0 K 1 ，A 1 ，K 2 ，A 2 ，…，K n ，A n )。其中： K i (1≤i≤n)是关键字，且K i ＜K i+1 (1≤i≤n—1)： A i (i=0，1，…，n)为指向孩子结点的指针，且A i-1 所指向的子树中所有结点的关键字都小于K i ，A i 所指向的子树中所有结点的关键字都大于K。 n是结点中关键字的个数，且[m／2]一1≤n≤m一1，n+1为子树的棵数。

11.在含有15个结点的平衡二叉树上，查找关键字为28(存在该结点)的结点，则依次比较的关键字有可能是( )。 （分数：2.00） A.30，36 B.38，48，28

C.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

hh-1

h-1

h-1h

含有结点数 =N 5 +N 4 +1=20＞150 也就是说，高度为6的平衡二叉树最少有20个结点，因此15个结点的平衡二叉

选项A在查找30后，指针应该指向

树的高度为5，而最小叶子结点的层数为3，所以选项D错误。 左孩子，而不是右孩子；选项B与选项A存在同样的问题，因而选项A、B错误。而选项C的查找路径如下图所示： 12.下面关于m阶B树的说法中，正确的是( )。 ①每个结点至少有两棵非空子树。 ②树中每个结点至多有m一1个关键字。 ③所有叶子在同一层上。 ④当插入一个数据项引起B树结点后，树长高一层。 （分数：2.00） A.①②③ B.②③ C.②③④ D.③ √

解析：解析：根据B树定义可知只有③正确。

13.下面关于B和B+树的叙述中，不正确的是( )。 （分数：2.00）

A.B树和B+树都是平衡的多叉树 B.B树和B+树都可用于文件的索引结构 C.B树和B+树都能有效地支持顺序检索 √ D.B树和B+树都能有效地支持随机检索

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

解析：解析：此题考查的知识点是m阶B一树的定义。B一树是一种平衡的多路排序树，m阶即m叉。应选B。

15.若对有18个元素的有序表做二分查找，则查找A[3]的比较序列的下标为( )。 （分数：2.00） A.1，2，3 B.9，4，2，3 C.10，5，3 D.9，2，3 √

解析：解析：二分查找判定树如下图所示，查找A[3]的比较序列的下标为9，4，2，3，本题选D。16.有一个有序表{1，3，9，12，32，41，45，62，75，77，82，95，100}，当用二分查找法查找值为82的结点时，经( )次比较后查找成功。 （分数：2.00） A.1 B.2 C.4 √ D.8

解析：解析：n=13，R[11]=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次。 17.采用分块查找时，若线性表有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，则每块分为( )个结点最佳。 （分数：2.00） A.9 B.25 √ C.6 D.625

解析：解析：分块查找时最佳块数为（分数：2.00） A.O(n)

。

18.在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为( )。

B.O(log 2 n) √ C.O(nlog 2 n) D.O(n )

解析：解析：有n个结点且为完全二叉树的二叉排序树的高度为log 2 n。 19.对包含n个关键码的散列表进行检索，平均检索长度为( )。 （分数：2.00） A.O(log 2 n) B.O(n) C.O(nlog 2 n) D.不直接依赖于n √

解析：解析：对散列表进行检索，平均检索长度仅与装填因子α有关，而与关键字个数n无关。 20.在散列表上，每个地址单元所链接的同义词表的( )。 （分数：2.00） A.键值相同 B.元素值相同 C.散列地址相同 √ D.含义相同

解析：解析：由同义词的定义可知本题答案为C。

21.设哈希表长m=14，哈希函数H(key)=key mod 11。表中已有4个结点addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空，如用二次探测再散列法处理冲突，则关键字为49的结点的地址是( )。 （分数：2.00） A.8 B.3 C.5 D.9 √

解析：解析：addr(49)=49 mod 11=5，冲突；hl=(5+1-1)mod 11=6，仍冲突；h2=(5+2*2)mod11=9，所以本题答案为D。

2

二、 综合应用题(总题数：20，分数：40.00)

22.综合应用题41-47小题。（分数：2.00）

__________________________________________________________________________________________ 解析：

23.请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink—rlink法存储。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre(初值为null)和全局变量flag，初值为true。若非二叉排序树，则置flag为false。 #define true 1 #define false 0 typedef struct node{ datatype data； struct node * llink，* rlink： }*BTree； void JudgeBST(BTree t，int flag){ ／／判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论 if(t!=null&&flag){ JudgeBST(t一＞llink，flag)： ／／中序遍历左子树 if(pre==null)pre=t； ／／中序遍历的第一个结点不必判断 else if(pre一＞data＜t一＞data)pre=t； ／／前驱指针指向当前结点 else flag=false： ／／不是二叉排序树 JudgeBST(t一＞rlink，flag)； ／／中序遍历右子树 } } 本题的另一算法是依照定义，二叉排序树的左右子树都是二叉排序树，根结点的值大于左子树中所有值而小于右子树中所有值，即根结点大于左子树的最大值而小于右子树的最小值。算法如下： int JudgeBST(BTree t){ ／／判断二叉树t是否是二叉排序树，若是，返回true，否则，返回false if(t==null)return true； if(JudgeBST(t-＞

llink)&&JudgeBST(t-＞rlink)){ ／／若左右子树均为二叉排序树 m=max(t一＞llink)：n=min(t-＞rlink)； ／／左子树中最大值和右子树中最小值 return(t一＞data＞m&&t一＞data＜n)； } else return false： ／／不是二叉排序树 } int max(BTree p／{ ／／求二叉树左子树的最大值 if(p==null)return-maxint； ／／返回机器最小整数 else{ while(p一＞rlink!=null)P=p一＞rlink； return p一＞data； } } int

min(BTree P){ ／／求二叉树右子树的最小值 if(P==null)return maxint； ／／返回机器最大整数 else{ while(p一＞llink!=null)p=p一＞rlink； return p一＞data； } }) 解析：

24.某个任务的数据模型可以抽象为给定的k个集合：S 1 ，S 2 ，…，S k 。其中S i (1≤i≤k中的元素个数不定。在处理数据过程中将会涉及元素的查找和新元素的插入两种操作，查找和插入时用一个二元组(i，x)来规定一个元素，i是集合的序号，x是元素值。设计一种恰当的数据结构来存储这k个集合的元素，并能高效地实现所要求的查找和插入操作。 (1)构造数据结构，并且说明选择的理由。 (2)若一组数据模型为S ={10．2，1．7，4．8，16．2}，S ={1．7，8．4，0．5}，S ={4．8，4．2，3．6，2．7，5．1，1 2 3 3．9}，待插入的元素二元组为(2，11．2)和(1，5．3)，按你的设计思想画出插入元素前后的数据结构状态。

（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：借助于分块查找思想，在建立数据顺序表的同时，建立一索引表。数据表中按k个集合分块(元素个数不一定相等)，索引表中有两个域，一是各集合最后一个元素在数据表中的位置(一维数组中的下标)，二是集合的个数(k)。实现数据运算时，根据给定的二元组(i，x)，首先在索引表中找到集合i的位置，然后在数据表中查找x。查到x，则查找成功，返回x在数据表中的位置，否则查找失败。若要插入，则将数据表中的数据后移，插入x，同时修改索引表。 typedef struct{datatype data；}rectype； typedef struct{ int a[]； ／／a数组容量够大，存储各集合最后一个数 据在数据表中的下标 int k： ／／集合个数 }index； int SetSearch_Insert(rectype R[]I index id，datatype x，int i){ ／／数据表R，查找第i个集合的元素X，若查找成功，返回其位置， ／／否则将其插入第i个集合 if(i＜1 || i＞id．k){printf(”无第％d个集合＼n”，i)；exit(0)； } if(i==1)first=0； ／／first指向第i个集合在数据表的首址 else first=id．a[i一1]+1； last=id．a[i]； ／／last是第i个集合在数据表中的末址 for(j=first；j＜last；j++)if(R[j]==X)return(j)； ／／查找成功 for(j=id．a[id．k]；j＞id．A[i]；j--){ ／／查找失败，将x插入数据表 R[j+1]=R[j]； ／／元素后移 R[j+1]=x： ／／将X插入到原第i个集合最后一个元素之后 for(j=i；j≤k；j++)id．a[j]++； ／／修改索引表中各集合最后一个元素的下标 } 由于各集合元素个数不等，各块长度不等且块间无序，索引表中用数组表示，数组中元素值是各集合最后一个元素在数据表中的下标。按本算法插入(2，11．2)和(1，5．3)，数据表前后状态如下：解析：

25.假设K 1 ,…，K n 是n个关键词，试解答： (1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K 1 ，K 2 ，…，K n 时，用算法建立一棵以LLINK—RIJNK链接表示的二叉查找树。 (2)设计一个算法，打印出该二叉查找树的嵌套括号表示结构。假定该二叉查找树的嵌套括号表示结构为B(A，D(C，E))。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：(1)非递归建立二叉排序树，在二叉排序树上插入的结点都是叶子结点。 typedef struet node{ Elemtype data； struet node*LLINK，*RLINK： }node*BiTree； void Create_BST(B／Tree bst，datatype K[]，int n){ ／／以存储在数组K中的n个关键字，建立一棵初始为空的二叉排序树 int i； BiTree P，f； for(i=1；i＜=n；i++){ P=bst：f=null； ／／在调用Create_BST时，bst=null while(P!=null) if(P-＞data＜K[i]){f=P；P=p一＞RLINK；} I／f是P的双亲 else if(p-＞data＞K[i]){f=p：P=p一＞LLINK；} S=(BiTree)malloc(sizeof(B／Node))；／／申请结点空间 s-＞data=K[i]；s-＞LLINK=null；s一＞RLINK=null； if(f==null)bst=S： ／／根结点 else if(s一＞data＜f一＞data)f-＞LLINK=s； ／／左子女 else f一＞RLINK=s： ／／右子树根结点的值大于等于根结点的值 } } (2)本题要求输出遍历二又排序树的嵌套括号表示。其算法思想是，若二叉排序树非空，则输出根结点，再输出其左右子树。在输出其左右子树前，要输出左括号，在输出其右子树前要输出逗号，在输出其右子树后要输出右括号，在左右子树均空情况下，则不输出括号。 void Print(BiTree t){ ／／以嵌套括号表示结构打印二叉排序树 if(t!=null){ printf(t-＞data)： ／／打印根结点值 if(t一＞LLINK ||t-＞LLINK)； ／／左子女和右子女中至少有一个不空 printf(”(”)； ／／输出左括号 Print(t-＞LLINK)； ／／输出左子树的嵌套括

插入前，索引表中a数组的内容是3，6，12，插入后修改为4，8，14。)

号表示 if(t-＞RLINK)printf(”，”)； ／／若右子树不空，输出逗号 Print(t一＞RLINK)： ／／输出右子树的嵌套括号表示 printf(”)”)； ／／输出右括号 } }) 解析：

26.写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设删除结点由指针p所指，其双亲结点由指针f所指，并假设被删除结点是其双亲结点的右孩子。描述上述算法。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：void Delete(BSTree t，P){ ／／在二叉排序树t中，删除f所指结点的右孩子(由P所指向) if(P一＞lchild==null){f一＞rchild=P一＞rchild；free(P)；}／／p无左子女 else{ ／／用P左子树中的最大值代替P结点的值 q=P一＞lchild；s=q； while(q一＞rchild){ S=q；q=q-＞rchild；} ／／查P左子树中序序列最右结点 if(s==p一＞lchild) ／／p左子树的根结点无右子女 {p一＞data=s一＞data；p一＞lchild=s一＞lchild；free(S)；} else{p一＞data=q一＞data；s一＞rchild=q一＞lehild；free(q)；} } }) 解析：

27.已知二叉树排序树中某结点指针p，其双亲结点指针为fp，p为fp的左孩子。试编写算法，删除p所指结点。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：本题用被删结点右子树中最小值(中序遍历第一个)结点代替被删结点。 void Delete(BSTree bst，P，fp){ ／／在二叉排序树bst上，删除fp所指结点的左子女(由P所指向) if(!p一＞lchild){fp一＞lchild=p一＞rchild；free(P)；} ／／p无左子女 else if(!p一＞rchild){fp一＞lchild=p一＞lchild；free(P)；} ／／p无右子女 else ／／P有左子女和右子女 {q=P一＞rchild；s=q； ／／用P右子树中的最小值代替P结点的值 while(q一＞lchild){s=q；q=q一＞lchild；} ／／查P右子树中序序列最左结点 if(s==p一＞rehild) ／／p右子树的根结点无左子女 {p一＞data=s一＞data；p一＞rchild=s一＞rchild；frees)；} else{p一＞data=q一＞data；s一＞lchild=q-＞rchild；free(q)；} } }) 解析：

28.二叉排序树采用二叉链表存储。写一个算法，删除结点值是X的结点。要求删除该结点后，此树仍然是一棵二叉排序树，并且高度没有增长(注意：可不考虑被删除的结点是根的情况)。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：在二叉排序树上删除结点，首先要查找该结点。查找成功后，若该结点无左子树，则可直接将其右子树的根结点接到其双亲结点上；若该结点有左子树，则将其左子树中按中序遍历的最后一个结点代替该结点，从而不增加树的高度。 void Delete(BSTree bst，keytype X){ ／／在二叉排序树bst上，删除其关键字为X的结点 BSTree f，P=bst： while(P&&p一＞key!=X) ／／查找值为X的结点 if(p一＞key＞X){f=P；p=p-＞lehild；} else{f=p；P=p一＞rehild；} if(P==null){prinff(”无关键字为x的结点＼n”)；exit(0)：} if(p-＞lchild==null){ ／／被删结点无左子树 if(f一＞lchild==P)f一＞lchild=P一＞rchild；／／将被删结点的右子树接到其双亲上 else f一＞rchild=p一＞rchild； } else{q=p；s=p-＞lchild； ／／被删结点有左子树 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.设记录R 1 ，R 2 ，…，R n 按关键字值从小到大顺序存储在数组r[1．．n]中，在r[n+1]处设立一个监督哨，其关键字值为+∞。试写一查找给定关键字k的算法，并画出此查找过程的判定树，求出在等概率情况下查找成功时的平均查找长度。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：intSearch(rectype r[]，int n，keytype k){ ／／在n个关键字从小到大排列的

顺序表中，查找关键字为k的结点 r[n+1]．key=MAXINT； ／／在高端设置监视哨 int i=1： while(r[i]．key＜k)i++； if(r[n+1]．key==k)return(i％(n+1))； else return(0)； } 查找过程的判定树是单枝树。本题中虽然表按关键字有序，但进行顺序查找，查找成功的平均查找长度亦为(n+1)／2。) 解析：

30.给出折半查找的递归算法，并给出算法时间复杂度分析。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：int BinSrch(rectype r[]，int k，low，high){ ／／在长为n的有序表中查找关键字k，若查找成功，返回k所在位置，查找失败返回0 if(low＜=high){ ／／low和high分别是有序表的下界和上界 mid=(low+high)／2； if(r[mid]．key==k)return(mid)； else if(r[mid]．key＞k)return(BinSrch(r，k，mid+1，high))； else return(BinSrch(r，k，low，mid一1))； } else return 0： ／／查找失败 } 算法时间复杂度为O(log 2 n)。) 解析：

31.键树(Trie)，又称数字查找树，它是一棵度大于等于2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。请用类C语言或类PASCAL语言编写一个在键树T上查找关键字等于给定值KEy的记录的算法。若查找成功，返回指向该记录的指针；否则返回空指针。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：在Trie树上查找给定值KEY的过程如下：沿和给定值相应的指针向下，直至叶子结点，若叶子中的关键字和KEY相等，则查找成功；若分支结点中和给定值相应的指针为空，或叶子结点中的关键字和给定值不等，则查找不成功。 typedef enum{LEAF，BRANCH}NodeKind； ／／结点种类{叶子，分支} typedef struct TrieNode{ NodeKind kind； union{struct{KeyType K；Record*infoptr}If； ／／叶子结点 struct{TrieNode*ptr[27]；int hum}bh； ／／分支结点 }； }TrieNode，*TrieTree； ／／键树类型 Record * SearchTrie(TrieTree T，KeyType KEY){ ／／在Trie树T中查找关键字等于K的记录 for(P=T，i=0； ／／对KEY的每个字符逐个查找 P&&P-＞kind==BRANCH&&i＜K．Bum； ／／*P为分支结点 P=P一＞bh．ptr[ord(KEY．ch[i])]，++i)： ／／ord求字符在字母表中的序号 if(P&&P一＞kind==LEAF&&P一＞lf．K==KEY)return P一＞lf．infoptr； ／／查找成功 else return null； }) 解析：

32.写出从哈希表中删除关键字为K的一个记录的算法。设哈希函数为H，解决冲突的方法为链地址法。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：用链地址法解决冲突的哈希表是一个指针数组，数组分量均是指向单链表的指针，(第i个)单链表结点有两个域，一个是哈希地址为i的关键字，另一个是指向同义词结点的指针。删除算法与单链表上删除算法类似。 typedef struct node{ keytype key； struct node*next： }HSNode * HSList； typedef struct node*HLK； void Delete(HLK HT[]，keytype K){ ／／用链地址法解决冲突，从哈希表中删去关键字为K的记录 int i=H(K)； ／／用哈希函数确定关键字K的哈希地址 if(HT[i]==null){printf(”无被删除记录＼n”)；exit(0)；} HLK P，q；p=H[i]：q=p； ／／p指向当前记录(关键字)，q是P的前驱 while(P&&p一＞key!=k){q=P；P=P一＞next；} if(P==null){printf(”无被删除记录”)；exit(0)；} if(q==H[i]){HT[i]=HT[i]．next；free(P)；} ／／被删除关键字是链表中第一个结点 else{q一＞next=p一＞next；free(P)；} }) 解析：

33.用C语言或PASCAL编写一用链接表(Linked List)解决冲突的哈希表插入函数。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：本题仍用上面已定义的存储结构。首先计算关键字K的哈希地址，若该哈希地址的头指针为空，则直接插入；否则，先在该链表上查找，若查找失败，则插入链表；若查找成功，则不再插入。 typedef struct node{ keytype key； struct node*next； }HSNode * HSList： typedef struct node*HLK： void Insert(HLK HT[]，keytype K){ ／／用链接表解决冲突的哈希表插入函数 i=H(K)； ／／计算关键字K的哈希地址 if(HT[i]==null) ／／关键字K所在链表为空 {s=(HSNode *)malloc(sizeof(HSNode))；

s一＞key=k；s-＞next=HT[i]：HT[i]=s；} else{ ／／在链表中查询关键字K P=HT[i]； while(P&&p一＞key!=k)P=p-＞next： if(!P){ ／／链表中无关键字K，应该插入 S=(HSNode*)malloc(sizeof(HSNode))： s-＞next=HT[i]；HT[i]=S； } ／／插入后成为哈希地址为i的链表中的第一个结点 } }) 解析：

34.在用除余法作为散列函数线性探测解决冲突的散列表中，写一删除关键字的算法，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不至于断裂。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：首先计算关键字的散列地址，若该地址为空，则空操作；若该地址有关键字，但与给定值不等，则用解决冲突的方法去查找给定值；若该地址有关键字且与给定值相等，则执行删除。题目要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不断裂。由于用线性探测解决冲突，设被删除元素的散列地址为i，则其余m一1(m为表长)个位置均可能是同义词。查找同义词的操作直到碰到空地址或循环一圈回到i才能结束。为了提高算法效率，减少数据移动，应将最后一个同义词前移填充被删除关键字。 void HsDelete(rectype HS[]，K){ ／／在以除余法为散列函数线性探测解决冲突的散列表HS中，删除关键字K int i=K％P： ／／以造表所用的除余法计算关键字K的散列地址

if(HS[i]==null){printf(”散列表中无被删关键字”)； exit(0)； } ／／此处null代表散列表初始化时的空值 switch(HS[i]==k){ case true：del(HS，i，j，K)；break； case false：di=1；j=(i+di)％m； ／／m为表长 while(HS[j]!=null&&HS[j]!=K&&J!=i){ ／／查找关键字K di=di+1： j=(i+di)％m； } if(HS[j]==K)del(HS，i，j，K)； else{printf(”散列表中无被删关键字”)；exit(0)；} }／／switch } void 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(HS[x]==null)break； ／／探测到空位置，结束探测 else if(HS[x]％P==i)last=x； ／／关键字K的同义词 di=di+1；x=(j+di)％m； ／／取下一地址探测 } HS[j]=HS[last]；HS[last]=null； ／／将哈希地址last的关键字移到哈希地址j } 算法讨论：由于用线性探测解决冲突，可能发生“二次聚集”(两个第一哈希地址不同的记录争夺同一后继哈希地址)。像上面这样处理后，对于哈希地址为i的记录没有问题了，但由于将地址j置空，有可能截断了其他记录的探测通路。最明显的是哈希地址为j的记录就查不到了。解决的办法是继续调整，直到当前哈希表中的每个记录的查找都是正确的为止。这里不再深入讨论。) 解析：

35.设排序二叉树中结点的结构由三个域构成：数据域data，指向左儿子结点的指针域left，指向右儿子结点的指针域right。设data域为正整数，该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序，实现将data域的值小于等于x的结点全部删除。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：利用二叉排序树的性质，从根结点开始查找，若根结点的值小于等于x，则根结点及其左子树均应删除，然后以右子树的根结点为树根，重新开始查找。若根结点的值大于x，则顺左子树向下查找，直到某结点的值小于等于x，则该结点及其左子树均应删除。下面设计一查找算法，确定被删除子树的根结点，再设计一删除算法，删除以被删结点为根的子树。 typedef struct node{ int data； struct node*left * right： }BiTNode，* BSTree； void DelTree(BSTree r){ ／／非递归删除以r为根的二叉排序树 BSTree S[]； ／／栈，容量足够大，栈中元素是二叉排序树结点的指针 BSTree P； int top=0； while(r!=null || top＞0){ while(r!=null){S[++top]=r；r=r一＞left；} ／／沿左分支向下 if(top＞0) ／／退栈，沿栈顶结点的右子树向下删除，释放被删除结点空间 {p=S[top一一]；r=p一＞fight；free(P)；} } }／／DelTree void DeleteAllx(BSTree T，int X){ ／／在二叉排序树T中，删除所有小于等于X的结点 BSTree P=T，q； while(T&＆T-＞data＜=x){ ／／根结点的值小于等于x P=T；T=T一＞fight；p一＞fight=null； DelTree(P)； } ／／删除二叉树P，删除持续到”根”结点值大于x或T为空树为止 if(T){ q=T；P=T一＞left； while(P&&P一＞data＞x){ ／／沿根结点左分支向下，查小于等于x的结点 while(P＆&p一＞data＞x){q=p；p=p一＞left；} ／／q记P的双亲 if(P) ／／p结点的值

小于等于X { q一＞left=p一＞fight；p一＞fight=null；DelTree(P)； } P=q一＞left； ／／再查原P的右子树中小于等于X的结点 } } }) 解析：

36.已知二叉树T的结点形式为(llink，data，count，rlink)，在树中查找值为X的结点，若找到，则记数(count)加1；否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：typedef struct node{ datatype data； int count； struct node * llink，*rlink： }BiTNode，*BSTree； void Search_InsertX(BSTree t，datatype X){ ／／在二叉排序树t中查找值为X的结点，若查到，则其结点的count域值增1， ／／否则，将其插入到二叉排序树中 BSTree p=t： while(P!=null&&P-＞data!=X){ ／／查找值为x的结点，f指向当前结点的双亲 f=p; if(P一＞data＜X)P=p一＞rlink； else p=p一＞llink： } if(!P){ ／／无值为X的结点，插入之

P=(BiTNode*)malloc(sizeof(BiTNode))： p一＞data=X；p一＞llink=null；p一＞rlink=null； if(f一＞data＞X)f一＞llink=P： else f一＞rlink=P： } else p-＞count++； ／／查询成功，值域为X的结点的count增1 }) 解析：

37.假设一棵平衡二叉树的每个结点都标明了平衡因子b，试设计一个算法，求平衡二叉树的高度。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：因为二叉树各结点已标明了平衡因子b，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子b为0时，任选左右一分支向下查找，若b不为0，则沿左(当b=1时)或右(当b=一1时)向下查找。 int Height(BSTree t){ ／／求平衡二叉树t的高度 int level=0： BSTree p=t； while(P){ level++： ／／树的高度增1 if(p-＞bf＜0)P=p-＞rchild；／／bf=一1沿右分支向下 ／／bf是平衡因子，是二叉树t结点的一个域，因篇幅所限，没有写出其存储定义 else P=P一＞lchild： ／／bf＞=0沿左分支向下 }／／while return(level)： ／／平衡二叉树的高度 }／／算法结束) 解析：

38.设从键盘输入一个整数的序列：n，a 1 ，a 2 ，…，a n ，其中n表示连续输入整数的个数。 (1)试编写一程序按整数值建立一个二叉排序树。 (2)在(1)的基础上将此二叉树上的各整数按降序写入一磁盘文件中。

（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：二叉排序树的建立问题前面第3题的(1)中已介绍，此处不再赘述。将二叉排序树上的各整数按降序写入磁盘，要对二叉排序树进行“中序遍历”，这里的“中序遍历”要采取“右根左”。为方便起见，先将整数写入一全局变量数组中，再写入磁盘文件中。 int i=0，a[n]： ／／长度为n的整型数组 void lnOrder(BSTree t){ ／／先右后左的中序遍历二叉排序树t，假定该树t已在第3题(1)中生成 if(t){ InOrder(t-＞rchild)； a[i++]=t-＞key； InOrder(t-＞lchild)； } } void SaveToDisk(){ //将二叉排序树上的各整数按降序写入磁盘 FILE*fp：

if((fo=fopen(”filel．dat”，”wb”))==null){ printf(”file can not open!＼n”)；exit(0)； } fwrite(a，sizeof(int)，n，fp)； ／／将数组a中的n个整数写入磁盘 fclose(fp)； ／／关闭文件 }) 解析：

39.设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空、右子树非空的结点的数据域的值。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：(1)递归算法 void DecPrint(BSTree t){ ／／递减序输出二叉排序树t中所有左子树为空、右子树非空的结点数据域的值 if(t){ DecPrint(t一＞rchild)： if(!t一＞lchild&&t一＞rchild)printf(t一＞data：4)； DecPrint(t一＞lchild)： } } (2)非递归算法 void DecPrint(BSTree t){ ／／递减序输出二叉排序树t中所有左子树为空、右子树非空的结点的值 BSTree s[]； ／／s是二

叉排序树结点指针的栈，容量足够大 int top=0： while(t || top＞0){ while(t){s[++top]=t；t=t-＞rchild；}／／沿右分支向下 if(top＞0){ t=s[top--]； if(!t一＞lchild&&t一＞rchild)printf(t一＞data：4)： t=t一＞lchild； ／／去左分支 }／／if }／／while }／／算法结束) 解析：

40.在单链表中，每个结点含有5个正整型的数据元素(若最后一个结点的数据元素不满5个，以值0充)，试编写一算法查找值为n(n＞0)的数据元素所在的结点指针以及在该结点中的序号，若链表中不存在该数据元素则返回空指针。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：这是一个在单链表中查找结点，在结点内查找给定值的过程，先定义存储结构。 typedef struct node{ int A[m]： ／／每个结点内含有m个正整数，本例中m为5 struct node *next； ／／指向下一结点的指针 }LNode，*LinkList： typedef struct{ int j； ／／i整数在结点内的序号 struct node *s； ／／结点的指针 }rcd； rcd * LSearch(LinkList head，int n){ ／／在链表中查找正整数n，若查找成功，返回该结点指针及n在结点中的序号， ／／否则返回空指针表示失败。 rcd*R； P=head一＞next； ／／假定链表带头结点，P指向链表第一元素结点 int found=0． mt 1； while(P&&!found){ for(i=0；i＜m；i++) if(P-＞A[i]==n)found=1 ／／查找成功 P=P-＞next： ／／下一结点 } if(P==null)return(null)； else{R．j=i；R．S=P；return(R)；} }) 解析：

41.编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，且查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：int Search(rectype R[]，int n，K){ ／／在具有n个元素的有序表R中，顺序查找值为K的结点，查找成功返回其位置， ／／否则返回一1表示失败 int i=0： while(i＜

n){ if(R[i]==K)return(i)； else if(R[i]＞K)return(一1)； i++： }／／while return一1； } 在等概率的情况下，则查找成功的平均查找长度为(n+1)／2，查找失败的平均查找长度为(n+2)／2(失败位置除小于第一个，还存在大于最后一个)。若查找成功和不成功的概率也相等，则查找成功时和关键字比较的个数的期望值约为(n+1)／4。) 解析：