1、一單項選擇題：共10小題、每題2分，滿分20分；將答案填入題中的括號中。1在一個長度為n的順序存儲線性表中，刪除第i個元素(1in)時，需要從前向后依次前移 個元素。 A、n-i B、n-i+1 C、n-i-1 D、i2.組成數(shù)據(jù)的基本單位是 。 A、數(shù)據(jù)項 B、數(shù)據(jù)類型 C、數(shù)據(jù)元素 D、數(shù)據(jù)變量3. 當利用大小為N的一維數(shù)組順序存儲一個棧時，假定用top=1表示?？?，則向這個棧插入一個元素時，首先應執(zhí)行 語句修改top指針。 Atop+； Btop-； Ctop=NULL ； Dtop；4. 若讓元素a，b，c依次進棧，則出棧次序不可能出現(xiàn) 種情況。 Acba Bbac Ccab Dacb

2、5. 線性表采用鏈式存儲時，其地址 。 A必須是連續(xù)的 B部分地址必須是連續(xù)的 C一定是不連續(xù)的 D連續(xù)與否均可以6. 線性表的鏈式存儲有利于 運算。 A插入 B讀表元 C查找 D定位7. 在一個長度為n的線性表中插入第i個元素的操作中，i的取值范圍是 A1in B0in C1i n+1 D1in-18.如果要查找單鏈表中的第i個元素，應該從 開始進行查找。A第i個結點 B 頭結點 C 尾結點 D 任意一個結點9.當采用順序存儲方式存儲隊列時，可能出現(xiàn)存儲空間剩余，而不允許繼續(xù)入隊的情況，稱為 。A溢出 B 假溢出 C隊列不能用順序存儲方式 D數(shù)組存儲空間過小 10.一棵完全二叉樹的結點按層次

3、遍歷從1開始編號，如果編號為m的結點有雙親，則雙親的編號為 。A2×m Bm1 Cm/2 D.m-1二判斷題：共10小題，每小題1分，滿分10分；請將答案以“”、“×”形式填入題后括號中。1.線性表不能采用鏈式存儲。 （ ）2.在單鏈表中插入結點主要通過移動元素實現(xiàn)。 （ ）3.棧是一種先進后出的線性表。 （ ）4.在循環(huán)順序隊列中插入新元素不需要判斷隊列是否滿了。 （ ）5.用頭部插入結點的方法建立單鏈表時，插入元素的順序和鏈表中的元素順序相同。 （ ）6. 一棵滿二叉樹一定是一棵完全二叉樹。 （ ）7. 線性表中的每個元素都有一個前驅元素和后繼元素。 （ ）8.葉子結點

4、的度不一定為0。 （ ）9.哈夫曼樹得到的帶權路徑長度一定是最小的。 （ ）10.有序表的折半查找只適用于升序表。 （ ）三填空題：共10小題，每題3分，滿分30分；請將一個正確答案的序號填入括號中。1. 數(shù)據(jù)結構中，非線性邏輯結構有 、 、 。2.在長度為n的順序表中插入第i個元素（假設i值可操作），要將元素從第 個到第 個元素向 （前或后）移動。3.將指向單鏈表中的某個結點的指針p移動到該結點的后繼結點表示為 。4.在長度為Maxsize的循環(huán)隊列中，刪除一個新元素，修改front隊頭指針為 。 5. 在鏈隊列中，與入隊相關的指針是 、與出隊有關的指針是 （頭指針或尾指針）。6. 總共三層

5、的完全二叉樹，其結點數(shù)至少有 個，至多有 個。7. 二叉樹的遍歷方法有 、 、 、 。8. 二叉樹的存儲結構有 、 、 結構表示。9.一棵哈夫曼樹有5個葉子結點組成，該哈夫曼樹總共有 個結點。10簡單排序有 、 、 方法。四數(shù)據(jù)結構圖形描述題：共3小題，每題10分，滿分30分；根據(jù)題目畫出示意圖。1.如圖1，畫出該二叉樹的順序存儲示意圖。 A BCD E F G H （圖1）0 1 2 3 4 5 6 7 8 9 10 11 12 13 142.一棵二叉樹的先序遍歷序列為ABDGCEHF，中序遍歷序列為DGBAEHCF，請畫出該二叉樹的示意圖。3.有一個初始序列為1，22，13，8的數(shù)據(jù)，要求

6、寫出該序列的冒泡排序示意圖。五算法描述題：共1小題，每題10分，滿分10分；用任何程序語言、偽語言或流程圖描述下列算法。1.如圖2所示已知一個單鏈表指針Q指向某結點，M指向待插入的值為X的結點，要求將M結點插到Q結點的后一結點位置。data *next結點的結構為：（1）請畫出示意圖（2）描述算法。/ /X Q M200 200 學年第 學期期末試題數(shù)據(jù)結構（C語言）答題卡題號一二三四五總分分數(shù)一單項選擇題：（2×15）12345678910二判斷題：(1×10)12345678910三填空題：（2×10）1. 、 、 2. 、 、 3. 4. 5. 、 6. 、

7、 7. 、 、 、 8. 、 、 9. 10. 、 、 四數(shù)據(jù)結構圖形描述題：（10 ×3）10 1 2 3 4 5 6 7 8 9 10 11 12 13 1423五算法描述題：（10）1.20052006學年第二學期期末試題數(shù)據(jù)結構（C語言）答案及評分標準一 單項選擇題：（2×10）12345678910AAACDACBBC二 判斷題：(1×10)12345678910×××××××三、 填空題：（3×10）1. 集合 、 樹 、 圖 2. n 、 i+1 、 后 3. p=p->next 4. front=(front+1)/Maxsize 5. 尾指針 、 頭指針 6. 4 、 7 7. 先序 、 中序 、 后序 、 層次 8. 順序存儲 、 二叉鏈表存儲 、 三叉鏈表存儲 9. 9 10. 直接插入排序 、 冒泡排序 、 簡單選擇排序 四 數(shù)據(jù)結構圖形描述題：（10 ×3）1.ABCDEFGH0 1 2 3 4 5 6 7 8 9 10 11 12 13 142. A B C D E F G H3. 1 22 13 8第一趟 第一次比較 1 22第二次比較、交換 13 22