华文慕课数据结构与算法(下)期末考试答案

1、( 1分 )有一组待排序的记录，其排序码为{18，5，20，30，9，27，6，14，45，22}，而采用直接选择排序的比较次数是

There is an array of records to be sorted, the sort key is {18，5，20，30，9，27，6，14，45，22}. The number of comparisons using straight selection sorting method is ( )
答案： 45
2、( 1分 )有一严格升序的整型数组A，元素个数为n。现将其前k（0≤k≤n）个元素整体移动到数组后面，得到数组B，使B数组的前n-k个元素恰好是A数组的后n-k个元素，B数组的后k个元素恰好是A数组的前k个元素，且前后两部分的内部升序仍保持不变。请设计一个算法在B数组中查找某个给定元素value。算法设计在函数searchValue中，函数头可采用searchValue(int B[ ], int value)。那么你设计的高效算法的时间复杂度是

There is an array of integers A with n elements in strict ascending order. Now move the first k (0<=k<=n) elements to the tail of the array. Now it is array B. The first n-k elements of B is just the last n-k elements of A. The last k elements of B is just the first k of A. The ascending order of these two parts remain unchanged. Please design an algorithm to find a specific element, value. The algorithm is in the function searchValue, that is searchValue(int B[], int value). Then the time complexity of your efficient algorithm is?

A、
O(n)

B、
O(n^0.5)

C、
O(log n)

D、
O((log n)^2)

