國(guó)家開(kāi)放大學(xué)數(shù)據(jù)結(jié)構(gòu)（本）

PAGE練習(xí)一單選題1.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（）。DA.存儲(chǔ)結(jié)構(gòu)B.物理和存儲(chǔ)結(jié)構(gòu)C.物理結(jié)構(gòu)D.邏輯結(jié)構(gòu)2．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）。DA.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)D.線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)3．設(shè)有一個(gè)長(zhǎng)度為n的順序表，要?jiǎng)h除第i個(gè)元素,則需移動(dòng)元素的個(gè)數(shù)為（）。CA.iB.n-i-1C.n-iD.n-i+14．設(shè)頭指針為head的非空的單向鏈表，指針p指向尾結(jié)點(diǎn),則通過(guò)以下操作（)可使其成為單向循環(huán)鏈表。DA.head=p;B.p=head;C.p->next=NULL;D.p->next=head;5．一個(gè)棧的進(jìn)棧序列是10，20，30，40，50，則棧的不可能輸出序列是（）（進(jìn)棧出棧可以交替進(jìn)行）。BA．10,20,30,40,50B．40,30,50,10,20C．40,50,30,20,10D．50,40,30,20,106．在一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（）。DA．x=top;top=top->next;B．x=top->data;C．top=top->next;x=top->data;D．x=top->data;top=top->next;7．判斷一個(gè)順序隊(duì)列sq（最多元素為m）為空的條件是（）。CA．sq->rear-sq->front==mB．sq->rear-sq->front-1==mC．sq->front==sq->rearD．sq->front==sq->rear+18．串函數(shù)Strcat（a,b）的功能是進(jìn)行串（）。DA．比較B．復(fù)制C．賦值D．連接9．稀疏矩陣采用壓縮存儲(chǔ)的目的主要是（）。DA．表達(dá)變得簡(jiǎn)單B．對(duì)矩陣元素的存取變得簡(jiǎn)單C．去掉矩陣中的多余元素D．減少不必要的存儲(chǔ)空間的開(kāi)銷(xiāo)10.深度為5的二叉樹(shù)至多有（）個(gè)結(jié)點(diǎn)。CA.16B.32C.31D.1011.如圖所示二叉樹(shù)的中序遍歷序列是（）。BA.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh12.一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖包含（）條邊。CA．n（n-1）B．n（n+1）C．n（n-1）/2D．n（n+1）/213.圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的（）遍歷。AA．先序B．中序C．后序D．層次14.在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找值86時(shí)，經(jīng)（）次比較后查找成功。BA．3B．4C．6D．815.依次將每?jī)蓚€(gè)相鄰的有序表合并成一個(gè)有序表的排序方法稱(chēng)為（）。DA.插入排序B.交換排序C.選擇排序D.歸并排序16.下面程序段的時(shí)間復(fù)雜度是（）。Dfor(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}A.O(1)B.O(log2n)C.O(n)D.O(n3)17．在一個(gè)單鏈表中p指向結(jié)點(diǎn)a,q指向結(jié)點(diǎn)a的直接后繼結(jié)點(diǎn)b，要?jiǎng)h除結(jié)點(diǎn)b，可執(zhí)行（）。AA．p->next=q->next;B．p=q->next;C．p->next=q;D．p->next=q;18．設(shè)有一個(gè)長(zhǎng)度為n的順序表，要在第i個(gè)元素之前（也就是插入元素作為新表的第i個(gè)元素），插入一個(gè)元素，則移動(dòng)元素個(gè)數(shù)為（）。CA.n-iB.n-i-1C.n-i+1D.i19．一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4。則隊(duì)列的輸出序列是（）。BA．4，3，2，1B．1，2，3，4C．1，4，3，2D．3，2，4，120．在一個(gè)棧頂指針為top的鏈棧中，將一個(gè)p指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行（）。CA．top->next=p;B．p->next=top->next;top->next=p;C．p->next=top;top=p;D．p->next=top->next;top=top->next;21．判斷一個(gè)循環(huán)隊(duì)列Q（最多元素為m）為滿(mǎn)的條件是（）。CA．Q->front==Q->rearB．Q->front!=Q->rearC．Q->front==(Q->rear+1)%mD．Q->front!=(Q->rear+1)%m22．設(shè)有兩個(gè)串p和q，其中q是p的子串，q在p中首次出現(xiàn)的位置的算法稱(chēng)為（）。CA．求子串B．連接C．模式匹配D．求串長(zhǎng)23．一個(gè)非空廣義表的表頭（）。DA．不可能是原子B．只能是子表C．只能是原子D．可以是子表或原子24.樹(shù)中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（）。DA.1B.0C.2D.-125.在一棵二叉樹(shù)上，第5層的結(jié)點(diǎn)數(shù)最多為（）。CA．8B．15C．16D．3226.在一個(gè)圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的（）倍。CA．1/2B．1C．2D．427.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則所有頂點(diǎn)鄰接表中的結(jié)點(diǎn)總數(shù)為（）。DA．nB．eC．2nD．2e28.有一個(gè)長(zhǎng)度為12的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。AA．37/12B．39/12C．41/12D．35/1229.從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱(chēng)為（）。AA.插入排序B.交換排序C.選擇排序D.歸并排序30．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（）。DA.數(shù)據(jù)處理的方法B.相關(guān)算法C.數(shù)據(jù)元素的類(lèi)型D.數(shù)據(jù)元素間的關(guān)系的表示31．在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（）。DA．p->next=s;s->next=p->next;B．p->next=s->next;C．p=s->next;D．s->next=p->next;p->next=s;32．在一個(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ǔ)句（）。CA．p=q->next;B．p->next=q;C．p->next=q->next;D．q->next=NULL;33．表達(dá)式a*(b+c)-d的后綴表達(dá)式是（）。BA．a(chǎn)bcd*+-B．a(chǎn)bc+*d-C．a(chǎn)bc*++d-D．-+*abcd34．判斷順序棧s滿(mǎn)（元素個(gè)數(shù)最多n個(gè)）的條件是（）。CA．s->top==0B．s->top!=0C．s->top==n-1D．s->top!=n-135．串的長(zhǎng)度是指（）。BA．串中所含不同字母的個(gè)數(shù)B．串中所含字符的個(gè)數(shù)C．串中所含不同字符的個(gè)數(shù)D．串中所含非空格字符的個(gè)數(shù)36．廣義表(a,(d,a,b),h,(e,((i,j),k)))深度是()。DA．6B．10C．8D．437.在一棵二叉樹(shù)中，若編號(hào)為8的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（）。DA．18B．16C．15D．1738.對(duì)于一個(gè)線(xiàn)性表，若要求既能進(jìn)行較快地插入和刪除，又要求存儲(chǔ)結(jié)構(gòu)能夠反映數(shù)據(jù)元素之間的邏輯關(guān)系，則應(yīng)該（）。BA．以順序存儲(chǔ)方式B．以鏈接存儲(chǔ)方式C．以索引存儲(chǔ)方式D．以散列存儲(chǔ)方式39.從未排序序列中挑選元素，并將其放入已排序序列的一端，此方法稱(chēng)為（）。CA.插入排序B.交換排序C.選擇排序D.歸并排序40.每個(gè)存儲(chǔ)結(jié)點(diǎn)只存儲(chǔ)一個(gè)數(shù)據(jù)元素，各結(jié)點(diǎn)存儲(chǔ)在連續(xù)的存儲(chǔ)空間，該存儲(chǔ)方式是（）存儲(chǔ)方式。AA．順序B．鏈接C．索引D．散列41．元素4，6，8，10按順序依次進(jìn)棧，按該棧的可能輸出序列依次入隊(duì)列，該隊(duì)列的可能輸出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）。DA．10，8，4，6B．10，6，4，8C．8，4，6，10D．10，8，6，442．如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退棧操作時(shí)（）。CA．必須判斷棧是否滿(mǎn)B．判斷棧元素類(lèi)型C．必須判斷棧是否空D．對(duì)棧不作任何判斷43．串與普通的線(xiàn)性表相比較，它的特殊性體現(xiàn)在（）。CA．順序的存儲(chǔ)結(jié)構(gòu)B．鏈接的存儲(chǔ)結(jié)構(gòu)C．?dāng)?shù)據(jù)元素是一個(gè)字符D．?dāng)?shù)據(jù)元素可以任意44．設(shè)有一個(gè)廣義表A(a)，其表尾為（）。CA．a(chǎn)B．(())C．（）D．(a)45.權(quán)值為{1，2，6，8}的四個(gè)結(jié)點(diǎn)構(gòu)成的哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度是（）。DA．18B．28C．19D．2946.一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖包含（）條邊。AA．n（n-1）B．n（n+1）47．n（n-1）/2D．n（n+1）/247.采用順序查找方法查找長(zhǎng)度為n的線(xiàn)性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為（）。CA．nB．n/2C．(n+1)/2D．(n-1)/248.當(dāng)兩個(gè)元素出現(xiàn)逆序的時(shí)候就交換位置，這種排序方法稱(chēng)為（）。BA.插入排序B.交換排序C.選擇排序D.歸并排序49．下列說(shuō)法中，不正確的是（）。DA．?dāng)?shù)據(jù)元素是數(shù)據(jù)的基本單位B．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)識(shí)單位C．?dāng)?shù)據(jù)可有若干個(gè)數(shù)據(jù)元素構(gòu)成D．?dāng)?shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成50.每個(gè)存儲(chǔ)結(jié)點(diǎn)不僅含有一個(gè)數(shù)據(jù)元素，還包含一組指針，該存儲(chǔ)方式是（）存儲(chǔ)方式。BA．順序B．鏈接C．索引D．散列51．向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)（）。AA．先移動(dòng)棧頂指針，再存入元素B．先存入元素，再移動(dòng)棧頂指針C．先后次序無(wú)關(guān)緊要D．同時(shí)進(jìn)行52．一般情況下，將遞歸算法轉(zhuǎn)換成等價(jià)的非遞歸算法應(yīng)該設(shè)置（）。AA．棧B．隊(duì)列C．堆?；蜿?duì)列D．?dāng)?shù)組53．空串與空格串（）。BA．相同B．不相同C．可能相同D．無(wú)法確定54．廣義表(f,h,(a,b,d,c),d,e,((i,j),k))的長(zhǎng)度是()。AA．6B．10C．8D．455.二叉樹(shù)第k層上最多有（）個(gè)結(jié)點(diǎn)。BA．2kB．2k-1C．2k-1D．2k-156.對(duì)于具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則該矩陣的大小為（）。BA．nB．n2C．n-1D．(n-1)257.采用折半查找方法查找長(zhǎng)度為n的線(xiàn)性表時(shí)，其算法的時(shí)間復(fù)雜度為（）。DA．O(n2)B．O(nlog2n)C．O(n)D．O(log2n)

