1、綜合練習(xí)一、單項(xiàng)選擇題1. 數(shù)據(jù)在計(jì)算機(jī)存儲器內(nèi)表示時(shí)，物理地址與邏輯地址不相同的，稱之為（C ）。 A.存儲結(jié)構(gòu)B.邏輯結(jié)構(gòu) C.鏈?zhǔn)酱鎯Y(jié)構(gòu)D.順序存儲結(jié)構(gòu)2. 設(shè)語句x+的時(shí)間是單位時(shí)間，則以下語句的時(shí)間復(fù)雜度為（ B ）。for(i=1; i<=n; i+) for(j=i; j<=n; j+) x+; A.O(1)B.O()C.O(n)D.O()3. 鏈?zhǔn)酱鎯Y(jié)構(gòu)的最大優(yōu)點(diǎn)是（ D ）。 A.便于隨機(jī)存取B.存儲密度高 C.無需預(yù)分配空間D.便于進(jìn)行插入和刪除操作 4. 假設(shè)在順序表a0,a1,an1中，每一個(gè)數(shù)據(jù)元素所占的存儲單元的數(shù)目為4，且第0個(gè)數(shù)據(jù)元素的存儲地址為

2、100，則第7個(gè)數(shù)據(jù)元素的存儲地址是（ D ）。 A.106 B. 107 C.124 D.1285. 在線性表中若經(jīng)常要存取第i個(gè)數(shù)據(jù)元素及其前趨，則宜采用（ A ）存儲方式。 A.順序表B. 帶頭結(jié)點(diǎn)的單鏈表 C.不帶頭結(jié)點(diǎn)的單鏈表D. 循環(huán)單鏈表6. 在鏈表中若經(jīng)常要?jiǎng)h除表中最后一個(gè)結(jié)點(diǎn)或在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)，則宜采用（ C ）存儲方式。 A.順序表B. 用頭指針標(biāo)識的循環(huán)單鏈表 C. 用尾指針標(biāo)識的循環(huán)單鏈表D. 雙向鏈表7. 在一個(gè)含有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)，使單鏈表仍然保持有序的算法的時(shí)間復(fù)雜度是（ C ）。 O(1) B. O(log2n) C. O(n

3、) D. O(n2)8. 要將一個(gè)順序表a0,a1,an-1中第i個(gè)數(shù)據(jù)元素ai(0in-1)刪除，需要移動（ B ）個(gè)數(shù)據(jù)元素。 A.i B. n-i-1 C. n-i D. n-i+19. 在棧中存取數(shù)據(jù)的原則是（ B ）。 A.先進(jìn)先出 B. 先進(jìn)后出 C. 后進(jìn)后出 D. 沒有限制10. 若將整數(shù)1、2、3、4依次進(jìn)棧，則不可能得到的出棧序列是（ D ）。 A1234 B. 1324 C. 4321 D. 142311. 在鏈棧中，進(jìn)行出棧操作時(shí)（ B ）。 A需要判斷棧是否滿 B. 需要判斷棧是否為空 C. 需要判斷棧元素的類型 D. 無需對棧作任何差別12. 在順序棧中，若棧頂指針

4、top指向棧頂元素的存儲單元，且順序棧的最大容量是maxSize，則順序棧的判空條件是（B）。 Atop=0 B.top=-1 C. top=maxSize D.top=maxSize-113. 在順序棧中，若棧頂指針top指向棧頂元素的下一個(gè)存儲單元，且順序棧的最大容量是maxSize。則順序棧的判滿的條件是（C ）。 Atop=0 B.top=-1 C. top=maxSize D.top=maxSize-114. 在隊(duì)列中存取數(shù)據(jù)元素的原則是（ A ）。 A先進(jìn)先出 B. 先進(jìn)后出 C. 后進(jìn)后出 D. 沒有限制15. 在循環(huán)順序隊(duì)列中，假設(shè)以少用一個(gè)存儲單元的方法來區(qū)分隊(duì)列判滿和判空的

