大學(xué)數(shù)據(jù)結(jié)構(gòu)期末考試試題(有答案)

1、“數(shù)據(jù)結(jié)構(gòu)”期末考試試題一、單選題(每小題2分，共12分)在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行()。HL=psp一next=HLpnext=HL；HL=p3pnext=Hl；p=HL；pnext=HLnext;HLnext=p；n個頂點的強(qiáng)連通圖中至少含有()。A.nl條有向邊B.n條有向邊C.n(n1)/2條有向邊D.n(n1)條有向邊從一棵二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為()。A.O(1)B.O(n)C.O(1Ogzn)D.O(n2)由權(quán)值分別為3，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為()。A.24B.48C.72D.53當(dāng)

2、一個作為實際傳遞的對象占用的存儲空間較大并可能需要修改時，應(yīng)最好把它說明為()參數(shù)，以節(jié)省參數(shù)值的傳輸時間和存儲參數(shù)的空間。A.整形B.引用型C.指針型D.常值引用型6向一個長度為n的順序表中插人一個新元素的平均時間復(fù)雜度為()。A.O(n)B.O(1)C.O(n2)D.O(10g2n)二、填空題(每空1分，共28分)數(shù)據(jù)的存儲結(jié)構(gòu)被分為、和四種。在廣義表的存儲結(jié)構(gòu)中，單元素結(jié)點與表元素結(jié)點有一個域?qū)?yīng)不同，各自分別為域和域。中綴表達(dá)式3十x*(2.4/56)所對應(yīng)的后綴表達(dá)式為。4在一棵高度為h的3叉樹中，最多含有結(jié)點。5假定一棵二叉樹的結(jié)點數(shù)為18,則它的最小深度為，最大深度為在一棵二叉搜

3、索樹中，每個分支結(jié)點的左子樹上所有結(jié)點的值一定該結(jié)點的值，右子樹上所有結(jié)點的值一定該結(jié)點的值。當(dāng)向一個小根堆插入一個具有最小值的元素時,該元素需要逐層調(diào)整,直到被調(diào)整到位置為止。表示圖的三種存儲結(jié)構(gòu)為、和。對用鄰接矩陣表示的具有n個頂點和e條邊的圖進(jìn)行任一種遍歷時，其時間復(fù)雜度為一一，對用鄰接表表示的圖進(jìn)行任一種遍歷時,其時間復(fù)雜度為。從有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素時，其查找長度分別為和假定對長度n=144的線性表進(jìn)行索引順序查找，并假定每個子表的長度均為，則進(jìn)行索引順序查找的平均查找長度為一一，時間復(fù)雜度為12一棵B樹中的所有葉子結(jié)點均

