数据结构练习9.doc

习 题
10．1单项选择题。
(1)排序方法的时间效率主要用排序过程中——来衡量。
A．排序趟数的多少
B．参加排序的序列中元素的多少
D．排序过程中元素移动或者交换的次数
D．排序过程中元素之间的比较次数
(2)从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放在已排序序列中的合适位置，这种排序方法称为——。
A．选择排序法 B．插入排序法
C．泡排序法 D．堆积排序法
(3)每一趟排序从未排序序列中挑选一个值最小的元素，然后将其放在已排序序列的右端，这种排序方法称为——。
A．选择排序法 B．插入排序法
C．快速排序法 ， D．谢尔排序法
(4)从未排序序列中任选出一个元素，该元素将当前参加排序的序列分成前后两个部分，前一部分中所有元素均小于等于所选元素，后一部分中所有元素均大于等于所选元素，而
所选元素处在排序的最终位置，然后分别对被分成的两部分中元素个数超过1的部分重
复上述过程，直至排序结束。这种排序方法称为——。
A．选择排序法 B．插入排序法
C．快速排序法 D．二路归并排序法
(5)与直接插入排序方法比较，折半插入排序方法减少了排序过程中的——。
A．排序趟数 D．元素之间的比较次数
C．元素的移动次数 D．辅助空间
(6)在所学过的排序方法中，排序趟数与序列的原始状态有关的方法是——。
A．选择排序法 B．谢尔排序法
C．堆积排序法 D．泡排序法
(7)对序列(49，38，65，97，76，13，47，50)采用折半插入排序法进行排序，当把第七个元素47插入到已排序序列中，为寻找插入的合适位置需要进行——次元素间的比较。
A．3 B．4 C．5 D．6
(8)若对序列(tang，deng，an，wang，shi，bai，fang，1iu)采用选择排序法按字典顺序进行排序，下面给出的四个序列中，——是第三趟的结果。
A．an，bai，deng，wang，tang，fang，shi，1iu
B．an，bai，deng，wang，shi，tang，fang，liu
C．an，bai，deng，wang，shi，fang，tang，1lu
D．an，bai，deng，wang，shi，1iu，tang，fang
(9)对于序列(49，38，65，97，13，27，50)按从小到大进行排序，——是初始步长d=4的谢尔排序法第一趟的结果。
A．49，76，65，13，27，50，97，38
B．3，27，38，49，50，65，76，97
C．97，76，65，50，49，38，27，13
D．49，13，27，50，76，38，65，97
(10)对序列(Q，D，F，X，A，P，N，B，Y，M，C，W)采用二路归并排序，下面的四个序列中——是第三趟的结果。
A．A，B，D，F，N，P，Q，X，C，W，M，Y
B．A，B，F，D，N，P，Q，X，C，M，W，Y
C．A，B，D，F，P，Q，X，N，C，M，W，Y
D．A，B，D，F，N，P，Q，X，C，M，W，Y
(11)对具有n个元素的序列采用选择排序法排序，排序趟数为——。
A．n B．n-1 C．n+l D．Llog2n』
(12)对具有n个元素的序列采用泡排序法排序，排序趟数为——。
A．n B．n-1 C．[1，n] D．[1，n-1]
(13)对具有n个元素的序列采用堆积排序法排序，排序趟数为——。
A．n B.Lnlog2nJ C.L10g2nJ D．n-1
(14)根据(大顶)堆积的定义，下面的四个序列中——是一个堆积。
A．75，65，30，15，25，45，20，10
B．75，65，45，10，30，25，20，15
C．75，45，65，30，15，25，20，10
D．75，45，65，10，25，30，20，15
(15)插入排序法的时间花费主要取决于元素间的比较次数，若具有n个元素的序列初始时已经是一个递增序列，则排序过程中一共要进行——次这种比较。
A．n B．n-1 C．n(n-1)／2 D．n2
(16)插入排序法的时间花费主要取决于元素间的比较次数，若具有n个元素的序列初始时为一个递减序列，则排序过程中一共要进行——次元素间的比较。
A．n B．n-1 C．n(n-1)／2 D．n2
(17)若——，则称这样的排序方法为非稳定性排序方法。
A．排序前后，值相同的元素的先后相对位置可能会颠倒
B．排序前后，值相同的元素的先后相对位置一定会颠倒
C．对同一个序列，每次排序的结果可能不相同
D．排序结果不可预测
(18)下面四种排序方法中，——是一种稳定性排序方法。
A．插入排序法 B.选择排序法
C．快速排序法 D．谢尔排序法
(19)下面四种排序方法中，——占用的辅助空间最多。
A．插入排序法 B．堆积排序法
C．快速排序法 D．二路归并排序法
(20)在序列中各元素已经排好序的情况下，采用——方法可以尽可能快地结束排序。
A，插入排序 B．泡排序 C．快速排序 D．堆积排序
(21)在序列中各元素已经排好序的情况下，采用——方法的时间效率最低。
A。插入排序 B．泡排序 C．快速排序 D．堆积排序
(22)在序列中各元素已经排好序的情况下，采用——方法时元素的移动次数最少。
A。选择排序 B．快速排序 C．堆积排序 D．归并排序
(23)若序列的原始状态为9，8，7，6，5，4，3，2，1，要想获得比较好的时间效率，不应该采用下列四种排序方法中的——方法。
A。谢尔排序 B．快速排序 C．堆积排序 D．归并排序
(24)若序列的原始状态为1，2，3，4，5，10，6，7，8，9，要想使得排序过程中元素的比较次数最少，应该采用——方法。
A，插入排序 B．选择排序 C．谢尔排序 D．泡排序
(25)当参加排序的数据量较大，元素的分布又比较随机，并且无排序稳定性要求，宜选择_____.
A。插入排序法 B．选择排序法 C．快速排序法 D．堆积排序法 10．2 请以关键字序列{503，87，512，75，93，170，365，602，612}为例，分别写出执行以下排序算法时每一趟排序的结果，并分别统计每一趟排序过程中所进行的关键字比较的次数。
(1)插入排序；
(2)谢尔排序；
(3)堆积排序；
(4)二路归并排序。
10．3 什么是堆积?请根据堆积的定义和堆积的构造方法写出对应于序列{12，18，4，36，23，41，20，50，19}的初始堆积。
10．4 已知序列为{12，2，16，30，8，28，4，10，20，6}，请分别写出采用下列排序方法进行排序时每一 趟结束的结果。
(1)选择排序法；
(2)泡排序法；
(3)快速排序法；
(4)基数排序法。 10．5 设有10000个元素组成的无序序列，希望尽快挑选出其中前10个(仅挑出前10个㈠最大值元素，在不改变已有算法结构的前提下，以下几种内排序算法中哪一种最合适?为什么?
(1)选择排序法；
(2)快速排序法；
(3)堆积排序法；
(4)泡排序法。
10．6 请写出快速排序法的非递归算法。
10．7 请写出用带头结点的线性链表作为存储结构时的选择排序算法。设链表中头结点的指针为list；要求算法中不得使用除链表以外的其他链结点空间，也不得改变链结点数据域内容。
10．8 请写出用带头结点的双向循环链表作为存储结构时的插入排序算法。设头结点指针为list；算法中不得使用除链表外的其他链结点空间，也不得改变链结点数据域内容。
10．9 请回答在你所学过的内排序方法中，哪些方法是稳定的?哪些方法是不稳定的?并为每一 种不稳定的排序方法举出一个不稳定的实例。
10．10 选择排序法与堆积排序法每一趟排序都是从当前未排好序的元素中选出一个元素，而一般情况下堆积排序法的时间效率远比选择排序法的时间效率要高，为什么?
10．11 若n个值各不同的元素存在于数组A[n]中，则可按如下所述过程实现的排序方法称为计数排序法：另设一个数组B[n](初值均为0)，对A中每个元素A[i]，统计A中值比它小的元素的个数并存于B[i]中，则与B[i]0对应的元素A[i]必为A中值最小的元素；然后，根据B[i]值的大小将A中元素重新排列(即根据BC门确定A[i]的排序位置)。请编写一算 法，实现上述排序方法。
10．12 请为下列每种情况选择合适的内排序方法：
(1)n=30，且要求最坏情况下速度最快；
(2)n=30，且要求既要快，又要排序稳定；
(3)n=1000，要求平均情况下速度最快；
(4)n=1000，要求最坏情况下速度最快；
(5)n=1000，要求既要快，又要最节省存储空间。

历年考试题

12．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（　　　）
A．左子树的叶子结点 B．左子树的分支结点
C．右子树的叶子结点 D．右子树的分支结点
13．希尔排序的增量序列必须是（　　　）
A．递增的 B．随机的
C．递减的 D．非递减的
14．如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为（　　　）
A．插入排序 B．归并排序
C．冒泡排序 D．堆排序
2．设某二维数组A［1..n，1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为（　　　）
A．O（log2n） B．O(n)
C．O(nlog2n) D．O(n2)
14．下列关键码序列中，属于堆的是（　　　）
A．（15，30，22，93，52，71） B．（15，71，30，22，93，52）
C．（15，52，22，93，30，71） D．（93，30，52，22，15，71）
15．已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列按从小到大排序，经过一趟冒泡排序后的序列为（　　　）
A．16，28，34，54，73，62，60，26，43，95
B．28，16，34，54，62，73，60，26，43，95
C．28，16，34，54，62，60，73，26，43，95
D．16，28，34，54，62，60，73，26，43，95
14．一组记录的键值为（46，74，18，53，14，20，40，38，86，65），利用堆排序的方法建立的初始堆为（　　　）
A．（14，18，38，46，65，40，20，53，86，74）
B．（14，38，18，46，65，20，40， 53，86，74）
C．（14，18，20，38，40，46，53，65，74，86）
D．（14，86，20，38，40，46，53，65，74，18）
15．对序列（22，86，19，49，12，30，65，35，18）进行一趟排序后得到的结果如下：（18，12，19，22，49，30，65，35，86），则可以认为使用的排序方法是（　　　）
A．选择排序 B．冒泡排序
C．快速排序 D．插入排序
12.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是( )
A.快速排序 B.堆排序 C.归并排序 D.基数排序
13.不可能生成右图所示二叉排序树的关键字序列是( )
A.4 5 3 1 2
B.4 2 5 3 1
C.4 5 2 1 3
D.4 2 3 1 5

14.ALV树是一种平衡的二叉排序树，树中任一结点的( )
A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不超过1
C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度
15.在VSAM文件的控制区间中，记录的存储方式为( )
A.无序顺序 B.有序顺序
C.无序链接 D.有序链接
3、某顺序存储的表格,其中有90, 000个元素,已按关键项的植的上升顺序排列。现假定对各个元素进行查的概率是相同的, 并且各个元素的关键项的值皆不相同。
用顺序查找法查找时，平均比较次数约为＿A＿，最大比较次数为＿B＿。
现把90,000个元素按排列顺序划分成若干组，使每组有g个元素（最后一组可能不足g个）。查找时，先从第一组开始，通过比例各组的最后一个元素的关键项的值，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的平均比较次数最小的g是＿C＿，此时的平均比较次数是＿D＿。当g的值大于等于90，000时，此方法的查找速度接近于＿E＿。　
供选择的答案
A、B：①25，000　 ②30，000 ③45，000 　④90，000
C、D：①100 　　　②200 ③300　　　　 ④400
E：①快速分类法　 ②斐波那契查找法
③二分法　　 　 ④顺序查找法
(试题2）
堆是一种特殊的数据结构，__A__是一个堆，堆排序是一种__B__排序，m个元素进行堆排序时，其时间复杂性为__C__。
　　排序的算法很多，若按排序的稳定性和不稳定性分类，则__D__是不稳定排序。
　　外排序是指__E__。
供选择的答案　
　　Ａ：①19,75,34,26,97,56 ②97,26,34,75,19,56
　　　　③19,56,26,97,34,75 ④19,34,26,97,56,75
　　Ｂ：①归并　　 ②交换 ③选择　　 ④插入
　　Ｃ：①o(m)　　 ②o(m2) ③o(log2m) ④o(mlog2m)
　　Ｄ：①冒泡排序 ②归并排序 ③直接插入排序 ④希尔(shell)排序
　　Ｅ：①用机器指令直接对硬盘中需排序数据排序
　　　　②把需排序数据，用其他大容量机器排序
　　　　③把外存中需排序数据一次性调入内存，排好序后，再输回外存
　　　　④对外存中大于内存允许空间的需排序的数据，通过多次内外存间的交换实现排序。
试题6
　　堆是一种有用的数据结构。例如关键码序列＿A＿是一个堆。　　　　　　　
堆排序是一种＿B＿排序，它的一个基本问题是如何建堆，常用的建堆算法是1964 年 Floyd 提出的，＿C＿对含 n 个元素的序列进行排序时，堆排序的时间复杂性是＿D＿，所需的附加存储结点是＿E＿。　　　　　　　　　　　　　　　
供选择的答案
　　A： ①16, 72, 31, 23, 94, 53 ②94, 53, 31, 72, 16, 53 
③16, 53, 23, 94, 31, 72 ④16, 31, 23, 94, 53, 72 
⑤94, 31, 53, 23, 16, 72 
B： ①插入　　　 ②选择　　　 ③交换　 　 ④基数　　 ⑤归并　
　　C： ①淘汰法　　 ②筛选法　　 ③递推法　 ④LRU 算法　　　　　　
D、E：①O(nlog2n) ②O(n) ③O(log2n) ④O(n2)  ⑤O(1)

(试题1 )
在排序算法中，两两比较待排序的记录，当发现不满意顺序要求时，变更它们的相对位置，这就是__A__ 排序。每次从未排序的记录中挑出最小(或最大)关键码值的记录，加入到已排序记录的末尾，这是__B__就组成一个堆，堆排序的平均执行时间和需附加的存储结点分别为__E__。
供选择的答案
A～C：① 插入 ② 枚举 ③ 交换 ④ 归并
⑤ 基数 ⑥ 选择 ⑦ 希尔
D： ① 20、76、35、23、80、54 ② 20、54、23、80、35、76
③ 80、23、35、76、20、54 ④ 20、35、23、80、54、76
E： ① O（n2）和O（1） ② O（n log2 n）和O（1）
③ O（n log2 n）和O（n） ④ O(n2) 和O(n)

23．若希望只进行8趟排序便能在4800个元素中找出其中值最小的8个元素，并且要求排序过程中所进行的关键字比较次数尽可能少，则应该选用________________排序方法。
27．在待排序的n个记录中任取一个记录，以该记录的键值作为标准，将所有记录分为两组，使得第一组中各记录的键值均小于或等于该键值，第二组中的各记录的键值均大于该键值；然后将该记录排在两组中间。再对所分成的两组分别使用上述方法，直到所有记录都排在适当位置为止。这种排序方法称为________________。
28．在对一组记录关键字（54，38，96，23，15，72，60，45，83）进行冒泡排序时，整个冒泡排序过程中需进行________________趟才能完成。
23.对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为________。
24.由10000个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值可能达到________。
28.对关键字序列(72，87，61，23，94，16，05，58)进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和前三趟的序列状态。
初始堆：________
第1趟：________
第2趟：________
第3趟：________
(3) 给定序列{100, 86, 48, 73, 35, 39, 42, 57, 66, 21}, 按堆结构的定义, 则它一定( ⑤ )堆。
(4) 在进行直接插入排序时, 其数据比较次数与数据的初始排列（ ⑥ ）关；而在进行直接选择排序时，其数据比较次数与数据的初始排列（ ⑦ ）关。

33．已知序列（503，87，512，61，908，170，897，275，653，462）请给出采用快速排序法作升序排序时的每一趟的结果。（8分）
29．已知R［1..8］中的元素依次为（12，5，9，20，6，31，24，27），写出按算法MergeSortDC　对R进行自顶向下的二路归并排序过程中，前5次调用函数Merge(R, low, mid, high)时参数 low, mid 和high的值。
void MergeSortDC (int R[], int low, int mid, int high )
{
int mid;
if (low<high)
{
mid = (low +high)/2;
MergeSortDC (R, low, mid);
MergeSortDC (R, mid+1, high);
Merge (R, low, mid, high);
}
} // MergeSortDC
　（1）第一次调用时的参数值；
　（2）第二次调用时的参数值；
（3）第三次调用时的参数值；
（4）第四次调用时的参数值；
（5）第五次调用时的参数值；
33．已知整形数组L［1..8］中的元素依次为（9，8，5，7，6，3，2，1），阅读下列函数，并写出执行函数调用　sort(L, 8)时，对L进行的头两趟（pass分别为0和1）处理结果。
　Void sort (int R[],int n)
{
　 int pass = 0, k, exchange, x;
　 do {
　 k=pass%2+1;
　 exchange = 0;
　 while (k<n)
　 {
　 　if (R[k]>R[k+1])
　 　{
　 x = R[k]; R[k] = R[k+1]; R[k+1] = x;
　 exchange =1;
}
K+=2
}
　pass ++;
}while (exchange = = 1|| pass <=1);
}
第一趟（pass = 0）:
第二趟（pass = 1）:
34．已知二叉排序树中结点的关键字为整数，设计递归算法按递增有序性输出树中所有大于或等于给定值x的结点，并以函数的参数返回输出的结点个数。假设以二叉链表为存储结构，其结点结构为：

lchild
key
rchild

33．已知序列（10，18，4，3，6，12，1，9，15，8），请给出采用二路归并排序法对该序列进行升序排序时的每一趟结果。（6分）
35．修改冒泡排序法以实现双向冒泡排序。双向冒泡排序指第一次把最大记录放到表尾，第二次把最小记录放到表头，如此反复进行。试编写修改后的算法：void dbubble(int a[],int n)。（8分）

试题三
阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。
[函数3．1说明]
函数insert_sort(int a[]，int count)是用直接插入排序法对指定数组的前count个元素从小到大排序。
直接插入排序法的基本思想是：将整个数组(count个元素)看成是由有序的(a[0]，…，a[i-1])和无序的(a[i]，…，a[Count-1))两个部分组成；初始时i等于1，每趟排序时将无序部分中的第一个元素a[i]插入到有序部分中的恰当位置，共需进行count-1趟，最终使整个数组有序。
[函数3.1]
void insert_sort(int a[] , int count)
{ int i, j, t;
for(i=1 ; i<count ; i++)
{ /*控制a[i],……, a[count-1]的比较和插入*/
t=a[i];
j= (1) ;
while (j>=0 && t<a[j])
{ /*在有序部分中寻找元素a[i]的插入位置*/
(2) ;
j--;
}
(3) ;
}
}
[函数3．2说明]
递归函数invert(int a[]，int k)将指定数组中的前k个元素逆置。
[函数3．2]
void invert(int a[] , int k);
{ int t;
if ( (4) ) {
invert( (5) );
t=a[0];
a[0]=a[k-1];
a[k-1]=t;
}
}

试题五
阅读下列函数说明和C代码，将应填入 (n) 处的字句写在答题纸的对应栏内。
设二叉树的结点数据类型为：
typedef struct node{
char data；
struct node *left；
struct node *right：
}BTREE；
[函数5.1说明]
函数void SortTreelnsert(BTREE **tree，BTREE*s)采用递归方法，将结点s插入以*tree为根结点指针的二叉排序树(二叉查找树)中。
[函数5.1)
void SortTreelnsert(BTREE **tree，BTREE *S)
{ if(*tree = = NULL) *tree=S;
else if(S->data<(*tree)->data)
SortTreelnsert( (1) ，S)；
else if(S->data>(*tree)->data)
SortTreelnsert( (2) ，S)；
}
[函数5．2说明]
函数void TraversalTree(BTREE *tree)用非递归方法，对以tree为根结点指针的二叉树进行后序遍历。
[函数5，2]
void TraversalTree(BTREE *tree)
{ BTREE *stack[1000]，*p；
int tag[1000]，top=0；
p=tree；
do {
while(p!=NULL){
stack[++top]=p；
(3) ；
tag[hop]=0； ／*标志栈顶结点的左子树已进行过后序遍历*／ ：
}
while(top>0 && (4) ){ /* 栈顶结点的右子树是否被后序遍历过*／
p=stack[top--];
putchar(p->data)；
}
if (top>0) { /*对栈顶结点的右子树进行后序遍历*／
(5) ；
tag[top]=1；
}
}while(top>0)；
}