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

1、生命太過短暫，今天放棄了明天不一定能得到。數(shù)據(jù)結(jié)構(gòu)C語言模擬試題及答案數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)題一、選擇題1在數(shù)據(jù)結(jié)構(gòu)中從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為 C A動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C線性結(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)B數(shù)據(jù)結(jié)構(gòu)C數(shù)據(jù)的邏輯結(jié)構(gòu) D數(shù)據(jù)元素之間的關(guān)系3在數(shù)據(jù)結(jié)構(gòu)中與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的 A 結(jié)構(gòu)A邏輯B存儲C邏輯和存儲D物理4在存儲數(shù)據(jù)時通常不僅要存儲各數(shù)據(jù)元素的值而且還要存儲 C A數(shù)據(jù)的處理方法B數(shù)據(jù)元素的類型C數(shù)據(jù)元素之間的關(guān)系D數(shù)據(jù)的存儲方法5在決定選取何種存儲結(jié)構(gòu)時一般不考慮 A A各結(jié)點(diǎn)的值

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

3、；9下面程序段的時間復(fù)雜度是O（n*m）for（ i 0； in； i）for（j0；jm；j）Aij 0；10下面程序段的時間復(fù)雜度是O（log3n）i 0；while（in）i i * 3；11在以下的敘述中正確的是 B A線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C棧的操作方式是先進(jìn)先出D隊(duì)列的操作方式是先進(jìn)后出12通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性這意味著B A數(shù)據(jù)元素具有同一特點(diǎn)B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個數(shù)要相同而且對應(yīng)的數(shù)據(jù)項(xiàng)的類型要一致C每個數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個數(shù)要相等13鏈表不具備的特點(diǎn)是A A可隨機(jī)訪

4、問任一結(jié)點(diǎn)B插入刪除不需要移動元素C不必事先估計(jì)存儲空間D所需空間與其長度成正比14不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是 Anext NULLCheadnext headD head！NULL15帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是 Bnext NULLCheadnext headD head！NULL16若某表最常用的操作是在最后一個結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)或刪除最后一個結(jié)點(diǎn)則采用D存儲方式最節(jié)省運(yùn)算時間A單鏈表 B給出表頭指針的單循環(huán)鏈表C雙鏈表 D帶頭結(jié)點(diǎn)的雙循環(huán)鏈表17需要分配較大空間插入和刪除不需要移動元素的線性表其存儲結(jié)構(gòu)是 B A單鏈表 B靜態(tài)鏈表C線性鏈表 D順序存儲結(jié)構(gòu)

5、18非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足C Apnext NULLBp NULLCpnext head Dp head19在循環(huán)雙鏈表的p所指的結(jié)點(diǎn)之前插入s所指結(jié)點(diǎn)的操作是 D AppriorpriorBppriorpriorCspriornext sDspriorprior s20如果最常用的操作是取第i個結(jié)點(diǎn)及其前驅(qū)則采用D存儲方式最節(jié)省時間A單鏈表 B雙鏈表C單循環(huán)鏈表D 順序表21在一個具有n個結(jié)點(diǎn)的有序單鏈表中插入一個新結(jié)點(diǎn)并仍然保持有序的時間復(fù)雜度是B AO（1） BO（n）CO（n2）DO（nlog2n）22在一個長度為n（n1）的單鏈表上設(shè)有頭和尾兩個指針執(zhí)行

6、B操作與鏈表的長度有關(guān)A刪除單鏈表中的第一個元素B刪除單鏈表中的最后一個元素C在單鏈表第一個元素前插入一個新元素D在單鏈表最后一個元素后插入一個新元素23與單鏈表相比雙鏈表的優(yōu)點(diǎn)之一是DA插入、刪除操作更簡單B可以進(jìn)行隨機(jī)訪問C可以省略表頭指針或表尾指針D順序訪問相鄰結(jié)點(diǎn)更靈活24如果對線性表的操作只有兩種即刪除第一個元素在最后一個元素的后面插入新元素則最好使用 B A只有表頭指針沒有表尾指針的循環(huán)單鏈表B只有表尾指針沒有表頭指針的循環(huán)單鏈表C非循環(huán)雙鏈表D循環(huán)雙鏈表25在長度為n的順序表的第i個位置上插入一個元素（1 i n1）元素的移動次數(shù)為： A An - i 1Bn - iCiDi -