5、條件，front和rear分別為隊(duì)首和隊(duì)尾指針，它們分別指向隊(duì)首元素和隊(duì)尾元素的下一個(gè)存儲單元，隊(duì)列的最大存儲容量為maxSize，則隊(duì)列的判空條件是（ A ）。 Afront=rear B. front!=rear C. front=rear+1 D. front=(rear+1)% maxSize 16. 在循環(huán)順序隊(duì)列中，假設(shè)以少用一個(gè)存儲單元的方法來區(qū)分隊(duì)列判滿和判空的條件，front和rear分別為隊(duì)首和隊(duì)尾指針，它們分別指向隊(duì)首元素和隊(duì)尾元素的下一個(gè)存儲單元，隊(duì)列的最大存儲容量為maxSize，則隊(duì)列的判滿條件是（ D ）。 Afront=rear B. front!=rear C

6、. front=rear+1 D. front=(rear+1)% maxSize17. 在循環(huán)順序隊(duì)列中，假設(shè)以少用一個(gè)存儲單元的方法來區(qū)分隊(duì)列判滿和判空的條件，front和rear分別為隊(duì)首和隊(duì)尾指針，它們分別指向隊(duì)首元素和隊(duì)尾元素的下一個(gè)存儲單元，隊(duì)列的最大存儲容量為maxSize，則隊(duì)列的長度是（ C ）。 Arear-front B. rear-front+1 C. (rear-front+maxSize)%maxSize D. (rear-front+1)%maxSize18. 設(shè)長度為n的鏈隊(duì)列采用單循環(huán)鏈表加以表示，若只設(shè)一個(gè)頭指針指向隊(duì)首元素，則入隊(duì)操作的時(shí)間復(fù)雜度為（ B

7、）。 AO(1) BO(n) CO(log2n) DO(n2)19. 串的長度是指( A ) A. 串中包含的字符個(gè)數(shù) B. 串中包含的不同字符個(gè)數(shù) C. 串中除空格以外的字符個(gè)數(shù) D. 串中包含的不同字母個(gè)數(shù)20. 設(shè)有兩個(gè)串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（ C ） A求子串         B聯(lián)接            C模式匹配   

8、0;       D求串長21. 設(shè)有一個(gè)10階的對稱矩陣A，采用壓縮存儲方式，以行序?yàn)橹鬟M(jìn)行存儲，a11為第一元素，其存儲地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（ B ）。A. 13 B. 33 C. 18 D. 4022. 7. 有一個(gè)二維數(shù)組A1.6, 0.7 ，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲，存儲器按字節(jié)編址，那么這個(gè)數(shù)組占用的存儲空間大小是（ D ）個(gè)字節(jié)。 A. 48 B. 96 C. 252 D. 28823. 在哈夫曼樹中，任何一個(gè)結(jié)點(diǎn)它的度都是（ C ）。 A.0或1 B. 1或2 C. 0或2 D.

9、0或1或224. 對一棵深度為h的二叉樹，其結(jié)點(diǎn)的個(gè)數(shù)最多為（ D ）。 A.2h B. 2h-1 C. 2h-1 D. 2h-1 C. 只有一個(gè)根結(jié)點(diǎn) D. 任意一棵二叉樹25. 假設(shè)一棵二叉樹中度為1的結(jié)點(diǎn)個(gè)數(shù)為5，度為2的結(jié)點(diǎn)個(gè)數(shù)為3，則這棵二叉樹的葉結(jié)點(diǎn)的個(gè)數(shù)是（ C ） A2 B. 3 C. 4 D. 526. 若某棵二叉樹的先根遍歷序列為ABCDEF，中根遍歷序列為CBDAEF，則這棵二叉樹的后根遍歷序列為（ B ）。 A. FEDCBA B. CDBFEA C. CDBEFA D. DCBEFA27. 在有n個(gè)結(jié)點(diǎn)的二叉樹的二叉鏈表存儲結(jié)構(gòu)中有（ C ）個(gè)空的指針域。 An-1

