數(shù)據(jù)結(jié)構(gòu)(本)

1、任務(wù)一一、單項(xiàng)選擇題（每小題3 分，共 60 分）把數(shù)據(jù)存儲到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為（） 。A. 給相關(guān)變量分配存儲單元B. 物理結(jié)構(gòu)C. 算法的具體實(shí)現(xiàn)D. 邏輯結(jié)構(gòu)下列說法中，不正確的是（） 。A. 數(shù)據(jù)元素是數(shù)據(jù)的基本單位B. 數(shù)據(jù)可有若干個(gè)數(shù)據(jù)元素構(gòu)成C. 數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)識單位D. 數(shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成一個(gè)存儲結(jié)點(diǎn)存儲一個(gè)（） 。A. 數(shù)據(jù)元素B. 數(shù)據(jù)結(jié)構(gòu)C. 數(shù)據(jù)類型D. 數(shù)據(jù)項(xiàng)數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（） 。A. 邏輯結(jié)構(gòu)B. 存儲結(jié)構(gòu)C. 物理結(jié)構(gòu)D. 物理和存儲結(jié)構(gòu)在線性表的順序結(jié)構(gòu)中，以下說法正確的是（） 。

2、A. 邏輯上相鄰的元素在物理位置上不一定相鄰B. 進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高C. 數(shù)據(jù)元素是不能隨機(jī)訪問的D. 邏輯上相鄰的元素在物理位置上也相鄰對鏈表 , 以下敘述中正確的是（） 。A. 可以通過下標(biāo)對鏈表進(jìn)行直接訪問B. 結(jié)點(diǎn)占用的存儲空間是連續(xù)的C. 插入刪除元素的操作一定要要移動(dòng)結(jié)點(diǎn)D. 不能隨機(jī)訪問任一結(jié)點(diǎn)下列的敘述中，不屬于算法特性的是（） 。A. 有窮性B. 可行性C. 輸入性D. 可讀性）有關(guān)。算法的時(shí)間復(fù)雜度與（A. 數(shù)據(jù)結(jié)構(gòu)B. 所使用的計(jì)算機(jī)C. 計(jì)算機(jī)的操作系統(tǒng)D. 算法本身設(shè)有一個(gè)長度為n 的順序表，要在第i 個(gè)元素之前（也就是插入元素作為新表的第i 個(gè)元素）

3、，插入一個(gè)元素，則移動(dòng)元素個(gè)數(shù)為（） 。A. iB. n-i+1C. n-iD. n-i-1設(shè)有一個(gè)長度為n 的順序表，要?jiǎng)h除第i 個(gè)元素移動(dòng)元素的個(gè)數(shù)為（） 。A. n-i-1B. iC. n-iD. n-i+1在一個(gè)單鏈表中，p、 q 分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且 q 所指結(jié)點(diǎn)是p 所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q 所指結(jié)點(diǎn)，可用語句（） 。A. q->next=NULLB. p->next=qC. p=q->nextD. p->next=q->next在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（）。A. p=s->nextB. p-&g

4、t;next=s->next;C. p->next= s; s->next= p->nextD. s->next=p->next; p->next=s;非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿足（）（設(shè)頭指針為head,指針p指向尾結(jié)點(diǎn)）。A. p= headB. p->next=headC. p=NULLD. p->next=NULL鏈表不具有的特點(diǎn)是（） 。A. 可隨機(jī)訪問任一元素B. 邏輯上相鄰的元素在物理位置上不一定相鄰C. 不必事先估計(jì)存儲空間D. 插入刪除不需要移動(dòng)元素帶頭結(jié)點(diǎn)的鏈表為空的判斷條件是（） （設(shè)頭指針為head） 。A. he

5、ad!=NULLB. head->next=NULLC. head =NULLD. head->next=head在一個(gè)長度為n 的順序表中為了刪除第5 個(gè)元素，由第6 個(gè)元素開始從后到前依次移動(dòng)了15 個(gè)元素。則原順序表的長度為（） 。A. 25B. 21C. 19D. 20有關(guān)線性表的正確說法是（） 。A. 除了一個(gè)和最后一個(gè)元素外，其余元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼B. 每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼C. 線性表至少要求一個(gè)元素D. 表中的元素必須按由小到大或由大到下排序向一個(gè)有127 個(gè)元素的順序表中插入一個(gè)新元素，并保持原來的順序不變，平均要移動(dòng)（）

