國開形成性考核02272《數(shù)據(jù)結(jié)構(gòu)》形考任務(wù)(1-4)試題及答案

1、國開形成性考核數(shù)據(jù)結(jié)構(gòu)形考任務(wù)(1-4)試題及答案（課程ID：02272，整套相同，如遇順序不同，Ctrl F查找，祝同學(xué)們?nèi)〉脙?yōu)異成績?。┬慰既蝿?wù)（1）一、單項選擇題（每小題3分，共60分）題目：1、把數(shù)據(jù)存儲到計算機中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為（B）?！続】：給相關(guān)變量分配存儲單元【B】：物理結(jié)構(gòu)【C】：邏輯結(jié)構(gòu)【D】：算法的具體實現(xiàn)題目：2、下列說法中，不正確的是（B）。【A】：數(shù)據(jù)項是數(shù)據(jù)中不可分割的最小可標(biāo)識單位【B】：數(shù)據(jù)項可由若干個數(shù)據(jù)元素構(gòu)成【C】：數(shù)據(jù)可有若干個數(shù)據(jù)元素構(gòu)成【D】：數(shù)據(jù)元素是數(shù)據(jù)的基本單位題目：3、一個存儲結(jié)點存儲一個（D）。【A】：數(shù)據(jù)類型【B】：

2、數(shù)據(jù)項【C】：數(shù)據(jù)結(jié)構(gòu)【D】：數(shù)據(jù)元素題目：4、數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（B）?！続】：存儲結(jié)構(gòu)【B】：邏輯結(jié)構(gòu)【C】：物理和存儲結(jié)構(gòu)【D】：物理結(jié)構(gòu)題目：5、在線性表的順序結(jié)構(gòu)中，以下說法正確的是（D）?！続】：進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高【B】：邏輯上相鄰的元素在物理位置上也相鄰【C】：數(shù)據(jù)元素是不能隨機訪問的【D】：邏輯上相鄰的元素在物理位置上不一定相鄰題目：6、對鏈表, 以下敘述中正確的是（D）。【A】：可以通過下標(biāo)對鏈表進(jìn)行直接訪問【B】：插入刪除元素的操作一定要要移動結(jié)點【C】：結(jié)點占用的存儲空間是連續(xù)的【D】：不能隨機訪問任一結(jié)點題目：7、下列的敘述中，不屬

3、于算法特性的是（B）。【A】：可行性【B】：可讀性【C】：有窮性【D】：輸入性題目：8、算法的時間復(fù)雜度與（B）有關(guān)?！続】：所使用的計算機【B】：算法本身【C】：數(shù)據(jù)結(jié)構(gòu)【D】：計算機的操作系統(tǒng)題目：9、設(shè)有一個長度為n的順序表，要在第i個元素之前（也就是插入元素作為新表的第i個元素），插入一個元素，則移動元素個數(shù)為（C）?！続】：i【B】：n-i【C】：n-i 1【D】：n-i-1題目：10、設(shè)有一個長度為n的順序表，要刪除第i個元素移動元素的個數(shù)為（D）?！続】：n-i-1【B】：i【C】：n-i 1【D】：n-i題目：11、在一個單鏈表中，p、q分別指向表中兩個相鄰的結(jié)點，且q所指結(jié)點

4、是p所指結(jié)點的直接后繼，現(xiàn)要刪除q所指結(jié)點，可用語句（D）?！続】：q-next=NULL【B】：p-next=q【C】：p=q-next【D】：p-next=q-next題目：12、在一個單鏈表中p所指結(jié)點之后插入一個s所指的結(jié)點時，可執(zhí)行（D）?！続】：p-next=s-next;【B】：p-next= s; s-next= p-next【C】：p=s-next【D】：s-next=p-next; p-next=s;題目：13、非空的單向循環(huán)鏈表的尾結(jié)點滿足（D）（設(shè)頭指針為head，指針p指向尾結(jié)點）?！続】：p-next=NULL【B】：p=NULL【C】：p= head【D】：p-n

