數(shù)據(jù)結(jié)構(gòu)C語言模擬試題及答案沒印27934

1、保持平常心，營造好環(huán)境，揚(yáng)起常笑臉，輕松迎高考。 數(shù)據(jù)結(jié)構(gòu)C語言模擬試題及答案數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)題一、選擇題1在數(shù)據(jù)結(jié)構(gòu)中從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為CA. 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2.數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指AA.數(shù)據(jù)的存儲結(jié)構(gòu)3.在數(shù)據(jù)結(jié)構(gòu)中B.數(shù)據(jù)結(jié)構(gòu)C.數(shù)據(jù)的邏輯結(jié)構(gòu)與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的A結(jié)構(gòu)D.數(shù)據(jù)元素之間的關(guān)系A(chǔ).邏輯B.存儲4.在存儲數(shù)據(jù)時(shí)通常不僅要存儲各數(shù)據(jù)元素的值 而且還要存儲CC.邏輯和存儲D.物理A.數(shù)據(jù)的處理方法C.數(shù)據(jù)元素之間的關(guān)系5.在決定選取何種存儲結(jié)構(gòu)時(shí) 般不考慮AB.數(shù)據(jù)元素的類型D.

2、數(shù)據(jù)的存儲方法A.C.各結(jié)點(diǎn)的值如何 對數(shù)據(jù)有哪些運(yùn)算B.結(jié)點(diǎn)個(gè)數(shù)的多少D.所用的編程語言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便6.以下說法正確的是A.B.C.D.7.數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位數(shù)據(jù)元素是數(shù)據(jù)的最小單位數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項(xiàng)的集合一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu) 算法分析的目的是C算法分析的兩個(gè)主要方面是A(1) A.找出數(shù)據(jù)結(jié)構(gòu)的合理性C.分析算法的效率以求改進(jìn)(2) A.空間復(fù)雜度和時(shí)間復(fù)雜度C.可讀性和文檔性&下面程序段的時(shí)間復(fù)雜度是B .研究算法中的輸入和輸出的關(guān)系 C .分析算法的易讀性和文檔性B.正確性和簡明性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性O(shè) (n2)s = 0;for ( I

3、 = 0; i v n; i + + )for (j = 0; j v n; j + + )s += Bij；sum = s ;9下面程序段的時(shí)間復(fù)雜度是O( n*m)for ( i = 0; i v n; i + + )for (j = 0; j v m; j + + )Aij= 0 ;10下面程序段的時(shí)間復(fù)雜度是O( log3n )i = 0 ;while (i v= n)i = i * 3;11在以下的敘述中正確的是 BA. 線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B. 二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C. 棧的操作方式是先進(jìn)先出D. 隊(duì)列的操作方式是先進(jìn)后出12.通常要求同一邏輯結(jié)構(gòu)中

4、的所有數(shù)據(jù)元素具有相同的特性 這意味著 BA. 數(shù)據(jù)元素具有同一特點(diǎn)B. 不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同而且對應(yīng)的數(shù)據(jù)項(xiàng)的類型要一致C. 每個(gè)數(shù)據(jù)元素都一樣D. 數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等13鏈表不具備的特點(diǎn)是AA.可隨機(jī)訪問任一結(jié)點(diǎn)C.不必事先估計(jì)存儲空間 14不帶頭結(jié)點(diǎn)的單鏈表B. 插入刪除不需要移動(dòng)元素D. 所需空間與其長度成正比 head 為空的判定條件是 An ext = NULLC. head next = headD head != NULL15帶頭結(jié)點(diǎn)的單鏈表head 為空的判定條件是 Bn ext = NULLC. head next = headD head

5、 != NULL16. 若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn) 則采用D 存儲方式最節(jié)省運(yùn)算時(shí)間A. 單鏈表B 給出表頭指針的單循環(huán)鏈表C.雙鏈表 D 帶頭結(jié)點(diǎn)的雙循環(huán)鏈表17. 需要分配較大空間 插入和刪除不需要移動(dòng)元素的線性表 其存儲結(jié)構(gòu)是 BA. 單鏈表B 靜態(tài)鏈表C.線性鏈表D 順序存儲結(jié)構(gòu)18. 非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足 CA. p next = NULLB. p = NULLC. p next = headD . p = head19. 在循環(huán)雙鏈表的p所指的結(jié)點(diǎn)之前插入 s所指結(jié)點(diǎn)的操作是DApprior priorBppr