數(shù)據(jù)結(jié)構(gòu)（本）試題一、單項(xiàng)選擇題（把合適的選項(xiàng)編號(hào)填寫(xiě)在括號(hào)內(nèi)。每小題3分，共45分）1.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（D）。A.存儲(chǔ)結(jié)構(gòu)B.物理和存儲(chǔ)結(jié)構(gòu)C.物理結(jié)構(gòu)D.邏輯結(jié)構(gòu)2．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（D）。A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)D.線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)3．設(shè)有一個(gè)長(zhǎng)度為n的順序表，要?jiǎng)h除第i個(gè)元素,則需移動(dòng)元素的個(gè)數(shù)為（C）。A.i B.n-i-1C.n-i D.n-i+14．設(shè)頭指針為head的非空的單向鏈表，指針p指向尾結(jié)點(diǎn),則通過(guò)以下操作（D)可使其成為單向循環(huán)鏈表。A.head=p;B.p=head;C.p->next=NULL;D.p->next=head;5．一個(gè)棧的進(jìn)棧序列是10，20，30，40，50，則棧的不可能輸出序列是（B）（進(jìn)棧出棧可以交替進(jìn)行）。A．10,20,30,40,50B．40,30,50,10,20C．40,50,30,20,10D．50,40,30,20,106．在一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（D）。A．x=top;top=top->next;B．x=top->data;C．top=top->next;x=top->data;D．x=top->data;top=top->next;7．判斷一個(gè)順序隊(duì)列sq（最多元素為m）為空的條件是（C）。A．sq->rear-sq->front==mB．sq->rear-sq->front-1==mC．sq->front==sq->rearD．sq->front==sq->rear+18．串函數(shù)Strcat（a,b）的功能是進(jìn)行串（D）。A．比較B．復(fù)制C．賦值D．連接9．稀疏矩陣采用壓縮存儲(chǔ)的目的主要是（D）。A．表達(dá)變得簡(jiǎn)單B．對(duì)矩陣元素的存取變得簡(jiǎn)單C．去掉矩陣中的多余元素D．減少不必要的存儲(chǔ)空間的開(kāi)銷(xiāo)10.深度為5的二叉樹(shù)至多有（C）個(gè)結(jié)點(diǎn)。A.16B.32C.31D.1011.如圖所示二叉樹(shù)的中序遍歷序列是（B）。A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh12.一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖包含（C）條邊。A．n（n-1）B．n（n+1）C．n（n-1）/2D．n（n+1）/213.圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的（A）遍歷。A．先序B．中序C．后序D．層次14.在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找值86時(shí)，經(jīng)（B）次比較后查找成功。A．3B．4C．6D．815.依次將每?jī)蓚€(gè)相鄰的有序表合并成一個(gè)有序表的排序方法稱(chēng)為（D）。A.插入排序 B.交換排序C.選擇排序 D.歸并排序二、判斷題（根據(jù)敘述正確與否在其后面的括號(hào)內(nèi)打?qū)μ?hào)“√”或打叉號(hào)“×”。每小題2分，共30分）1.數(shù)據(jù)元素可以有一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成。(√)2．?dāng)?shù)據(jù)結(jié)構(gòu)中,元素之間存在多對(duì)多的關(guān)系稱(chēng)為樹(shù)狀結(jié)構(gòu)。(×)3．設(shè)有一個(gè)不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，指針p指向尾結(jié)點(diǎn)，現(xiàn)要使p指向第一個(gè)結(jié)點(diǎn)，可用語(yǔ)句p=p->next;。(√)4．要在一個(gè)單向鏈表中p所指向的結(jié)點(diǎn)之后插入一個(gè)s所指向的新結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，可執(zhí)行p->next=s;s->next=p->next；的操作。(×)5.鏈?zhǔn)綏Ｅc順序棧相比，一個(gè)明顯的優(yōu)點(diǎn)是通常不會(huì)出現(xiàn)棧滿(mǎn)的情況。(√)6.在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中,隊(duì)頭指針指向隊(duì)頭元素的后一個(gè)位置。(×)7.一個(gè)遞歸算法不必包括遞歸終止條件。(×)8．空串的長(zhǎng)度是1。(×)9.一個(gè)廣義表((a),((b),c),(((d))))的長(zhǎng)度為3，深度為4。(√)10．如果結(jié)點(diǎn)A有3個(gè)兄弟，而且B是A的雙親，則B的度是4。(√)11.哈夫曼樹(shù)只存在著雙支結(jié)點(diǎn)，不存在單支結(jié)點(diǎn)。(√)12.無(wú)向圖的鄰接矩陣一定是對(duì)稱(chēng)的。（√）13.AOV網(wǎng)拓?fù)渑判虻慕Y(jié)果是惟一的。（×）14.折半查找的前提條件是，查找表中記錄相應(yīng)的關(guān)鍵字值必須有序或者部分有序。(×)15.對(duì)16個(gè)元素的序列用冒泡排法進(jìn)行排序，通常需要進(jìn)行15趟冒泡。(√)三、綜合應(yīng)用及程序設(shè)計(jì)題（每小題5分，共25分）1．設(shè)有一個(gè)不帶頭結(jié)點(diǎn)的單向鏈表，頭指針為head，p、prep是指向結(jié)點(diǎn)類(lèi)型的指針，該鏈表在輸入信息時(shí)不慎把相鄰兩個(gè)結(jié)點(diǎn)的信息重復(fù)輸入，以下程序段是在該單向鏈表中查找這相鄰兩個(gè)結(jié)點(diǎn)，把該結(jié)點(diǎn)的數(shù)據(jù)域data打印出來(lái)，并把其中之一從鏈表中刪除，填寫(xiě)程序中的空格。（A）prep=head;p=prep->next;while(p->data!=prep->data){prep=p;____①____;}printf(“%d”,p->data);prep->next=____②____;A.①p=p->next②p->nextB.①prep->data②p->nextC.①p->next②p=p->nextD.①p->next②p->data2．設(shè)SeqStack為順序棧，寫(xiě)出下列程序段執(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(S));執(zhí)行后的輸出結(jié)果為：__________A________。1512851333581213151513128531512133853．以下程序段執(zhí)行后，c的值為（A）。char*a[5]={“12378”,”1237”,”1236789”,”1237”,”123708”}inti,c=0for(i=0;i<5;i++)if(strcmp(a[i],”1237”)==0)c++;A.2B.5C.0D.12374．以1，2，3，6，7，8作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(shù)是如下哪個(gè)圖？（B）379273792717103612866727151233128771236612631982793938271512123675．以下直接插入排序算法對(duì)存放在a[0],a[1],···,a[n-1]中，長(zhǎng)度為n的記錄序列按關(guān)鍵字key由小到大排序，完成程序中空格部分。(C)voiddisort(NODEa[],intn){inti,j;NODEtemp;for(i=1;i<n;i++){temp=a[i];j=i-1;while(j>=0&&temp.key<a[j].key){a[j+1]=a[j];_______;}a[j+1]=temp;}}A.j++B.i++C.j--D.i--

