安陽工學(xué)院軟件工程專業(yè)大二2017-2018數(shù)據(jù)結(jié)構(gòu)與算法模擬試題七

1、安陽工學(xué)院軟件工程專業(yè)大二2017-2018數(shù)據(jù)結(jié)構(gòu)與算法模擬試題七您的姓名： 填空題 *_1.以下英文字符串中是回文字符串的是（）。 單選題 *A: aabbaa(正確答案)B: aabbccddC: ABCABCD: AABBB2.數(shù)據(jù)結(jié)構(gòu)與算法內(nèi)，折半查找的時(shí)間復(fù)雜度是（）。 單選題 *A: O(1)B: O(log2n)(正確答案)C: O(n*n)D: O(n)3.棧是操作受限的線性表，不能插入、刪除的一端稱為（）。 單選題 *A: 棧頂B: 棧底(正確答案)C: 棧中D: 以上都不對4.表達(dá)式求值算法中，當(dāng)某運(yùn)算符優(yōu)先級(jí)低于棧頂符號(hào)的優(yōu)先級(jí)時(shí)，該運(yùn)算符（）。 單選題 *A: 不能進(jìn)

2、棧(正確答案)B: 可以進(jìn)棧C: 進(jìn)?；蛘卟贿M(jìn)棧都可以D: 都不對5.線性結(jié)構(gòu)中，無需為表中的元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間是（）的優(yōu)點(diǎn)。 單選題 *A: 順序表(正確答案)B: 鏈表C: 結(jié)構(gòu)體D: 指針6.線性表n個(gè)元素采用順序表存儲(chǔ)，在第i個(gè)位置刪除需要移動(dòng)（）個(gè)元素,其時(shí)間復(fù)雜度是(B)。 單選題 *A: n-i+1 O(n)B: n-i O(n)(正確答案)C: n-i O(1)D: (n-1)/2 O(1)7.線性結(jié)構(gòu)中，線性表采用鏈?zhǔn)酱鎯?chǔ)的好處是（）。 單選題 *A: 可以隨機(jī)訪問任何一個(gè)元素B: 元素都存在一片連續(xù)的存儲(chǔ)空間C: 無需預(yù)估存儲(chǔ)空間的大小(正確答案)D:

3、插入刪除需要移動(dòng)大量元素8.以下屬于哈希函數(shù)的構(gòu)造方法的是（）。 單選題 *A: 直接定址法(正確答案)B: 哈希再散列法C: 線性探測再散列法D: 二次探測再散列法9.下列那個(gè)是直接遞歸形式函數(shù)（）。 單選題 *A: void tell_stroy( ) tell_stroy(); (正確答案)B: void tell_stroy( ) void tell_stroy(); C: void tell_stroy( ) stroy(); D: void tell_stroy( ) tell(); 10.如孫子算經(jīng)中描述的雞兔同籠問題之窮舉算法的時(shí)間復(fù)雜度是（）。 單選題 *A: O(n)B:

4、O(n*n)(正確答案)C: O(nlog2n)D: O(1)11.以下英文字符串中是回文字符串的應(yīng)該是（）。 單選題 *A: 123321(正確答案)B: 11223311C: 123213D: 12312312.在一個(gè)單層循環(huán)中的循環(huán)體某處想停止本次循環(huán)，繼續(xù)下一次循環(huán)，應(yīng)在該處使用（）語句。 單選題 *A: break語句B: return語句C: continue語句(正確答案)D: exit(0)語句13.雞與兔共有35只，腳共94只，問雞有（）只。 單選題 *A: 23(正確答案)B: 12C: 22D: 1314.一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（

5、）。 單選題 *A: CABDEFGB: ABCDEFG(正確答案)C: DACEFBGD: ADCFEG15.關(guān)于二叉樹樹，某完全二叉樹按層次編號(hào)后，某結(jié)點(diǎn)是i，若有左孩子，則左孩子的編號(hào)是（）。 單選題 *A: 2i(正確答案)B: 2i+1C: 2i-1D: i/216.假定有k個(gè)關(guān)鍵字互為同義詞，若用線性探測法把這k個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行多少次探測？（）。 單選題 *A: k-1次B: k次C: k+1次D: k(k+1)/2次(正確答案)17.n個(gè)盤子的漢諾塔問題，移動(dòng)步數(shù)是（）。 單選題 *A: 2的n次冪減1(正確答案)B: 2*n-1C: 2*n+1D: log2n1

