寧夏開(kāi)放大學(xué)《數(shù)據(jù)結(jié)構(gòu)》終結(jié)性考試復(fù)習(xí)題庫(kù)（附答案）

PAGEPAGE1寧夏開(kāi)放大學(xué)《數(shù)據(jù)結(jié)構(gòu)》終結(jié)性考試復(fù)習(xí)題庫(kù)（附答案）一、單選題1.最小生成樹(shù)指的是()。A、由連通圖所得到的邊數(shù)最少的生成樹(shù)B、由連通圖所得到的頂點(diǎn)數(shù)相對(duì)較少的生成樹(shù)C、連通圖中所有生成樹(shù)中權(quán)值之和為最小的生成樹(shù)D、連通圖的極小連通子圖答案：C2.設(shè)有一個(gè)順序棧S,元素1,2,3,4,5,6依次進(jìn)棧,如果6個(gè)元素的出棧順序?yàn)?,3,4,6,5,1,1則順序站的容量至少可以存儲(chǔ)()個(gè)元素。A、2B、3C、4D、5答案：B3.一個(gè)向量第一個(gè)元素的地址是100,每個(gè)元素的長(zhǎng)度為2,則第5個(gè)元素的地址是()。A、100B、108C、110D、120答案：B4.樹(shù)中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加()。A、0B、1C、-1D、2答案：C5.一棵樹(shù)的廣義表表示為a(b(c),d(e(g(h)),f,k)),則該樹(shù)中e結(jié)點(diǎn)的孩子結(jié)點(diǎn)個(gè)數(shù)為()。A、0B、1C、2D、3答案：B6.已知輸入序列為abcd,經(jīng)過(guò)隊(duì)列后能得到的輸出序列有()。A、dacbB、abcdC、dcbaD、cadb答案：B7.下圖中的樹(shù)轉(zhuǎn)換成二又樹(shù)后,B結(jié)點(diǎn)的孩子結(jié)點(diǎn)有()。A、僅有EB、C和DC、E和CD、E和F答案：C8.某圖的鄰接矩陣如圖所示,若G為有向圖,則G中共有()條弧。

A、1B、2C、3D、4答案：D9.G是一個(gè)簡(jiǎn)單的非連通無(wú)向圖,共有28條邊,則該圖至少有()個(gè)頂點(diǎn)。A、6B、7C、8D、9答案：D10.最大容量為n的循環(huán)隊(duì)列,隊(duì)尾指針是rear,隊(duì)頭指針是front,初始時(shí)均為0,采用損失一個(gè)空間的原則,則隊(duì)空的條件是()。A、(rear+1)%n==frontB、rear==frontC、rear+1==frontD、(rear-1)%n==front答案：B11.設(shè)無(wú)向圖G中有五個(gè)頂點(diǎn),各頂點(diǎn)的度分別為2、4、3、1、2,則G中邊數(shù)為()。A、4B、5C、6D、無(wú)法確定答案：C12.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種()的存取結(jié)構(gòu)。A、隨機(jī)存取B、順序存取C、索引存取D、Hash存取答案：A13.下面關(guān)于圖的敘述中,正確的是()。A、圖與樹(shù)的區(qū)別在于圖的邊數(shù)大于頂點(diǎn)數(shù)B、假設(shè)有圖G=(V,C、,頂點(diǎn)集V’V,E’E則V’和E’構(gòu)成G的子圖D、無(wú)向圖的連通分量指無(wú)向圖中的極大連通子圖E、圖的遍歷就是從圖中某個(gè)頂點(diǎn)出發(fā)訪問(wèn)圖中的其余頂點(diǎn)。答案：C14.設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn),則選用()最節(jié)省時(shí)間。A、單鏈表B、單循環(huán)鏈表C、帶尾指針的單循環(huán)鏈表D、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表答案：C15.對(duì)圖從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷,則()是可能得到的遍歷序列。

A、cfgdebB、abcdefgC、acdgbefD、abefgcd答案：A16.一棵左子樹(shù)為空的二叉樹(shù),在先序線索化后,其中為空的指針域個(gè)數(shù)是()。A、不確定B、0C、1D、2答案：D17.圖的廣度優(yōu)先遍歷類似于二叉樹(shù)的()遍歷,它所用到的數(shù)據(jù)結(jié)構(gòu)是()。A、前序,棧B、層次,棧C、前序,隊(duì)列D、層次,隊(duì)列答案：D18.用單鏈表方式存儲(chǔ)的線性表,存儲(chǔ)每個(gè)結(jié)點(diǎn)需要兩個(gè)域,一個(gè)數(shù)據(jù)域,另一個(gè)是()。A、當(dāng)前結(jié)點(diǎn)所在地址域B、地址域C、空指針域D、空閑域答案：B19.已知單鏈表的每個(gè)結(jié)點(diǎn)包括一個(gè)指針域next,它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。現(xiàn)要將指針指向的新結(jié)點(diǎn)插入到指針p指向的結(jié)點(diǎn)之后,下面的操作序列中正確的是()。A、q=p->next;p->next=q->next:B、p->next=q->next:q=p->next:C、q->next=p->next;p->next=q:D、p->next=q;q->next=p->next;答案：C20.n個(gè)頂點(diǎn)的無(wú)向圖的接表最多有()個(gè)結(jié)點(diǎn)。A、n2B、n(n-1)C、n(n+1)D、n(n-1)/2答案：B21.遞歸函數(shù)調(diào)用時(shí),處理參數(shù)及返回地址,要用一種稱為()的數(shù)據(jù)結(jié)構(gòu)A、隊(duì)列B、多維數(shù)組C、棧D、線性表答案：C22.對(duì)有n個(gè)頂點(diǎn)、e條邊且使用鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先遍歷,其算法的時(shí)間復(fù)雜度是()。A、O(n)B、O(e)C、O(n+e)D、O(nXe)答案：C23.一個(gè)圖中包含k個(gè)連通分量,若按深度優(yōu)先遍歷方法訪問(wèn)多有頂點(diǎn),則必須調(diào)用()次深度優(yōu)先遍歷算法。A、1B、k-1C、kD、k+1答案：C24.在下圖中,F結(jié)點(diǎn)的兄弟結(jié)點(diǎn)是()。

