數據結構試卷(一)（數據結構試卷）

大家好，我是小華，我來為大家解答以上問題。數據結構試卷(一)，數據結構試卷很多人還不知道，現在讓我們一起來看看吧！

1、一、填空題（每空1分，共22分） 數據結構被形式地定義為（D, R），其中D是 數據元素 的有限集合，R是D上的 關系 有限集合。

2、 2、一個算法的效率可分為 時間 效率和 空間 效率。

3、 3、向一個長度為n的向量的第i個元素(1≤i≤n+1)之前插入一個元素時，需向后移動 n-i+1 個元素。

4、 4、在一個循環隊列中，隊首指針指向隊首元素的 前一個 位置。

5、 5、在具有n個單元的循環隊列中，隊滿時共有 n-1 個元素。

6、 6、向棧中壓入元素的操作是先 移動棧頂指針 ，后 存入元素 。

7、 7、 不包含任何字符（長度為0）的串 稱為空串； 由一個或多個空格（僅由空格符）組成的串 稱為空白串。

8、 8、假設有二維數組A6×8，每個元素用相鄰的6個字節存儲，存儲器按字節編址。

9、已知A的起始存儲位置（基地址）為1000，則數組A的體積（存儲量）為 288 B ；末尾元素A57的第一個字節地址為 1282 ；若按行存儲時，元素A14的第一個字節地址為 (8+4)×6+1000=1072 ；若按列存儲時，元素A47的第一個字節地址為 (6×7＋4)×6＋1000）＝1276 。

10、 9、設一棵完全二叉樹具有1000個結點，則此完全二叉樹有 500 個葉子結點，有 499 個度為2的結點，有 1 個結點只有非空左子樹，有 0 個結點只有非空右子樹。

11、 10、線性有序表（a1，a2，a3，…，a256)是從小到大排列的，對一個給定的值k，用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索 8 次。

12、設有100個結點，用二分法查找時，最大比較次數是 7 。

13、 1散列法存儲的基本思想是由 關鍵字的值 決定數據的存儲地址。

14、 一、 判斷題（每題1分，共10分） （ × ）9. 隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結構。

15、 （ × ）1.二叉樹中所有結點個數是2k-1-1，其中k是樹的深度。

16、（應2i-1） （ √ ）7. 棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。

17、 （ × ）2.二叉樹中所有結點，如果不存在非空左子樹，則不存在非空右子樹。

18、 （ × ）3.對于一棵非空二叉樹，它的根結點作為第一層，則它的第i層上最多能有2i—1個結點。

19、（應2i-1） （ × ）3. 鏈表的刪除算法很簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續的各個單元向前移動。

20、 （ √ ）4.用二叉鏈表法（link-rlink）存儲包含n個結點的二叉樹，結點的2n個指針區域中有n+1個為空指針。

21、 （ √ ）5.具有12個結點的完全二叉樹有5個度為2的結點。

22、 （ × ）8. 線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。

23、 （ × ）5. 順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。

24、 三、單項選擇題（每小題2分，共18分） （ C ）1．數據在計算機存儲器內表示時，物理地址與邏輯地址相同并且是連續的，稱之為： （A）存儲結構 （B）邏輯結構 （C）順序存儲結構 （D）鏈式存儲結構 （ B ）2.一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是 （A）110 （B）108 （C）100 （D）120 （ A ）3. 在n個結點的順序表中，算法的時間復雜度是O（1）的操作是： （D） 訪問第i個結點（1≤i≤n）和求第i個結點的直接前驅（2≤i≤n） （E） 在第i個結點后插入一個新結點（1≤i≤n） （F） 刪除第i個結點（1≤i≤n） （G） 將n個結點從小到大排序 （ B ）4. 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動 個元素 （A）8 （B）63.5 （C）63 （D）7 （ A ）4.判定一個隊列QU（最多元素為m0）為滿隊列的條件是_______ Ａ．QU->rear － QU->front = = m0 Ｂ．QU->rear － QU->front －1= = m0 Ｃ．QU->front = = QU->rear Ｄ．QU->front = = QU->rear+1 （ B ）6. 鏈表是一種采用 存儲結構存儲的線性表； （A）順序 （B）鏈式 （C）星式 （D）網狀 （ D ）7. 線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址: （A）必須是連續的 （B）部分地址必須是連續的 （C）一定是不連續的 （D）連續或不連續都可以 （ B ）8． 線性表Ｌ在 情況下適用于使用鏈式結構實現。

25、 （Ａ）需經常修改Ｌ中的結點值 （Ｂ）需不斷對Ｌ進行刪除插入 （Ｃ）Ｌ中含有大量的結點 （Ｄ）Ｌ中結點結構復雜 （ C ）9. 若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為 Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不確定 四、 略 2、 答：X= 116 Y= 0 Z= 100 首址= 108 末址= 112 五、 答：輸出為“stack”。

26、 2、 答：輸出為“char”。

27、 六、解：方案1；哈夫曼編碼 先將概率放大100倍，以方便構造哈夫曼樹。

28、 w={7,19,2,6,32,3,21,10}，按哈夫曼規則：【[（2,3），6], (7,10)】, ?……19, 21, 32 （100） （40） （60） 19 21 32 （28） （17） （11） 7 10 6 （5） 2 3。

本文到此講解完畢了，希望對大家有幫助。