國家開放大學電大數(shù)據(jù)結構網(wǎng)絡課形考任務4作業(yè)及答案檔任務4一、單項選擇題（每小題2分，共40分）題目1對線性表進行二分查找時，要求線性表必須（）=選擇一項：A. 以鏈接存儲方式B. 以鏈接存儲方式，且數(shù)據(jù)元素有序C. 以順序存儲方式D. 以順序存儲方式，且數(shù)據(jù)元素有序題目2采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（）。選擇一項：A. nB. （n-l）/2C. n/2D. （n+l）/2題目3有一個長度為10的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（）.選擇一項：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有數(shù)據(jù)（53,30,37, 12,45,24,96.從空二叉樹開始逐個插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，應該選擇的序列是（）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的比較次數(shù)是（）.選擇一項：A. 4B. 6C. 3D. 5題目7在所有的排序方法中，關鍵字比較的次數(shù)與記錄初始排列秩序無關的是（）選擇一項：A. 希爾捧序B. 直涯序C. 冒泡排序D. 直接插入捶序題目8從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱為（）。選擇一項：A. 插入拌序B. 選擇排序C. 歸并排序D. 交換排序題目9依次將每兩個相鄰的有序表合并成一個有序表的排序方法稱為（）<>選擇一項：A. 交換排序B. 歸并排序C. 插入排序D. 選擇捶序題目10當兩個元素出現(xiàn)逆序的時候就交換位置，這種排序方法稱為（）選擇一項：A. 選擇捶序B. 插入擂序C. 歸并捶序D. 交換排序題目11每次把待排序的區(qū)間劃分為左、右兩個子區(qū)間，其中左區(qū)間中記錄的關鍵字均小于等于基準記錄的關鍵字，右區(qū)間中記錄的關鍵字均大于等于基準記錄的關鍵字，這種排序稱為（）。選擇一項：A. 插入排序B. 快鞘序C. 堆排序D. 歸并排序題目12一組記錄的關鍵字序列為（46,20,30,79, 56.38, 40, 84,90,110）,利用快速排序，以第一個關鍵字為分割元素，經(jīng)過一次劃分后結果為（）選擇一項：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時，經(jīng)（）次比較后查找成功。選擇一項：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個數(shù)據(jù)元素為（54, 28, 16, 34, 73, 62, 95, 60, 26, 43）,對該數(shù)列從小到大排序，經(jīng)過一趟冒泡排序后的序列為（）-選擇一項: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）,利用快速排序，以第一個關鍵字為分割元素，經(jīng)過一次劃分 后結果為（）.選擇一項：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以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結點的指針，否則，返回值是指向樹結點的結構指 針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(k<p->key)p=p->left 寸；else p=p->right y ;if(p=NULL) break;return( p v 題目22以下程序是折半插入排序的算法設待排序的記錄序列存放在al,an中，以a0作為輔助工作單元，程序是要把ai插入到已經(jīng)有序的序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) m=| (s+jy2 I for (k=k1;k>=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 )在等概率條件下，成功查找的平均比較次數(shù)為B # V。A.24/9 B. 25/9C.3D.2.5題目242 - (47、80、57、3gkr46 )、sisiiMU B " <磊島沖洲池婀、M沖洲-米曲食3*斗厚)。> 39-4L57.847.46 B.3g.4BCDp47.570- 3g.47.46.84L57 D.39.4L5700P46.47 Q 淳任A " < - A4M7.46.8P57 B.4L5746.8P47 C.4L57.8P47.46 D.4L8P4647.57s 25(1)咨冰電囤倒(56公.7言4含.占6).絲魚港廁贛> 、潛白>竺少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 " <A3T 28 46 36 69 74 B.2S03?36 46 69 74 92W 3CL46L6 69 74 0- 3T 28 36k6 69 L4(2) > 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