1、计算机专业基础综合（数据结构）模拟试卷 6及答案解析(总分：88.00，做题时间：90 分钟)一、单项选择题(总题数：23，分数：48.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。_2.若查找每个记录的概率均等，则在具有 n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度 ASL为( )。（分数：2.00）A.(n1)2B.n2C.(n+1)2D.n顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( (1) )，二分法查找只适用于查找顺序存储的有序表，平均比较次数为( (2) )。在此假定 N为线性表中结点数，且每
2、次查找都是成功的。（分数：4.00）(1).(1)（分数：2.00）A.N+1B.2log 2 NC.log 2 ND.N2(2).(2)（分数：2.00）A.N+1B.2log 2 NC.log 2 ND.N23.适用于折半查找的表的存储方式及元素排列要求为( )。（分数：2.00）A.链接方式存储，元素无序B.链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序4.具有 12个关键字的有序表，折半查找的平均查找长度为( )。（分数：2.00）A.31B.4C.25D.55.折半查找的时间复杂性为( )。（分数：2.00）A.O(n 2 )B.O(n)C.O(nlog
3、2 n)D.O(log 2 n)6.当采用分块查找时，数据的组织方式为( )。（分数：2.00）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D.数据分成若干块，每块(除最后一块外)中数据个数需相同7.下面函数的功能是实现分块查找，空白处应该添加的内容是( )。 int BlkSearch(int*nz，int key，int block，int BLK，int len) int i； block=block1： if(lenlen)BLK=l
4、en； for(i=block*BLK；ilen)BLK=len； for(i=block*BLK；i(block+1)*BLK 否则将其插入第 i个集合 if(i1 | 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；j idAi；j-)t 查找失败，将 x插入数据表 Rj+1=Rj； 元素后移 Rj+1=x； 将 x插入到原第 i个集合最后一个元素之后 for(j=i
5、;jk；j+)idaj+； 修改索引表中各集合最后一个元素的下标 由于各集合元素个数不等，各块长度不等且块间无序，索引表中用数组表示，数组中元素值是各集合最后一个元素在数据表中的下标。按本算法插入(2，112)和(1，53)，数据表前后状态如下： * 插入前，索引表中 a数组的内容是 3，6，12，插入后修改为 4，8，14。)解析：25.假设 K 1 ,，K n 是 n个关键词，试解答： (1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为 K 1 ，K 2 ，K n 时，用算法建立一棵以 LLINKRLINK链接表示的二叉查找树。 (2)设计一个算法，打印出该二叉查找树
6、的嵌套括号表示结构。假定该二叉查找树的嵌套括号表示结构为 B(A，D(C，E)。（分数：2.00）_正确答案：(正确答案：(1)非递归建立二叉排序树，在二叉排序树上插入的结点都是叶子结点。 typedef struct node Elemtype data； struct node*LLINK，*RLINK； node*BiTree： void Create_BST(BiTree bst，datatype K，int n) 以存储在数组 K中的 n个关键字，建立一棵初始为空的二又排序树 int i： BiTree P，f： for(i=1；i=n；i+) p=bst：f=null； 在调用Cr
7、eate_BST时，bst=null while(P!=null) if(P-dataKi)f=P；P=p 一RLINK； f 是 P的双亲 else if(p 一dataKi)f=P；P=p 一LLINK； S=(BiTree)malloc(sizeof(BiNode)；申请结点空间 s-data=Ki; s-LLINK=null ; s 一RLINK=null； if(f=null)bst：S； 根结点 else if(S-dataf-data)f-LLINK=S； 左子女 else f 一RLINK=s： 右子树根结点的值大于等于根结点的值 (2)本题要求输出遍历二叉排序树的嵌套括号表示
8、。其算法思想是，若二叉排序树非空，则输出根结点，再输出其左右子树。在输出其左右子树前，要输出左括号，在输出其右子树前要输出逗号，在输出其右子树后要输出右括号，在左右子树均空情况下，则不输出括号。 void Print(BiTree t) 以嵌套括号表示结构打印二叉排序树 if(t!=null) printf(t 一data)； 打印根结点值 if(t 一LLINK |t 一LLINK)； 左子女和右子女中至少有一个不空 printf(”(”)；输出左括号 Print(t 一LLINK)i 输出左子树的嵌套括号表示 if(t 一RLINK)printf(”，”)；若右子树不空，输出逗号 Prin
9、t(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
10、=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)； elsep 一data=q 一data；s 一rchild=q 一lchild；free(q)； )解析：27.已知二叉树排序树中某结点指针 p，其双亲结点指针为 fp，p 为 fp的左孩子。试编写算法，删除 p所指结点。（分数：2.00）_正确答案：(正确答案：本题用被删结点右子树中最小值(中序遍历第一个)结点代替被删结点。 w)id Del
11、ete(BSTree bst，P，fp) 在二叉排序树 bst上，删除 fp所指结点的左子女(由 P所指向) if(!p一lchild)fp 一lchild=p 一rchild；free(P)； p 无左子女 else if(!p 一rchild)fp 一lchild=p 一lehild；flee(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
12、 一data；p 一rchild=s 一rchild；frees)； elsep 一data=q 一data；s 一lchild=q 一rchild；free(q)； )解析：28.二叉排序树采用二叉链表存储。写一个算法，删除结点值是 X的结点。要求删除该结点后，此树仍然是一棵二叉排序树，并且高度没有增长(注意：可不考虑被删除的结点是根的情况)。（分数：2.00）_正确答案：(正确答案：在二叉排序树上删除结点，首先要查找该结点。查找成功后，若该结点无左子树，则可直接将其右子树的根结点接到其双亲结点上；若该结点有左子树，则将其左子树中按中序遍历的最后一个结点代替该结点，从而不增加树的高度。 vo
13、id Delete(BSTree bst，keytype X) 在二叉排序树 bst上，删除其关键字为 X的结点 BSTree f，p=bst： while(P将被删结点的右子树接到其双亲上 else f 一rchild=p一rehild； elseq=P；s=p 一lehild； 被删结点有左子树 while(S-rehild!=null) 查左子树中最右下的结点(中序最后结点) q=s；s=s 一rehild; P 一key=s 一key； 结点值用其左子树最右下的结点的值代替 if(q=P)P 一lchild=s 一lchild； 被删结点左子树的根结点无右子女 else q 一rchi
14、ld=s 一lchild； s 是被删结点左子树中序序列最后一个结点 free(s)； )解析：29.设记录 R 1 ，R 2 ，R n 按关键字值从小到大顺序存储在数组 r1n中，在 rn+1处设立一个监督哨，其关键字值为+。试写一查找给定关键字 k的算法，并画出此查找过程的判定树，求出在等概率情况下查找成功时的平均查找长度。（分数：2.00）_正确答案：(正确答案：intSeareh(reetype r，int n，keytype k) 在 n个关键字从小到大排列的顺序表中，查找关键字为 k的结点 rn+1key=MAXINTi 在高端设置监视哨 int i=1： while(rikeyk
15、)i+； if(rn+1key=k)return(i(n+1)； else return(0)； 查找过程的判定树是单枝树。本题中虽然表按关键字有序，但进行顺序查找，查找成功的平均查找长度亦为(n+1)2。)解析：30.给出折半查找的递归算法，并给出算法时间复杂度分析。（分数：2.00）_正确答案：(正确答案：int BinSreh(reetype r，int k，low，high) 在长为 n的有序表中查找关键字 k，若查找成功，返回 k所在位置，查找失败返回 0 if(low=high)f low 和 high分别是有序表的下界和上界 mid=(low+high)2： if(rmidkey
16、=k)return(mid)； else if(rmidkeyk)return(BinSreh(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）_
17、正确答案：(正确答案：在 Trie树上查找给定值 KEY的过程如下：沿和给定值相应的指针向下，直至叶子结点，若叶子中的关键字和 KEY相等，则查找成功;若分支结点中和给定值相应的指针为空，或叶子结点中的关键字和给定值不等，则查找不成功。 typedef enulTlLEAF，BRANCHNodeKind； 结点种类叶子，分支 typedef struet TrieNode NodeKind kind； unionstruetKeyType K；Record*infoptrlf； 叶子结点 structTrieNode*ptr27；int numbh； 分支结点 ； TrieNode，*Trie
18、Tree； 键树类型 Record*SearchTrie(TrieTree T，KeyType KEY) 在 Trie树 T中查找关键字等于 K的记录 for(P=T，i：0； 对 KEY的每个字符逐个查找 P P=T 一left； while(Pp=p 一left； q 记 P的双亲 if(P) p 结点的值小于等于 X q一left=P 一right；p 一right=null；DelTree(P)； P=q一left； 再查原 P的右子树中小于等于 X的结点 )解析：36.已知二又树 T的结点形式为(Uink，data，count，rlink)，在树中查找值为 X的结点，若找到，则记数(
19、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 每个结点内含有 m个正整数，本例中 m为 5
20、 struet node*next； 指向下一结点的指针 LNode，*LinkList； typedef struet int j； 正整数在结点内的序号 struet node*s； 结点的指针 rcd； rcd*LSearch(LinkList head，int n) 在链表中查找正整数 n，若查找成功，返回该结点指针及 n在结点中的序号， 否则返回空指针表示失败。 rcd*R： P=head一next； 假定链表带头结点，P 指向链表第一元素结点 int found=0： Int 1； while(P&!found) for(i=0；im；i+) if(P 一Ai=n)found=1
21、查找成功 P=P 一next： 下一结点 if(P=null)return(null)； elseRj=i；Rs=P；return(R)； )解析：41.编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，且查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。（分数：2.00）_正确答案：(正确答案：int Search(rectype R，int n，K) 在具有 n个元素的有序表 R中，顺序查找值为 K的结点，查找成功返回其位置， 否则返回一 1表示失败 int i=0： while(in) if(Ri=K)return(i)； else if(RiK)return(一 1)i i+： while return 一 1； 在等概率的情况下，则查找成功的平均查找长度为(n+1)2，查找失败的平均查找长度为(n+2)2(失败位置除小于第一个，还存在大于最后一个)。若查找成功和不成功的概率也相等，则查找成功时和关键字比较的个数的期望值约为(n+1)4。)解析：
