1、數據結構第二次單元測試姓名學號.分數.一、 單項選擇題（每小題2 分，共 26 分）1、A2、C3、D4、A5、D6、C7、B8、A9、B10 、A11 、D12 、D131. 數據結構是指（）。A. 數據元素的組織形式B.數據類型C.數據存儲結構D.數據定義2. 數據在計算機存儲器內表示時，物理地址與邏輯地址不相同的，稱之為（）。A. 存儲結構B.邏輯結構C.鏈式存儲結構D.順序存儲結構3. 樹形結構是數據元素之間存在一種（）。A. 一對一關系B.多對多關系C.多對一關系D. 一 對 多 關系4.在一個長度為n 的順序表中刪除第i 個元素 (0<=i<=n) 時，需向前移動個元素

2、。A n-iB n-i+lC n-i-1D i5.線性表采用鏈式存儲時，其地址_。A 必須是連續的B一定是不連續的C部分地址必須是連續的D 連續與否均可以6.下圖所示的是線性表的鏈接存儲結構，采用的是()鏈表。Ha1aa2nA. 單鏈表B. 十字鏈表C.雙鏈表D.循環鏈表7. 一個二叉樹按順序方式存儲在一個維數組中，如圖01234567891011121314ABCDEFGHIJ則結點 E 在二叉樹的第（）層。A. 1B. 2C. 3D.48 線性表采用鏈式存儲時，結點的存儲地址（）A 連續與否均可B必須是不連續的C必須是連續的D 和頭結點的存儲地址相連續9 空串與空格字符組成的串的區別在于（

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

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

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