7、 126對于只在表的首、尾兩端進(jìn)行插入操作的線性表宜采用的存儲結(jié)構(gòu)為 CA順序表 B 用頭指針表示的循環(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)于線性表的敘述中錯誤的是哪一個? BA線性表采用順序存儲必須占用一片連續(xù)的存儲單元B線性表采用順序存儲便于進(jìn)行插入和刪除操作C線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲單元D線性表采用鏈?zhǔn)酱鎯Ρ阌谶M(jìn)行插入和刪除操作29線性表是具有n個 B 的有限序列A字符B數(shù)據(jù)元素 C數(shù)據(jù)項(xiàng)D表元素30在n個結(jié)點(diǎn)的線性表的數(shù)組實(shí)現(xiàn)中算法的時

8、間復(fù)雜度是O（1）的操作是 A A訪問第i（1in）個結(jié)點(diǎn)和求第i個結(jié)點(diǎn)的直接前驅(qū)（1in）B在第i（1in）個結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)C刪除第i（1in）個結(jié)點(diǎn)D以上都不對31若長度為n的線性表采用順序存儲結(jié)構(gòu)在其第i個位置插入一個新元素的算法的時間復(fù)雜度為CAO（0） BO（1）CO（n）DO（n2）32對于順序存儲的線性表訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時間復(fù)雜度為 CAO（n） O（n） BO（n） O（1）CO（1） O（n）DO（1） O（1）33線性表（a1a2. an）以鏈?zhǔn)椒绞酱鎯υL問第i位置元素的時間復(fù)雜度為 CAO（0） BO（1）CO（n）DO（n2）34單鏈表中增加一個頭結(jié)點(diǎn)的

9、目的是為了CA使單鏈表至少有一個結(jié)點(diǎn) B標(biāo)識表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置C方面運(yùn)算的實(shí)現(xiàn) D說明單鏈表是線性表的鏈?zhǔn)酱鎯?5在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)正確的操作是 B Apnextpnextpnexts；Cpnextsnextsnext；pnexts36線性表的順序存儲結(jié)構(gòu)是一種A A隨機(jī)存取的存儲結(jié)構(gòu)B順序存取的存儲結(jié)構(gòu)C索引存取的存儲結(jié)構(gòu)DHash存取的存儲結(jié)構(gòu)37棧的特點(diǎn)是 B 隊(duì)列的特點(diǎn)是AA先進(jìn)先出 B先進(jìn)后出38棧和隊(duì)列的共同點(diǎn)是C A都是先進(jìn)后出 B都是先進(jìn)先出C只允許在端點(diǎn)處插入和刪除元素 D沒有共同點(diǎn)39一個棧的進(jìn)棧序列是abcde則棧的不可能的輸出序列是 C Ae

10、dcbaBdecbaCdceabDabcde40設(shè)有一個棧元素依次進(jìn)棧的順序?yàn)锳、B、C、D、E下列 C 是不可能的出棧序列 AABCDE BBCDEACEABCD DEDCBA 41以下 B 不是隊(duì)列的基本運(yùn)算?A從隊(duì)尾插入一個新元素B從隊(duì)列中刪除第i個元素C判斷一個隊(duì)列是否為空D讀取隊(duì)頭元素的值42若已知一個棧的進(jìn)棧序列是123n其輸出序列為p1p2p3.pn若p1n則pi為 CAi Bni Cni1 D不確定43判定一個順序棧st（最多元素為MaxSize）為空的條件是B Asttop ！top 1Csttop ！top MaxSize44判定一個順序棧st（最多元素為MaxSize）為

11、滿的條件是D Asttop ！top 1Csttop ！top MaxSize45一個隊(duì)列的入隊(duì)序列是1234則隊(duì)列的輸出序列是B A4321 B1234C1432 D324146判定一個循環(huán)隊(duì)列qu（最多元素為MaxSize）為空的條件是C Aqurear - qurear - qufront 1MaxSizeCqufront 147在循環(huán)隊(duì)列中若front與rear 分別表示對頭元素和隊(duì)尾元素的位置則判斷循環(huán)隊(duì)列空的條件是 CAfrontrear1 Brearfront1 Cfrontrear Dfront048向一個棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)點(diǎn)時應(yīng)執(zhí)行D操作Ahne