A、EB、DC、ID、空答案：D25.以下說(shuō)法不正確的是()。A、無(wú)向圖中的極大連通子圖稱為連通分量B、圖的廣度優(yōu)先遍歷中一般要采用隊(duì)列來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn)C、圖的深度優(yōu)先遍歷中一般要采用棧來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn)D、有向圖的遍歷不可采用廣度優(yōu)先遍歷方法答案：D26.一維數(shù)組與線性表的區(qū)別是()。A、前者長(zhǎng)度固定,后者長(zhǎng)度可變B、兩者長(zhǎng)度均固定C、后者長(zhǎng)度固定,前者長(zhǎng)度可變答案：A解析：D兩者長(zhǎng)度均可變27.對(duì)于順序存儲(chǔ)的棧和隊(duì)列,進(jìn)行插入和刪除的算法的時(shí)間復(fù)雜度為()。A、O(1)B、O(n)C、0(n2)D、無(wú)法確定答案：A28.在C語(yǔ)言中,有一種適用于不同數(shù)據(jù)類型構(gòu)成的數(shù)據(jù)的結(jié)構(gòu)稱為()。A、結(jié)構(gòu)體B、數(shù)組C、變量D、常量答案：A29.設(shè)T是赫夫曼樹(shù),具有5個(gè)葉結(jié)點(diǎn),樹(shù)T的高度最高可以是()。A、2B、3C、4D、5答案：D30.用鄰接表存儲(chǔ)圖所用的空間大小()。A、與圖的頂點(diǎn)數(shù)和邊數(shù)都有關(guān)B、只與圖的邊數(shù)有關(guān)C、只與圖的頂點(diǎn)數(shù)有關(guān)D、與邊數(shù)的平方有關(guān)答案：A31.棧中元素的進(jìn)出原則是()。A、先進(jìn)先出B、后進(jìn)先出C、棧空則進(jìn)D、棧滿則出答案：B32.當(dāng)順序棧中元素為n個(gè),進(jìn)棧運(yùn)算時(shí)發(fā)生上溢,則說(shuō)明該棧的最大容量為()。A、n-1B、nC、n+1D、n/2答案：B33.某順序棧saStack,其成員包含兩部分:data[10]和top,分別代表數(shù)據(jù)和棧頂,初始時(shí)top值為-1,則表示棧頂數(shù)據(jù)元素的是()。A、sqStack.data[9]B、sqStack.topC、sqStack.data[sqStack.top]D、sqStack.top+1答案：C34.如下圖所示的4棵二叉樹(shù)中,（）不是完全二又樹(shù)。