4、處在上。每次從無序表中順序取出一個元素,把這插入到有序表中的適當(dāng)位置,此種排序方法叫做排序；每次從無序表中挑選出一個最小或最大元素,把它交換到有序表的一端,此種排序方法叫做排序?？焖倥判蛟诤蹙闆r下的時間復(fù)雜度為,最壞情況下的時間復(fù)雜度為。三、運(yùn)算題(每小題6分,共24分)1假定一棵二叉樹廣義表表示為a(b(c,d),c(,8),分別寫出對它進(jìn)行先序、中序、后序和后序遍歷的結(jié)果。先序：中序；后序：2已知一個帶權(quán)圖的頂點集V和邊集G分別為：V=0,1,2,3,4,5；E=(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(4,5)10,則求出該

5、圖的最小生成樹的權(quán)。最小生成樹的權(quán)；假定一組記錄的排序碼為(46,79,56,38,40,84,50,42),則利用堆排序方法建立的初始堆為。有7個帶權(quán)結(jié)點,其權(quán)值分別為3,7,8,2,6,10,14,試以它們?yōu)槿~子結(jié)點生成一棵哈夫曼樹,求出該樹的帶權(quán)路徑長度、高度、雙分支結(jié)點數(shù)。帶權(quán)路徑長度：高度：雙分支結(jié)點數(shù)：。四、閱讀算法,回答問題(每小題8分,共16分)VOldAC(List&L)InitList(L)；InsertRear(L;25)；InsertFront(L，50)；IntaL4=5,8,12,15,36;for(inti=0;i5;i+)if(ai%2=0)InsertFron

6、t(L,ai)；elselnsertRear(L,ai)；該算法被調(diào)用執(zhí)行后，得到的線性表L為：2voidAG(Queue&Q)InitQueue(Q)；inta5=6,12,5,15,8；for(inti=0;i5;i+)QInsert(Q,ai)；QInsert(Q,QDelete(Q)；QInsert(Q,20)；QInsert(Q,QDelete(Q)十16)；while(!QueueEmpty(Q)coutQDelete(Q)”；該算法被調(diào)用后得到的輸出結(jié)果為：五、算法填空,在畫有橫線的地方填寫合適的內(nèi)容(每小題6分,共12分)1從一維數(shù)組An)中二分查找關(guān)鍵字為K的元素的遞歸算法，

7、若查找成功則返回對應(yīng)元素的下標(biāo)，否則返回一1。IntBinsch(ElemTypeA,Intlow,inthigh,KeyTypeK)if(low=high)intmid=(low+high)/2；if(K=Amid.key)；elseif(KAmid.key)；else；elsereturnl；已知二叉樹中的結(jié)點類型BinTreeNode定義為：structBinTreeNodeElemTypedata；BinTreeNode*left,*right；其中data為結(jié)點值域，left和right分別為指向左、右子女結(jié)點的指針域。下面函數(shù)的功能是返回二叉樹BT中值為x的結(jié)點所在的層號,請在劃有

8、橫線的地方填寫合適內(nèi)容。IntNodeLevel(BinTreeNode*BT,ElemTypeX)if(BT：=NULL)return0；/空樹的層號為0elseif(BTdata=X)return1;/根結(jié)點的層號為1/向子樹中查找x結(jié)點elseintcl=NodeLevel(BTleft,X)；if(cl=1)returncl+1;intc2=；if；/若樹中不存在X結(jié)點則返回。elsereturn0；六、編寫算法(8分)按所給函數(shù)聲明編寫一個算法，從表頭指針為HL的單鏈表中查找出具有最大值的結(jié)點，該最大值由函數(shù)返回，若單鏈表為空則中止運(yùn)行。EIemTypeMaxValue(LNOde*

9、HL);數(shù)據(jù)結(jié)構(gòu)”期末考試試題答案一、單選題(每小題2分,共12分)評分標(biāo)準(zhǔn)；選對者得2分,否則不得分。6.A散列結(jié)構(gòu)(次序無先后)B2.B6.A散列結(jié)構(gòu)(次序無先后)二、填空題(每空1分,共28分)順序結(jié)構(gòu)鏈接結(jié)構(gòu)索引結(jié)構(gòu)值(或data)子表指針(或sublist)33x2456一*十(3h1)/2TOC o 1-5 h z518小于大于(或大于等于)向上堆頂鄰接矩陣鄰接表邊集數(shù)組(次序無先后)9.O(n2)O(e)10.1311.13O()同一層插人選擇14.O(nlogn)O(n)22三、運(yùn)算題(每小題6分，共24分)先序：a,b,c,d,e,f,e/2分中序：c,b,d,a,f,8,e

10、/2分后序：c,d,b,e,f,e,a/2分TOC o 1-5 h z最小生成樹的權(quán)：31/6分(84,79,56,42,40,46,50,38)/6分帶權(quán)路徑長度：131/3分高度：5/2分雙分支結(jié)點數(shù)：6/1分四、閱讀算法,回答問題(每小題8分,共16分)評分標(biāo)準(zhǔn)：每小題正確得8分,出現(xiàn)一處錯誤扣4分,兩處及以上錯誤不得分(36,12,8,50,25,5,15)2.515862028五、算法填空,在畫有橫線的地方填寫合適的內(nèi)容(每小題6分,共12分)feturnmid/2分returnBinsch(A,low,mid一1,K)/2分returnBmsch(A,mid+1,high,K)/2

11、分NodeLevel(BTright,X)/3分(c2=1)returnc2十1/3分六、編寫算法(8分)評分標(biāo)準(zhǔn)：請參考語句后的注釋,或根據(jù)情況酌情給分。ElemTypeMaxValue(LNodeO*HL。)if(HL=NUlL)/2分cerrLinkedllstisempty!”data；/3分LNOde*p=HInext；/4分while(P!：NULL)/7分if(maxdata；p=pnext；returnmax；/8分?jǐn)?shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料一、填空題數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的一以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D,R),其中D是的有限集

12、合，R是D上的_有限集合。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)一、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算這三個方面的內(nèi)容。數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。在線性結(jié)構(gòu)中，第一個結(jié)點一沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點；最后一個結(jié)點一后續(xù)結(jié)點，其余每個結(jié)點有且只有1個后續(xù)結(jié)點。在樹形結(jié)構(gòu)中，樹根結(jié)點沒有前驅(qū)一結(jié)點，其余每個結(jié)點有且只有一丄一個前驅(qū)結(jié)點；葉子結(jié)點沒有后續(xù)結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點數(shù)可以任意多個。在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以任意多個數(shù)據(jù)的存儲