6、ior priorCsprior next = sDsprior prior = s20如果最常用的操作是取第i 個(gè)結(jié)點(diǎn)及其前驅(qū)則采用 D 存儲方式最節(jié)省時(shí)間A. 單鏈表B 雙鏈表C.單循環(huán)鏈表D.順序表21在一個(gè)具有 n 個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度 是 BAO（1）BO（n）CO（n2）DO （ nlog2n ）22在一個(gè)長度為 n（ n 1 ）的單鏈表上設(shè)有頭和尾兩個(gè)指針 執(zhí)行 B 操作與鏈表的長度有關(guān)A. 刪除單鏈表中的第一個(gè)元素B. 刪除單鏈表中的最后一個(gè)元素C. 在單鏈表第一個(gè)元素前插入一個(gè)新元素D. 在單鏈表最后一個(gè)元素后插入一個(gè)新元素 23與單鏈

7、表相比雙鏈表的優(yōu)點(diǎn)之一是 DA. 插入、刪除操作更簡單B. 可以進(jìn)行隨機(jī)訪問C. 可以省略表頭指針或表尾指針D. 順序訪問相鄰結(jié)點(diǎn)更靈活24如果對線性表的操作只有兩種 即刪除第一個(gè)元素 在最后一個(gè)元素的后面插入新元素 則最好使用 BA. 只有表頭指針沒有表尾指針的循環(huán)單鏈表B. 只有表尾指針沒有表頭指針的循環(huán)單鏈表C. 非循環(huán)雙鏈表D. 循環(huán)雙鏈表25. 在長度為n的順序表的第i個(gè)位置上插入一個(gè)元素(K i n+ 1)元素的移動(dòng)次數(shù)為： AA. n - i 1B. n - iC. iD. i - 126. 對于只在表的首、尾兩端進(jìn)行插入操作的線性表宜采用的存儲結(jié)構(gòu)為 CA.順序表B.用頭指針表

8、示的循環(huán)單鏈表C.用尾指針表示的循環(huán)單鏈表D.單鏈表27下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)? CA插入運(yùn)算方便B可方便地用于各種邏輯結(jié)構(gòu)的存儲表示C存儲密度大D刪除運(yùn)算方便28下面關(guān)于線性表的敘述中錯(cuò)誤的是哪一個(gè) ? BA線性表采用順序存儲必須占用一片連續(xù)的存儲單元B線性表采用順序存儲 便于進(jìn)行插入和刪除操作C線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲單元D線性表采用鏈?zhǔn)酱鎯?便于進(jìn)行插入和刪除操作29線性表是具有 n 個(gè) B 的有限序列D.表元素A.字符 B.數(shù)據(jù)元素C .數(shù)據(jù)項(xiàng)30在 n 個(gè)結(jié)點(diǎn)的線性表的數(shù)組實(shí)現(xiàn)中算法的時(shí)間復(fù)雜度是 O( 1)的操作是AA. 訪問第i (1v= i v= n)個(gè)

9、結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(1v i = n)B. 在第i (1 = i = n)個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)C. 刪除第i (1= i n ext = p n ext = p n ext = s;C. p n ext = s next = s next ; p next = s36. 線性表的順序存儲結(jié)構(gòu)是一種AA.隨機(jī)存取的存儲結(jié)構(gòu)C.索引存取的存儲結(jié)構(gòu)37. 棧的特點(diǎn)是 B 隊(duì)列的特點(diǎn)是 AB. 順序存取的存儲結(jié)構(gòu)D. Hash存取的存儲結(jié)構(gòu)A.先進(jìn)先出B .先進(jìn)后出38棧和隊(duì)列的共同點(diǎn)是CA都是先進(jìn)后出B .都是先進(jìn)先出C. 只允許在端點(diǎn)處插入和刪除元素D .沒有共同點(diǎn)39一個(gè)棧的進(jìn)棧序列

10、是abcde則棧的不可能的輸出序列是 CA edcbaB decbaC dceabD abcde40設(shè)有一個(gè)棧元素依次進(jìn)棧的順序?yàn)锳、 B、 C、 D、 E下列 C 是不可能的出棧序列AABCDE BBCDEACEABCDDEDCBA41 以下 B 不是隊(duì)列的基本運(yùn)算 ?A.從隊(duì)尾插入一個(gè)新元素B.從隊(duì)列中刪除第i個(gè)元素C.判斷一個(gè)隊(duì)列是否為空D.讀取隊(duì)頭元素的值42若已知一個(gè)棧的進(jìn)棧序列是13n其輸出序列為 p1p2p3 pn若 pl = n則 pi 為 CA.43.i B . n i C . n i 1 D .不確定為空的條件是 B判定一個(gè)順序棧 st （最多元素為MaxSize )A.s

