國家開放大學(xué)數(shù)據(jù)結(jié)構(gòu)（本）期末考試復(fù)習(xí)資料匯編

數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題2020秋季第一章緒論超越高度溫馨提醒：可以使用word査找功能快速査找對應(yīng)題目和答案。査找快捷鍵：Ctrl+F一、選擇題1、 把數(shù)據(jù)存儲到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為（）o給相關(guān)變量分配存儲單元物理結(jié)構(gòu)算法的具體實(shí)現(xiàn)邏輯結(jié)構(gòu)2、 下列說法中，不正確的是（）o數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)識單位數(shù)據(jù)元素是數(shù)據(jù)的基本單位數(shù)據(jù)可有若干個數(shù)據(jù)元素構(gòu)成數(shù)據(jù)項(xiàng)可由若干個數(shù)據(jù)元素構(gòu)成3、 一個存儲結(jié)點(diǎn)存儲一個（）。數(shù)據(jù)元素?cái)?shù)據(jù)結(jié)構(gòu)數(shù)據(jù)項(xiàng)數(shù)據(jù)類型4、 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（）。存儲結(jié)構(gòu)物理和存儲結(jié)構(gòu)物理結(jié)構(gòu)邏輯結(jié)構(gòu)5、 下列的敘述中，不屬于算法特性的是（）?？尚行暂斎胄钥勺x性有窮性6、 算法的時間復(fù)雜度與()有關(guān)。計(jì)算機(jī)的操作系統(tǒng)算法本身數(shù)據(jù)結(jié)構(gòu)所使用的計(jì)算機(jī)。7、 下面程序段的時間復(fù)雜度是()。i=s=O;while(s<n)(i++；s+=i;}A.O(n0.5) B.O(log2n)C.0(n) D.O(l)8、 下面程序段的時間復(fù)雜度是()ointffunsignedintn){if(n==0||n==l)return1;elsereturnn*f(n-l);}A.O(l) B.O(log2n)C.O(n!)D.O(n)10、 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為( )。動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) D.線性結(jié)構(gòu)和非線性結(jié)構(gòu)11、 執(zhí)行下面程序段時，執(zhí)行S語句的次數(shù)為( )。for(inti=l;i<=n;i++)for(intj=l;i<=i;j++)S;A.n2 B.n2/2 C.n(n+1) D.n(n+l)/212、 數(shù)據(jù)的存儲結(jié)構(gòu)包括數(shù)據(jù)元素的表示和()o數(shù)據(jù)元素間的關(guān)系的表示數(shù)據(jù)處理的方法數(shù)據(jù)元素的類型相關(guān)算法13、樹狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。一對一多對多每一個元素都有一個直接前驅(qū)和一個直接后繼一對多14、一種邏輯結(jié)構(gòu)（ ）。與存儲該邏輯結(jié)構(gòu)的計(jì)算機(jī)相關(guān)只能有唯一的存儲結(jié)構(gòu)可以有不同的存儲結(jié)構(gòu)是指某一種數(shù)據(jù)元素的性質(zhì)15、把數(shù)據(jù)存儲到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為（ ）。邏輯結(jié)構(gòu)數(shù)據(jù)元素的存儲存儲結(jié)構(gòu)給數(shù)據(jù)元素分配存儲空間二、判斷題數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立的。（）算法和程序原則上沒有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時二者是通用的。（）數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。（）算法和程序都應(yīng)具有下面一些特征：有輸入，有輸出，確定性，有窮性，有效性。（）只有用面向?qū)ο蟮挠?jì)算機(jī)語言才能描述數(shù)據(jù)結(jié)構(gòu)算法。（）數(shù)據(jù)元素可以有一個或多個數(shù)據(jù)項(xiàng)組成。（）數(shù)據(jù)元素之間的抽象關(guān)系稱為物理結(jié)構(gòu)。（）數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為邏輯結(jié)構(gòu)。（）數(shù)據(jù)的邏輯結(jié)構(gòu)是與存儲該結(jié)構(gòu)的計(jì)算機(jī)相關(guān)的。（）數(shù)據(jù)結(jié)構(gòu)中,元素之間存在多對多的關(guān)系稱為樹狀結(jié)構(gòu)。（）通?？梢园涯吵鞘兄懈鞴徽军c(diǎn)間的線路圖抽象成樹型結(jié)構(gòu)。（通?？梢园岩槐竞胁煌鹿?jié)的書的目錄結(jié)構(gòu)抽象成線性結(jié)構(gòu)。（結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為圖形結(jié)構(gòu)。（）數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)可以由一個或多個數(shù)據(jù)項(xiàng)組成。（）三、程序題指出下列各算法的時間復(fù)雜度。1、intprimefintn){inti=l;intx=(int)sqrt(n);while(++i<=x)if(n%i==0)break;if(i>x)return1;elsereturn0;2、intsuml(intn)(intp=l,s=0;for(inti=l;i<=n;i++)(P*=i；s+=P；returns;3^intsum2(intn)ints=0;for(int1-1;l<-n;I++){intp=l;for(intj=l;j<=l;j++)P*=j；s+=p;}returns;}intfun(intn)(int1=1,s=l;while(s<n)s+=++l;returnI;第二章線性表一、選擇題1、 設(shè)有一個長度為n的順序表，要在第i個元素之前（也就是插入元素作為新表的第i個元素），插入一個元素，則移動元素個數(shù)為（Kn-i B.n-i-1 C.n-i+1 D.i2、 設(shè)有一個長度為n的順序表，要刪除第i個元素移動元素的個數(shù)為（）。I B.n-i-1 C.n-iD.n-i+13、 在一個單鏈表中，p、q分別指向表中兩個相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要刪除q所指結(jié)點(diǎn)，可用語句（）。q->next=NULL B.p->next=q->nextC.p=q->next D.p->next=q4、 在一個單鏈表中p所指結(jié)點(diǎn)之后插入一個s所指的結(jié)點(diǎn)時，可執(zhí)行（）。p->next=s;s->next=p->nextB.p->next=s->next;C.s->next=p->next;p->next=s;D.p=s->next5、 非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿足（）（設(shè)頭指針為head,指針p指向尾結(jié)點(diǎn)）。A.p->next==head B.p==NULLC.p==head D.p->next==NULL6、 鏈表不具有的特點(diǎn)是（）。不必事先估計(jì)存儲空間可隨機(jī)訪問任一元素邏輯上相鄰的元素在物理位置上不一定相鄰插入刪除不需要移動元素7、 帶頭結(jié)點(diǎn)的鏈表為空的判斷條件是（）（設(shè)頭指針為head）。head->next==headhead==NULLhead->next==NULLhead!=NULL8、在一個長度為n的順序表中為了刪除第5個元素，由第6個元素開始從后到前依次移動了15個元素。則原順序表的長度為（）。A.19B.21 C.20 D.259、 有關(guān)線性表的正確說法是（）。線性表至少要求一個元素每個元素都有一個直接前驅(qū)和一個直接后繼表中的元素必須按由小到大或由大到下排序除了一個和最后一個元素外，其余元素都有一個且僅有一個直接前驅(qū)和一個直接后繼10、 向一個有127個元素的順序表中插入一個新元素，并保持原來的順序不變,平均要移動（）個元素。A.63.5B.7C.63D.811、一個順序表第一個元素的存儲地址是90,每個元素的長度為2,則第6個元素的地址是（)oA.106B.98C.102 D.10012、 在一個不帶頭結(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)。可用的語句是p=p->next;和（ ）。A.q->next=p B.p->next=qC.q=p D.p=q->next13、 在線性表的順序結(jié)構(gòu)中，以下說法正確的是（）o邏輯上相鄰的元素在物理位置上不一定相鄰數(shù)據(jù)元素是不能隨機(jī)訪問的進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高邏輯上相鄰的元素在物理位置上也相鄰14、 對鏈表，以下敘述中正確的是（）o不能隨機(jī)訪問任一結(jié)點(diǎn)插入刪除元素的操作一定要要移動結(jié)點(diǎn)結(jié)點(diǎn)占用的存儲空間是連續(xù)的可以通過下標(biāo)對鏈表進(jìn)行直接訪問15、 設(shè)有一個長度為n的順序表，要在第i個元素之前（也就是插入元素作為新表的第i個元素），插入一個元素，則移動元素個數(shù)為（KA.n-i+1 B.iC.n-i-1 D.n-i16、 在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點(diǎn)，則執(zhí)行HL=p;p->next=HL;p->next=HL;HL=p;p->next=HL;p=HL;p->next=HL->next;HL->next=p;17、 在一個單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則以下操作哪個是正確的（ ）。s->next=p->next；p->next=s；p->next=s->next；s->next=p；p->next=s；s->next=q；q->next=s；s->next=p；18、 在循環(huán)雙鏈表的p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是（ ）。p->right=s；s->left=p；p->right->left=s；s->right=p->right；p->right=s；p->right->left=s；s->left=p；s->right=p->right；s->left=p；s->right=p->right；p->right=s；p->right->left=s；s->left=p；s->right=p->right：p->right->left=s：p->right=s；19、 若HL為一個不帶表頭結(jié)點(diǎn)的循環(huán)單鏈表的表頭指針，若有HL->next==HL條件存在，則該循環(huán)單鏈表是（ ）。A.空表 B.只有1個元素；C.空表或只有一個元素 D.非空表20、若HL為一個帶表頭結(jié)點(diǎn)的單鏈表的表頭指針，則該表為空表的條件是

)o)oA.HL==NULLHL->next==NULLA.HL==NULLHL->next==HL D.HL!=NULL21、設(shè)頭指針為head的非空的單向鏈表，指針p指向尾結(jié)點(diǎn)，則通過以下操作( )可使其成為單向循環(huán)鏈表。選擇一項(xiàng)：head=p; B.p=head;C.p->next=NULL; D.p->next=head;二、判斷題1、 設(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；o()2、 設(shè)有一個單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext,頭指針為head,p指向尾結(jié)點(diǎn)，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句p->next=heado()3、 設(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)。()4、 要在一個單向鏈表中p所指向的結(jié)點(diǎn)之后插入一個s所指向的新結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext,可執(zhí)行p->next=s;s->next=p->next；的操作。()5、 要在一個單向鏈表中刪除p所指向的結(jié)點(diǎn)，已知q指向p所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext,則可執(zhí)行q->next=p->nexto()6、 要在一個帶頭結(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；<>()7、 設(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；o()8、 設(shè)有一個長度為40的順序表，要刪除第8個元素需移動元素的個數(shù)為3。()9、 線性表用關(guān)鍵字的順序方式存儲，可以用二分法排序。()10、線性表用順序方式存儲可以隨機(jī)訪問。()三、程序填空1、設(shè)線性表以不帶頭結(jié)點(diǎn)的單向鏈表存儲，鏈表頭指針為head,以下程序的功能是輸岀鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)域data,完成程序中空格部分。ttdefineNULL0voidmain()(NODE*head,*p;P=head; /*p為工作指針*/do{printf("%d\n〃，TOC\o"1-5"\h\z[ 1 ]；[ 2 ]；}while[ 3 ]：2、 設(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)鏈表⑵插入結(jié)點(diǎn)s,使它成為a結(jié)點(diǎn)的直接前驅(qū)q=p;x=p->data;while([ 4 ])q=q->next;q->next=head;q=P；p=p->next;while(p->data!=x){q=p;[ 5 ]s->next=p;

3、設(shè)有一個不帶頭結(jié)點(diǎn)的單向鏈表，頭指針為head,p、prep是指向結(jié)點(diǎn)類型的指針，該鏈表在輸入信息時不慎把相鄰兩個結(jié)點(diǎn)的信息重復(fù)輸入，以下程序段是在該單向鏈表中查找這相鄰兩個結(jié)點(diǎn)，把該結(jié)點(diǎn)的數(shù)據(jù)域data打印岀來，并把其中之一從鏈表中刪除，填寫程序中的空格。prep=head;p=prep->next;while(p->data!=prep->data)(prep=p;[ 7 ]；}printf("min=%d”,[ 8 ])；prep->next=[]；prep->next=[]；-、選擇題1-若讓元素1,2,3,2,13,1,2第三章數(shù)組和廣義表3依次進(jìn)棧，則出棧順序不可能為（2,1,32.一個隊(duì)列的入隊(duì)序列是1,2,3,-、選擇題1-若讓元素1,2,3,2,13,1,2第三章數(shù)組和廣義表3依次進(jìn)棧，則出棧順序不可能為（2,1,32.一個隊(duì)列的入隊(duì)序列是1,2,3,4o則隊(duì)列的輸出序列是（）。4,3,2,11,2,3,41,4,3,23,2,4,13.一個棧的進(jìn)棧序列是10,20,30,40,50,則棧的不可能輸出序列是（（進(jìn)棧出棧可以交替進(jìn)行）。A.10,20,30,40,50B.40,30,50,10,20C.40,50,30,20,10D.50,40,30,20,104.元素4,6,8,10按順序依次進(jìn)棧,按該棧的可能輸出序列依次入隊(duì)列，該隊(duì)列的可能輸出序列是（）（進(jìn)棧出棧可以交替進(jìn)行）。A.10,8,4,610,6,4,88,4,6,1010,8,6,45.向順序棧中壓入新元素時，應(yīng)當(dāng)（）。A.先移動棧頂指針，再存入元素B.先存入元素，再移動棧頂指針C.先后次序無關(guān)緊要D.同時進(jìn)行）o6.在一個棧頂指針為top的鏈棧中,將一個p指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行（）oA.top->next=p;A.top->next=p;B.C.p->next=top;top=p;B.C.p->next=top;top=p;p->next=top->next;top->next=p;D.p->next=top->next;top=top->next;D.7.在一個棧頂指針為top的鏈棧中刪除一個結(jié)點(diǎn)時，用x保存被刪結(jié)點(diǎn)的值,則執(zhí)行（）o

x=top;top=top->next;x=top->data;top=top->next;x=top->data;x=top->data;top=top->next;8-一般情況下，將遞歸算法轉(zhuǎn)換成等價的非遞歸算法應(yīng)該設(shè)置（九A.棧 B.隊(duì)列C.堆?；蜿?duì)列 D.數(shù)組表達(dá)式a*（b+c）-d的后綴表達(dá)式是（ ）。+++abcd*+-B.abc+*d-C.abc*++d-D.-+*abcd判斷一個順序隊(duì)列sq（最多元素為m）為空的條件是（ ）。sq->rear-sq->front==m B.sq->rear-sq->front-l==mC.sq->front==sq->rear D.sq->front==sq->rear+l判斷一個循環(huán)隊(duì)列Q（最多元素為m）為滿的條件是（）。Q->front==Q->rearQ->front!=Q->rearQ->front==Q->rearQ->front!=Q->rearQ->front==（Q->rear+l）%mQ->front!=（Q->rear+l）%mQ->front==（Q->rear+l）%mQ->front!=（Q->rear+l）%m12.判斷棧s滿（元素個數(shù)最多n12.判斷棧s滿（元素個數(shù)最多n個）的條件是（A.s->top==0B.s->top!=0C.s->top==n-lD.s->top!=n-lC.s->top==n-lD.s->top!=n-l13.一個隊(duì)列的入隊(duì)順序是a,b,c,d,則離隊(duì)的順序是（A.a,d,cbB.a,b,c,dC.d,c,b,aD.c,b,d,a13.一個隊(duì)列的入隊(duì)順序是a,b,c,d,則離隊(duì)的順序是（A.a,d,cbB.a,b,c,dC.d,c,b,aD.c,b,d,a14.如果以鏈表作為棧的存儲結(jié)構(gòu),則退棧操作時（必須判斷棧是否滿判斷棧元素類型必須判斷棧是否滿判斷棧元素類型必須判斷棧是否空D.必須判斷棧是否空D.對棧不作任何判斷在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)中，而打印機(jī)則從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應(yīng)該是一個（）結(jié)構(gòu)。A.堆棧B.隊(duì)列打印，該緩沖區(qū)應(yīng)該是一個（）結(jié)構(gòu)。A.堆棧B.隊(duì)列C.數(shù)組D.先性表一個遞歸算法必須包括（A.遞歸部分B.A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分17.從一個棧頂指針為top的鏈棧中刪除一個結(jié)點(diǎn)時，用變量x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（A.x=top->data;top=top->next;B.x=top->data;C.top-top->next;x-top->data;D.top-top->next;x-data;18.在一個鏈隊(duì)中,假設(shè)f和C.迭代部分D.終止條件和迭代部分17.從一個棧頂指針為top的鏈棧中刪除一個結(jié)點(diǎn)時，用變量x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（A.x=top->data;top=top->next;B.x=top->data;C.top-top->next;x-top->data;D.top-top->next;x-data;18.在一個鏈隊(duì)中,假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個結(jié)點(diǎn)的運(yùn)算）。A.r=f->next;B.r=r->next;C.f=f->next;D.f=r->next;19.在一個鏈隊(duì)中,假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算為（）of->next=s;f=s;r->next=s;r=s;s->next=r;r=s;s->next=f;f=s;20.在一個不帶頭結(jié)點(diǎn)的鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則從該對列中刪除一個結(jié)點(diǎn)并把結(jié)點(diǎn)的值保存在變量x中的運(yùn)算為（ ）0+++A.x=r->data：r=r->next;r=r->next;x=r->datax=f->data；f=f->next;f=f->next;x=f->data21.棧和隊(duì)列的共同特點(diǎn)是（A.都是先進(jìn)后出B.A.都是先進(jìn)后出C.只容許在端點(diǎn)處插入和刪除元素D.都是先進(jìn)先出22.棧的插入和刪除操作在（ ）進(jìn)行。A.棧頂B.棧底C.任意位置D.指定位置23.C.只容許在端點(diǎn)處插入和刪除元素D.都是先進(jìn)先出22.棧的插入和刪除操作在（ ）進(jìn)行。A.棧頂B.棧底C.任意位置D.指定位置23.在一個順序隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的（ ）位置。A.前一個B-后一個C.當(dāng)前D.后面24.當(dāng)利用大小為n的數(shù)組順序存儲一個隊(duì)列時，該隊(duì)列的最大長度為（A.n-2B.n-1C.nD.n+125.從一個順序存儲的循環(huán)隊(duì)列中刪除一個元素時，首先需要（A.隊(duì)頭指針加一 B.隊(duì)頭指針減一

C.取出隊(duì)頭指針?biāo)傅脑谻.取出隊(duì)頭指針?biāo)傅脑厝〕鲫?duì)尾指針?biāo)傅脑囟?、判斷題鏈?zhǔn)綏Ｅc順序棧相比，一個明顯的優(yōu)點(diǎn)是通常不會出現(xiàn)棧滿的情況。（）在一個順序存儲的循環(huán)隊(duì)列中，隊(duì)頭指針指向隊(duì)頭元素的后一個位置。（）棧和隊(duì)列都是順序存取的線性表，但它們對存取位置的限制不同。（）若讓元素1,2,3依次進(jìn)棧，則岀棧次序1,3,2是不可能出現(xiàn)的情況。（）在用單鏈表表示的鏈?zhǔn)疥?duì)列Q中，隊(duì)頭指針為Q->front,隊(duì)尾指針為Q->rear,則隊(duì)空條件為Q->front==Q->rear。（）遞歸定義的數(shù)據(jù)結(jié)構(gòu)通常用遞歸算法來實(shí)現(xiàn)對它的操作。（）遞歸的算法簡單、易憧、容易編寫，而且執(zhí)行效率也高。（）遞歸調(diào)用算法與相同功能的非遞歸算法相比，主要問題在于重復(fù)計(jì)算太多，而旦調(diào)用本身需要分配額外的空間和傳遞數(shù)據(jù)和控制，所以時間與空間開銷通常都比較大。（）用非遞歸方法實(shí)現(xiàn)遞歸算法時一定要使用遞歸工作棧。（）棧是限定在表的一端進(jìn)行插入和刪除操作的線性表，又稱為先進(jìn)后出表。（）隊(duì)列的特性是先進(jìn)后出。（）往棧中插入元素的操作方式是：先寫入元素，后移動棧頂指針。（）循環(huán)隊(duì)列隊(duì)頭指針在隊(duì)尾指針前一個位置，隊(duì)列是“滿”狀態(tài)。（）在隊(duì)列的順序存儲結(jié)構(gòu)中，當(dāng)插入一個新的隊(duì)列元素時，尾指針后移，當(dāng)刪除一個元素隊(duì)列時，頭指針后移。（）向一個棧頂指針為h的鏈棧（結(jié)點(diǎn)的指針域?yàn)閚ext）中插入一個s所指結(jié)點(diǎn)時,先執(zhí)行s->next=h,再執(zhí)行h=s操作。（）一個遞歸算法不必包括遞歸終止條件。（）在一個鏈?zhǔn)疥?duì)列中，若隊(duì)頭指針與隊(duì)尾指針的值相同，則表示該隊(duì)列至多有1個結(jié)點(diǎn)。（）在用循環(huán)單鏈表表示的鏈?zhǔn)疥?duì)列中，可以不設(shè)隊(duì)頭指針，僅在鏈尾設(shè)置隊(duì)尾指針。（）