13、結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別是順序、鏈?zhǔn)?、索引和散列。?shù)據(jù)的運(yùn)算最常用的有5種，它們分別是插入、刪除、修改、査找、排序。一個算法的效率可分為一時間效率和空間效率。在順序表中插入或刪除一個元素，需要平均移動表中一半元素,具體移動的元素個數(shù)與表長和該元素在表中的位置有關(guān)。線性表中結(jié)點的集合是有限的，結(jié)點間的關(guān)系是一一對一的。向一個長度為n的向量的第i個元素（1WiWn+1）之前插入一個元素時，需向后移動一個元素。向一個長度為n的向量中刪除第i個元素（1WiWn）時，需向前移動Z一個元素。在順序表中訪問任意一結(jié)點的時間復(fù)雜度均為-0（1）,因此，順序表也稱為隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu)。17順序表

14、中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置衛(wèi)一定相鄰。在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置由其直接前驅(qū)結(jié)點的鏈域的值指示。在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p,需找到它的前驅(qū)結(jié)點的地址，其時間復(fù)雜度為向量、棧和隊列都是-線性一結(jié)構(gòu)，可以在向量的任何位置插入和刪除元素；對于棧只能在棧頂一插入和刪除元素；對于隊列只能在一隊屋一插入和隊首刪除元素。棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為棧頂。不允許插入和刪除運(yùn)算的一端稱為一棧底。隊列是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。23不包含任何字符（長度為0）的串稱為空串；

15、一由一個或多個空格（僅由空格符）組成的串為空白串。子串的定位運(yùn)算稱為串的模式匹配；被匹配的主串稱為目標(biāo)串，子串一為模式。假設(shè)有二維數(shù)組A，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存儲位置（基地址）為1000，則6X8數(shù)組A的體積（存儲量）為288-B；末尾元素A57的第一個字節(jié)地址為1282;若按行存儲時，元素A】4的第一個字節(jié)地址為；若按列存儲時，元素A的第一個字節(jié)地址為（6X7+4）X6+1000）=1276。47由3個結(jié)點所構(gòu)成的二叉樹有5種形態(tài)?？蒙疃葹?的滿二叉樹有中叮0+叮nT=31一個分支結(jié)點和232個葉子。注：滿二叉樹沒有度為1的結(jié)點，所以分支結(jié)點數(shù)就是二度

16、結(jié)點數(shù)。一棵具有257個結(jié)點的完全二叉樹，它的深度為一9。（注：用Llog（n）+1=L8.xx+1=92設(shè)一棵完全二叉樹有700個結(jié)點，則共有_350_個葉子結(jié)點。答：最快方法：用葉子數(shù)=n/2=350設(shè)一棵完全二叉樹具有1000個結(jié)點，則此完全二叉樹有50個葉子結(jié)點，有99一個度為2的結(jié)點，有一1_個結(jié)點只有非空左子樹，有Q個結(jié)點只有非空右子樹。答：最快方法：用葉子數(shù)=n/2=500，n=n-1=499。另外，最后一結(jié)點為2i屬于左葉子，右葉子是空的，所以有1個非空20左子樹。完全二叉樹的特點決定不可能有左空右不空的情況，所以非空右子樹數(shù)=0.31在數(shù)據(jù)的存放無規(guī)律而言的線性表中進(jìn)行檢索的

17、最佳方法是順序査找（線性査找）。線性有序表（a，a，a，a）是從小到大排列的，對一個給定的值k，用二分法檢索表中與k相等的元素，在査找不成123256功的情況下，最多需要檢索8次。設(shè)有100個結(jié)點，用二分法査找時，最大比較次數(shù)是。假設(shè)在有序線性表a20上進(jìn)行折半査找，則比較一次査找成功的結(jié)點數(shù)為1；比較兩次査找成功的結(jié)點數(shù)為_2一；比較四次査找成功的結(jié)點數(shù)為8一；平均査找長度為口。解：顯然，平均査找長度=0（1og2n）top0B.ST-top=0C.ST-topm0D.ST-top=m0(C)18.在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的倍。A.1/2B.1C.2D.4(B)19.在一個

18、有向圖中，所有頂點的入度之和等于所有頂點的出度之和的倍。D.4D.112D.112TOC o 1-5 h z1/2B.D.4D.112D.112(B)20.有8個結(jié)點的無向圖最多有條邊。14B.28C.56(C)21.有8個結(jié)點的有向完全圖有條邊。14B.28C.56(B)22在表長為n的鏈表中進(jìn)行線性查找，它的平均查找長度為ASL=n;B.ASL=(n+l)/2;C.ASL=*n+l;D.ASLlog2(n+l)l(A)23.折半查找有序表(4,6,10,12,20,30,50,70,88,100)。若查找表中元素58,則它將依次與表中比較大小,查找結(jié)果是失敗。20,70,30,50B.30