11、t top ！top= 1C.st top ！top= MaxSize44.判定一個(gè)順序棧 st （最多元素為MaxSize )為滿的條件是 DA. st top ! top = 1C. st top ！top = MaxSize45. 一個(gè)隊(duì)列的入隊(duì)序列是 1 2則隊(duì)列的輸出序列是 BA.4321B.1234C.1432D.346. 判定一個(gè)循環(huán)隊(duì)列qu （最多元素為 MaxSize）為空的條件是 CA. qu rear - qu rear - qu front 1 = MaxSizeC. qufront 147. 在循環(huán)隊(duì)列中若 front 與 rear 分別表示對頭元素和隊(duì)尾元素的位置

12、則判斷循環(huán)隊(duì)列空的條件是 CD . frontA. front = rear + 1 B . rear = front + 1C . front = rear=048. 向一個(gè)棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)點(diǎn)時(shí)應(yīng)執(zhí)行 D 操作Ahn ext = h ;Csn ext = hn ext = s ;49輸入序列為 ABC可以變?yōu)镃BA時(shí) 經(jīng)過的棧操作為 BA. pushpoppushpoppushpop B. pushpushpushpoppoppopC. pushpushpoppoppushpopD. pushpoppushpushpoppop 50若棧采用順序存儲方式存儲 現(xiàn)

13、兩棧共享空間 V1 m top1 、 top2 分別代表第 1 和第 2個(gè)棧的棧頂 棧 1 的底在 V1 棧 2 的底在 Vm 則棧滿的條件是 BA. |top2 top1|= 0 B . top1 + 1 = top2 C . top1 + top2D. top1 = top251 設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號是否配對出現(xiàn)的算法采用 D 數(shù)據(jù)結(jié)構(gòu)最佳=mA.線性表的順序存儲結(jié)構(gòu)B .隊(duì)列52允許對隊(duì)列進(jìn)行的操作有 DC .線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)D.棧A.對隊(duì)列中的元素排序C.在隊(duì)頭元素之前插入元素53對于循環(huán)隊(duì)列DB.取出最近進(jìn)隊(duì)的元素D.刪除隊(duì)頭元素A.無法判斷隊(duì)列是否為空B 無法判斷隊(duì)列

14、是否為滿C.隊(duì)列不可能滿D 以上說法都不對54若用一個(gè)大小為6 的數(shù)值來實(shí)現(xiàn)循環(huán)隊(duì)列且當(dāng)前 rear 和 front 的值分別為 0 和 3 當(dāng)從隊(duì)列中刪除一個(gè)元素 再加入兩個(gè)元素后rear 和 front 的值分別為 BA. 1 和 5 B . 2 和 4 C. 4 和 2D. 5 和 155隊(duì)列的 先進(jìn)先出 特性是指 DA. 最早插入隊(duì)列中的元素總是最后被刪除B. 當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)總是插入操作優(yōu)先C. 每當(dāng)有刪除操作時(shí) 總是要先做一次插入操作D. 每次從隊(duì)列中刪除的總是最早插入的元素 56和順序棧相比鏈棧有一個(gè)比較明顯的優(yōu)勢是 AA.通常不會出現(xiàn)棧滿的情況B .通常不會出現(xiàn)棧空的

15、情況C 插入操作更容易實(shí)現(xiàn)D 刪除操作更容易實(shí)現(xiàn)57 用不帶頭結(jié)點(diǎn)的單鏈表存儲隊(duì)列其頭指針指向隊(duì)頭結(jié)點(diǎn) 尾指針指向隊(duì)尾結(jié)點(diǎn) 則在進(jìn)行出隊(duì)操作時(shí) CB.僅修改隊(duì)尾指針D.隊(duì)頭、隊(duì)尾指針都要修改A.僅修改隊(duì)頭指針C.隊(duì)頭、隊(duì)尾指針都可能要修改58. 若串 S=software其子串的數(shù)目是 BA. 8 B. 37 C . 36D. 959. 串的長度是指 BB .串中所含字符的個(gè)數(shù)D .串中所含非空格字符的個(gè)數(shù)A.串中所含不同字母的個(gè)數(shù)C.串中所含不同字符的個(gè)數(shù)60. 串是一種特殊的線性表其特殊性體現(xiàn)在 BA.可以順序存儲B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈?zhǔn)酱鎯.數(shù)據(jù)元素可以是多個(gè)字符61. 設(shè)有