三、程序選擇題在下面空格處填寫一條語句，以使下面的鏈?zhǔn)疥?duì)列全部元素出隊(duì)的算法完整。intwrite(LinkQueue*q)(QueueNode*p;intwrite(LinkQueue*q)(QueueNode*p;if(q->front--q->rear){printf("隊(duì)空！無元素可取〃);exit(O);}while(q->front->next!=NULL)(p=q->front->next;q->front->next=p->next;printf("%4d",p->data);free(p);/*隊(duì)空*//*出隊(duì)*//*釋放己出隊(duì)結(jié)點(diǎn)*//*隊(duì)空時，頭尾指針指向頭結(jié)點(diǎn)*/q->front=q->rear;q=q->next;q->rear=q->front;p=p->next;在下面空格處填寫適當(dāng)?shù)恼Z句，以使下面的循環(huán)隊(duì)列的入隊(duì)和出隊(duì)算法完整defineMAXSIZE100;typedefcharElemtype;typedefstruct(Elemtypequeue[MAXSIZE];intfront,rear;)sequeuetype;SequeuetypeQ;intencqueue(sequeuetype*Q,elemtypex)if((Q->rear+l)%MAXSIZE==Q->front){printf(“隊(duì)列已滿!\n");return1;!else(Q->rear=(Q->rear+l)%MAXSIZE;(1)return0;})/*入隊(duì)算法*/Elemtypedel_cqueue(sequeuetype*Q){if((2) )(printf(“隊(duì)列為空!\n〃)；return1;}else{Q->front=(Q->front+l)%MAXSIZE;return(Q->queue[Q->front]);}}/*出隊(duì)算法*/(1)(Q->rear+l)%MAXSIZE==Q->front (2)Q->front=(Q->front+l)%MAXSIZE;⑴(Q->front+l)%MAXSIZE==Q->rear (2)Q->rear=(Q->rear+l)%MAXSIZE;⑴Q->front==Q->rear(2)Q->queue[Q->rear]=x;(1)Q->queue[Q->rear]=x;(2)Q->front==Q->rear寫出下列程序執(zhí)行后的結(jié)果SeqQueueQ;InitQueue(Q);inta[4]={5,8,12,15);forfinti=0;i<4;i++)lnQueue(Q,a[i]);lnQueue(Q,OutQueue(Q));lnQueue(Q,30);lnQueue(Q,OutQueue(Q)+10);while)IQueueEmpty(Q))printf("%d”,OutQueue(Q));執(zhí)行后的輸出結(jié)果為： 。58121530121553018812153018121551830寫出下列程序執(zhí)行后的結(jié)果SeqStackS;InitStack(S);Push(S,3);Push(S,4);Push(S,5);intx=Pop(S)+2*Pop(S);Push(S,x);inti,a[4]={5,8,12,15);for(i=0;i<4;i++)Push(S,a[i]);while(!StackEmpty(S))Printf("％d“,Pop⑸)；執(zhí)行后的輸出結(jié)果為： 。15128513335812131515 13 12 8 5 315 12 13 3 8 5在下面空格處填寫一條語句，以使下面的進(jìn)棧算法完整。voidPush(structSeqStack*szElemTypex)(If(s->top==MaxSize-l)(printf(w棧滿溢出錯誤!\n〃)；exit(l);s->data[s->top]=x;}s->top=s->data;s->data++;s->top++;s->data=s->top;在下面空格處填寫一條語句，以使下面的出棧算法完整。ElemTypePop(structSeqStack*szElemTypex)(If(StackEmpty(s))(printf(“棧下溢出錯誤！\n〃)；exit(l);}x=s->data[s->top];returnx;s->top-;s->data~;s->top=s->data;s->data=s->top;第四章字符串-、選擇題1.以下陳述中正確的是（ ）。A.串是一種特殊的線性表B-串的長度必須大于零C.串中元素只能是字母D.空串就是空白串2.設(shè)有兩個串p和q,其中q是p的子串，q在p中首次岀現(xiàn)的位置的算法稱為()。A.求子串B.連接C.匹配D.求串長3.串是（ ）。A.不少于一個字母的序列B.任意個字母的序列C.不少于一個字符的序列D.有限個字符的序列4.串的長度是指（ ）。A.串中所含不同字母的個數(shù)B.串中所含字符的個數(shù)C.串中所含不同字符的個數(shù)D.串中所含非空格字符的個數(shù)若串S=="English”，其子串的個數(shù)是（ ）。+++9B.16 C.36 D.28下面關(guān)于串的敘述中，不正確的是（ ）。A-串是字符的有限序列空串是由空格構(gòu)成的串模式匹配是串的一種重要運(yùn)算串即可以釆用順序存儲，也可以釆用鏈?zhǔn)酱鎯Υc普通的線性表相比較，它的特殊性體現(xiàn)在（ ）。A.順序的存儲結(jié)構(gòu)B.鏈接的存儲結(jié)構(gòu)C.數(shù)據(jù)元素是一個字符D.數(shù)據(jù)元素可以任意8-空串與空格串（ ）。BA.相同 B.不相同C.可能相同 D.無法確定9.兩個字符串相等的條件是（）。兩串的長度相等兩串包含的字符相同兩串的長度相等，并且兩串包含的字符相同兩串的長度相等，并且對應(yīng)位置上的字符相同TOC\o"1-5"\h\z串函數(shù)Strcat(a,b)的功能是進(jìn)行串( )。A.比較 B.復(fù)制 C.賦值 D.連接串函數(shù)StrCmp("ABCd”,“ABCD”)的值為( )。A.0 B.-1 C.1 D.3設(shè)主串為“FABcCDABcdEFaBc”，以下模式串能與主串成功匹配的是(A.EFaBc B.ABCdEC.DABCC D.FAbcC13.以下四個串中最小的是（）oA."ABADF" B.〃ABAFD〃C.'ABADFA" D."ABAF〃14.在實(shí)際應(yīng)用中，要輸入多個字符串，旦長度無法預(yù)定。則應(yīng)該采用( )存儲比較合適。A.鏈?zhǔn)紹.順序C.堆結(jié)構(gòu)D.無法確定二、 判斷題用字符數(shù)組存儲長度為n的字符串，數(shù)組長度至少為n+1。()串是一種特殊的線性表，其特殊性表現(xiàn)在組成串的數(shù)據(jù)元素都是字符。()串的兩種最基本的存儲方式是順序和鏈接。()4-空串的長度是1。()一個空格的串的長度是0。()6-兩個串相等的充分必要條件是每一個對應(yīng)位置的字符相同。()字符串a(chǎn)l="heijing”,a2=''hen”,a3="heifang”,a4="heni”最小的是a2o()串函數(shù)StrCmp("ABCd”，“ABCD”)的值為-1。()三、 程序選擇題一下程序段的結(jié)果是：c的值為( )char*a[5]={"12378”,"1237”,"1236789〃,"1237”,"123708"}inti,c=0for(i=0;i<5;i++)if(strcmp(a[i]//1237w)--0)C++；A.2 B.5 C.O D.1237以下程序段的結(jié)果是：c的值為( )+++chara[5]="1236789"；int*p=a,c=O;While(*p++)C++;A.8 B.7 C.10 D.12第五章數(shù)組和廣義表-、選擇題1.一維數(shù)組A采用順序存儲結(jié)構(gòu)，每個元素占用6個字節(jié)，第6個元素的存儲地址為100,則該數(shù)組的首地址是（)u+++A.64 B.28C.70 D.902.稀疏矩陣采用壓縮存儲的目的主要是（）。A-表達(dá)變得簡單B.對矩陣元素的存取變得簡單C.去掉矩陣中的多余元素D.減少不必要的存儲空間的開銷3.一個非空廣義表的表頭（ ）oA.不可能是原子B.只能是子表C.只能是原子D.可以是子表或原子4.常對數(shù)組進(jìn)行的兩種基本操作是（）。A.建立與刪除B.索引與修改C.査找和修改D.査找與索引設(shè)二維數(shù)組A[5][6]按行優(yōu)先順序存儲在內(nèi)存中，己知A[0][0]起始地址為1000,TOC\o"1-5"\h\z每個數(shù)組元素占用5個存儲單元，則元素A[4]⑷的地址為（ ）。A.1140 B.1145C.1120 D.1125設(shè)有一個20階的對稱矩陣A,采用壓縮存儲的方式，將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a9,2在一維數(shù)組B中的下標(biāo)是（ ）。A.41 B.32 C.18 D.38廣義表的（a,（d,a,b）,h,（e,（（iJ）,k）））深度是（ ）。A. 6 B. 10C. 8 D. 4廣義表（f,h,（a,b,d,c）,d,e,（（ij）,k））的長度是（ ）。A. 6 B. 10C. 8 D. 4設(shè)有一個廣義表A(a),其表尾為( )。A.a B.(()) C.() D.(a)下列廣義表中的線性表是( )。A.E(a,(b,c))B.E(a,E)C.E(a,b)D.E(a,L())二、判斷題使用三元組表示稀疏矩陣中的非零元素能節(jié)省存儲空間。()一個廣義表的表頭總是一個廣義表。()一個廣義表的表尾總是一個表。()一個廣義表((a),((b),c),(((d))))的長度為3,深度為4。()一個廣義表((a),((b),c),(((d))))的表尾是((b),c),(((d)))。()需要壓縮存儲的矩陣可分為特殊矩陣矩陣和稀疏矩陣矩陣兩種。()設(shè)廣義表L=((),()),則其表頭是(O)o()設(shè)廣義表L=((),()),則其表尾是()。()設(shè)廣義表L=((),()),則其長度是0。()廣義表A((a,b,c),(d,e,f))的表尾為((d,e,f))°()對稀疏矩陣進(jìn)行壓縮存儲，矩陣中每個非零元素對應(yīng)的三元組包括該元素的行號、列號和元素值三項(xiàng)信息。()設(shè)有n階對稱矩陣A,用一維數(shù)組s壓縮存儲A的下三角元素，s的下標(biāo)從零開始，元素s[26]相應(yīng)于A中的元素為a7,6。()第六章樹和二叉樹一、選擇題樹最適合用來表示（B.無序數(shù)據(jù)元素有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素2.3.4.C.元素之間具有分支層次關(guān)系的數(shù)據(jù)樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（A.1B.0對于一個滿二叉樹，m個樹葉，n個結(jié)點(diǎn),A.n=h+mB.h+m=2n如圖所示一棵二叉樹中，（C深度為5的二叉樹至多有（A.16B.2.3.4.C.元素之間具有分支層次關(guān)系的數(shù)據(jù)樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（A.1B.0對于一個滿二叉樹，m個樹葉，n個結(jié)點(diǎn),A.n=h+mB.h+m=2n如圖所示一棵二叉樹中，（C深度為5的二叉樹至多有（A.16B.32)oD.元素之間無聯(lián)系的數(shù)據(jù)C.2D.-l深度為h,則（C.m=h-1）不是完全二叉樹。）個結(jié)點(diǎn)。C.31）。D.n=2h-1D.106.假定一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15,單分支結(jié)點(diǎn)數(shù)為30,則葉子結(jié)點(diǎn)數(shù)6.為（）。A,15 B.16 C.177.二叉樹第k層上最多有（）個結(jié)點(diǎn)。D.47A.2k B.2k-l C.2k-l8.在一棵度具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（）oD.2k-lA.31 B.32 C.339,在一棵二叉樹上，第5層的結(jié)點(diǎn)數(shù)最多為（）。D.16A.8 B.15 C.1610.具有127個結(jié)點(diǎn)的完全二叉樹其深度為（）。D.32A.8 B.7 C.6D.511.設(shè)一棵二叉樹中沒有度為1的結(jié)點(diǎn)，已知葉子結(jié)點(diǎn)數(shù)為n.此樹的結(jié)點(diǎn)數(shù)為)<.

A.2n+2 B.2n+l C.2n D.2n-l設(shè)二叉樹中有n2個度為2的結(jié)點(diǎn)，nl個度為1的結(jié)點(diǎn)，nO個葉子結(jié)點(diǎn)，則此二叉樹中空指針域個數(shù)為（A.nO+nl+n2B.n2+nl+2n0C.2n2+nl D.2n0+nln個結(jié)點(diǎn)的二叉樹中，用二叉鏈表做存儲，非空指針數(shù)目為（）。A.nB.2nC.n-1D.n+1A.nB.2nC.n-1D.n+114.A.0B.1C.2D.15.在一非空二叉樹的中序遍歷序列中,14.A.0B.1C.2D.15.在一非空二叉樹的中序遍歷序列中,根結(jié)點(diǎn)的右邊（）。A.只有右子樹上的所有結(jié)點(diǎn)C.只有左子樹上的所有結(jié)點(diǎn)只有右子樹上的部分結(jié)點(diǎn)D.只有左子樹上的部分結(jié)點(diǎn)在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加（如圖所示二叉樹的中序遍歷序列是（）oB.dgbaechfC.gdbehfcaD.abcdefghA.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefghA.abdgcefh設(shè)n、m為一棵二叉樹上的兩個結(jié)點(diǎn)，中序遍歷時n在m前的條件是（）。A.n在m右方B.n是m祖先C.n在m左方D.n是m子孫某二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定（）。A.空或只有一個結(jié)點(diǎn)C.二叉排序樹A.空或只有一個結(jié)點(diǎn)C.二叉排序樹19.二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK中序遍歷：HFIEJKG該二叉樹根的右子樹的根是（）。A.E B.FB.完全二叉樹D.深度等于其結(jié)點(diǎn)數(shù)C.GD.H如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹的帶權(quán)路徑長度最小，則該樹稱為（）。A.哈夫曼樹 B.平衡二叉樹C.二叉樹D.完全二叉樹

利用n個值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹中共包含有（）個結(jié)點(diǎn)。A.n B.n+1 C.2*n D.2*n-l利用2、4、5、10這四個值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹中所有葉子的最長帶權(quán)路徑長度為（）。A.18 B.16哈夫曼樹是（）。A.滿二叉樹C.38 D.30B.二叉排序樹D.帶權(quán)路徑長度最短的二叉樹A.2n-lB.2nC.2n+lD.不確定樹的路徑長度最短的二叉樹24.用權(quán)值分別為15,2,4,5C.38 D.30B.二叉排序樹D.帶權(quán)路徑長度最短的二叉樹A.2n-lB.2nC.2n+lD.不確定二、判斷題1-樹是一種線性結(jié)構(gòu)。（）樹最適合表示元素之間具有層次關(guān)系的數(shù)據(jù)。（）如果結(jié)點(diǎn)A有3個兄弟，而且B是A的雙親，則B的度是4。（）樹中全部結(jié)點(diǎn)的度均大于0。（）森林是m（mNO）棵互不相交的樹的集合。（）深度為k的完全二叉樹至少有2k-l個結(jié)點(diǎn)。（）完全二叉樹中沒有度為1的結(jié)點(diǎn)。（）8-若樹的度為2時，該數(shù)為二叉樹。（）具有三個結(jié)點(diǎn)的二叉樹有五種。（）深度為5的二叉樹最多有3層。（）具有256個結(jié)點(diǎn)的完全二叉樹的深度為90（）貝有100個結(jié)點(diǎn)的完仝二叉樹有50個葉子。（）在二叉樹的鏈接存儲中，每個結(jié)點(diǎn)設(shè)置三個域：值域、左指針域和右指針域。（）二叉樹只能采用二叉鏈表來存儲。（）具有n個結(jié)點(diǎn)的二叉樹，釆用二叉鏈表存儲，共有n+1個空鏈域。（）二叉樹的前序遍歷序列中，任意一個結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面。（）巳知一棵樹的先序序列和后序序列，一定能構(gòu)造出該樹。（）二叉樹的遍歷就是按照一定次序訪問樹中所有結(jié)點(diǎn)，并且每個結(jié)點(diǎn)的值僅被訪問一次的過程。（）哈夫曼樹一定是完全二叉樹或滿二叉樹。（）哈夫曼樹只存在著雙支結(jié)點(diǎn)，不存在單支結(jié)點(diǎn)。（）三、本章綜合應(yīng)用或程序題（都用客觀選擇形式）有一棵樹如圖所示，回答下面問題：（1） 這棵樹的根結(jié)點(diǎn)是（）； b/T\j（2） 這棵樹的葉子結(jié)點(diǎn)是（）; e f（3） 這棵樹的度是（）； Tg（4） 這棵樹的深度是（）;（5） c結(jié)點(diǎn)的孩子結(jié)點(diǎn)是（）;（6） c結(jié)點(diǎn)的父母結(jié)點(diǎn)是（）。3 B.4C.aD.e、fE.b、e、d、g由如圖所示的二叉樹，回答以下問題：（6.4） 卜頂七（1） 其中序遍歷序列（）;（2） 其前序遍歷序列（）： 〉（3） 其后序遍歷序列（）; 1gdbeihfcaB.gbaechifC.abdgcefhi以3,4,5,8,9,作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹。該樹的帶權(quán)路徑長度為（）61B.62 C.63 D.65以2,3,4,7,8,9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹。權(quán)重值為4的葉結(jié)點(diǎn)的哈夫曼編碼為（）000B.001 C.010 D.10第七章圖一、單選題(共25題)TOC\o"1-5"\h\z在一個圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的( )倍。1/2124一個具有n個頂點(diǎn)的無向完全圖包含( )條邊。n(n-1)n(n+1)n(n-1)/2n(n+1)/2一個具有n個頂點(diǎn)的有向完全圖包含( )條邊。n(n-1)n(n+1)n(n-1)/2n(n+1)/2對于一個具有n個頂點(diǎn)和e條邊的無向圖，若釆用鄰接表表示，則所有頂點(diǎn)TOC\o"1-5"\h\z鄰接表中的結(jié)點(diǎn)總數(shù)為( )。ne2n2e在有向圖的鄰接表中，每個頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有( )鄰接點(diǎn)。入邊出邊入邊和出邊不是入邊也不是出邊鄰接表是圖的一種（）oA.順序存儲結(jié)構(gòu)B-鏈?zhǔn)酱鎯Y(jié)構(gòu)索引存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn),則該圖一定是（）o完全圖連通圖有冋路一棵樹下列有關(guān)圖遍歷的說法不正確的是（ ）。A.連通圖的深度優(yōu)先搜索是一個遞歸過程B-圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特征非連通圖不能用深度優(yōu)先搜索法圖的遍歷要求每一頂點(diǎn)僅被訪問一次無向圖的鄰接矩陣是一個（）o對稱矩陣零矩陣上三角矩陣對角矩陣圖的深度優(yōu)先遍歷算法類似于二叉樹的（ ）遍歷。先序中序后序?qū)哟蜧是一個非連通無向圖，共28條邊，則該圖至少有（ ）個頂點(diǎn)。678D.9在一個無向圖中，若兩頂點(diǎn)之間的路徑長度為k,則該路徑上的頂點(diǎn)數(shù)為()<.難度：+TOC\o"1-5"\h\zkk+1k+22kn個頂點(diǎn)的強(qiáng)連通圖中至少含有()。n—I條有向邊n條有向邊n(n—1)/2條有向邊n(n—1)條有向邊巳知如圖1所示的一個圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為( )。abecdfacfebdaedfcbaebcfd關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中()。從源點(diǎn)到匯點(diǎn)的最長路徑從源點(diǎn)到匯點(diǎn)的最短路徑最長的回路最短的回路下面（）可以判斷出一個有向圖中是否有環(huán)（回路）。廣度優(yōu)先遍歷拓?fù)渑判蚯笞疃搪窂角箨P(guān)鍵路徑采用鄰接表存儲的圖，其深度優(yōu)先遍歷類似于二叉樹的（）。中序遍歷先序遍歷后序遍歷按層次遍歷己知無向圖G的頂點(diǎn)數(shù)為n,邊數(shù)為e,其鄰接表表示的空間復(fù)雜度為（）。0（n2）O（n*e）O（n+e）0（2n）已知一個圖如下圖所示，若從頂點(diǎn)a出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。acfdebacfebdacbdefabecdf在無向圖中定義頂點(diǎn)vi與vj之間的路徑為從vi到vj的一個（）。A.頂點(diǎn)序列邊序列權(quán)值總和邊的條數(shù)在有向圖的逆鄰接表中，每個頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（）鄰接點(diǎn)。入邊出邊入邊和出邊不是出邊也不是入邊設(shè)G1=（V1,E1）和G2=（V2,E2）為兩個圖，如果VlcV2,ElcE2則稱（）。G1是G2的子圖G2是G1的子圖G1是G2的連通分量G2是G1的連通分量己知一個有向圖的鄰接矩陣表示，要刪除所有從第i個結(jié)點(diǎn)發(fā)出的邊，應(yīng)（將鄰接矩陣的第i行刪除將鄰接矩陣的第i行元素全部置為0將鄰接矩陣的第i列刪除將鄰接矩陣的第i列元素全部置為0二、判斷題圖的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列不是惟一的。（）鄰接表只能用于存儲有向圖，而鄰接矩陣則可存儲有向圖和無向圖。（）存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點(diǎn)個數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。（）A0V網(wǎng)是一個帶權(quán)的有向圖。（）從源點(diǎn)到終點(diǎn)的最短路徑是唯一的。（）圖的生成樹是惟一的。（）對連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點(diǎn)。（）有n個結(jié)點(diǎn)的無向圖中，若邊數(shù)大于n-1,則該圖是連通的。（）若一個有向圖的鄰接矩陣中對角線以下元素均為零，則該圖的拓?fù)溆行蛐蛄斜囟ù?。（）AOV網(wǎng)拓?fù)渑判虻慕Y(jié)果是惟一的。（）圖的廣度優(yōu)先搜索序列是惟一的。（）貝有n個頂點(diǎn)的無向圖釆用鄰接矩陣表示，圖中的邊數(shù)等于鄰接矩陣中非零元素之和的一半。（）若連通圖上各邊權(quán)值均不相同，則該圖的最小生成樹是惟一的。（）無向圖的鄰接矩陣一定是對稱的。（）有向圖的鄰接矩陣一定是非對稱的。（）用鄰接矩陣存儲圖的時候，占用空間大小不但與圖的結(jié)點(diǎn)個數(shù)有關(guān)還與圖的邊數(shù)有關(guān)。（）圖的連通分量是無向圖的極小連通子圖。（）圖的強(qiáng)連通分量是無向圖的極大連通子圖。（）對任意一個圖從它的某個頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索遍歷可訪問到該圖的每個頂點(diǎn)。（）一個有向圖的鄰接表和逆鄰接表中的節(jié)點(diǎn)個數(shù)一定相等。（）有向圖用鄰接矩陣表示后，頂點(diǎn)i的出度等于第i行中非0且非無窮的元素個數(shù)。（）圖G的某一最小生成樹的代價一定小于其他生成樹的代價。（）任一個有向圖的拓?fù)湫蛄兄挥幸粋€。（）一個無向連通圖的生成樹是含有該連通圖的全部頂點(diǎn)的極小連通子圖。（）采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的按層次遍歷。（）三、程序填空題（2題，附加題）1.己知圖G的鄰接矩陣如下所示：從頂點(diǎn)1出發(fā)的廣度優(yōu)先搜索序列為（）。1；2,3,4；5；62；1,3,5；4：63；1,2,4；5；6

