數(shù)據(jù)結(jié)構(gòu)C語言版期末考試試題(附帶復(fù)習(xí)資料)...doc

“數(shù)據(jù)結(jié)構(gòu)”期末考試試題一、單選題(每小題2分，共12分) 1在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行( )。 A HLps p一nextHL B p一nextHL；HLp3 C p一nextHl；pHL； D p一nextHL一next;HL一nextp； 2n個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有( )。 A.nl條有向邊 B.n條有向邊 C.n(n1)2條有向邊 D.n(n一1)條有向邊 3.從一棵二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為( )。 A.O(1) B.O(n)C.O(1Ogzn) D.O(n2)4由權(quán)值分別為3，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為( )。 A24 B48C 72 D 535當(dāng)一個(gè)作為實(shí)際傳遞的對(duì)象占用的存儲(chǔ)空間較大并可能需要修改時(shí)，應(yīng)最好把它說明為( )參數(shù)，以節(jié)省參數(shù)值的傳輸時(shí)間和存儲(chǔ)參數(shù)的空間。 A.整形 B.引用型 C.指針型 D.常值引用型6向一個(gè)長度為n的順序表中插人一個(gè)新元素的平均時(shí)間復(fù)雜度為( )。 AO(n) BO(1) CO(n2) DO(10g2n)二、填空題(每空1分，共28分)1數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為、和四種。 2在廣義表的存儲(chǔ)結(jié)構(gòu)中，單元素結(jié)點(diǎn)與表元素結(jié)點(diǎn)有一個(gè)域?qū)?yīng)不同，各自分別為域和域。3中綴表達(dá)式 3十x*(2.456)所對(duì)應(yīng)的后綴表達(dá)式為。 4在一棵高度為h的3叉樹中，最多含有結(jié)點(diǎn)。5假定一棵二叉樹的結(jié)點(diǎn)數(shù)為18，則它的最小深度為，最大深度為 6在一棵二叉搜索樹中，每個(gè)分支結(jié)點(diǎn)的左子樹上所有結(jié)點(diǎn)的值一定該結(jié)點(diǎn)的值，右子樹上所有結(jié)點(diǎn)的值一定該結(jié)點(diǎn)的值。 7當(dāng)向一個(gè)小根堆插入一個(gè)具有最小值的元素時(shí)，該元素需要逐層調(diào)整，直到被調(diào)整到位置為止。 8表示圖的三種存儲(chǔ)結(jié)構(gòu)為、和。 9對(duì)用鄰接矩陣表示的具有n個(gè)頂點(diǎn)和e條邊的圖進(jìn)行任一種遍歷時(shí)，其時(shí)間復(fù)雜度為，對(duì)用鄰接表表示的圖進(jìn)行任一種遍歷時(shí)，其時(shí)間復(fù)雜度為。 10從有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素時(shí)，其查找長度分別為和 11假定對(duì)長度n144的線性表進(jìn)行索引順序查找，并假定每個(gè)子表的長度均為，則進(jìn)行索引順序查找的平均查找長度為，時(shí)間復(fù)雜度為 12一棵B樹中的所有葉子結(jié)點(diǎn)均處在上。 13每次從無序表中順序取出一個(gè)元素，把這插入到有序表中的適當(dāng)位置，此種排序方法叫做排序；每次從無序表中挑選出一個(gè)最小或最大元素，把它交換到有序表的一端，此種排序方法叫做排序。 14快速排序在乎均情況下的時(shí)間復(fù)雜度為，最壞情況下的時(shí)間復(fù)雜度為。 三、運(yùn)算題(每小題6分，共24分) 1假定一棵二叉樹廣義表表示為a(b(c，d)，c(，8)，分別寫出對(duì)它進(jìn)行先序、中序、后序和后序遍歷的結(jié)果。 先序： 中序； 后序： 2已知一個(gè)帶權(quán)圖的頂點(diǎn)集V和邊集G分別為： V0，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個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3，7，8，2，6，10，14，試以它們?yōu)槿~子結(jié)點(diǎn)生成一棵哈夫曼樹，求出該樹的帶權(quán)路徑長度、高度、雙分支結(jié)點(diǎn)數(shù)。 帶權(quán)路徑長度： 高度： 雙分支結(jié)點(diǎn)數(shù)：。四、閱讀算法，回答問題(每小題8分，共16分) 1VOldAC(List&L) InitList(L)； InsertRear(L;25)； InsertFront(L，50)； IntaL45，8，12，15，36; for(inti0; i5; i+) if (ai20)InsertFront(L，ai)； elselnsertRear(L，ai)； 該算法被調(diào)用執(zhí)行后，得到的線性表L為： 2void AG(Queue&Q) InitQueue(Q)； inta56，12，5，15，8； for(int i0;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的元素的遞歸算法，若查找成功則返回對(duì)應(yīng)元素的下標(biāo)，否則返回一1。 IntBinsch(ElemTypeA，Intlow，int high，KeyTypeK) if(lowhigh) int mid(low+high)2； if(KAmid.key)； else if (KdataX)return 1; 根結(jié)點(diǎn)的層號(hào)為1 向子樹中查找x結(jié)點(diǎn) else int clNodeLevel(BT一left，X)； if(cl1)return cl+1; int c2 ； if； 若樹中不存在X結(jié)點(diǎn)則返回o else return 0； 六、編寫算法(8分) 按所給函數(shù)聲明編寫一個(gè)算法，從表頭指針為HL的單鏈表中查找出具有最大值的結(jié)點(diǎn)，該最大值由函數(shù)返回，若單鏈表為空則中止運(yùn)行。 EIemType MaxValue(LNOde*HL);“數(shù)據(jù)結(jié)構(gòu)”期末考試試題答案 一、單選題(每小題2分，共12分) 評(píng)分標(biāo)準(zhǔn)；選對(duì)者得2分，否則不得分。 1B 2B 3C 4D 5B 6A 二、填空題(每空1分，共28分) 1順序結(jié)構(gòu) 鏈接結(jié)構(gòu) 索引結(jié)構(gòu) 散列結(jié)構(gòu)(次序無先后) 2值(或data) 子表指針(或sublist) 33 x 24 56一*十 4(3h一1)2 5 5 18 6小于 大于(或大于等于) 7向上 堆頂 8鄰接矩陣 鄰接表 邊集數(shù)組(次序無先后) 9O(n2) O(e) 10 1 3 1113 O() 12同一層 13插人 選擇 14O(nlog2n) O(n2) 三、運(yùn)算題(每小題6分，共24分) 1先序：a，b，c，d，e，f，e 2分 中序：c，b，d，a，f，8，e 2分 后序：c，d，b，e，f，e，a 2分 2最小生成樹的權(quán)：31 6分 3(84，79，56，42，40，46，50，38) 6分 4帶權(quán)路徑長度：131 3分 高度：5 2分 雙分支結(jié)點(diǎn)數(shù)：6 1分四、閱讀算法，回答問題(每小題8分，共16分) 評(píng)分標(biāo)準(zhǔn)：每小題正確得8分，出現(xiàn)一處錯(cuò)誤扣4分，兩處及以上錯(cuò)誤不得分。 1(36，12，8，50，25，5，15) 25 15 8 6 20 28五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(每小題6分，共12分) 1feturn mid 2分 returnBinsch(A，low，mid一1，K) 2分 returnBmsch(A，mid+1，high，K) 2分 2NodeLevel(BT一right，X) 3分 (c2=1)returnc2十1 3分六、編寫算法(8分) 評(píng)分標(biāo)準(zhǔn)：請(qǐng)參考語句后的注釋，或根據(jù)情況酌情給分。 ElemType MaxValue(LNodeO* HL。) if (HL=NUlL) 2分 cerrLinked llst is empty!”data； 3分 LNOde*p=HI一next； 4分 while(P!：NULL) 7分 if(maxdata)maxp一data； pp一next； returnmax； 8分 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 一、填空題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的 操作對(duì)象 以及它們之間的 關(guān)系 和運(yùn)算等的學(xué)科。2. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R），其中D是 數(shù)據(jù)元素 的有限集合，R是D上的 關(guān)系 有限集合。3. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯結(jié)構(gòu) 、數(shù)據(jù)的 存儲(chǔ)結(jié)構(gòu) 和數(shù)據(jù)的 運(yùn)算 這三個(gè)方面的內(nèi)容。4. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) 。5. 線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。6 在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn) 沒有 前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn) 沒有 后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。7. 在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 前驅(qū) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有 后續(xù) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè) 。8. 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以 任意多個(gè) 。9數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是順序 、 鏈?zhǔn)?、 索引 和 散列 。10. 數(shù)據(jù)的運(yùn)算最常用的有5種，它們分別是插入 、 刪除、修改、 查找 、排序。11. 一個(gè)算法的效率可分為 時(shí)間 效率和 空間 效率。12. 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng) 表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與 表長和該元素在表中的位置 有關(guān)。13. 線性表中結(jié)點(diǎn)的集合是 有限 的，結(jié)點(diǎn)間的關(guān)系是 一對(duì)一 的。14. 向一個(gè)長度為n的向量的第i個(gè)元素(1in+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng) n-i+1 個(gè)元素。15. 向一個(gè)長度為n的向量中刪除第i個(gè)元素(1in)時(shí)，需向前移動(dòng) n-i 個(gè)元素。16. 在順序表中訪問任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為 O(1) ，因此，順序表也稱為 隨機(jī)存取 的數(shù)據(jù)結(jié)構(gòu)。17. 順序表中邏輯上相鄰的元素的物理位置 必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置 不一定 相鄰。18在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由 其直接前驅(qū)結(jié)點(diǎn)的鏈域的值 指示。19 在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的前驅(qū)結(jié)點(diǎn)的地址，其時(shí)間復(fù)雜度為O（n）。20. 向量、棧和隊(duì)列都是 線性 結(jié)構(gòu)，可以在向量的 任何 位置插入和刪除元素；對(duì)于棧只能在 棧頂 插入和刪除元素；對(duì)于隊(duì)列只能在 隊(duì)尾 插入和 隊(duì)首 刪除元素。21. 棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為 棧頂 。不允許插入和刪除運(yùn)算的一端稱為 棧底 。22. 隊(duì)列 是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。23. 不包含任何字符（長度為0）的串 稱為空串； 由一個(gè)或多個(gè)空格（僅由空格符）組成的串 稱為空白串。24. 子串的定位運(yùn)算稱為串的模式匹配； 被匹配的主串 稱為目標(biāo)串， 子串 稱為模式。25. 假設(shè)有二維數(shù)組A68，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置（基地址）為1000，則數(shù)組A的體積（存儲(chǔ)量）為 288 B ；末尾元素A57的第一個(gè)字節(jié)地址為 1282 ；若按行存儲(chǔ)時(shí)，元素A14的第一個(gè)字節(jié)地址為 (8+4)6+1000=1072 ；若按列存儲(chǔ)時(shí)，元素A47的第一個(gè)字節(jié)地址為 (674)61000）1276 。26 由個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹有 5 種形態(tài)。 27. 一棵深度為6的滿二叉樹有 n1+n2=0+ n2= n0-1=31 個(gè)分支結(jié)點(diǎn)和 26-1 =32 個(gè)葉子。注：滿二叉樹沒有度為1的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。28 一棵具有個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為 9 。（ 注：用 log2(n) +1= 8.xx +1=929設(shè)一棵完全二叉樹有700個(gè)結(jié)點(diǎn)，則共有 350 個(gè)葉子結(jié)點(diǎn)。答：最快方法：用葉子數(shù)n/2350 30 設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹有 500 個(gè)葉子結(jié)點(diǎn)，有 499 個(gè)度為2的結(jié)點(diǎn)，有 1 個(gè)結(jié)點(diǎn)只有非空左子樹，有 0 個(gè)結(jié)點(diǎn)只有非空右子樹。答：最快方法：用葉子數(shù)n/2500 ，n2=n0-1=499。 另外，最后一結(jié)點(diǎn)為2i屬于左葉子，右葉子是空的，所以有1個(gè)非空左子樹。完全二叉樹的特點(diǎn)決定不可能有左空右不空的情況，所以非空右子樹數(shù)0.31在數(shù)據(jù)的存放無規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是 順序查找（線性查找） 。32. 線性有序表（a1，a2，a3，a256)是從小到大排列的，對(duì)一個(gè)給定的值k，用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索 8 次。設(shè)有100個(gè)結(jié)點(diǎn)，用二分法查找時(shí)，最大比較次數(shù)是 7 。33. 假設(shè)在有序線性表a20上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為1；比較兩次查找成功的結(jié)點(diǎn)數(shù)為 2 ；比較四次查找成功的結(jié)點(diǎn)數(shù)為 8 ；平均查找長度為 3.7 。解：顯然，平均查找長度O（log2n）top0 ST-top=0 ST-topm0 ST-top=m0（ C ）18. 在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的 倍。 A1/2 B. 1 C. 2 D. 4 （ B ）19. 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 倍。 A1/2 B. 1 C. 2 D. 4 （ B ）20. 有8個(gè)結(jié)點(diǎn)的無向圖最多有 條邊。 A14 B. 28 C. 56 D. 112 （ C ）21. 有8個(gè)結(jié)點(diǎn)的有向完全圖有 條邊。 A14 B. 28 C. 56 D. 112 （ B ）22在表長為的鏈表中進(jìn)行線性查找，它的平均查找長度為. ; . （）; . ; . （）（ A ）23折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中 比較大小，查找結(jié)果是失敗。A20，70，30，50 B30，88，70，50 C20，50 D30，88，50（ C ）24對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較 次關(guān)鍵字。A3 B4 C5 D 6（ A ）25. 鏈表適用于 查找A順序 B二分法 C順序，也能二分法 D隨機(jī)數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)題一、選擇題。1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為 C 。A動(dòng)態(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數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指 A 。A數(shù)據(jù)的存儲(chǔ)結(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ì)算機(jī)無關(guān)的是數(shù)據(jù)的 A 結(jié)構(gòu)。A邏輯 B存儲(chǔ) C邏輯和存儲(chǔ) D物理4在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ) C 。A數(shù)據(jù)的處理方法 B數(shù)據(jù)元素的類型 C數(shù)據(jù)元素之間的關(guān)系 D數(shù)據(jù)的存儲(chǔ)方法5在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮 A 。A各結(jié)點(diǎn)的值如何 B結(jié)點(diǎn)個(gè)數(shù)的多少C對(duì)數(shù)據(jù)有哪些運(yùn)算 D所用的編程語言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。6以下說法正確的是 D 。A數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位B數(shù)據(jù)元素是數(shù)據(jù)的最小單位C數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項(xiàng)的集合D一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)7算法分析的目的是 C ，算法分析的兩個(gè)主要方面是 A 。（1）A找出數(shù)據(jù)結(jié)構(gòu)的合理性 B研究算法中的輸入和輸出的關(guān)系C分析算法的效率以求改進(jìn) C分析算法的易讀性和文檔性（2）A空間復(fù)雜度和時(shí)間復(fù)雜度 B正確性和簡明性 C可讀性和文檔性 D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性8下面程序段的時(shí)間復(fù)雜度是 O(n2) 。 s =0;for( I =0; in; i+) for(j=0;jn;j+)s +=Bij;sum = s ;9下面程序段的時(shí)間復(fù)雜度是 O(n*m) 。for( i =0; in; i+) for(j=0;jm;j+)Aij 0;10下面程序段的時(shí)間復(fù)雜度是 O(log3n) 。i 0；while（inext =NULL Chead-next =head D head!=NULL15帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是 B 。Ahead = NULL B head-next =NULL Chead-next =head D head!=NULL16若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用 D 存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A單鏈表 B給出表頭指針的單循環(huán)鏈表 C雙鏈表 D帶頭結(jié)點(diǎn)的雙循環(huán)鏈表17需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是 B 。A單鏈表 B靜態(tài)鏈表 C線性鏈表 D順序存儲(chǔ)結(jié)構(gòu)18非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足 C 。Ap-next = NULL Bp = NULLCp-next =head Dp = head19在循環(huán)雙鏈表的p所指的結(jié)點(diǎn)之前插入s所指結(jié)點(diǎn)的操作是 D 。Ap-prior = s；s-next = p；p-prior-next = s；s-prior = p-priorBp-prior = s；p-prior-next = s；s-next = p；s-prior = p-priorCs-next = p；s-prior = p-prior；p-prior = s；p-prior-next = sDs-next = p；s-prior = p-prior；p-prior-next = s；p-prior = s20如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用 D 存儲(chǔ)方式最節(jié)省時(shí)間。A單鏈表 B雙鏈表 C單循環(huán)鏈表 D 順序表21在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是 B 。AO（1） BO（n） CO（n2） DO（nlog2n）22在一個(gè)長度為n（n1）的單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行 B 操作與鏈表的長度有關(guān)。A刪除單鏈表中的第一個(gè)元素B刪除單鏈表中的最后一個(gè)元素C在單鏈表第一個(gè)元素前插入一個(gè)新元素D在單鏈表最后一個(gè)元素后插入一個(gè)新元素23與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是 D 。A插入、刪除操作更簡單 B可以進(jìn)行隨機(jī)訪問C可以省略表頭指針或表尾指針D順序訪問相鄰結(jié)點(diǎn)更靈活24如果對(duì)線性表的操作只有兩種，即刪除第一個(gè)元素，在最后一個(gè)元素的后面插入新元素，則最好使用 B 。A只有表頭指針沒有表尾指針的循環(huán)單鏈表B只有表尾指針沒有表頭指針的循環(huán)單鏈表C非循環(huán)雙鏈表D循環(huán)雙鏈表25在長度為n的順序表的第i個(gè)位置上插入一個(gè)元素（1 i n+1），元素的移動(dòng)次數(shù)為： A 。An i + 1 Bn i Ci Di 1 26對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為 C 。A順序表 B 用頭指針表示的循環(huán)單鏈表C用尾指針表示的循環(huán)單鏈表 D單鏈表27下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？ C 。A插入運(yùn)算方便 B可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示C存儲(chǔ)密度大 D刪除運(yùn)算方便28下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？ B 。A線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C線性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D線性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)行插入和刪除操作。29線性表是具有n個(gè) B 的有限序列。A字符 B數(shù)據(jù)元素 C數(shù)據(jù)項(xiàng) D表元素30在n個(gè)結(jié)點(diǎn)的線性表的數(shù)組實(shí)現(xiàn)中，算法的時(shí)間復(fù)雜度是O（1）的操作是 A 。A訪問第i（1=i=n）個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（1i=n）B在第i（1=i=n）個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)C刪除第i（1=inext=s；s-next=p-next B s-next=p-next ；p-next=s;Cp-next=s；p-next=s-next Dp-next=s-next；p-next=s36線性表的順序存儲(chǔ)結(jié)構(gòu)是一種 A 。A隨機(jī)存取的存儲(chǔ)結(jié)構(gòu) B順序存取的存儲(chǔ)結(jié)構(gòu)C索引存取的存儲(chǔ)結(jié)構(gòu) DHash存取的存儲(chǔ)結(jié)構(gòu)37棧的特點(diǎn)是 B ，隊(duì)列的特點(diǎn)是 A 。A先進(jìn)先出 B先進(jìn)后出38棧和隊(duì)列的共同點(diǎn)是 C 。A都是先進(jìn)后出 B都是先進(jìn)先出C只允許在端點(diǎn)處插入和刪除元素 D沒有共同點(diǎn)39一個(gè)棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能的輸出序列是 C 。Aedcba Bdecba Cdceab Dabcde40設(shè)有一個(gè)棧，元素依次進(jìn)棧的順序?yàn)锳、B、C、D、E。下列 C 是不可能的出棧序列。 AA,B,C,D,E BB,C,D,E,A CE,A,B,C,D DE,D,C,B,A41以下 B 不是隊(duì)列的基本運(yùn)算？A從隊(duì)尾插入一個(gè)新元素 B從隊(duì)列中刪除第i個(gè)元素C判斷一個(gè)隊(duì)列是否為空 D讀取隊(duì)頭元素的值42若已知一個(gè)棧的進(jìn)棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1n，則pi為 C 。Ai Bni Cni1 D不確定43判定一個(gè)順序棧st（最多元素為MaxSize）為空的條件是 B 。Ast-top != -1 Bst-top = -1 Cst-top != MaxSize D st-top = MaxSize 44判定一個(gè)順序棧st（最多元素為MaxSize）為滿的條件是 D 。Ast-top != -1 Bst-top = -1 Cst-top != MaxSize Dst-top = MaxSize 45一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則隊(duì)列的輸出序列是 B 。A4，3，2，1 B1，2，3，4C1，4，3，2 D3，2，4，146判定一個(gè)循環(huán)隊(duì)列qu（最多元素為MaxSize）為空的條件是 C 。Aqu-rear qu-front =MaxSize Bqu-rear qu-front -1=MaxSize Cqu-rear =qu-front D qu-rear =qu-front -147在循環(huán)隊(duì)列中，若front與rear 分別表示對(duì)頭元素和隊(duì)尾元素的位置，則判斷循環(huán)隊(duì)列空的條件是 C 。 Afront=rear+1 Brear=front+1 Cfront=rear Dfront=048向一個(gè)棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行 D 操作。Ah-next=s; Bs-next=h;Cs-next=h;h =s; Ds-next=h-next;h-next=s;49輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過的棧操作為 B 。Apush，pop，push，pop，push，pop Bpush，push，push，pop， pop， pop Cpush，push，pop， pop，push，pop Dpush，pop，push，push，pop， pop50若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V1 m，top1、top2分別代表第1和第2個(gè)棧的棧頂，棧1的底在V1，棧2的底在Vm，則棧滿的條件是 B 。A|top2-top1|=0 B top1+1=top2 Ctop1+top2=m Dtop1=top251設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用 D 數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲(chǔ)結(jié)構(gòu) B隊(duì)列 C線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D棧52允許對(duì)隊(duì)列進(jìn)行的操作有 D 。A對(duì)隊(duì)列中的元素排序 B取出最近進(jìn)隊(duì)的元素 C在隊(duì)頭元素之前插入元素 D刪除隊(duì)頭元素53對(duì)于循環(huán)隊(duì)列 D 。A無法判斷隊(duì)列是否為空 B無法判斷隊(duì)列是否為滿 C隊(duì)列不可能滿 D以上說法都不對(duì)54若用一個(gè)大小為6的數(shù)值來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為 B 。A1和5 B2和4 C4和2 D5和155隊(duì)列的“先進(jìn)先出”特性是指 D 。A最早插入隊(duì)列中的元素總是最后被刪除 B當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)先C每當(dāng)有刪除操作時(shí)，總是要先做一次插入操作D每次從隊(duì)列中刪除的總是最早插入的元素56和順序棧相比，鏈