6、個(gè)元素。A. 63.5B. 7C. 63D. 8一個(gè)順序表第一個(gè)元素的存儲地址是90，每個(gè)元素的長度為2，則第6 個(gè)元素的地址是（） 。A. 98B. 102C. 100D. 106在一個(gè)不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p、 q 分別指向表中第一個(gè)結(jié)點(diǎn)和尾結(jié)點(diǎn)，現(xiàn)要?jiǎng)h除第一個(gè)結(jié)點(diǎn)，且p、q仍然分別指向新表中第一個(gè)結(jié)點(diǎn)和尾結(jié)點(diǎn)?？捎玫恼Z句是p=p->next;和（）。A. p=q->nextB. q->next=pC. p->next=q D. q=p二、判斷題（每小題 2 分， 14 題，共 28 分）數(shù)據(jù)元素可以有一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成。V數(shù)據(jù)元素之間的抽象關(guān)系稱為物理結(jié)構(gòu)。

7、x數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為邏輯結(jié)構(gòu)。x數(shù)據(jù)的邏輯結(jié)構(gòu)是與存儲該結(jié)構(gòu)的計(jì)算機(jī)相關(guān)的。x數(shù)據(jù)結(jié)構(gòu)中，元素之間存在多對多的關(guān)系稱為樹狀結(jié)構(gòu)。x通常可以把一本含有不同章節(jié)的書的目錄結(jié)構(gòu)抽象成線性結(jié)構(gòu)。x通?？梢园涯吵鞘兄懈鞴徽军c(diǎn)間的線路圖抽象成樹型結(jié)構(gòu)。x設(shè)有一個(gè)不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext,指針p指向尾結(jié)點(diǎn)，現(xiàn)要使 p指向第一個(gè)結(jié)點(diǎn)，可用語句 p=p->next;。V設(shè)有一個(gè)單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext,頭指針為head, p指向尾結(jié)點(diǎn)，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句p->next=head 。 V設(shè)有一個(gè)單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ex

8、t,頭指針為head,指針p指向表中某結(jié)點(diǎn)，若邏輯表達(dá)式p->next=head;的結(jié)果為真，則 p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)。,要在一個(gè)單向鏈表中p所指向的結(jié)點(diǎn)之后插入一個(gè)s所指向的新結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext,可執(zhí)行 p->next=s; s->next= p->next;的操作。x要在一個(gè)單向鏈表中刪除p所指向的結(jié)點(diǎn)，已知q指向p所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)?next,則可執(zhí)行 q->next= p->next; V要在一個(gè)帶頭結(jié)點(diǎn)的單向循環(huán)鏈表中刪除頭結(jié)點(diǎn)，得到一個(gè)新的不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，若結(jié)點(diǎn) 的指針域?yàn)?next,頭指針為

9、 head,尾指針為 p,則可執(zhí)行 head=head-> next; p->next=head ；。V設(shè)有一個(gè)單向循環(huán)鏈表，頭指針為head,鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext, p指向尾結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若要?jiǎng)h除尾結(jié)點(diǎn)，得到一個(gè)新的單向循環(huán)鏈表，可執(zhí)行操作p->next=head ；。,三、程序填空題(每小題6分，共12分。請點(diǎn)擊正確選項(xiàng)，然后拖拽至相應(yīng)的方框上)設(shè)線性表以不帶頭結(jié)點(diǎn)的單向鏈表存儲，鏈表頭指針為head,以下程序的功能是輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)域data,完成程序中空格部分。#define NULL 0void main() NODE *head ,*p ;p