12、xth ；Csnexthnexts ；49輸入序列為ABC可以變?yōu)镃BA時經(jīng)過的棧操作為BApushpoppushpoppushpopBpushpushpushpop pop popCpushpushpop poppushpopDpushpoppushpushpop pop50若棧采用順序存儲方式存儲現(xiàn)兩棧共享空間V1mtop1、top2分別代表第1和第2個棧的棧頂棧1的底在V1棧2的底在Vm則棧滿的條件是BA|top2top1|0 B top11top2 Ctop1top2mDtop1top251設(shè)計(jì)一個判別表達(dá)式中左、右括號是否配對出現(xiàn)的算法采用D 數(shù)據(jù)結(jié)構(gòu)最佳A線性表的順序存儲結(jié)構(gòu) B隊(duì)

13、列 C線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)D棧52允許對隊(duì)列進(jìn)行的操作有DA對隊(duì)列中的元素排序B取出最近進(jìn)隊(duì)的元素C在隊(duì)頭元素之前插入元素D刪除隊(duì)頭元素53對于循環(huán)隊(duì)列D A無法判斷隊(duì)列是否為空 B無法判斷隊(duì)列是否為滿C隊(duì)列不可能滿 D以上說法都不對54若用一個大小為6的數(shù)值來實(shí)現(xiàn)循環(huán)隊(duì)列且當(dāng)前rear和front的值分別為0和3當(dāng)從隊(duì)列中刪除一個元素再加入兩個元素后rear和front的值分別為 BA1和5 B2和4 C4和2D5和155隊(duì)列的"先進(jìn)先出"特性是指 D A最早插入隊(duì)列中的元素總是最后被刪除B當(dāng)同時進(jìn)行插入、刪除操作時總是插入操作優(yōu)先C每當(dāng)有刪除操作時總是要先做一次插入操作

14、D每次從隊(duì)列中刪除的總是最早插入的元素56和順序棧相比鏈棧有一個比較明顯的優(yōu)勢是A A通常不會出現(xiàn)棧滿的情況 B 通常不會出現(xiàn)?？盏那闆r C插入操作更容易實(shí)現(xiàn) D刪除操作更容易實(shí)現(xiàn) 57用不帶頭結(jié)點(diǎn)的單鏈表存儲隊(duì)列其頭指針指向隊(duì)頭結(jié)點(diǎn)尾指針指向隊(duì)尾結(jié)點(diǎn)則在進(jìn)行出隊(duì)操作時 C A僅修改隊(duì)頭指針B僅修改隊(duì)尾指針 C隊(duì)頭、隊(duì)尾指針都可能要修改D隊(duì)頭、隊(duì)尾指針都要修改 58若串S'software'其子串的數(shù)目是 B A8 B37 C36D9 59串的長度是指B A串中所含不同字母的個數(shù) B串中所含字符的個數(shù) C串中所含不同字符的個數(shù) D串中所含非空格字符的個數(shù) 60串是一種特殊的線性

15、表其特殊性體現(xiàn)在B A可以順序存儲B數(shù)據(jù)元素是一個字符 C可以鏈?zhǔn)酱鎯數(shù)據(jù)元素可以是多個字符 61設(shè)有兩個串p和q求q在p中首次出現(xiàn)的位置的運(yùn)算稱為B A連接 B 模式匹配 C求子串D求串長 62數(shù)組A中每個元素的長度為3個字節(jié)行下標(biāo)i從1到8列下標(biāo)j從1到10從首地址SA開始連續(xù)存放的存儲器內(nèi)該數(shù)組按行存放元素A85的起始地址為 C ASA141B SA144 CSA222DSA225 63數(shù)組A中每個元素的長度為3個字節(jié)行下標(biāo)i從1到8列下標(biāo)j從1到10從首地址SA開始連續(xù)存放的存儲器內(nèi)該數(shù)組按行存放元素A58的起始地址為 C ASA141B SA180 CSA222DSA225 64若

16、聲明一個浮點(diǎn)數(shù)數(shù)組如下： froat averagenew float30； 假設(shè)該數(shù)組的內(nèi)存起始位置為200 average15的內(nèi)存地址是C A214 B215 C260D256 65設(shè)二維數(shù)組A1. m1. n按行存儲在數(shù)組B中則二維數(shù)組元素Aij在一維數(shù)組B中的下標(biāo)為 A An*（i1）jB n*（i1）j1Ci*（j1） Dj*mi1 66有一個100×90的稀疏矩陣非0元素有10設(shè)每個整型數(shù)占2個字節(jié)則用三元組表示該矩陣時所需的字節(jié)數(shù)是B A20 B 66C18 000 D33 67數(shù)組A0 . 41 . 35.7中含有的元素個數(shù)是A A55 B 45C36 D16 68

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