19、,88,70,50C.20,50D.30,88,50(C)24.對22個記錄的有序表作折半查找，當(dāng)查找失敗時，至少需要比較次關(guān)鍵字。3B.4C.5D.6(A)25.鏈表適用于查找順序B二分法C.順序，也能二分法D.隨機(jī)數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)題一、選擇題。TOC o 1-5 h z在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為一C。A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計算機(jī)內(nèi)存中的表示是指一A。A.數(shù)據(jù)的存儲結(jié)構(gòu)B.數(shù)據(jù)結(jié)構(gòu)C.數(shù)據(jù)的邏輯結(jié)構(gòu)D.數(shù)據(jù)元素之間的關(guān)系3在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的一A一結(jié)構(gòu)。A.邏輯B.存儲C.

20、邏輯和存儲D.物理4在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲C。A.數(shù)據(jù)的處理方法B.數(shù)據(jù)元素的類型1313鏈表不具備的特點是AC.數(shù)據(jù)元素之間的關(guān)系D.數(shù)據(jù)的存儲方法5在決定選取何種存儲結(jié)構(gòu)時，一般不考慮一。A.各結(jié)點的值如何B.結(jié)點個數(shù)的多少C.對數(shù)據(jù)有哪些運(yùn)算D.所用的編程語言實現(xiàn)這種結(jié)構(gòu)是否方便。6以下說法正確的是。數(shù)據(jù)項是數(shù)據(jù)的基本單位數(shù)據(jù)元素是數(shù)據(jù)的最小單位數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項的集合D一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)7算法分析的目的是L，算法分析的兩個主要方面是A.找出數(shù)據(jù)結(jié)構(gòu)的合理性C.分析算法的效率以求改進(jìn)A.空間復(fù)雜度和時間復(fù)雜度C.可讀性和文

21、檔性研究算法中的輸入和輸出的關(guān)系分析算法的易讀性和文檔性正確性和簡明性數(shù)據(jù)復(fù)雜性和程序復(fù)雜性8下面程序段的時間復(fù)雜度是s=0;for(I=0;in;i+)for(j=0;jn;j+)s+=Bij;sum=s;9下面程序段的時間復(fù)雜度是。for(i=0;in;i+)for(j=0;jm;j+)=0;10.下面程序段的時間復(fù)雜度是i=0；while(inext=NULLC.head-next=headDhead!=NULL15帶頭結(jié)點的單鏈表head為空的判定條件是一B一。A.head=NULLBhead-next=NULLC.head-next=headDhead!=NULL16.若某表最常用的

22、操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點，則采用D一存儲方式最節(jié)省運(yùn)算時間。A.單鏈表B.給出表頭指針的單循環(huán)鏈表C.雙鏈表D.帶頭結(jié)點的雙循環(huán)鏈表17需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結(jié)構(gòu)是B。A.單鏈表B.靜態(tài)鏈表C.線性鏈表D.順序存儲結(jié)構(gòu)18.非空的循環(huán)單鏈表head的尾結(jié)點（由p所指向）滿足C。A.p-next=NULLB.p=NULLC.p-next=headD.p=head19在循環(huán)雙鏈表的p所指的結(jié)點之前插入s所指結(jié)點的操作是一D。p-prior=s；s-next=p；p-prior-next=s；s-prior=p-priorp-prio

23、r=s；p-prior-next=s；s-next=p；s-prior=p-priors-next=p；s-prior=p-prior；p-prior=s；p-prior-next=ss-next=p；s-prior=p-prior；p-prior-next=s；p-prior=s20如果最常用的操作是取第i個結(jié)點及其前驅(qū)，則采用存儲方式最節(jié)省時間。A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.順序表21在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復(fù)雜度是L。A.O（1）B.O（n）C.O（n2）D.O（nlog2n）22在一個長度為n（n1）的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行

24、一操作與鏈表的長度有關(guān)。刪除單鏈表中的第一個元素刪除單鏈表中的最后一個元素在單鏈表第一個元素前插入一個新元素在單鏈表最后一個元素后插入一個新元素23與單鏈表相比，雙鏈表的優(yōu)點之一是D。插入、刪除操作更簡單可以進(jìn)行隨機(jī)訪問可以省略表頭指針或表尾指針順序訪問相鄰結(jié)點更靈活24如果對線性表的操作只有兩種，即刪除第一個元素，在最后一個元素的后面插入新元素，則最好使用B只有表頭指針沒有表尾指針的循環(huán)單鏈表只有表尾指針沒有表頭指針的循環(huán)單鏈表非循環(huán)雙鏈表循環(huán)雙鏈表25.在長度為n的順序表的第i個位置上插入一個元素(1WiWn+1),元素的移動次數(shù)為：A。A.n-i+1B.n-iC.iD.i-126對于只在

25、表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為C。A.順序表B.用頭指針表示的循環(huán)單鏈表C.用尾指針表示的循環(huán)單鏈表D.單鏈表27下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？C。A插入運(yùn)算方便B可方便地用于各種邏輯結(jié)構(gòu)的存儲表示C存儲密度大D刪除運(yùn)算方便28下面關(guān)于線性表的敘述中，錯誤的是哪一個？B。A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B線性表采用順序存儲，便于進(jìn)行插入和刪除操作。C線性表采用鏈?zhǔn)酱鎯?，不必占用一片連續(xù)的存儲單元D線性表采用鏈?zhǔn)酱鎯?，便于進(jìn)行插入和刪除操作。29.線性表是具有n個B的有限序列。A.字符B.數(shù)據(jù)元素C.數(shù)據(jù)項D.表元素30在n個結(jié)點的線性表的數(shù)組實現(xiàn)中，算