10、=head; /*p為工作指針*/printfCHdW, p->data 寸 p=p->next 9 Jwllile pl=NULL 3 ;設(shè)有一個(gè)頭指針為 head的不帶頭結(jié)點(diǎn)單向鏈表，p、q是指向鏈表中結(jié)點(diǎn)類型的指針變量，p指向鏈表中結(jié)點(diǎn)a,(設(shè)鏈表中沒有結(jié)點(diǎn)的數(shù)據(jù)域與結(jié)點(diǎn)a的數(shù)據(jù)域相同)，寫出相關(guān)語句(1)使該單向鏈表成為單向循環(huán)鏈表(2)插入結(jié)點(diǎn)s,使它成為a結(jié)點(diǎn)的直接前驅(qū)q=p x=p->datawhile q->next!=NULL y ) q=q->next:q-#next=h 巳己 d:q=p; p=p->n«xt;while(p-

11、>datal=x)q=p：p=p->next y&->rext=p;q->next=s ”任務(wù)二、單項(xiàng)選擇題（每小題 2分，共50分）若讓元素1,2, 3依次進(jìn)棧，則出棧順序不可能為（）。A. 3, 1, 2B. 3, 2, 1C. 2, 1, 3D. 1 , 3, 2一個(gè)隊(duì)列的入隊(duì)序列是1, 2, 3, 4。則隊(duì)列的輸出序列是（）。A.4, 3, 2, 1B. 1, 4, 3, 2C. 1, 2, 3, 4D.3, 2, 4, 1向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)（）。A.同時(shí)進(jìn)行B.先存入元素，再移動(dòng)棧頂指針C.先移動(dòng)棧頂指針，再存入元素D.先后次序無關(guān)緊要在一個(gè)

12、棧頂指針為top的鏈棧中，將一個(gè)p指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行（）。A. top->next=p;B. p->next=top ->next;top ->next=p;C. p->next=top ->next;top=top ->next;D. p->next=top;top=p;在一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用 x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（）。A. x=top ->data;B. top=top ->next;x=top->data;C. x=top;top=top ->next;D. x=top->

13、;data;top=top ->next;判斷一個(gè)順序隊(duì)列（最多元素為m）為空的條件是（）。A. front=rearB. front=rear+1C. rear=mD. rear=m-1判斷一個(gè)循環(huán)隊(duì)列為滿的條件是（）。A. rear%MaxSize= =frontB. rear=MaxSizeC. （rear+1）%MaxSize=frontD. front=rear+1判斷棧滿（元素個(gè)數(shù)最多n個(gè)）的條件是（A. top=n-1B. top=0C. top!=0D. top=-1設(shè)有一個(gè)20階的對稱矩陣A （第一個(gè)元素為a1,1）,采用壓縮存儲的方式，將其下三角部分以行序?yàn)橹餍虼鎯Φ?/p>

14、一維數(shù)組B 中（數(shù)組下標(biāo)從1 開始） ， 則矩陣元素a6,2 在一維數(shù)組B 中的下標(biāo)是（） 。A. 23B. 17C. 28D. 21在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)中，而打印機(jī)則從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應(yīng)該是一個(gè)（）結(jié)構(gòu)。A. 隊(duì)列B. 線性表C. 堆棧D. 數(shù)組一個(gè)遞歸算法必須包括（） 。A. 迭代部分B. 遞歸部分C. 終止條件和迭代部分D. 終止條件和遞歸部分在一個(gè)鏈隊(duì)中，假設(shè)f 和 r 分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（） 。A. r=f->next;B. f=f->next;C.

15、 r=r->next;D. f=r->next;在一個(gè)鏈隊(duì)中，假設(shè)f 和 r 分別為隊(duì)頭和隊(duì)尾指針，則插入s 所指結(jié)點(diǎn)的運(yùn)算為（） 。A. s->next=r;r=s;B. r->next=s;r=s;C. s->next=f;f=s;D. f->next=s;f=s;數(shù)組a經(jīng)初始化char a = "English" ;a7中存放的是（）。A. "h"B. 變量hC. 字符hD. 字符串的結(jié)束符設(shè)主串為" ABcCDABcdEFaBc 以下模式串能與主串成功匹配的是（）。A. AbcB. ABCC. BCd

