1、國(guó)家開(kāi)放大學(xué)數(shù)據(jù)結(jié)構(gòu)（本）形考作業(yè)1-4參考答案形考作業(yè)1一、單項(xiàng)選擇題（每小題3分，共60分）1.把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為（ ）。A. 算法的具體實(shí)現(xiàn)B. 物理結(jié)構(gòu)C. 邏輯結(jié)構(gòu)D. 給相關(guān)變量分配存儲(chǔ)單元2.下列說(shuō)法中，不正確的是（ ）。A. 數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)識(shí)單位B. 數(shù)據(jù)元素是數(shù)據(jù)的基本單位C. 數(shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成D. 數(shù)據(jù)可有若干個(gè)數(shù)據(jù)元素構(gòu)成3.一個(gè)存儲(chǔ)結(jié)點(diǎn)存儲(chǔ)一個(gè)（ ）。A. 數(shù)據(jù)結(jié)構(gòu)B. 數(shù)據(jù)元素C. 數(shù)據(jù)類(lèi)型D. 數(shù)據(jù)項(xiàng)4.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（ ）。A. 物理和存儲(chǔ)結(jié)構(gòu)B. 物理結(jié)構(gòu)C. 邏輯結(jié)

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

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

4、一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（ ）。A. p->next=s->next;B. p->next= s; s->next= p->nextC. p=s->nextD. s->next=p->next; p->next=s;13.非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿足（ ）（設(shè)頭指針為head，指針p指向尾結(jié)點(diǎn)）。A. p->next=headB. p=NULLC. p->next=NULLD. p= head14.鏈表不具有的特點(diǎn)是（ ）。A. 邏輯上相鄰的元素在物理位置上不一定相鄰B. 插入刪除不需要移動(dòng)元素C. 不必事先估計(jì)存儲(chǔ)空間D.

5、 可隨機(jī)訪問(wèn)任一元素15.帶頭結(jié)點(diǎn)的鏈表為空的判斷條件是（ ）（設(shè)頭指針為head）。A. head =NULLB. head!=NULLC. head->next=NULLD. head->next=head16.在一個(gè)長(zhǎng)度為n的順序表中為了刪除第5個(gè)元素，由第6個(gè)元素開(kāi)始從后到前依次移動(dòng)了15個(gè)元素。則原順序表的長(zhǎng)度為（ ）。A. 20B. 25C. 21D. 1917.有關(guān)線性表的正確說(shuō)法是（ ）。A. 線性表至少要求一個(gè)元素B. 表中的元素必須按由小到大或由大到下排序C. 每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼D. 除了一個(gè)和最后一個(gè)元素外，其余元素都有一個(gè)且僅有一個(gè)直接前

6、驅(qū)和一個(gè)直接后繼18.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素，并保持原來(lái)的順序不變，平均要移動(dòng)（ ）個(gè)元素。A. 8B. 63C. 7D. 63.519.一個(gè)順序表第一個(gè)元素的存儲(chǔ)地址是90，每個(gè)元素的長(zhǎng)度為2，則第6個(gè)元素的地址是（ ）。A. 102B. 100C. 106D. 9820. 在一個(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)。可用的語(yǔ)句是p=p->next;和（ ）。A. p->next=qB. p=q->nextC. q=pD. q->next=p二、判斷題（

7、每小題2分，14題，共28分）21.數(shù)據(jù)元素可以有一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成。（）22.數(shù)據(jù)元素之間的抽象關(guān)系稱為物理結(jié)構(gòu)。（×）23.數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為邏輯結(jié)構(gòu)。（×）24.數(shù)據(jù)的邏輯結(jié)構(gòu)是與存儲(chǔ)該結(jié)構(gòu)的計(jì)算機(jī)相關(guān)的。（×）25.數(shù)據(jù)結(jié)構(gòu)中,元素之間存在多對(duì)多的關(guān)系稱為樹(shù)狀結(jié)構(gòu)。（×）26.通常可以把一本含有不同章節(jié)的書(shū)的目錄結(jié)構(gòu)抽象成線性結(jié)構(gòu)。（×）27.通常可以把某城市中各公交站點(diǎn)間的線路圖抽象成樹(shù)型結(jié)構(gòu)。（×）28.設(shè)有一個(gè)不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，指針p指向尾結(jié)點(diǎn)，現(xiàn)要使p指向第一個(gè)結(jié)點(diǎn)，可

8、用語(yǔ)句p=p->next;。（）29.設(shè)有一個(gè)單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，p指向尾結(jié)點(diǎn)，為了使該單向鏈表改為單向循環(huán)鏈表，可用語(yǔ)句p->next=head。（）30.設(shè)有一個(gè)單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，指針p指向表中某結(jié)點(diǎn)，若邏輯表達(dá)式p->next=head;的結(jié)果為真，則p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)。（）31.要在一個(gè)單向鏈表中p所指向的結(jié)點(diǎn)之后插入一個(gè)s所指向的新結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，可執(zhí)行 p->next=s; s->next= p->next；的操作。（×）32.要在一個(gè)單向鏈表中

