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

“數(shù)據(jù)結(jié)構(gòu)”期末考試試題一、單選題(每小題2分，共12分)1．在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行()。A．HL＝psp一>next＝HLB．p一>next＝HL；HL＝p3C．p一>next＝Hl；p＝HL；D．p一>next＝HL一>next;HL一>next＝p；2．n個頂點的強連通圖中至少含有()。A.n—l條有向邊B.n條有向邊C.n(n—1)／2條有向邊D.n(n一1)條有向邊3.從一棵二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為()。A.O(1)B.O(n)C.O(1Ogzn)D.O(n2)4．由權(quán)值分別為3，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為()。A．24B．48C．72D．535．當(dāng)一個作為實際傳遞的對象占用的存儲空間較大并可能需要修改時，應(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分)1．?dāng)?shù)據(jù)的存儲結(jié)構(gòu)被分為——、——、——和——四種。2．在廣義表的存儲結(jié)構(gòu)中，單元素結(jié)點與表元素結(jié)點有一個域?qū)?yīng)不同，各自分別為——域和——域。3．——中綴表達(dá)式3十x*(2.4／5—6)所對應(yīng)的后綴表達(dá)式為————。4．在一棵高度為h的3叉樹中，最多含有——結(jié)點。5．假定一棵二叉樹的結(jié)點數(shù)為18，則它的最小深度為——，最大深度為——·6．在一棵二叉搜索樹中，每個分支結(jié)點的左子樹上所有結(jié)點的值一定——該結(jié)點的值，右子樹上所有結(jié)點的值一定——該結(jié)點的值。7．當(dāng)向一個小根堆插入一個具有最小值的元素時，該元素需要逐層——調(diào)整，直到被調(diào)整到——位置為止。8．表示圖的三種存儲結(jié)構(gòu)為——、——和———。9．對用鄰接矩陣表示的具有n個頂點和e條邊的圖進(jìn)行任一種遍歷時，其時間復(fù)雜度為——，對用鄰接表表示的圖進(jìn)行任一種遍歷時，其時間復(fù)雜度為——。10．從有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素時，其查找長度分別為——和——·11．假定對長度n＝144的線性表進(jìn)行索引順序查找，并假定每個子表的長度均為，則進(jìn)行索引順序查找的平均查找長度為——，時間復(fù)雜度為——·12．一棵B—樹中的所有葉子結(jié)點均處在——上。13．每次從無序表中順序取出一個元素，把這插入到有序表中的適當(dāng)位置，此種排序方法叫做——排序；每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做——排序。14．快速排序在乎均情況下的時間復(fù)雜度為——，最壞情況下的時間復(fù)雜度為——。三、運算題(每小題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}，則求出該圖的最小生成樹的權(quán)。最小生成樹的權(quán)；3．假定一組記錄的排序碼為(46，79，56，38，40，84，50，42)，則利用堆排序方法建立的初始堆為——。4．有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分)1．VOldAC(List&L){InitList(L)；InsertRear(L;25)；InsertFront(L，50)；IntaL4]＝{5，8，12，15，36};for(inti＝0;i<5;i++)if(a[i]％2＝＝0)InsertFront(L，a[i])；elselnsertRear(L，a[i])；}該算法被調(diào)用執(zhí)行后，得到的線性表L為：2．voidAG(Queue&Q){InitQueue(Q)；inta[5]＝{6，12，5，15，8}；for(inti＝0;i<5;i++)QInsert(Q，a[i])；QInsert(Q，QDelete(Q))；QInsert(Q，20)；QInsert(Q，QDelete(Q)十16)；while(!QueueEmpty(Q))cout<<QDelete(Q)<<”；}該算法被調(diào)用后得到的輸出結(jié)果為：五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(每小題6分，共12分)1．從一維數(shù)組A[n)中二分查找關(guān)鍵字為K的元素的遞歸算法，若查找成功則返回對應(yīng)元素的下標(biāo)，否則返回一1。IntBinsch(ElemTypeA[]，Intlow，inthigh，KeyTypeK){if(low<＝high){intmid＝(low+high)／2；if(K＝＝A[mid].key)——；elseif(K<A[mid].key)——；else；}elsereturn—l；}2．已知二叉樹中的結(jié)點類型BinTreeNode定義為：structBinTreeNode{ElemTypedata；BinTreeNode*left，*right}；其中data為結(jié)點值域，left和right分別為指向左、右子女結(jié)點的指針域。下面函數(shù)的功能是返回二叉樹BT中值為x的結(jié)點所在的層號，請在劃有橫線的地方填寫合適內(nèi)容。IntNodeLevel(BinTreeNode*BT，ElemTypeX){if(BT：＝NULL)return0；／／空樹的層號為0elseif(BT一>data＝＝X)return1;／／根結(jié)點的層號為1／／向子樹中查找x結(jié)點else{intcl＝NodeLevel(BT一>left，X)；if(cl>＝1)returncl+1;intc2＝；if——；／／若樹中不存在X結(jié)點則返回oelsereturn0；}}六、編寫算法(8分)按所給函數(shù)聲明編寫一個算法，從表頭指針為HL的單鏈表中查找出具有最大值的結(jié)點，該最大值由函數(shù)返回，若單鏈表為空則中止運行。EIemTypeMaxValue(LNOde*HL);