D.4；2,3,6；1；5co65ooooco65oooo6co15586co155883885oo8588423oo64oo2no66oo2.對于一個無向圖，假定釆用鄰接矩陣表示,2.對于一個無向圖，假定釆用鄰接矩陣表示,試分別寫出從頂點(diǎn)0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。先搜索遍歷得到的頂點(diǎn)序列。注：每一種序列都是唯一的,因?yàn)槎际窃诖鎯Y(jié)構(gòu)上得到的。注：每一種序列都是唯一的,因?yàn)槎际窃诖鎯Y(jié)構(gòu)上得到的。0 1 2 3 4 5 60 1 2 3 4 5 60,2,3,4,5,1,60,2,3,4,5,1,60,2,3,5,1,6,40,2,3,5,1,6,4C.0,2,3,C.0,2,3,5,6,1,D.D.0,2,3,4,5,1,6第八章査找第八章査找一、選擇題1.順序査找方法適合于存儲結(jié)構(gòu)為（1.順序査找方法適合于存儲結(jié)構(gòu)為（）的線性表。散列存儲B.散列存儲B.索引存儲C.散列存儲或索引存儲C.散列存儲或索引存儲D.順序存儲或鏈接存儲2.在有序表｛1,3,8,13,33,42,46,63,76,78,86,97,100｝中，用折半查找值86時，經(jīng)（ ）次比較后查找成功。對二叉排序樹進(jìn)行（）遍歷，可以使遍歷所得到的序列是有序序列。A.按層次B.后序C.中序D.前序有一個長度為12的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下査找成功的平均比較次數(shù)為（ ）。+++++37/12B.39/12C.41/12D.35/12已知一個有序表為｛11,22,33,44,55,66,77,88,99｝,則順序査找元素55需要比較（）次。A.3 B.4 C.5 D.6順序查找法與折半查找法對存儲結(jié)構(gòu)的要求是（）。順序査找與折半査找均只適用于順序表順序查找與折半查找均既適用于順序表，也適用于鏈表順序查找只是適用于順序表折半查找適用于順序表有數(shù)據(jù)｛53,30,37,12,45,24,96）,從空二叉樹開始逐個插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，應(yīng)該選擇的序列是（ ）。A.45,24,53,12,37,96,30 B.37,24,12,30,53,45,9612,24,30,37,45,53,96 D.30,24,12,37,45,96,53采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（）＜.A.nn/2