10、B. n C. n+1 D. 028. 利用二叉鏈表存儲樹，則根結(jié)點(diǎn)的右指針是（ C ）。A 指向最左孩子 B指向最右孩子 C空 D非空29. 引入二叉線索樹的目的是（ A ）。A加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度 B為了能在二叉樹中方便的進(jìn)行插入與刪除C為了能方便的找到雙親 D使二叉樹的遍歷結(jié)果唯一30.設(shè)F是一個(gè)森林，B是由F變換得的二叉樹。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（ C）個(gè)。An1BnCn + 1Dn + 231.在一個(gè)有個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度之和為，則所有頂點(diǎn)的入度之和為（A）。 A.B.C.D.32.具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有（A）條邊才能確保是一

11、個(gè)連通圖。 A.5B.6C.7D.833.一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有（C）條邊。 A.B.C.D.34.n個(gè)頂點(diǎn)的連通圖用鄰接距陣表示時(shí)，該距陣至少有（ B ）個(gè)非零元素。An B2(n-1) Cn/2 Dn2 35.對某個(gè)無向圖的鄰接矩陣來說，下列敘述正確的是（A）。 A.第行上的非零元素個(gè)數(shù)和第列上的非零元素個(gè)數(shù)一定相等 B.矩陣中的非零元素個(gè)數(shù)等于圖中的邊數(shù) C.第行與第列上的非零元素的總數(shù)等于頂點(diǎn)的度數(shù) D.矩陣中非全零行的行數(shù)等于圖中的頂點(diǎn)數(shù) .32.任何一個(gè)無向連通圖的最小生成樹（B）。 A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在36.下面（ B ）方法可以判斷出一

12、個(gè)有向圖是否有環(huán)。 A 深度優(yōu)先遍歷 B拓?fù)渑判?C求最短路徑 D求關(guān)鍵路徑37.對線性表進(jìn)行二分查找時(shí)，要求線性表必須( B ) A.以順序方式存儲 B.以順序方式存儲，且結(jié)點(diǎn)按關(guān)鍵字值有序排列 C.以鏈接方式存儲 D.以鏈接方式存儲，且結(jié)點(diǎn)按關(guān)鍵字值有序排列38.用二分查找法查找具有n個(gè)結(jié)點(diǎn)的順序表時(shí)，查找每個(gè)結(jié)點(diǎn)的平均比較次數(shù)是( D ) A.O(n2) B.O(nlog2n) C.O(n) D.O(log2n)39.若有一個(gè)長度為64的有序表，現(xiàn)用二分查找方法查找某一記錄，則查找不成功，最多需要比較( B )次。 A.9 B.7 C.5 D.340.若結(jié)點(diǎn)的存儲地址與其關(guān)鍵字之間存在某

13、種映射關(guān)系，則稱這種存儲結(jié)構(gòu)為( D ) A.順序存儲結(jié)構(gòu) B.鏈?zhǔn)酱鎯Y(jié)構(gòu) C.索引存儲結(jié)構(gòu) D.散列存儲結(jié)構(gòu)41. 設(shè)哈希表長為14，哈希函數(shù)是H(key)=key%11，表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84共四個(gè)，現(xiàn)要將關(guān)鍵字為49的元素加到表中，用二次探測法解決沖突，則放入的位置是（ D ）。 A8 B3 C5 D9 42.下面給出的四種排序算法中，( B )是不穩(wěn)定的排序。 A插入排序   B堆排序    C二路歸并排序     D冒泡排序43.在下列排序算法中，哪一種算法的時(shí)間復(fù)雜度與初始排序序

14、列無關(guān)（ D ）。 A直接插入排序 B冒泡排序  C快速排序  D直接選擇排序44. 關(guān)鍵字序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中( C )的兩趟排序后的結(jié)果。A選擇排序    B.冒泡排序      C.插入排序    D.堆排序45.一組記錄的關(guān)鍵字為（46，79，56，38，40，84），則利用快速排序的方法，以第一個(gè)記錄為支點(diǎn)得到的一次劃分結(jié)果為（ C ）。 A(38,40,46,56,79,84)   B(40,38,46,79

15、,56,84)C(40,38,46,56,79,84)  D(40,38,46,84,56,79)46.在對一組關(guān)鍵字序列15，33,55，100，65，50，40，95，進(jìn)行直接插入排序時(shí)，把65插入，需要比較( A )次。 A. 2 B. 4 C. 6 D. 847.從待排序的序列中選出關(guān)鍵字值最大的記錄放到有序序列中，該排序方法稱為( B )。 A. 希爾排序 B. 直接選擇排序 C. 冒泡排序 D. 快速排序48.當(dāng)待排序序列基本有序時(shí)，以下排序方法中，( B )最不利于其優(yōu)勢的發(fā)揮。 A. 直接選擇排序 B. 快速排序 C.冒泡排序 D.直接插入排序49.在待排序序列局部有