18、n hm B hm 2n C m h1Dn 2h1 74任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對次序 A A不發(fā)生改變 B發(fā)生改變C不能確定 D以上都不對 75在線索化樹中每個結(jié)點(diǎn)必須設(shè)置一個標(biāo)志來說明它的左、右鏈指向的是樹結(jié)構(gòu)信息還是線索化信息若0標(biāo)識樹結(jié)構(gòu)信息1標(biāo)識線索對應(yīng)葉結(jié)點(diǎn)的左右鏈域應(yīng)標(biāo)識為_ D_ A00 B01C10D11 76在下述論述中正確的是 D 只有一個結(jié)點(diǎn)的二叉樹的度為0；二叉樹的度為2；二叉樹的左右子樹可任意交換； 深度為K的順序二叉樹的結(jié)點(diǎn)個數(shù)小于或等于深度相同的滿二叉樹 AB C D 77設(shè)森林F對應(yīng)的二叉樹為B它有m個結(jié)點(diǎn)B的根為pp的右子樹的

19、結(jié)點(diǎn)個數(shù)為n森林F中第一棵樹的結(jié)點(diǎn)的個數(shù)是A Amn Bmn1 Cn1D不能確定 78若一棵二叉樹具有10個度為2的結(jié)點(diǎn)5個度為1的結(jié)點(diǎn)則度為0的結(jié)點(diǎn)的個數(shù)是B A9 B11 C15D不能確定 79具有10個葉子結(jié)點(diǎn)的二叉樹中有 B 個度為2的結(jié)點(diǎn) A8 B9 C10 D11 80在一個無向圖中所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的C 倍 A1/2 B 1C 2 D4 81在一個有向圖中所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的B倍 A1/2 B 1C 2 D4 82某二叉樹結(jié)點(diǎn)的中序序列為ABCDEFG后序序列為BDCAFGE則其左子樹中結(jié)點(diǎn)數(shù)目為：C A3B2 C4D5 83已知一算術(shù)表達(dá)式的中

20、綴形式為AB *C-D/E后綴形式為ABC *DE/-其前綴形式為 D A-AB*C/DE B-AB*CD/E C -*ABC/DE D-A*BC/DE 84已知一個圖如圖所示若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷則可能得到的一種頂點(diǎn)序列為_D_；按廣度搜索法進(jìn)行遍歷則可能得到的一種頂點(diǎn)序列為_A_； AabecdfBacfebd CaebcfdDaedfcb AabcedfBabcefd CaebcfdDacfdeb 85采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的_A_ A先序遍歷 B中序遍歷 C后序遍歷 D按層遍歷 86采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的_D_ A先序遍

21、歷 B中序遍歷 C后序遍歷 D按層遍歷 87具有n 個結(jié)點(diǎn)的連通圖至少有 A 條邊 An1B n C n（n1）/2 D 2n 88廣義表（a）a）的表頭是 C表尾是C Aa B（）C （a） D （a） 89廣義表（a）的表頭是 C表尾是B Aa B（）C （a） D （a） 90順序查找法適合于存儲結(jié)構(gòu)為 B的線性表 A散列存儲 B順序存儲或鏈?zhǔn)酱鎯壓縮存儲 D索引存儲 91對線性表進(jìn)行折半查找時要求線性表必須B A以順序方式存儲 B以順序方式存儲且結(jié)點(diǎn)按關(guān)鍵字有序排列 C以鏈?zhǔn)椒绞酱鎯?D以鏈?zhǔn)椒绞酱鎯η医Y(jié)點(diǎn)按關(guān)鍵字有序排列 92采用折半查找法查找長度為n的線性表時每個元素的平均查找長

22、度為D AO（n2） BO（nlog2n） CO（n）DO（log2n） 93有一個有序表為139123241456275778295100當(dāng)折半查找值為82的結(jié)點(diǎn)時C次比較后查找成功 A11 B5 C 4 D8 94二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值這種說法B A 正確 B 錯誤 95下面關(guān)于B樹和B樹的敘述中不正確的結(jié)論是 A AB樹和B樹都能有效的支持順序查找 BB樹和B樹都能有效的支持隨機(jī)查找 CB樹和B樹都是平衡的多叉樹 DB樹和B樹都可用于文件索引結(jié)構(gòu) 96以下說法錯誤的是 B A散列法存儲的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲地址 B散