9、刪除p所指向的結(jié)點(diǎn)，已知q指向p所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，則可執(zhí)行q->next= p->next；（）33.要在一個(gè)帶頭結(jié)點(diǎn)的單向循環(huán)鏈表中刪除頭結(jié)點(diǎn)，得到一個(gè)新的不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，若結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，尾指針為p，則可執(zhí)行head=head-> next; p->next=head；。（）34.設(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分，

10、共12分。請(qǐng)點(diǎn)擊正確選項(xiàng)，然后拖拽至相應(yīng)的方框上）35.設(shè)線性表以不帶頭結(jié)點(diǎn)的單向鏈表存儲(chǔ)，鏈表頭指針為head，以下程序的功能是輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)域data,完成程序中空格部分。 #define NULL 0 void main( ) NODE *head ,*p ; p=head; /*p為工作指針*/ do printf(“%dn”,（p>data）; （p=p>next）; while（p!=NULL）; p>datap=p>nextp!=NULL36.設(shè)有一個(gè)頭指針為head的不帶頭結(jié)點(diǎn)單向鏈表，p、q是指向鏈表中結(jié)點(diǎn)類(lèi)型的指針變量，p指向鏈表中結(jié)點(diǎn)a,

11、 （設(shè)鏈表中沒(méi)有結(jié)點(diǎn)的數(shù)據(jù)域與結(jié)點(diǎn)a的數(shù)據(jù)域相同）,寫(xiě)出相關(guān)語(yǔ)句 (1)使該單向鏈表成為單向循環(huán)鏈表 (2)插入結(jié)點(diǎn)s,使它成為a結(jié)點(diǎn)的直接前驅(qū)q=p; x=p->data;while （q>next!=NULL）q=q->next;q->next=head;q=p; p=p->next;while(p->data!=x) q=p;（p=p>next）s->next=p;（q>next=s） p=p>nextq>next=sq>next!=NULL形考作業(yè)2一、單項(xiàng)選擇題（每小題2分，共50分）1.若讓元素1，2，3依次進(jìn)

12、棧，則出棧順序不可能為（ ）。A. 1，3，2B. 3，1，2C. 3，2，1D. 2，1，32.一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4。則隊(duì)列的輸出序列是（ ）。A. 3，2，4，1B. 1，2，3，4C. 1，4，3，2D. 4，3，2，13.向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)（ ）。A. 先后次序無(wú)關(guān)緊要B. 同時(shí)進(jìn)行C. 先存入元素，再移動(dòng)棧頂指針D. 先移動(dòng)棧頂指針，再存入元素4.在一個(gè)棧頂指針為top的鏈棧中，將一個(gè)p指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行（ ）。A. p->next=top->next;top=top->next;B. top->next=p;C. p->

13、next=top->next;top->next=p;D. p->next=top;top=p;5.在一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用 x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（ ）。A. x=top;top=top->next;B. x=top->data;top=top->next;C. x=top->data;D. top=top->next;x=top->data;6.判斷一個(gè)順序隊(duì)列（最多元素為m）為空的條件是（ ）。A. front=rearB. rear=m-1C. rear=mD. front=rear+17.判斷一個(gè)循環(huán)隊(duì)

