國(guó)家開(kāi)放大學(xué)《數(shù)據(jù)結(jié)構(gòu)（本）》期末復(fù)習(xí)題參考答案

國(guó)家開(kāi)放大學(xué)《數(shù)據(jù)結(jié)構(gòu)（本）》期末復(fù)習(xí)題參考答案一、單選題1.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（）。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)分為（）。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.線性結(jié)構(gòu)和非線性結(jié)構(gòu)3.線性結(jié)構(gòu)中數(shù)據(jù)元素之間的關(guān)系是（）A.一對(duì)一B.一對(duì)多C.多對(duì)一D.多對(duì)多4.樹形結(jié)構(gòu)中數(shù)據(jù)元素之間的關(guān)系是（）A.一對(duì)一B.一對(duì)多C.多對(duì)一D.多對(duì)多5.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（）。A.數(shù)據(jù)處理的方法B.相關(guān)算法C.數(shù)據(jù)元素的類型D.數(shù)據(jù)元素間的關(guān)系的表示6.每個(gè)存儲(chǔ)結(jié)點(diǎn)只存儲(chǔ)一個(gè)數(shù)據(jù)元素，各結(jié)點(diǎn)存儲(chǔ)在連續(xù)的存儲(chǔ)空間，該存儲(chǔ)方式是（）存儲(chǔ)方式。A.順序B.鏈接C.索引D.散列7.線性表中（）稱為線性表的長(zhǎng)度。A.數(shù)據(jù)最大值B.數(shù)據(jù)最小值C.數(shù)據(jù)元素個(gè)數(shù)D.表的行數(shù)8.設(shè)有一個(gè)長(zhǎng)度為n的順序表，要在第i個(gè)元素之前（也就是插入元素作為新表的第i個(gè)元素），插入一個(gè)元素，則移動(dòng)元素個(gè)數(shù)為（）。A.n-iB.n-i-1C.n-i+1D.i9.設(shè)有一個(gè)長(zhǎng)度為n的順序表，要?jiǎng)h除第i個(gè)元素,則需移動(dòng)元素的個(gè)數(shù)為（）。A.iB.n-i-1C.n-iD.n-i+110.有關(guān)線性表的正確說(shuō)法是（）。A.線性表至少要求一個(gè)元素B.每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼C.表中的元素必須按由小到大或由大到下排序D.除了一個(gè)和最后一個(gè)元素外，其余元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼11.在線性表的順序結(jié)構(gòu)中，以下說(shuō)法正確的是（）。A.邏輯上相鄰的元素在物理位置上不一定相鄰B.數(shù)據(jù)元素是不能隨機(jī)訪問(wèn)的C.進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高D.邏輯上相鄰的元素在物理位置上也相鄰12.在非空雙向循環(huán)鏈表的*p結(jié)點(diǎn)之前插入*q結(jié)點(diǎn)的操作是（）。A.p->prior=q;q->next=p;p->prior->next=q;q->prior=p->prior;B.p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior;C.q->next=p;q->prior=p->prior;p->prior=q;p->prior->next=q;D.q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;13.對(duì)鏈表,以下敘述中正確的是（）。A.不能隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B.插入刪除元素的操作一定要要移動(dòng)結(jié)點(diǎn)C.結(jié)點(diǎn)占用的存儲(chǔ)空間是連續(xù)的D.可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)14.非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿足（）（設(shè)頭指針為head，指針p指向尾結(jié)點(diǎn)）。A.p->next==headB.p==NULLC.p==headD.p->next==NULL15.設(shè)頭指針為head的非空的單向鏈表，指針p指向尾結(jié)點(diǎn),則通過(guò)以下操作（)可使其成為單向循環(huán)鏈表。A.head=p;B.p=head;C.C.p->next=NULL;D.p->next=head;16.鏈表不具有的特點(diǎn)是（）。A.不必事先估計(jì)存儲(chǔ)空間B.可隨機(jī)訪問(wèn)任一元素C.邏輯上相鄰的元素在物理位置上不一定相鄰D.插入刪除不需要移動(dòng)元素17.在一個(gè)單鏈表Head中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行（）。A.Head=p;p->next=Head;B.p->next=Head;Head=p;C.p->next=Head;p=Head;D.p->next=Head->next;Head->next=p;18.在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（）。A.p->next=s;s->next=p->next;B.p->next=s->next;C.p=s->next;D.s->next=p->next;p->next=s;19.對(duì)于一個(gè)線性表，若要求既能進(jìn)行較快地插入和刪除，又要求存儲(chǔ)結(jié)構(gòu)能夠反映數(shù)據(jù)元素之間的邏輯關(guān)系，則應(yīng)該（）。A.以順序存儲(chǔ)方式B.以鏈接存儲(chǔ)方式C.以索引存儲(chǔ)方式D.以散列存儲(chǔ)方式20.若Head為一個(gè)帶表頭結(jié)點(diǎn)的單鏈表的表頭指針，則該表為空表的條件是（）。A.Head==NULLB.Head->next==NULLC.Head->next==HeadD.Head!=NULL21.每個(gè)存儲(chǔ)結(jié)點(diǎn)不僅含有一個(gè)數(shù)據(jù)元素，還包含一組指針，該存儲(chǔ)方式是（）存儲(chǔ)方式。A.順序B.鏈接C.索引D.散列22.非空的單向循環(huán)鏈表L的尾結(jié)點(diǎn)（由p所指向）滿足（）。A.p==NULLB.p->next==NULLC.p==LD.p->next==L23.在雙向循環(huán)雙鏈表中，刪除*p結(jié)點(diǎn)需要（）。A.p->next->prior=p->prior;p->prior->next=p->next;B.p->prior->next=p->next;p->next->prior=p->prior;C.p->prior->next=p;p->prior=p->prior->prior;D.p->prior=p->next->next;p->next=p->prior->prior;24.鏈表所具備的特點(diǎn)是（）。A.可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B.占用連續(xù)的存儲(chǔ)空間C.插入刪除元素的操作不需要移動(dòng)元素結(jié)點(diǎn)D.可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)25.帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L為空表的條件是（）。A.L==NULLB.L->next->prior=NULLC.L->next==LD.L->prior==NULL26.在一個(gè)帶頭結(jié)點(diǎn)的單向鏈表中，若要在指針q所指結(jié)點(diǎn)后插入p指針?biāo)附Y(jié)點(diǎn)，則執(zhí)行（）。A.p->next=q->next;q->next=p;B.q->next=p->next;p=q;C.p->next=q->next;p->next=q;D.q->next=p->next;p->next=q;27.若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)，則采用_____最節(jié)省運(yùn)算時(shí)間。A.單鏈表B.給出表頭指針的單向循環(huán)鏈表C.雙鏈表D.帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表28.設(shè)有兩個(gè)長(zhǎng)度為n的單向鏈表，結(jié)點(diǎn)類型相同，分別是循環(huán)鏈表和非循環(huán)鏈表，則（）。A.對(duì)于兩個(gè)鏈表來(lái)說(shuō)，刪除第一個(gè)結(jié)點(diǎn)的操作，其時(shí)間復(fù)雜度都是O(1)B.對(duì)于兩個(gè)鏈表來(lái)說(shuō)，刪除最后一個(gè)結(jié)點(diǎn)的操作，其時(shí)間復(fù)雜度都是O(n)C.循環(huán)鏈表要比非循環(huán)鏈表占用更多的內(nèi)存空間D.循環(huán)鏈表與非循環(huán)鏈表占用相同的內(nèi)存空間29.單向線性鏈表的結(jié)點(diǎn)包含data域和（）域。A.nextB.rightC.leftD.head30.帶頭結(jié)點(diǎn)的單向鏈表為空的判斷條件是（）（設(shè)頭指針為head）。A.head==NULLB.head!=NULLC.head->next==headD.head->next==NULL31.當(dāng)利用大小為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==-1表示?？眨瑒t入棧應(yīng)該執(zhí)行（）語(yǔ)句修改top指針。A.top++B.top—C.top=0D.！top32.從順序棧中刪除新元素時(shí)，應(yīng)當(dāng)（）。A.先移動(dòng)棧頂指針，再存入元素B.先讀取元素，再移動(dòng)棧頂指針C.先后次序無(wú)關(guān)緊要D.同時(shí)進(jìn)行3.（）的一個(gè)重要應(yīng)用是在程序設(shè)計(jì)中實(shí)現(xiàn)遞歸調(diào)用。A.雙向鏈表B.循環(huán)鏈表C.棧D.隊(duì)列34.棧是一種操作受限的線性表，其限制是（）。A.僅允許在表的一端進(jìn)行插入和刪除操作B.僅允許進(jìn)行插入操作C.僅允許進(jìn)行刪除操作D.僅允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除操作35.表達(dá)式3*(x+y)/(2-x)的后綴表達(dá)式是（）。A.3xy+2*2x-/B.3x*y+2x-/C.3xy2x*+/-D.3xy+*2x-/36.當(dāng)利用大小為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示?？?，則入棧應(yīng)該執(zhí)行（）語(yǔ)句修改top指針。A.top++B.top—C.top=0D.！top37.在一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（）。A.x=top;top=top->next;B.x=top->data;C.top=top->next;x=top->data;D.x=top->data;top=top->next;38.關(guān)于單鏈表實(shí)現(xiàn)的鏈棧，下面說(shuō)法正確的是（）。A.表頭為棧頂效率高B.表尾為棧頂效率高C.表中為棧頂效率高D.以上答案均不對(duì)39.表達(dá)式8/5+4的后綴表達(dá)式是（）。A.854/+B.85/+4C.84+5/D.85/4+40.棧頂指針通常命名為（）A.nextB.topC.rearD.front41.元素4，6，8，10按順序依次進(jìn)棧，按該棧的可能輸出序列依次入隊(duì)列，該隊(duì)列的可能輸出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A.10，8，4，6B.10，6，4，8C.8，4，6，10D.10，8，6，442.一般情況下，將遞歸算法轉(zhuǎn)換成等價(jià)的非遞歸算法應(yīng)該設(shè)置（）。A.棧B.隊(duì)列C.堆?；蜿?duì)列D.數(shù)組43.棧的基本運(yùn)算包括（）A.求棧長(zhǎng)B.修改棧元素C.取棧底元素D.取棧頂元素44.若讓元素a，b，c依次進(jìn)棧，則出棧順序不可能為（）。A.c，b，aB.b，a，cC.c，a，bD.a，c，b45.通常的使用順序?；蛘哝湕?shí)現(xiàn)遞歸算法，下面哪個(gè)說(shuō)法正確（）。A.順序棧效率高B.鏈棧效率高C.順序棧和鏈棧性能基本相同D.視情況而定46.一個(gè)棧的進(jìn)棧序列是10，20，30，40，50，則棧的不可能輸出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A.10,20,30,40,50B.40,30,50,10,20C.40,50,30,20,10D.50,40,30,20,1047.向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)（）。A.先移動(dòng)棧頂指針，再存入元素B.先存入元素，再移動(dòng)棧頂指針C.先后次序無(wú)關(guān)緊要D.同時(shí)進(jìn)行48.鏈棧和順序棧相比，有一個(gè)比較明顯的優(yōu)點(diǎn)，即（）。A.插入操作更加方便B.通常不會(huì)出現(xiàn)棧滿的情況C.不會(huì)出現(xiàn)?？盏那闆rD.刪除操作更加方便49.以下數(shù)據(jù)結(jié)構(gòu)中（）是線性結(jié)構(gòu)。A.有向圖B.堆C.完全二叉樹D.棧50.表達(dá)式a*(b+c)-d的后綴表達(dá)式是（）。A.abcd*+-B.abc+*d-C.abc*++d-D.-+*abcd51.在一個(gè)棧頂指針為top的鏈棧中，將一個(gè)p指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行（）。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->next52.一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4。則隊(duì)列的輸出序列是（）。A.4，3，2，1B.1，2，3，4C.1，4，3，2D.3，2，4，153.判斷一個(gè)順序隊(duì)列sq（最多元素為m）為空的條件是（）。A.sq->rear-sq->front==mB.sq->rear-sq->front-1==mC.sq->front==sq->rearD.sq->front==sq->rear+154.以下（）不是隊(duì)列的基本運(yùn)算。A.向隊(duì)尾插入一個(gè)新元素B.判斷一個(gè)隊(duì)列是否為空C.從隊(duì)列中刪除第i個(gè)元素D.讀取隊(duì)首元素的值55.假設(shè)鏈隊(duì)的隊(duì)首和隊(duì)尾指針是F和R，那么隊(duì)空的條件是（）。A.F==RB.F！=NULLC.R=NULLD.F！=R56.隊(duì)列是一種操作受限的線性表，其限制是（）。A.僅允許在表的一端進(jìn)行插入和刪除操作B.僅允許進(jìn)行插入操作C.僅允許進(jìn)行刪除操作D.僅允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除操作57.順序隊(duì)列中，隊(duì)首元素位置為5，則隊(duì)首指針位置為（）。A.3B.4C.5D.658.（）的一個(gè)重要應(yīng)用是解決主機(jī)和打印機(jī)之間速度不匹配的問(wèn)題。A.雙向鏈表B.循環(huán)鏈表C.棧D.隊(duì)列59.下面關(guān)于串的敘述中，正確的是（）。A.串其實(shí)是字母序列B.空串是由空格構(gòu)成的串C.模式匹配是串的一種重要運(yùn)算D.串只能采用順序存儲(chǔ)60.空串與空格串（）。A.相同B.不相同C.可能相同D.無(wú)法確定61.下列是”abcd321ABCD”的子串的選項(xiàng)是（）。A.“21ABC”B.“abcABCD”C.“abcD”D.“321a”62.串是什么？（）。A.多個(gè)字母的序列B.任意個(gè)字母的序列C.有限個(gè)字符的序列D.無(wú)數(shù)個(gè)字符的序列63.以下陳述中正確的是（）。A.串是一種特殊的線性表B.串的長(zhǎng)度必須大于零C.串中元素只能是字母D.空串就是空白串64.下列說(shuō)法不正確的是（）。A.串不是線性結(jié)構(gòu)B.串中元素可能是字母、數(shù)字或其他字符C.空串和空白串不一樣D.串的長(zhǎng)度可能等于零65.兩個(gè)字符串相等的條件是（）。A.串的長(zhǎng)度相等B.含有相同的字符集C.都是非空串D.兩個(gè)串的長(zhǎng)度相等且對(duì)應(yīng)位置的字符相同66.以下四個(gè)串中最小的是（）。A.“ABADF”B.“ABAFD”C.“ABADFA”D.“ABAF”67.串函數(shù)Strcat（a,b）的功能是進(jìn)行串（）。A.比較B.復(fù)制C.賦值D.連接68.字符串處理函數(shù)Strcmp（a,b）的功能是進(jìn)行串（）。A.連接B.比較C.復(fù)制D.模式匹配69.設(shè)有兩個(gè)串p和q，其中q是p的子串，q在p中首次出現(xiàn)的位置的算法稱為（）。A.求子串B.連接C.模式匹配D.求串長(zhǎng)70.兩個(gè)字符串相等的條件是（）。A.兩串的長(zhǎng)度相等B.兩串包含的字符相同C.兩串的長(zhǎng)度相等，并且兩串包含的字符相同D.兩串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符相同71.某串的長(zhǎng)度小于一個(gè)常數(shù)，則采用（）存儲(chǔ)方式最節(jié)省空間。A.鏈?zhǔn)紹.順序C.堆結(jié)構(gòu)D.無(wú)法確定72.如果進(jìn)行串的比較，下列哪個(gè)串最大？（）A.“BEIJING”B.“BEI”C.“BEFANG”D.“BEFI”73.廣義表(f,h,(a,b,d,c),d,e,((i,j),k))的長(zhǎng)度是()。A.6B.10C.8D.474.一個(gè)非空廣義表的表頭（）。A.不可能是原子B.只能是子表C.只能是原子D.可以是子表或原子75.下列廣義表中的線性表是（）。A.E(a,(b,c))B.E(a,E)C.E(a,b)D.E(a,L())76.廣義表(a,(d,a,b),h,(e,((i,j),k)))深度是()。A.6B.10C.8D.477.廣義表（a，a，b，d，e，（（i，j），k））的表頭是（）。A.（a）B.aC.a,（a，b）D.（a，a，b）78.設(shè)有一個(gè)廣義表A(a)，其表尾為（）。A.aB.(())C.()D.(a)79.深度為5的二叉樹至多有（）個(gè)結(jié)點(diǎn)。A.16B.32C.31D.1080.在一棵二叉樹中，若編號(hào)為8的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（）。A.18B.16C.15D.1781.在二叉樹的第4層最多含有（）個(gè)結(jié)點(diǎn)。A.8B.15C.16D.1782.假定一棵二叉樹中，葉子結(jié)點(diǎn)數(shù)為10，單分支結(jié)點(diǎn)數(shù)為30，則雙分支結(jié)點(diǎn)數(shù)為（）。A.7B.8C.9D.1983.在一棵二叉樹上，第5層的結(jié)點(diǎn)數(shù)最多為（）。A.8B.15C.16D.3284.一棵高度為4的二叉樹，最多含有（）個(gè)結(jié)點(diǎn)。A.8B.15C.16D.1785.在一棵樹中，度為0的結(jié)點(diǎn)稱作（）。A.葉子結(jié)點(diǎn)B.分支結(jié)點(diǎn)C.孩子結(jié)點(diǎn)D.雙親結(jié)點(diǎn)86.樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（）。A.1B.0C.2D.-187.在一棵度具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（）。A.31B.32C.33D.1688.二叉樹的按層遍歷算法需要使用（）A.隊(duì)列B.棧C.廣義表D.二維數(shù)組89.對(duì)一棵二叉樹中順序編號(hào)為i的結(jié)點(diǎn)，若它存在左孩子，則左孩子結(jié)點(diǎn)的編號(hào)為（）。A.2iB.2i+1C.2i-1D.i/290.權(quán)值為{1，2，6，8}的四個(gè)結(jié)點(diǎn)構(gòu)成的哈夫曼樹的帶權(quán)路徑長(zhǎng)度是（）。A.18B.28C.19D.2991.利用2、4、5、10這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹的帶權(quán)路徑長(zhǎng)度為（）。A.18B.16C.38D.3092.哈夫曼樹只有（）的結(jié)點(diǎn)的二叉樹。A.度為0B.度為2C.度為2和度為0D.度為2或度為093.設(shè)a，b為一棵二叉樹的兩個(gè)結(jié)點(diǎn)，在后續(xù)遍歷中，a在b前的條件是（）。A.a在b上方B.a在b下方C.a在b左方D.a在b右方94.由六個(gè)葉子結(jié)點(diǎn)a、b、c、d、e、f構(gòu)造的哈夫曼樹（）。A.唯一B.不唯一C.不確定D.以上都不對(duì)95.設(shè)一棵哈夫曼樹有20個(gè)葉子結(jié)點(diǎn)，該樹共有（）個(gè)非葉子結(jié)點(diǎn)。A.19B.20C.39D.4096.無(wú)向圖的鄰接矩陣是一個(gè)（）。A.對(duì)稱矩陣B.零矩陣C.上三角矩陣D.對(duì)角矩陣97.在無(wú)向圖中定義頂點(diǎn)vi與vj之間的路徑為從vi到vj的一個(gè)（）。A.頂點(diǎn)序列B.邊序列C.權(quán)值總和D.邊的條數(shù)98.在一個(gè)圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的（）倍。A.1/2B.1C.2D.499.一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖包含（）條邊。A.n（n-1）B.n（n+1）C.n（n-1）/2D.n（n+1）/2100.在一個(gè)無(wú)向圖中，若兩頂點(diǎn)之間的路徑長(zhǎng)度為k，則該路徑上的頂點(diǎn)數(shù)為（）。A.kB.k+1C.k+2D.2k101.鄰接表是圖的一種（）。A.順序存儲(chǔ)結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C.索引存儲(chǔ)結(jié)構(gòu)D.散列存儲(chǔ)結(jié)構(gòu)102.在有向圖的鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（）鄰接點(diǎn)。A.入邊B.出邊C.入邊和出邊D.不是入邊也不是出邊103.對(duì)有18個(gè)元素的有序表作二分查找，則查找A[3]的比較序列的下標(biāo)可能為（）。A.1、2、3B.9、5、2、3C.9、5、3D.9、4、2、3104.已知一個(gè)有序表為{11,22,33,44,55,66,77,88,99}，則順序查找元素55需要比較（）次。A.3B.4C.5D.6105.有一個(gè)長(zhǎng)度為12的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。A.37/12B.39/12C.41/12D.35/12106.有一個(gè)長(zhǎng)度為10的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。A.29/10B.31/10C.26/10D.29/9107.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（）。A.以順序存儲(chǔ)方式B.以鏈接存儲(chǔ)方式C.以順序存儲(chǔ)方式，且數(shù)據(jù)元素有序D.以鏈接存儲(chǔ)方式，且數(shù)據(jù)元素有序108.對(duì)于順序存儲(chǔ)的有序表{5，12，20，26，37，42，46，50，64}，若采用折半查找，則查找元素26的比較次數(shù)是（）。A.2B.3C.4D.5109.一組記錄的關(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，57110.每次把待排序的區(qū)間劃分為左、右兩個(gè)子區(qū)間，其中左區(qū)間中記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄的關(guān)鍵字，右區(qū)間中記錄的關(guān)鍵字均大于等于基準(zhǔn)記錄的關(guān)鍵字，這種排序稱為（）。A.插入排序B.快速排序C.堆排序D.歸并排序111.設(shè)有2000個(gè)無(wú)序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好選用（）排序法。A.快速排序B.基數(shù)排序C.冒泡排序D.堆排序112.一組記錄的關(guān)鍵字序列為（26，59，36，18，20，25），利用堆排序的方法建立的初始小根堆為（）。A.18，20，36，59，26，25B.18，20，25，59，26，36C.26，18，59，20，36，25D.26，59，36，18，20，25113.對(duì)數(shù)據(jù)元素序列（49，72，68，13，38，50，97，27）進(jìn)行排序，前三趟排序結(jié)果時(shí)的結(jié)果依次為第一趟：49，72，68，13，38，50，97，27；第二趟：49，68，72，13，38，50，97，27；第三趟：13，49，68，72，38，50，97，27。該排序采用的方法是（）。A.插入排序法B.選擇排序法C.冒泡排序法D.堆排序法114.就排序算法所用的輔助空間而言，堆排序、快速排序、歸并排序的關(guān)系是（）。A.堆排序>快速排序>歸并排序B.堆排序<快速排序<歸并排序C.堆排序<歸并排序<快速排序D.堆排序>歸并排序>快速排序115.從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱為（）。A.插入排序B.交換排序C.選擇排序D.歸并排序116.依次將每?jī)蓚€(gè)相鄰的有序表合并成一個(gè)有序表的排序方法稱為（）。A.插入排序B.交換排序C.選擇排序D.歸并排序117.一組記錄的關(guān)鍵字序列為（60，47，80，57，39，41，46，30），利用歸并排序的方法,第一趟歸并后的結(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，46118.將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（）。A.2n-1B.n-1C.2nD.n119.已知10個(gè)數(shù)據(jù)元素為（54，28，16，34，73，62，95，60，26，43），對(duì)該數(shù)列從小到大排序，經(jīng)過(guò)一趟冒泡排序后的序列為（）。A.16，28，34，54，73，62，60，26，43，95B.28，16，34，54，62，73，60，26，43，95C.16，28，34，54，62，60，73，26，43，95D.28，16，34，54，62，60，73，26，43，95二、判斷題1.通?？梢园涯吵鞘兄懈鞴徽军c(diǎn)間的線路圖抽象成樹型結(jié)構(gòu)。（×）2.數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置最重要的準(zhǔn)則是實(shí)現(xiàn)應(yīng)用程序與存儲(chǔ)結(jié)構(gòu)的獨(dú)立。（√）3.數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。（√）4.數(shù)據(jù)結(jié)構(gòu)中,元素之間存在多對(duì)多的關(guān)系稱為樹狀結(jié)構(gòu)。（×）5.只有用面向?qū)ο蟮挠?jì)算機(jī)語(yǔ)言才能描述數(shù)據(jù)結(jié)構(gòu)算法。（×）6.算法可以用不同的語(yǔ)言描述,如果用C語(yǔ)言或PASCAL語(yǔ)言等高級(jí)語(yǔ)言來(lái)描述,則算法實(shí)際上就是程序了。（×）7.數(shù)據(jù)元素可以由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成。（√）8.數(shù)據(jù)元素之間的抽象關(guān)系稱為物理結(jié)構(gòu)。（×）9.數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。（√）10.健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。（√）11.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（×）12.通常可以把一本含有不同章節(jié)的書的目錄結(jié)構(gòu)抽象成線性結(jié)構(gòu)。（×）13.數(shù)據(jù)元素是對(duì)數(shù)據(jù)操作的基本單位。（√）14.類C語(yǔ)言是對(duì)C語(yǔ)言的簡(jiǎn)化和擴(kuò)展，強(qiáng)化了C語(yǔ)言的表達(dá)能力。（√）15.數(shù)據(jù)的邏輯結(jié)構(gòu)說(shuō)明數(shù)據(jù)元素之間的順序關(guān)系,它依賴于計(jì)算機(jī)的儲(chǔ)存結(jié)構(gòu)。（×）16.順序表屬于邏輯結(jié)構(gòu)。（×）17.算法和程序都應(yīng)具有下面一些特征：有輸入，有輸出，確定性，有窮性，有效性。（×）18.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大,且插入、刪除運(yùn)算效率高。（×）19.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。（×）20.數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素構(gòu)成的集合。（√）21.線性表是一個(gè)有限序列，不可以為空。（×）22.線性結(jié)構(gòu)采取鏈?zhǔn)酱鎯?chǔ)時(shí)，其元素地址一定是連續(xù)的。（×）23.求線性表各元素的平均值是線性表的基本運(yùn)算之一。（×）24.向一個(gè)長(zhǎng)度為n的順序表中的第i個(gè)元素（1≤i≤n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)n-i個(gè)元素。（×）25.若頻繁地對(duì)一個(gè)線性表進(jìn)行插入和刪除操作，則使用順序表比較好。（×）26.用順序結(jié)構(gòu)存儲(chǔ)的線性表稱為順序表。（√）27.長(zhǎng)度為0的線性表稱為空表。（√）28.對(duì)于一個(gè)線性表，既要求能夠較快地進(jìn)行插入和刪除，又要求存儲(chǔ)結(jié)構(gòu)能夠反映數(shù)據(jù)元素之間的邏輯關(guān)系，則應(yīng)采用鏈?zhǔn)酱鎯?chǔ)方式。（√）29.在線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)物理存儲(chǔ)位置決定的；在線性表的鏈?zhǔn)酱鎯?chǔ)中，元素之間的邏輯關(guān)系是通過(guò)鏈域的指針值決定的。（√）30.一個(gè)新結(jié)點(diǎn)插入鏈表中只需要修改一個(gè)指針域即可，而不需要移動(dòng)數(shù)據(jù)元素。（×）31.在單鏈表中，要?jiǎng)h除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)。（√）32.設(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;。（√）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；。（√）34.如果不知道單向鏈表的頭指針，就無(wú)法訪問(wèn)該鏈表的任意結(jié)點(diǎn)。（√）35.各種鏈表只需定義有兩個(gè)域的結(jié)點(diǎn)。（×）36.在雙向循環(huán)鏈表上，刪除最后一個(gè)結(jié)點(diǎn)，其算法的時(shí)間復(fù)雜度為0(1)。（√）37.設(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)。（√）38.訪問(wèn)單鏈表中的結(jié)點(diǎn)，必須沿著指針鏈依次進(jìn)行。（√）39.要在一個(gè)單向鏈表中p所指向的結(jié)點(diǎn)之后插入一個(gè)s所指向的新結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，可執(zhí)行p->next=s;s->next=p->next；的操作。（×）40.要在一個(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。（√）41.采用鏈?zhǔn)酱鎯?chǔ)的線性表稱作鏈表。（√）42.設(shè)有一個(gè)單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，p指向尾結(jié)點(diǎn)，為了使該單向鏈表改為單向循環(huán)鏈表，可用語(yǔ)句p->next=head。（√）43.鏈?zhǔn)綏Ｅc順序棧相比，一個(gè)明顯的優(yōu)點(diǎn)是通常不會(huì)出現(xiàn)棧滿的情況。（√）44.遞歸的算法簡(jiǎn)單、易懂、容易編寫，而且執(zhí)行效率也高。（×）45.進(jìn)棧運(yùn)算是棧的基本運(yùn)算之一。（√）46.若讓元素a,b,c依次進(jìn)棧，則出棧次序c,a,b是不可能出現(xiàn)的情況。（√）47.遞歸算法可讀性差，但是效率高（×）48.往棧中插入元素的操作方式是：先寫入元素，后移動(dòng)棧頂指針。（×）49.棧是限定在表的一端進(jìn)行插入和刪除操作的線性表，又稱為先進(jìn)后出表。（√）50.棧是限定在表的兩端進(jìn)行插入和刪除操作的線性表，又稱為先進(jìn)先出表。（×）51.不考慮?？?，順序棧刪除元素操作是，先讀出元素，再移動(dòng)棧頂指針（√）52.順序棧永遠(yuǎn)不會(huì)出現(xiàn)棧滿的狀態(tài)（×）53.鏈棧永遠(yuǎn)不會(huì)出現(xiàn)?？盏臓顟B(tài)（×）54.遞歸定義的數(shù)據(jù)結(jié)構(gòu)通常用遞歸算法來(lái)實(shí)現(xiàn)對(duì)它的操作。（√）55.用數(shù)組實(shí)現(xiàn)順序棧，棧底可以是數(shù)組空間的任何一端（√）56.鏈棧通常不會(huì)出現(xiàn)棧滿的狀態(tài)（√）57.隊(duì)列的特性是先進(jìn)后出。（×）58.雙向循環(huán)鏈表構(gòu)建的隊(duì)列，可以只設(shè)立隊(duì)首指針，也可以只設(shè)隊(duì)尾指針（√）59.在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，當(dāng)插入一個(gè)新的隊(duì)列元素時(shí)，尾指針后移，當(dāng)刪除一個(gè)元素隊(duì)列時(shí)，頭指針后移。（√）60.將新元素插入到隊(duì)列任意位置是隊(duì)列的基本運(yùn)算之一。（×）61.隊(duì)列允許刪除的一端稱為隊(duì)尾，允許插入的一端稱為隊(duì)頭。（×）62.順序隊(duì)列的入隊(duì)算法是先檢查隊(duì)列是否為滿，若不滿則將新元素值賦給隊(duì)頭指針?biāo)赶虻臄?shù)據(jù)單元，再將隊(duì)頭指針加1。（×）63.在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中,隊(duì)頭指針指向隊(duì)頭元素的后一個(gè)位置。（×）64.串中的元素只可能是字母。（×）65.字符串屬于線性的數(shù)據(jù)結(jié)構(gòu)（√）66.串函數(shù)StrCmp（“ABCd”，“ABCD”）的值為-1。（×）67.長(zhǎng)度為0字符串稱為空白串。（×）68.兩個(gè)字符串比較時(shí)，較長(zhǎng)的串比較短的串大（×）69.用字符數(shù)組存儲(chǔ)長(zhǎng)度為n的字符串，數(shù)組長(zhǎng)度至少為n+1。（√）70.串即可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)（√）71.一個(gè)空格的串的長(zhǎng)度是0。（×）72.空串的長(zhǎng)度是1。（×）73.一個(gè)廣義表的表尾總是一個(gè)表。（√）74.一個(gè)廣義表的表頭總是一個(gè)廣義表。（×）75.數(shù)組通常具有的操作是順序存取。（×）76.廣義表的表頭總是一個(gè)廣義表。（×）77.遞歸算法執(zhí)行時(shí)，每次遞歸可將原問(wèn)題的規(guī)?？s小。（√）78.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的行號(hào)、列號(hào)和元素值三項(xiàng)信息。（√）79.廣義表A（（a,b,c）,(d,e,f)）的表尾為（(d,e,f)）。（√）80.一個(gè)廣義表((a),((b),c),(((d))))的長(zhǎng)度為3，深度為4。（√）81.設(shè)廣義表L=（（），（）），則其表頭是（（））。（×）82.樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)。（√）83.對(duì)完全二叉樹按從上到下、從左到右的順序依次編號(hào)1,2,...,n，則有當(dāng)2i≤n時(shí)，結(jié)點(diǎn)i的左孩子編號(hào)為2i，否則無(wú)左孩子。（√）84.在二叉樹的鏈接存儲(chǔ)中，每個(gè)結(jié)點(diǎn)設(shè)置三個(gè)域：值域、左指針域和右指針域。（√）85.對(duì)于一棵深度為h，度為3的樹最多有（3h-1）/2個(gè)結(jié)點(diǎn)。（×）86.一棵完全二叉樹深度為5，最少有16個(gè)結(jié)點(diǎn)。（√）87.完全二叉樹中沒(méi)有度為1的結(jié)點(diǎn)。（×）88.若樹的度為2時(shí)，該數(shù)為二叉樹。（×）89.二叉樹的存儲(chǔ)結(jié)構(gòu)有兩種，分別為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。（√）90.森林是m（m≥0）棵互不相交的樹的集合。（√）91.樹的所有結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)。（×）92.樹中全部結(jié)點(diǎn)的度均大于0。（×）93.深度為5的二叉樹最多有3層。（×）94.父親李貴有兩個(gè)兒子李萬(wàn)勝和李萬(wàn)利，李萬(wàn)勝又有三個(gè)兒子李建新、李建中和李建國(guó)，這個(gè)家庭可以用樹結(jié)構(gòu)來(lái)描述。（√）95.如果結(jié)點(diǎn)A有3個(gè)兄弟3個(gè)孩子，而且B是A的雙親，則A的度是3。（×）96.具有12個(gè)結(jié)點(diǎn)的完全二叉樹的深度為4。（√）97.一棵二叉樹每一層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹是完全二叉樹。（×）98.完全二叉樹和滿二叉樹比較合適采用順序存儲(chǔ)。（√）99.具有32個(gè)葉子結(jié)點(diǎn)的滿二叉樹共有63個(gè)結(jié)點(diǎn)。（√）100.二叉樹只能采用二叉鏈表來(lái)存儲(chǔ)。（×）101.如果結(jié)點(diǎn)A有3個(gè)兄弟，而且B是A的雙親，則B的度是4。（√）102.對(duì)于一棵深度為4的滿三叉樹，其結(jié)點(diǎn)數(shù)為40。（√）103.哈夫曼樹只存在著雙支結(jié)點(diǎn)，不存在單支結(jié)點(diǎn)。（√）104.如果一個(gè)葉子結(jié)點(diǎn)是某二叉樹中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，那么它也是該二叉樹的先序遍歷序列的最后一個(gè)結(jié)點(diǎn)。（√）105.哈夫曼樹一定是完全二叉樹或滿二叉樹。（×）106.二叉樹的遍歷就是按照一定次序訪問(wèn)樹中所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)的值僅被訪問(wèn)一次的過(guò)程。（√）107.已知一棵樹的先序序列和后序序列，一定能構(gòu)造出該樹。（×）108.圖的連通分量是無(wú)向圖的極大連通子圖。（√）109.在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接表中，邊結(jié)點(diǎn)的個(gè)數(shù)為e。（×）110.由一個(gè)具有n個(gè)頂點(diǎn)的連通圖生成的最小生成樹中，具有n-1條邊。（√）111.強(qiáng)連通分量是有向圖的極大連通子圖。（√）112.有向圖用鄰接矩陣表示后，頂點(diǎn)i的出度等于第i行中非0且非無(wú)窮的元素個(gè)數(shù)。（√）113.對(duì)于一個(gè)無(wú)向圖，每個(gè)頂點(diǎn)的入度等于出度。（√）114.對(duì)任意一個(gè)圖從它的某個(gè)頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索遍歷可訪問(wèn)到該圖的每個(gè)頂點(diǎn)。（×）115.一個(gè)有向圖的鄰接表和逆鄰接表中的節(jié)點(diǎn)個(gè)數(shù)一定相等。（√）116.有n個(gè)結(jié)點(diǎn)的無(wú)向圖中，若邊數(shù)大于n-1，則該圖是連通的。（√）117.無(wú)向圖的鄰接矩陣一定是對(duì)稱的。（√）118.對(duì)連通圖進(jìn)行深度優(yōu)先遍歷可以訪問(wèn)到該圖中的所有頂點(diǎn)。（√）119.在一個(gè)連通圖中存在著1個(gè)連通分量。（√）120.鄰接表只能用于存儲(chǔ)有向圖，而鄰接矩陣則可存儲(chǔ)有向圖和無(wú)向圖。（×）121.有向圖的鄰接矩陣一定是非對(duì)稱的。（×）122.圖的廣度優(yōu)先搜索序列是惟一的。（×）123.采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷方法類似于二叉樹的按層次遍歷方法。（√）124.圖的最小生成樹只有一棵。（×）125.根據(jù)圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行某種次序的遍歷，得到的頂點(diǎn)序列是唯一的。（×）126.使用鄰接矩陣存儲(chǔ)圖的時(shí)候，占用空間大小與圖的結(jié)點(diǎn)個(gè)數(shù)沒(méi)有關(guān)系。（×）127.用鄰接矩陣存儲(chǔ)圖的時(shí)候，占用空間大小不但與圖的結(jié)點(diǎn)個(gè)數(shù)有關(guān)還與圖的邊數(shù)有關(guān)。（×）128.假設(shè)在有序線性表A[1..20]上進(jìn)行折半查找，則比較五次查找成功的結(jié)點(diǎn)數(shù)為5。（√）129.在一個(gè)查找表中，能夠唯一地確定一個(gè)記錄的關(guān)鍵字稱為主關(guān)鍵字。（√）130.折半查找只適用于順序存儲(chǔ)結(jié)構(gòu)的有序表。（√）131.采用順序查找法對(duì)長(zhǎng)度為n（n為偶數(shù)）的線性表進(jìn)行查找，采用從前向后的方向查找。在等概率條件下成功查找到前n/2個(gè)元素的平均查找長(zhǎng)度為(n+2)/4。（√）132.在順序查找、折半查找、哈希表查找3種方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是折半查找。（×）133.二叉排序樹的建立過(guò)程實(shí)際上是從空樹逐次插入的過(guò)程。（√）134.二叉排序樹中某一結(jié)點(diǎn)的左兒子一定小于樹中任一個(gè)結(jié)點(diǎn)的右兒子。（×）135.根據(jù)無(wú)序序列構(gòu)造二叉排序樹的過(guò)程，也是對(duì)無(wú)序序列排序的過(guò)程。（√）136.使用折半查找算法的前提條件是，查找表中記錄相應(yīng)的關(guān)鍵字值必須按升序或降序排列。（√）137.二叉樹為二叉排序樹的充分必要條件是，任一個(gè)分支結(jié)點(diǎn)的值都大于其左孩子的值，小于右孩子的值。（×）138.在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是哈希表查找。（√）139.理想情況下，哈希表查找等概率查找成功的時(shí)間復(fù)雜度是O(1)。（√）140.采用分塊查找時(shí)，數(shù)據(jù)的組織方式是把數(shù)據(jù)分成若干塊，塊內(nèi)數(shù)據(jù)不必有序，但塊間必需有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引表。（√）141.折半查找的前提條件是，查找表中記錄相應(yīng)的關(guān)鍵字值必須有序或者部分有序。（×）142.折半查找方法運(yùn)用在升序序列比降序序列效率更高，所以降序序列最好先轉(zhuǎn)換為升序序列。（×）143.一個(gè)好的哈希函數(shù)，應(yīng)該使哈希地址均勻地分布在整個(gè)哈希表的地址區(qū)間中，完全避免沖突的發(fā)生。（×）144.二叉排序樹中任一棵子樹都是二叉排序樹。（√）145.分塊查找是一種介于順序查找和折半查找之間的查找方法。（√）146.按{18，42，10，86，52，20}的順序構(gòu)成的二叉排序樹，其根結(jié)點(diǎn)為18。（√）147.線性表用關(guān)鍵字的順序方式存儲(chǔ)，可以用二分法排序。（×）148.對(duì)二叉排序樹進(jìn)行后序遍歷，可以使遍歷所得到的序列是有序序列。（×）149.二叉排序樹在呈單支二叉樹時(shí)，查找效率最低。（√）150.采用分塊查找時(shí)，若線性表中共有324個(gè)元素，查找每個(gè)元素的概率相同，假設(shè)采用順序查找來(lái)確定結(jié)點(diǎn)所在的塊，每塊應(yīng)分12個(gè)結(jié)點(diǎn)最佳。（×）151.按照一定規(guī)則，在二叉排序樹上插入、刪除結(jié)點(diǎn)，仍能保持二叉排序樹的性質(zhì)。（√）152.分塊查找分為兩個(gè)步驟：第一步是要對(duì)索引表進(jìn)行查找；第二步是在塊中查找。這兩步查找都可以采用折半查找或者順序查找方法。（×）153.序列3,1,7,18,6,9,13,12經(jīng)一趟歸并排序的結(jié)果為1,3,7,18,6,9,13,12。（×）154.在歸并排序中，在第3趟歸并中，是把長(zhǎng)度為4的有序表歸并為長(zhǎng)度為8的有序表。（√）155.對(duì)記錄序列排序是指按記錄的某個(gè)關(guān)鍵字排序，記錄序列按主關(guān)鍵字排序結(jié)果是唯一的。（√）156.對(duì)16個(gè)元素的序列用冒泡排法進(jìn)行排序，最多需要進(jìn)行15趟冒泡。（√）157.待排序的序列為8,3,4,1,2,5,9，采用直接選擇排序算法，當(dāng)進(jìn)行了兩趟選擇后，結(jié)果序列為1,2,8,3,4,5,9。（×）158.在對(duì)一組記錄（50，40，95，20，15，70，60，45，80）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需要比較2次。（×）159.冒泡排序是一種比較簡(jiǎn)單的交換排序方法。（√）160.8個(gè)元素進(jìn)行冒泡法排序，至多需要進(jìn)行7趟冒泡,其中第5趟冒泡共需要進(jìn)行3次元素間的比較。（√）161.在堆排序和快速排序中，若原始記錄接近正序和反序，則最好選用快速排序。（×）162.簡(jiǎn)單插入排序是不穩(wěn)定的排序算法。（×）163.序列15,13,16,14,19,17，采用冒泡排序算法(升序)，經(jīng)一趟冒泡后，結(jié)果序列是13,15,14,16,17,19。（√）三、綜合題1.設(shè)SeqStack為順序棧，寫出下列程序段執(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));A.151285133B.358121315C.151312853D.1512133852.設(shè)有一個(gè)不帶頭結(jié)點(diǎn)的單向鏈表，頭指針為head，p、prep是指向結(jié)點(diǎn)類型的指針，該鏈表在輸入信息時(shí)不慎把相鄰兩個(gè)結(jié)點(diǎn)的信息重復(fù)輸入，以下程序段是在該單向鏈表中查找這相鄰兩個(gè)結(jié)點(diǎn)，把該結(jié)點(diǎn)的數(shù)據(jù)域data打印出來(lái)，并把其中之一從鏈表中刪除，填寫程序中的空格。

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->data3.設(shè)有一個(gè)頭指針為head的單向鏈表中（結(jié)點(diǎn)類型為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;