5、ext=head題目：14、鏈表不具有的特點是（C）?！続】：邏輯上相鄰的元素在物理位置上不一定相鄰【B】：插入刪除不需要移動元素【C】：可隨機訪問任一元素【D】：不必事先估計存儲空間題目：15、帶頭結(jié)點的鏈表為空的判斷條件是（A）（設(shè)頭指針為head）?！続】：head-next=NULL【B】：head!=NULL【C】：head =NULL【D】：head-next=head題目：16、在一個長度為n的順序表中為了刪除第5個元素，由第6個元素開始從后到前依次移動了15個元素。則原順序表的長度為（D）?！続】：25【B】：19【C】：21【D】：20題目：17、有關(guān)線性表的正確說法是（C）

6、?！続】：每個元素都有一個直接前驅(qū)和一個直接后繼【B】：表中的元素必須按由小到大或由大到下排序【C】：除了一個和最后一個元素外，其余元素都有一個且僅有一個直接前驅(qū)和一個直接后繼【D】：線性表至少要求一個元素題目：18、向一個有127個元素的順序表中插入一個新元素，并保持原來的順序不變，平均要移動（A）個元素?！続】：63.5【B】：8【C】：7【D】：63題目：19、一個順序表第一個元素的存儲地址是90，每個元素的長度為2，則第6個元素的地址是（C）?！続】：106【B】：102【C】：100【D】：98題目：20、在一個不帶頭結(jié)點的單循環(huán)鏈表中，p、q分別指向表中第一個結(jié)點和尾結(jié)點，現(xiàn)要刪除

7、第一個結(jié)點，且p、q仍然分別指向新表中第一個結(jié)點和尾結(jié)點。可用的語句是p=p-next;和（A）?！続】：q-next=p【B】：p=q-next【C】：p-next=q【D】： q=p二、判斷題（每小題2分，14題，共28分）題目：21、數(shù)據(jù)元素可以有一個或多個數(shù)據(jù)項組成。（V）題目：22、數(shù)據(jù)元素之間的抽象關(guān)系稱為物理結(jié)構(gòu)。（X）題目：23、數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示稱為邏輯結(jié)構(gòu)。（X）題目：24、數(shù)據(jù)的邏輯結(jié)構(gòu)是與存儲該結(jié)構(gòu)的計算機相關(guān)的。（X）題目：25、數(shù)據(jù)結(jié)構(gòu)中,元素之間存在多對多的關(guān)系稱為樹狀結(jié)構(gòu)。（X）題目：26、通?？梢园岩槐竞胁煌鹿?jié)的書的目錄結(jié)構(gòu)抽象成線性結(jié)構(gòu)。（X

8、）題目：27、通?？梢园涯吵鞘兄懈鞴徽军c間的線路圖抽象成樹型結(jié)構(gòu)。（X）題目：28、設(shè)有一個不帶頭結(jié)點的單向循環(huán)鏈表，結(jié)點的指針域為next，指針p指向尾結(jié)點，現(xiàn)要使p指向第一個結(jié)點，可用語句p=p-next;。（V）題目：29、設(shè)有一個單向鏈表，結(jié)點的指針域為next，頭指針為head，p指向尾結(jié)點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句p-next=head 。（V）題目：30、設(shè)有一個單向循環(huán)鏈表，結(jié)點的指針域為next，頭指針為head，指針p指向表中某結(jié)點，若邏輯表達(dá)式p-next=head;的結(jié)果為真，則p所指結(jié)點為尾結(jié)點。（V）題目：31、要在一個單向鏈表中p所指向的結(jié)點之