16、兩個(gè)串 p 和 q求q在p中首次出現(xiàn)的位置的運(yùn)算稱為BA.連接 B .模式匹配62 .數(shù)組A中 每個(gè)元素的長度為 3 個(gè)字節(jié) 行下標(biāo) i 從 1到 8 列下標(biāo) j 從 1 到 10從首地址SA開始連續(xù)存放的存儲器內(nèi) 該數(shù)組按行存放 元素 A85 的起始地址為 CA SA141 B SA14463 .數(shù)組A中每個(gè)元素的長度為 3個(gè)字節(jié) 行下標(biāo) i 從 1到 8 列下標(biāo) j 從 1 到 10從首地址SA開始連續(xù)存放的存儲器內(nèi) 該數(shù)組按行存放 元素 A58 的起始地址為 CA SA141 B SA180 64若聲明一個(gè)浮點(diǎn)數(shù)數(shù)組如下： 假設(shè)該數(shù)組的內(nèi)存起始位置為 average15 的內(nèi)存地址是 C

17、C 求子串D求串長CSA 222D SA 225CSA 222D SA 225froat average=new float30;200A 214B 21565設(shè)二維數(shù)組 A1. m 1. n 按行存儲在數(shù)組 B 中 則二維數(shù)組元素 Ai j 在一維數(shù)組 B 中的下標(biāo)為 AC 260D 256An*（i 1）j B n* （i 1）j166 .有一個(gè)100 X 90的稀疏矩陣非 0 元素有 10 設(shè)每個(gè)整型數(shù)占 2 個(gè)字節(jié)C. i* （j 1）D. j*mi 1則用三元組表示該矩陣時(shí) 所需的字節(jié)數(shù)是 BA20B 66C18 00067數(shù)組 A0 . 4 1 . 35.7中含有的元素個(gè)數(shù)是AD.

18、 33A. 55 B . 45C. 36D. 1668.對矩陣進(jìn)行壓縮存儲是為了DA.方便運(yùn)算 B.方便存儲C.提高運(yùn)算速度D .減少存儲空間69設(shè)有一個(gè) 10 階的對稱矩陣 A采用壓縮存儲方式以行序?yàn)橹鞔鎯11 為第一個(gè)元素其存儲地址為 1每個(gè)元素占 1 個(gè)地址空間則 a85 的地址為 BA13 B 33C18D4070稀疏矩陣一般的壓縮存儲方式有兩種即 CB 三元組和散列D 散列和十字鏈表A. 二維數(shù)組和三維數(shù)組C.三元組和十字鏈表71 樹最適合用來表示CB.無序數(shù)據(jù)元素D.元素之間無聯(lián)系的數(shù)據(jù)A.有序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù) 72深度為 5 的二叉樹至多有 C 個(gè)結(jié)點(diǎn)

19、A 16 B 32 C 31C 1073對一個(gè)滿二叉樹m個(gè)葉子n 個(gè)結(jié)點(diǎn) 深度為 h則 DA. n = h + m B h + m = 2n C m = h 1Dn = 2h 174任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對次序AA.不發(fā)生改變B .發(fā)生改變C.不能確定D .以上都不對75.在線索化樹中每個(gè)結(jié)點(diǎn)必須設(shè)置一個(gè)標(biāo)志來說明它的左、右鏈指向的是樹結(jié)構(gòu)信息 還是線索化信息 若 0 標(biāo)識樹結(jié)構(gòu)信息1 標(biāo)識線索 對應(yīng)葉結(jié)點(diǎn)的左右鏈域 應(yīng)標(biāo)識為 _ D _A. 00B . 01C. 10D. 1176.在下述論述中正確的是 D只有一個(gè)結(jié)點(diǎn)的二叉樹的度為 0;二叉樹的度為 2;二