23、列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息不包含指針 C負(fù)載因子是散列表的一個重要參數(shù)它反映了散列表的飽滿程度 D散列表的查找效率主要取決于散列表構(gòu)造時選取的散列函數(shù)和處理沖突的方法 97查找效率最高的二叉排序樹是C A所有結(jié)點(diǎn)的左子樹都為空的二叉排序樹 B所有結(jié)點(diǎn)的右子樹都為空的二叉排序樹 C平衡二叉樹 D沒有左子樹的二叉排序樹 98排序方法中從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較將其放入已排序序列的正確位置上的方法稱為C A希爾排序 B冒泡排序 C插入排序 D選擇排序 99在所有的排序方法中關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是D A希爾排序B冒泡排序 C直接插入排序 D直

24、接選擇排序 100堆是一種有用的數(shù)據(jù)結(jié)構(gòu)下列關(guān)鍵碼序列D 是一個堆 A943153231672B945331721623 C165323943172D163123945372 101堆排序是一種B排序 A插入B選擇C交換D歸并 102D 在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高 A順序查找B折半查找C分塊查找D插入 103直接選擇排序的時間復(fù)雜度為 D （n 為元素個數(shù)） AO（n） BO（log2n） CO（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)和

25、圖狀結(jié)構(gòu)4種 3在線性結(jié)構(gòu)中第一個結(jié)點(diǎn) 沒有 前驅(qū)結(jié)點(diǎn)其余每個結(jié)點(diǎn)有且只有 1個前驅(qū)結(jié)點(diǎn)；最后一個結(jié)點(diǎn) 沒有后續(xù)結(jié)點(diǎn)其余每個結(jié)點(diǎn)有且只有1個后續(xù)結(jié)點(diǎn) 4線性結(jié)構(gòu)中元素之間存在 一對一 關(guān)系樹形結(jié)構(gòu)中元素之間存在 一對多 關(guān)系圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系 5在樹形結(jié)構(gòu)中樹根結(jié)點(diǎn)沒有 前驅(qū) 結(jié)點(diǎn)其余每個結(jié)點(diǎn)有且只有 1個前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)其余每個結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以任意多個 6數(shù)據(jù)結(jié)構(gòu)的基本存儲方法是 順序、鏈?zhǔn)健?索引和 散列存儲 7衡量一個算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和 時間復(fù)雜度與 空間復(fù)雜度 8評估一個算法的優(yōu)劣通常從時間復(fù)雜度 和空間復(fù)雜度 兩個方面考察 9算法

26、的5個重要特性是有窮性、確定性 、可行性、輸入和輸出 10在一個長度為n的順序表中刪除第i個元素時需向前移動 ni1個元素 11在單鏈表中要刪除某一指定的結(jié)點(diǎn)必須找到該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn) 12在雙鏈表中每個結(jié)點(diǎn)有兩個指針域一個指向 前驅(qū) 結(jié)點(diǎn)另一個指向 后繼結(jié)點(diǎn) 13在順序表中插入或刪除一個數(shù)據(jù)元素需要平均移動 n個數(shù)據(jù)元素移動數(shù)據(jù)元素的個數(shù)與 位置 有關(guān) 14當(dāng)線性表的元素總數(shù)基本穩(wěn)定且很少進(jìn)行插入和刪除操作但要求以最快的速度存取線性表的元素是應(yīng)采用順序 存儲結(jié)構(gòu) 15根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個結(jié)點(diǎn)包含的指針個數(shù)將線性鏈表分成單鏈表 和 雙鏈表 16順序存儲結(jié)構(gòu)是通過 下標(biāo) 表示元素之間的

27、關(guān)系的；鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過指針 表示元素之間的關(guān)系的 17帶頭結(jié)點(diǎn)的循環(huán)鏈表L中只有一個元素結(jié)點(diǎn)的條件是LnextnextL 18棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表其運(yùn)算遵循后進(jìn)先出的原則 19空串是 零個字符的串其長度等于 零空白串是由一個或多個空格字符組成的串其長度等于其包含的空格個數(shù) 20組成串的數(shù)據(jù)元素只能是 單個字符 21一個字符串中 任意個連續(xù)字符構(gòu)成的部分 稱為該串的子串 22子串 "str" 在主串 "datastructure" 中的位置是 5 23二維數(shù)組M的每個元素是6個字符組成的串行下標(biāo)i的范圍從0到8列下標(biāo)j的范圍從1到