q->next=s;A.p=p->nextB.q=q->nextC.s=s->nextD.head=head->next4.設(shè)有一個(gè)頭指針為head的不帶頭結(jié)點(diǎn)單向鏈表中（結(jié)點(diǎn)類型為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)

q=q->next;

s->next=p;

________;A.p->next=qB.p->next=sC.q->next=sD.q->next=p5.設(shè)線性表以不帶頭結(jié)點(diǎn)的單向鏈表存儲(chǔ)，鏈表頭指針為head。以下程序的功能是輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)域data，完成程序中空格部分。

#defineNULL0

voidmain()

{NODE*head,*p;

p=head;/*p為工作指針*/

do

{printf(“%d\n”,p->data);

p=p->next;

}while(________);

}A.p==NULLB.p!=NULLC.p!=headD.p==head6.假設(shè)隊(duì)列順序存儲(chǔ)結(jié)構(gòu)為：

structSeqQueue{

ElemTypedata[MaxSize];

intfront,rear;

};

structSeqQueue*sq;

請(qǐng)補(bǔ)充下面出隊(duì)算法（不考慮空間循環(huán)使用）。

voidOutQueue(structSeqQueue*sq,ElemtTypex){

if(1){

printf(“隊(duì)列已空，不能出隊(duì)\n”);

exit(1);

}

2

returnsq->data[sq->front-1];

}

