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

國開形成性考核《數(shù)據(jù)結(jié)構(gòu)》形考任務(wù)(1-4)試題及答案（課程ID：02272，整套相同，如遇順序不同，Ctrl+F查找，祝同學(xué)們?nèi)〉脙?yōu)異成績?。┬慰既蝿?wù)（1）一、單項(xiàng)選擇題（每小題3分，共60分）題目：1、把數(shù)據(jù)存儲到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為（B）?！続】：給相關(guān)變量分配存儲單元【B】：物理結(jié)構(gòu)【C】：邏輯結(jié)構(gòu)【D】：算法的具體實(shí)現(xiàn)題目：2、下列說法中，不正確的是（B）?！続】：數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)識單位【B】：數(shù)據(jù)項(xiàng)可由若干個數(shù)據(jù)元素構(gòu)成【C】：數(shù)據(jù)可有若干個數(shù)據(jù)元素構(gòu)成【D】：數(shù)據(jù)元素是數(shù)據(jù)的基本單位題目：3、一個存儲結(jié)點(diǎn)存儲一個（D）?！続】：數(shù)據(jù)類型【B】：數(shù)據(jù)項(xiàng)【C】：數(shù)據(jù)結(jié)構(gòu)【D】：數(shù)據(jù)元素題目：4、數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(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ù)元素是不能隨機(jī)訪問的【D】：邏輯上相鄰的元素在物理位置上不一定相鄰題目：6、對鏈表,以下敘述中正確的是（D）?！続】：可以通過下標(biāo)對鏈表進(jìn)行直接訪問【B】：插入刪除元素的操作一定要要移動結(jié)點(diǎn)【C】：結(jié)點(diǎn)占用的存儲空間是連續(xù)的【D】：不能隨機(jī)訪問任一結(jié)點(diǎn)題目：7、下列的敘述中，不屬于算法特性的是（B）?！続】：可行性【B】：可讀性【C】：有窮性【D】：輸入性題目：8、算法的時間復(fù)雜度與（B）有關(guān)?！続】：所使用的計(jì)算機(jī)【B】：算法本身【C】：數(shù)據(jù)結(jié)構(gòu)【D】：計(jì)算機(jī)的操作系統(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é)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要刪除q所指結(jié)點(diǎn)，可用語句（D）?！続】：q->next=NULL【B】：p->next=q【C】：p=q->next【D】：p->next=q->next題目：12、在一個單鏈表中p所指結(jié)點(diǎn)之后插入一個s所指的結(jié)點(diǎn)時，可執(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é)點(diǎn)滿足（D）（設(shè)頭指針為head，指針p指向尾結(jié)點(diǎn)）?！続】：p->next==NULL【B】：p==NULL【C】：p==head【D】：p->next==head題目：14、鏈表不具有的特點(diǎn)是（C）?！続】：邏輯上相鄰的元素在物理位置上不一定相鄰【B】：插入刪除不需要移動元素【C】：可隨機(jī)訪問任一元素【D】：不必事先估計(jì)存儲空間題目：15、帶頭結(jié)點(diǎn)的鏈表為空的判斷條件是（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）?！続】：每個元素都有一個直接前驅(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é)點(diǎn)的單循環(huán)鏈表中，p、q分別指向表中第一個結(jié)點(diǎn)和尾結(jié)點(diǎn)，現(xiàn)要刪除第一個結(jié)點(diǎn)，且p、q仍然分別指向新表中第一個結(jié)點(diǎn)和尾結(jié)點(diǎn)?？捎玫恼Z句是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ù)項(xiàng)組成。（V）題目：22、數(shù)據(jù)元素之間的抽象關(guān)系稱為物理結(jié)構(gòu)。（X）題目：23、數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為邏輯結(jié)構(gòu)。（X）題目：24、數(shù)據(jù)的邏輯結(jié)構(gòu)是與存儲該結(jié)構(gòu)的計(jì)算機(jī)相關(guān)的。（X）題目：25、數(shù)據(jù)結(jié)構(gòu)中,元素之間存在多對多的關(guān)系稱為樹狀結(jié)構(gòu)。（X）題目：26、通?？梢园岩槐竞胁煌鹿?jié)的書的目錄結(jié)構(gòu)抽象成線性結(jié)構(gòu)。（X）題目：27、通?？梢园涯吵鞘兄懈鞴徽军c(diǎn)間的線路圖抽象成樹型結(jié)構(gòu)。（X）題目：28、設(shè)有一個不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，指針p指向尾結(jié)點(diǎn)，現(xiàn)要使p指向第一個結(jié)點(diǎn)，可用語句p=p->next;。（V）題目：29、設(shè)有一個單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，p指向尾結(jié)點(diǎn)，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句p->next=head。（V）題目：30、設(shè)有一個單向循環(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)。（V）題目：31、要在一個單向鏈表中p所指向的結(jié)點(diǎn)之后插入一個s所指向的新結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，可執(zhí)行p->next=s;s->next=p->next；的操作。（X）題目：32、要在一個單向鏈表中刪除p所指向的結(jié)點(diǎn)，已知q指向p所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，則可執(zhí)行q->next=p->next；（V）題目：33、要在一個帶頭結(jié)點(diǎn)的單向循環(huán)鏈表中刪除頭結(jié)點(diǎn)，得到一個新的不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，若結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，尾指針為p，則可執(zhí)行head=head->next;p->next=head；。（V）題目：34、設(shè)有一個單向循環(huán)鏈表，頭指針為head，鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，p指向尾結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若要刪除尾結(jié)點(diǎn)，得到一個新的單向循環(huán)鏈表，可執(zhí)行操作p->next=head；。（V）三、程序填空題（每小題6分，共12分。請點(diǎn)擊正確選項(xiàng)，然后拖拽至相應(yīng)的方框上）題目：35、設(shè)線性表以不帶頭結(jié)點(diǎn)的單向鏈表存儲，鏈表頭指針為head，以下程序的功能是輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)域data,完成程序中空格部分。#defineNULL0voidmain{NODE*head,*p;p=head;/*p為工作指針*/do{printf(“%d\n”,p?>data;p=p?>next;}whilep!=NULL;}題目：36、設(shè)有一個頭指針為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->data;whileq?>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形考任務(wù)（2）一、單項(xiàng)選擇題（每小題2分，共50分）題目：1、若讓元素1，2，3依次進(jìn)棧，則出棧順序不可能為（D）?！続】：1，3，2【B】：2，1，3【C】：3，2，1【D】：3，1，2題目：2、一個隊(duì)列的入隊(duì)序列是1，2，3，4。則隊(duì)列的輸出序列是（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é)點(diǎn)入棧，應(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->next;題目：5、在一個棧頂指針為top的鏈棧中刪除一個結(jié)點(diǎn)時，用x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（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、判斷一個順序隊(duì)列（最多元素為m）為空的條件是（A）?！続】：front==rear【B】：front==rear+1【C】：rear==m-1【D】：rear=m題目：7、判斷一個循環(huán)隊(duì)列為滿的條件是（C）?！続】：front==rear+1【B】：rear=MaxSize【C】：(rear+1)%MaxSize==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），采用壓縮存儲的方式，將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣元素a6,2在一維數(shù)組B中的下標(biāo)是（A）?！続】：17【B】：28【C】：23【D】：21題目：10、在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)中，而打印機(jī)則從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應(yīng)該是一個（A）結(jié)構(gòu)?！続】：隊(duì)列【B】：數(shù)組【C】：線性表【D】：堆棧題目：11、一個遞歸算法必須包括（B）?！続】：遞歸部分【B】：終止條件和遞歸部分【C】：迭代部分【D】：終止條件和迭代部分題目：12、在一個鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個結(jié)點(diǎn)的運(yùn)算為（B）?！続】：r=f->next;【B】：f=f->next;【C】：f=r->next;【D】：r=r->next;題目：13、在一個鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算為（D）?！続】：s->next=r;r=s;【B】：s->next=f;f=s;【C】：f->next=s;f=s;【D】：r->next=s;r=s;題目：14、數(shù)組a經(jīng)初始化chara[]=“English”;a[7]中存放的是（C）?！続】：變量h【B】："h"【C】：字符串的結(jié)束符【D】：字符h題目：15、設(shè)主串為“ABcCDABcdEFaBc”，以下模式串能與主串成功匹配的是（B）?！続】：BCd【B】：Bcd【C】：Abc【D】：ABC題目：16、字符串a(chǎn)1="AEIJING"，a2="AEI"，a3="AEFANG"，a4="AEFI"中最大的是（A）?！続】：a1【B】：a2【C】：a3【D】：a4題目：17、兩個字符串相等的條件是（A）?！続】：兩串的長度相等，并且對應(yīng)位置上的字符相同【B】：兩串的長度相等，并且兩串包含的字符相同【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列的稀疏矩陣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é)點(diǎn)，并給該結(jié)點(diǎn)賦值a，則執(zhí)行:p=(structnode*)malloc(sizeof(structnode);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、頭指針為head的帶頭結(jié)點(diǎn)的單向鏈表為空的判定條件是（B）為真?！続】：head->next!=NULL【B】：head->next==NULL【C】：head==NULL【D】：head->next!=NULL題目：24、設(shè)有一個對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從1開始），B數(shù)組共有55個元素,則該矩陣是（C）階的對稱矩陣?！続】：5【B】：15【C】：10【D】：20題目：25、數(shù)組a經(jīng)初始化chara[]=“English”;a[1]中存放的是（B）?！続】："E"【B】：字符n【C】："n"【D】：字符E二、判斷題（每小題2分，16題，共32分）題目：26、設(shè)有一個鏈棧，棧頂指針為hs，現(xiàn)有一個s所指向的結(jié)點(diǎn)要入棧，則可執(zhí)行操作。hs=s；s->next=hs;（X）。題目：27、設(shè)有一個非空的鏈棧，棧頂指針為hs，要進(jìn)行出棧操作，用x保存出棧結(jié)點(diǎn)的值，棧結(jié)點(diǎn)的指針域?yàn)閚ext，則可執(zhí)行hs=hs->next;x=hs->data;（X）。題目：28、有一個鏈棧，棧頂指針為h，現(xiàn)有一個p所指向的結(jié)點(diǎn)要入棧，則可執(zhí)行操作p->next=h;和h=p；（V）。題目：29、設(shè)有一個非空的鏈棧，棧頂指針為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;（X）。題目：30、在一個鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext，則插入所指結(jié)點(diǎn)的操作為r->next=s；r=s；（V）。題目：31、在一個鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext，s指向一個要入隊(duì)的結(jié)點(diǎn)，則入隊(duì)操作為r=s；r->next=s；（X）。題目：32、在一個不帶頭結(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）。題目：33、對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表，一個6行7列的稀疏矩陣A相應(yīng)的三元組表共有8個元素,則矩陣A共有34個零元素。（V）。題目：34、循環(huán)隊(duì)列的最大存儲空間為MaxSize，隊(duì)頭指針為f，隊(duì)尾指針為r，當(dāng)（r+1）%MaxSize=f時表明隊(duì)列已滿。（X）。題目：35、循環(huán)隊(duì)列的隊(duì)頭指針為f，隊(duì)尾指針為r，當(dāng)r==f時表明隊(duì)列已滿。（X）。題目：36、空串的長度是0；空格串的長度是空格字符的個數(shù)。（V）。題目：37、對稀疏矩陣進(jìn)行壓縮存儲，矩陣中每個非零元素對應(yīng)的三元組包括該元素的行下標(biāo)、列下標(biāo)、和非零元素值三項(xiàng)信息。（V）。題目：38、循環(huán)隊(duì)列的引入，目的是為了克服假上溢。（V）。題目：39、設(shè)有n階對稱矩陣A，用一維數(shù)組s壓縮存儲A的下三角元素，s的下標(biāo)從零開始，元素s[26]相應(yīng)于A中的元素為a7,5。（X）。題目：40、循環(huán)隊(duì)列的最大存儲空間為MaxSize=6，采用少用一個元素空間以有效的判斷?？栈驐M，若隊(duì)頭指針front=4，當(dāng)隊(duì)尾指針rear=3時隊(duì)滿。（V）。題目：41、循環(huán)隊(duì)列的最大存儲空間為MaxSize=6，采用少用一個元素空間以有效的判斷?？栈驐M，若隊(duì)頭指針front=4，隊(duì)尾指針rear=3時，隊(duì)列中共有5個元素。（V）。三、程序選擇填空題（每小題9分，共18分。請點(diǎn)擊正確選項(xiàng)，然后拖拽至相應(yīng)的方框上）題目：42、以下函數(shù)為鏈棧的進(jìn)棧操作，x是要進(jìn)棧的結(jié)點(diǎn)的數(shù)據(jù)域，top為棧頂指針structnode{ElemTypedata;structnode*next;};structnode*top;voidPush(ElemTypex){structnode*p;p=(structnode*)malloc【A】：sizeof(structnode);p->data=x;p?>next=top;top=p;}題目：43、以下函數(shù)為鏈隊(duì)列的入隊(duì)操作，x為要入隊(duì)的結(jié)點(diǎn)的數(shù)據(jù)域的值，front、rear分別鏈隊(duì)列的隊(duì)頭、隊(duì)尾指針structnode{ElemTypedata;structnode*next;};structnode*front，*rear;voidInQueue(ElemTypex){structnode*p;p=(structnode*)malloc(sizeof(structnode);p->data=x;p->next=NULL;rear?>next=p;rear=p;}形考任務(wù)（3）一、單項(xiàng)選擇題（每小題2分，共38分）題目：1、假定一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30，則葉子結(jié)點(diǎn)數(shù)為（B）?！続】：47【B】：16【C】：17【D】：15題目：2、二叉樹第k層上最多有（B）個結(jié)點(diǎn)?！続】：2k【B】：2k-1【C】：2k-1【D】：2k-1題目：3、將含有150個結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點(diǎn)進(jìn)行編號，根結(jié)點(diǎn)的編號為1，則編號為69的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為（D）?！続】：33【B】：36【C】：35【D】：34題目：4、如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹的帶權(quán)路徑長度最小，則該樹稱為（A）?！続】：哈夫曼樹【B】：平衡二叉樹【C】：二叉樹【D】：完全二叉樹題目：5、在一棵度具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（A）?！続】：31【B】：16【C】：33【D】：32題目：6、一棵完全二叉樹共有6層，且第6層上有6個結(jié)點(diǎn)，該樹共有（C）個結(jié)點(diǎn)?！続】：31【B】：38【C】：37【D】：72題目：7、利用3、6、8、12這四個值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹中所有葉子結(jié)點(diǎn)中的最長帶權(quán)路徑長度為（B）?！続】：30【B】：18【C】：12【D】：16題目：8、在一棵樹中，（A）沒有前驅(qū)結(jié)點(diǎn)?！続】：樹根結(jié)點(diǎn)【B】：空結(jié)點(diǎn)【C】：葉結(jié)點(diǎn)【D】：分支結(jié)點(diǎn)題目：9、設(shè)一棵采用鏈?zhǔn)酱鎯Φ亩鏄?，除葉結(jié)點(diǎn)外每個結(jié)點(diǎn)度數(shù)都為2，該樹結(jié)點(diǎn)中共有20個指針域?yàn)榭?則該樹有（C）個葉結(jié)點(diǎn)?！続】：21【B】：9【C】：10【D】：22題目：10、在一個圖G中，所有頂點(diǎn)的度數(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)先遍歷算法類似于二叉樹的（C）遍歷?！続】：后序【B】：層次【C】：先序【D】：中序題目：13、已知下圖所示的一個圖，若從頂點(diǎn)V1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（B）?！続】：V1V2V4V5V8V3V6V7【B】：V1V2V4V8V5V3V6V7【C】：V1V2V4V8V3V5V6V7【D】：V1V3V6V7V2V4V5V8題目：14、已知如下圖所示的一個圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（B）?！続】：abecdf【B】：aecbdf【C】：aedfcb【D】：aebcfd題目：15、圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（D）的關(guān)系?！続】：每一個元素都有一個且只有一個直接前驅(qū)和一個直接后繼【B】：一對一【C】：一對多【D】：多對多題目：16、在一棵二叉樹中，若編號為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號為（A）?！続】：2i+1【B】：2i-1【C】：2i【D】：2i+2題目：17、一棵具有16個結(jié)點(diǎn)的完全二叉樹，共有（B）層。(設(shè)根結(jié)點(diǎn)在第一層)【A】：4【B】：5【C】：6【D】：7題目：18、對二叉排序樹進(jìn)行（C）遍歷，可以使遍歷所得到的序列是有序序列?！続】：按層次【B】：后序【C】：中序【D】：前序題目：19、已知一個圖的邊數(shù)為m，則該圖的所有頂點(diǎn)的度數(shù)之和為（D）?！続】：m【B】：2m+1【C】：m/2【D】：2m二、判斷題（每小題1分，共10分）題目：20、一棵二叉樹的葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）數(shù)為5，單分支結(jié)點(diǎn)數(shù)為2，該樹共有11個結(jié)點(diǎn)。（V）題目：21、一棵有14個結(jié)點(diǎn)的完全二叉樹，則它的最高層上有7個結(jié)點(diǎn)。（V）題目：22、一棵二叉樹有6個葉結(jié)點(diǎn)，則該樹總共有11個結(jié)點(diǎn)。（X）題目：23、根據(jù)搜索方法的不同，圖的遍歷有．先序；中序；后序三種方法。（X）題目：24、對于一棵具有n個結(jié)點(diǎn)的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)中共有n-1個指針域空。（X）題目：25、設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點(diǎn)的編號為奇數(shù)，該葉結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為10，該完全二叉樹一共有21個結(jié)點(diǎn)。（V）題目：26、設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點(diǎn)的編號為偶數(shù)，該葉結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為9，該完全二叉樹一共有19個結(jié)點(diǎn)。（X）題目：27、按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有深度優(yōu)先遍歷和深度優(yōu)先遍兩種方法。（X）題目：28、一棵有8個權(quán)重值構(gòu)造的哈夫曼數(shù)，共有17個結(jié)點(diǎn)。（X）題目：29、一棵有7個葉結(jié)點(diǎn)的二叉樹，其1度結(jié)點(diǎn)數(shù)的個數(shù)為2，則該樹共有15個結(jié)點(diǎn)。（V）三、程序填空題（每空6分，共12分。請點(diǎn)擊正確選項(xiàng)，然后拖拽至相應(yīng)的方框上）題目：30、以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。完成程序中空格部分。voidInorder(structBTreeNode*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;題目：31、以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。voidInorder(structBTreeNode*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;四、綜合應(yīng)用題（每小題8分，5題，共40分）題目：32、（1）以3，4，5，8，9，作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹。該樹的帶權(quán)路徑長度為（B）。A,64【B】：65【C】：62【D】：66（2）權(quán)重為3的葉結(jié)點(diǎn)的哈夫曼編碼為（C）?！続】：010【B】：0101【C】：000【D】：0111題目：33、（1）以2，3，4，7，8，9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為（B）?！続】：66【B】：80【C】：62【D】：87（2）權(quán)重值為4的葉結(jié)點(diǎn)的哈夫曼編碼為（C）。【A】：0001【B】：1110【C】：001【D】：110題目：34、（1）已知某二叉樹的后序遍歷序列是debca，中序遍歷序列是dbeac，該二叉樹的根結(jié)點(diǎn)是（D）。【A】：e【B】：c【C】：b【D】：a（2）先序遍歷序列是（C）。【A】：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é)點(diǎn)是（D）。【A】：e【B】：c【C】：b【D】：a（2）后序遍歷序列為（A）。【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)，建立一棵哈夫曼樹,該樹的中序遍歷序列為（B）?！続】：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é)點(diǎn)的哈夫曼為（D）?！続】：1001【B】：011【C】：001【D】：0001形考任務(wù)（4）一、單項(xiàng)選擇題（每小題2分，共40分）題目：1、對線性表進(jìn)行二分查找時，要求線性表必須（D）?！続】：以順序存儲方式【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）?！続】：29/9【B】：29/10【C】：26/10【D】：31/10題目：4、已知一個有序表為{11,22,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）?！続】：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【B】：4【C】：5【D】：6題目：7、在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄初始排列秩序無關(guān)的是（B）?！続】：冒泡排序【B】：直接選擇排序【C】：直接插入排序【D】：希爾排序題目：8、從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱為（B）?！続】：選擇排序【B】：插入排序【C】：歸并排序【D】：交換排序題目：9、依次將每兩個相鄰的有序表合并成一個有序表的排序方法稱為（B）?！続】：選擇排序【B】：歸并排序【C】：插入排序【D】：交換排序題目：10、當(dāng)兩個元素出現(xiàn)逆序的時候就交換位置，這種排序方法稱為（C）?！続】：選擇排序【B】：插入排序【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）?！続】：20,30,40，38，46，79，56，84,90,100【B】：40，20,30,38，46，56，79，84,90,110【C】：20,3038，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、排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（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【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，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，46，80，41，57二、程序填空題（每題10分，2題，共20分。請點(diǎn)擊正確選項(xiàng)，然后拖拽至相應(yīng)的方框上）題目：21、以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點(diǎn)的指針，否則，返回值是指向樹結(jié)點(diǎn)的結(jié)構(gòu)指針p（查找成功p指向查到的樹結(jié)點(diǎn)，不成功p指向?yàn)镹ULL）完成程序中的空格typedefstructBnode{intkey;structBnode*left;structBnode*right;}Bnode;Bnode*BSearch(Bnode*bt,intk)/*bt用于接收二叉排序樹的根結(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;elsep=p?>right;if(p==NULL)break;}return(p;}題目：22、以下程序是折半插入排序的算法設(shè)待排序的記錄序列存放在a[1],…a[n]中，以a[0]作為輔助工作單元，程序是要把a(bǔ)[i]插入到已經(jīng)有序的序列a[1],…a[i-1]中。voidbinsort(NODEa[],intn){intx,i,j,s,k,m;for（i=2；i<=n;i++）{a[0]=a[i];x=a[i].key;s=1;j=i-1;