16、D. Bcd字符串 a1="AEIJING", a2="AEI", a3="AEFANG", a4="AEFI"中最大的是（）。A. a3B. a1C. a2D. a4兩個(gè)字符串相等的條件是（） 。A. 兩串的長度相等B. 兩串的長度相等，并且對應(yīng)位置上的字符相同C. 兩串的長度相等，并且兩串包含的字符相同D. 兩串包含的字符相同一維數(shù)組A 采用順序存儲結(jié)構(gòu)，每個(gè)元素占用6 個(gè)字節(jié)，第6 個(gè)元素的存儲地址為100，則該數(shù)組的首地址是（） 。A. 90B. 70C. 64D. 28一個(gè)非空廣義表的表頭（） 。A. 可

17、以是子表或原子B. 不可能是原子C. 只能是原子D. 只能是子表對稀疏矩陣進(jìn)彳T壓縮存儲，可采用三元組表，一個(gè)10行8列的稀疏矩陣 A,其相應(yīng)的三元組表共有6個(gè)元素，矩陣A 共有（）個(gè)零元素。A. 72B. 8C. 10D. 74對稀疏矩陣進(jìn)彳T壓縮存儲，可采用三元組表，一個(gè) 10行8列的稀疏矩陣 A共有73個(gè)零元素，A的右下角元素為 6，其相應(yīng)的三元組表中的第7 個(gè)元素是（） 。A. （ 10， 8， 7）B. （ 7， 10， 8）C. （ 7， 8， 10）D. （ 10， 8， 6）對一個(gè)棧頂指針為top 的鏈棧進(jìn)行入棧操作，通過指針變量p 生成入棧結(jié)點(diǎn)，并給該 結(jié)點(diǎn)賦值a， 則執(zhí)行

18、:p=（struct node *）malloc（sizeof（struct node）;p ->data=a;和 （）。A. top->next=p;p=top;B. top=top ->next;p=top;C. p->next=top;top=p;D. p->next=top;p=top;頭指針為head 的帶頭結(jié)點(diǎn)的單向鏈表為空的判定條件是（）為真。A. head->next!=NULLB. head->next=NULLC. head->next!=NULLD. head=NULL設(shè)有一個(gè)對稱矩陣 A,采用壓縮存儲的方式，將其下三角部分

19、以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從 1 開始） ， B 數(shù)組共有55 個(gè)元素,則該矩陣是（）階的對稱矩陣。A. 10B. 15C. 20D. 5數(shù)組a經(jīng)初始化char a = "English" ;a1中存放的是（）。A. 字符 nB. "n"C. "E"D. 字符 E二、判斷題（每小題2 分， 16 題，共 32 分 ）設(shè)有一個(gè)鏈棧，棧頂指針為hs,現(xiàn)有一個(gè)s所指向的結(jié)點(diǎn)要入棧，則可執(zhí)行操作。hs=s; x設(shè)有一個(gè)非空的鏈棧，棧頂指針為hs,要進(jìn)行出棧操作，用x保存出棧結(jié)點(diǎn)的值，棧結(jié)點(diǎn)的指針域?yàn)閚ext,貝U可執(zhí)行 hs=h

20、s->next ;x=hs->data;x有一個(gè)鏈棧，棧頂指針為h,現(xiàn)有一個(gè)p所指向的結(jié)點(diǎn)要入棧，則可執(zhí)行操作p->next=h; V設(shè)有一個(gè)非空的鏈棧，棧頂指針為hs,要進(jìn)行出棧操作，用x保存出棧結(jié)點(diǎn)的值，棧結(jié)點(diǎn)的指針域?yàn)閚ext,數(shù)據(jù)域?yàn)?data,則可執(zhí)行 hs= hs->next; x= hs->data; x在一個(gè)鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext,則插入所指結(jié)點(diǎn)的操作為r->next=s; r=s; V在一個(gè)鏈隊(duì)中，f 和 r 分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext， s 指向一個(gè)要入隊(duì)的結(jié)點(diǎn)，則入隊(duì)操作為 r=