16、序時(shí)，效率最高的排序算法是( B )。 A. 直接選擇排序 B. 直接插入排序 C. 快速排序 D.歸并排序50.數(shù)據(jù)表中有10000個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用( D )算法最節(jié)省時(shí)間。A冒泡排序 B快速排序 C簡單選擇排序 D堆排序二、填空題1. 一個(gè)串的任意連續(xù)字符組成的子序列稱為串的 子串 ，該串稱為 主串 。2. 若兩個(gè)串的長度相等且對應(yīng)位置上的字符也相等，則稱兩個(gè)串 相等 。3. 尋找子串在主串中的位置，稱為 模式匹配 。其中，子串又稱為 模式串 。4. 設(shè)數(shù)組A1.5,1.6的基地址為1000，每個(gè)元素占5個(gè)存儲單元，若以行序?yàn)橹餍蝽樞虼鎯Γ瑒t元素A5,5的

17、存儲地址為 1140 。5. 一個(gè)n×n的對稱矩陣，如果以相同的元素只存儲一次的原則進(jìn)行壓縮存儲，則其元素壓縮后所需的存儲容量為 n(n+1)/2 。6. 對矩陣壓縮的目的是為了 節(jié)省存儲空間 。7. 循環(huán)順序隊(duì)列是將順序隊(duì)列的存儲區(qū)域看成是一個(gè)首尾相連的環(huán)，首尾相連的狀態(tài)是通過數(shù)學(xué)上的 求模（或取余） 運(yùn)算來實(shí)現(xiàn)的。8. 一棵具有100個(gè)結(jié)點(diǎn)的完全二叉樹，其葉結(jié)點(diǎn)的個(gè)數(shù)為 50 。9. 以5，9，12，13，20，30為葉結(jié)點(diǎn)的權(quán)值所構(gòu)造的哈夫曼樹的帶權(quán)路徑長度是 217 。10. 有m個(gè)葉結(jié)點(diǎn)的哈夫曼樹中，結(jié)點(diǎn)的總數(shù)是 2m-1 。11. 若一棵完全二叉樹的第4層(根結(jié)點(diǎn)在第0層

18、)有7個(gè)結(jié)點(diǎn)，則這棵完全二叉樹的葉子結(jié)點(diǎn)總數(shù)是 11 。12. 在深度為k的完全二叉樹中至少有 k個(gè)結(jié)點(diǎn)，至多有 2k-1 個(gè)結(jié)點(diǎn)。13. 假定待查找記錄個(gè)數(shù)為n,則在等概率的情況下，順序查找在查找成功情況下的平均查找長度為 (n+1)/2 ；在查找失敗情況下的平均查找長度為 n+1 。14. 對線性表進(jìn)行二分查找時(shí)，要求線性表必須以順序方式存儲，且數(shù)據(jù)有序 。15. 分塊查找分為兩個(gè)階段，分別是確定待查元素所在的塊 和 在塊內(nèi)查找待查的元素。16. 哈希法存儲中，沖突指的是不同關(guān)鍵字值對應(yīng)到相同的存儲地址。17. 一棵二叉排序樹用中序遍歷輸出的信息是 遞增 序列。18. 哈希法存儲的基本思想是根據(jù) 關(guān)鍵字 來決定存儲地址。19. 若用表示圖中頂點(diǎn)數(shù)，則有條邊的無向圖稱為完全圖。20. 個(gè)頂點(diǎn)的連通無向圖至少有條邊，至多有條邊。21. 若有向圖的鄰接矩