A.n(n+l)/2對于一個線性表，若要求既能進(jìn)行較快地插入和刪除，又要求存儲結(jié)構(gòu)能夠反映數(shù)據(jù)元素之間的邏輯關(guān)系，則應(yīng)該()映數(shù)據(jù)元素之間的邏輯關(guān)系，則應(yīng)該()。+++++以順序存儲方式以鏈接存儲方式以順序存儲方式以鏈接存儲方式以索引存儲方式以散列存儲方式以索引存儲方式以散列存儲方式10.哈希函數(shù)有一個共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以(10.哈希函數(shù)有一個共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以()取其值域的每個值。A.最大概率A.最大概率最小概率平均概率同等概率平均概率同等概率11.在最壞情況下，折半查找與二叉排序樹查找性能比較，(A.完全相同B.A.完全相同C.二叉排序樹査找性能好C.二叉排序樹査找性能好D.不能確定12.設(shè)哈希表長m=14,哈希函數(shù)H(key)=keymod11。表中己有4個結(jié)點(diǎn):adcr(15)=4;addr(38)=5;addr(61)=6;addr(84)=7o如用線性探測處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是(A.8B.3C.5D.913.釆用折半査找方法査找長度為A.8B.3C.5D.913.釆用折半査找方法査找長度為n的線性表時,每個元素的平均査找長度為)。+++++++A.n2B.nlog2nC.nD.log2nA.n2B.nlog2nC.nD.log2n14.哈希表的平均查找長度(A.與處理沖突的方法有關(guān),與表的長度無關(guān)B.與處理沖突的方法無關(guān),與表的長度有關(guān)C.與處理沖突的方法有關(guān),A.與處理沖突的方法有關(guān),與表的長度無關(guān)B.與處理沖突的方法無關(guān),與表的長度有關(guān)C.與處理沖突的方法有關(guān),與表的長度有關(guān)D.與處理沖突的方法無關(guān),與表的長度無關(guān)15.一組記錄的關(guān)鍵字是{19,14,23,1,68,20,84,27,55,11,10,79},用鏈接地址法構(gòu)造)個記散列表，散列函數(shù)為H(key)=keymod13,散列地址為1的鏈中有(二、判斷題)個記A.1B.2C.3D.416.二叉排序樹的查找效率與二叉樹的()有關(guān)。A.高度A.1B.2C.3D.416.二叉排序樹的查找效率與二叉樹的()有關(guān)。A.高度B.結(jié)點(diǎn)個數(shù) C.樹形D.結(jié)點(diǎn)的位置1-在順序查找、折半查找、哈希表查找3種方法中，平均查找長度與結(jié)點(diǎn)個數(shù)n無關(guān)的査找方法是折半査找。（）在一個查找表中，能夠唯一地確定一個記錄的關(guān)鍵字稱為主關(guān)鍵字。（）順序査找是一種最簡單的査找方法。（）折半查找的前提條件是，查找表中記錄相應(yīng)的關(guān)鍵字值必須有序或者部分有序。（）二叉排序樹的建立過程上實(shí)際上是從空樹逐次插入的過程。（）理想情況下，哈希表查找等概率查找成功的時間復(fù)雜度是0（l）o（）按照一定規(guī)則，在二叉排序樹上插入、刪除結(jié)點(diǎn)，仍能保持二叉排序樹的性質(zhì)。（）分塊査找分為兩個步驟：第一步是要對索引表進(jìn)行査找；第二步是在塊中査找。這兩步查找都可以采用折半查找或者順序查找方法。（）一個好的哈希函數(shù)，應(yīng)該使哈希地址均勻地分布在整個哈希表的地址區(qū)間中，完全避免沖突的發(fā)生。（）在有序順序存儲的線性表中査找一個元素，用折半査找速度一定比順序査找快。（）二叉樹為二叉排序樹的充分必要條件是，任一個分支結(jié)點(diǎn)的值都大于其左孩子的值，小于右孩子的值。（）二叉排序樹在呈單支二叉樹時，查找效率最低。（）將10個元素散列到10000個單元的哈希表中，仍然可能會產(chǎn)生沖突。（）根據(jù)無序序列構(gòu)造二叉排序樹的過程，也是對無序序列排序的過程。（）折半査找方法運(yùn)用在升序序列比降序序列效率更高，所以降序序列最好先轉(zhuǎn)換為升序序列。（）第九章排序-、選擇題從未排序序列中依次取岀元素與已經(jīng)排好序的序列中的元素作比較。將其放入己排序序列的正確的位置上，此方法稱為（）。插入排序 B.交換排序C.選擇排序 D.歸并排序依次將每兩個相鄰的有序表合并成一個有序表的排序方法稱為（）。插入排序 B.交換排序C.選擇排序 D.歸并排序當(dāng)兩個元素岀現(xiàn)逆序的時候就交換位置，這種排序方法稱為（）。插入排序 B.交換排序C.選擇排序 D.歸并排序5.A.插入排序C.選擇排序在下列排序方法中,5.A.插入排序C.選擇排序在下列排序方法中,A.冒泡排序C.選擇排序交換排序D.歸并排序關(guān)鍵字比較的次數(shù)與記錄初始排列秩序無關(guān)的是（）o希爾排序D.插入排序在待排序元素基本有序的情況下，效率最高的排序方法是（）。A.插入排序 B.快速排序堆排序 D.歸并排序在下列幾種排序方法中，平均情況下占用內(nèi)存量最大的是（）方法。A.插入排序 B.選擇排序快速排序 D.歸并排序每次把待排序的區(qū)間劃分為左、右兩個子區(qū)間，其中左區(qū)間中記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄的關(guān)鍵字，右區(qū)間中記錄的關(guān)鍵字均大于等于基準(zhǔn)記錄的關(guān)鍵字，這種排序稱為（）。A.插入排序A.插入排序快速排序堆排序 D.歸并排序設(shè)已有m個元素有序，在未排好序的序列中挑選第m+1個元素，并且只經(jīng)過一次元素的交換就使第m+1個元素排序到位，該方法是（）。

A.折半插入排序 B.冒泡排序C.歸并排序 D.直接選擇排序?qū)哂衝個元素的任意序列采用插入排序法進(jìn)行排序，排序趟數(shù)為（）。n-1 B.nC.n+1 D.[Iog2n]對序列（49,38,65,97,76,13,47,50）采用直接插入排序法進(jìn)行排序,要把第七個元素47插入到己排序中，為尋找插入的合適位置需要進(jìn)行（）次元素間的比較。3 B.4D.6C.D.612.18個元素進(jìn)行冒泡法排序，通常需要進(jìn)行17趟冒泡，其中第10趟冒泡共需要進(jìn)行（）次元素間的比較。B.87B.8C.9D.10C.9經(jīng)過一趟冒泡排序后的序列為（）。13.已知10個數(shù)據(jù)元素為（54,28,16,34,73,62,93,60,26,43）,對該數(shù)列從小到大排序，經(jīng)過一趟冒泡排序后的序列為（）。16,28,34,28,16,34,16,28,34,16,28,34,28,16,34,16,28,34,28,16,34,54,73,62,54,62,73,54,62,60,54,62,60,60,26,43,9560,26,43,9573,26,43,9573,26,43,95經(jīng)過一次劃分后結(jié)果為（經(jīng)過一次劃分后結(jié)果為（14.一組記錄的關(guān)鍵字序列為（46,79,56,38,40,84）,利用快速排序，以第一個關(guān)鍵字為分割元素，A.18,20,36,59,26,2518,20,25,59,26,3626,18,59,20,36,2526,59,36,18,20,2517.—組記錄的關(guān)鍵字序列為（80,57,41,39,46,47）,利用堆排序（堆頂元素是最小元索）的方法建立的初始堆為（）。A.39,47,46,80,41,57B.41,39,46,47,57,80C.39,46,41,57,80,47D.39,80,46,47,41,5718.一組記錄的關(guān)鍵字序列為（46,79,56,38,40,84）,利用堆排序的方法建立的初始堆為（）。A.79,46,56,38,40,84B.84,79,56,38,40,46C.84,79,56,46,40,38D,84,56,79,40,46,38一組記錄的關(guān)鍵字序列為（25,48,16,35,79,82,23,40,36,72）,其中，含有5個長度為2的有序表，按歸并排序的方法對該序列進(jìn)行一趟歸并后的結(jié)果為（）。A.16,25,48,35,79,82,23,36,40,72B.16,25,35,48,23,40,79,82,36,72C,16,25,35,48,79,82,23,36,40,72D,16,25,35,48,79,23,36,40,82,72一組記錄的關(guān)鍵字序列為（60,47,80.57,39,41,46,30）,利用歸并排序的方法,對該序列進(jìn)行（1,1）歸并，即第一趟歸并后的結(jié)果為（）。A.47,57,60,80,30,39,41,46B.30,39,41,46,47,57,60,80C.30,47,80,57,39,41,46,60D,47,60,57,80,39,41,30,46二、判斷題n個元素進(jìn)行冒泡法排序，通常需要進(jìn)行n-1趟冒泡。（）對16個元素的序列用冒泡排法進(jìn)行排序，通常需要進(jìn)行15趟冒泡。（）n個元素進(jìn)行冒泡法排序，通常第j趟冒泡要進(jìn)行n-j次元素間的比較。（）18個元素進(jìn)行冒泡法排序，通常需要進(jìn)行17趟冒泡，其中第10趟冒泡共需要進(jìn)行8次元素間的比較。（）序列3,1,7,18,6,9,13,12經(jīng)一趟歸并排序的結(jié)果為1,3,7,18,6,9,13,12。（）待排序的序列為8,3,4,125,9,釆用直接選擇排序算法，當(dāng)進(jìn)行了兩趟選擇后,結(jié)果序列為128,3,4,5,9。（）序列15,13,16,14,19,17,采用冒泡排序算法（升序），經(jīng)一趟冒泡后，結(jié)果序列是13,15,14,16,17,19。（）在對10個記錄的序列（14,30,10,7,22,13,66,85,47,58）進(jìn)行直接插入排序時,當(dāng)把第6個記錄13插入到有序表時，為尋找插入位置，需比較3次。（）冒泡排序是一種比較簡單的插入排序方法。（）在歸并排序中，在第3趟歸并中，是把長度為4的有序表歸并為長度為8的有序表。（）三、綜合應(yīng)用選擇題空題（把合適的選項(xiàng)編號填寫在括號內(nèi)）1.（1） 一組記錄的關(guān)鍵字序列為（45,40,65,43,35,95）,利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一趟劃分的結(jié)果為（）。35,40,65,45,35,9535,40,65,43,45,9535,40,43,45,65,9535,40,45,43,65,95（2） 對上述序列利用直接插入排序，逐次插入過程中，共進(jìn)行了（）次元素間的比較。A.8 B.11C.9D.10（1）對關(guān)鍵字序列（36,69,46,28,30,74）采用快速排序，以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后的結(jié)果序列為（）。A.30,28,46,36,69,74B.28,30,36,46,69,74C.28,30,46,36,69,74D.30,28,36,46,69,74（2）用冒泡法對上述序列排序，經(jīng)過兩趟冒泡的結(jié)果序列為（）。A.36,28,30,46,69,74B.36,46,28,20,69,74C.38,36,30,46,69,74D.28,36,30,46,69,743.（1）一組記錄的關(guān)鍵字序列為（47,80,57,39,41,46）,利用堆排序的方法建立的初始堆為（）（堆頂元素是最小元素，釆用樹的形式建堆）。

39,41,57,80,47,4639,41,46,80,47,5739,41,57,80,47,4639,41,46,80,47,5739,47,46,80,41,57D.39,41,57,80,46,47（2）輸出堆頂元素后,調(diào)整后的堆為（）o41,47,46,80,57 B.41,57,46,80,47C.41,57,80,47,46 D.41,80,46,47,574.（1） 一組記錄的關(guān)鍵字序列為（42,37,62,40,32,92）,利用快速排序算法,以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（37,32,40,42,62,92 B.32,37,40,42,62,92C.32,37,40,62,42,92 D.42,37,40,62,32,92（2） 利用篩選過程把序列（42,82,67,102,16,32,57,52）建成初始堆（小根堆）為（A.42,16,67,52,82,32,57,102B.16,32,42,52,82,57,67,102C.16,42,32,52,82,67,57,102D.16,32,82,52,42,102,67,575.對關(guān)鍵字序列(56,51,71,54,46,106),利用快速排序，以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為()。46,51,56,54,71,106 B.56,51,54,46,71,106C.46,51,54,56,71,106 D.56,51,46,54,71,106一組記錄的關(guān)鍵字序列為(60,47,80,57,39,41,46,30),利用歸并排序的方法，經(jīng)過(2,2)歸并的結(jié)果序列為()。A.30,57,60,80,47,39,41,46B.47,,60,57,80,30,39,41,46C.41,57,60,80,30,39,47,46D.47,57,60,80,30,39,41,46四、程序選擇題空題(從答案選項(xiàng)中選擇合適的內(nèi)容，完成程序中的空格)以下直接插入排序算法對存放在…,a[n-l]中，長度為n的記錄序列按關(guān)鍵字key由小到大排序。voiddisort(NODEa[],intn)（inti,j;NODEtemp;for(i=l;i<n;i++)(temp=a[i];while((1) &&temp.key<a[j].key)TOC\o"1-5"\h\z(a【i+ll=(2) ；;a[j+l]=⑷ ；}}【答案選項(xiàng)】AJ--j>=0tempa[j]以下程序是折半插入排序的算法設(shè)待排序的記錄序列存放在a[lL?.a[n]中，以a[0]作為輔助工作單元，程序是要把a(bǔ)[i]插入到己經(jīng)有序的序列a[lL...a[i-l]中。voidbinsort(NODEa[],intn)(intx,ij,s,k,m;for(i=2；i<=(1) ;i++){a[O]=a[i];x=a[i].key;s=l；j=i-l；while(s<=j)TOC\o"1-5"\h\z{m=(2) ;iffx<a[m].key);else;}for(k=i-l;k>=j+l;k--)=afkl:a[j+l]=a[0];}}【答案選項(xiàng)】(s+j)/2j=m-la[k+l]ns=m+l3.以下冒泡法程序?qū)Υ娣旁赼[lj,a[2],……，a[n]中的序列進(jìn)行排序，其中n是元素個數(shù)，要求按升序排列。voidbsort(NODEa[],intn)(NODEtemp;intijflag;for(j=l; (1) j++){flag=0;for(i=l;⑵ ;i++)if(a[i].key>a[i+1].key){flag=l;temp=a[i];(31；；}if(flag==0)break;})程序中flag的功能是 。【答案選項(xiàng)】a[i]=a[i+l]j<=n-la[i+l]=temp當(dāng)某趟冒泡中沒有出現(xiàn)交換則己排好序結(jié)束循環(huán)i<=n-j4.以下函數(shù)為直接選擇排序算法，對a[l],a[2L-a[n]中的記錄進(jìn)行直接選擇排序。typedefstruct(intkey; }NODE;voidselsort(NODEa[],intn)inti,j,k;NODEtemp;for(i=l;i<= (1) ;i++)(k=i；for(j=i+l；j<=_[2] ;j++)if(aU].key<a[k].key)J3) ,iffi!=k){temp=a[i];TOC\o"1-5"\h\z ; ;【答案選項(xiàng)】na[i]=a[k]k=ja[k]=tempn-1以下程序是快速排序的算法設(shè)待排序的記錄序列存放在a[start],...a[end]中，按記錄的關(guān)鍵字進(jìn)行快速排序，先進(jìn)行一次劃分，再分別進(jìn)行遞歸調(diào)用。voidquicksort(NODEa[],intstart,intend){inti,j;NODEmid;if(start>=end)return;i=start;j=end;mid=a[i];while(i<j)(while(i<j&&a[j].key>mid.key)j--；if(ivj){a[i]=aU];TOC\o"1-5"\h\z ill ；}whilefkj&&a[i].key<=mid.key)⑵ ；if(i<j){ (3) ;⑷ ；a[i]=mid;quicksort(a,stat,i-1);quicksort (5) 【答案選項(xiàng)】a[j]=a[i](a,i+l,end)i++j-數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題2020秋季(參考答案)第二章緒論一、 選擇題1、 B.物理結(jié)構(gòu)2、 D.數(shù)據(jù)項(xiàng)可由若干個數(shù)據(jù)元素構(gòu)成3、 A.數(shù)據(jù)元素4、 D.邏輯結(jié)構(gòu)5、 C.可讀性6、 B.算法本身7、 B.O(log2n)8、 B.O(log2n)10、 C.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)11、 B.n2/212、 A.數(shù)據(jù)元素間的關(guān)系的表示13、 B.多對多14、 A.與存儲該邏輯結(jié)構(gòu)的計(jì)算機(jī)相關(guān)15、 B.數(shù)據(jù)元素的存儲二、 判斷題TOC\o"1-5"\h\zX/X/XX/XXTOC\o"1-5"\h\zXXXXXX三、程序題1、 答案：O(log2n)2、 答案：O(log2n)3、 答案：O(n!)4、 答案：O(n)第二章線性表一、 選擇題1、 C.n-i+12、 C.n-i3、 B.p->next=q->next4、 C.s->next=p->next;p->next=s;5、 A.p->next==head6、 B.可隨機(jī)訪問任一元素7、 A.head->next==head8、 C.209、 D.除了一個和最后一個元素外，其余元素都有一個且僅有一個直接訂驅(qū)和一個直接后繼10、 A.63.511、 A.10612、 A.q->next=p13、 D.邏輯上相鄰的元素在物理位置上也相鄰14、 A.不能隨機(jī)訪問任一結(jié)點(diǎn)15、 A.n-i+116、 A.HL=p;p->next=HL;17、 D.q->next=s；s->next=p；18B.p->right=s；p->right->left=s；s->left=p：s->right=p->right；19、 B.只有1個元素；20、 B.HL->next==NULL21、 D.p->next=he