21、s; r->next=s; x在一個(gè)不帶頭結(jié)點(diǎn)白非空鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閐ata,指針域?yàn)閚ext,若要進(jìn)行出隊(duì)操作，并用變量x存放出隊(duì)元素的數(shù)據(jù)值，則相關(guān)操作為x=f->data; f=f->next; V對稀疏矩陣進(jìn)彳T壓縮存儲，可采用三元組表，一個(gè)6行7列的稀疏矩陣 A相應(yīng)的三元組表共有 8個(gè)元素，則矩陣A共有34個(gè)零元素。V循環(huán)隊(duì)列的最大存儲空間為MaxSize,隊(duì)頭指針為f,隊(duì)尾指針為r,當(dāng)（r+1） %MaxSize=f時(shí)表明隊(duì)列已滿。V循環(huán)隊(duì)列的隊(duì)頭指針為f,隊(duì)尾指針為r,當(dāng)r= =f時(shí)表明隊(duì)列已滿。x空串的長度是0;空格串的長度

22、是空格字符的個(gè)數(shù)。V對稀疏矩陣進(jìn)行壓縮存儲，矩陣中每個(gè)非零元素對應(yīng)的三元組包括該元素的行下標(biāo)、列下標(biāo)、和非零元素值三項(xiàng)信息。V循環(huán)隊(duì)列的引入，目的是為了克服假上溢。V設(shè)有n階對稱矩陣A,用一維數(shù)組s壓縮存儲A的下三角元素，s的下標(biāo)從零開始，元素 s26相應(yīng)于A中 的元素為a 7,5。X循環(huán)隊(duì)列的最大存儲空間為MaxSize=6,采用少用一個(gè)元素空間以有效的判斷?？栈驐M，若隊(duì)頭指針front=4 ,當(dāng)隊(duì)尾指針rear=3時(shí)隊(duì)滿。V循環(huán)隊(duì)列的最大存儲空間為 MaxSize=6,采用少用一個(gè)元素空間以有效的判斷棧空或棧滿，若隊(duì)頭指 針front=4 ,隊(duì)尾指針rear=3時(shí)，隊(duì)列中共有 5個(gè)元素。

23、V三、程序選擇填空題（每小題 9分，共18分。請點(diǎn)擊正確選項(xiàng)，然后拖拽至相應(yīng)的方框上） 以下函數(shù)為鏈棧的進(jìn)棧操作，x是要進(jìn)棧的結(jié)點(diǎn)的數(shù)據(jù)域，top為棧頂指針struct node ElemType data;struct node *next;struct node *top ;void Push（ElemType x）struct nodeA sizeof (siruct node)struct nodc*)nnalocy ;p-neyt=lapIgp印IQ front、rear分別鏈隊(duì)列的隊(duì)頭、隊(duì)尾指以下函數(shù)為鏈隊(duì)列的入隊(duì)操作，x為要入隊(duì)的結(jié)點(diǎn)的數(shù)據(jù)域的值,針struct node Ele

24、mType data;struct node*next;struct node*front , *rear;void InQueue(ElemType x)struct node *p;VVIU 1 r T WUUUftILJG_| n I J pc Nstruct node(sizeoftstruct node)p= (struct node* malloc;p->ata=x.PWER re3r->nePrear-3 ：任務(wù)三、單項(xiàng)選擇題（每小題 2分，共38分）假定一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15,單分支結(jié)點(diǎn)數(shù)為 30,則葉子結(jié)點(diǎn)數(shù)為（A. 16B. 17C. 15D. 47二

25、叉樹第k層上最多有（）個(gè)結(jié)點(diǎn)。A 21cl B 2h->C. 2kD 2k-1!將含有150個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點(diǎn)進(jìn)行編號，根結(jié)點(diǎn)的編號為 1,則編號為69的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為（）。A. 33B. 34C. 36D. 35如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹的帶權(quán)路徑長度最小，則該樹稱為（A.完全二叉樹B.平衡二叉樹C.哈夫曼樹D.二叉樹在一棵度具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（A. 33B. 31C. 32D. 16）個(gè)結(jié)點(diǎn)。一棵完全二叉樹共有 6層，且第6層上有6個(gè)結(jié)點(diǎn)，該樹共有A. 31B. 72C. 38D. 37利用3、6、8

26、、12這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹中所有葉子結(jié)點(diǎn)中的最長帶權(quán)路 徑長度為（）。A. 16B. 12C. 30D. 18在一棵樹中，（）沒有前驅(qū)結(jié)點(diǎn)。A.葉結(jié)點(diǎn)B.空結(jié)點(diǎn)C.樹根結(jié)點(diǎn)D.分支結(jié)點(diǎn)設(shè)一棵采用鏈?zhǔn)酱鎯Φ亩鏄?，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2,該樹結(jié)點(diǎn)中共有20個(gè)指針域?yàn)榭眨瑒t該樹有（）個(gè)葉結(jié)點(diǎn)。A. 21B. 10C. 9D. 22在一個(gè)圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的（）倍。A. 1B. 2C. 4D. 1/2鄰接表是圖的一種（）。A.鏈?zhǔn)酱鎯Y(jié)構(gòu)B.順序存儲結(jié)構(gòu)C.索引存儲結(jié)構(gòu)D.散列存儲結(jié)構(gòu)圖的深度優(yōu)先遍歷算法類似于二叉樹的（）遍歷。A.層次B.先

