《數(shù)據(jù)結(jié)構(gòu)》考試及答案說(shuō)課材料

1、數(shù)據(jù)結(jié)構(gòu)考試及答案數(shù)據(jù)結(jié)構(gòu)第二次單元測(cè)試姓名學(xué)號(hào). 分?jǐn)?shù).一、 單項(xiàng)選擇題（每小題2 分，共 26 分）1、 A2、 C3、D4、A5、D6、C7、B8、 A9、 B10、A11、D12、 D131. 數(shù)據(jù)結(jié)構(gòu)是指（ ）。A. 數(shù)據(jù)元素的組織形式B.數(shù)據(jù)類(lèi)型C.數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)D.數(shù)據(jù)定義2. 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址不相同的，稱(chēng)之為（ ）。A. 存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.順序存儲(chǔ)結(jié)構(gòu)3. 樹(shù)形結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（ ）。A. 一對(duì)一關(guān)系B.多對(duì)多關(guān)系C.多對(duì)一關(guān)系D.一對(duì)多關(guān)系4. 在一個(gè)長(zhǎng)度為 n 的順序表中刪除第i 個(gè)元素 (0<=i<=

2、n) 時(shí)，需向前移動(dòng)個(gè)元素。A n-iBn-i+lCn-i-1Di5. 線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址 _。A 必須是連續(xù)的B一定是不連續(xù)的C部分地址必須是連續(xù)的D連續(xù)與否均可以6. 下圖所示的是線(xiàn)性表的鏈接存儲(chǔ)結(jié)構(gòu)，采用的是 ( ) 鏈表。Ha12naaA. 單鏈表B.十字鏈表C.雙鏈表D.循環(huán)鏈表7. 一個(gè)二叉樹(shù)按順序方式存儲(chǔ)在一個(gè)維數(shù)組中，如圖01234567891011121314ABCDEFGHIJ則結(jié)點(diǎn) E 在二叉樹(shù)的第（）層。A. 1B. 2C. 3D.48線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（）A連續(xù)與否均可B必須是不連續(xù)的C必須是連續(xù)的D和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)9空串與空格字符

3、組成的串的區(qū)別在于（）。A. 沒(méi)有區(qū)別B.兩串的長(zhǎng)度不相等C.兩串的長(zhǎng)度相等D.兩串包含的字符不相同10棧和隊(duì)列的共同特點(diǎn)是()。A. 只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒(méi)有共同點(diǎn)11用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)( D ).A. 僅修改頭指針B. 頭、尾指針都要修改C. 僅修改尾指針D.頭、尾指針可能都要修改12 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線(xiàn)性結(jié)構(gòu)？( d )A. 隊(duì)列B. 棧C. 線(xiàn)性表D. 二叉樹(shù)13 二叉樹(shù)的第 k 層的結(jié)點(diǎn)數(shù)最多為 ( D ).A 2k-1B.2K+1C.2K-1D. 2k-1二、填空題（每空2 分，共 32 分）1. 一維數(shù)組的邏

4、輯結(jié)構(gòu)是 _線(xiàn)性 _，存儲(chǔ)結(jié)構(gòu)是 _順序存儲(chǔ) _；對(duì)于二維或多維數(shù)組，分為 _順序 _和 _鏈?zhǔn)?_兩種不同的存儲(chǔ)方式。2. 棧是一種運(yùn)算受限的線(xiàn)性表，其限制是僅允許在表的一端進(jìn)行插入和刪除操作，進(jìn)行操作的這一端稱(chēng)為棧頂，與其對(duì)應(yīng)的另一端稱(chēng)為棧底。3. 在樹(shù)型結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有 _后繼 _結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的有且只有 _1_個(gè)前趨驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有 _子_結(jié)點(diǎn)；其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以 _有多個(gè)結(jié)點(diǎn) _。4. 線(xiàn)性結(jié)構(gòu)中元素之間存在 _一對(duì)一 _關(guān)系；樹(shù)型結(jié)構(gòu)中元素之間存在 _一對(duì)多 _關(guān)系。5. 一棵深度為 k 的滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)總數(shù)為 _ (2h)-1 _ ，一棵深度為 k 的完全二叉

5、樹(shù)的結(jié)點(diǎn)總數(shù)的最小值為 _(2h)-1_ ，最大值為 _(2h)-1_ 。6. 設(shè)一棵完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)元素為ABCDEFG ，則該二叉樹(shù)的前序遍歷序列為 _ABDECFG_ 。三、判斷題 （每題 1 分，共 8 分）1、×2、3、4、×5、×6、×7、×8、1. 數(shù)組可看作基本線(xiàn)性表的一種推廣，因此與線(xiàn)性表一樣，可以對(duì)它進(jìn)行插入、刪除等操作。（ ）2.對(duì)于不同的特殊矩陣應(yīng)該采用不同的存儲(chǔ)方式。（）3.采用壓縮存儲(chǔ)之后，下三角矩陣的存儲(chǔ)空間可以節(jié)約一半。（）4. 在一般情況下，采用壓縮存儲(chǔ)之后，對(duì)稱(chēng)矩陣是所有特殊矩陣中存儲(chǔ)空間節(jié)約最多的。（ ）5.距陣中的數(shù)據(jù)元素可以是不同的數(shù)據(jù)類(lèi)型。（）6.矩陣中的行列數(shù)往往是不相等的。（）7線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更好。（）8不論是入隊(duì)列操作還是入棧操作，在順序存儲(chǔ)結(jié)構(gòu)上都需要考慮 “溢出 ”情況。（ ）四、名詞解釋?zhuān)款}4 分，共 16 分）1 數(shù)據(jù)結(jié)構(gòu)2 線(xiàn)性表3. 樹(shù)4. 矩陣五、解答題（