26、法的時間復(fù)雜度是0(1)的操作是。訪問第i(1=i=n)個結(jié)點和求第i個結(jié)點的直接前驅(qū)(1i=n)在第i(1=i=n)個結(jié)點后插入一個新結(jié)點刪除第i(1=i=n)個結(jié)點以上都不對TOC o 1-5 h z31若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為。A.0(0)B.0(1)C.0(n)D.0(n2)32對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復(fù)雜度為一C。A.0(n)0(n)B.0(n)0(1)C.0(1)0(n)D.0(1)0(1)33線性表(a1,a2,an)以鏈?zhǔn)椒绞酱鎯?，訪問第i位置元素的時間復(fù)雜度為一C。A.0(0)B.0(1)

27、C.0(n)D.0(n2)34單鏈表中，增加一個頭結(jié)點的目的是為了。A.使單鏈表至少有一個結(jié)點B.標(biāo)識表結(jié)點中首結(jié)點的位置C.方面運(yùn)算的實現(xiàn)D.說明單鏈表是線性表的鏈?zhǔn)酱鎯?5在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是B。A.p-next=s；s-next=p-nextB.s-next=p-next；p-next=s;Cp-next=s；p-next=s-nextDp-next=s-next；p-next=sCp-next=s；p-next=s-nextDp-next=s-next；p-next=sTOC o 1-5 h z36線性表的順序存儲結(jié)構(gòu)是一種_。隨機(jī)存取的存儲結(jié)構(gòu)B

28、.順序存取的存儲結(jié)構(gòu)C.索引存取的存儲結(jié)構(gòu)D.Hash存取的存儲結(jié)構(gòu)37棧的特點是B一，隊列的特點是。先進(jìn)先出B.先進(jìn)后出棧和隊列的共同點是C。A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點處插入和刪除元素D.沒有共同點一個棧的進(jìn)棧序列是a,b,c,d,e,則棧的不可能的輸出序列是CA.edcbaB.decbaC.dceabA.edcbaB.decbaC.dceabD.abcde40設(shè)有一個棧，元素依次進(jìn)棧的順序為A、B、C、D、E。下列C是不可能的出棧序列。A.A,B,C,D,EB.B,C,D,E,AC.E,A,B,C,DD.E,D,C,B,A41以下B不是隊列的基本運(yùn)算？A.從隊尾插入一

29、個新元素B.從隊列中刪除第i個元素C.判斷一個隊列是否為空D.讀取隊頭元素的值若已知一個棧的進(jìn)棧序列是1,2,3,n,其輸出序列為pl,p2,p3,，pn,若p1=n，則pi為C。A.iB.niC.ni+1D.不確定判定一個順序棧st（最多元素為MaxSize）為空的條件是B。A.st-top!=-1B.st-top=-1C.st-top!=MaxSizeD.st-top=MaxSize判定一個順序棧st（最多元素為MaxSize）為滿的條件是一D。A.st-top!=-1B.st-top=-1C.st-top!=MaxSizeD.st-top=MaxSize一個隊列的入隊序列是1,2,3,4