9、后插入一個s所指向的新結(jié)點，若鏈表中結(jié)點的指針域為next，可執(zhí)行 p-next=s; s-next= p-next；的操作。（X）題目：32、要在一個單向鏈表中刪除p所指向的結(jié)點，已知q指向p所指結(jié)點的直接前驅(qū)結(jié)點，若鏈表中結(jié)點的指針域為next，則可執(zhí)行q-next= p-next；（V）題目：33、要在一個帶頭結(jié)點的單向循環(huán)鏈表中刪除頭結(jié)點，得到一個新的不帶頭結(jié)點的單向循環(huán)鏈表，若結(jié)點的指針域為next，頭指針為head，尾指針為p，則可執(zhí)行head=head- next; p-next=head；。（V）題目：34、設(shè)有一個單向循環(huán)鏈表，頭指針為head，鏈表中結(jié)點的指針域為next，

10、p指向尾結(jié)點的直接前驅(qū)結(jié)點，若要刪除尾結(jié)點，得到一個新的單向循環(huán)鏈表，可執(zhí)行操作p-next=head；。（V）三、程序填空題（每小題6分，共12分。請點擊正確選項，然后拖拽至相應(yīng)的方框上）題目：35、設(shè)線性表以不帶頭結(jié)點的單向鏈表存儲，鏈表頭指針為head，以下程序的功能是輸出鏈表中各結(jié)點中的數(shù)據(jù)域data,完成程序中空格部分。#define NULL 0void main NODE *head ,*p ;p=head; /*p為工作指針*/doprintf(“%dn”, pdata ;p=pnext ;while p!=NULL ;題目：36、設(shè)有一個頭指針為head的不帶頭結(jié)點單向鏈表，

11、p、q是指向鏈表中結(jié)點類型的指針變量，p指向鏈表中結(jié)點a, （設(shè)鏈表中沒有結(jié)點的數(shù)據(jù)域與結(jié)點a的數(shù)據(jù)域相同）,寫出相關(guān)語句(1)使該單向鏈表成為單向循環(huán)鏈表(2)插入結(jié)點s,使它成為a結(jié)點的直接前驅(qū)q=p; x=p-data;while qnext!=NULL）q=q-next;q-next=head;q=p; p=p-next;while(p-data!=x) q=p;p=pnexts-next=p;qnext=s形考任務(wù)（2）一、單項選擇題（每小題2分，共50分）題目：1、若讓元素1，2，3依次進(jìn)棧，則出棧順序不可能為（D）?！続】：1，3，2【B】：2，1，3【C】：3，2，1【D】：3

12、，1，2題目：2、一個隊列的入隊序列是1，2，3，4。則隊列的輸出序列是（B）?！続】：1，4，3，2【B】：1，2，3，4【C】：3，2，4，1【D】：4，3，2，1題目：3、向順序棧中壓入新元素時，應(yīng)當(dāng)（B）?！続】：先后次序無關(guān)緊要【B】：先移動棧頂指針，再存入元素【C】：先存入元素，再移動棧頂指針【D】：同時進(jìn)行題目：4、在一個棧頂指針為top的鏈棧中，將一個p指針?biāo)傅慕Y(jié)點入棧，應(yīng)執(zhí)行（B）?！続】：top-next=p;【B】：p-next=top;top=p;【C】：p-next=top-next;top-next=p;【D】：p-next=top-next;top=top-ne

13、xt;題目：5、在一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用 x保存被刪結(jié)點的值，則執(zhí)行（A）。【A】：x=top-data;top=top-next;【B】：top=top-next;x=top-data;【C】：x=top-data;【D】：x=top;top=top-next;題目：6、判斷一個順序隊列（最多元素為m）為空的條件是（A）?！続】：front=rear【B】：front=rear 1【C】：rear=m-1【D】：rear=m題目：7、判斷一個循環(huán)隊列為滿的條件是（C）?！続】：front=rear 1【B】：rear=MaxSize【C】：(rear 1)%MaxSi

