11. 对于顺序存储的有序表{5，12，20，26，37，42，46，50，64}，若采用折半查找，则查找元素26的比较次数是（ C ）。 A.3 B. 3 C. 4 D.5
12.在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（ C ）。
A. 冒泡排序 B. 希尔排序 C. 直接选择排序 D. 直接插入排序 13.从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已
排序序列的正确的位置上，此方法称为（ A ）
A. 插入排序 B. 选择排序 C. 交换排序 D. 归并排序
14.从未排序序列中挑选元素，并将其放入已排序序列的一端，此方法称为（ C ）。 A．79，46，56，38，40，84 B．84，79，56，38，40，46
C．84，79，56，46， 40，38， D．84，56，79，40，46，38 28．一组记录的关键字序列为（25，48，16，35，79，82，23，40，36，72），其中，含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（ A ）。
A．16，25，35，48，23，40，79，82，36，72
B．16，25，35，48，79，82，23，36，40，72 C．16，25，48，35，79，82，23，36，40，72 D．16，25，35，48，79，23，36，40，82，72
29．已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数 A. 插入排序 B. 交换排序 C. 选择排序 D. 归并排序 15.依次将每两个相邻的有序表合并成一个有序表的排序方法称为（ D ）。
A. 插入排序 B. 交换排序 C. 选择排序 D. 归并排序
16.当两个元素出现逆序的时候就交换位置，这种排序方法称为（ B ）。 A. 插入排序 B. 交换排序 C. 选择排序 D. 归并排序
17.每次把待排序的区间划分为左、右两个子区间，其中左区间中记录的关键字均小
于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种排序称为（ B ）。
A. 插入排序 B. 快速排序 C. 堆排序 D. 归并排序 18.在正常情况下，直接插入排序的时间复杂度为（ D ）。 A. O(log2
2n) B. O(n) C. O(n log2n) D. O(n) 19.在正常情况下，冒泡排序的时间复杂度为（ D ）。
A. O(log2
2n) B. O(n) C. O(n log2n) D. O(n) 20.在待排序元素基本有序的情况下，效率最高的排序方法是（ A ）。 A. 插入排序 B. 快速排序 C. 堆排序 D. 归并排序
21.在下列排序方法中，关键字比较的次数与记录的初始排列秩序无关的是（ D ）。 A. 希尔排序 B. 冒泡排序 C. 插入排序 D. 选择排序 22.下述几种排序方法中，平均情况下占用内存量最大的是（ D ）方法。
A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序
23.对数据元素序列（49，72，68，13，38，50，97，27）进行排序，前三趟排序结
果时的结果依次为第一趟：49，72，68，13，38，50，97，27；第二趟：49，68，72，13，38，50，97，27；第三趟：13，49，68，72，38，50，97，27。该排序采用的方法是（ A ）。
A. 插入排序法 B. 选择排序法 C. 冒泡排序法 D.堆积排序法
24.对具有n个元素的任意序列采用插入排序法进行排序，排序趟数为（A ）。
A. n-1 B. n C. n+1 D. ?log2n?
25.对序列（49，38，65，97，76，13，47，50）采用直接插入排序法进行排序，要把第七个元素47插入到已排序中，为寻找插入的合适位置需要进行（C ）次元素间的比较。
A. 3 B. 4 C. 5 D. 6
26．一组记录的关键字序列为（46，79，56，38，40，84），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ C ）。
A．40，38，46，79，56，84 B．40，38，46，84，56，79
C．40，38，46，56，79，84 D．38，40，46，56，79，84
27．一组记录的关键字序列为（46，79，56，38，40，84），利用堆排序的方法建立的初始堆为（ B ）。
列从小到到大排序，经过一趟冒泡排序后的序列为（ B ）。
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
30．用某种排序的方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：
（1）25，84，21，47，15，27，68，35，20 （2）20，15，21，25，47，27，68，35，84 （3）15，20，21，25，35，27，47，68，84
（4）15，20，21，25，27，35，47，68，84 其所采用的排序方法是（ C ）。
A. 希尔排序 B.归并排序 C.快速排序 D. 直接选择排序 二、填空题
1．在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 哈希表查找法 。
2．关键字是记录某个 数据项的值 ，用它可以识别、确定一个 记录 。
3．在一个查找表中，能够唯一地确定一个记录的关键字称为 主关键字 。 4．平均查找长度是指为确定记录在查找表中的位置，需要与给定值进行比较的关键字个数的 数学期望值 。
5． 顺序 查找是一种最简单的查找方法。
6．折半查找又称为 二分查找 。使用该查找算法的前提条件是，查找表中记录相应的关键字值必须按 升序或降序排列 。
7．折半查找只适用于 顺序存储结构 的有序表 。
8．分块查找又称为 索引顺序查找 ，它是一种介于 顺序查找 和折半查找之间的查找方法。
9．二叉排序树或者是一棵空树，或者是具有下列性质的一棵二叉树： （1）若左子数不空，则左子树所有结点的值 均小于根结点的值 。 （2）若右子数不空，则右子树所有结点的值 均大于根结点的值 。 （3）左右子树又分别是 二叉排序树 。
10．哈希表是用来存放查找表中记录序列的表，每一个记录的存储位置是以该记录得到关键字为 自变量 ，由相应哈希函数计算所得到的 函数值 。
11．在有序表A[1….18]中，采用二分查找算法查找元素值等于A[17]的元素，所比较过的元素的下标依次是 9， 14， 16 ，17 。
12．根据排序过程中所用的存储器不同，可以将排序方法分为 内部排序 和 11
外部排序 。
13．冒泡排序是一种比较简单的 交换排序 方法。
14．在对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需要比较 3 次。
15．在归并排序中，在第3趟归并中，是把长度为 5 的有序表归并为长度为 8 有序表。
16．在堆排序和快速排序中，若原始记录接近正序和反序，则选用 堆排序 ，若原始记录无序，则最好选用 快速排序 。
17．对记录序列排序是指按记录的某个关键字排序，记录序列按___主关键字__排序结果是唯一的。
第2趟： [170，87，275，61] 462，503[897，908，653，512] 第3趟： [87，61]170[275] 462，503[897，908，653，512] 第4趟： 61 [87]170[275] 462，503[897，908，653，512] 第5趟： 61 ，87，170，[275] 462，503[897，908，653，512] 第6趟： 61 ，87，170，275，462，503[897，908，653，512] 第7趟： 61 ，87，170，275，462，503[512，653]897[908] 第8趟： 61 ，87，170，275，462，503，512，[653] 897[908] 第9趟： 61 ，87，170，275，462，503，653，897[908] 第10趟： 61 ，87，170，275，462，503，653，897，908
5．设一组记录的关键字序列为（51，85，61，43，45，49），采用堆排序算法完成以下18．按某关键字对记录序列排序， 关键字相等的记录 若在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。
19．n个元素进行冒泡法排序，通常需要进行__ n-1__趟冒泡，第j趟冒泡要进行__ n-j ____次元素间的比较。
20．当从一个小根堆中删除一个元素时，需要把 堆尾 元素填补到 堆顶 位置，然后再按条件把它逐层 向下 调整。 三、综合题
1．已知序列（70，83，100，105，10，32，7，9），请写出对此序列采用插入排序法进行升序排序时各趟的结果。
答：
原始序列：（70），83，100，65，10，32，7，9 第1趟： （70，83），100，65，10，32，7，9 第2趟：（70，83，100），65，10，32，7，9
第3趟：（65，70，83，100），10，32，7，9 第4趟：（10，65，70，83，100），32，7，9 第5趟：（10，32，65，70，83，100），7，9 第6趟：（7，10，32，65，70，83，100），9 第7趟：（7，9，10，32，65，70，83，100）
2．已知序列（10，18，4，3，6，12，1，9，15，8），请写出对此序列采用归并排序法进行升序排序时各趟的结果。
答：原始序列：10，18，4，3，6，12，1，9，15，8
第1趟： [10，18][ 3，4][6，12][1，9][ 8，15] 第2趟： [3，4，10，18，][ 1，6，9，12][ 8，15] 第3趟： [3，4，10，18，][ 1，6，8，9，12，15] 第4趟： [1，3，4，6，8，9，10，12，15，18]
3．已知序列（17，18，60，40，7，32，73，65，85）请给出采用冒泡排序法对该序列作升序排列时的每一趟结果。
第1趟：17，18，40，7，32，60，65，73，85
第2趟：17，18，7，32，40，60，65，73，85 第3趟：17，7，18，32，40，60，65，73，85 第4趟：7，17，18，32，40，60，65，73，85 第5趟：7，17，18，32，40，60，65，73，85
4．已知序列（503，87，512，61，908，170，897，275，653，462）请给出采用快速排序法对该序列作升序排列时的每一趟结果。
原始序列：503，87，512，61，908，170，897，275，653，462
第1趟： [462，87，275，61，170]503[897，908，653，512]
操作：（要求小根堆，并画出中间过程） （1）以二叉树描述6个元素的初始堆
（2）以二叉树描述逐次取走堆顶元素后，经调整得到的5个元素、4个元素的堆 （1）
（2）
6．设查找表为(20,19,24,57,68,11)
(1)用冒泡对该表进行排序，要求写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多少趟冒泡？第j趟要进行多少次元素间的比较？
(2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树.(要求以数据元素作为树结点)
(3)求在等概率条件下,对上述有序表成功查找的平均查找长度。
(1)原序列16 15 20 53 64 7
15 16 20 53 7 64 n-1趟 15 16 20 7 53 64 n-j次 15 16 7 20 53 64 15 7 16 20 53 64 7 15 16 20 53 64 (2) 16 7 53
15 20 64
(3)平均查找长度=（1*1+2*2+3*3）/6=14/6
7．(1) 设有查找表{8,17,5,9,21,10,7,19,6},依次取表中数据，构造一棵二叉排序树. （2）说明如何通过序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果.
（1）
5 12
2 14
(2)
for(j=1; （1）j<=n-1 ;j++); {flag=0;
for(i=1; （2）i<=n-j ;i++) if(a[i].key>a[i+1].key)
{flag=1; temp=a[i];
（3）a[i]=a[i+1] ; （4）a[i+1]=temp ; }
if(flag= =0)break; 中序遍历：2，3，4，5，6，7，14，16，18
四、程序填空题
1．以下直接输入排序算法对存放在a[0],a[1],···,a[n-1]中，长度为n的记录序列按关键字key由小到大排序，完成程序中的空格部分。 void disort (NODE a[ ], int n) { int I,j;
NODE temp; /*工作单位*/ for (i=1;i while (__①_ j>=0___&&temp.key a[j+1]=____④__ temp __; } } 2．以下冒泡法程序对存放在a[1]，a[2]，……，a[n]中的序列进行冒泡排序完成程序中的空格部分，其中n是元素个数，程序按升序排列。 Void bsort (NODE a[ ], int) { NODE temp; int i,j,flag; else if(a[mid].key } return -1; /*查找失败*/ } 2．编写顺序查找算法。 顺序查找算法如下： int search(NODE a[],int n, int k) /*在a[0]～a[n-1]中顺序查找关键字等于k的记录。查找成功时返回该记录的下标，失败时返回-1*/ } } 程序中flag的功能是 （5）当某趟冒泡中没有出现交换则已排好序结束循环 五、算法设计题 1．写出在二叉树中删除一个结点的算法，且使删除后仍为二叉树，设删除的结点由指针p所指，其双亲结点由指针f所指，并假设被删除结点是其双亲结点的右孩子。 折半查找算法如下； int Binary_Search(NODE a[],int n, int k) /* 在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1 */ { int low,mid,high; low=0; high=n-1; while(low<=high) { mid=(low+high)/2; if(a[mid].key==k) return mid; /*查找成功，返回查找到的记 录的下标*/ { int i=0; while(i */ i++; if(a[i].key=k) /*查找成功*/ return i; else return -1; /*查找失败*/ } 六、完成：实验5――查找 实验6——排序 根据实验要求（见教材P207－208）认真完成本实验，并提交实验报告。 13 49 49 最新资料，word文档，可以自由编辑！！ 49 83 47 41 83 59 41 精43 47 41 43 59 83 59 41 41 49 品 47 43 47 83 43 59 83 49 59 文 59 43 档 43 43 47 59 47 49 47 41 83 49 下 49 41 83 83 59 41 59 47 49 载 47 49 59 83 43 41 83 43 41 【本页是封面，下载后可以删 !】 除 14
2017年电大电大数据结构(本)形成性考核册(作业1-4)原题带答案
