1、數(shù)據(jù)結(jié)構(gòu)考試及答案數(shù)據(jù)結(jié)構(gòu)第二次單元測試姓名學(xué)號. 分?jǐn)?shù).一、 單項選擇題（每小題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ù)類型C.數(shù)據(jù)存儲結(jié)構(gòu)D.數(shù)據(jù)定義2. 數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址不相同的，稱之為（ ）。A. 存儲結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.鏈?zhǔn)酱鎯Y(jié)構(gòu)D.順序存儲結(jié)構(gòu)3. 樹形結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（ ）。A. 一對一關(guān)系B.多對多關(guān)系C.多對一關(guān)系D.一對多關(guān)系4. 在一個長度為 n 的順序表中刪除第i 個元素 (0<=i<=

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

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

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

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