27、序C.后序D.中序已知下圖所示的一個(gè)圖，若從頂點(diǎn)V1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。A. V1V2V4 V8V5V3V6V7B. V1V2 V4 V8 V3 V5 V6 V7C. V1V3V6V7V2V4V5V8D. V1V2V4V5V8V3V6V7已知如下圖所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為)A. aebcfdB. abecdfC. aedfcbD. aecbdf圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（A. 一對多）的關(guān)系。B. 一對一C.每一個(gè)元素都有一個(gè)且只有一個(gè)直接前驅(qū)和一個(gè)直接后繼D.多對多在一棵二叉樹中，若編

28、號為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號為（）。A. 2i+2B. 2i+1C. 2i-1D. 2i一棵具有16個(gè)結(jié)點(diǎn)的完全二叉樹，共有（）層。（設(shè)根結(jié)點(diǎn)在第一層）A. 6B. 4C. 7D. 5對二叉排序樹進(jìn)行（）遍歷，可以使遍歷所得到的序列是有序序列。A.中序B.前序C.按層次D.后序已知一個(gè)圖的邊數(shù)為 m,則該圖的所有頂點(diǎn)的度數(shù)之和為（）。A. m/2B. mC. 2mD. 2m+1二、判斷題（每小題1分，共10分）一棵二叉樹的葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）數(shù)為 5,單分支結(jié)點(diǎn)數(shù)為2,該樹共有11個(gè)結(jié)點(diǎn)。V一棵有14個(gè)結(jié)點(diǎn)的完全二叉樹，則它的最高層上有 7個(gè)結(jié)點(diǎn)。V一棵二叉樹有6個(gè)葉結(jié)點(diǎn)，則該樹總

29、共有 11個(gè)結(jié)點(diǎn)。X根據(jù)搜索方法的不同，圖的遍歷有.先序；中序；后序三種方法。X對于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)中共有n-1個(gè)指針域空。X設(shè)一棵完全二叉樹， 其最高層上最右邊的葉結(jié)點(diǎn)的編號為奇數(shù)，該葉結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為10,該完全二叉樹一共有 21個(gè)結(jié)點(diǎn)。V設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點(diǎn)的編號為偶數(shù)，該葉結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為9,該完全二叉樹一共有19個(gè)結(jié)點(diǎn)。X按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有深度優(yōu)先遍歷和深度優(yōu)先遍兩種方法。x一棵有8個(gè)權(quán)重值構(gòu)造的哈夫曼數(shù)，共有17個(gè)結(jié)點(diǎn)。X一棵有7個(gè)葉結(jié)點(diǎn)的二叉樹，其 1度結(jié)點(diǎn)數(shù)的個(gè)數(shù)為2,則該樹共有15個(gè)結(jié)