6、8.字符串處理函數(shù)是字符串連接的是（）。 單選題 *A: strcat(正確答案)B: strcpyC: strcmpD: strlen19.若有說明:int a34;，則對a數(shù)組元素的非法引用是：（）。 單選題 *A: a02*1B: a13C: a4-20D: a04(正確答案)20.數(shù)據(jù)結(jié)構(gòu)與算法內(nèi)，改進(jìn)的冒泡排序的任一趟排序過程中，如果沒有發(fā)生（），則說明已經(jīng)有序；排序完畢。 單選題 *A: 數(shù)據(jù)交換(正確答案)B: 數(shù)據(jù)刪除C: 數(shù)據(jù)增加D: 都不對21.以下英文字符串中是回文字符串的應(yīng)該是（）。 單選題 *A: 123321(正確答案)B: 11223311C: 123213D:

7、12312322.數(shù)據(jù)結(jié)構(gòu)與算法內(nèi)，從時(shí)間復(fù)雜度的角度來看，快速排序的時(shí)間復(fù)雜度是（）。 單選題 *A: O(n*n)B: O(nlog2n)(正確答案)C: O(1)D: 都不對23.以下英文字符串中是回文字符串的是（）。 單選題 *A: aabbaa(正確答案)B: aabbccddC: ABCABCD: AABBB24.char s100="abc" 則執(zhí)行strcpy(s,strcat(s,"123");后s的結(jié)果是（）。 單選題 *A: abc123(正確答案)B: 123abcC: abcD: 12325.若有說明int a34;，則對a數(shù)組

8、元素的非法引用是（）。 單選題 *A: a02*1B: a13C: a4-20D: a04(正確答案)26.下列關(guān)于二叉排序樹中說法正確的是（）。 單選題 *A: 二叉排序樹的定義具有反復(fù)性B: 二叉排序樹的定義具有遞歸性(正確答案)C: 二叉排序樹的定義具有回溯性D: 二叉排序樹的定義具有反彈性27.冒泡排序最好的情況是，記錄完全有序，20個(gè)記錄待排序只需要比較（）次即可完成排序。 單選題 *A: 20B: 19(正確答案)C: 18D: 19028.哪種排序可能發(fā)生在最后一趟排序開始之前，所有記錄均不在其最終位置上（）。 單選題 *A: 直接插入排序(正確答案)B: 簡單選擇排序C: 冒泡

9、排序D: 快速排序29.直接插入排序的時(shí)間復(fù)雜度和折半查找的時(shí)間復(fù)雜度分別是（）。 單選題 *A: O(n*n)和O(log2n)(正確答案)B: O(n*n)和O(n)C: O(1)和)O(n)D: O(n)和O(1)30.以下屬于哈希函數(shù)的構(gòu)造方法的是（）。 單選題 *A: 直接定址法(正確答案)B: 哈希再散列法C: 線性探測再散列法D: 二次探測再散列法31.隊(duì)列具有先進(jìn)先出的特性，那么入隊(duì)的O，P，Q順序的三個(gè)元素，出隊(duì)順序是（）。 單選題 *A: O，P，Q(正確答案)B: O，Q，PC: Q，P，OD: O，Q，P32.單鏈表中刪除p指針指向結(jié)點(diǎn)的后繼(假設(shè)存在)的語句序列正確的

10、是（）。 單選題 *A: p->next=p->next;B: p->next=p->next->next;(正確答案)C: p->next=p;D: p=p->next;33.在樹的概念中，樹的某結(jié)點(diǎn)的直接后繼稱為該結(jié)點(diǎn)的 （）。 單選題 *A: 孩子(正確答案)B: 雙親C: 子孫D: 祖先34.下列選項(xiàng)中關(guān)于二叉樹先序遍歷的順序說法正確的是（）。 單選題 *A: 左子樹 根結(jié)點(diǎn) 右子樹B: 根結(jié)點(diǎn) 左子樹 右子樹(正確答案)C: 左子樹 右子樹 根結(jié)點(diǎn)D: 無正確答案35.一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（）。 單

11、選題 *A: CABDEFGB: ABCDEFG(正確答案)C: DACEFBGD: ADCFEG36.度為0的結(jié)點(diǎn)又稱為（） 。 單選題 *A: 葉子(正確答案)B: 根結(jié)點(diǎn)C: 分支結(jié)點(diǎn)D: 內(nèi)部結(jié)點(diǎn)37.在隊(duì)列中能插入的一端稱為（）。 單選題 *A: 隊(duì)頭B: 隊(duì)尾(正確答案)C: 棧頂D: 棧底38.有關(guān)函數(shù)，下面描述正確的是（）。 *A: 定義函數(shù)時(shí)如果在函數(shù)名前加void,表示該函數(shù)沒有返回值(正確答案)B: 函數(shù)的值只能通過return語句返回主調(diào)函數(shù)(正確答案)C: 定義函數(shù)時(shí)函數(shù)名可以定義fun。(正確答案)D: 從參數(shù)角度看函數(shù)可分為庫函數(shù)和用戶定義函數(shù)39.關(guān)于冒泡排序的