28、10則存放M至少需要 540個字節(jié)；M的第8列和第5行共占108個字節(jié) 24稀疏矩陣一般的壓縮存儲方法有兩種即 三元組表和十字鏈表 25廣義表（a）（b）c）（d）的長度是3深度是4 26在一棵二叉樹中度為零的結(jié)點(diǎn)的個數(shù)為n0度為2 的結(jié)點(diǎn)的個數(shù)為n2則有n0 n21 27在有n個結(jié)點(diǎn)的二叉鏈表中空鏈域的個數(shù)為_n1_ 28一棵有n個葉子結(jié)點(diǎn)的哈夫曼樹共有_2n1_個結(jié)點(diǎn) 29深度為5的二叉樹至多有31 個結(jié)點(diǎn) 30若某二叉樹有20個葉子結(jié)點(diǎn)有30個結(jié)點(diǎn)僅有一個孩子則該二叉樹的總結(jié)點(diǎn)個數(shù)為 69 31某二叉樹的前序遍歷序列是abdgcefh中序序列是dgbaechf其后序序列為gdbehfca

29、 32線索二叉樹的左線索指向其 遍歷序列中的前驅(qū) 右線索指向其遍歷序列中的后繼 33在各種查找方法中平均查找長度與結(jié)點(diǎn)個數(shù)n無關(guān)的查找方法是散列查找法 34在分塊索引查找方法中首先查找 索引表然后查找相應(yīng)的塊表 35一個無序序列可以通過構(gòu)造一棵二叉排序 樹而變成一個有序序列構(gòu)造樹的過程即為對無序序列進(jìn)行排序的過程 36具有10個頂點(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)一個索引隸屬于某個數(shù)據(jù)記錄集它

30、由若干索引項(xiàng)組成索引項(xiàng)的結(jié)構(gòu)為關(guān)鍵字 和 關(guān)鍵字對應(yīng)記錄的地址 39Prim 算法生成一個最小生成樹每一步選擇都要滿足 邊的總數(shù)不超過n1 當(dāng)前選擇的邊的權(quán)值是候選邊中最小的 選中的邊加入樹中不產(chǎn)生回路三項(xiàng)原則 40在一棵m階B樹中除根結(jié)點(diǎn)外每個結(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)中第一個結(jié)點(diǎn)_無_前驅(qū)結(jié)點(diǎn)其余每個結(jié)點(diǎn)有且只有_1_個前驅(qū)結(jié)點(diǎn)；最后一個結(jié)點(diǎn)_無_后續(xù)結(jié)點(diǎn)其余每個結(jié)點(diǎn)有且只有_1_個后續(xù)結(jié)點(diǎn) 4線性結(jié)構(gòu)中元素之間存在 _一個對一個的_ 關(guān)系樹形結(jié)構(gòu)中元素

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

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

33、t=L_ 18_棧_是限定僅在表尾進(jìn)行插入或刪除操作的線性表其運(yùn)算遵循_后進(jìn)先出_的原則 三、判斷題 1在決定選取何種存儲結(jié)構(gòu)時一般不考慮各結(jié)點(diǎn)的值如何（） 2抽象數(shù)據(jù)類型（ADT）包括定義和實(shí)現(xiàn)兩方面其中定義是獨(dú)立于實(shí)現(xiàn)的定義僅給出一個ADT的邏輯特性不必考慮如何在計(jì)算機(jī)中實(shí)現(xiàn)（ ） 3抽象數(shù)據(jù)類型與計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)無關(guān)（ ） 4順序存儲方式插入和刪除時效率太低因此它不如鏈?zhǔn)酱鎯Ψ绞胶茫?×） 5線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲空間可以是不連續(xù)的（ × ） 6對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)（ ×） 7順序存儲方式只能用于存儲線性結(jié)構(gòu)（ ×） 8集合與線性表的區(qū)別在于是否按關(guān)鍵字排序（ ×） 9線性表中每個元素都有一個直接前驅(qū)和一個直接后繼（ ×） 10線性表就是順序存儲的表（ ×） 11取線性表的第i個元素的時間同i的大