14、列為滿的條件是（ ）。A. (rear+1)%MaxSize=frontB. front=rear+1C. rear%MaxSize= =frontD. rear=MaxSize8.判斷棧滿（元素個(gè)數(shù)最多n個(gè)）的條件是（ ）。A. top=-1B. top=0C. top=n-1D. top!=09.設(shè)有一個(gè)20階的對(duì)稱矩陣A（第一個(gè)元素為a1,1），采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始）， 則矩陣元素a6,2在一維數(shù)組B中的下標(biāo)是（ ）。A. 23B. 21C. 28D. 1710.在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題時(shí)通常設(shè)置一個(gè)打印數(shù)據(jù)

15、緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入緩沖區(qū)中，而打印機(jī)則從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應(yīng)該是一個(gè)（ ）結(jié)構(gòu)。A. 堆棧B. 線性表C. 數(shù)組D. 隊(duì)列11.一個(gè)遞歸算法必須包括（ ）。A. 遞歸部分B. 終止條件和迭代部分C. 迭代部分D. 終止條件和遞歸部分12.在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（ ）。A. f=f->next;B. r=r->next;C. f=r->next;D. r=f->next;13.在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算為（ ）。A. f->next=s;f=s;B.

16、s->next=r;r=s;C. s->next=f;f=s;D. r->next=s;r=s;14.數(shù)組a經(jīng)初始化char a =“English”;a7中存放的是（ ）。A. 變量hB. 字符hC. "h"D. 字符串的結(jié)束符15.設(shè)主串為“ABcCDABcdEFaBc”，以下模式串能與主串成功匹配的是（ ）。A. AbcB. BcdC. BCdD. ABC16.字符串 a1="AEIJING"，a2="AEI"，a3="AEFANG"，a4="AEFI"中最大的是（ ）。

17、A. a4B. a1C. a3D. a217.兩個(gè)字符串相等的條件是（ ）。A. 兩串包含的字符相同B. 兩串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符相同C. 兩串的長(zhǎng)度相等，并且兩串包含的字符相同D. 兩串的長(zhǎng)度相等18.一維數(shù)組A采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用6個(gè)字節(jié)，第6個(gè)元素的存儲(chǔ)地址為100，則該數(shù)組的首地址是（ ）。A. 70B. 28C. 90D. 6419.一個(gè)非空廣義表的表頭（ ）。A. 只能是原子B. 可以是子表或原子C. 只能是子表D. 不可能是原子20.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表，一個(gè)10 行8列的稀疏矩陣A，其相應(yīng)的三元組表共有6個(gè)元素，矩陣A共有（ ）個(gè)零元素。

18、A. 72B. 10C. 74D. 821.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表，一個(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）22.對(duì)一個(gè)棧頂指針為top的鏈棧進(jìn)行入棧操作，通過(guò)指針變量p生成入棧結(jié)點(diǎn)，并給該 結(jié)點(diǎn)賦值a，則執(zhí)行: p=(struct node *)malloc(sizeof(struct node);p->data=a;和（ ）。A. p->next=top;top=p;B. p->next=top;p=to

19、p;C. top=top->next;p=top;D. top->next=p;p=top;23.頭指針為head的帶頭結(jié)點(diǎn)的單向鏈表為空的判定條件是（ ）為真。A. head=NULLB. head->next!=NULLC. head->next!=NULLD. head->next=NULL24.設(shè)有一個(gè)對(duì)稱矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），B數(shù)組共有55個(gè)元素,則該矩陣是（ ）階的對(duì)稱矩陣。A. 20B. 5C. 15D. 1025.數(shù)組a經(jīng)初始化char a =“English”;a1中存放的是

20、（ ）。A. 字符EB. "E"C. "n"D. 字符n二、判斷題（每小題2分，16題，共32分）26.設(shè)有一個(gè)鏈棧，棧頂指針為hs，現(xiàn)有一個(gè)s所指向的結(jié)點(diǎn)要入棧，則可執(zhí)行操作。hs=s；s-> next=hs; （×）27.設(shè)有一個(gè)非空的鏈棧，棧頂指針為hs，要進(jìn)行出棧操作，用x保存出棧結(jié)點(diǎn)的值，棧結(jié)點(diǎn)的指針域?yàn)閚ext，則可執(zhí)行hs=hs->next ;x=hs->data;（）28.有一個(gè)鏈棧，棧頂指針為h，現(xiàn)有一個(gè)p所指向的結(jié)點(diǎn)要入棧，則可執(zhí)行操作p->next=h;和h=p；（）29.設(shè)有一個(gè)非空的鏈棧，棧頂指

21、針為hs，要進(jìn)行出棧操作，用x保存出棧結(jié)點(diǎn)的值，棧結(jié)點(diǎn)的指針域?yàn)閚ext，數(shù)據(jù)域?yàn)閐ata，則可執(zhí)行hs= hs->next; x= hs->data; （×）30. 在一個(gè)鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext，則插入所指結(jié)點(diǎn)的操作為r->next=s；r=s；（）31.在一個(gè)鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext，s指向一個(gè)要入 隊(duì)的結(jié)點(diǎn)，則入隊(duì)操作為r=s；r->next=s；（×）32.在一個(gè)不帶頭結(jié)點(diǎn)的非空鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閐ata，指針域?yàn)閚ext，若要進(jìn)行出隊(duì)