30、點(diǎn)。，三、程序填空題（每空 6分，共12分。請點(diǎn)擊正確選項(xiàng)，然后拖拽至相應(yīng)的方框上）以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right,數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。完成程序中空格部分。YOUInorder (struct RTrepNide(rf( STI=MULL)(Inord er(BT-> left);Inorder但T-> right)“利月上述程序?qū)ψ髨D在行后序遍歷.知甲是printffcVBT->data' V以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右

31、指針域分別為left和right,數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。void inarler （stn .cl RTreeNixieff（BT!-NJLLXInorder）norder（BT.>矛屁上逑程宗時(shí)古國祖行中序遍歷，結(jié)果是Id b.e a rt .四、綜合應(yīng)用題（每小題 8分，5題，共40分）332正逢花號直州郎祖擊&口附F標(biāo)舊3怎我333iFW五號由：0天甲的&口暗霸弓34TWJtSaoo&(P 節(jié)&口吩Y,牛為葉卓跑笈，蜘國 理勝人景能.汪快打帶郵徑匕度為5 ，A RdE6S C 62 D 66力 蒼卓土的1用谷耗超支員市巧立： 5

32、.A010 B0101 GOOD 0.01111）以2.3,*,7".刪期tW的慢,杓r糜*用出融璃曲錮闋 艮才 力A.6E 6.60 C 62 口 S7<23"重值力/神鰭點(diǎn)的鹿X曼闌謝：廣# 5 *A.00010. 1110 C.OOi D 110（O百噴二叉積的后序遍歷序列是改bf甲序調(diào)歷第幄*二,詼二叉樹的根潔點(diǎn)是7等5A. e B. t C- b D. a.一為序痂于以更是l i八A e;bhc,d.a o. c.a,d.e c a n.a.ejc. o a c toe,隹言聲正蛹m中土的分= 度S.DO醛F目<t>日噤二更樹的內(nèi)序造質(zhì)翎是皿叫

33、中序迫歷序是Uk*,該二Xtt曲賭點(diǎn)是匚，3、& e&.C C. & D. a（2 ）后fi場。弛先A i y *A «,d.b.c,a B, *ab,dC, d,b.d.e.c0前工b工島即36 正衲E三.0口* 印.00才<0 源定粗隸值3如171 11 j落，和，力上特點(diǎn)，彈立T哈天色材茂樹的中庫遍田芹9為e。/A " 11T 2Sf 6, ?T 5Sf 30, ML 1S7 相，25B 5> 11* 6t 萬.IT,沏 90j 1L 監(jiān)，跖,25Cl5, Ilj % 衰，tOL 猛 弛 17, 18, 43, 25D &,

34、 IL . 2», R. 5S* 30, 10b IE, 25,二(2)也亙值的他口葉籠與弗夫受：J D t A 1001 H 011 C 1X)1 D D001任務(wù)四一、單項(xiàng)選擇題（每小題2分，共40分）對線性表進(jìn)行二分查找時(shí)，要求線性表必須（）。A.以鏈接存儲方式B.以鏈接存儲方式，且數(shù)據(jù)元素有序C.以順序存儲方式D.以順序存儲方式，且數(shù)據(jù)元素有序采用順序查找方法查找長度為n 的線性表時(shí)，每個(gè)元素的平均查找長度為（） 。A. （n-1）/2B. nC. （n+1）/2D. n/2有一個(gè)長度為10 的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（） 。A

35、. 31/10B. 29/10C. 29/9D. 26/10已知一個(gè)有序表為11,22,33,44,55,66,77,88,99，則順序查找元素55 需要比較（）次。A. 5B. 6C. 4D. 3有數(shù)據(jù)53,30,37,12,45,24,96， 從空二叉樹開始逐個(gè)插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，應(yīng)該選擇的序列是（） 。A. 12,24,30,37,45,53,96B. 30,24,12,37,45,96,53C. 37,24,12,30,53,45,96D. 45,24,53,12,37,96,30對于順序存儲的有序表5,12,20,26,37,42,46,50,64 ， 若采用折

36、半查找，則查找元素26 的比較次數(shù)是（） 。A. 4B. 6C. 5D. 3在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄初始排列秩序無關(guān)的是（） 。A. 希爾排序B. 冒泡排序C. 直接插入排序D. 直接選擇排序從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱為（） 。A. 插入排序B. 選擇排序C. 歸并排序D. 交換排序 依次將每兩個(gè)相鄰的有序表合并成一個(gè)有序表的排序方法稱為（A. 插入排序B. 選擇排序C. 歸并排序D. 交換排序當(dāng)兩個(gè)元素出現(xiàn)逆序的時(shí)候就交換位置，這種排序方法稱為（） 。A. 交換排序B. 插入排序C. 歸并排序D.

37、選擇排序每次把待排序的區(qū)間劃分為左、右兩個(gè)子區(qū)間，其中左區(qū)間中記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄的關(guān)鍵字，右區(qū)間中記錄的關(guān)鍵字均大于等于基準(zhǔn)記錄的關(guān)鍵字，這種排序稱為（） 。A. 快速排序B. 歸并排序C. 堆排序D. 插入排序一組記錄的關(guān)鍵字序列為（46,20,30,79， 56， 38， 40， 84,90,110） ，利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（） 。A. 40， 20,30,38，46，56，79，84,90,110B. 20,30 38， 40，46，56，79，84,90,100C. 30,20,40， 38，46，84，56，79,90,100D.

38、20,30,40， 38，46，79，56，84,90,100在有序表10,14，34，43，47，64， 75， 80，90中，用折半查找法查找值 80 時(shí)，經(jīng)（）次比較后查找成功。A. 3B. 4C. 2D. 5對序列（49， 38， 65， 97， 76， 13， 47， 50）采用直接插入排序法進(jìn)行排序，要把第七個(gè)元素47 插入到已排序中，為尋找插入的合適位置需要進(jìn)行（）次元素間的比較。A. 3B. 5C. 4D. 6排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為 （）排序。A. 插入B. 選擇C. 快速D. 歸并一組記錄的關(guān)鍵字序列為（26

39、， 59， 36， 18， 20， 25） ，利用堆排序的方法建立的初始小根堆為（A.26，59，36，18，20，25B.18，20，25，59，26，36C.26，18，59，20，36，25D.18，20，36，59，26，25一組記錄的關(guān)鍵字序列為（25， 48， 16， 35， 79， 82， 23， 40， 36， 72） ，其中，含有5 個(gè)長度為2 的有序表，按歸并排序的方法對該序列進(jìn)行一趟歸并后的結(jié)果為（） 。A.16，25，35，48，23，40，79，82，36，72B.16，25，35，48，79，23，36，40，82，72C.16，25，48，35，79，82，23，

40、36，40，72D.16，25，35，48，79，82，23，36，40，7210 個(gè)數(shù)據(jù)元素為（54，28，16， 34， 73，62，95，60，26，43），對該數(shù)列從小到大排序，經(jīng)過一趟）。A. 28，16，34，54，62，73，60，26，43，95B. 16，28，34，54，73，62，60，26，43，95C. 28，16，34，54，62，60，73，26，43，95D. 16，28，34，54，62，60，73，26，43，95一組記錄的關(guān)鍵字序列為（46， 79， 56， 38， 40， 84） ，利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（） 。A.

41、40，38，46，84，56，79B.40，38，46，56，79，84C.38，40，46，56，79，84D.40，38，46，79，56，84一組記錄的關(guān)鍵字序列為（80,57,41,39,46,47） ，利用堆排序（堆頂元素是最小元素）的方法建立的初始堆為（） 。A. 41， 39， 46， 47， 57， 80B. 39， 47， 46， 80， 41， 57C. 39，80，46，47，41，57D. 39，46，41，57，80，47二、程序填空題（每題10 分， 2 題，共 20 分。請點(diǎn)擊正確選項(xiàng)，然后拖拽至相應(yīng)的方框上）以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點(diǎn)的指針，否則，返回值是指向樹結(jié)點(diǎn)的結(jié)構(gòu)指針p （查找成功p指向查到的樹結(jié)點(diǎn)，不成功 p指向?yàn)镹ULL）完成程序中的空格 typedef struct Bnode int key;structBnode *left;structBnode *right; Bnode;Bnode *BSearch（Bnode *bt, int k）/* bt 用于接收二叉排序樹的根結(jié)點(diǎn)的指針，k 用以接收要查找的關(guān)鍵字*/ Bn ode 'p：Iftbt NULL y )remm (M)：P-bl.(ifiK<p->ksy i以下程序是折半插入排序的算法設(shè)待排序的記錄序列存放在a