国家开放大学电大《数据结构》网络课形考任务4作业及答案

国家开放大学电大数据结构网络课形考任务4作业及答案档任务4一、单项选择题（每小题2分，共40分）题目1对线性表进行二分查找时，要求线性表必须（）=选择一项：A. 以链接存储方式B. 以链接存储方式，且数据元素有序C. 以顺序存储方式D. 以顺序存储方式，且数据元素有序题目2采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。选择一项：A. nB. （n-l）/2C. n/2D. （n+l）/2题目3有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）.选择一项：A. 29/9B. 29/10C. 26/10D. 31/10题目4已知一个有序表为（11,22, 33,44, 55, 66, 77,88,99,则顺序查找元素55需要比较（）次。选择一项：A. 6B. 3C. 5D. 4题目5有数据（53,30,37, 12,45,24,96.从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（）o选择一项：A. 12, 24, 30, 37, 45, 53, 96B. 30, 24, 12, 37, 45, 96, 53C. 45, 24, 53, 12, 37, 96, 30D. 37,24,12,30,53,45,96题目6对于顺序存储的有序表5,12,20,26,37,42, 46,50,64,若采用折半查找，则查找元素26的比较次数是（）.选择一项：A. 4B. 6C. 3D. 5题目7在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（）选择一项：A. 希尔捧序B. 直涯序C. 冒泡排序D. 直接插入捶序题目8从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为（）。选择一项：A. 插入拌序B. 选择排序C. 归并排序D. 交换排序题目9依次将每两个相邻的有序表合并成一个有序表的排序方法称为（）选择一项：A. 交换排序B. 归并排序C. 插入排序D. 选择捶序题目10当两个元素出现逆序的时候就交换位置，这种排序方法称为（）选择一项：A. 选择捶序B. 插入擂序C. 归并捶序D. 交换排序题目11每次把待排序的区间划分为左、右两个子区间，其中左区间中记录的关键字均小于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种排序称为（）。选择一项：A. 插入排序B. 快鞘序C. 堆排序D. 归并排序题目12一组记录的关键字序列为（46,20,30,79, 56.38, 40, 84,90,110）,利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）选择一项：A. 40, 20,30,38,46, 56, 79, 84,90,110B. 20,30 38, 40,46, 56, 79, 84,90,100C. 20,30,40, 38.46, 79, 56. 84,90,100D. 30,20,40, 38,46, 84, 56. 79,90,100题目13在有序表10,14, 34, 43, 47, 64. 75, 80. 90中，用折半查找法查找值80时，经（）次比较后查找成功。选择一项：A. 5B. 3C. 2D. 4题目14对序列（49, 38, 65, 97, 76, 13,47, 50）采用直接插入排序法进行排序，要把第七个元素47插入到已排序中，为寻找插入的合适位置需要进行（）次元素间的比较。选择一项：A. 3B. 4C. 6D. 5题目15排序方法中，从未捶序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端的方法，称为（）排序。选择一项：A. 插入B. 快速C. 归并D. 选择题目16一组记录的关键字序列为（26. 59.36. 18, 20. 25）,利用堆排序的方法建立的初始小根堆为（）。选择一项：A. 26,18,59,20,36,25B. 18,20,25,59,26,36C. 18,20,36,59,26,25D. 26,59,36,18,20,25题目17一组记录的关键字序列为（25, 48.16, 35, 79. 82, 23, 40, 36, 72）,其中，含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（）选择一项：A. 16,25,35,48,79,23,36,40,82,72B. 16,25,35,48,23,40,79,82,36,72C. 16,25,48,35,79,82,23,36.40.72D. 16,25,35,48,79,82,23,36,40,72题目18已知10个数据元素为（54, 28, 16, 34, 73, 62, 95, 60, 26, 43）,对该数列从小到大排序，经过一趟冒泡排序后的序列为（）-选择一项:A. 16, 28. 34, 54, 62, 60,73, 26, 43, 95B. 28, 16, 34, 54, 62, 73,60, 26, 43, 95C. 16, 28. 34, 54, 73, 62,60. 26, 43, 95D. 28, 16, 34, 54, 62, 60,73, 26, 43, 95题目19一组记录的关键字序列为（46. 79. 56, 38, 40, 84）,利用快速排序，以第一个关键字为分割元素，经过一次划分 后结果为（）.选择一项：A. 40,38,46,84,56,79B. 40,38,46,79,56,84C. 38,40,46,56,79,84D. 40,38,46,56,79,84题目20一组记录的关键字序列为（80,57,41,39,46,47）,利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（）.选择一项：A. 39,80,46,47,41,57B. 39,46,41,57,80,47C. 41,39,46,47,57,80D. 39,47,46,80,41,57二、程序填空JS 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= NULL 寸)return (bt);P=bt;while(p-key!= k 寸) if(kkey)p=p-left 寸；else p=p-right y ;if(p=NULL) break;return( p v 题目22以下程序是折半插入排序的算法设待排序的记录序列存放在al,an中，以a0作为辅助工作单元，程序是要把ai插入到已经有序的序void binsort (NODE a jnt n) intxjj.sKm;for (i=2 ; i= n 寸;i+ ) a(0=ali;x= ai.key;S=1；j=i-1；while (s=j+1;k-)ak+l v =ak;aj+1=aOj;三、综合题(每小题8分，共40分)题目23(1)设查找表为(1,10,11,14,23,27,29,55,68)，画出对上述直找表进行折半直找所对应的判定树，为了成功查 找到元素14,需要依次与元素C = V进行比较。A. 23.10.1.14B.23.29.27.14 C. 23.10,11.14 D.23.29.55,14(2 )在等概率条件下，成功查找的平均比较次数为B # V。A.24/9 B. 25/9C.3D.2.5题目242 - (47、80、57、3gkr46 )、sisiiMU B 39-4L57.847.46 B.3g.4BCDp47.570- 3g.47.46.84L57 D.39.4L5700P46.47 Q 淳任A 、潜白竺少on爵油翌c ” 46.5L56.54m 二。6 B. 56.5L54.46.7二060-46.5L54.56.7L106 0. 56.5L46.54.71M6-e Baucis ( 6.470?57、39kr46 .3。)、座理1JJ%4 藻3,卅成K(2.2s*s 籍&*一 0A(3p57. 6P8P47.39.4L46 ) B.(47. 6P57000. 3P39BM6 )C.(4L 57. 6P8P30.3g.47.46 ) 0. (47. 573 8P30.3941 .46 )筒IE26(1) 涔冰漏40囤涅(36念.46.28.3。74)湘丑5廖赣、H普府*叶慰弟、的心寿竺冷5B3器油 画浸D 36.28.3。46念.74 w 3646.28.2P69-740- 38.36.3。.46 念.74 D.2B.36.3P46.6W74S 27(-、4。、653 35 951任迷前一港圆岩教圳研座3&性d)曹醐涉00 -A 35 40 65 45 35 95B 35 4。65 43 45 95935 4043 45 65 95D 35 40 45 43 65 95（2 ）对上述序511利用直接插入排序，逐次插入过程中，共进行了 D W /次元素间的比较A. 8 B. 11C.9 D 10