22、操作，并用變量x存放出隊(duì)元素的數(shù)據(jù)值，則相關(guān)操作為x=f->data; f=f->next; （）33.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表，一個(gè)6行7列的稀疏矩陣A相應(yīng)的三元組表共有8個(gè)元素,則矩陣A共有34個(gè)零元素。（）34.循環(huán)隊(duì)列的最大存儲(chǔ)空間為MaxSize，隊(duì)頭指針為f，隊(duì)尾指針為r，當(dāng)（r+1）%MaxSize=f 時(shí)表明隊(duì)列已滿。（）35.循環(huán)隊(duì)列的隊(duì)頭指針為f，隊(duì)尾指針為r，當(dāng)r= =f時(shí)表明隊(duì)列已滿。（×）36.空串的長(zhǎng)度是0；空格串的長(zhǎng)度是空格字符的個(gè)數(shù)。（）37.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的行下標(biāo)、列下標(biāo)、和

23、非零元素值三項(xiàng)信息。（）38.循環(huán)隊(duì)列的引入，目的是為了克服假上溢。（）39.設(shè)有n階對(duì)稱矩陣A，用一維數(shù)組s壓縮存儲(chǔ)A的下三角元素，s的下標(biāo)從零開(kāi)始，元素 s26相應(yīng)于A中的元素為a 7,5。（×）40.循環(huán)隊(duì)列的最大存儲(chǔ)空間為MaxSize=6，采用少用一個(gè)元素空間以有效的判斷棧空或棧滿，若隊(duì)頭指針front=4，當(dāng)隊(duì)尾指針rear=3時(shí)隊(duì)滿。（）41.循環(huán)隊(duì)列的最大存儲(chǔ)空間為MaxSize=6，采用少用一個(gè)元素空間以有效的判斷棧空或棧滿，若隊(duì)頭指針front=4，隊(duì)尾指針rear=3時(shí)，隊(duì)列中共有5個(gè)元素。（）三、程序選擇填空題（每小題9分，共18分。請(qǐng)點(diǎn)擊正確選項(xiàng)，然后拖拽至