A、圖AB、圖BC、圖CD、圖D答案：C35.一棵深度為h的滿k又樹(shù)有如下性質(zhì):第h層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn),其余各層上的每個(gè)結(jié)點(diǎn)都有k棵非空子樹(shù)。如果按層次順序(同層自左至右)從1開(kāi)始對(duì)全部結(jié)點(diǎn)編號(hào),則第i層結(jié)點(diǎn)數(shù)目是()。A、iB、kC、ki-1D、ki-1答案：D36.若鄰接表中有奇數(shù)個(gè)邊結(jié)點(diǎn),則一定是()。A、圖中有奇數(shù)個(gè)頂點(diǎn)B、圖中有偶數(shù)個(gè)頂點(diǎn)C、圖為無(wú)向圖D、圖為有向圖答案：D37.由3個(gè)結(jié)點(diǎn)所構(gòu)成的二又樹(shù)有()種形態(tài)。A、1B、3C、5D、7答案：C38.對(duì)于順序循環(huán)隊(duì)列,以下說(shuō)法正確的是()。A、無(wú)法判斷隊(duì)列是否為空B、無(wú)法判斷隊(duì)列是否為滿C、隊(duì)列不可能滿D、以上說(shuō)法都不對(duì)答案：D39.雙向鏈表中有兩個(gè)指針域,link和rink分別指向前趨及后,設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn),現(xiàn)要求刪去p所指結(jié)點(diǎn),則正確的刪除是()(鏈中結(jié)點(diǎn)數(shù)大于2,p不是第一個(gè)結(jié)點(diǎn))。A、p->llink->rlink=p->llink;p->rlink->llink=p->rlink;free(p);B、free(p);p->llink->rlink=p->llink;p->rlink->llink=p->rlink;C、p->llink->rlink=p->llink;free(p);p->rlink->llink=p->rlink;D、以上A,B,C都不對(duì)答案：D40.下列關(guān)于最小生成樹(shù)的敘述中,正確的是()。A、最小生成樹(shù)不唯一,但是最小生成樹(shù)各邊權(quán)值總和唯一B、所有權(quán)值最小的邊一定會(huì)出現(xiàn)在最小生成樹(shù)中C、使用Prim算法從不同頂點(diǎn)開(kāi)始得到的最小的生成樹(shù)一定相同D、使用Prim算法和使用Kruskal算法得到的最小生成樹(shù)總不相同答案：A41.已知一個(gè)有向圖的邊集為{<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>},則由該圖產(chǎn)生的一種可能的拓?fù)湫蛄袨?)。A、,b,c,d,eB、A,b,d,e,bC、A,c,b,e,dD、A,c,d,b,e答案：A42.在AOE網(wǎng)中()關(guān)鍵路徑。A、一定只有一條B、可能只有一條C、不可能只有一條D、以上答案都不對(duì)答案：B43.用鄰接矩陣存儲(chǔ)有向圖,矩陣中主對(duì)角線以下的元素均為零,則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)論是()。A、拓?fù)湫蛄写嬖谇椅ㄒ籅、拓?fù)湫蛄写嬖谇也晃ㄒ籆、拓?fù)湫蛄写嬖谇铱赡懿晃ㄒ籇、無(wú)法確定拓?fù)湫蛄惺欠翊嬖诖鸢福篊44.分析以下程序段,其時(shí)間復(fù)雜度為T(mén)()=()。

I=1;

While(i<=n)

I="3*i;<">A、O(n)B、O(n2)C、O(n3)D、O(log3n)答案：D45.用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí),其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn),則在進(jìn)行插入(入隊(duì))操作時(shí)()。A、僅修改隊(duì)頭指針B、僅修改隊(duì)尾指針C、隊(duì)頭、隊(duì)尾指針都要修改D、隊(duì)頭和隊(duì)尾指針都可能要修改答案：D46.已知單鏈表的每個(gè)結(jié)點(diǎn)包括一個(gè)指針域next,它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。帶頭結(jié)點(diǎn)的單鏈表L為空的條件是()A、L!=NULLB、L==NULLC、L->next==NULLD、L->next==L答案：C47.下面關(guān)于圖的敘述中,正確的是()。A、強(qiáng)連通有向圖的任何頂點(diǎn)到所有其他頂點(diǎn)都有弧B、任意圖頂點(diǎn)的入度都等于出度C、有向完全圖一定是強(qiáng)連通有向圖D、有向圖邊集的子集和頂點(diǎn)集的子集可構(gòu)成原有向圖的子集答案：C48.棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是()。A、順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B、散列方式和索引方式C、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和數(shù)組D、線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)答案：A49.靜態(tài)鏈表與動(dòng)態(tài)鏈表相比,其缺點(diǎn)是()。A、插入刪除時(shí)需要移動(dòng)較多數(shù)據(jù)B、有可能浪費(fèi)較多空間C、不能隨機(jī)存取D、以上都不對(duì)答案：B50.如圖所示,該二又樹(shù)的前序遍歷序列是()A、EGFACDBB、EAGCFBDC、EACBDGFD、EGACDFB答案：C51.計(jì)算機(jī)算法指的是解決問(wèn)題的有限運(yùn)算序列,它必具備輸入、輸出和()等五個(gè)特性。A、可行性、可移植性和可擴(kuò)充性B、可行性、確定性和有窮性C、確定性、有窮性和穩(wěn)定性D、易讀性、穩(wěn)定性和安全性答案：B52.已知單鏈表的每個(gè)結(jié)點(diǎn)包括一個(gè)指針域next,它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。兩個(gè)指針P和Q,分別指向單鏈表的兩個(gè)結(jié)點(diǎn),P所指結(jié)點(diǎn)是Q所指結(jié)點(diǎn)直接前驅(qū)的條件是()。A、P->next==Q->nextB、P->next==QC、Q->next==PD、P==Q、答案：B53.已知鏈表的每個(gè)結(jié)點(diǎn)包括一個(gè)指針域next,它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。非空的循環(huán)單鏈表head的尾結(jié)針p滿足()。A、p->next=headB、p->next=NULLC、p=NULLD、p=head答案：A54.若有向圖G中頂點(diǎn)數(shù)為n,則圖G至多有()條邊。A、0B、nC、n(n-1)/2D、n(n-1)答案：D55.設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空,元素1,e2,e3,e4,e5和e6依次通過(guò)棧S,一個(gè)元素出棧后即進(jìn)隊(duì)列Q若6個(gè)元素出隊(duì)的序列是e2,e4,e3,e6,e5,e1則棧S的容量至少應(yīng)該是()。A、6B、4C、3D、2答案：C56.一棵完全二又樹(shù)按層次遍歷的序列為ABCDEFGHI，后序遍歷中結(jié)點(diǎn)B的直接后繼是結(jié)點(diǎn)()。A、DB、FC、HD、I答案：B57.某無(wú)向圖的鄰接矩陣如圖所示,可以看出該圖共有()個(gè)頂點(diǎn)。