30、,則隊列的輸出序列是一。A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,146判定一個循環(huán)隊列qu（最多元素為MaxSize）為空的條件是一。A.qu-rear-qu-front=MaxSizeB.qu-rear-qu-frontT=MaxSizeC.qu-rear=qu-frontD.qu-rear=qu-front-147在循環(huán)隊列中，若front與rear分別表示對頭元素和隊尾元素的位置，則判斷循環(huán)隊列空的條件是CA.front=rear+1B.rear=front+1C.front=rearD.front=048向一個棧頂指針為h的帶頭結(jié)點的鏈棧中插入指針s所指的

31、結(jié)點時，應(yīng)執(zhí)行操作。Ah-next=sBs-next=hCs-next=h;h=s;Ds-next=h-next;h-next=s;49輸入序列為ABC,可以變?yōu)镃BA時，經(jīng)過的棧操作為一。Apush，pop，push，pop，push，popBpush，push，push，pop，pop，popCpush,push,pop,pop,push,popDpush,pop,push,push,pop,popTOC o 1-5 h z50若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V1m,topl、top2分別代表第1和第2個棧的棧頂，棧1的底在V1,棧2的底在Vm，則棧滿的條件是。A.|top2-to

32、p1|=0B.top1+1=top2C.top1+top2=mD.top1=top251設(shè)計一個判別表達(dá)式中左、右括號是否配對出現(xiàn)的算法，采用數(shù)據(jù)結(jié)構(gòu)最佳。A.線性表的順序存儲結(jié)構(gòu)B.隊列C.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)D.棧52.允許對隊列進(jìn)行的操作有D。A.對隊列中的元素排序B.取出最近進(jìn)隊的元素C.在隊頭元素之前插入元素D.刪除隊頭元素53對于循環(huán)隊列D。A.無法判斷隊列是否為空B.無法判斷隊列是否為滿C.隊列不可能滿D.以上說法都不對54若用一個大小為6的數(shù)值來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為B。

33、A.1和5B.2和4C.4和2D.5和155隊列的“先進(jìn)先出”特性是指_D。最早插入隊列中的元素總是最后被刪除當(dāng)同時進(jìn)行插入、刪除操作時，總是插入操作優(yōu)先每當(dāng)有刪除操作時，總是要先做一次插入操作每次從隊列中刪除的總是最早插入的元素56和順序棧相比，鏈棧有一個比較明顯的優(yōu)勢是。A.通常不會出現(xiàn)棧滿的情況B.通常不會出現(xiàn)?？盏那闆rC.插入操作更容易實現(xiàn)D.刪除操作更容易實現(xiàn)57用不帶頭結(jié)點的單鏈表存儲隊列，其頭指針指向隊頭結(jié)點，尾指針指向隊尾結(jié)點，則在進(jìn)行出隊操作時CA.僅修改隊頭指針B.僅修改隊尾指針C.隊頭、隊尾指針都可能要修改D.隊頭、隊尾指針都要修改58.若串S=software，其子串的

34、數(shù)目是一B一。A.8B.37C.36D.959串的長度是指一。A.串中所含不同字母的個數(shù)B.串中所含字符的個數(shù)C.串中所含不同字符的個數(shù)D.串中所含非空格字符的個數(shù)TOC o 1-5 h z60串是一種特殊的線性表，其特殊性體現(xiàn)在一。A.可以順序存儲B.數(shù)據(jù)元素是一個字符C.可以鏈?zhǔn)酱鎯.數(shù)據(jù)元素可以是多個字符61.設(shè)有兩個串p和q,求q在P中首次出現(xiàn)的位置的運(yùn)算稱為B。A.連接B.模式匹配C.求子串D.求串長62數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1到10,從首地址SA開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A85的起始地址為。A.SA141B.SA144C

35、.SA222D.SA22563數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1到10,從首地址SA開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A58的起始地址為C。A.SA141B.SA180C.SA222D.SA225若聲明一個浮點數(shù)數(shù)組如下：froataverage=newfloat30;假設(shè)該數(shù)組的內(nèi)存起始位置為200,average15的內(nèi)存地址是。TOC o 1-5 h zA.214B.215C.260D.256設(shè)二維數(shù)組A1m,1n按行存儲在數(shù)組B中，則二維數(shù)組元素Ai,j在一維數(shù)組B中的下標(biāo)為A。A.n*(i-1)+jB.n*(i-1)+j-1C.i*(j-1)

36、D.j*m+i-1有一個100X90的稀疏矩陣，非0元素有10,設(shè)每個整型數(shù)占2個字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是B。A.20B.66C.18000D.3367數(shù)組A04,-1-3,5中含有的元素個數(shù)是。A.55B.45C.36D.1668對矩陣進(jìn)行壓縮存儲是為了D。A.方便運(yùn)算B.方便存儲C.提高運(yùn)算速度D.減少存儲空間69設(shè)有一個10階的對稱矩陣A,采用壓縮存儲方式，以行序為主存儲，a為第一個元素，其存儲地址為1,每個元素占1個1，1地址空間，則a的地址為B_。8,5A.13B.33C.18D.4070稀疏矩陣一般的壓縮存儲方式有兩種，即。A.二維數(shù)組和三維數(shù)組B.三元組和散列