其中，1和2處應(yīng)該補(bǔ)充的代碼是（）A.sq->front==sq->rear,sq->front++B.sq->rear==sq->front,sq->rear++;C.sq->front=sq->rear,sq->front++D.sq->rear=sq->front,sq->rear++;7.以下程序段執(zhí)行后，c的值為（）。

char*a[5]={“12378”,”1237”,”1236789”,”1237”,”123708”}

inti,c=0

for(i=0;i<5;i++)

if(strcmp(a[i],”1237”)==0)c++;A.2B.5C.0D.12378.假設(shè)鏈表結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)為：

structnode{

intdata;

structnode*next;

};

structnode*front,*next;

InitQueue()、InQueue()、OutQueue()、QueueEmpty()分別是鏈隊(duì)的初始化、入隊(duì)、出隊(duì)、判空操作。

下面程序執(zhí)行后，運(yùn)行結(jié)果是（）。

inti;

InitQueue();

for(i=0;i<6;i++)InQueue(i++);

while(!QueueEmpty())

printf(“%d”,OutQueue());

printf(“\n”);A.012345B.123456C.01491625D.以上答案均不對(duì)9.在下面空格處填寫一條語(yǔ)句，以使下面的順序隊(duì)列入隊(duì)算法完整。

voidInQueue(structSeqQueue*sq,intx)