A、1B、3C、6D、9答案：B58.設(shè)有一順序棧已含3個(gè)元素,如下圖所示,元素a4正等待進(jìn)棧。那么下列4個(gè)序列中不可能出現(xiàn)的出棧序列是()。

A、3,a1,a4,a2B、a3,a2,a4,a1C、a3,a4,a2,a1D、a4,a3,a2,a1答案：A59.在鏈隊(duì)列中,假定fornt和rear分別為隊(duì)首和隊(duì)尾指針,則刪除一個(gè)結(jié)點(diǎn)的操作為()。A、front=front->next;B、rear=rear->next;C、rear=front->next:D、front=rear->next;答案：A60.在進(jìn)棧運(yùn)算時(shí),應(yīng)先判別棧是否①,在出棧運(yùn)算時(shí).應(yīng)先判別棧是否②,①②處應(yīng)該是()。A、空,滿B、滿,空C、滿,上溢D、空,下溢答案：B61.棧和隊(duì)列的共同點(diǎn)是()。A、都是先進(jìn)先出B、都是先進(jìn)后出C、只允許在端點(diǎn)處插入和刪除元素D、沒(méi)有共同點(diǎn)答案：C62.設(shè)一棵二叉樹(shù)中有3個(gè)葉子結(jié)點(diǎn),有8個(gè)度為1的結(jié)點(diǎn),則該二叉樹(shù)中總的結(jié)點(diǎn)數(shù)是()A、11B、12C、13D、無(wú)法確定答案：C63.若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列,且當(dāng)前rear和front的值分別為0和3,當(dāng)從隊(duì)列中刪除一個(gè)元素,再加入兩個(gè)元素后,rear和front的值分別為()。A、1和5B、2和4C、4和2D、5和1答案：B64.設(shè)無(wú)向圖G中頂點(diǎn)數(shù)為n,則圖G至多有()條邊。A、0B、nC、n(n-1)/2D、n(n-1)答案：C65.在下圖中，A結(jié)點(diǎn)是（）。

A、葉節(jié)點(diǎn)B、根結(jié)點(diǎn)但不是分支結(jié)點(diǎn)C、根結(jié)點(diǎn)也是分支結(jié)點(diǎn)D、分支結(jié)點(diǎn)但不是根結(jié)點(diǎn)答案：C66.n個(gè)頂點(diǎn)的強(qiáng)連通圖至少有()條邊。A、nB、n-1C、n+1D、n*(n-1)答案：A67.對(duì)于任何一棵二又樹(shù),如果其終端結(jié)點(diǎn)數(shù)為no,度為2的結(jié)點(diǎn)數(shù)為n2,則no=()。A、n2-1B、n2+1C、n2D、n2-2答案：B68.一棵樹(shù)的廣義表表示為a(b(c),d(e(g(h)),f,k)),則該樹(shù)的度為()。A、0B、1C、2D、3答案：D69.分析以下程序段,其時(shí)間復(fù)雜度為T(mén)()=()

X=0;

For(i=1;i<n;i++);

For(j=1;j<n;j++);

For(k=1;k<n;k++);

x++;A、O(n)B、O(n2)C、O(n3)D、O(1)答案：A70.若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu),訪問(wèn)其第i個(gè)元素的算法時(shí)間復(fù)雜度為()A、O(1)B、O(n)C、O(n2)D、O(log2n)答案：A71.已知二又樹(shù)的后序遍歷序列是dabe

C,中序序列是deba

C,則它的前序遍歷是()。A、cedbaB、acbedC、decabD、eabc答案：A72.用一維數(shù)組存放的一棵完全二叉樹(shù)如下圖所示,則后序遍歷該二叉樹(shù)時(shí)產(chǎn)生的結(jié)點(diǎn)序列中結(jié)點(diǎn)B后面的結(jié)點(diǎn)是()。