數(shù)據(jù)結(jié)構(gòu)（本）試題一、單項(xiàng)選擇題（把合適的選項(xiàng)編號(hào)填寫(xiě)在括號(hào)內(nèi)。每小題3分，共45分）1．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（D）。A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)D.線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)2.下面程序段的時(shí)間復(fù)雜度是（D）。for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}O(1)B.O(log2n)C.O(n)D.O(n3)3．在一個(gè)單鏈表中p指向結(jié)點(diǎn)a,q指向結(jié)點(diǎn)a的直接后繼結(jié)點(diǎn)b，要?jiǎng)h除結(jié)點(diǎn)b，可執(zhí)行（A）。A．p->next=q->next;B．p=q->next;C．p->next=q;D．p->next=q;4．設(shè)有一個(gè)長(zhǎng)度為n的順序表，要在第i個(gè)元素之前（也就是插入元素作為新表的第i個(gè)元素），插入一個(gè)元素，則移動(dòng)元素個(gè)數(shù)為（C）。A.n-iB.n-i-1C.n-i+1D.i5．一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4。則隊(duì)列的輸出序列是（B）。A．4，3，2，1B．1，2，3，4C．1，4，3，2D．3，2，4，16．在一個(gè)棧頂指針為top的鏈棧中，將一個(gè)p指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行（C）。A．top->next=p;B．p->next=top->next;top->next=p;C．p->next=top;top=p;D．p->next=top->next;top=top->next;7．判斷一個(gè)循環(huán)隊(duì)列Q（最多元素為m）為滿(mǎn)的條件是（C）。A．Q->front==Q->rearB．Q->front!=Q->rearC．Q->front==(Q->rear+1)%mD．Q->front!=(Q->rear+1)%m8．設(shè)有兩個(gè)串p和q，其中q是p的子串，q在p中首次出現(xiàn)的位置的算法稱(chēng)為（C）。A．求子串B．連接C．模式匹配D．求串長(zhǎng)9．一個(gè)非空廣義表的表頭（D）。A．不可能是原子B．只能是子表C．只能是原子D．可以是子表或原子10.樹(shù)中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（D）。A.1B.0C.2D.-111.在一棵二叉樹(shù)上，第5層的結(jié)點(diǎn)數(shù)最多為（C）。A．8B．15C．16D．3212.在一個(gè)圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的（C）倍。A．1/2B．1C．2D．413.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則所有頂點(diǎn)鄰接表中的結(jié)點(diǎn)總數(shù)為（D）。A．nB．eC．2nD．2e14.有一個(gè)長(zhǎng)度為12的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（A）。A．37/12B．39/12C．41/12D．35/1215.從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱(chēng)為（A）。A.插入排序 B.交換排序C.選擇排序 D.歸并排序二、判斷題（根據(jù)敘述正確與否在其后面的括號(hào)內(nèi)打?qū)μ?hào)“√”或打叉號(hào)“×”。每小題2分，共30分）1.數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶(hù)根據(jù)應(yīng)用需要建立的。（√）2．?dāng)?shù)據(jù)結(jié)構(gòu)中,元素之間存在多對(duì)多的關(guān)系稱(chēng)為圖狀結(jié)構(gòu)。(√)3．設(shè)有一個(gè)單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，p指向尾結(jié)點(diǎn)，為了使該單向鏈表改為單向循環(huán)鏈表，可用語(yǔ)句p->next=head。(√)4．設(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)。(√)5.棧和隊(duì)列都是特殊的線(xiàn)性表,但它們對(duì)存取位置的限制不同。(√)6.棧是限定在表的兩端進(jìn)行插入和刪除操作的線(xiàn)性表，又稱(chēng)為先進(jìn)先出表。(×)7.遞歸定義的數(shù)據(jù)結(jié)構(gòu)通常用遞歸算法來(lái)實(shí)現(xiàn)對(duì)它的操作。(√)8．一個(gè)空格的串的長(zhǎng)度是0。(×)9.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的行號(hào)、列號(hào)和元素值三項(xiàng)信息。(√)10．深度為k的完全二叉樹(shù)至少有2k-1個(gè)結(jié)點(diǎn)。（×）11.完全二叉樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)。（×）12.圖的生成樹(shù)是惟一的。（×）13.對(duì)連通圖進(jìn)行深度優(yōu)先遍歷可以訪(fǎng)問(wèn)到該圖中的所有頂點(diǎn)。（√）14.在順序查找、折半查找、哈希表查找3種方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是折半查找。(×)15.n個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行n-1趟冒泡。(√)三、綜合應(yīng)用及程序設(shè)計(jì)題（每小題5分，共25分）1．在下面空格處填寫(xiě)一條語(yǔ)句，以使下面的鏈?zhǔn)疥?duì)列全部元素出隊(duì)的算法完整。(C)intwrite(LinkQueue*q){QueueNode*p;if(q->front==q->rear)/*隊(duì)空*/{printf(“隊(duì)空！無(wú)元素可取”);exit(0);}while(q->front->next!=NULL){p=q->front->next;q->front->next=p->next;/*出隊(duì)*/printf(“%4d”,p->data);free(p);/*釋放已出隊(duì)結(jié)點(diǎn)*/}_____________/*隊(duì)空時(shí)，頭尾指針指向頭結(jié)點(diǎn)*/}q->front=q->rear;q=q->next;q->rear=q->front;D.p=p->next;2．以下程序是先序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分（樹(shù)結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。(C)voidPreorder(structBTreeNode*BT){if(BT!=NULL){_________________;Preorder(BT-->left);Preorder(BT-->right);}}A.printf(“%c”,BT->left)B.printf(“%c”,BT->right)C.printf(“%c”,BT->data)D.printf(“%d”,BT->data)3．9684968457969654789784569784569684754．設(shè)關(guān)鍵字序列為：（36，69，46，28，30，74）（1）將此序列用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一趟劃分的結(jié)果為（D）。（本小題3分）A.30，28，46，36，69，74