答案： C
3、( 1分 )将序列(p, h, n, d, y, a, f, q, x, m, c, e）中的关键码按字母升序重新排序，

初始步长为4的shell排序一趟扫描的结果为（用一个空格分隔字母）

Sort the key of sequence (p, h, n, d, y, a, f, q, x, m, c, e） in ascending alphabetical order. The result of a round of shell sorting with the initial step size 4 is ? (Separate the letter by a space)
答案： p a c d x h f e y m n q
4、( 1分 )将序列(p, h, n, d, y, a, f, q, x, m, c, e）中的关键码按字母升序重新排序，以第一个元素为轴值的快速排序一趟扫描的结果为（用一个空格分隔字母）

Sort the key of sequence (p, h, n, d, y, a, f, q, x, m, c, e） in ascending alphabetical order. The result of a round of quick sorting with the first letter as the pivot is ? (Separate the letter by a space)
答案： e h n d c a f m p x q y
5、( 1分 )
序列(p, h, n, d, y, a, f, q, x, m, c, e）中的关键码按字母升序重新排序，自底向上的二路归并排序第一趟扫描的结果为（用一个空格分隔字母）

Sort the key of sequence (p, h, n, d, y, a, f, q, x, m, c, e） in ascending alphabetical order. The result of a round of two-way merge is ? (Separate the letter by a space)

答案： h p d n a y f q m x c e
6、( 1分 )以下排序算法中，不需要比较待排序记录关键码的算法是：

Which of these sorting methods do not need to compare the key of unsorted records?
A、 基数排序 Radix Sorting
B、 冒泡排序 Bubble Sorting
C、 堆排序 Heap Sorting
D、 直接插入排序 Straight Insertion Sorting
答案： A
7、( 1分 )下面的排序算法哪些是稳定的。 （多选）

Which of these algorithm are stable?
A、 插入排序 Insertion Sorting
B、 归并排序 Merge Sorting
C、 shell排序 Shell Sorting
D、 选择排序 Selection Sorting
E、 桶式排序 Bucket Sorting
F、 基数排序 Radix Sorting
G、 堆排序 Heap Sorting
H、 快速排序 Quick Sorting
I、 冒泡排序 Bubble Sorting
答案： A,B,E,F,I
8、( 1分 )对于排序算法特性的叙述正确的是() （多选）

Which of these statements about the features of sorting methods is correct? （multi-choice）
A、
冒泡排序不需要访问那些已排好序的记录 Bubble sorting does not need to visit the records that are in order.

B、
shell排序过程中，当对确定规模的这些小序列进行插入排序时，要访问序列中的所有记录 In shell sorting, when do the insertion sorting for small sequence with determined scale, all records are visited.

C、
选择排序需要访问那些已排好序的记录 In selection sorting, those in order should be visited.

D、
快速排序过程中，递归树上根据深度划分的每个层次都要访问序列中的所有记录 In quick sorting, in each level of the recursion tree divided by depth, all records are visited.

E、
归并排序过程中，递归树上每个层次的归并操作不需要访问序列中的所有记录 In merge sorting, the merge operation at each level of the recursion tree does not need to visit all records.

F、
基数排序过程中，按照每个排序码进行的桶式排序不需要访问序列中的所有记录 In radix sorting, the bucket sorting according to the sort key does not need visit all records in sequence.

显示解析
答案： A,B,D
9、( 1分 )排序算法大都是基于数组实现的，大部分的算法也能用链表来实现，但有些特殊的算法不适合线性链表存储，不适合（使算法复杂度增大）链式存储的算法有()

Sorting methods are almost implemented by arrays. Most methods can be implemented by lists. But some special methods are not suited to being stored by linear lists. Those are not suited to (increase the complexity) linked storage are ( )

A、 直接选择排序 Straight Selection Sorting
B、 插入排序 Insertion sorting
C、 堆排序 Heap sorting
D、 shell排序 Shell sorting
答案： C,D
10、( 1分 )已知数组A如下： 37 90 79 66 76 80 27 42

采用低位优先法的基数排序进行升序排序的第一轮之后的排序结果为？（数字间以一个空格分隔）

The array A is known as: 37 90 79 66 76 80 27 42

Do the ascending sort by radix sorting with the least significant digit first (LSD), what is the result of the first round? (The numbers are separated by a space)
答案： 90 80 42 66 76 37 27 79
11、( 1分 )计 划对磁带中的16条数据：｛18, 43, 38, 16, 4, 28, 7, 99, 19, 54, 42, 6, 74, 17, 63, 3｝进行排序。若排序过程中使用大小为3的堆，则对上述数据采用置换选择算法，所得最长的顺串为 ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。(数字之间用空格分隔)

Plan to sort these 16 pieces of data: {18, 43, 38, 16, 4, 28, 7, 99, 19, 54, 42, 6, 74, 17, 63, 3}. If we use a heap, whose size is 3, to sort the data, and the algorithm is "replacement selection", then the longest run will be _______________ (separate the number by a space)
答案： 4 7 16 19 28 42 54 74 99
12、( 1分 )假定有k个关键码互为同义词，即hash函数结果相同，若采用闭散列的线性探测法把这k个关键字存入散列表中，至少要进行（）次探测？

If there are k key values which are synonyms of each other, which means their return values of hash function are same, if we insert these k key values into the hash table by linear probing of closed hashing, we need to probe at least () times.
A、
k

B、 k-1
C、 k*(k+1)/2
D、 k+1
答案： C
13、( 1分 )分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成()块最好

In the blocking search, if we use sequential search to the index table and each block, then the linear table which has 900 elements should be divided into () parts at best.
答案： 30
14、( 1分 )一个散列表的散列函数是h（key）=key%19，共有20个槽，用闭散列的线性探查方法。从空表开始，依次进行如下插入删除操作，问这些操作的平均检索长度是：

提示：散列表中不能插入两个相同的关键码

There is a hash table of size 20, its hashing function is h (key) = key % 19. We use linear probing of closed hashing. We start from an empty table, in turns, perform the following insert operations and delete operations, ask you what is the average length of retrieval： (Express the answer by integer or fraction.)

Hint: we can’t insert two same key values into a hash table.

Add 26

Add 25

Add 24

Add 195

Del 26

Add 176

Add 45
A、 15/7
B、 16/7
C、 2
D、 16/5
显示解析
答案： B
15、( 1分 )有一个散列表，共有N个槽，采用双散列探查的闭散列方法解决冲突。经过一系列插入操作，当前散列表中有M个元素，负载因子a为0.1，即M/N=a=0.1。假设M,N都非常大，并且双散列探查方法近使得每一次探查的位置，可以近似为均匀分布（即等概率地探查每个槽）。

当前对于某个关键码，近似估算不成功检索的平均检索长度（）请保留2位小数

There is a hash table of size N, using closed hashing implemented by double hashing retrieval to solve conflicts. After a series of insert operations, there are M elements in the table, the load factor a is 0.1, which means M/N = a = 0.1. We assume that m and n are both very big. And the probabilities of all the position to be probed is approximately evenly distributed because of double hashing retrieval.

Now for some key value, approximately estimating the average length of failed retrieval (). Please keep two places of decimal.
答案： 1.11
16、( 1分 )在一棵m阶的B+树中，若在某结点中插入一个新关键码而引起该结点分裂，则此结点中原有的关键码个数为＿＿＿＿＿＿＿。

Consider a B+ tree with rank of m, if inserting a new key value into a node cause this node to split, then this node originally has ___ key values.
A、 m-1
B、 m
C、 m+1
D、 2*m
显示解析
答案： B
17、( 1分 )数组a在C语言中的定义为“int a[25][15][10]”。假设a[0][0][0]的地址为4000，则a[5][9][4]的地址为____。
显示解析
答案： 7376
18、( 1分 )广义表E((a,(a,b),((a,b),c)))。则E的深度为____。
显示解析
答案： 4
19、( 1分 )现有有序空闲块600,1000,1200,500,2000,800,500，以及请求序列500,600,1000,1500,500,500,500,800。使用最优适配，则有几个请求会被满足?
显示解析
答案： 8
20、( 1分 )
AVL树中任何节点的两个子树的高度最大差别为____

AVL树查找时间为O(____)，树的结构____(会/不会)改变

For every node, the heights of its left and right subtrees differ by at most ____

It takes O(___) to retrieve, and the tree structure ____(will/will not) change after retrieval.

A、 1 logN 不会will not
B、 0 logN 会will
C、 1 N 不会will not
D、 1 logN 会will
答案： A