“數(shù)據(jù)結(jié)構(gòu)”期末考試試題答案一、單選題(每小題2分，共12分)評分標(biāo)準(zhǔn)；選對者得2分，否則不得分。1．B2．B3．C4．D5．B6．A二、填空題(每空1分，共28分)1．順序結(jié)構(gòu)鏈接結(jié)構(gòu)索引結(jié)構(gòu)散列結(jié)構(gòu)(次序無先后)2．值(或data)子表指針(或sublist)3．3x2．45／6一*十4．(3h一1)／25．5186．小于大于(或大于等于)（×）28.對于一棵非空二叉樹，它的根結(jié)點作為第一層，則它的第i層上最多能有2i—1個結(jié)點。（應(yīng)2i-1）（√）29.用二叉鏈表法（link-rlink）存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n+1個為空指針。（√）30.具有12個結(jié)點的完全二叉樹有5個度為2的結(jié)點。三、單項選擇題（B）1.非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：A）一對多關(guān)系B）多對多關(guān)系C）多對一關(guān)系D）一對一關(guān)系（C）2.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的結(jié)構(gòu)；A)存儲B)物理C)邏輯D)物理和存儲（C）3.算法分析的目的是：A)找出數(shù)據(jù)結(jié)構(gòu)的合理性B)研究算法中的輸入和輸出的關(guān)系C)分析算法的效率以求改進(jìn)D)分析算法的易懂性和文檔性（A）4.算法分析的兩個主要方面是：A)空間復(fù)雜性和時間復(fù)雜性B)正確性和簡明性C)可讀性和文檔性D)數(shù)據(jù)復(fù)雜性和程序復(fù)雜性（C）5.計算機算法指的是：A)計算方法B)排序方法C)解決問題的有限運算序列D)調(diào)度方法（B）6.計算機算法必須具備輸入、輸出和等5個特性。A)可行性、可移植性和可擴充性B)可行性、確定性和有窮性C)確定性、有窮性和穩(wěn)定性D)易讀性、穩(wěn)定性和安全性（C）7．?dāng)?shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：（A）存儲結(jié)構(gòu)（B）邏輯結(jié)構(gòu)（C）順序存儲結(jié)構(gòu)（D）鏈?zhǔn)酱鎯Y(jié)構(gòu)（B）8.一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（A）110（B）108（C）100（D）120（A）9.在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O（1）的操作是：訪問第i個結(jié)點（1≤i≤n）和求第i個結(jié)點的直接前驅(qū)（2≤i≤n）在第i個結(jié)點后插入一個新結(jié)點（1≤i≤n）刪除第i個結(jié)點（1≤i≤n）將n個結(jié)點從小到大排序（B）10.向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動個元素（A）8（B）63.5（C）63（D）7（A）11.鏈接存儲的存儲結(jié)構(gòu)所占存儲空間：分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針只有一部分，存放結(jié)點值(C）只有一部分，存儲表示結(jié)點間關(guān)系的指針（D）分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)（B）12.鏈表是一種采用存儲結(jié)構(gòu)存儲的線性表；（A）順序（B）鏈?zhǔn)剑–）星式（D）網(wǎng)狀（D）13.線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址:（A）必須是連續(xù)的（B）部分地址必須是連續(xù)的（C）一定是不連續(xù)的（D）連續(xù)或不連續(xù)都可以（B）14．線性表Ｌ在情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)。（Ａ）需經(jīng)常修改Ｌ中的結(jié)點值（Ｂ）需不斷對Ｌ進(jìn)行刪除插入（Ｃ）Ｌ中含有大量的結(jié)點（Ｄ）Ｌ中結(jié)點結(jié)構(gòu)復(fù)雜（B）15.棧中元素的進(jìn)出原則是Ａ．先進(jìn)先出Ｂ．后進(jìn)先出Ｃ．棧空則進(jìn)Ｄ．棧滿則出（C）16.若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為Ａ．iＢ．n=iＣ．n-i+1Ｄ．不確定（B）17.判定一個棧ST（最多元素為m0）為空的條件是Ａ．ST->top<>0Ｂ．ST->top=0Ｃ．ST->top<>m0Ｄ．ST->top=m0（C）18.在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的倍。A．1/2B.1C.2D.4（B）19.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的倍。A．1/2B.1C.2D.4（B）20.有8個結(jié)點的無向圖最多有條邊。A．14B.28C.56D.112（C）21.有8個結(jié)點的有向完全圖有條邊。A．14B.28C.56D.112（B）22．在表長為ｎ的鏈表中進(jìn)行線性查找，它的平均查找長度為Ａ.ＡＳＬ＝ｎ;Ｂ.ＡＳＬ＝（ｎ＋１）／２;Ｃ.ＡＳＬ＝＋１;Ｄ.ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１（A）23．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中比較大小，查找結(jié)果是失敗。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50（C）24．對22個記錄的有序表作折半查找，當(dāng)查找失敗時，至少需要比較次關(guān)鍵字。A．3B．4C．5D．6（A）25.鏈表適用于查找A．順序B．二分法C．順序，也能二分法D．隨機《數(shù)據(jù)結(jié)構(gòu)與算法》復(fù)習(xí)題一、選擇題。1．在數(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)2．?dāng)?shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指A。A．?dāng)?shù)據(jù)的存儲結(jié)構(gòu)B．?dāng)?shù)據(jù)結(jié)構(gòu)C．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)D．?dāng)?shù)據(jù)元素之間的關(guān)系3．在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的A結(jié)構(gòu)。A．邏輯B．存儲C．邏輯和存儲D．物理4．在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲C。A．?dāng)?shù)據(jù)的處理方法B．?dāng)?shù)據(jù)元素的類型C．?dāng)?shù)據(jù)元素之間的關(guān)系D．?dāng)?shù)據(jù)的存儲方法5．在決定選取何種存儲結(jié)構(gòu)時，一般不考慮A。A．各結(jié)點的值如何B．結(jié)點個數(shù)的多少C．對數(shù)據(jù)有哪些運算D．所用的編程語言實現(xiàn)這種結(jié)構(gòu)是否方便。6．以下說法正確的是D。A．?dāng)?shù)據(jù)項是數(shù)據(jù)的基本單位B．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位C．?dāng)?shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項的集合D．一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)7．算法分析的目的是C，算法分析的兩個主要方面是A。（1）A．找出數(shù)據(jù)結(jié)構(gòu)的合理性B．研究算法中的輸入和輸出的關(guān)系C．分析算法的效率以求改進(jìn)C．分析算法的易讀性和文檔性（2）A．空間復(fù)雜度和時間復(fù)雜度B．正確性和簡明性C．可讀性和文檔性D．?dāng)?shù)據(jù)復(fù)雜性和程序復(fù)雜性8．下面程序段的時間復(fù)雜度是O(n2)。 s=0;for(I=0;i<n;i++) for(j=0;j<n;j++) s+=B[i][j];sum=s;9．下面程序段的時間復(fù)雜度是O(n*m)。for(i=0;i<n;i++) for(j=0;j<m;j++) A[i][j]＝0;10．下面程序段的時間復(fù)雜度是O(log3n)。i＝0；while（i<=n） i=i*3；11．在以下的敘述中，正確的是B。A．線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B．二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C．棧的操作方式是先進(jìn)先出D．隊列的操作方式是先進(jìn)后出12．通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著B。A．?dāng)?shù)據(jù)元素具有同一特點B．不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)的數(shù)據(jù)項的類型要一致C．每個數(shù)據(jù)元素都一樣D．?dāng)?shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等13．鏈表不具備的特點是A。A．可隨機訪問任一結(jié)點B．插入刪除不需要移動元素C．不必事先估計存儲空間D．所需空間與其長度成正比14．不帶頭結(jié)點的單鏈表head為空的判定條件是A。A．head==NULLBhead->next==NULLC．head->next==headDhead!=NULL15．帶頭結(jié)點的單鏈表head為空的判定條件是B。A．head==NULLBhead->next==NULLC．head->next==headDhead!=NULL16．若某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點，則采用D存儲方式最節(jié)省運算時間。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。A．p->prior=s；s->next=p；p->prior->next=s；s->prior=p->priorB．p->prior=s；p->prior->next=s；s->next=p；s->prior=p->priorC．s->next=p；s->prior=p->prior；p->prior=s；p->prior->next=sD．s->next=p；s->prior=p->prior；p->prior->next=s；p->prior=s20．如果最常用的操作是取第i個結(jié)點及其前驅(qū)，則采用D存儲方式最節(jié)省時間。A．單鏈表B．雙鏈表C．單循環(huán)鏈表D．順序表21．在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復(fù)雜度是B。A．O（1）B．O（n）C．O（n2）D．O（nlog2n）22．在一個長度為n（n>1）的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行B操作與鏈表的長度有關(guān)。A．刪除單鏈表中的第一個元素B．刪除單鏈表中的最后一個元素C．在單鏈表第一個元素前插入一個新元素D．在單鏈表最后一個元素后插入一個新元素23．與單鏈表相比，雙鏈表的優(yōu)點之一是D。A．插入、刪除操作更簡單B．可以進(jìn)行隨機訪問C．可以省略表頭指針或表尾指針D．順序訪問相鄰結(jié)點更靈活24．如果對線性表的操作只有兩種，即刪除第一個元素，在最后一個元素的后面插入新元素，則最好使用B。A．只有表頭指針沒有表尾指針的循環(huán)單鏈表B．只有表尾指針沒有表頭指針的循環(huán)單鏈表C．非循環(huán)雙鏈表D．循環(huán)雙鏈表25．在長度為n的順序表的第i個位置上插入一個元素（1≤i≤n+1），元素的移動次數(shù)為：A。A．n–i+1B．n–iC．iD．i–126．對于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為C。A．順序表B．用頭指針表示的循環(huán)單鏈表C．用尾指針表示的循環(huán)單鏈表D．單鏈表27．下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？C。A插入運算方便B可方便地用于各種邏輯結(jié)構(gòu)的存儲表示C存儲密度大D刪除運算方便28．下面關(guān)于線性表的敘述中，錯誤的是哪一個？B。A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B線性表采用順序存儲，便于進(jìn)行插入和刪除操作。C線性表采用鏈?zhǔn)酱鎯?，不必占用一片連續(xù)的存儲單元D線性表采用鏈?zhǔn)酱鎯?，便于進(jìn)行插入和刪除操作。29．線性表是具有n個B的有限序列。A．字符B．?dāng)?shù)據(jù)元素C．?dāng)?shù)據(jù)項D．表元素30．在n個結(jié)點的線性表的數(shù)組實現(xiàn)中，算法的時間復(fù)雜度是O（1）的操作是A。A．訪問第i（1<=i<=n）個結(jié)點和求第i個結(jié)點的直接前驅(qū)（1<i<=n）B．在第i（1<=i<=n）個結(jié)點后插入一個新結(jié)點C．刪除第i（1<=i<=n）個結(jié)點D．以上都不對31．若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為C。A．O(0)B．O(1)C．O(n)D．O(n2)32．對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復(fù)雜度為C。A．O(n)O(n)B．O(n)O(1)C．O(1)O(n)D．O(1)O(1)33．線性表（a1,a2,…,an）以鏈?zhǔn)椒绞酱鎯?，訪問第i位置元素的時間復(fù)雜度為C。A．O(0)B．O(1)C．O(n)D．O(n2)34．單鏈表中，增加一個頭結(jié)點的目的是為了C。A．使單鏈表至少有一個結(jié)點 B．標(biāo)識表結(jié)點中首結(jié)點的位置C．方面運算的實現(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;C．p->next=s；p->next=s->nextD．p->next=s->next；p->next=s36．線性表的順序存儲結(jié)構(gòu)是一種A。A．隨機存取的存儲結(jié)構(gòu)B．順序存取的存儲結(jié)構(gòu)C．索引存取的存儲結(jié)構(gòu)D．Hash存取的存儲結(jié)構(gòu)37．棧的特點是B，隊列的特點是A。A．先進(jìn)先出B．先進(jìn)后出38．棧和隊列的共同點是C。A．都是先進(jìn)后出B．都是先進(jìn)先出C．只允許在端點處插入和刪除元素D．沒有共同點39．一個棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能的輸出序列是C。A．edcbaB．decbaC．dceabD．a(chǎn)bcde40．設(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不是隊列的基本運算？A．從隊尾插入一個新元素B．從隊列中刪除第i個元素C．判斷一個隊列是否為空D．讀取隊頭元素的值42．若已知一個棧的進(jìn)棧序列是1，2，3，，n，其輸出序列為p1，p2，p3，…，pn，若p1＝n，則pi為C。A．iB．n－iC．n－i＋1D．不確定43．判定一個順序棧st（最多元素為MaxSize）為空的條件是B。A．st->top!=-1B．st->top==-1C．st->top!=MaxSizeD．st->top==MaxSize44．判定一個順序棧st（最多元素為MaxSize）為滿的條件是D。A．st->top!=-1B．st->top==-1C．st->top!=MaxSizeD．st->top==MaxSize45．一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是B。A．4，3，2，1B．1，2，3，4C．1，4，3，2D．3，2，4，146．判定一個循環(huán)隊列qu（最多元素為MaxSize）為空的條件是C。A．qu->rear–qu->front==MaxSizeB．qu->rear–qu->front-1==MaxSizeC．qu->rear==qu->frontD．qu->rear=qu->front-147．在循環(huán)隊列中，若front與rear分別表示對頭元素和隊尾元素的位置，則判斷循環(huán)隊列空的條件是C。A．front==rear+1B．rear==front+1C．front==rearD．front==048．向一個棧頂指針為h的帶頭結(jié)點的鏈棧中插入指針s所指的結(jié)點時，應(yīng)執(zhí)行D操作。A．h->next=s

;B．s->next=h

;C．s->next=h

;h=s

;D．s->next=h->next

;h->next=s

;49．輸入序列為ABC，可以變?yōu)镃BA時，經(jīng)過的棧操作為B。A．push，pop，push，pop，push，popB．push，push，push，pop，pop，popC．push，push，pop，pop，push，popD．push，pop，push，push，pop，pop50．若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V[1m]，top[1]、top[2]分別代表第1和第2個棧的棧頂，棧1的底在V[1]，棧2的底在V[m]，則棧滿的條件是B。A．|top[2]-top[1]|=0B．top[1]+1=top[2]C．top[1]+top[2]=mD．top[1]=top[2]51．設(shè)計一個判別表達(dá)式中左、右括號是否配對出現(xiàn)的算法，采用D數(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。A．1和5B．2和4C．4和2D．5和155．隊列的“先進(jìn)先出”特性是指D。A．最早插入隊列中的元素總是最后被刪除B．當(dāng)同時進(jìn)行插入、刪除操作時，總是插入操作優(yōu)先C．每當(dāng)有刪除操作時，總是要先做一次插入操作D．每次從隊列中刪除的總是最早插入的元素56．和順序棧相比，鏈棧有一個比較明顯的優(yōu)勢是A。A．通常不會出現(xiàn)棧滿的情況B．通常不會出現(xiàn)?？盏那闆rC．插入操作更容易實現(xiàn)D．刪除操作更容易實現(xiàn)57．用不帶頭結(jié)點的單鏈表存儲隊列，其頭指針指向隊頭結(jié)點，尾指針指向隊尾結(jié)點，則在進(jìn)行出隊操作時C。A．僅修改隊頭指針B．僅修改隊尾指針C．隊頭、隊尾指針都可能要修改D．隊頭、隊尾指針都要修改58．若串S=‘software’，其子串的數(shù)目是B。A．8B．37C．36D．959．串的長度是指B。A．串中所含不同字母的個數(shù)B．串中所含字符的個數(shù)C．串中所含不同字符的個數(shù)D．串中所含非空格字符的個數(shù)60．串是一種特殊的線性表，其特殊性體現(xiàn)在B。A．可以順序存儲B．?dāng)?shù)據(jù)元素是一個字符C．可以鏈?zhǔn)酱鎯．?dāng)?shù)據(jù)元素可以是多個字符61．設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱為B。A．連接B．模式匹配C．求子串D．求串長62．?dāng)?shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A[8][5]的起始地址為C。A．SA＋141B．SA＋144C．SA＋222D．SA＋22563．?dāng)?shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A[5][8]的起始地址為C。A．SA＋141B．SA＋180C．SA＋222D．SA＋22564．若聲明一個浮點數(shù)數(shù)組如下：froataverage[]=newfloat[30];假設(shè)該數(shù)組的內(nèi)存起始位置為200，average[15]的內(nèi)存地址是C。A．214B．215C．260D．25665．設(shè)二維數(shù)組A[1…m,1…n]按行存儲在數(shù)組B中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為A。A．n*(i-1)+jB．n*(i-1)+j-1C．i*(j-1)D．j*m+i-166．有一個100×90的稀疏矩陣，非0元素有10，設(shè)每個整型數(shù)占2個字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是B。A．20B．66C．18000D．3367．?dāng)?shù)組A[0…4，-1…-3，5…7]中含有的元素個數(shù)是A。A．55B．45C．36D．1668．對矩陣進(jìn)行壓縮存儲是為了D。A．方便運算B．方便存儲C．提高運算速度D．減少存儲空間69．設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a1，1為第一個元素，其存儲地址為1，每個元素占1個地址空間，則a8，5的地址為B。A．13B．33C．18D．4070．稀疏矩陣一般的壓縮存儲方式有兩種，即C。A．二維數(shù)組和三維數(shù)組B．三元組和散列C．三元組和十字鏈表D．散列和十字鏈表71．樹最適合用來表示C。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，則D。A．n=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é)點的左右鏈域，應(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é)點。A．8B．9C．10D．1180．在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的C倍。A．1/2B1C2D481．在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的B倍。A．1/2B1C2D482．某二叉樹結(jié)點的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結(jié)點數(shù)目為：CA．3B．2C．4D．583．已知一算術(shù)表達(dá)式的中綴形式為A＋B*C–D/E，后綴形式為ABC*+DE/–，其前綴形式為

