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

1、成都東軟信息技術(shù)學(xué)院200 200 學(xué)年第 學(xué)期期末試題數(shù)據(jù)結(jié)構(gòu)（C語言）題號(hào)一二三四五總分分?jǐn)?shù)說明：本試卷共五大題，試卷滿分100分，考試時(shí)間120分鐘。一單項(xiàng)選擇題：共10小題、每題2分，滿分20分；將答案填入題中的括號(hào)中。1在一個(gè)長度為n的順序存儲(chǔ)線性表中，向第i個(gè)元素(1in+1)之前插入一個(gè)新元素時(shí)，需要從后向前依次后移 個(gè)元素。 A、n-i B、n-i+1 C、n-i-1 D、i2在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(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在一個(gè)單鏈表HL中，若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(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棧的插入與刪除操作在 進(jìn)行。 A、棧頂 B、棧底 C、任意位置

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

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

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

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

7、3.已知有二叉樹如右圖所示 。 （1）寫出各結(jié)點(diǎn)的度。（2）畫出右圖二叉樹對(duì)應(yīng)的二叉鏈表存儲(chǔ)結(jié)構(gòu)示意圖。ABCDIEFHG五算法描述題：共1小題，每題10分，滿分10分；用任何程序語言、偽語言或流程圖描述下列算法。1設(shè)計(jì)一個(gè)算法，將一順序棧中的元素依次取出，并打印元素值。已知順序棧的數(shù)據(jù)結(jié)構(gòu)如下： Typedef struct int data100； int top； SeqStack； 答案及評(píng)分標(biāo)準(zhǔn)：數(shù)據(jù)結(jié)構(gòu)（C語言）答案及評(píng)分標(biāo)準(zhǔn)一 單項(xiàng)選擇題：（2×10）12345678910BDCACADADA二 判斷題：(1×10)12345678910××××三 填空題：（3×10）1.集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)2.一對(duì)一、一對(duì)多、多對(duì)多3.494.25.n（n-1）/2、 n（n-1）6.鄰接矩陣、鄰接表、逆鄰接表7.38.鏈?zhǔn)?.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學(xué)年第二學(xué)期期末試題數(shù)據(jù)結(jié)構(gòu)（C語言