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

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

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

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

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

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

6、寫(xiě)出該序列的冒泡排序示意圖。五算法描述題：共1小題，每題10分，滿分10分；用任何程序語(yǔ)言、偽語(yǔ)言或流程圖描述下列算法。1.如圖2所示已知一個(gè)單鏈表指針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）請(qǐng)畫(huà)出示意圖（2）描述算法。/ /X Q M200 200 學(xué)年第 學(xué)期期末試題數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言）答題卡題號(hào)一二三四五總分分?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語(yǔ)言）答案及評(píng)分標(biāo)準(zhǔn)一 單項(xiàng)選擇題：（2×10）12345678910AAACDACBBC二 判斷題：(1×10)12345678910×××××××三、 填空題：（3×10）1. 集合 、 樹(shù) 、 圖 2. n 、 i+1 、 后 3. p=p->next 4. front=(front+1)/Maxsize 5. 尾指針 、 頭指針 6. 4 、 7 7. 先序 、 中序 、 后序 、 層次 8. 順序存儲(chǔ) 、 二叉鏈表存儲(chǔ) 、 三叉鏈表存儲(chǔ) 9. 9 10. 直接插入排序 、 冒泡排序 、 簡(jiǎn)單選擇排序 四 數(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