A、LB、FC、D、A答案：A73.n個(gè)頂點(diǎn)的強(qiáng)連通圖,若該連通圖含有最少的邊,其形狀是()。A、無(wú)回路B、有多個(gè)回路C、環(huán)狀D、無(wú)法確定答案：C74.判定一個(gè)非循環(huán)的順序隊(duì)列Q(最多元素為M)為滿隊(duì)列的條件是()。A、Q->rear-Q->front==MB、Q->rear-Q->front-1==MC、Q->front==Q->rearD、Q->rear==M-1答案：D75.有結(jié)構(gòu)體定義及結(jié)構(gòu)體類型數(shù)組如下:structworklist{intno;charnamel20];charsex;}person[5];需要給結(jié)構(gòu)體數(shù)組中第2個(gè)變量的no成員賦值為5,正確的寫(xiě)法是()。A、no=5;B、person.no=5:C、person[2].no=5;D、person[1].no=5.答案：D76.線性表L=(a1,a2,...,an),下列說(shuō)法正確的是()。A、每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B、線性表中至少有一個(gè)元素C、表中所有元素的排列順序是由小到大或者由大到小D、除了第一個(gè)元素和最后一個(gè)元素外,其余每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼答案：D77.已知鏈表的每個(gè)結(jié)點(diǎn)包括一個(gè)指針域next它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。在頭指針為head且表長(zhǎng)大于1的單循環(huán)鏈表中,指針p指向表中某個(gè)結(jié)點(diǎn),若p->next->next=head,則()。A、p指向頭結(jié)點(diǎn)B、p指向尾結(jié)點(diǎn)C、?p的直接后繼是頭結(jié)點(diǎn)D、?p的直接后繼是尾結(jié)點(diǎn)答案：D78.一個(gè)容量為15的循環(huán)隊(duì)列中,隊(duì)尾指針是rear,隊(duì)頭是front,初始時(shí)均為0,且采用損失一個(gè)空間的原則。若頭指front=5,尾指針rear=9,則該循環(huán)隊(duì)列中共有()個(gè)元素。A、5B、9C、4D、14答案：C79.下面關(guān)于圖的敘述中,正確的是()。A、回路是簡(jiǎn)單路徑B、存儲(chǔ)稀疏圖用鄰接矩陣比鄰接表更節(jié)省存儲(chǔ)空間C、若有向圖中存在拓?fù)湫蛄?則該圖不存在回路D、若有向圖中存在拓?fù)湫蛄?則該圖可能存在回路答案：C80.設(shè)深度為k的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn),則這棵樹(shù)所含的結(jié)點(diǎn)數(shù)至少為()。A、k+1B、2k-1C、2kD、2k+1答案：B81.已知單鏈表的每個(gè)結(jié)點(diǎn)包括一人指針域next,它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。在一個(gè)單鏈表中,若刪除p所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)則執(zhí)行()。A、p->next=p->next->next;B、p=p->next;p->next=p->next->next;C、p=p->next->next;答案：A82.隊(duì)列的“先進(jìn)先出”特性是指()。A、最早插入隊(duì)列中的元素總是最后被刪除B、當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí),總是插入操作優(yōu)先C、每當(dāng)有刪除操作時(shí),總是要先做一次插入操作D、每次從隊(duì)列中刪除的總是最早插入的元素答案：D83.在一棵二又樹(shù)上第5層的結(jié)點(diǎn)數(shù)最多為()。A、8B、15C、16D、32答案：C84.算法分析的目的是分析算法的效率以求改進(jìn),算法分析的兩個(gè)主要方面是()。A、空間復(fù)雜性和時(shí)間復(fù)雜性B、正確性和簡(jiǎn)明性C、可讀性和文檔性D、數(shù)據(jù)復(fù)雜性和程序復(fù)雜性答案：A85.若用單鏈表來(lái)表示隊(duì)列,則應(yīng)該選用()。A、帶尾指針的非循環(huán)鏈表B、帶尾指針的循環(huán)鏈表C、帶頭指針的非循環(huán)鏈表D、帶頭指針的循環(huán)鏈表答案：B86.一棵二又樹(shù)前序遍歷序列是ABDGCFK,中序序列是DGBAFCK,則它的后序遍歷序列是()。A、CFKDBGB、GDBFKCAC、KCFAGDBD、ABCDFKG答案：B87.數(shù)組Q[n]用來(lái)表示一個(gè)循環(huán)隊(duì)列,為當(dāng)前隊(duì)列頭元素的前一位置,r為隊(duì)尾元素的位置,假定隊(duì)列中元素的個(gè)數(shù)小于n,計(jì)算隊(duì)列中元素的公式為()。A、r-fB、(n+f-r)%nC、n+r-fD、(n+r-f)%n答案：D88.在一個(gè)無(wú)向圖中,所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的()倍。A、1/2B、1C、2D、4答案：C89.對(duì)圖從頂點(diǎn)a出發(fā)進(jìn)行廣度優(yōu)先遍歷,則()是不可能得到的遍歷序列。

A、bcdefgB、acdbfgeC、abdcegfD、adcbgef答案：D90.在有向圖G的拓?fù)湫蛄兄?若頂點(diǎn)Vi在頂點(diǎn)Vj之前,則下列情形不可能出現(xiàn)的是()。A、G中有弧B、G中有一條從Vi到Vj的路徑C、G中沒(méi)有弧D、G中有一條從Vj到Vi的路徑答案：D91.以下說(shuō)法正確的是()。A、若一個(gè)樹(shù)葉是某二叉樹(shù)的前序遍歷序列中的最后一個(gè)結(jié)點(diǎn),則它必是該二又樹(shù)的后序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。B、若一個(gè)樹(shù)葉是某二叉樹(shù)的前序遍歷序列中的最后一個(gè)結(jié)點(diǎn),則它必是該二叉樹(shù)的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。C、若二叉樹(shù)中,有兩個(gè)孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)在中序遍歷序列中,它的后繼結(jié)點(diǎn)中必然有一個(gè)孩子結(jié)點(diǎn)。D、若二叉樹(shù)中,有一個(gè)孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)在中序遍歷序列中,它的后繼結(jié)點(diǎn)中沒(méi)有該孩子結(jié)點(diǎn)。答案：C92.在一棵二叉樹(shù)的二叉鏈表中，空指針域等于所有非空指針域相加()。A、-1B、0C、1D、2答案：D93.一棵樹(shù)的廣義表表示為a(b(c),de(g(h)),f,k)),則該樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)為()。A、2B、3C、4D、5答案：C94.該二叉樹(shù)對(duì)應(yīng)的森林有()棵樹(shù)。