{if(sq->rear==MaxSize)

{printf(“隊(duì)列已滿！\n”);

exit(1);

}

______________

sq->rear++;

}A.x=sq->data[sq->rear];B.x=sq->rear[sq->data];C.sq->rear[sq->data]=x;D.sq->data[sq->rear]=x;10.假設(shè)隊(duì)列順序存儲(chǔ)結(jié)構(gòu)為：

structSeqQueue{

ElemTypedata[MaxSize];

intfront,rear;

};

structSeqQueue*sq;

請(qǐng)補(bǔ)充下面入隊(duì)算法（不考慮空間循環(huán)使用）。

voidInQueue(structSeqQueue*sq,ElemtTypex){

if(1){

printf(“隊(duì)列已滿\n”);

exit(1);

}

sq->data[sq->rear]=x;

2

}

其中，1和2處應(yīng)該補(bǔ)充的代碼是（）A.sq->front==Maxsize,sq->rear++;B.sq->rear==Maxsize,sq->rear++;C.sq->front==Maxsize,sq->front++;D.sq->rear==Maxsize,sq->front++;11.寫出下列程序段執(zhí)行后的結(jié)果

SeqQueueQ;

InitQueue(Q);

inti,a[4]={5,8,12,15};

for(i=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));A.58121530B.121553018C.812153018D.12155183012.在下面空格處填寫一條語(yǔ)句，以使下面的循環(huán)隊(duì)列出隊(duì)算法完整。

