1、计算机学科专业基础综合数据结构-9 及答案解析(总分：97.50，做题时间：90 分钟)一、综合应用题(总题数：24，分数：97.50)假定把关键字 key散列到有 n个表项(从 0到 n-1编址)的散列表中。对于下面的每一个函数 H(key)(keyr为整数)，这些函数能够当作散列函数吗?(即对于插入和查找，散列程序能正常工作吗?)如果能够，它是一个好的散列函数吗?请说明理由。设函数 random(n)返回一个 0到 n-1之间的随机整数(包括 0与 n-1在内)。（分数：10.00）(1).H(key)=key/n（分数：2.50）_(2).H(key)=1（分数：2.50）_(3).H(
2、key)=(Key+random(n)%n（分数：2.50）_(4).H(key)=key%p(n)；其中 p(n)是不大于 n的最大素数（分数：2.50）_对于一个长度为 m=41的散列表，采用双散列法解决冲突，对于关键字 k 1 ，k 2 ，k 3 ，若 h(k 1 )=30，h(k 2 )=28，h(k 3 )=19，h 2 (k 1 )=14，h 2 (k 2 )=27，h 2 (k 3 )=35，则 k 1 ，k 2 ，k 3 的探测序列中前 4个位置各为多少。（分数：7.50）(1).k 1 的探测序列： 30 ，_，_，_；（分数：2.50）_(2).k 2 的探测序列： 28
3、，_，_，_；（分数：2.50）_(3).k 3 的探测序列：_，_，_，_；（分数：2.50）_1.设有 150个记录要存储到散列表中，要求利用双散列法解决冲突，同时要求找到新记录插入位置的平均比较次数不超过 2次。试问散列表需要设计为多大?请为这个散列表设计散列函数(除留余数法)和再散列函数。 设 是散列表的装载因子，则应用双散列法解决冲突时的查找成功的平均查找长度和查找不成功的平均查找长度分别为 （分数：2.50）_若对有 n个元素的有序顺序表和无序顺序表进行顺序查找，试就下列三种情况分别讨论两者在相等查找概率时的平均查找长度是否相同?（分数：7.50）(1).查找失败。（分数：2.50
4、）_(2).查找成功，且表中只有一个关键字等于给定值 k的元素。（分数：2.50）_(3).查找成功，且表中有若干个关键字等于给定值 k的元素，要求一次查找能找出所有元素。（分数：2.50）_2.设有序顺序表中的元素依次为017，094，154，170，275，503，509，512，553，612，677，765，897，908。试画出对其进行折半查找时的判定树，并计算查找成功的平均查找长度和查找不成功的平均查找长度。 （分数：2.50）_已知一个有序顺序表 ABN-1的表长为 8N，并且表中没有关键字相同的数据元素。假设按如下所述的方法查找一个关键字值等于给定值 X的数据元素：先在 A7，
5、A15，A23，A8K-1，A8N-1中进行顺序查找，若查找成功，则算法报告成功位置并返回；若不成功，当 A8K-1XA8(K+1)-1时，若 XA8N-1的关键字，则查找失败。（分数：5.00）(1).画出描述上述查找过程的判定树。（分数：2.50）_(2).计算相等查找概率下查找成功的平均查找长度。（分数：2.50）_3.设有一棵 B+树，其结点最多可存放 100个索引项。对于高度为 1、2、3、4 的 B+树，最多能存储多少索引项?最少能存储多少索引项? （分数：2.50）_4.设敞列表为 HT13，散列函数为 H(key)=key%13。用开地址法解决冲突，对下列关键字序列12，23，
6、45，57，20，03，78，3l，15，36 造表。采用线性探测法寻址下一个空位，画出相应的散列表，并计算等概率下查找成功的平均查找长度和查找不成功的平均查找长度。 （分数：2.50）_设有一个散列表，要存放的数据有 8个，采用除留余数法计算散列地址，并用二次散列法解决冲突，不过仅用 H i =(H o +i 2 )%m计算下一个散列地址，m 是表的长度，i=1，2，m-1。（分数：5.00）(1).如果要求平均探测两次就能找到新表项的散列地址，确定表长度 m和散列函数。(设 是装填因子)（分数：2.50）_(2).设存放的数据为25，40，11，97，59，30，87，73，依次计算并存放
7、这些数据到散列表中，并计算存放后表的查找成功的平均查找长度。（分数：2.50）_设散列表为 HT0.12即表的大小为 m=13。现采用链地址法解决冲突。若插入的关键字序列为2，8，31，20，19，18，53，27。（分数：5.00）(1).画出插入这 8个关键字后的散列表。（分数：2.50）_(2).计算查找成功的平均查找长度和查找不成功的平均查找长度。（分数：2.50）_如果有一个时间复杂性为 O(n 2 )的算法(如冒泡排序、选择排序或插入排序等)，在有 200个元素的数组上运行需要时 3.1毫秒，试问在下列类似的数组上运行大约需要多长时间?（分数：5.00）(1).具有 400个元素。
8、（分数：2.50）_(2).具有 40000个元素。（分数：2.50）_5.希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法，试举例说明。 （分数：2.50）_6.在冒泡排序过程中，什么情况下排序码会朝与排序相反的方向移动?试举例说明。在快速排序过程中有这种现象吗? （分数：2.50）_7.如果只想在一个有 n个元素的任意序列中得到其中最小的第 k(kn)个元素之前的部分排序序列，那么最好采用什么排序方法?为什么?例如有这样一个序列57，40，38，11，13，34，48，75，6，19，9，7，要得到其第 4个元素之前的部分有序序列6，7，9，11，用所选择的算法实现时，要执行多少
9、次比较? （分数：2.50）_8.多路平衡归并排序是外排序的主要方法，试问多路平衡归并排序包括哪两个相对独立的阶段?每个阶段完成何种工作? （分数：2.50）_如果某个文件经内排序得到 80个初始归并段，试问：（分数：5.00）(1).若使用多路平衡归并执行 3趟完成排序，那么应取的归并路数至少应为多少?（分数：2.50）_(2).如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过 15个，则按多路归并至少需要几趟可用完成排序?如果限定趟数，可取的最低路数是多少?（分数：2.50）_假设文件有 4500个记录，在磁盘上每个块可放 75个记录。计算机中用于排序的内存区可容纳 450个记
10、录。试问：（分数：5.00）(1).可以建立多少个初始归并段?每个初始归并段有多少记录?存放于多少个块中?（分数：2.50）_(2).应采用几路归并?请写出归并过程及每趟需要读写磁盘的块数。（分数：2.50）_9.磁盘文件采用选择法实现 m路归并时，占用 CPU的时间与 m是否相关?为什么? （分数：2.50）_10.败者树中的“败者”指的是什么?若利用败者树求 m个排序码中的最大者，在某次比较中得到 ab，那么谁是败者? （分数：2.50）_11.设有一个排序码输入序列10，40，30，50，20，25，45，60，试根据败者树的构造算法构造一棵败者树。 （分数：2.50）_12.设输入文件
11、保存以下记录：14，22，7，24，15，16，11，100，10，9，20，12，90，17。现采用置换-选择方法生产初始归并段，并假设内存工作区可同时容纳 5个记录，请画出选择的过程。 （分数：2.50）_13.试为下列每种情况选择合适的排序方法： (1)n=30，要求最坏情况下速度最快。 (2)n=30，要求既要快，又要排序稳定。 (3)n=1000，要求平均情况下速度最快。 (4)n=1000，要求最坏情况下速度最快且稳定。 (5)n=1000，要求既快又最省内存。 （分数：2.50）_下面给出一个排序算法，数组 a是存放待排序数据元素的数组，n 是数组大小，数据元素的数据类型是Dat
12、aType。 void unknow(DataType a,int n) int high=n-1,i,j;DataType w; while(high0) j=0; for(i=0;ihigh;i+) if(aiai+1) w=ai;ai=ai+1;ai+1=w; j=i; high=j; （分数：7.50）(1).该算法的功能是什么?（分数：2.50）_(2).若待排序数据序列为10，20，30，40，50，60，画出每次执行的结果序列。（分数：2.50）_(3).若待排序数据序列为60，50，40，30，20，10，画出每次执行的结果序列。（分数：2.50）_14.在已排好序的序列中，一
13、个元素所处的位置取决于具有更小排序码的元素的个数。基于这个思想，可得计数排序方法。假设待排序元素放在数组 an中，n 是待排序元素个数。该方法建立一个计数数组countn，用 counti记下在已排好序的序列中 ai前面的元素个数，最后依 count的值，将序列在an中重新排列，就可完成排序。编写一个算法，实现计数排序，并说明对于一个有 a个元素的序列，为确定所有元素的 count值，最多需要做 n(n-1)/2次排序码比较。 （分数：2.50）_计算机学科专业基础综合数据结构-9 答案解析(总分：97.50，做题时间：90 分钟)一、综合应用题(总题数：24，分数：97.50)假定把关键字
14、key散列到有 n个表项(从 0到 n-1编址)的散列表中。对于下面的每一个函数 H(key)(keyr为整数)，这些函数能够当作散列函数吗?(即对于插入和查找，散列程序能正常工作吗?)如果能够，它是一个好的散列函数吗?请说明理由。设函数 random(n)返回一个 0到 n-1之间的随机整数(包括 0与 n-1在内)。（分数：10.00）(1).H(key)=key/n（分数：2.50）_正确答案：()解析：不能当作散列函数，因为 key/n可能大于 n，这样就找不到适合的位置。(2).H(key)=1（分数：2.50）_正确答案：()解析：能够作为散列函数，但不是一个好的散列函数，因为所有
15、关键字都映射到同一位置，造成大量的冲突机会。(3).H(key)=(Key+random(n)%n（分数：2.50）_正确答案：()解析：不能当作散列函数，因为该函数的返回值不确定，这样无法进行正常的查找。(4).H(key)=key%p(n)；其中 p(n)是不大于 n的最大素数（分数：2.50）_正确答案：()解析：能够作为散列函数，是一个好的散列函数。对于一个长度为 m=41的散列表，采用双散列法解决冲突，对于关键字 k 1 ，k 2 ，k 3 ，若 h(k 1 )=30，h(k 2 )=28，h(k 3 )=19，h 2 (k 1 )=14，h 2 (k 2 )=27，h 2 (k 3
16、 )=35，则 k 1 ，k 2 ，k 3 的探测序列中前 4个位置各为多少。（分数：7.50）(1).k 1 的探测序列： 30 ，_，_，_；（分数：2.50）_正确答案：()解析：在双散列法中，求初始散列地址的散列函数为 h(x)，求下一个空位的增量函数为 h 2 (x)，一旦发生冲突，求下一个空位的公式为： H i =(h(x)+ih 2 (x)%m，i=1，2，m-1 据此可得： k 1 的探测序列： 30 ， 3 ， 17 ， 31 ；(2).k 2 的探测序列： 28 ，_，_，_；（分数：2.50）_正确答案：()解析：k 2 的探测序列： 28 ， 14 ， 0 ， 22 ；
17、(3).k 3 的探测序列：_，_，_，_；（分数：2.50）_正确答案：()解析：k 3 的探测序列： 19 ， 13 ， 7 ， 1 。1.设有 150个记录要存储到散列表中，要求利用双散列法解决冲突，同时要求找到新记录插入位置的平均比较次数不超过 2次。试问散列表需要设计为多大?请为这个散列表设计散列函数(除留余数法)和再散列函数。 设 是散列表的装载因子，则应用双散列法解决冲突时的查找成功的平均查找长度和查找不成功的平均查找长度分别为 （分数：2.50）_正确答案：()解析：已知要存储的记录数为 n=150，找到新记录的插入位置的平均比较次数即查找不成功的平均查找长度为 AS L不成功
18、 2，则有 ，解得 。又有 若对有 n个元素的有序顺序表和无序顺序表进行顺序查找，试就下列三种情况分别讨论两者在相等查找概率时的平均查找长度是否相同?（分数：7.50）(1).查找失败。（分数：2.50）_正确答案：()解析：若对有 n个元素的有序顺序表和无序顺序表进行顺序查找，查找失败的平均查找长度不同。因为有序顺序表查找到其关键字值比要查找值大的元素时就停止查找，报告失败信息，不必查找到表尾；而无序顺序表必须查找到表尾才能断定查找失败。(2).查找成功，且表中只有一个关键字等于给定值 k的元素。（分数：2.50）_正确答案：()解析：若对有 n个元素的有序顺序表和无序顺序表进行顺序查找，查
19、找成功，且表中只有一个关键字等于给定值 k的元素时的平均查找长度相同。查找到表中元素的关键字值等于给定值时就停止查找，报告成功信息。(3).查找成功，且表中有若干个关键字等于给定值 k的元素，要求一次查找能找出所有元素。（分数：2.50）_正确答案：()解析：若对有 n个元素的有序顺序表和无序顺序表进行顺序查找，查找成功，且表中有若干个关键字等于给定值 k的元素要求一次查找能找出所有元素时的平均查找长度不同。有序顺序表中关键字相等的元素相继排列在一起，只要查找到第一个就可以连续查找到其他关键字相同的元素。而无序顺序表必须查找全部表中元素才能确定相同关键字的元素都找了出来，所需时间就不相同了。2
20、.设有序顺序表中的元素依次为017，094，154，170，275，503，509，512，553，612，677，765，897，908。试画出对其进行折半查找时的判定树，并计算查找成功的平均查找长度和查找不成功的平均查找长度。 （分数：2.50）_正确答案：()解析：判定树如下图所示： 计算 已知一个有序顺序表 ABN-1的表长为 8N，并且表中没有关键字相同的数据元素。假设按如下所述的方法查找一个关键字值等于给定值 X的数据元素：先在 A7，A15，A23，A8K-1，A8N-1中进行顺序查找，若查找成功，则算法报告成功位置并返回；若不成功，当 A8K-1XA8(K+1)-1时，若 XA
21、8N-1的关键字，则查找失败。（分数：5.00）(1).画出描述上述查找过程的判定树。（分数：2.50）_正确答案：()解析：相应的判定树如下图所示。其中，每一个关键字下的数字为其查找成功时的关键字比较次数。 (2).计算相等查找概率下查找成功的平均查找长度。（分数：2.50）_正确答案：()解析：查找成功的平均查找长度为： 3.设有一棵 B+树，其结点最多可存放 100个索引项。对于高度为 1、2、3、4 的 B+树，最多能存储多少索引项?最少能存储多少索引项? （分数：2.50）_正确答案：()解析：能存储多少索引项，主要看叶结点。非叶结点是对下层最多关键字的复写。 对于高度为 1的 B+
22、树：根据 B+树定义，根结点又是叶结点，最多可存储 m=100个索引项，最少可存放 1个索引项。 对于高度为 2的 B+树：最多可存储 mm=100 2 个索引项，最少可存储 101个索引项。因为当根结点关键字个数 n达到 101，发生结点分裂，其高度才会变为 2。 对于高度为 3的 B+树：最多可存储 mmm=100 3 个索引项，最少可存储 2101=202个索引项。因为当第 1层的关键字个数达到 101做结点分裂，叶结点才会落到第 2层，第 2层 2个结点，每个结点的关键字个数达到 101引发结点分裂，叶结点落到第 3层。此时，叶结点有 51+50+51+50=202个索引项。 对于高度
23、为 4的 B+树：第 4层是叶结点。最多可存储 m 4 =100 4 个索引项，最少可存储 4101=404个索引项。叶结点有 51+50+51+50+51+50+51+50=404个索引项。4.设敞列表为 HT13，散列函数为 H(key)=key%13。用开地址法解决冲突，对下列关键字序列12，23，45，57，20，03，78，3l，15，36 造表。采用线性探测法寻址下一个空位，画出相应的散列表，并计算等概率下查找成功的平均查找长度和查找不成功的平均查找长度。 （分数：2.50）_正确答案：()解析：使用散列函数 H(key)=key%13，有： H(12)=12，H(23)=10，H
24、(45)=6，H(57)=5，H(20)=7， H(03)=3，H(78)=0，H(31)=5，H(15)=2，H(36)=10。 利用线性探测法造表，如下图所示： 查找成功的平均查找长度为： 查找不成功的平均查找长度为： 设有一个散列表，要存放的数据有 8个，采用除留余数法计算散列地址，并用二次散列法解决冲突，不过仅用 H i =(H o +i 2 )%m计算下一个散列地址，m 是表的长度，i=1，2，m-1。（分数：5.00）(1).如果要求平均探测两次就能找到新表项的散列地址，确定表长度 m和散列函数。(设 是装填因子)（分数：2.50）_正确答案：()解析：选用 U n ，有 ， 又根
25、据题意，n=8，有 (2).设存放的数据为25，40，11，97，59，30，87，73，依次计算并存放这些数据到散列表中，并计算存放后表的查找成功的平均查找长度。（分数：2.50）_正确答案：()解析：依次计算并存储的数据为25，40，11，97，59，30，87，73 Hash(25)=25%19=6；Hash(40)=40%19=2；Hash(11)=11%19=11； Hash(97)=97%19=2，冲突，(2+1 2 )%19=3； Hash(59)=59%19=2，冲突，(2+1 2 )%19=3，冲突，(2+2 2 )%19=6，冲突， (2+3 2 )%19=11，冲突，(2
26、+4 2 )%19=18； Hash(30)=30%19=11，冲突，(11+1 2 )%19=12； Hash(87)=87%19=11，冲突，(11+1 2 )%19=12，冲突，(11+2 2 )%19=15； Hash(73)=73%19=16。 括号内是探测次数，如下图所示。由此计算查找成功的平均查找长度： 设散列表为 HT0.12即表的大小为 m=13。现采用链地址法解决冲突。若插入的关键字序列为2，8，31，20，19，18，53，27。（分数：5.00）(1).画出插入这 8个关键字后的散列表。（分数：2.50）_正确答案：()解析：散列表 HT012，散列函数为 Hash(k
27、ey)=key%13；插入关键字序列为2，8，31，20，19，18，53，27，计算各关键字的散列地址如下： Hash(2)=2%13=2，Hash(8)=8%13=8，Hash(31)=31%13=5。 Hash(20)=20%13=7，Hash(19)=19%13=6，Hash(18)=18%13=5， Hash(53)=53%13=1，Hash(27)=27%13=1， 插入 8个关键字后的散列表，如下图所示： (2).计算查找成功的平均查找长度和查找不成功的平均查找长度。（分数：2.50）_正确答案：()解析：查找成功的平均查找长度为： 查找不成功的平均查找长度为： 如果有一个时间复
28、杂性为 O(n 2 )的算法(如冒泡排序、选择排序或插入排序等)，在有 200个元素的数组上运行需要时 3.1毫秒，试问在下列类似的数组上运行大约需要多长时间?（分数：5.00）(1).具有 400个元素。（分数：2.50）_正确答案：()解析：当 n=200时，T(200)=O(200 2 )=3.1毫秒；当 n=400时，T(400)=O(400 2 )=4O(200 2 )=43.1=12.4毫秒。(2).具有 40000个元素。（分数：2.50）_正确答案：()解析：T(40000)=O(40000 2 )=200 2 O(200 2 )=400003.1=124000毫秒=124 秒
29、。5.希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法，试举例说明。 （分数：2.50）_正确答案：()解析：以下例子中的 275和 275 * 是排序码相等的不同数据元素，为区分起见，在后一个 275上加 * ，以示区别。如果排序后 275 * 跑到 275前面，表示此排序方法不稳定。 (1) (2) 061 275 * 275 512结果 (3) (4) 6.在冒泡排序过程中，什么情况下排序码会朝与排序相反的方向移动?试举例说明。在快速排序过程中有这种现象吗? （分数：2.50）_正确答案：()解析：如果在待排序序列的后面的若干排序码比前面的排序码小，则在冒泡排序的过程中，排序码
30、可能向与最终它应移向的位置相反的方向移动。如下图所示。 7.如果只想在一个有 n个元素的任意序列中得到其中最小的第 k(kn)个元素之前的部分排序序列，那么最好采用什么排序方法?为什么?例如有这样一个序列57，40，38，11，13，34，48，75，6，19，9，7，要得到其第 4个元素之前的部分有序序列6，7，9，11，用所选择的算法实现时，要执行多少次比较? （分数：2.50）_正确答案：()解析：一般来讲，当 n比较大且要选的数据 k远小于 n时，采用堆排序方法中的筛选算法 siftDown()最好。 例如，对于序列57，40，38，11，13，34，48，75，6，19，9，7，选最小数据 6，需形成初始堆，进行 23+22+22+21+1=19次数据