12、比較次數(shù)和排序趟數(shù)描述正確的是（）。 *A: N個(gè)記錄最多N-1趟排序即可完成(正確答案)B: N個(gè)記錄最少比較N-1次，可完成排序，這是記錄完全有序的情況(正確答案)C: N個(gè)記錄最多比較N*(N-1)/2次可完成排序，這是記錄完全逆序的情況。(正確答案)D: 在一趟排序中若無記錄交換，就會(huì)停止排序。(正確答案)40.在C語言中，系統(tǒng)函數(shù)strcmp的返回值類型不是（）。 *A: intB: char(正確答案)C: char*(正確答案)D: float(正確答案)41.荷蘭國旗的算法使用的到的技術(shù)有（）。 *A: 循環(huán)(正確答案)B: 分支判斷(正確答案)C: 一維數(shù)組(正確答案)D:

13、循環(huán)嵌套42.樹的葉子結(jié)點(diǎn)描述正確的是（）。 *A: 葉子結(jié)點(diǎn)的度為0(正確答案)B: 葉子結(jié)點(diǎn)又稱終端結(jié)點(diǎn)(正確答案)C: 葉子結(jié)點(diǎn)一定不是內(nèi)部結(jié)點(diǎn)(正確答案)D: 葉子結(jié)點(diǎn)可能是分支結(jié)點(diǎn)43.下列排序中是穩(wěn)定排序的是（）。 *A: 希爾排序B: 快速排序C: 直接插入排序(正確答案)D: 冒泡排序(正確答案)44.以下是回文字符串的是（）。 *A: aba(正確答案)B: 11811(正確答案)C: abcabcD: xyzyx(正確答案)45.動(dòng)態(tài)查找表：邊查找，邊改變集合中的元素，改變的方式可以是（）。 *A: 增加(正確答案)B: 刪除(正確答案)C: 交換D: 移動(dòng)46.漢諾塔問題

14、的求解方式不屬于以下哪類算法（）。 *A: 窮舉(正確答案)B: 分治(正確答案)C: 遞歸D: 迭代(正確答案)47.線性結(jié)構(gòu)之隊(duì)列的應(yīng)用包括哪些（）。 *A: 消息的緩存(正確答案)B: 操作系統(tǒng)的作業(yè)調(diào)度(正確答案)C: 離散事件的模擬(正確答案)D: 進(jìn)制轉(zhuǎn)換48.在下列結(jié)論中，正確的是（）。 *A: 只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0(正確答案)B: 二叉樹的度小于等于2(正確答案)C: 二叉樹的左右子樹不可任意交換(正確答案)D: 深度為K的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹(正確答案)49.今有雉(雞)兔同籠，上有三十五頭，下有九十四足。問雉兔各幾何？答案不正確的是（）。

15、 *A: 雞23兔12B: 雞12兔23(正確答案)C: 雞22兔13(正確答案)D: 雞13兔22(正確答案)50.關(guān)于二叉排序樹描述有誤的是（）。 *A: 二叉排序的右子樹上結(jié)點(diǎn)的關(guān)鍵字小于左子樹上的結(jié)點(diǎn)的關(guān)鍵字(正確答案)B: 二叉排序的左子樹上結(jié)點(diǎn)的關(guān)鍵字小于右子樹上的結(jié)點(diǎn)的關(guān)鍵字C: 二叉排序的根節(jié)點(diǎn)的關(guān)鍵大于右子樹上結(jié)點(diǎn)的關(guān)鍵字(正確答案)D: 二叉排序的根節(jié)點(diǎn)的關(guān)鍵大于左子樹上結(jié)點(diǎn)的關(guān)鍵字51.下列關(guān)于查找表描述正確的是（）。 *A: 查找表分為靜態(tài)查找表和動(dòng)態(tài)查找表(正確答案)B: 動(dòng)態(tài)查找表邊查找，邊改變集合內(nèi)的元素(正確答案)C: 靜態(tài)查找表只查找不改變集合中的元素(正確答

16、案)D: 其它選項(xiàng)說法都正確(正確答案)52.回文字符串的判斷可以使用的方法有（）。 *A: 遞歸方式(正確答案)B: 非遞歸方式利用循環(huán)解決(正確答案)C: 非遞歸方式用系統(tǒng)函數(shù)解決(正確答案)D: 以上答案都正確(正確答案)53.今有雉(雞)兔同籠，上有三十五頭，下有九十四足。問雉兔各幾何？答案不正確的是（）。 *A: 雞23兔12B: 雞12兔23(正確答案)C: 雞22兔13(正確答案)D: 雞13兔22(正確答案)54時(shí)間復(fù)雜度是O(n*n)的排序是（）。 *A: 簡單選擇排序(正確答案)B: 冒泡排序(正確答案)C: 直接插入排序(正確答案)D: 快速排序55.完全二叉樹中，結(jié)點(diǎn)個(gè)

