大工14秋《數(shù)據(jù)結(jié)構(gòu)》在線作業(yè)3及答案

1、大工14秋數(shù)據(jù)結(jié)構(gòu)在線作業(yè)3試卷總分：100 測(cè)試時(shí)間：- 單選題 判斷題 一、單選題（共10道試題，共50分。）V 1.下列排序算法中（ ）不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上。 A. 快速排序B. shell排序C. 堆排序D. 冒泡排序滿分：5分2.一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（ ）。 A. (38,40,46,56,79,84)B. (40,38,46,79,56,84)C. (40,38,46,56,79,84)D. (40,38,46,84,56,79)滿分：5分3.將10個(gè)元素

2、散列到個(gè)單元的哈希表中，則（ ）產(chǎn)生沖突。 A. 一定會(huì)B. 一定不會(huì)C. 仍可能會(huì)D. 以上都不對(duì)滿分：5分4.快速排序方法在（ ）情況下最不利于發(fā)揮其長(zhǎng)處。 A. 要排序的數(shù)據(jù)量太大B. 要排序的數(shù)據(jù)中含有多個(gè)相同值C. 要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)D. 要排序的數(shù)據(jù)已基本有序滿分：5分5.若查找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，對(duì)成功的查找，其平均查找長(zhǎng)度為（ ）。 A. (n-1)/2B. n/2C. (n+1)/2D. n滿分：5分6.散列表的地址區(qū)間為0-17,散列函數(shù)為H(K)=K mod 17。采用線性探測(cè)法處理沖突，并將關(guān)鍵字序列26，

3、25，72，38，8，18，59依次存儲(chǔ)到散列表中。存放元素59需要搜索的次數(shù)是（ ）。 A. 2B. 3C. 4D. 5滿分：5分7.運(yùn)用直接插入排序方法對(duì)下面四個(gè)序列進(jìn)行從小到大排序，元素比較次數(shù)最少的是（ ）。 A. 90,69,80,46,21,40B. 40,21,46,69,90,80C. 90,80,69,46,40,21D. 21,40,46,69,80,90滿分：5分8.二分法查找，要求線性表一定是（ ）。 A. 順序存儲(chǔ)的無(wú)序表B. 鏈?zhǔn)酱鎯?chǔ)的無(wú)序表C. 順序存儲(chǔ)的有序表D. 鏈?zhǔn)酱鎯?chǔ)的有序表滿分：5分9.若要求排序是穩(wěn)定的，且關(guān)鍵字為實(shí)數(shù)，則在下列排序方法中應(yīng)選（ ）排序

4、為宜。 A. 直接插入B. 直接選擇C. 堆D. 快速滿分：5分10.采用簡(jiǎn)單選擇排序，比較次數(shù)與移動(dòng)次數(shù)分別為（ ）。 A. O（n）,O(logn)B. O(logn),0(n*n)C. 0(n*n),0(n)D. 0(nlogn),0(n)二、判斷題（共10道試題，共50分。）V 1.直接插入排序是不穩(wěn)定性排序法。（ ） A. 錯(cuò)誤B. 正確滿分：5分2.快速排序是穩(wěn)定的排序方法。（ ） A. 錯(cuò)誤B. 正確滿分：5分3.堆是完全二叉樹(shù)。（ ） A. 錯(cuò)誤B. 正確滿分：5分4.從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）一端的方法，稱為希爾排序。（ ） A. 錯(cuò)誤B. 正確滿分：5分5.合并排序是利用“合并”方法來(lái)進(jìn)行排序。合并是將兩個(gè)或多個(gè)有序表進(jìn)行合并，得到一個(gè)有序表。（ ） A. 錯(cuò)誤B. 正確滿分：5分6.存儲(chǔ)在磁帶上的順序文件的查找只能用順序查找。（ ） A. 錯(cuò)誤B. 正確滿分：5分7.散列文件的基本存儲(chǔ)單位是頁(yè)塊。（ ） A. 錯(cuò)誤B. 正確滿分：5分8.交換排序的基本思想是兩兩比較待排序記錄的排序碼，并交換不滿足順序要求的那些偶對(duì)，直到全部滿足順序要求為止。（ ） A. 錯(cuò)誤B. 正確滿分：5分9.用冒泡排序的方法對(duì)n個(gè)數(shù)據(jù)