24、相應(yīng)的方框上）42.以下函數(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 node *p; p=(struct node*)malloc（A.sizeof(struct node)）; p->data=x; （p>next=top）; （top=p）; A.sizeof(struct node)top=pp>next=top43.以下函數(shù)為鏈隊(duì)列的入隊(duì)操作，x為要入隊(duì)的結(jié)點(diǎn)的數(shù)據(jù)域的

25、值，front、rear分別鏈隊(duì)列的隊(duì)頭、隊(duì)尾指針struct node ElemType data;struct node *next;struct node *front，*rear; void InQueue(ElemType x) struct node *p; p= (struct node*) malloc（(sizeof(struct node)）; p->data=x; p->next=NULL; （rear>next=p）; rear（p）; rear>next=pp(sizeof(struct node)形考作業(yè)3一、單項(xiàng)選擇題（每小題2分，共38分

26、）1.假定一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30，則葉子結(jié)點(diǎn)數(shù)為（ ）。A. 17B. 47C. 16D. 152.二叉樹(shù)第k層上最多有（ ）個(gè)結(jié)點(diǎn)。A. 2kB. 2k-1C. 2k-1D. 2k-13.將含有150個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為69的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為（ ）。A. 33B. 35C. 34D. 364.如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹(shù)的帶權(quán)路徑長(zhǎng)度最小，則該樹(shù)稱為（ ）。A. 平衡二叉樹(shù)B. 二叉樹(shù)C. 完全二叉樹(shù)D. 哈夫曼樹(shù)5.在一棵度具有5層的滿二叉樹(shù)中結(jié)點(diǎn)總數(shù)為（ ）

27、。A. 16B. 31C. 33D. 326.一棵完全二叉樹(shù)共有6層，且第6層上有6個(gè)結(jié)點(diǎn)，該樹(shù)共有（ ）個(gè)結(jié)點(diǎn)。A. 72B. 38C. 31D. 377.利用3、6、8、12這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹(shù)，該樹(shù)中所有葉子結(jié)點(diǎn)中的最長(zhǎng)帶權(quán)路徑長(zhǎng)度為（ ）。A. 12B. 18C. 16D. 308.在一棵樹(shù)中，（ ）沒(méi)有前驅(qū)結(jié)點(diǎn)。A. 分支結(jié)點(diǎn)B. 葉結(jié)點(diǎn)C. 樹(shù)根結(jié)點(diǎn)D. 空結(jié)點(diǎn)9.設(shè)一棵采用鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2，該樹(shù)結(jié)點(diǎn)中共有20個(gè)指針域?yàn)榭?則該樹(shù)有（ ）個(gè)葉結(jié)點(diǎn)。 A. 10B. 9C. 21D. 2210.在一個(gè)圖G中，所有頂點(diǎn)的度數(shù)之和等于所

28、有邊數(shù)之和的（ ）倍。A. 1/2B. 2C. 4D. 111.鄰接表是圖的一種（ ）。A. 索引存儲(chǔ)結(jié)構(gòu)B. 順序存儲(chǔ)結(jié)構(gòu)C. 散列存儲(chǔ)結(jié)構(gòu)D. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)12.圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的（ ）遍歷。A. 后序B. 層次C. 先序D. 中序13.已知下圖所示的一個(gè)圖，若從頂點(diǎn)V1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。A. V1V2V4V8V3V5V6V7B. V1V3V6V7V2V4V5V8C. V1V2V4V5V8V3V6V7 D. V1V2V4V8V5V3V6V714.已知如下圖所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種

29、頂點(diǎn)序列為（ ）。 A. aebcfdB. aecbdfC. aedfcbD. abecdf15.圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。A. 一對(duì)多B. 每一個(gè)元素都有一個(gè)且只有一個(gè)直接前驅(qū)和一個(gè)直接后繼C. 一對(duì)一D. 多對(duì)多16.在一棵二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（ ）。A. 2i-1B. 2i+1C. 2iD. 2i+217.一棵具有16個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，共有（ ）層。(設(shè)根結(jié)點(diǎn)在第一層)A. 4B. 5C. 6D. 718.對(duì)二叉排序樹(shù)進(jìn)行（ ）遍歷，可以使遍歷所得到的序列是有序序列。A. 中序B. 按層次C. 后序D. 前序19.已知一個(gè)圖的邊

30、數(shù)為m，則該圖的所有頂點(diǎn)的度數(shù)之和為（ ）。A. m/2B. 2m+1C. 2mD. m二、判斷題 （每小題1分，共10分）20.一棵二叉樹(shù)的葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）數(shù)為5，單分支結(jié)點(diǎn)數(shù)為2，該樹(shù)共有11個(gè)結(jié)點(diǎn)。（）21.一棵有14個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，則它的最高層上有7個(gè)結(jié)點(diǎn)。（）22.一棵二叉樹(shù)有6個(gè)葉結(jié)點(diǎn)，則該樹(shù)總共有11個(gè)結(jié)點(diǎn)。（×）23.根據(jù)搜索方法的不同，圖的遍歷有先序；中序；后序三種方法。（×）24.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其相應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中共有n-1個(gè)指針域空。（×）25.設(shè)一棵完全二叉樹(shù)，其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為奇數(shù)，該葉結(jié)點(diǎn)的雙親結(jié)點(diǎn)

31、的編號(hào)為10，該完全二叉樹(shù)一共有21個(gè)結(jié)點(diǎn)。（）26.設(shè)一棵完全二叉樹(shù)，其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為偶數(shù)，該葉結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為9，該完全二叉樹(shù)一共有19個(gè)結(jié)點(diǎn)。（×）27.按照二叉樹(shù)的遞歸定義，對(duì)二叉樹(shù)遍歷的常用算法有深度優(yōu)先遍歷和深度優(yōu)先遍兩種方法。（×）28.一棵有8個(gè)權(quán)重值構(gòu)造的哈夫曼數(shù)，共有17個(gè)結(jié)點(diǎn)。（×）29.一棵有7個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，其1度結(jié)點(diǎn)數(shù)的個(gè)數(shù)為2，則該樹(shù)共有15個(gè)結(jié)點(diǎn)。（）三、程序填空題（每空6分，共12分。請(qǐng)點(diǎn)擊正確選項(xiàng)，然后拖拽至相應(yīng)的方框上）30.以下程序是后序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分（樹(shù)結(jié)構(gòu)中左、右指

32、針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。完成程序中空格部分。 void Inorder (struct BTreeNode *BT)if( BT!=NULL)Inorder(BT->left);（Inorder(BT> right)）（printf(“%c”,BT>data)）利用上述程序?qū)ψ髨D進(jìn)行后序遍歷，結(jié)果是（d,e,b,f,c,a）;Inorder(BT> right)d,e,b,f,c,aprintf(“%c”,BT>data)31.以下程序是中序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分（樹(shù)結(jié)構(gòu)中左、右指針域分別為

