【考研类试卷】计算机学科专业基础综合数据结构-查找(二)及答案解析.doc

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

1、计算机学科专业基础综合数据结构-查找(二)及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：22，分数：24.00)1.若查找每个记录的概率均等，则在具有 n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度 ASL为_。（分数：1.00）A.(n-1)/2B.n/2C.(n+1)/2Dn顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( 2 )，二分法查找只适用于查找顺序存储的有序表，平均比较次数为( 3 )。在此假定 N为线性表中结点数，且每次查找都是成功的。 A.N+1 B.2log2N C.log2N D.N/2 E.Nlog2N

2、 F.N2（分数：2.00）A.B.C.D.E.F.A.B.C.D.E.F.2.适用于折半查找的表的存储方式及元素排列要求为_。（分数：1.00）A.链接方式存储，元素无序B.链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序3.具有 12个关键字的有序表，折半查找的平均查找长度为_。（分数：1.00）A.3.1B.4C.2.5D.54.折半查找的时间复杂性为_。 A.O(n2) B.O(n) C.O(nlog2n) D.O(log2n)（分数：1.00）A.B.C.D.5.当采用分块查找时，数据的组织方式为_。（分数：1.00）A.数据分成若干块，每块内数据有序B.数

3、据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D.数据分成若干块，每块(除最后一块外)中数据个数需相同6.下面函数的功能是实现分块查找，空白处应该添加的内容是_。 int BlkSearch(int*nz,int key,int block,int BLK,int len) int i; block=block-1; if(len=0) puts(“表为空!“); return 0; if(BLKlen)BLK=len; for(i=block*BLK;i(block+1)*BLKi

4、+) if(_) printf(“找到第%d 个数是%d/n“,i,key); return 0; printf(“/n“); printf(“查找结束/n“); return 0; （分数：1.00）A.nzi=keyB.nzi=BLKC.nz1 i=blockD.nzi=0二叉查找树的查找效率与二叉树的( 9 )有关，在( 10 )时其查找效率最低。（分数：2.00）A.高度B.结点的多少C.树形D.结点的位置A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂7.在一棵高度为 h的理想平衡二叉树中，最少含有_个结点，最多含有_个结点。 A.2h 2h-1 B.2h-1 2h C.2h+1

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

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

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

8、相同，假设采用顺序查找来确定结点所在的块，则每块分为_个结点最佳。（分数：1.00）A.9B.25C.6D.62517.在有 n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为_。 A.O(n) B.O(log2/n) C.O(nlog2n) D.O(n2)（分数：1.00）A.B.C.D.18.对包含 n个关键码的散列表进行检索，平均检索长度为_。（分数：1.00）A.O(log2n)B.O(n)C.O(nlog2n)D.不直接依赖于 n19.在散列表上，每个地址单元所链接的同义词表的_。（分数：1.00）A.键值相同B.元素值相同C.散列地址相同D.含义相同20.设

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

10、将会涉及元素的查找和新元素的插入两种操作，查找和插入时用一个二元组(i，x)来规定一个元素，i 是集合的序号，x 是元素值。设计一种恰当的数据结构来存储这 k个集合的元素，并能高效地实现所要求的查找和插入操作。 (1)构造数据结构，并且说明选择的理由。 (2)若一组数据模型为 S 1 =10.2，1.7，4.8，16.2，S 2 =1.7，8.4，0.5，S 3 =4.8，4.2，3.6，2.7，5.1，3.9，待插入的元素二元组为(2，11.2)和(1，5.3)，按你的设计思想画出插入元素前后的数据结构状态。 （分数：4.00）_23.假设 K 1 ，K n 是 n个关键词，试解答： (1)

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

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

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

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

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

16、个结点的数据元素不满 5个，以值 0充)，试编写一算法查找值为 n(n0)的数据元素所在的结点指针以及在该结点中的序号，若链表中不存在该数据元素则返回空指针。 （分数：4.00）_39.编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，且查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字 （分数：4.00）_计算机学科专业基础综合数据结构-查找(二)答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：22，分数：24.00)1.若查找每个记录的概率均等，则在具有 n个记录的连续顺序文件中采用顺序查