A、1B、2C、3D、4答案：D95.在下圖中,J結(jié)點(diǎn)是()。

A、葉節(jié)點(diǎn)B、根結(jié)點(diǎn)但不是分支結(jié)點(diǎn)C、根結(jié)點(diǎn)也是分支結(jié)點(diǎn)D、分支結(jié)點(diǎn)但不是根結(jié)點(diǎn)答案：A96.在一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中,分支結(jié)點(diǎn)的最大編號(hào)為()。A、[2/n+1]B、[2/n-1]C、[2/n]D、[2/n]答案：D97.設(shè)森林F對(duì)應(yīng)的二叉樹(shù)有m個(gè)結(jié)點(diǎn),二叉樹(shù)的根節(jié)點(diǎn)的右子樹(shù)上結(jié)點(diǎn)個(gè)數(shù)為n,則森林F中第一個(gè)樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為()。A、m-nB、m-n-1C、m-n+1D、無(wú)法確定答案：A98.循環(huán)單鏈表的主要優(yōu)點(diǎn)是()。A、不再需要頭指針了B、已知某個(gè)結(jié)點(diǎn)的位置后,能夠容易找到他的直接前趨C、在進(jìn)行插入、刪除運(yùn)算時(shí),能更好的保證鏈表不斷開(kāi)D、從表中的任意結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表答案：D99.順序棧包含兩部分,數(shù)組data[10]和棧頂top,當(dāng)top值為()表示棧滿A、0B、9C、10D、-1答案：B100.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖,若采用鄰接表表示,則頂點(diǎn)表向量的大小和所有鄰接表中的結(jié)點(diǎn)總數(shù)分別是()。A、都是nB、都是n+eC、n和n+eD、n和2e答案：D101.在一個(gè)順序循環(huán)隊(duì)列中,隊(duì)尾指向隊(duì)尾元素的()位置。A、前一個(gè)B、后一個(gè)C、當(dāng)前D、最后答案：B102.線性表是具有n個(gè)()的有限序列。A、數(shù)據(jù)項(xiàng)B、數(shù)據(jù)元素C、表元素D、字符答案：B103.為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí),只有當(dāng)()時(shí),才產(chǎn)生上溢A、兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn)B、其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn)C、兩個(gè)棧的棧頂在?？臻g的某一位置相遇D、兩個(gè)棧均不空,且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底答案：C104.一棵完全二又樹(shù)按層次遍歷的序列為ABCDEFGHI則在前序遍歷中結(jié)點(diǎn)E的直接前驅(qū)為結(jié)點(diǎn)()。A、DB、FC、HD、I答案：D105.已知單鏈表的每個(gè)結(jié)點(diǎn)包括一個(gè)指針域next,它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。在一個(gè)單鏈表中,已知q指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn),若在q和p之間插入s結(jié)點(diǎn),則執(zhí)行()。A、s->next=p->next;p->next=s;B、p->next=s->next;s->next=p:C、q->next=s;s->next=p;D、p->next=s;s->next=q;答案：C106.在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題時(shí),通常設(shè)置個(gè)打印機(jī)數(shù)據(jù)緩沖區(qū),主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入該緩沖區(qū)打印機(jī)則從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個(gè)()結(jié)構(gòu)。A、棧B、隊(duì)列C、樹(shù)D、線性表答案：B107.已知單鏈表的每個(gè)結(jié)點(diǎn)包括一個(gè)指針域next,它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。不帶頭結(jié)點(diǎn)的單鏈表L為空的條件是()。A、L!=NULLB、L==NULLC、L->next==NULLD、L->next==L答案：B108.若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素,則采用()存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A、順序表B、單鏈表C、雙鏈表答案：A解析：D循環(huán)單鏈表109.向一個(gè)隊(duì)首指針為front、隊(duì)尾指針為rear的鏈隊(duì)列中插入一個(gè)s所指結(jié)點(diǎn)時(shí),其操作步驟為()。A、s->next=front;front->next=s;B、front=front->next;C、rear->next=s;rear=s;D、rear=s;s->next=rear;答案：C110.在一棵深度為k的完全二叉樹(shù)中,所含結(jié)點(diǎn)個(gè)數(shù)至少()。A、2K（2的K次方）B、2k+1（2的K次方+1）C、2k-1（不選C）D、2k-1（2的K次方-1）答案：D111.棧的插入和刪除操作在()進(jìn)行。A、棧底B、棧頂C、任意位置D、指定中間某位置答案：B112.用順序存儲(chǔ)的方法將完全二叉樹(shù)中所有結(jié)點(diǎn)逐層存放在數(shù)組R[]，根結(jié)點(diǎn)存入R[1],結(jié)點(diǎn)R[]若有左子樹(shù),則左子樹(shù)是結(jié)點(diǎn)()。A、R[2*i+I]B、R[2*i]C、R[i/2]D、R[2*i-1]答案：B113.當(dāng)定義一個(gè)結(jié)構(gòu)體變量時(shí),系統(tǒng)為它分配的內(nèi)存空間是()。A、結(jié)構(gòu)體中一個(gè)成員所需的內(nèi)存容量B、結(jié)構(gòu)體中第一個(gè)成員所需的內(nèi)存容量C、結(jié)構(gòu)體中占內(nèi)存容量最大者所需的容量D、結(jié)構(gòu)體中各成員所需內(nèi)存容量之和答案：D114.棧和隊(duì)列都是特殊的線性表,其特殊性在于()。A、它們具有一般線性表所沒(méi)有的邏輯特性B、它們的存儲(chǔ)結(jié)構(gòu)比較特殊C、對(duì)他們的使用方法做了限制D、它們比一般線性表更簡(jiǎn)單答案：C115.用鏈?zhǔn)酱鎯?chǔ)的棧在進(jìn)棧操作時(shí),將要進(jìn)棧的結(jié)點(diǎn)放在鏈表的()。A、頭部B、尾部C、中間D、用戶指定的位置答案：A116.任何一棵二又樹(shù)的葉結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對(duì)次序()。A、不發(fā)生變化B、發(fā)生變化C、某些樹(shù)中發(fā)生變化,某些樹(shù)中不發(fā)生變化D、沒(méi)有規(guī)律,無(wú)法確定答案：A117.如下圖說(shuō)是的二叉樹(shù)按中序線索化,則結(jié)點(diǎn)X的右指針和Y的左指針?lè)謩e指向()結(jié)點(diǎn)。