37、C.三元組和十字鏈表D.散列和十字鏈表71樹最適合用來表示一。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)72深度為5的二叉樹至多有一C一個結(jié)點。A.16B.32C.31C.1073對一個滿二叉樹，m個葉子，n個結(jié)點，深度為h,則_An=h+mBh+m=2nCm=h-1Dn=2h-174任何一棵二叉樹的葉子結(jié)點在前序、中序和后序遍歷序列中的相對次序一A一。A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對75在線索化樹中，每個結(jié)點必須設(shè)置一個標(biāo)志來說明它的左、右鏈指向的是樹結(jié)構(gòu)信息，還是線索化信息，若0標(biāo)識樹結(jié)構(gòu)信息，1標(biāo)識線索，對應(yīng)葉結(jié)點的左右

38、鏈域，應(yīng)標(biāo)識為_-D_。A.00B.01C.10D.1176在下述論述中，正確的是D一。只有一個結(jié)點的二叉樹的度為0;二叉樹的度為2；二叉樹的左右子樹可任意交換；深度為K的順序二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。A.B.C.D.77設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p，p的右子樹的結(jié)點個數(shù)為n，森林F中第一棵樹的結(jié)點的個數(shù)是A。A.m-nB.m-n-1C.n+1D.不能確定78若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點的個數(shù)是B。A.9B.11C.15D.不能確定79具有10個葉子結(jié)點的二叉樹中有一B一個度為2的結(jié)點。TOC o 1-5 h z

39、A.8B.9C.10D.1180在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的倍。A.1/2B1C2D481在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的倍。A.1/2B1C2D482某二叉樹結(jié)點的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結(jié)點數(shù)目為：C一A.3B.2C.4D.583已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為DA.-A+B*C/DE-A+B*CD/EC-A.-A+B*C/DE-A+B*CD/EC-+*ABC/DE-+A*BC/DEaefb則可能得到的一種頂點歹Uaefb則可能得到的一種頂點歹U為

40、A；A.a，b，e，c，d，fB.a，c，f，e，b，dC.a，e，b，c，f，d，D.a，e，d，f，c，bA.a，b，c，e，d，fB.a，b，c，e，f，dC.a，e，b，c，f，d，D.a，c，f，d，e，b84已知一個圖，如圖所示，若從頂點a出發(fā)按深度搜索法進(jìn)行遍歷,序列為_D_；按廣度搜索法進(jìn)行遍歷，則可能得到的一種頂點序85采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的_A。A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷86采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的亠_D_。A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷87具有n個結(jié)點的連通圖至少有一A一條邊。A

41、.n-1B.nC.n（n-1）/2D.2n88.廣義表（a）,a）的表頭是-C，表尾是C。A.aB（）C（a）D（a）89廣義表（a）的表頭是-L,表尾是B。A.aB（）C（a）D（a）90順序查找法適合于存儲結(jié)構(gòu)為一的線性表。A散列存儲B順序存儲或鏈?zhǔn)酱鎯壓縮存儲D索引存儲91.對線性表進(jìn)行折半查找時，要求線性表必須。A以順序方式存儲B以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列C以鏈?zhǔn)椒绞酱鎯以鏈?zhǔn)椒绞酱鎯?，且結(jié)點按關(guān)鍵字有序排列92采用折半查找法查找長度為n的線性表時，每個元素的平均查找長度為_D_。AO（n2）BO（nlogn）CO（n）DO（logn）2293有一個有序表為1,3,9,

42、12,32,41,45,62,75,77,82,95,100,當(dāng)折半查找值為82的結(jié)點時，_C次比較后查找成功。TOC o 1-5 h zA.11B5C4D8二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法BA正確B錯誤下面關(guān)于B樹和B+樹的敘述中，不正確的結(jié)論是A。AB樹和B+樹都能有效的支持順序查找BB樹和B+樹都能有效的支持隨機(jī)查找CB樹和B+樹都是平衡的多叉樹DB樹和B+樹都可用于文件索引結(jié)構(gòu)96以下說法錯誤的是B。散列法存儲的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲地址散列表的結(jié)點中只包含數(shù)據(jù)元素自身的信息，不包含指針。負(fù)載因子是散列表的一個重要參