17、找法查找一个记录，其平均查找长度 ASL为_。（分数：1.00）A.(n-1)/2B.n/2C.(n+1)/2 Dn解析：此题考查的知识点是顺序查找长度 ASL的计算。假设表长度为 n，那么查找第 i个数据元素需进行n-i+1次比较，即 C i =n-i+1。又假设查找每个数据元素的概率相等，即 P i =1/n，则顺序查找算法的平均查找长度为： 顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( 2 )，二分法查找只适用于查找顺序存储的有序表，平均比较次数为( 3 )。在此假定 N为线性表中结点数，且每次查找都是成功的。 A.N+1 B.2log2N C.log2N D.N/2

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

19、的表的存储方式及元素排列要求为_。（分数：1.00）A.链接方式存储，元素无序B.链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序 解析：此题考查的知识点是折半查找的特点。折半查找要求顺序存储且元素有序，所以应选 D。3.具有 12个关键字的有序表，折半查找的平均查找长度为_。（分数：1.00）A.3.1 B.4C.2.5D.5解析：此题考查的知识点是折半查找的思想。把关键字按完全二叉树的形式画出查找树，按结点高度计算比较次数。12 个结点可以画出高度为 4的完全二叉树，1 层 1个结点比较 1次，2 层 2个结点比较 2次，3层 4个结点比较 3次，4 层 5个结点

20、比较 4次，37/123.1，应选 A。4.折半查找的时间复杂性为_。 A.O(n2) B.O(n) C.O(nlog2n) D.O(log2n)（分数：1.00）A.B.C.D. 解析：此题考查的知识点是折半查找的效率。其查找效率与比较次数有关，折半查找成功时，关键字比较次数最多不超过log 2 n+1，所以其效率为 O(log 2 n)，应选 D。5.当采用分块查找时，数据的组织方式为_。（分数：1.00）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块 C.数据分成若干块，每块内数据有序，每块内最大(或最小)的

21、数据组成索引块D.数据分成若干块，每块(除最后一块外)中数据个数需相同解析：分块查找是将数据分成若干块，块间有序，块内不必有序。6.下面函数的功能是实现分块查找，空白处应该添加的内容是_。 int BlkSearch(int*nz,int key,int block,int BLK,int len) int i; block=block-1; if(len=0) puts(“表为空!“); return 0; if(BLKlen)BLK=len; for(i=block*BLK;i(block+1)*BLKi+) if(_) printf(“找到第%d 个数是%d/n“,i,key); ret

22、urn 0; printf(“/n“); printf(“查找结束/n“); return 0; （分数：1.00）A.nzi=key B.nzi=BLKC.nz1 i=blockD.nzi=0解析：如果当前的值与所查找关键字相等，则完成查找。二叉查找树的查找效率与二叉树的( 9 )有关，在( 10 )时其查找效率最低。（分数：2.00）A.高度B.结点的多少C.树形 D.结点的位置解析：A.结点太多B.完全二叉树C.呈单枝树 D.结点太复杂解析：二叉查找树的查找效率与树形有关，当结点呈单枝树排列时效率最低。7.在一棵高度为 h的理想平衡二叉树中，最少含有_个结点，最多含有_个结点。 A.2h

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

24、(100，60，80，90，120，110，130) D.(100，80，60，90，120，130，110)解析：分别根据给出的序列构建平衡二叉树，得出 C与其他不同。9.关于 B-树，下列说法中不正确的是_。（分数：1.00）A.B-树是一种查找树B.所有的叶结点具有相同的高度C.2-3树中，所有非叶子结点有 1或者 3个孩子结点 D.通常情况下，B-树不是二叉树解析：B-树定义如下： 一棵 m阶 B-树，或者是空树，或者是满足以下性质的 m叉树： (1)根结点或者是叶子，或者至少有两棵子树，至多有 m棵子树。 (2)除根结点外，所有非终端结点至少有 棵子树，至多有 m棵子树。 (3)所有