A、，DB、，CC、D，AD、C，A答案：C118.某順序棧sqStack,其成員包含兩部分:data[10]和top,分別代表數(shù)據(jù)和棧頂,則表示棧中第三個(gè)數(shù)據(jù)元素的是()。A、sqStack.data[2]B、sqStack.data[3]C、sqStack.data[4]D、無(wú)法表示答案：A119.鏈隊(duì)列的在建立時(shí),可以采用()將幾個(gè)元素鏈接起來(lái)建立單鏈表A、頭插法B、尾插法C、隨機(jī)插入法D、需要指定插入位置的方法答案：B120.一棵深度為6的滿二又樹(shù)一共有個(gè)()結(jié)點(diǎn)。A、31B、32C、63D、64答案：C121.利用數(shù)組a[]存儲(chǔ)一個(gè)順序棧時(shí),用top標(biāo)識(shí)棧頂指針(初值為-1)已知棧未滿,當(dāng)元素x進(jìn)行進(jìn)棧時(shí)執(zhí)行的操作是()。A、[--top]=x;B、a[top--]=x;C、a[++top]=x;D、a[top++]=x;答案：C122.以下鏈表結(jié)構(gòu)中,從當(dāng)前結(jié)點(diǎn)出發(fā)能夠訪問(wèn)到任一結(jié)點(diǎn)的是()。A、單向鏈表和雙向鏈表B、雙向鏈表和循環(huán)鏈表C、單向鏈表和循環(huán)鏈表D、單向鏈表、雙向鏈表和循環(huán)鏈表答案：B123.下面關(guān)于工程計(jì)劃的AOE網(wǎng)的敘述中,不正確的是()。A、關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B、任何一個(gè)關(guān)鍵活動(dòng)提前完成,那么整個(gè)工程將會(huì)提前完成C、所有的關(guān)鍵活動(dòng)都提前完成.那么整個(gè)工程將會(huì)提前完成D、某些關(guān)鍵活動(dòng)若提前完成,那么整個(gè)工程將會(huì)提前完答案：B124.雙向鏈表中有兩個(gè)指針域.link和rink分別指向前趨及后繼,設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn),在p的結(jié)點(diǎn)前插入一個(gè)指針g指向的結(jié)點(diǎn)操作是()。A、p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=q;B、p->llink=q;p->llink->rlink=q;q->rlink=p;q->llink=p->llink:C、q->rlink=p;q->llink=p->llink;p->llink->rlink=q;p->llink=q;D、q->llink=p->llink;q->rlink=p;p->llink=q;p->llink->rlink=q;答案：C125.最大容量為maxsize的循環(huán)隊(duì)列,隊(duì)尾指針是rear,隊(duì)頭是front,初始時(shí)均為0且采用損失一個(gè)空間的原則,則隊(duì)滿條件為()。A、(rear+1)%maxsize==(front+1)%maxsizeB、(front+1)%maxsize==rearC、(rear+1)%maxsize==frontD、rear==front答案：C126.有一份電文中共使用5個(gè)字符:a、b、c、d、e,它們的出現(xiàn)頻率依次為4、7、5、2、9,對(duì)應(yīng)的赫夫曼樹(shù)中字符a的赫夫曼編碼長(zhǎng)度為()。A、1B、2C、3D、4答案：C127.兩類存儲(chǔ)結(jié)構(gòu)為()。A、線性結(jié)構(gòu)和非線性結(jié)構(gòu)B、邏輯結(jié)構(gòu)和非邏輯結(jié)構(gòu)C、順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)D、邏輯結(jié)構(gòu)和物理結(jié)構(gòu)答案：C128.后綴表達(dá)式“45*32+-”的值為()。A、21B、17C、15D、5答案：C129.以下說(shuō)法錯(cuò)誤的是()。A、存在這樣的二叉樹(shù),對(duì)它采用任何次序遍歷其結(jié)點(diǎn)訪問(wèn)序列均相同B、普通二叉樹(shù)只能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)C、由樹(shù)轉(zhuǎn)換成二叉樹(shù),其根結(jié)點(diǎn)的右子樹(shù)總是空的D、二叉樹(shù)只有一棵子樹(shù)的情況下也要明確指出該子樹(shù)是左子樹(shù)還是右子樹(shù)答案：B130.分析以下程序段,其時(shí)間復(fù)雜度為T(mén)()=()。