20、叉樹的左右子樹可任意 交換；深度為K的順序二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹A.B.C .D .77設(shè)森林 F 對應(yīng)的二叉樹為B它有m個(gè)結(jié)點(diǎn)B 的根為 pp 的右子樹的結(jié)點(diǎn)個(gè)數(shù)為 n森林F中第一棵樹的結(jié)點(diǎn)的個(gè)數(shù)是AAmnBmn1C n1D.不能確定78.若一棵二叉樹具有 10 個(gè)度為 2 的結(jié)點(diǎn)5 個(gè)度為 1 的結(jié)點(diǎn) 則度為 0 的結(jié)點(diǎn)的個(gè)數(shù)是 BA. 9 B . 11 C . 15D.不能確定79具有 10個(gè)葉子結(jié)點(diǎn)的二叉樹中有 B 個(gè)度為 2的結(jié)點(diǎn)A8B9 C10 D1180在一個(gè)無向圖中 所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 C 倍A1/2 B 1C 2 D 481在一個(gè)有向圖中

21、所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 B 倍A1/2 B 1 C 2 D 4 82某二叉樹結(jié)點(diǎn)的中序序列為ABCDEFG后序序列為 BDCAFGE 則其左子樹中結(jié)點(diǎn)數(shù)目為： CA 3B2C4D583已知一算術(shù)表達(dá)式的中綴形式為AB *C-D/E后綴形式為 ABC *DE/- 其前綴形式為 D- A*BC/DEA-AB*C/DEB-AB*CD/EC - *ABC/DE84已知一個(gè)圖如圖所示若從頂點(diǎn) a 出發(fā)按深度搜索法進(jìn)行遍歷 則可能得到的一種頂點(diǎn)序列為 D_；按廣度搜索法進(jìn)行遍歷則可能得到的一種頂點(diǎn)序列為 _A_；A. abecdfB. ac e b dC. ae b c f dD. a

22、bA. abcedfB. abcefdC. aebcfdD. acfdeb_A按層遍歷_D按層遍歷A.先序遍歷B.中序遍歷C.后序遍歷D86.采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的A.先序遍歷B.中序遍歷C.后序遍歷D87.具有 n 個(gè)結(jié)點(diǎn)的連通圖至少有A條邊A.n 1B. nC. n （n1） /2 D . 2n88.廣義表（ a）a）的表頭是C表尾是 CA. aB（）C （ a）D（a）89.廣義表（a）的表頭是 C表尾是 BA. aB（）C （ a）D（a）90.順序查找法適合于存儲結(jié)構(gòu)為B的線性表85.采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的A 散列存儲 B 順序

23、存儲或鏈?zhǔn)酱鎯?C 壓縮存儲 D 索引存儲 91對線性表進(jìn)行折半查找時(shí)要求線性表必須 BA 以順序方式存儲 且結(jié)點(diǎn)按關(guān)鍵字有序排列C 以鏈?zhǔn)椒绞酱鎯?且結(jié)點(diǎn)按關(guān)鍵字有序排列92采用折半查找法查找長度為 每個(gè)元素的平均查找長度為 DB 以順序方式存儲D 以鏈?zhǔn)椒绞酱鎯 的線性表時(shí)A O（ n2）B O（ nlog2n ）C O（n）93有一個(gè)有序表為 13D O（ log2n ）123241456275778295100當(dāng)折半查找值為 82 的結(jié)點(diǎn)時(shí) C 次比較后查找成功A 11 B 5C 4 D 894二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值 這種

24、說法 BA 正確 B 錯(cuò)誤95. 下面關(guān)于B樹和B+樹的敘述中不正確的結(jié)論是 AB B樹和B+樹都能有效的支持隨D B樹和B+樹都可用于文件索引A B樹和B+樹都能有效的支持順序查找 機(jī)查找C B樹和B+樹都是平衡的多叉樹 結(jié)構(gòu)96. 以下說法錯(cuò)誤的是 BA. 散列法存儲的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲地址B. 散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息不包含指針C. 負(fù)載因子是散列表的一個(gè)重要參數(shù)它反映了散列表的飽滿程度D. 散列表的查找效率主要取決于散列表構(gòu)造時(shí)選取的散列函數(shù)和處理沖突的方法97. 查找效率最高的二叉排序樹是CA. 所有結(jié)點(diǎn)的左子樹都為空的二叉排序樹B. 所有結(jié)點(diǎn)的右子樹都為空