B.28，30，36，46，69，74C.28，30，46，36，69，74

D.

30，28，36，46，69，74（2）用冒泡法對(duì)上述序列排序，經(jīng)過(guò)兩趟冒泡的結(jié)果序列為（A）。（本小題2分）

A.36，28，30，46，69，74

B.36，46，28，20，69，74

C.38，36，30，46，69，74

D.28，36，30，46，69，745．設(shè)數(shù)據(jù)序列為：{53,30,37,12,45,24,96}（1）從空二叉樹(shù)開(kāi)始逐個(gè)插入該數(shù)據(jù)序列來(lái)形成二叉排序樹(shù)，若希望高度最小，應(yīng)該選擇的序列是（B）。（本小題3分）A．45,24,53,12,37,96,30B．37,24,12,30,53,45,96C．12,24,30,37,45,53,96D．30,24,12,37,45,96,53（2）用鏈接地址法將該數(shù)據(jù)序列構(gòu)造哈希表，哈希函數(shù)為H(key)=keymod13，則散列地址為1的鏈中有（B）個(gè)記錄。（本小題2分）A.0 B.1 C.2 D.3

練習(xí)三綜合應(yīng)用及程序設(shè)計(jì)題1．設(shè)有一個(gè)不帶頭結(jié)點(diǎn)的單向鏈表，頭指針為head，p、prep是指向結(jié)點(diǎn)類(lèi)型的指針，該鏈表在輸入信息時(shí)不慎把相鄰兩個(gè)結(jié)點(diǎn)的信息重復(fù)輸入，以下程序段是在該單向鏈表中查找這相鄰兩個(gè)結(jié)點(diǎn)，把該結(jié)點(diǎn)的數(shù)據(jù)域data打印出來(lái)，并把其中之一從鏈表中刪除，填寫(xiě)程序中的空格。prep=head;p=prep->next;while(p->data!=prep->data){prep=p;____①____;}printf(“%d”,p->data);prep->next=____②____;A.①p=p->next②p->nextB.①prep->data②p->nextC.①p->next②p=p->nextD.①p->next②p->dataA2.在下面空格處填寫(xiě)一條語(yǔ)句，以使下面的進(jìn)棧算法完整。voidPush(structSeqStack*s,ElemTypex){if(s->top==MaxSize-1){printf(“棧滿(mǎn)溢出錯(cuò)誤！\n”);exit(1);}________s->data[s->top]=x;}s->top=s->data;B.s->data++;C.s->top++;D.s->data=s->top;C3．設(shè)有一個(gè)頭指針為head的不帶頭結(jié)點(diǎn)單向鏈表中（結(jié)點(diǎn)類(lèi)型為NODE），p為指向該鏈表中某個(gè)結(jié)點(diǎn)的指針。以下程序段為插入一個(gè)指針為s的結(jié)點(diǎn)，使它成為p結(jié)點(diǎn)的直接前驅(qū)，請(qǐng)選擇其中空格的選項(xiàng)。NODE*q;q=head;while(q->next!=p)____①____;s->next=p;____②____;①A.p=p->next B.q=q->nextC.s=s->nextD.head=head->nextB②A.p->next=qB.p->next=sC.q->next=sD.q->next=pC4.設(shè)線(xiàn)性表以不帶頭結(jié)點(diǎn)的單向鏈表存儲(chǔ)，鏈表頭指針為head。以下程序的功能是輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)域data，完成程序中空格部分。#defineNULL0voidmain(){NODE*head,*p;p=head;/*p為工作指針*/do{printf(“%d\n”,p->data);____①____;}while(____②____);}①A.head=p->next B.p=head->nextC.p=p->nextD.head=head->nextC②A.p==NULLB.p!=NULLC.p!=headD.p==headB5.寫(xiě)出下列程序執(zhí)行后的結(jié)果SeqQueueQ;InitQueue(Q);inta[4]={5,8,12,15};for(inti=0;i<4;i++)InQueue(Q,a[i]);InQueue(Q,OutQueue(Q));InQueue(Q,30);InQueue(Q,OutQueue(Q)+10);while(!QueueEmpty(Q))printf(“%d”,OutQueue(Q));執(zhí)行后的輸出結(jié)果為：__________________。58121530121553018812153018121551830B6．設(shè)SeqStack為順序棧，寫(xiě)出下列程序段執(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(S));執(zhí)行后的輸出結(jié)果為：__________________。151285133358121315151312853151213385A7．以下程序段執(zhí)行后，c的值為（）。char*a[5]={“12378”,”1237”,”1236789”,”1237”,”123708”}inti,c=0for(i=0;i<5;i++)if(strcmp(a[i],”1237”)==0)c++;A.2B.5C.0D.1237A8．以下程序是先序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分（樹(shù)結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。voidPreorder(structBTreeNode*BT){if(BT!=NULL){_________________;Preorder(BT-->left);Preorder(BT-->right);}}A.printf(“%c”,BT->left)B.printf(“%c”,BT->right)C.printf(“%c”,BT->data)D.printf(“%d”,BT->data)C9.設(shè)某二叉樹(shù)先序遍歷為abdec，中序遍歷為dbeac（1）該二叉樹(shù)的圖形是（）。BdeabdeabcabcdeababdceabcdeC.D.（2）寫(xiě)出該二叉樹(shù)后序遍歷的結(jié)果（）。BA.edbcaB.debcaC.ebdcaD.bceda10．已知某帶權(quán)圖的鄰接矩陣如下所示：從頂點(diǎn)1出發(fā)的廣度優(yōu)先搜索序列為（）。AA.1，2，3，4，5，6B.1，4，3，2，6，5C.1，3，2，4，6，5D.1，2，4，3，5，611．以1，2，3，6，7，8作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(shù)是如下哪個(gè)圖？（）B3792737927171036128667271512331287712366126319827939382715121236712．以下直接插入排序算法對(duì)存放在a[0],a[1],···,a[n-1]中，長(zhǎng)度為n的記錄序列按關(guān)鍵字key由小到大排序，完成程序中空格部分。voiddisort(NODEa[],intn){inti,j;NODEtemp;for(i=1;i<n;i++){temp=a[i];j=i-1;while(j>=0&&temp.key<a[j].key){a[j+1]=a[j];_______;}a[j+1]=temp;}}A.j++