33、left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。 void Inorder (struct BTreeNode *BT)if(BT!=NULL)Inorder(BT->left);（printf(“%c”,BT>data)）;（Inorder(BT>right)）;利用上述程序?qū)τ覉D進(jìn)行中序遍歷，結(jié)果是（d,b,e,a,f,c）;d,b,e,a,f,cprintf(“%c”,BT>data)Inorder(BT>right)四、綜合應(yīng)用題（每小題8分，5題，共40分）32.（1）以3，4，5，8，9，作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(shù)。該樹(shù)的帶權(quán)路徑

34、長(zhǎng)度為（）。A,64 B.65 C. 62 D. 66（2）權(quán)重為3的葉結(jié)點(diǎn)的哈夫曼編碼為（）。 A.010 B.0101 C.000 D.011133.（1）以2，3，4，7，8，9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(shù)，該樹(shù)的帶權(quán)路徑長(zhǎng)度為（）。A,66 B. 80 C. 62 D. 87（2）權(quán)重值為4的葉結(jié)點(diǎn)的哈夫曼編碼為（）。A.0001 B. 1110 C.001 D. 11034.（1）已知某二叉樹(shù)的后序遍歷序列是debca，中序遍歷序列是dbeac，該二叉樹(shù)的根結(jié)點(diǎn)是（）。A. e B. c C. b D. a（2）先序遍歷序列是（）。A. e,b,c,d,a B. c,a,b,d,

35、e C. a,b,d,e,c D. a.c,b,d,e,35.（1）已知某二叉樹(shù)的先序遍歷序列是aecdb，中序遍歷序列是eadcb，該二叉樹(shù)的根結(jié)點(diǎn)是（）; A. e B. c C. b D. a（2）后序遍歷序列為（）。A. e,d,b,c,a B. c,a,b,d,e C. a,b,d,e,c D. a.c,b,d,e,36.（1）以給定權(quán)重值5，6，17，18，25，30，為葉結(jié)點(diǎn)，建立一棵哈夫曼樹(shù),該樹(shù)的中序遍歷序列為（）。A. 5，11，28，6，17，58，30，101，18，43，25B. 5，11，6，28，17，58，30，101，18，43，25 C. 5，11，6，28

36、，101，58，30，17，18，43，25 D. 5，11，6，28，17，58，30，101，18，25，43 （2）權(quán)重值為6的葉結(jié)點(diǎn)的哈夫曼為回答. A. 1001 B. 011 C.001 D.0001形考作業(yè)4一、單項(xiàng)選擇題（每小題2分，共40分）1.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（ ）。A. 以鏈接存儲(chǔ)方式B. 以順序存儲(chǔ)方式C. 以順序存儲(chǔ)方式，且數(shù)據(jù)元素有序D. 以鏈接存儲(chǔ)方式，且數(shù)據(jù)元素有序2.采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為（ ）。A. nB. (n-1)/2C. n/2D. (n+1)/23.有一個(gè)長(zhǎng)度為10的有序表，按折半查找對(duì)