25、的二叉排序樹C. 平衡二叉樹D. 沒有左子樹的二叉排序樹98. 排序方法中 從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較 將其放入已排序序列的正確位置上的方法稱為 CA.希爾排序B冒泡排序 C 插入排序D選擇排序99. 在所有的排序方法中關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是DA.希爾排序B.冒泡排序C 直接插入排序D 直接選擇排序100. 堆是一種有用的數(shù)據(jù)結(jié)構(gòu) 下列關(guān)鍵碼序列 D 是一個(gè)堆A. 943153231672B. 945331721623C165323943172D 163123945372101堆排序是一種B 排序A.插入B.選擇C.交換D.歸并102 D 在鏈

26、表中進(jìn)行操作比在順序表中進(jìn)行操作效率高A.順序查找B.折半查找103直接選擇排序的時(shí)間復(fù)雜度為 n 為元素個(gè)數(shù)）A O（ n）B O（log2n ）C.分塊查找D插入DC O（ nlog2n ）D O（n2）二、填空題1 數(shù)據(jù)邏輯結(jié)構(gòu)包括 線性結(jié)構(gòu)、 樹形結(jié)構(gòu)和 圖狀結(jié)構(gòu)三種類型樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱 非線性結(jié)構(gòu)2 數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、 樹形結(jié)構(gòu)和 圖狀結(jié)構(gòu)4種3 在線性結(jié)構(gòu)中第一個(gè)結(jié)點(diǎn) 沒有 前驅(qū)結(jié)點(diǎn)其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn) 沒有 后續(xù)結(jié)點(diǎn) 其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)后續(xù)結(jié)點(diǎn)4 線性結(jié)構(gòu)中元素之間存在 一對一 關(guān)系 樹形結(jié)構(gòu)中元素之間存在 一對多 關(guān)

27、系 圖形結(jié)構(gòu)中元素之間存在 多對多 關(guān)系5在樹形結(jié)構(gòu)中樹根結(jié)點(diǎn)沒有 前驅(qū) 結(jié)點(diǎn) 其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有 后續(xù) 結(jié)點(diǎn) 其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以 任意多個(gè)6數(shù)據(jù)結(jié)構(gòu)的基本存儲方法是順序 、 鏈?zhǔn)?、 索引 和 散列 存儲7衡量一個(gè)算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和時(shí)間復(fù)雜度與 空間復(fù)雜度8評估一個(gè)算法的優(yōu)劣通常從 時(shí)間復(fù)雜度 和 空間復(fù)雜度 兩個(gè)方面考察9算法的 5 個(gè)重要特性是 有窮性 、 確定性 、 可行性 、輸入和輸出10在一個(gè)長度為 n 的順序表中刪除第 i 個(gè)元素時(shí) 需向前移動(dòng) n i 1 個(gè)元素11在單鏈表中 要?jiǎng)h除某一指定的結(jié)點(diǎn) 必須找到該結(jié)點(diǎn)的

28、 前驅(qū) 結(jié)點(diǎn)12在雙鏈表中 每個(gè)結(jié)點(diǎn)有兩個(gè)指針域 一個(gè)指向 前驅(qū) 結(jié)點(diǎn) 另一個(gè)指向 后繼結(jié)點(diǎn)13在順序表中插入或刪除一個(gè)數(shù)據(jù)元素 需要平均移動(dòng) n 個(gè)數(shù)據(jù)元素 移動(dòng)數(shù)據(jù)元素的個(gè)數(shù)與 位置 有關(guān)14當(dāng)線性表的元素總數(shù)基本穩(wěn)定 且很少進(jìn)行插入和刪除操作 但要求以最快的速度存取線性表的元素是 應(yīng)采用 順序 存儲結(jié)構(gòu)15根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù) 將線性鏈表分成 單鏈表 和 雙鏈表16順序存儲結(jié)構(gòu)是通過 下標(biāo) 表示元素之間的關(guān)系的； 鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過 指 針 表示元素之間的關(guān)系的17.帶頭結(jié)點(diǎn)的循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是L next next = L18 棧 是限定