ElemTypeOutQueue(structSeqQueue*sq)

{if(sq->rear==sq->front)

{printf(“隊(duì)列已空，不能進(jìn)行出隊(duì)操作！\n”);

exit(1);

}

________

sq->front=(sq->front+1)%MaxSize;

returnx;

}A.x=sq->data[sq->front-1];B.x=sq->data[sq->front+1];C.x=sq->data[sq->front];D.x=sq->data[sq->rear];13.在下面空格處填寫一條語(yǔ)句，以使下面的串比較算法完整。

intstrcmp(char*s1,char*s2)

{inti;

for(i=0;s1[i]!=’\0’&&s2[i]!=’\0’;i++)

if(s1[i]>s2[i])

return1;

else

if(s1[i]<s2[i])

return-1;

if(s1[i]==’\0’&&s2[i]==’\0’)

_________

else

if(s1[i]!=’\0’)

return1;

else

return-1;

}A.return0;B.return-1;C.return1;D.returni;14.以下程序段的結(jié)果是：c的值為（）

chara[]=”abcdefgjh”；

int*p=a,c=0;

While(*p++)c++;A.8B.9C.10D.1115.設(shè)查找表為：

用折半查找在該查找表成功查找到元素55需要經(jīng)過(guò)（）次比較。A.1B.2C.3D.416.設(shè)查找表為(16,15,20,53,64,7)，用冒泡法對(duì)該表進(jìn)行排序，在排序后的有序表的基礎(chǔ)上進(jìn)行折半查找，在等概率條件下,成功查找的平均查找長(zhǎng)度為（）。A.3.5B.3C.19/6D.14/617.設(shè)查找表為(1,10,11,14,23,27,29,55,68)，對(duì)上述查找表進(jìn)行折半查找，為了成功查找到元素14,需要依次與元素（）進(jìn)行比較。A.23,10,1,14B.23,29,27,14C.23,10,11,14D.23,29,55,1418.設(shè)有數(shù)據(jù)集合{50，39，17，83，91，14，65}，此二叉排序樹的（）遍歷是有序序列。A.先序B.中序C.后序D.按層19.設(shè)有查找表為(5,14,2,6,18,7,4,16,3),依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹，對(duì)該二叉樹進(jìn)行后序遍歷的結(jié)果序列為（）。A.3,4,2,7,6,16,18,14,5B.2,3,4,5,6,7,14,16,18C.5,2,14,4,6,18,3,7,16D.5,2,4,3,14,6,7,18,1620.以下為求二叉樹深度的算法，完成程序中空格部分。