37、該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（ ）。A. 29/10B. 31/10C. 29/9D. 26/104.已知一個(gè)有序表為11,22,33,44,55,66,77,88,99，則順序查找元素55需要比較（ ）次。A. 5B. 6C. 4D. 35.有數(shù)據(jù)53,30,37,12,45,24,96，從空二叉樹(shù)開(kāi)始逐個(gè)插入數(shù)據(jù)來(lái)形成二叉排序樹(shù)，若希望高度最小，應(yīng)該選擇的序列是（ ）。A. 37,24,12,30,53,45,96B. 12,24,30,37,45,53,96C. 45,24,53,12,37,96,30D. 30,24,12,37,45,96,536.對(duì)于順序存儲(chǔ)

38、的有序表5,12,20,26,37,42,46,50,64，若采用折半查找，則查找元素26的比較次數(shù)是（ ）。A. 4B. 3C. 5D. 67.在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄初始排列秩序無(wú)關(guān)的是（ ）。A. 直接插入排序B. 冒泡排序C. 希爾排序D. 直接選擇排序8.從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱為（ ）。A. 插入排序B. 選擇排序C. 交換排序D. 歸并排序9.依次將每?jī)蓚€(gè)相鄰的有序表合并成一個(gè)有序表的排序方法稱為（ ）。A. 選擇排序B. 歸并排序C. 插入排序D. 交換排序10.當(dāng)兩個(gè)元素出現(xiàn)逆序的

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

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

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

42、23，36，40，82，72C. 16，25，35，48，23，40，79，82，36，72D. 16，25，35，48，79，82，23，36，40，7218.已知10個(gè)數(shù)據(jù)元素為（54，28，16，34，73，62，95，60，26，43），對(duì)該數(shù)列從小到大排序，經(jīng)過(guò)一趟冒泡排序后的序列為（ ）。A. 28，16，34，54，62，73，60，26，43，95B. 16，28，34，54，73，62，60，26，43，95C. 16，28，34，54，62，60，73，26，43，95D. 28，16，34，54，62，60，73，26，43，9519.一組記錄的關(guān)鍵字序列為（46，79，

43、56，38，40，84），利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后結(jié)果為（ ）。A. 40，38，46，79，56，84B. 40，38，46，84，56，79C. 38，40，46，56，79，84D. 40，38，46，56，79，8420.一組記錄的關(guān)鍵字序列為（80,57,41,39,46,47），利用堆排序（堆頂元素是最小元素）的方法建立的初始堆為（ ）。A. 39，46，41，57，80，47B. 39，47，46，80，41，57C. 41，39，46，47，57，80D. 39，80，46，47，41，57二、程序填空題（每題10分，2題，共20分。請(qǐng)點(diǎn)擊正確選項(xiàng)

44、，然后拖拽至相應(yīng)的方框上）21.以下函數(shù)是二叉排序樹(shù)的查找算法，若二叉樹(shù)為空，則返回根結(jié)點(diǎn)的指針，否則，返回值是指向樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)指針p（查找成功p指向查到的樹(shù)結(jié)點(diǎn)，不成功p指向?yàn)镹ULL）完成程序中的空格typedef struct Bnode int key;struct Bnode *left;struct Bnode *right; Bnode; Bnode *BSearch(Bnode *bt, int k) /* bt用于接收二叉排序樹(shù)的根結(jié)點(diǎn)的指針，k用以接收要查找的關(guān)鍵字*/ Bnode *p; if(bt= （NULL） ) return (bt); p=bt; while(p->key!=（k） ) if(k<p->key) （p=p>left） ; else （p=p>>right） ; if(p=NULL) break; return(（p） ; p=p>leftNULLp=p>>rightpk22.以下程序是折半插入排序的算法設(shè)待排序的記錄序列存放在a1,an中，以a0作為輔助工作單元，程序是要把a(bǔ)i 插入到已經(jīng)有序的序列a1,ai-1中。 void binsort (NODE a