14、ze=front【D】：rear%MaxSize= =front題目：8、判斷棧滿（元素個數(shù)最多n個）的條件是（A）?！続】：top=n-1【B】：top=-1【C】：top=0【D】：top!=0題目：9、設(shè)有一個20階的對稱矩陣A（第一個元素為a1,1），采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始）， 則矩陣元素a6,2在一維數(shù)組B中的下標(biāo)是（A）?！続】：17【B】：28【C】：23【D】：21題目：10、在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)中，而打印機則從緩沖區(qū)中取出數(shù)據(jù)打印，該

15、緩沖區(qū)應(yīng)該是一個（A）結(jié)構(gòu)?！続】：隊列【B】：數(shù)組【C】：線性表【D】：堆棧題目：11、一個遞歸算法必須包括（B）?！続】：遞歸部分【B】：終止條件和遞歸部分【C】：迭代部分【D】：終止條件和迭代部分題目：12、在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則刪除一個結(jié)點的運算為（B）?！続】：r=f-next;【B】：f=f-next;【C】：f=r-next;【D】：r=r-next;題目：13、在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則插入s所指結(jié)點的運算為（D）?！続】：s-next=r;r=s;【B】：s-next=f;f=s;【C】：f-next=s;f=s;【D】：r-n

16、ext=s;r=s;題目：14、數(shù)組a經(jīng)初始化char a =“English”;a7中存放的是（C）?！続】：變量h【B】：h【C】：字符串的結(jié)束符【D】：字符h題目：15、設(shè)主串為“ABcCDABcdEFaBc”，以下模式串能與主串成功匹配的是（B）?！続】：BCd【B】：Bcd【C】：Abc【D】：ABC題目：16、字符串 a1=AEIJING，a2=AEI，a3=AEFANG，a4=AEFI中最大的是（A）?！続】：a1【B】：a2【C】：a3【D】：a4題目：17、兩個字符串相等的條件是（A）?！続】：兩串的長度相等，并且對應(yīng)位置上的字符相同【B】：兩串的長度相等，并且兩串包含的字符

17、相同【C】：兩串的長度相等【D】：兩串包含的字符相同題目：18、一維數(shù)組A采用順序存儲結(jié)構(gòu)，每個元素占用6個字節(jié)，第6個元素的存儲地址為100，則該數(shù)組的首地址是（C）?！続】：64【B】：28【C】：70【D】：90題目：19、一個非空廣義表的表頭（C）?！続】：只能是子表【B】：只能是原子【C】：可以是子表或原子【D】：不可能是原子題目：20、對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表，一個10 行8列的稀疏矩陣A，其相應(yīng)的三元組表共有6個元素，矩陣A共有（A）個零元素?！続】：74【B】：72【C】：10【D】：8題目：21、對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表，一個10 行8列的稀疏矩陣

