(精华版)国家开放大学电大《数据结构》网络课形考任务4作业及答案.docx
国家开放大学电大数据结构网络课形考任务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,45,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依次将每两个相邻的有序表合并成一个有序表的擂序方法称为（）选择一项：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, 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, 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一组记录的关键字序列为（46, 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指向为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(k<p->key)p=p->left v ；else p=p->right v ；if(p=NULL) break;return(p v ;题目22以下程序是折半插入排序的算法插入到已经有序的序设待排序的记录序列存放在al,-an中，以a0作为辅助工作单元，程序是要把况i<05 号 sort (NODE n)f 一mxM-s.kmfor (s ;An n <_.+) f aoHaMXH a 三.key;s"-t3wn=e aAJl.Jf m=| a+jy2 4for (kur.-tk>JI.) 里k+二 < 直芸 au+亍目III，I (a、J，i8 8 *40v) 蹈皿23(1二冷圈港洲苫?1.0.-工23-27-29-55念)、回任邕_费>|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.4L4746ODP57 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 <ACOP57- 6P8047-39411) B. (47-6.57-co.3-p3g_41l)0(4.57-6。00- 3p3gBU6 ) 口 (47-罗sS. 30-3941-46 )(1) 母*陶电面倒(36 念一金-28-30-74)制丑>#>、岐日f逵济5B3爵油 浏倒* D " <A3E、2CO、46、36、69、74 B.2S03E、36、46、69、74 0- 2W 3?46、36、69、74 0-3E-2CO、366、69、74(2) > 0 < A 36-28-3P46 念-74 w 3646-28-2p6g-74.0- 3936-3P46 念-74 D.2536:3.46 念-74醐皿27(1 ) nfia知3薯咽&净工5、40、65、43 - 35、95顶任圣前薄胃 E 费圳卅、四3&芷53龄>皆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