intBTreeDepth(BTreeNode*BT)

{if(BT==NULL)

return0;

else

{intdep1=BTreeDepth(BT->left);/*計(jì)算左子樹的深度*/

intdep2=BTreeDepth(BT->right);/*計(jì)算右子樹的深度*/

if(________)

returndep1+1;

else

returndep2+!;

}

}A.dep1>dep2B.dep1<dep2C.BT->left==NULLD.BT->right==NULL21.以下程序是先序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(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)22.設(shè)數(shù)據(jù)序列為：{53,30,37,12,45,24,96}，從空二叉樹開(kāi)始逐個(gè)插入該數(shù)據(jù)序列來(lái)形成二叉排序樹，若希望高度最小，應(yīng)該選擇的序列是（）。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,5323.設(shè)一組記錄的關(guān)鍵字序列為（49，83，59，41，43，47），采用堆排序算法建立初始小根堆，在該小根堆上逐次取走堆頂元素后，經(jīng)調(diào)整得到的4個(gè)元素的堆為（）。A.47，49，59，83B.47，59，49，83C.47，83，49，59D.49，59，47，8324.以下是直接插入排序算法對(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++B.i++C.j—D.i--25.一組記錄的關(guān)鍵字序列為（36，69，46，28，30，84），對(duì)該序列進(jìn)行直接選擇排序（每次選擇最小關(guān)鍵字），第二趟排序后的結(jié)果序列為（）。A.28，69，46，36，30，84B.28，30，46，36，69，84C.36，46，69，28，30，84D.28，30，36，69，46，8426.設(shè)關(guān)鍵字序列為：（36，69，46，28，30，74），將此序列用快速排序的方法，以第一個(gè)記錄