29、僅在表尾進(jìn)行插入或刪除操作的線性表 其運(yùn)算遵循 后進(jìn)先出 的原則19空串是 零個(gè)字符的串 其長度等于 零 空白串是由一個(gè)或多個(gè)空格字符組成的串 其長度等于其包含的空格個(gè)數(shù)20組成串的數(shù)據(jù)元素只能是單個(gè)字符21一個(gè)字符串中 任意個(gè)連續(xù)字符構(gòu)成的部分 稱為該串的子串22子串 str在主串 datastructure 中的位置是 523. 二維數(shù)組M的每個(gè)元素是6個(gè)字符組成的串行下標(biāo) i 的范圍從 0 到 8列下標(biāo) j 的范圍從 1 到 10則存放M至少需要540個(gè)字節(jié)；M的第8列和第5行共占108個(gè)字節(jié)24. 稀疏矩陣一般的壓縮存儲方法有兩種即 三元組表 和 十字鏈表25. 廣義表( a)(b)c

30、)(d)的長度是3深度是 426. 在一棵二叉樹中度為零的結(jié)點(diǎn)的個(gè)數(shù)為 n0 度為 2 的結(jié)點(diǎn)的個(gè)數(shù)為 n2 則有n0=n2 127. 在有 n 個(gè)結(jié)點(diǎn)的二叉鏈表中 空鏈域的個(gè)數(shù)為 _n1_28. 棵有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有_2n1_個(gè)結(jié)點(diǎn)29. 深度為 5 的二叉樹至多有 31 個(gè)結(jié)點(diǎn)30. 若某二叉樹有 20 個(gè)葉子結(jié)點(diǎn)有 30 個(gè)結(jié)點(diǎn)僅有一個(gè)孩子則該二叉樹的總結(jié)點(diǎn)個(gè)數(shù)為 6931某二叉樹的前序遍歷序列是 abdgcefh 中序序列是 dgbaechf 其后序序列為 gdbehfca32線索二叉樹的左線索指向其 遍歷序列中的前驅(qū) 右線索指向其遍歷序列中的后繼33在各種查找方法中平均查找

31、長度與結(jié)點(diǎn)個(gè)數(shù) n 無關(guān)的查找方法是 散列查找法34在分塊索引查找方法中 首先查找 索引表 然后查找相應(yīng)的 塊表35一個(gè)無序序列可以通過構(gòu)造一棵二叉排序 樹而變成一個(gè)有序序列構(gòu)造樹的過程即為對無序序列進(jìn)行排序的過程36具有 10 個(gè)頂點(diǎn)的無向圖邊的總數(shù)最多為 _45_37. 已知圖G的鄰接表如圖所示其從頂點(diǎn) v1 出發(fā)的深度優(yōu)先搜索序列為 _v1v2v3v6v5v4_ 其從頂點(diǎn) v1 出發(fā)的廣度優(yōu)先搜索序列為 _v1v2v5v4v3v6_38. 索引是為了加快檢索速度而引進(jìn)的一種數(shù)據(jù)結(jié)構(gòu) 一個(gè)索引隸屬于某個(gè)數(shù)據(jù)記錄集 它由若干索引項(xiàng)組成索引項(xiàng)的結(jié)構(gòu)為 關(guān)鍵字 和 關(guān)鍵字對應(yīng)記錄的地址39. P

32、rim 算法生成一個(gè)最小生成樹每一步選擇都要滿足邊的總數(shù)不超過 n1當(dāng)前選擇的邊的權(quán)值是候選邊中最小的選中的邊加入樹中不產(chǎn)生回路 三項(xiàng)原則40. 在一棵m階B樹中除根結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)最多有 m 棵子樹最少有 m/2 棵子樹1 數(shù)據(jù)邏輯結(jié)構(gòu)包括 _線性結(jié)構(gòu) 、 _ 樹形結(jié)構(gòu) 和 _圖狀結(jié)構(gòu) 三種類型樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱 _ 非線性結(jié)構(gòu) 2在線性結(jié)構(gòu)中第一個(gè)結(jié)點(diǎn) _無 前驅(qū)結(jié)點(diǎn)其余每個(gè)結(jié)點(diǎn)有且只有 1_個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn) 無 后續(xù)結(jié)點(diǎn)其余每個(gè)結(jié)點(diǎn)有且只有 _1個(gè)后續(xù)結(jié)點(diǎn)4線性結(jié)構(gòu)中元素之間存在 _ 一個(gè)對一個(gè)的 關(guān)系樹形結(jié)構(gòu)中元素之間存在 _一個(gè)對多個(gè)的 關(guān)系圖形結(jié)構(gòu)中元素之間存在 _多個(gè)對

