國家開放大學(xué)電大數(shù)據(jù)結(jié)構(gòu)網(wǎng)絡(luò)課形考任務(wù)4作業(yè)及答案形考任務(wù)4一、單項(xiàng)選擇題（每小題2分，共40分）題目1對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（）o選擇一項(xiàng)：A. 以鏈接存儲(chǔ)方式B. 以鏈接存儲(chǔ)方式，旦數(shù)據(jù)元素有序C. 以順序存儲(chǔ)方式D. 以順序存儲(chǔ)方式，且數(shù)據(jù)元素有序題目2采用順序查找方法查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為（）。選擇一項(xiàng)：A. nB. （n-l）/2C. n/2D. （n+1） /2題目3有一個(gè)長度為10的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。選擇一項(xiàng)：A. 29/9B. 29/10C. 26/10D. 31/10題目4已知一個(gè)有序表為11, 22, 33, 44, 55, 66, 77, 88, 99）,則順序查找元素55需要比較（）次。選擇一項(xiàng)：A. 6B. 3C. 5D. 4題目5有數(shù)據(jù)（53, 30, 37, 12, 45, 24, 96）,從空二叉樹開始逐個(gè)插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，應(yīng)該選擇的序列是（）o選擇一項(xiàng)：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對(duì)于順序存儲(chǔ)的有序表5, 12, 20, 26, 37, 42, 46, 50, 64,若采用折半查找，則查找元素26的比較次數(shù)是（）。選擇一項(xiàng)：A. 4B. 6C. 3D. 5題目7在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄初始排列秩序無關(guān)的是（）o選擇一項(xiàng)：A. 希爾排序B. 直接選擇排序C. 冒泡排序D. 直接插入排序題目8從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱 為（）。選擇一項(xiàng)：A. 插入排序B. 選擇排序C. 歸并排序D. 交換排序題目9依次將每兩個(gè)相鄰的有序表合并成一個(gè)有序表的排序方法稱為（）o選擇一項(xiàng)：A. 交換排序B. 歸并排序C. 插入排序D. 選擇排序題目10當(dāng)兩個(gè)元素出現(xiàn)逆序的時(shí)候就交換位置，這種排序方法稱為（）。選擇一項(xiàng)：A. 選擇排序B. 插入排序C. 歸并排序D. 交換排序題目11每次把待排序的區(qū)間劃分為左、右兩個(gè)子區(qū)間，其中左區(qū)間中記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄的關(guān)鍵字，右區(qū)間中記錄的關(guān)鍵字均大于等于基準(zhǔn)記錄的關(guān)鍵字，這種排序稱為（）。選擇一項(xiàng)：A. 插入排序B. 快速排序C. 堆排序D. 歸并排序題目12一組記錄的關(guān)鍵字序列為（46, 20, 30, 79, 56,38, 40, 84,90,110）,利用快速排序，以第一個(gè)關(guān)鍵字為分割元素,經(jīng)過一次劃分后結(jié)果為（）o選擇一項(xiàng)：A. 40,20,30,38,46,56,79,84,90,110B. 20,3038,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時(shí)，經(jīng)（）次比較后查找成功。選擇一項(xiàng)：A. 5B. 3C. 2D. 4 題目14 對(duì)序列（49, 38, 65, 97, 76, 13, 47, 50）采用直接插入排序法進(jìn)行排序，要把第七個(gè)元素47插入到已排序中，為 尋找插入的合適位置需要進(jìn)行（）次元素間的比較。選擇一項(xiàng)：A. 3B. 4C. 6D. 5題目15排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（）排序。選擇一項(xiàng)：A. 插入B. 快速C. 歸并D. 選擇題目16一組記錄的關(guān)鍵字序列為（26, 59, 36, 18, 20, 25）,利用堆排序的方法建立的初始小根堆為（）。選擇一項(xiàng)：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一組記錄的關(guān)鍵字序列為（25, 48, 16, 35, 79, 82, 23, 40, 36, 72）,其中，含有5個(gè)長度為2的有序表，按歸并排序的方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為（）o選擇一項(xiàng)：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個(gè)數(shù)據(jù)元素為（54, 28, 16, 34, 73, 62, 95, 60, 26, 43）,對(duì)該數(shù)列從小到大排序，經(jīng)過一趟冒泡排序后的序列為（）o選擇一項(xià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一組記錄的關(guān)鍵字序列為（46, 79, 56, 38, 40, 84）,利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（）0選擇一項(xià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一組記錄的關(guān)鍵字序列為（80, 57, 41, 39, 46, 47）,利用堆排序（堆頂元素是最小元素）的方法建立的初始堆為（）。選擇一項(xiàng)：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二、程序填空題（每題10分，2題，共20分。請(qǐng)點(diǎn)擊正確選項(xiàng)，然后拖拽至相應(yīng)的方框上）題目21以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點(diǎn)的指針，否則，返回值是指向樹結(jié)點(diǎn)的結(jié)構(gòu)指 針P （查找成功p指向查到的樹結(jié)點(diǎn)，不成功p指向?yàn)镹ULL）完成程序中的空格typedef struct Bnode Int key;struct Bnode *1汛struct Bnode ight; Bnode;-Bnode *BSearch(Bnode *bt, Int k)r于按收二叉排序閔的1艮結(jié)點(diǎn)的指針，k用以挎收吏直我的關(guān)鍵字駕 Bnode *p;lt(bt= ?NULL v )returnPebt;whlle(p->keyi= k v)i(：(lf(k<p->key)p=p->left v ；else： p=p->rightlf(p=NULL) break;retum( p v ;：題目22以下程序是折半插入排序的算法設(shè)待排序的記錄序列存放在al,-an中，以a0作為輔助工作單元，程序是要把a(bǔ)i插入到已經(jīng)有序的序列void binsort (NODE a JJnt n)irit x j jgkmfor (1=2 ; l<= n v ；I-H-)咐潮(rn (stJ)/2 vif( x<amakey)j=m-1 yelses=m+1 v)for (k1;k>=j+1;k-)a|k+i| 力=ak；at|+1=aDi)三、綜合題(每小題8分，共40分)題目23(1 )設(shè)查找表為27,29,55.68)畫出對(duì)上述直詼進(jìn)行t斤半查找所對(duì)應(yīng)的判定樹，為了成功查 找到元素M,需要依次與元素 危# V進(jìn)行比較.A. 23.10.1.14日.23,29,27.14C.23JD.11.14 0.23.29,55,14(2)在等柢率條件F 成功查找的平均比較次數(shù)為,A 24/9B 25/9C.3D.2 5題目24(1 )-組記錄的關(guān)鍵字序列為(47.80,57,39,41 .46),利用坷非序的方:曜立的初始堆為B / (堆頂元素是剽沅素，采用捌的形式建堆). , . * . A. 39,41.57.80.47,46B.39.41,45.80,47.57C. 39.47,46,80,41,57D.39.41,57,80,46.47(.2)輸出堆J頁j謙后,調(diào)饕后的堆為A = 八 * A.41.476,80,578.41.57.46,60.47C 41.57.80.47,46D .41.90,46,47,57題目251)對(duì)關(guān)裱字序列(56,51 71,54,46 J06),利用快速排序，以第一4關(guān)鍵字為分劇元親.經(jīng)過T欠劃分后結(jié)巢 為條圳“；A. 46,51.56,54,7106.C. 46,51.54,56,71,1060,56,51.54/671.106D. 56.51,46,54,71.106(2) 一組記錄的美襟字序列為(60.47.00.57 . 39.41 t 46.30 ).利用歸井排序的方法甕過(2.2)歸并的 暗果序列為|A(3S 57、60, 00.47.39.41.46 )B. (47. 60, 57. 80, 30,39.41；46 )0,(41.57. 60. 80. 30.39.47,46 )0, (47,57. 60, 80, 30,39,41.46 )題目26(1)對(duì)關(guān)鍵字序列(36,59,46,28,30,74)采用快激E序以第f 關(guān)鍵字為分劇元素,經(jīng)過一次劃分后的免果 序列為0 = VA.30,28,46,36,69,7432& 30 代6,46 . 69；, 74C. 28, 30.4 , 36,69 , 74 D. 30,28,36,46.69 , 74 用冒泡法對(duì)上述序列排序，經(jīng)兩翅冒湖腌早序列為A V .A 3&28.3。,46.69,74.C. 38.36,30.46,69,74B. 36,46,28.20.6974D.28,36M30l46r69l74題目27(1 ) 一組記錄的湘t字字列為做5,40.65,43 35 95寫出利用快速排序的方法,以第T記錄為基街導(dǎo)到的TSSU分的結(jié)果為 GS 9 ；A. 35 40 65 45 35 95(B. 3540 65 4345 951C. 3540 4345 65 95D. 35 40 4543 65 95（2 ）對(duì)上述序利用直控插入排字.逐次插入過程中，共進(jìn)行了 口=力：欠元素間的比較.A. 8 B； 11C D:10