18、A共有73個零元素，A的右下角元素為6，其相應(yīng)的三元組表中的第7個元素是（B）?！続】：（10，8，7）【B】：（10，8，6）【C】：（7，10，8）【D】：（7，8，10）題目：22、對一個棧頂指針為top的鏈棧進(jìn)行入棧操作，通過指針變量p生成入棧結(jié)點，并給該 結(jié)點賦值a，則執(zhí)行: p=(struct node *)malloc(sizeof(struct node);p-data=a;和（C）?！続】：p-next=top;p=top;【B】：top-next=p;p=top;【C】：p-next=top;top=p;【D】：top=top-next;p=top;題目：23、頭指針為he

19、ad的帶頭結(jié)點的單向鏈表為空的判定條件是（B）為真。【A】：head-next!=NULL【B】：head-next=NULL【C】： head=NULL【D】：head-next!=NULL題目：24、設(shè)有一個對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），B數(shù)組共有55個元素,則該矩陣是（C）階的對稱矩陣。【A】：5【B】：15【C】：10【D】：20題目：25、數(shù)組a經(jīng)初始化char a =“English”;a1中存放的是（B）?！続】：E【B】：字符n【C】：n【D】：字符E二、判斷題（每小題2分，16題，共32分）題目：26、設(shè)有一

20、個鏈棧，棧頂指針為hs，現(xiàn)有一個s所指向的結(jié)點要入棧，則可執(zhí)行操作。hs=s；s- next=hs;（X）。題目：27、設(shè)有一個非空的鏈棧，棧頂指針為hs，要進(jìn)行出棧操作，用x保存出棧結(jié)點的值，棧結(jié)點的指針域為next，則可執(zhí)行hs=hs-next ;x=hs-data; （X）。題目：28、有一個鏈棧，棧頂指針為h，現(xiàn)有一個p所指向的結(jié)點要入棧，則可執(zhí)行操作p-next=h;和h=p；（V）。題目：29、設(shè)有一個非空的鏈棧，棧頂指針為hs，要進(jìn)行出棧操作，用x保存出棧結(jié)點的值，棧結(jié)點的指針域為next，數(shù)據(jù)域為data，則可執(zhí)行hs= hs-next; x= hs-data; （X）。題目：

21、30、在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結(jié)點的指針域為next，則插入所指結(jié)點的操作為r-next=s；r=s；（V）。題目：31、在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結(jié)點的指針域為next，s指向一個要入 隊的結(jié)點，則入隊操作為r=s；r-next=s；（X）。題目：32、在一個不帶頭結(jié)點的非空鏈隊中，f和r分別為隊頭和隊尾指針，隊結(jié)點的數(shù)據(jù)域為data，指針域為next，若要進(jìn)行出隊操作，并用變量x存放出隊元素的數(shù)據(jù)值，則相關(guān)操作為x=f-data; f=f-next; （V）。題目：33、對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表，一個6行7列的稀疏矩陣A相應(yīng)的三元組表共有

22、8個元素,則矩陣A共有34個零元素。（V）。題目：34、循環(huán)隊列的最大存儲空間為MaxSize，隊頭指針為f，隊尾指針為r，當(dāng)（r 1）%MaxSize=f 時表明隊列已滿。（X）。題目：35、循環(huán)隊列的隊頭指針為f，隊尾指針為r，當(dāng)r= =f時表明隊列已滿。（X）。題目：36、空串的長度是0；空格串的長度是空格字符的個數(shù)。（V）。題目：37、對稀疏矩陣進(jìn)行壓縮存儲，矩陣中每個非零元素對應(yīng)的三元組包括該元素的行下標(biāo)、列下標(biāo)、和非零元素值三項信息。（V）。題目：38、循環(huán)隊列的引入，目的是為了克服假上溢。（V）。題目：39、設(shè)有n階對稱矩陣A，用一維數(shù)組s壓縮存儲A的下三角元素，s的下標(biāo)從零開始

23、，元素 s26相應(yīng)于A中的元素為a 7,5。（X）。題目：40、循環(huán)隊列的最大存儲空間為MaxSize=6，采用少用一個元素空間以有效的判斷棧空或棧滿，若隊頭指針front=4，當(dāng)隊尾指針rear=3時隊滿。（V）。題目：41、循環(huán)隊列的最大存儲空間為MaxSize=6，采用少用一個元素空間以有效的判斷棧空或棧滿，若隊頭指針front=4，隊尾指針rear=3時，隊列中共有5個元素。（V）。三、程序選擇填空題（每小題9分，共18分。請點擊正確選項，然后拖拽至相應(yīng)的方框上）題目：42、以下函數(shù)為鏈棧的進(jìn)棧操作，x是要進(jìn)棧的結(jié)點的數(shù)據(jù)域，top為棧頂指針struct node ElemType d

24、ata;struct node *next;struct node *top ;void Push(ElemType x)struct node *p;p=(struct node*)malloc【A】：sizeof (struct node) ;p-data=x;pnext=top ;top=p ;題目：43、以下函數(shù)為鏈隊列的入隊操作，x為要入隊的結(jié)點的數(shù)據(jù)域的值，front、rear分別鏈隊列的隊頭、隊尾指針struct node ElemType data;struct node *next;struct node *front，*rear;void InQueue(ElemType

25、x)struct node *p;p= (struct node*) malloc (sizeof (struct node) ;p-data=x;p-next=NULL;rearnext=p ;rear=p ;形考任務(wù)（3）一、單項選擇題（每小題2分，共38分）題目：1、假定一棵二叉樹中，雙分支結(jié)點數(shù)為15，單分支結(jié)點數(shù)為30，則葉子結(jié)點數(shù)為（B）?！続】：47【B】：16【C】：17【D】：15題目：2、二叉樹第k層上最多有（B）個結(jié)點?！続】：2k【B】：2k-1【C】：2k-1【D】：2k-1題目：3、將含有150個結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進(jìn)行編號，根結(jié)

26、點的編號為1，則編號為69的結(jié)點的雙親結(jié)點的編號為（D）?！続】：33【B】：36【C】：35【D】：34題目：4、如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹的帶權(quán)路徑長度最小，則該樹稱為（A）?！続】：哈夫曼樹【B】：平衡二叉樹【C】：二叉樹【D】：完全二叉樹題目：5、在一棵度具有5層的滿二叉樹中結(jié)點總數(shù)為（A）?！続】：31【B】：16【C】：33【D】：32題目：6、一棵完全二叉樹共有6層，且第6層上有6個結(jié)點，該樹共有（C）個結(jié)點?！続】：31【B】：38【C】：37【D】：72題目：7、利用3、6、8、12這四個值作為葉子結(jié)點的權(quán)，生成一棵哈夫曼樹，該樹中所有葉子結(jié)點中的最長

27、帶權(quán)路徑長度為（B）?！続】：30【B】：18【C】：12【D】：16題目：8、在一棵樹中，（A）沒有前驅(qū)結(jié)點。【A】：樹根結(jié)點【B】：空結(jié)點【C】：葉結(jié)點【D】：分支結(jié)點題目：9、設(shè)一棵采用鏈?zhǔn)酱鎯Φ亩鏄?，除葉結(jié)點外每個結(jié)點度數(shù)都為2，該樹結(jié)點中共有20個指針域為空,則該樹有（C）個葉結(jié)點?！続】：21【B】：9【C】：10【D】：22題目：10、在一個圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的（A）倍?！続】：2【B】：1/2【C】：4【D】：1題目：11、鄰接表是圖的一種（D）?！続】：順序存儲結(jié)構(gòu)【B】：索引存儲結(jié)構(gòu)【C】：散列存儲結(jié)構(gòu)【D】：鏈?zhǔn)酱鎯Y(jié)構(gòu)題目：12、圖的深度優(yōu)先遍

