(精华版)国家开放大学电大《数据结构》网络课形考任务4作业及答案.docx

《(精华版)国家开放大学电大《数据结构》网络课形考任务4作业及答案.docx》由会员分享，可在线阅读，更多相关《(精华版)国家开放大学电大《数据结构》网络课形考任务4作业及答案.docx（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、国家开放大学电大数据结构网络课形考任务4作业及答案档任务4一、单项选择题（每小题2分，共40分）题目1对线性表进行二分查找时，要求线性表必须（）=选择一项：D.以顺序存储方式，且数据元素有序题目2采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）选择一项：D. （n+l）/2题目3有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）.选择一项：B. 29/10题目4已知一个有序表为11, 22, 33,44, 55, 66, 77,88, 99,则顺序查找元素55需要比较（）次。选择一项：C. 5题目5有数据53,30,37,12,4

2、5,24,96,从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（）-选择一项：D. 37,24,12,30,63,45,96题目6对于顺序存储的有序表5,12,20,26,37,42,46,50,64,若采用折半查找，则查找元素26的比较次数是（）.选择一项：A. 4题目7在所有的捶序方法中，关键字比较的次数与记录初始排列秩序无关的是（）。选择一项：B. 直接选择拌序题目8从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称 为（）.选择一项：A. 插入排序题目9依次将每两个相邻的有序表合并成一个有序表的擂序方法称

3、为（）选择一项：B. 归并拌序题目10当两个元素出现逆序的时候就交换位置，这种排序方法称为（）。选择一项：D.交换拌序题目11每次把待排序的区间划分为左、右两个子区间，其中左区间中记录的关键字均小于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种排序称为（）选择一项：B.快速排序题目12一组记录的关键字序列为（46,20,30,79, 56.38, 40, 84,90,110）,利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）选择一项：A. 40, 20,30,38, 46, 56, 79, 84,90,110题目13在有序表10,14, 34, 43

4、, 47, 64. 75, 80. 90中，用折半查找法查找值80时，经（）次比较后查找成功。选择一项：B. 3题目14对序列（49, 38, 65, 97, 76, 13, 47, 50）采用直接插入排序法进行排序，要把第七个元素47插入到已排序中， 为寻找插入的合适位置需要进行（）次元素间的比较。选择一项：D. 5题目15排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端的方法，称为（）排序。选择一项：D.选择题目16一组记录的关键字序列为（26, 59, 36, 18. 20, 25）,利用堆排序的方法建立的初始小根堆为（）。选择一项：B. 18, 20 25

5、, 59, 26, 36题目17一组记录的关键字序列为（25, 48. 16, 35. 79, 82, 23, 40, 36, 72）,其中，含有5个长度为2的有序表，按归 并排序的方法对该序列进行一趟归并后的结果为（）选择一项：B. 16, 25, 35, 48, 23, 40, 79, 82, 36, 72题目18已知10个数据元素为（54, 28, 16, 34, 73, 62, 95, 60, 26, 43）,对该数列从小到大排序，经过一趟冒泡排序后的序列为（）选择一项：B. 28, 16, 34, 54, 62, 73, 60, 26, 43, 95题目19一组记录的关键字序列为（4

6、6, 79, 56, 38, 40, 84）,利用快速排序，以第一个关键字为分割元素，经过一次划分 后结果为（）选择一项：D. 40, 38, 46, 56, 79, 84题目20一组记录的关键字序列为（80,57,41,39,46,47）,利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（）.选择一项：B. 39, 46, 41, 57, 80, 47二、程序填空题（每题10分，2题，共20分.请点击正确选项，然后拖拽至相应的方框上）题目21以下函数是二叉捶序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回值是指向树结点的结构指 针P （查找成功P指向查到的树结点，不成功P指向

7、为NULL）完成程序中的空格typedef struct Bnode( int key;struct Bnode *left;struct Bnode *right; Bnode;Bnode *BSearch(Bnode *bt, int k)r bt用于接收二叉排辆的根结点的指针，k用以接直找的关键字 Bnode *p;if(bt= NULL5/ )return (bt);P=bt;while(p-key!= k 寸) if(kkey)p=p-left v ；else p=p-right v ；if(p=NULL) break;return(p v ;题目22以下程序是折半插入排序的算法插入

8、到已经有序的序设待排序的记录序列存放在al,-an中，以a0作为辅助工作单元，程序是要把况i05 号 sort (NODE n)f 一mxM-s.kmfor (s ;An n JI.) 里k+二 |1|廿蜜国3善浏尊*7钏目嵋C ” 尊&臂。A 23-O-C4 B.23-29-27-14 0- 23-1PM-14 D.23-29-55-14B” .i B25393 D.2.5管IE24(-27、COE，7、3g、4r46 )、B 0 4 39一4一-5700047一46 B.3gB6co.47-57 0- 39B7-46-8P4L57 D.3g-57cotM6-47(2)淳任 0 。 A.4L

9、4746ODP57 B4L57-46-BP47C.4L57ODP4746 D.4LBP46-47-57醐皿25(1)邕流漏40闽倒(56-5L71史一含M6)丑插革环.奇竺泠耶爵油 牙 C 46-5L56M7L1Q6 B. 56-51 -5446-7L1E60-46-51 -5456-7.106 D. 56-5Lr-54-71M6Q rffia知3普州忍_味(6*7 搭?57、39、4r46COE )、座田远港号135卅隘昼 2一25半3 翦*样 0 0 #、岐日f逵济5B3爵油 浏倒* D 0 皆C” .35 40 65 45 35 95B 35 40 65 43 45 95Q 35 40 43 45 65 95D 35 40 45 43 65 95（2 ）对上述序利用直接插入排序，逐次插入过程中，共进行了 D $ “次元素间的比较.A 8 B. 11C.9 D.10