For(i=0;i<n;i++)

For(j=0;j<i;j++)

A[i][j]=0;A、O(n)B、O(n2)C、O(n3)D、O(1)答案：B131.鏈棧與順序棧相比,有一個(gè)比較明顯的優(yōu)點(diǎn)()。A、插入操作更方便B、刪除操作更方便C、通常不會(huì)出現(xiàn)棧滿的情況D、不會(huì)出現(xiàn)?？盏那闆r答案：C132.某圖的鄰接矩陣如圖所示,若G為無(wú)向圖,則G中共有()條邊。

A、1B、2C、3D、4答案：B133.有一個(gè)結(jié)構(gòu)體及其變量定義如下:structdate{intyear;intmonth:intday;}birthday;此時(shí)要調(diào)用變量中的year,正確的書(shū)寫(xiě)格式是()。A、yearB、irthday.yearC、date.yearD、struct.year答案：B134.表達(dá)式a*(b+c)-d的后綴表達(dá)式是()。A、bcd*+-B、abc+*d-C、abc*+d-D、-+*abcd答案：B135.在定義數(shù)組inta[10]后,需要訪問(wèn)數(shù)組中第3個(gè)元素,正確的是()。A、[0]B、a[1]C、a[2]D、a[3]答案：C136.若長(zhǎng)度為n的線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),訪問(wèn)其第i個(gè)元素的算法時(shí)間復(fù)雜度為()。A、O(1)B、O(n)C、O(n2)D、O(log2n)答案：B137.無(wú)向圖G=(V.E),其中:V={a,b,c,d,e,f}E={(a,b),(a,e),(a,c),b,e),(c,f),(f,d)(e,d)},對(duì)該圖進(jìn)行深度優(yōu)先遍歷,得到的頂點(diǎn)序列正確的是()。A、,b,e,c,d,fB、A,c,f,e,b,dC、A,e,b,c,f,dD、A,e,d,f,c,b答案：D138.5、森林F中有三棵樹(shù),每棵樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)分別為n1,n2和n3,森林F轉(zhuǎn)換二叉樹(shù)后,根結(jié)點(diǎn)的右子樹(shù)上結(jié)點(diǎn)個(gè)數(shù)為()。A、n1B、n1+n2C、n2+n3D、n1+n2+n3答案：C判斷題1.在鏈隊(duì)列中,執(zhí)行出隊(duì)操作是在隊(duì)頭進(jìn)行的,因此不可能改變鏈尾指針的值。A、正確B、錯(cuò)誤答案：B2.棧和隊(duì)列都是線性表,只是在插入和刪除時(shí)受到了一些限制。A、正確B、錯(cuò)誤答案：A3.在帶頭節(jié)點(diǎn)的單循環(huán)鏈表中,任意節(jié)點(diǎn)中的指針域都不為空A、正確B、錯(cuò)誤答案：A4.在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相的元素在物理位置上不一定相鄰。A、正確B、錯(cuò)誤答案：A5.由于隊(duì)列在程序調(diào)用時(shí)必不可少,因此遞歸離不開(kāi)隊(duì)列。A、正確B、錯(cuò)誤答案：B6.對(duì)任意一個(gè)圖,從某頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先遍歷,可訪問(wèn)圖的所有頂點(diǎn)。A、正確B、錯(cuò)誤答案：B7.在n個(gè)頂點(diǎn)的無(wú)向圖中,若邊數(shù)大于n-1,則該圖是連通圖。A、正確B、錯(cuò)誤答案：B8.一個(gè)棧的輸入序列是12345.則棧的輸出序列不可能是12345A、正確B、錯(cuò)誤答案：B9.樹(shù)中任意結(jié)點(diǎn)的子樹(shù)不必是有序的。A、正確B、錯(cuò)誤答案：A10.用棧這種數(shù)據(jù)結(jié)構(gòu)可以實(shí)現(xiàn)隊(duì)列這種數(shù)據(jù)