28、歷算法類似于二叉樹的（C）遍歷?！続】：后序【B】：層次【C】：先序【D】：中序題目：13、已知下圖所示的一個圖，若從頂點V1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點序列為（B）。【A】：V1V2V4V5V8V3V6V7【B】：V1V2V4V8V5V3V6V7【C】：V1V2V4V8V3V5V6V7【D】：V1V3V6V7V2V4V5V8題目：14、已知如下圖所示的一個圖，若從頂點a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點序列為（B）?！続】：abecdf【B】：aecbdf【C】：aedfcb【D】：aebcfd題目：15、圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（D）的關(guān)系

29、?！続】：每一個元素都有一個且只有一個直接前驅(qū)和一個直接后繼【B】：一對一【C】：一對多【D】：多對多題目：16、在一棵二叉樹中，若編號為i的結(jié)點存在右孩子，則右孩子的順序編號為（A）?！続】：2i 1【B】：2i-1【C】：2i【D】：2i 2題目：17、一棵具有16個結(jié)點的完全二叉樹，共有（B）層。(設(shè)根結(jié)點在第一層)【A】：4【B】：5【C】：6【D】：7題目：18、對二叉排序樹進(jìn)行（C）遍歷，可以使遍歷所得到的序列是有序序列?！続】：按層次【B】：后序【C】：中序【D】：前序題目：19、已知一個圖的邊數(shù)為m，則該圖的所有頂點的度數(shù)之和為（D）?！続】：m【B】：2m 1【C】：m/2【