33、多個(gè)的 關(guān)系5在樹形結(jié)構(gòu)中 樹根結(jié)點(diǎn)沒有 _前驅(qū) 結(jié)點(diǎn)其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有_后續(xù) 結(jié)點(diǎn)其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以_任意多個(gè) 和6數(shù)據(jù)結(jié)構(gòu)的基本存儲方法是_散列 存儲_ 順序 _ 、 鏈?zhǔn)?_、 _ 索引7衡量一個(gè)算法的優(yōu)劣主要考慮_正確性 _、_可讀性 _、_健壯性和 _ 時(shí)間復(fù)雜度 與 _ 空間復(fù)雜度 8算法的 5 個(gè)重要特性是 _有窮性 、 _確定性 、 _可行性 、 _輸入和輸出 10在一個(gè)長度為 n 的順序表中刪除第 i 個(gè)元素時(shí)需向前移動(dòng) n-i-1 個(gè)元素11在單鏈表中要?jiǎng)h除某一指定的結(jié)點(diǎn)必須找到該結(jié)點(diǎn)的 前驅(qū) 結(jié)點(diǎn)12在雙鏈表中每個(gè)結(jié)點(diǎn)有兩個(gè)指針域一

34、個(gè)指向 _直接后續(xù) 結(jié)點(diǎn)另一個(gè)指向 _直接前驅(qū)結(jié)點(diǎn) 13在順序表中插入或刪除一個(gè)數(shù)據(jù)元素需要平均移動(dòng) n個(gè)數(shù)據(jù)元素移動(dòng)數(shù)據(jù)元素的個(gè)數(shù)與 _位置 有關(guān)14當(dāng)線性表的元素總數(shù)基本穩(wěn)定 且很少進(jìn)行插入和刪除操作 但要求以最快的速度存取線性表的元素是 應(yīng)采用 順序表 存儲結(jié)構(gòu)15根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)將線性鏈表分成 _單鏈表 和 _ 雙向鏈表 16順序存儲結(jié)構(gòu)是通過 _下標(biāo)過 指針 表示元素之間的關(guān)系的表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯Y(jié)構(gòu)是通17帶頭結(jié)點(diǎn)的循環(huán)鏈表 L 中只有一個(gè)元素結(jié)點(diǎn)的條件是18 _棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表其運(yùn)算遵循 _后進(jìn)先出 的原則L

35、-next-next=L三、判斷題1在決定選取何種存儲結(jié)構(gòu)時(shí) 一般不考慮各結(jié)點(diǎn)的值如何(V)2 抽象數(shù)據(jù)類型(ADT包括定義和實(shí)現(xiàn)兩方面 其中定義是獨(dú)立于實(shí)現(xiàn)的定義僅給出一個(gè)ADT的邏輯特性 不必考慮如何在計(jì)算機(jī)中實(shí)現(xiàn)(V)3抽象數(shù)據(jù)類型與計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)無關(guān)(V)4順序存儲方式插入和刪除時(shí)效率太低 因此它不如鏈?zhǔn)酱鎯Ψ绞胶?X )5線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí) 結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲空間可以是不連續(xù)的(X)6對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)(X)7順序存儲方式只能用于存儲線性結(jié)構(gòu)(X )8集合與線性表的區(qū)別在于是否按關(guān)鍵字排序(X)9線性表中每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼(X)10線性表就是順序存儲的表(X)11取線性表的第 i 個(gè)元素的時(shí)間同 i 的大小有關(guān)(X)12循環(huán)鏈表不是線性表(X)13鏈表是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表 進(jìn)行插入、刪除操作時(shí) 在鏈表中比在順序表中效率高(v )14雙向鏈表可隨機(jī)訪問任一結(jié)點(diǎn)(X )15在單鏈表中 給定任一結(jié)點(diǎn)的地址 p 則可用下述語句將新結(jié)點(diǎn)s插入結(jié)點(diǎn)p的后面：pnext ； (X ) 16隊(duì)列是一種插入和刪除操作分別在表的兩端進(jìn)行的線性表 是一種先進(jìn)后出的結(jié)構(gòu)(X)17 串是一種特殊的線性表 其特殊性體現(xiàn)在可