國家開放大學(xué)電大《數(shù)據(jù)結(jié)構(gòu)》網(wǎng)絡(luò)課形考網(wǎng)考作業(yè)及答案

國家開放大學(xué)電大《數(shù)據(jù)結(jié)構(gòu)》網(wǎng)絡(luò)課形考網(wǎng)考作業(yè)及答案100%通過考試說明：2020年秋期電大把該網(wǎng)絡(luò)課納入到“國開平臺”進(jìn)行考核，該課程共有4個(gè)形考任務(wù)，針對該門課程，本人匯總了該科所有的題，形成一個(gè)完整的標(biāo)準(zhǔn)題庫，并且以后會不斷更新，對考生的復(fù)習(xí)、作業(yè)和考試起著非常重要的作用，會給您節(jié)省大量的時(shí)間。做考題時(shí)，利用本文檔中的查找工具，把考題中的關(guān)鍵字輸?shù)讲檎夜ぞ叩牟檎覂?nèi)容框內(nèi)，就可迅速查找到該題答案。本文庫還有其他網(wǎng)核及教學(xué)考一體化答案，敬請查看。?課程總成績=形成性考核×50%+終結(jié)性考試×50%形考任務(wù)1一、單項(xiàng)選擇題（每小題3分，共60分）題目1把數(shù)據(jù)存儲到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為（）。選擇一項(xiàng)：A.算法的具體實(shí)現(xiàn)B.邏輯結(jié)構(gòu)C.給相關(guān)變量分配存儲單元D.物理結(jié)構(gòu)題目2下列說法中，不正確的是（）。選擇一項(xiàng)：A.數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)識單位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è)存儲結(jié)點(diǎn)存儲一個(gè)（）。選擇一項(xiàng)：A.數(shù)據(jù)項(xiàng)B.數(shù)據(jù)類型C.數(shù)據(jù)元素D.數(shù)據(jù)結(jié)構(gòu)題目4數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（）。選擇一項(xiàng)：A.存儲結(jié)構(gòu)B.物理結(jié)構(gòu)C.邏輯結(jié)構(gòu)D.物理和存儲結(jié)構(gòu)題目5在線性表的順序結(jié)構(gòu)中，以下說法正確的是（）。選擇一項(xiàng)：A.進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高B.數(shù)據(jù)元素是不能隨機(jī)訪問的C.邏輯上相鄰的元素在物理位置上不一定相鄰D.邏輯上相鄰的元素在物理位置上也相鄰題目6對鏈表,以下敘述中正確的是（）。選擇一項(xiàng)：A.可以通過下標(biāo)對鏈表進(jìn)行直接訪問B.插入刪除元素的操作一定要要移動(dòng)結(jié)點(diǎn)C.不能隨機(jī)訪問任一結(jié)點(diǎn)D.結(jié)點(diǎn)占用的存儲空間是連續(xù)的題目7下列的敘述中，不屬于算法特性的是（）。選擇一項(xiàng)：A.可行性B.有窮性C.可讀性D.輸入性題目8算法的時(shí)間復(fù)雜度與（）有關(guān)。選擇一項(xiàng)：A.所使用的計(jì)算機(jī)B.計(jì)算機(jī)的操作系統(tǒng)C.數(shù)據(jù)結(jié)構(gòu)D.算法本身題目9設(shè)有一個(gè)長度為n的順序表，要在第i個(gè)元素之前（也就是插入元素作為新表的第i個(gè)元素），插入一個(gè)元素，則移動(dòng)元素個(gè)數(shù)為（）。選擇一項(xiàng)：A.n-i-1B.iC.n-i+1D.n-i題目10設(shè)有一個(gè)長度為n的順序表，要?jiǎng)h除第i個(gè)元素移動(dòng)元素的個(gè)數(shù)為（）。選擇一項(xiàng)：A.iB.n-i-1C.n-iD.n-i+1題目11在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q所指結(jié)點(diǎn)，可用語句（）。選擇一項(xiàng)：A.p->next=q->nextB.p->next=qC.p=q->nextD.q->next=NULL題目12在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（）。選擇一項(xiàng)：A.p->next=s->next;B.s->next=p->next;p->next=s;C.p=s->nextD.p->next=s;s->next=p->next題目13非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿足（）（設(shè)頭指針為head，指針p指向尾結(jié)點(diǎn)）。選擇一項(xiàng)：A.p->next==NULLB.p->next==headC.p==headD.p==NULL題目14鏈表不具有的特點(diǎn)是（）。選擇一項(xiàng)：A.邏輯上相鄰的元素在物理位置上不一定相鄰B.不必事先估計(jì)存儲空間C.可隨機(jī)訪問任一元素D.插入刪除不需要移動(dòng)元素題目15帶頭結(jié)點(diǎn)的鏈表為空的判斷條件是（）（設(shè)頭指針為head）。選擇一項(xiàng)：A.head->next==headB.head->next==NULLC.head==NULLD.head!=NULL題目16在一個(gè)長度為n的順序表中為了刪除第5個(gè)元素，由第6個(gè)元素開始從后到前依次移動(dòng)了15個(gè)元素。則原順序表的長度為（）。選擇一項(xiàng)：A.21B.25C.20D.19題目17有關(guān)線性表的正確說法是（）。選擇一項(xiàng)：A.除了一個(gè)和最后一個(gè)元素外，其余元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼B.每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼C.表中的元素必須按由小到大或由大到下排序D.線性表至少要求一個(gè)元素題目18向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素，并保持原來的順序不變，平均要移動(dòng)（）個(gè)元素。選擇一項(xiàng)：A.7B.63C.63.5D.8題目19一個(gè)順序表第一個(gè)元素的存儲地址是90，每個(gè)元素的長度為2，則第6個(gè)元素的地址是（）。選擇一項(xiàng)：A.102B.106C.100D.98題目20在一個(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;和（）。選擇一項(xiàng)：A.p->next=qB.q->next=pC.p=q->nextD.q=p二、判斷題（每小題2分，14題，共28分）題目21數(shù)據(jù)元素可以有一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成。選擇一項(xiàng)：對錯(cuò)題目22數(shù)據(jù)元素之間的抽象關(guān)系稱為物理結(jié)構(gòu)。選擇一項(xiàng)：對錯(cuò)題目23數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為邏輯結(jié)構(gòu)。選擇一項(xiàng)：對錯(cuò)題目24數(shù)據(jù)的邏輯結(jié)構(gòu)是與存儲該結(jié)構(gòu)的計(jì)算機(jī)相關(guān)的。選擇一項(xiàng)：對錯(cuò)題目25數(shù)據(jù)結(jié)構(gòu)中,元素之間存在多對多的關(guān)系稱為樹狀結(jié)構(gòu)。選擇一項(xiàng)：對錯(cuò)題目26通?？梢园岩槐竞胁煌鹿?jié)的書的目錄結(jié)構(gòu)抽象成線性結(jié)構(gòu)。選擇一項(xiàng)：對錯(cuò)題目27通?？梢园涯吵鞘兄懈鞴徽军c(diǎn)間的線路圖抽象成樹型結(jié)構(gòu)。選擇一項(xiàng)：對錯(cuò)題目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)，可用語句p=p->next;。選擇一項(xiàng)：對錯(cuò)題目29設(shè)有一個(gè)單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，p指向尾結(jié)點(diǎn)，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句p->next=head。選擇一項(xiàng)：對錯(cuò)題目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)。選擇一項(xiàng)：對錯(cuò)題目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；的操作。選擇一項(xiàng)：對錯(cuò)題目32要在一個(gè)單向鏈表中刪除p所指向的結(jié)點(diǎn)，已知q指向p所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，則可執(zhí)行q->next=p->next；選擇一項(xiàng)：對錯(cuò)題目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；。選擇一項(xiàng)：對錯(cuò)題目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；。選擇一項(xiàng)：對錯(cuò)三、程序填空題（每小題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”,;;}while;}p?>datap=p?>nextp!=NULL題目36設(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->data;while）q=q->next;q->next=head;q=p;p=p->next;while(p->data!=x){q=p;}s->next=p;形考任務(wù)2一、單項(xiàng)選擇題（每小題2分，共50分）題目1若讓元素1，2，3依次進(jìn)棧，則出棧順序不可能為（）。選擇一項(xiàng)：A.3，1，2B.3，2，1C.2，1，3D.1，3，2題目2一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4。則隊(duì)列的輸出序列是（）。選擇一項(xiàng)：A.1，4，3，2B.4，3，2，1C.3，2，4，1D.1，2，3，4題目3向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)（）。選擇一項(xiàng)：A.先后次序無關(guān)緊要B.先存入元素，再移動(dòng)棧頂指針C.同時(shí)進(jìn)行D.先移動(dòng)棧頂指針，再存入元素題目4在一個(gè)棧頂指針為top的鏈棧中，將一個(gè)p指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行（）。選擇一項(xiàng)：A.p->next=top->next;top->next=p;B.p->next=top->next;top=top->next;C.p->next=top;top=p;D.top->next=p;題目5在一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（）。選擇一項(xiàng)：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判斷一個(gè)順序隊(duì)列（最多元素為m）為空的條件是（）。選擇一項(xiàng)：A.front==rearB.front==rear+1C.rear==m-1D.rear=m題目7判斷一個(gè)循環(huán)隊(duì)列為滿的條件是（）。選擇一項(xiàng)：A.rear=MaxSizeB.(rear+1)%MaxSize==frontC.front==rear+1D.rear%MaxSize==front題目8判斷棧滿（元素個(gè)數(shù)最多n個(gè)）的條件是（）。選擇一項(xiàng)：A.top==n-1B.top=-1C.top!=0D.top==0題目9設(shè)有一個(gè)20階的對稱矩陣A（第一個(gè)元素為a1,1），采用壓縮存儲的方式，將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣元素a6,2在一維數(shù)組B中的下標(biāo)是（）。選擇一項(xiàng)：A.17B.28C.21D.23題目10在解決計(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)。選擇一項(xiàng)：A.數(shù)組B.堆棧C.線性表D.隊(duì)列題目11一個(gè)遞歸算法必須包括（）。選擇一項(xiàng)：A.終止條件和迭代部分B.遞歸部分C.迭代部分D.終止條件和遞歸部分題目12在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（）。選擇一項(xiàng)：A.f=f->next;B.r=r->next;C.r=f->next;D.f=r->next;題目13在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算為（）。選擇一項(xiàng)：A.r->next=s;r=s;B.s->next=f;f=s;C.s->next=r;r=s;D.f->next=s;f=s;題目14數(shù)組a經(jīng)初始化chara[]=“English”;a[7]中存放的是（）。選擇一項(xiàng)：A."h"B.字符hC.字符串的結(jié)束符D.變量h題目15設(shè)主串為“ABcCDABcdEFaBc”，以下模式串能與主串成功匹配的是（）。選擇一項(xiàng)：A.BCdB.ABCC.BcdD.Abc題目16字符串a(chǎn)1="AEIJING"，a2="AEI"，a3="AEFANG"，a4="AEFI"中最大的是（）。選擇一項(xiàng)：A.a4B.a1C.a3D.a2題目17兩個(gè)字符串相等的條件是（）。選擇一項(xiàng)：A.兩串包含的字符相同B.兩串的長度相等C.兩串的長度相等，并且兩串包含的字符相同D.兩串的長度相等，并且對應(yīng)位置上的字符相同題目18一維數(shù)組A采用順序存儲結(jié)構(gòu)，每個(gè)元素占用6個(gè)字節(jié)，第6個(gè)元素的存儲地址為100，則該數(shù)組的首地址是（）。選擇一項(xiàng)：A.70B.28C.90D.64題目19一個(gè)非空廣義表的表頭（）。選擇一項(xiàng)：A.只能是原子B.可以是子表或原子C.不可能是原子D.只能是子表題目20對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表，一個(gè)10行8列的稀疏矩陣A，其相應(yīng)的三元組表共有6個(gè)元素，矩陣A共有（）個(gè)零元素。選擇一項(xiàng)：A.10B.74C.8D.72題目21對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表，一個(gè)10行8列的稀疏矩陣A共有73個(gè)零元素，A的右下角元素為6，其相應(yīng)的三元組表中的第7個(gè)元素是（）。選擇一項(xiàng)：A.（10，8，6）B.（10，8，7）C.（7，8，10）D.（7，10，8）題目22對一個(gè)棧頂指針為top的鏈棧進(jìn)行入棧操作，通過指針變量p生成入棧結(jié)點(diǎn)，并給該結(jié)點(diǎn)賦值a，則執(zhí)行:p=(structnode*)malloc(sizeof(structnode);p->data=a;和（）。選擇一項(xiàng)：A.p->next=top;top=p;B.top->next=p;p=top;C.p->next=top;p=top;D.top=top->next;p=top;題目23頭指針為head的帶頭結(jié)點(diǎn)的單向鏈表為空的判定條件是（）為真。選擇一項(xiàng)：A.head==NULLB.head->next==NULLC.head->next!=NULLD.head->next!=NULL題目24設(shè)有一個(gè)對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從1開始），B數(shù)組共有55個(gè)元素,則該矩陣是（）階的對稱矩陣。選擇一項(xiàng)：A.10B.5C.15D.20題目25數(shù)組a經(jīng)初始化chara[]=“English”;a[1]中存放的是（）。選擇一項(xiàng)：A."n"B."E"C.字符nD.字符E二、判斷題（每小題2分，16題，共32分）題目26設(shè)有一個(gè)鏈棧，棧頂指針為hs，現(xiàn)有一個(gè)s所指向的結(jié)點(diǎn)要入棧，則可執(zhí)行操作。hs=s；s->next=hs;選擇一項(xiàng)：對錯(cuò)題目27設(shè)有一個(gè)非空的鏈棧，棧頂指針為hs，要進(jìn)行出棧操作，用x保存出棧結(jié)點(diǎn)的值，棧結(jié)點(diǎn)的指針域?yàn)閚ext，則可執(zhí)行hs=hs->next;x=hs->data;選擇一項(xiàng)：對錯(cuò)題目28有一個(gè)鏈棧，棧頂指針為h，現(xiàn)有一個(gè)p所指向的結(jié)點(diǎn)要入棧，則可執(zhí)行操作p->next=h;和h=p；選擇一項(xiàng)：對錯(cuò)題目29設(shè)有一個(gè)非空的鏈棧，棧頂指針為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;選擇一項(xiàng)：對錯(cuò)題目30在一個(gè)鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext，則插入所指結(jié)點(diǎn)的操作為r->next=s；r=s；選擇一項(xiàng)：對錯(cuò)題目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；選擇一項(xiàng)：對錯(cuò)題目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ì)操作，并用變量x存放出隊(duì)元素的數(shù)據(jù)值，則相關(guān)操作為x=f->data;f=f->next;選擇一項(xiàng)：對錯(cuò)題目33對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表，一個(gè)6行7列的稀疏矩陣A相應(yīng)的三元組表共有8個(gè)元素,則矩陣A共有34個(gè)零元素。選擇一項(xiàng)：對錯(cuò)題目34循環(huán)隊(duì)列的最大存儲空間為MaxSize，隊(duì)頭指針為f，隊(duì)尾指針為r，當(dāng)（r+1）%MaxSize=f時(shí)表明隊(duì)列已滿。選擇一項(xiàng)：對錯(cuò)題目35循環(huán)隊(duì)列的隊(duì)頭指針為f，隊(duì)尾指針為r，當(dāng)r==f時(shí)表明隊(duì)列已滿。選擇一項(xiàng)：對錯(cuò)題目36空串的長度是0；空格串的長度是空格字符的個(gè)數(shù)。選擇一項(xiàng)：對錯(cuò)題目37對稀疏矩陣進(jìn)行壓縮存儲，矩陣中每個(gè)非零元素對應(yīng)的三元組包括該元素的行下標(biāo)、列下標(biāo)、和非零元素值三項(xiàng)信息。選擇一項(xiàng)：對錯(cuò)題目38循環(huán)隊(duì)列的引入，目的是為了克服假上溢。選擇一項(xiàng)：對錯(cuò)題目39設(shè)有n階對稱矩陣A，用一維數(shù)組s壓縮存儲A的下三角元素，s的下標(biāo)從零開始，元素s[26]相應(yīng)于A中的元素為a7,5。選擇一項(xiàng)：對錯(cuò)題目40循環(huán)隊(duì)列的最大存儲空間為MaxSize=6，采用少用一個(gè)元素空間以有效的判斷?？栈驐M，若隊(duì)頭指針front=4，當(dāng)隊(duì)尾指針rear=3時(shí)隊(duì)滿。選擇一項(xiàng)：對錯(cuò)題目41循環(huán)隊(duì)列的最大存儲空間為MaxSize=6，采用少用一個(gè)元素空間以有效的判斷棧空或棧滿，若隊(duì)頭指針front=4，隊(duì)尾指針rear=3時(shí)，隊(duì)列中共有5個(gè)元素。選擇一項(xiàng)：對錯(cuò)三、程序選擇填空題（每小題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;p->data=x;;;}A.sizeof(structnode)top=pp?>next=top題目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;p->data=x;p->next=NULL;;rear=;}形考任務(wù)3一、單項(xiàng)選擇題（每小題2分，共38分）題目1假定一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30，則葉子結(jié)點(diǎn)數(shù)為（）。選擇一項(xiàng)：A.47B.16C.17D.15題目2二叉樹第k層上最多有（）個(gè)結(jié)點(diǎn)。選擇一項(xiàng)：A.2k-1B.2k-1C.2k-1D.2k題目3將含有150個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點(diǎn)進(jìn)行編號，根結(jié)點(diǎn)的編號為1，則編號為69的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為（）。選擇一項(xiàng)：A.36B.35C.34D.33題目4如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹的帶權(quán)路徑長度最小，則該樹稱為（）。選擇一項(xiàng)：A.二叉樹B.哈夫曼樹C.完全二叉樹D.平衡二叉樹題目5在一棵度具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（）。選擇一項(xiàng)：A.16B.32C.31D.33題目6一棵完全二叉樹共有6層，且第6層上有6個(gè)結(jié)點(diǎn)，該樹共有（）個(gè)結(jié)點(diǎn)。選擇一項(xiàng)：A.31B.37C.38D.72題目7利用3、6、8、12這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹中所有葉子結(jié)點(diǎn)中的最長帶權(quán)路徑長度為（）。選擇一項(xiàng)：A.18B.16C.30D.12題目8在一棵樹中，（）沒有前驅(qū)結(jié)點(diǎn)。選擇一項(xiàng)：A.樹根結(jié)點(diǎn)B.葉結(jié)點(diǎn)C.空結(jié)點(diǎn)D.分支結(jié)點(diǎn)題目9設(shè)一棵采用鏈?zhǔn)酱鎯Φ亩鏄?，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2，該樹結(jié)點(diǎn)中共有20個(gè)指針域?yàn)榭?則該樹有（）個(gè)葉結(jié)點(diǎn)。選擇一項(xiàng)：A.9B.10C.21D.22題目10在一個(gè)圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的（）倍。選擇一項(xiàng)：A.2B.1C.4D.1/2題目11鄰接表是圖的一種（）。選擇一項(xiàng)：A.鏈?zhǔn)酱鎯Y(jié)構(gòu)B.順序存儲結(jié)構(gòu)C.散列存儲結(jié)構(gòu)D.索引存儲結(jié)構(gòu)題目12圖的深度優(yōu)先遍歷算法類似于二叉樹的（）遍歷。選擇一項(xiàng)：A.先序B.后序C.層次D.中序題目13已知下圖所示的一個(gè)圖，若從頂點(diǎn)V1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。選擇一項(xiàng)：A.V1V2V4V5V8V3V6V7B.V1V3V6V7V2V4V5V8C.V1V2V4V8V3V5V6V7D.V1V2V4V8V5V3V6V7題目14已知如下圖所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。選擇一項(xiàng)：A.aedfcbB.abecdfC.aebcfdD.aecbdf題目15圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。選擇一項(xiàng)：A.一對多B.多對多C.每一個(gè)元素都有一個(gè)且只有一個(gè)直接前驅(qū)和一個(gè)直接后繼D.一對一題目16在一棵二叉樹中，若編號為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號為（）。選擇一項(xiàng)：A.2i+1B.2i-1C.2iD.2i+2題目17一棵具有16個(gè)結(jié)點(diǎn)的完全二叉樹，共有（）層。(設(shè)根結(jié)點(diǎn)在第一層)選擇一項(xiàng)：A.7B.5C.6D.4題目18對二叉排序樹進(jìn)行（）遍歷，可以使遍歷所得到的序列是有序序列。選擇一項(xiàng)：A.按層次B.中序C.前序D.后序題目19已知一個(gè)圖的邊數(shù)為m，則該圖的所有頂點(diǎn)的度數(shù)之和為（）。選擇一項(xiàng)：A.m/2B.mC.2mD.2m+1二、判斷題（每小題1分，共10分）題目20一棵二叉樹的葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）數(shù)為5，單分支結(jié)點(diǎn)數(shù)為2，該樹共有11個(gè)結(jié)點(diǎn)。選擇一項(xiàng)：對錯(cuò)題目21一棵有14個(gè)結(jié)點(diǎn)的完全二叉樹，則它的最高層上有7個(gè)結(jié)點(diǎn)。選擇一項(xiàng)：對錯(cuò)題目22一棵二叉樹有6個(gè)葉結(jié)點(diǎn)，則該樹總共有11個(gè)結(jié)點(diǎn)。選擇一項(xiàng)：對錯(cuò)題目23根據(jù)搜索方法的不同，圖的遍歷有．先序；中序；后序三種方法。選擇一項(xiàng)：對錯(cuò)題目24對于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)中共有n-1個(gè)指針域空。選擇一項(xiàng)：對錯(cuò)題目25設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點(diǎn)的編號為奇數(shù)，該葉結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為10，該完全二叉樹一共有21個(gè)結(jié)點(diǎn)。選擇一項(xiàng)：對錯(cuò)題目26設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點(diǎn)的編號為偶數(shù)，該葉結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為9，該完全二叉樹一共有19個(gè)結(jié)點(diǎn)。選擇一項(xiàng)：對錯(cuò)題目27按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有深度優(yōu)先遍歷和深度優(yōu)先遍兩種方法。選擇一項(xiàng)：對錯(cuò)題目28一棵有8個(gè)權(quán)重值構(gòu)造的哈夫曼數(shù)，共有17個(gè)結(jié)點(diǎn)。選擇一項(xiàng)：對錯(cuò)題目29一棵有7個(gè)葉結(jié)點(diǎn)的二叉樹，其1度結(jié)點(diǎn)數(shù)的個(gè)數(shù)為2，則該樹共有15個(gè)結(jié)點(diǎn)。選擇一項(xiàng)：對錯(cuò)三、程序填空題（每空6分，共12分。請點(diǎn)擊正確選項(xiàng)，然后拖拽至相應(yīng)的方框上）題目30以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。完成程序中空格部分。題目31以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。四、綜合應(yīng)用題（每小題8分，5題，共40分）題目32題目33題目34題目35題目36形考任務(wù)4一、單項(xiàng)選擇題（每小題2分，共40分）題目1對線性表進(jìn)行二分查找時(shí)，要求線性表必須（）。選擇一項(xiàng)：A.以鏈接存儲方式B.以鏈接存儲方式，且數(shù)據(jù)元素有序C.以順序存儲方式D.以順序存儲方式，且數(shù)據(jù)元素有序題目2采用順序查找方法查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為（）。選擇一項(xiàng)：A.nB.(n-1)/2C.n/2D.(n+1)/2題目3有一個(gè)長度為10的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。選擇一項(xiàng)：A.29/9B.29/10C.26/10D.31/10題目4已知一個(gè)有序表為{11,22,33,44,55,66,77,88,99}，則順序查找元素55需要比較（）次。選擇一項(xiàng)：A.6B.3C.5D.4題目5有數(shù)據(jù){53,30,37,12,45,24,96}，從空二叉樹開始逐個(gè)插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，應(yīng)該選擇的序列是（）。選擇一項(xiàng)：A.12,24,30,37,45,53,96B.30,24,12,37,45,96,53C.45,24,53,12,37,96,30D.37,24,12,30,53,45,96題目6對于順序存儲的有序表{5,12,20,26,37,42,46,50,64}，若采用折半查找，則查找元素26的比較次數(shù)是（）。選擇一項(xiàng)：A.4B.6C.3D.5題目7在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄初始排列秩序無關(guān)的是（）。選擇一項(xiàng)：A.希爾排序B.直接選擇排序C.冒泡排序D.直接插入排序題目8從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱為（）。選擇一項(xiàng)：A.插入排序B.選擇排序C.歸并排序D.交換排序題目9依次將每兩個(gè)相鄰的有序表合并成一個(gè)有序表的排序方法稱為（）。選擇一項(xiàng)：A.交換排序B.歸并排序C.插入排序D.選擇排序題目10當(dāng)兩個(gè)元素出現(xiàn)逆序的時(shí)候就交換位置，這種排序方法稱為（）。選擇一項(xiàng)：A.選擇排序B.插入排序C.歸并排序D.交換排序題目11每次把待排序的區(qū)間劃分為左、右兩個(gè)子區(qū)間，其中左區(qū)間中記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄的關(guān)鍵字，右區(qū)間中記錄的關(guān)鍵字均大于等于基準(zhǔn)記錄的關(guān)鍵字，這種排序稱為（）。選擇一項(xiàng)：A.插入排序B.快速排序C.堆排序D.歸并排序題目12一組記錄的關(guān)鍵字序列為（46,20,30,79，56，38，40，84,90,110），利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（）。選擇一項(xiàng)：A.40，20,30,38，46，56，79，84,90,110B.20,3038，40，46，56，79，84,90,100C.20,30,40，38，46，79，56，84,90,100D.30,20,40，38，46，84，56，79,90,100題目13在有序表{10,14，34，43，47，64，75，80，90}中，用折半查找法查找值80時(shí)，經(jīng)（）次比較后查找成功。選擇一項(xiàng)：A.5B.3C.2D.4題目14對序列（49，38，65，97，76，13