30、D】：2m二、判斷題 （每小題1分，共10分）題目：20、一棵二叉樹的葉結(jié)點（終端結(jié)點）數(shù)為5，單分支結(jié)點數(shù)為2，該樹共有11個結(jié)點。（V）題目：21、一棵有14個結(jié)點的完全二叉樹，則它的最高層上有7個結(jié)點。（V）題目：22、一棵二叉樹有6個葉結(jié)點，則該樹總共有11個結(jié)點。（X）題目：23、根據(jù)搜索方法的不同，圖的遍歷有先序；中序；后序三種方法。（X）題目：24、對于一棵具有n個結(jié)點的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)中共有n-1個指針域空。（X）題目：25、設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點的編號為奇數(shù)，該葉結(jié)點的雙親結(jié)點的編號為10，該完全二叉樹一共有21個結(jié)點。（V）題目：26、設(shè)一棵

31、完全二叉樹，其最高層上最右邊的葉結(jié)點的編號為偶數(shù)，該葉結(jié)點的雙親結(jié)點的編號為9，該完全二叉樹一共有19個結(jié)點。（X）題目：27、按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有深度優(yōu)先遍歷和深度優(yōu)先遍兩種方法。（X）題目：28、一棵有8個權(quán)重值構(gòu)造的哈夫曼數(shù)，共有17個結(jié)點。（X）題目：29、一棵有7個葉結(jié)點的二叉樹，其1度結(jié)點數(shù)的個數(shù)為2，則該樹共有15個結(jié)點。（V）三、程序填空題（每空6分，共12分。請點擊正確選項，然后拖拽至相應(yīng)的方框上）題目：30、以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向

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

33、(“%c”,BTdata) ;Inorder(BTright) ;利用上述程序?qū)τ覉D進(jìn)行中序遍歷，結(jié)果是d,b,e,a,f,c ;四、綜合應(yīng)用題（每小題8分，5題，共40分）題目：32、（1）以3，4，5，8，9，作為葉結(jié)點的權(quán)，構(gòu)造一棵哈夫曼樹。該樹的帶權(quán)路徑長度為 （B）。A,64【B】：65【C】： 62【D】： 66（2）權(quán)重為3的葉結(jié)點的哈夫曼編碼為（C）?！続】：010【B】：0101【C】：000【D】：0111題目：33、（1）以2，3，4，7，8，9作為葉結(jié)點的權(quán)，構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為（B）?！続】：66【B】： 80【C】： 62【D】： 87（2）權(quán)重值

34、為4的葉結(jié)點的哈夫曼編碼為（C）?！続】：0001【B】： 1110【C】：001【D】： 110題目：34、（1）已知某二叉樹的后序遍歷序列是debca，中序遍歷序列是dbeac，該二叉樹的根結(jié)點是（D）?！続】： e【B】： c【C】： b【D】： a（2）先序遍歷序列是（C）?！続】： e,b,c,d,a【B】： c,a,b,d,e【C】： a,b,d,e,c【D】：【A】：c,b,d,e,題目：35、（1）已知某二叉樹的先序遍歷序列是aecdb，中序遍歷序列是eadcb，該二叉樹的根結(jié)點是（D）。【A】： e【B】： c【C】： b【D】： a（2）后序遍歷序列為（A）?！続】： e,

