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

1、成都東軟信息技術(shù)學院200 200 學年第 學期期末試題數(shù)據(jù)結(jié)構(gòu)（C語言）題號一二三四五總分分數(shù)說明：本試卷共五大題，試卷滿分100分，考試時間120分鐘。一單項選擇題：共10小題、每題2分，滿分20分；將答案填入題中的括號中。1在一個長度為n的順序存儲線性表中，向第i個元素(1in+1)之前插入一個新元素時，需要從后向前依次后移 個元素。 A、n-i B、n-i+1 C、n-i-1 D、i2在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行 。 A、HL = p; p->next = HL; B、p->next = HL; HL = p; C、p->next

2、= HL; p = HL; D、p->next = HL->next; HL->next = p;3在一個單鏈表HL中，若要刪除由指針q所指向結(jié)點的后繼結(jié)點，則執(zhí)行 。 A、p = q->next ; p->next = q->next; B、p = q->next ; q->next = p; C、p = q->next ; q->next = p->next; D、q->next = q->next->next; q->next = q;4棧的插入與刪除操作在 進行。 A、棧頂 B、棧底 C、任意位置

3、 D、指定位置5若讓元素1，2，3依次進棧，則出棧次序不可能出現(xiàn) 種情況。 A、3，2，1 B、2，1，3 C、3，1，2 D、1，3，26在一個循環(huán)順序隊列中，隊首指針指向隊首元素的 位置。 A、前一個 B、后一個 C、當前 D、后面7在所有排序方法中，關(guān)鍵字比較次數(shù)與記錄的初始排列次序無關(guān)的是 。 A、直接插入排序 B、起泡排序 C、快速排序 D、直接選擇排序8假定一個鏈隊的隊首和隊尾指針分別為front和rear，則判斷隊空的條件是 。 A、front=rear B、front!=NULL C、rear!=NULL D、front=NULL9. 由權(quán)值分別為3,8,6,2,5的葉子結(jié)點生

4、成一棵哈夫曼樹，它的帶權(quán)路徑長度為_。 A、 24 B、 48 C、 72 D、 5310.組成數(shù)據(jù)的基本單位是 。 A、數(shù)據(jù)項 B、數(shù)據(jù)類型 C、數(shù)據(jù)元素 D、數(shù)據(jù)變量二判斷題：共10小題，每小題1分，滿分10分；請將答案以“”、“×”形式填入題后括號中。1無向圖的鄰接矩陣一定是對稱矩陣。 （ ）2任意一棵滿二叉樹一定也是完全二叉樹。 （ ）3如果某數(shù)據(jù)結(jié)構(gòu)的每一個元素都最多只有一個直接前驅(qū)和一個直接后繼，則該數(shù)據(jù)結(jié)構(gòu)必為線性表。 （ ）4有向圖鄰接矩陣的第i行的所有元素之和等于第i列的所有元素之和。 （ ）5進棧操作時，必須判斷棧是否已滿。 （ ）6線性表的唯一存儲形式就是鏈表。

5、 （ ）7一個強連通圖的連通分量只有一個。 （ ）8數(shù)據(jù)元素是數(shù)據(jù)的最小單元。 （ ）9滿二叉樹的葉子結(jié)點一定都在最后一層。 （ ）10完全二叉樹的葉子結(jié)點可能都在最后一層。 （ ）三填空題：共10小題，每題3分，滿分30分；請將一個正確答案的序號填入括號中。1. 數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_、_、_和_四種。2. 在線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點之間分別存在著_、_和_的聯(lián)系。3. 設(shè)一棵二叉樹有50個葉子結(jié)點，則共有 個度為2的結(jié)點。4在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的_倍。5在一個具有n個頂點的無向完全圖中，包含有_條邊，在一個具有n個頂點的有向完全圖中，包含有_條邊

6、。 6表示圖的三種存儲結(jié)構(gòu)為_、_和_。7在對一組記錄（54，38，96，23，15，72，60，45，83）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置需比較 次。8在線性表的_存儲中，對每一個元素只能采用順序查找。9對n個元素的序列進行起泡排序時，最少的比較次數(shù)是 。10. 采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為_。四應(yīng)用題：共3小題，每題10分，滿分30分。1.已知一棵二叉樹的中序遍歷結(jié)果為DBHEAFICG，前序遍歷結(jié)果為ABDEHCFIG，畫出該二叉樹。2.已知一棵完全二叉樹的順序存儲結(jié)構(gòu)如下表所示，試畫出該完全二叉樹的邏輯示意圖。

7、3.已知有二叉樹如右圖所示 。 （1）寫出各結(jié)點的度。（2）畫出右圖二叉樹對應(yīng)的二叉鏈表存儲結(jié)構(gòu)示意圖。ABCDIEFHG五算法描述題：共1小題，每題10分，滿分10分；用任何程序語言、偽語言或流程圖描述下列算法。1設(shè)計一個算法，將一順序棧中的元素依次取出，并打印元素值。已知順序棧的數(shù)據(jù)結(jié)構(gòu)如下： Typedef struct int data100； int top； SeqStack； 答案及評分標準：數(shù)據(jù)結(jié)構(gòu)（C語言）答案及評分標準一 單項選擇題：（2×10）12345678910BDCACADADA二 判斷題：(1×10)12345678910××××三 填空題：（3×10）1.集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)2.一對一、一對多、多對多3.494.25.n（n-1）/2、 n（n-1）6.鄰接矩陣、鄰接表、逆鄰接表7.38.鏈式9.n-110.（n+1）/2四 應(yīng)用題：（10 ×3）12.ABCDEHFGI3.（1）A-2、B-3、C-1、D-0、E-2、F-0、G-0、H-0、I-0 （2）答案略五 算法描述題：（10）答案略20052006學年第二學期期末試題數(shù)據(jù)結(jié)構(gòu)（C語言