17、數(shù)為n，則編號(hào)最大的分支結(jié)點(diǎn)的編號(hào)不可能為（）。 *A: n/2向下取整B: n/2向下取整+1(正確答案)C: n/2向下取整+2(正確答案)D: n/2向下取整-1(正確答案)56.已知一個(gè)棧入棧順序是1,2,3，入的過程可以出棧，則是正確出棧的順序是（）。 *A: 1,2,3(正確答案)B: 3,2,1(正確答案)C: 2,1,3(正確答案)D: 1,3,2(正確答案)57. 二叉樹的先序序列是：ABDCEF，中序序列是：ADBECF，則后序序列不可能是（）。 *A: DFECBA(正確答案)B: EFDCBA(正確答案)C: DEFCBAD: DFCEBA(正確答案)58.關(guān)于樹的概念

18、說法正確的是（）。 *A: 樹可以為空樹(正確答案)B: 樹的定義具有遞歸性(正確答案)C: 樹中若存在根結(jié)點(diǎn)，則有且只能有一個(gè)。(正確答案)D: 樹的結(jié)點(diǎn)若大于2個(gè)，則除了根結(jié)點(diǎn)，其余結(jié)點(diǎn)分為m個(gè)互不相交的子集，每個(gè)子集也是一顆樹(正確答案)59.數(shù)據(jù)結(jié)構(gòu)與算法內(nèi)，今有雉(雞)兔同籠，上有三十五頭，下有九十四足。問雉兔各幾何答案不正確的是（）。 *A: 雞23兔12B: 雞12兔23(正確答案)C: 雞22兔13(正確答案)D: 雞13兔22(正確答案)60.回文字符串存儲(chǔ)方式一般采用字符數(shù)組，則關(guān)于字符數(shù)組描述正確的是（）。 *A: 只能存放字符型數(shù)據(jù)(正確答案)B: 數(shù)組是定長的，定義后

19、不可改變(正確答案)C: 數(shù)組元素占有一片連續(xù)的存儲(chǔ)單元(正確答案)D: 數(shù)組元素可以存放不同類型的數(shù)據(jù)61.希爾排序的時(shí)間復(fù)雜度不可能是（）。 *A: O(n*n)(正確答案)B: O(nlog2n)(正確答案)C: O(n)(正確答案)D: O(n3/2)62.冒泡排序的改進(jìn)之處說法不對的是（）。 *A: 增加了比較的次數(shù)(正確答案)B: 增加了比較的趟數(shù)(正確答案)C: 盡可能的減少比較次數(shù)和趟數(shù)D: 一定會(huì)減少比較的次數(shù)和趟數(shù)(正確答案)63.以下的排序是內(nèi)排序的是（）。 *A: 希爾排序(正確答案)B: 快速排序(正確答案)C: 希爾排序(正確答案)D: 快速排序(正確答案)64.下

20、列排序中是穩(wěn)定排序的是（）。 *A: 希爾排序B: 快速排序C: 直接插入排序(正確答案)D: 冒泡排序(正確答案)65.排序是穩(wěn)定排序或不穩(wěn)排序的插入排序是（）。 *A: 希爾排序(正確答案)B: 直接插入排序(正確答案)C: 堆排序D: 快速排序66.關(guān)于二叉排序樹描述有誤的是（）。 *A: 二叉排序的右子樹上結(jié)點(diǎn)的關(guān)鍵字小于左子樹上的結(jié)點(diǎn)的關(guān)鍵字(正確答案)B: 二叉排序的左子樹上結(jié)點(diǎn)的關(guān)鍵字小于右子樹上的結(jié)點(diǎn)的關(guān)鍵字C: 二叉排序的根節(jié)點(diǎn)的關(guān)鍵大于右子樹上結(jié)點(diǎn)的關(guān)鍵字(正確答案)D: 二叉排序的根節(jié)點(diǎn)的關(guān)鍵大于左子樹上結(jié)點(diǎn)的關(guān)鍵字67.如有定義int a23;則數(shù)組a的最后一個(gè)元素為a12。 判斷題 *對(正確答案)錯(cuò)68.字