35、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é)點，建立一棵哈夫曼樹,該樹的中序遍歷序列為（B）。【A】： 5，11，28，6，17，58，30，101，18，43，25【B】： 5，11，6，28，17，58，30，101，18，43，25【C】： 5，11，6，28，101，58，30，17，18，43，25【D】： 5，11，6，28，17，58，30，101，18，25，43（2）權(quán)重值為6的葉結(jié)點的哈夫曼為（D）?！続】： 1001【B】： 011【C】：001【D】

36、：0001形考任務(wù)（4）一、單項選擇題（每小題2分，共40分）題目：1、對線性表進(jìn)行二分查找時，要求線性表必須（D）。【A】：以順序存儲方式【B】：以鏈接存儲方式【C】：以鏈接存儲方式，且數(shù)據(jù)元素有序【D】：以順序存儲方式，且數(shù)據(jù)元素有序題目：2、采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（B）?！続】：n【B】：(n 1)/2【C】：n/2【D】：(n-1)/2題目：3、有一個長度為10的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（B）。【A】：29/9【B】：29/10【C】：26/10【D】：31/10題目：4、已知一個有序表為11,2

37、2,33,44,55,66,77,88,99，則順序查找元素55需要比較（A）次?！続】：5【B】：4【C】：3【D】：6題目：5、有數(shù)據(jù)53,30,37,12,45,24,96，從空二叉樹開始逐個插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，應(yīng)該選擇的序列是（B）。【A】：45,24,53,12,37,96,30【B】：37,24,12,30,53,45,96【C】：30,24,12,37,45,96,53【D】：12,24,30,37,45,53,96題目：6、對于順序存儲的有序表5,12,20,26,37,42,46,50,64，若采用折半查找，則查找元素26的比較次數(shù)是（B）?！続】：3【

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

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

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

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

42、B】：16，25，35，48，79，82，23，36，40，72【C】：16，25，35，48，79，23，36，40，82，72【D】：16，25，35，48，23，40，79，82，36，72題目：18、已知10個數(shù)據(jù)元素為（54，28，16，34，73，62，95，60，26，43），對該數(shù)列從小到大排序，經(jīng)過一趟冒泡排序后的序列為（D）?！続】：16，28，34，54，73，62，60，26，43，95【B】：28，16，34，54，62，60，73，26，43，95【C】：16，28，34，54，62，60，73，26，43，95【D】：28，16，34，54，62，73，60，26

43、，43，95題目：19、一組記錄的關(guān)鍵字序列為（46，79，56，38，40，84），利用快速排序，以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（B）?！続】：40，38，46，79，56，84【B】：40，38，46，56，79，84【C】：40，38，46，84，56，79【D】：38，40，46，56，79，84題目：20、一組記錄的關(guān)鍵字序列為（80,57,41,39,46,47），利用堆排序（堆頂元素是最小元素）的方法建立的初始堆為（B）?！続】：41，39，46，47，57，80【B】：39，46，41，57，80，47【C】：39，80，46，47，41，57【D】：39，47

44、，46，80，41，57二、程序填空題（每題10分，2題，共20分。請點擊正確選項，然后拖拽至相應(yīng)的方框上）題目：21、以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點的指針，否則，返回值是指向樹結(jié)點的結(jié)構(gòu)指針p（查找成功p指向查到的樹結(jié)點，不成功p指向為NULL）完成程序中的空格typedef struct Bnode int key;struct Bnode *left;struct Bnode *right; Bnode;Bnode *BSearch(Bnode *bt, int k)/* bt用于接收二叉排序樹的根結(jié)點的指針，k用以接收要查找的關(guān)鍵字*/ Bnode *p;if(bt=NULL )return (bt);p=bt;while(p-key!=k ) if(kkey)p=pleft ;elsep=pright ;if(p=NULL) break;return(p ;題目：22、以下程序是折半插入排序的算法設(shè)待排序的記錄序列存放在a1,an中，以a0作為輔助工作單元，程序是要把ai 插入到已經(jīng)有序的序列a1,ai-1中。void bins