數(shù)據(jù)結(jié)構(gòu)C語言試卷6

1、一單項(xiàng)選擇題：共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ù)項(xiàng) B、數(shù)據(jù)類型 C、數(shù)據(jù)元素 D、數(shù)據(jù)變量3. 當(dāng)利用大小為N的一維數(shù)組順序存儲一個棧時，假定用top=1表示?？眨瑒t向這個棧插入一個元素時，首先應(yīng)執(zhí)行 語句修改top指針。 Atop+； Btop-； Ctop=NULL ； Dtop；4. 若讓元素a，b，c依次進(jìn)棧，則出棧次序不可能出現(xiàn) 種情況。 Acba Bbac Ccab Dacb

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

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

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

5、的完全二叉樹，其結(jié)點(diǎn)數(shù)至少有 個，至多有 個。7. 二叉樹的遍歷方法有 、 、 、 。8. 二叉樹的存儲結(jié)構(gòu)有 、 、 結(jié)構(gòu)表示。9.一棵哈夫曼樹有5個葉子結(jié)點(diǎn)組成，該哈夫曼樹總共有 個結(jié)點(diǎn)。10簡單排序有 、 、 方法。四數(shù)據(jù)結(jié)構(gòu)圖形描述題：共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指向某結(jié)點(diǎn)，M指向待插入的值為X的結(jié)點(diǎn)，要求將M結(jié)點(diǎn)插到Q結(jié)點(diǎn)的后一結(jié)點(diǎn)位置。data *next結(jié)點(diǎn)的結(jié)構(gòu)為：（1）請畫出示意圖（2）描述算法。/ /X Q M200 200 學(xué)年第 學(xué)期期末試題數(shù)據(jù)結(jié)構(gòu)（C語言）答題卡題號一二三四五總分分?jǐn)?shù)一單項(xiàng)選擇題：（2×15）12345678910二判斷題：(1×10)12345678910三填空題：（2×10）1. 、 、 2. 、 、 3. 4. 5. 、 6. 、

7、 7. 、 、 、 8. 、 、 9. 10. 、 、 四數(shù)據(jù)結(jié)構(gòu)圖形描述題：（10 ×3）10 1 2 3 4 5 6 7 8 9 10 11 12 13 1423五算法描述題：（10）1.20052006學(xué)年第二學(xué)期期末試題數(shù)據(jù)結(jié)構(gòu)（C語言）答案及評分標(biāo)準(zhǔn)一 單項(xiàng)選擇題：（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ù)結(jié)構(gòu)圖形描述題：（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