43、數(shù)，它反映了散列表的飽滿程度。散列表的查找效率主要取決于散列表構(gòu)造時選取的散列函數(shù)和處理沖突的方法。97查找效率最高的二叉排序樹是。所有結(jié)點的左子樹都為空的二叉排序樹。所有結(jié)點的右子樹都為空的二叉排序樹。平衡二叉樹。沒有左子樹的二叉排序樹。98排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為C。A.希爾排序B。冒泡排序C插入排序D。選擇排序99在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是A.希爾排序B.冒泡排序C.直接插入排序D.直接選擇排序堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列D是一個堆。A.94,31,53,

44、23,16,72B.94,53,31,72,16,2316,53,23,94,31,72D.16,31,23,94,53,72堆排序是一種一排序。A.插入B.選擇C.交換D.歸并D一在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高。A.順序查找B.折半查找C.分塊查找D.插入直接選擇排序的時間復(fù)雜度為D。(n為元素個數(shù))A.O(n)B.O(logn)C.O(nlogn)D.O(n2)22二、填空題。1數(shù)據(jù)邏輯結(jié)構(gòu)包括一、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)三種類型，樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱一。2數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)4種。3在線性結(jié)構(gòu)中，第一個結(jié)點_沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有個前驅(qū)結(jié)

45、點；最后一個結(jié)點沒有后續(xù)結(jié)點，其余每個結(jié)點有且只有1個后續(xù)結(jié)點。4線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。5在樹形結(jié)構(gòu)中，樹根結(jié)點沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有個前驅(qū)結(jié)點；葉子結(jié)點沒有后續(xù)結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點可以仟意多個。6數(shù)據(jù)結(jié)構(gòu)的基本存儲方法是_、鏈?zhǔn)絖、一和散列存儲。7衡量一個算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和時間復(fù)雜度與空間復(fù)雜度。8評估一個算法的優(yōu)劣，通常從_和_兩個方面考察。9算法的5個重要特性是_、確定性、_、輸入和輸出。在一個長度為n的順序表中刪除第i個元素時，需向前移動個元素。在單鏈表中，要刪除

46、某一指定的結(jié)點，必須找到該結(jié)點的結(jié)點。在雙鏈表中，每個結(jié)點有兩個指針域，一個指向前驅(qū)結(jié)點，另一個指向后繼結(jié)點。13在順序表中插入或刪除一個數(shù)據(jù)元素，需要平均移動亠個數(shù)據(jù)元素，移動數(shù)據(jù)元素的個數(shù)與佳置有關(guān)。當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表的元素是，應(yīng)采用存儲結(jié)構(gòu)。15根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成單鏈表一和雙鏈表。16順序存儲結(jié)構(gòu)是通過下標(biāo)表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過針表示元素之間的關(guān)系的。帶頭結(jié)點的循環(huán)鏈表L中只有一個元素結(jié)點的條件是_L-next-next=【,。棧是限定僅在表尾進(jìn)行插入或刪除操

47、作的線性表，其運(yùn)算遵循后講先出的原則。19空串是零個字符的串，其長度等于零?？瞻状怯梢粋€或多個空格字符組成的串，其長度等于其包含的空格個數(shù)。20組成串的數(shù)據(jù)元素只能是單個字符。一個字符串中仟意個連續(xù)字符構(gòu)成的部分稱為該串的子串。子串”str”在主串”datastructure”中的位置是一5。二維數(shù)組M的每個元素是6個字符組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從1到10,則存放M至少需要540個字節(jié)；M的第8列和第5行共占皿個字節(jié)。24稀疏矩陣一般的壓縮存儲方法有兩種，即三元組表和十字鏈表。25.廣義表（a）,（b）,c）,（d）的長度是3，深度是4。26在一棵二叉樹中，度為零的結(jié)

48、點的個數(shù)為n0,度為2的結(jié)點的個數(shù)為n2，則有n0=n2十。27在有n個結(jié)點的二叉鏈表中，空鏈域的個數(shù)為_n+1_。28.一棵有n個葉子結(jié)點的哈夫曼樹共有_2n丄個結(jié)點。29深度為5的二叉樹至多有一個結(jié)點。30若某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點個數(shù)為一69一。某二叉樹的前序遍歷序列是abdgcefh，中序序列是dgbaechf，其后序序列為gdbehfca。32線索二叉樹的左線索指向其，右線索指向其遍歷序列中的后繼。33在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是。34在分塊索引查找方法中，首先查找索引表，然后查找相應(yīng)的塊表。35.一個無序序列可以通過構(gòu)造一棵一叉排序樹而變成一個有序序列，構(gòu)造樹的過程即為對無序序列進(jìn)行排序的過程。36具有10個頂點的無向圖，邊的總數(shù)最多為_4