D

。

A．–A+B*C/DE

B．–A+B*CD/E

C–+*ABC/DE

D．–+A*BC/DE84．已知一個圖，如圖所示，若從頂點a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點序列為____D___；按廣度搜索法進(jìn)行遍歷，則可能得到的一種頂點序列為___A___；①A．a(chǎn)，b，e，c，d，fB．a(chǎn)，c，f，e，b，dC．a(chǎn)，e，b，c，f，d，D．a(chǎn)，e，d，f，c，b②A．a(chǎn)，b，c，e，d，fB．a(chǎn)，b，c，e，f，dC．a(chǎn)，e，b，c，f，d，D．a(chǎn)，c，f，d，e，b85．采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的___A____。A．先序遍歷B．中序遍歷C．后序遍歷D．按層遍歷86．采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的___D____。A．先序遍歷B．中序遍歷C．后序遍歷D．按層遍歷87．具有n個結(jié)點的連通圖至少有A條邊。A．n-1B．nC．n(n-1)/2D．2n88．廣義表（（a），a）的表頭是C，表尾是C。A．a(chǎn)B（）C（a）D（（a））89．廣義表（（a））的表頭是C，表尾是B。A．a(chǎn)B（）C（a）D（（a））90．順序查找法適合于存儲結(jié)構(gòu)為B的線性表。A散列存儲B順序存儲或鏈?zhǔn)酱鎯壓縮存儲D索引存儲91．對線性表進(jìn)行折半查找時，要求線性表必須B。A以順序方式存儲B以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列C以鏈?zhǔn)椒绞酱鎯以鏈?zhǔn)椒绞酱鎯Γ医Y(jié)點按關(guān)鍵字有序排列92．采用折半查找法查找長度為n的線性表時，每個元素的平均查找長度為D。AO(n2)BO(nlog2n)CO(n)DO(log2n)93．有一個有序表為｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，當(dāng)折半查找值為82的結(jié)點時，C次比較后查找成功。A．11B5C4D894．二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法B。A正確B錯誤95．下面關(guān)于B樹和B+樹的敘述中，不正確的結(jié)論是A。AB樹和B+樹都能有效的支持順序查找BB樹和B+樹都能有效的支持隨機查找CB樹和B+樹都是平衡的多叉樹DB樹和B+樹都可用于文件索引結(jié)構(gòu)96．以下說法錯誤的是B。A．散列法存儲的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲地址B．散列表的結(jié)點中只包含數(shù)據(jù)元素自身的信息，不包含指針。C．負(fù)載因子是散列表的一個重要參數(shù)，它反映了散列表的飽滿程度。D．散列表的查找效率主要取決于散列表構(gòu)造時選取的散列函數(shù)和處理沖突的方法。97．查找效率最高的二叉排序樹是C。A．所有結(jié)點的左子樹都為空的二叉排序樹。B．所有結(jié)點的右子樹都為空的二叉排序樹。C．平衡二叉樹。D．沒有左子樹的二叉排序樹。98．排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為C。A．希爾排序B。冒泡排序C插入排序D。選擇排序99．在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是D。A．希爾排序B．冒泡排序C．直接插入排序D．直接選擇排序100．堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列D是一個堆。A．94,31,53,23,16,72B．94,53,31,72,16,23C．16,53,23,94,31,72D．16,31,23,94,53,72101．堆排序是一種B排序。A．插入B．選擇C．交換D．歸并102．D在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高。A．順序查找B．折半查找C．分塊查找D．插入103．直接選擇排序的時間復(fù)雜度為D。（n為元素個數(shù)）A．O（n)B．O(log2n)C．O(nlog2n)D．O(n2)二、填空題。1．?dāng)?shù)據(jù)邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)三種類型，樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱非線性結(jié)構(gòu)。2．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)4種。3．在線性結(jié)構(gòu)中，第一個結(jié)點沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點；最后一個結(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é)點有且只有1個前驅(qū)結(jié)點；葉子結(jié)點沒有后續(xù)結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點可以任意多個。6．?dāng)?shù)據(jù)結(jié)構(gòu)的基本存儲方法是順序、鏈?zhǔn)?、索引和散列存儲?．衡量一個算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和時間復(fù)雜度與空間復(fù)雜度。8．評估一個算法的優(yōu)劣，通常從時間復(fù)雜度和空間復(fù)雜度兩個方面考察。9．算法的5個重要特性是有窮性、確定性、可行性、輸入和輸出。10．在一個長度為n的順序表中刪除第i個元素時，需向前移動n-i-1個元素。11．在單鏈表中，要刪除某一指定的結(jié)點，必須找到該結(jié)點的前驅(qū)結(jié)點。12．在雙鏈表中，每個結(jié)點有兩個指針域，一個指向前驅(qū)結(jié)點，另一個指向后繼結(jié)點。13．在順序表中插入或刪除一個數(shù)據(jù)元素，需要平均移動n個數(shù)據(jù)元素，移動數(shù)據(jù)元素的個數(shù)與位置有關(guān)。14．當(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)系的。17．帶頭結(jié)點的循環(huán)鏈表L中只有一個元素結(jié)點的條件是L->next->next=L。18．棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表，其運算遵循后進(jìn)先出的原則。19．空串是零個字符的串，其長度等于零。空白串是由一個或多個空格字符組成的串，其長度等于其包含的空格個數(shù)。20．組成串的數(shù)據(jù)元素只能是單個字符。21．一個字符串中任意個連續(xù)字符構(gòu)成的部分稱為該串的子串。22．子串”str”在主串”datastructure”中的位置是5。23．二維數(shù)組M的每個元素是6個字符組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從1到10，則存放M至少需要540個字節(jié)；M的第8列和第5行共占108個字節(jié)。24．稀疏矩陣一般的壓縮存儲方法有兩種，即三元組表和十字鏈表。25．廣義表（（a），（（b），c），（（（d））））的長度是3，深度是4。26．在一棵二叉樹中，度為零的結(jié)點的個數(shù)為n0，度為2的結(jié)點的個數(shù)為n2，則有n0＝n2+1。27．在有n個結(jié)點的二叉鏈表中，空鏈域的個數(shù)為__n+1__。28．一棵有n個葉子結(jié)點的哈夫曼樹共有__2n-1_個結(jié)點。29．深度為5的二叉樹至多有31個結(jié)點。30．若某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點個數(shù)為69。31．某二叉樹的前序遍歷序列是abdgcefh，中序序列是dgbaechf，其后序序列為gdbehfca。32．線索二叉樹的左線索