25、叶子结点都在树的同一层上。 (4)每个结点应包含如下信息：(n，A 0 ，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是结点中关键字的个数，且 10.在含有 15个结点的平衡二叉树上，查找关键字为 28(存在该结点)的结点，则依次比较的关键字有可能是_。（分数：1.00）A.30，36B.38，48，28C.48，18，38，28 D

26、.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个结点的平衡二叉树的高度为 5，而最小叶子结点的层数为 3，所以选项 D错误。 选项 A在查找 30后，指针应该指向左孩子，而不是右孩子；选项 B与选项 A存在

27、同样的问题，因而选项A、B 错误。而选项 C的查找路径如下图所示： 11.下面关于 m阶 B树的说法中，正确的是_。 每个结点至少有两棵非空子树。 树中每个结点至多有 m-1个关键字。 所有叶子在同一层上。 当插入一个数据项引起 B树结点分裂后，树长高一层。（分数：1.00）A.B.C.D. 解析：根据 B树定义可知只有正确。12.下面关于 B和 B+树的叙述中，不正确的是_。（分数：1.00）A.B树和 B+树都是平衡的多叉树B.B树和 B+树都可用于文件的索引结构C.B树和 B+树都能有效地支持顺序检索 D.B树和 B+树都能有效地支持随机检索解析：此题考查的知识点是 B-树和 B+树的定

28、义。 B-树定义如下： 一棵 m阶 B-树，或者是空树，或者是满足以下性质的 m叉树： (1)根结点或者是叶子，或者至少有两棵子树，至多有 m棵子树。 (2)除根结点外，所有非终端结点至少有 棵子树，至多有 m棵子树。 (3)所有叶子结点都在树的同一层上。 (4)每个结点应包含如下信息：(n，A 0 ，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

29、 i 。 n是结点中关键字的个数，且 13.m阶 B-树是一棵_。（分数：1.00）A.m叉排序树B.m叉平衡排序树 C.m-1叉平衡排序树D.m+1叉平衡排序树解析：此题考查的知识点是 m阶 B-树的定义。B-树是一种平衡的多路排序树，m 阶即 m叉。应选 B。14.若对有 18个元素的有序表做二分查找，则查找 A3的比较序列的下标为_。（分数：1.00）A.1，2，3B.9，4，2，3C.10，5，3D.9，2，3 解析：二分查找判定树如下图所示，查找 A3的比较序列的下标为 9，4，2，3，本题选 D。 15.有一个有序表1，3，9，12，32，41，45，62，75，77，82，95，

30、100，当用二分查找法查找值为 82的结点时，经_次比较后查找成功。（分数：1.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次。16.采用分块查找时，若线性表中共有 625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，则每块分为_个结点最佳。（分数：1.00）A.9B.25 C.6D.625解析：分块查找时最佳块数为17.在有 n个结点且为完全二

31、叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为_。 A.O(n) B.O(log2/n) C.O(nlog2n) D.O(n2)（分数：1.00）A.B. C.D.解析：有 n个结点且为完全二叉树的二叉排序树的高度为 log 2 n。18.对包含 n个关键码的散列表进行检索，平均检索长度为_。（分数：1.00）A.O(log2n)B.O(n)C.O(nlog2n)D.不直接依赖于 n 解析：对散列表进行检索，平均检索长度仅与装填因子 有关，而与关键字个数 n无关。19.在散列表上，每个地址单元所链接的同义词表的_。（分数：1.00）A.键值相同B.元素值相同C.散列地址相同 D.含义

32、相同解析：由同义词的定义可知本题答案为 C。20.设哈希表长 m=14，哈希函数 H(key)=key mod 11。表中已有 4个结点 addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空，如用二次探测再散列法处理冲突，则关键字为 49的结点的地址是_。（分数：1.00）A.8B.3C.5D.9 解析：addr(49)=49 mod 11=5，冲突；h1=(5+1*1)mod 11=6，仍冲突；h2=(5+2*2)mod 11=9，所以本题答案为 D。二、综合应用题(总题数：19，分数：76.00)21.请编写一个判别给定二叉树是否为二叉排序树

33、的算法，设二叉树用 llink-rlink法存储。 （分数：4.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(BTtee t, int flag)

34、/判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由 flag得出结论 if(t!=null /中序遍历左子树 if(pre=null) pre=t; /中序遍历的第一个结点不必判断 else if(pre-datat-data) pre=t; /前驱指针指向当前结点 else flag=false; /不是二叉排序树 JudgeBST(t-rlink, flag); /中序遍历右子树 本题的另一算法是依照定义，二叉排序树的左右子树都是二叉排序树，根结点的值大于左子树中所有值而小于右子树中所有值，即根结点大于左子树的最大值而小于右子树的最小值。算法如下： int JudgeBST(BTr

35、ee t) /判断二叉树 t是否是二叉排序树，若是，返回 true，否则，返回 false if(t=null) return true; if(JudgeBST(t-llink) n=min(t-rlink); /左子树中最大值和右子树中最小值 return(t-datam 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

36、p) /求二叉树右子树的最小值 if(p=null) return maxint; /返回机器最大整数 else while(p-llink !=null) p=p-rlink; return p-data; 22.某个任务的数据模型可以抽象为给定的 k个集合：S 1 ，S 2 ，S k 。其中 S i (1ik 中的元素个数不定。在处理数据过程中将会涉及元素的查找和新元素的插入两种操作，查找和插入时用一个二元组(i，x)来规定一个元素，i 是集合的序号，x 是元素值。设计一种恰当的数据结构来存储这 k个集合的元素，并能高效地实现所要求的查找和插入操作。 (1)构造数据结构，并且说明选择的理由

37、。 (2)若一组数据模型为 S 1 =10.2，1.7，4.8，16.2，S 2 =1.7，8.4，0.5，S 3 =4.8，4.2，3.6，2.7，5.1，3.9，待插入的元素二元组为(2，11.2)和(1，5.3)，按你的设计思想画出插入元素前后的数据结构状态。 （分数：4.00）_正确答案：()解析：借助于分块查找思想，在建立数据顺序表的同时，建立一索引表。数据表中按 k个集合分块(元素个数不一定相等)，索引表中有两个域，一是各集合最后一个元素在数据表中的位置(一维数组中的下标)，二是集合的个数(k)。实现数据运算时，根据给定的二元组(i，x)，首先在索引表中找到集合 i的位置，然后在数

38、据表中查找 x。查到 x，则查找成功，返回 x在数据表中的位置，否则查找失败。若要插入，则将数据表中的数据后移，插入 x，同时修改索引表。 typedef struct datatype data; rectype; typedef struct int a; /a数组容量够大，存储各集合最后一个数 据在数据表中的下标 int k; /集合个数 index; int SetSearch_Insert(rectype R, index id, datatype x, int i) /数据表 R，查找第 i个集合的元素 x，若查找成功，返回其位置， /否则将其插入第 i个集合 if(i1|iid.

39、k)printf(“无第%d 个集合/n“,i); exit(0); if(i=1) first=0； /first 指向第 i个集合在数据表的首址 else first=id.ai-1+1; last=id.ai； /last 是第 i个集合在数据表中的末址 for(j=first; jlast; j+) if(Rj=x) return(j); /查找成功 for(j=id.aid.k; jid.Ai; j-) /查找失败，将 x插入数据表 Rj+1; Rj; /元素后移 Rj+1=x; /将 x插入到原第 i个集合最后一个元素之后 for(j=i; jk; j+)id.aj+; /修改索引

40、表中各集合最后一个元素的下标 由于各集合元素个数不等，各块长度不等且块间无序，索引表中用数组表示，数组中元素值是各集合最后一个元素在数据表中的下标。按本算法插入(2，11.2)和(1，5.3)，数据表前后状态如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 插入前 10.2 1.7 4.8 16.2 1.7 8.4 0.5 4.8 4.2 3.6 2.7 5.1 3.9 插入后 10.2 1.7 4.8 16.2 5.3 1.7 8.4 0.5 11.2 4.8 4.2 3.6 2.7 5.1 3.9 插入前，索引表中 a数组的内容是 3，6，12，插入后修改为 4

41、，8，14。23.假设 K 1 ，K n 是 n个关键词，试解答： (1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为 K 1 ，K 2 ，K n 时，用算法建立一棵以 LLINK-RLINK链接表示的二叉查找树。 (2)设计一个算法，打印出该二叉查找树的嵌套括号表示结构。假定该二叉查找树的嵌套括号表示结构为B(A，D(C，E)。 （分数：4.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; /在调用 Create_