數(shù)據(jù)結(jié)構(gòu)試卷B卷(含答案)

1、數(shù)據(jù)結(jié)構(gòu)試卷B一、填空題(每空1分，共15分)1 .向量、棧和隊列都是 結(jié)構(gòu)，可以在向量的 位置插入和刪除元素；對于棧 只能在 插入和刪除元素；對于隊列只能在 插入和 刪除元素。2 .棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為 。不允許插入和刪除 運(yùn)算的一端稱為。3 .數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的 以及它們之間 的 和運(yùn)算等的學(xué)科。4 .在順序表中插入或刪除一個元素，需要平均移動 元素，具體移動的元素個數(shù)與 有關(guān)。5 .在具有n個單元的循環(huán)隊列中，隊滿時共有 個元素。6 .假設(shè)在有序線性表 a20上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為1;比較兩次查找成功的

2、結(jié)點(diǎn)數(shù)為 ;比較四次查找成功的結(jié)點(diǎn)數(shù)為 ;平均查找長度 為。二、判斷正誤(判斷下列概念的正確性，并作出簡要的說明。)(每小題1分，共10分)( )1.線性表的每個結(jié)點(diǎn)只能是一個簡單類型，而鏈表的每個結(jié)點(diǎn)可以是一個復(fù)雜類型。( )2.在表結(jié)構(gòu)中最常用的是線性表，棧和隊列不太常用。( )3.棧是一種對所有插入、 刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。( )4.對于不同的使用者，一個表結(jié)構(gòu)既可以是棧，也可以是隊列，也可以是線性表。( )5.線性表的邏輯順序與存儲順序總是一致的( )6.棧和隊列是一種非線性數(shù)據(jù)結(jié)構(gòu)。( )7.棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。( )

3、8.兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機(jī)會，應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。()9.隊是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。)10. 一個棧的輸入序列是 12345,則棧的輸出序列不可能是 12345。三、單項選擇題(每小題1分，共20分)()1.數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：(A)存儲結(jié)構(gòu)(B)邏輯結(jié)構(gòu)(C)順序存儲結(jié)構(gòu)(D)鏈?zhǔn)酱鎯Y(jié)構(gòu)()2.若已知一個棧的入棧序列是1, 2, 3,，n,其輸出序列為 p1, p2, p3,pn ,若 p1=n ,貝U pi 為A. i B. n=i

4、 C. n-i+1D.不確定()3.判定一個棧ST (最多元素為 m0)為空的條件是A. ST->top<>0 B . ST->top=0C. ST->top<>m0D. ST->top=m0()4設(shè)矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分(如下圖所示)按行序存放在一維數(shù)組 B 1, n(n-1)/2 中，對下三角部分中任一元素au(i<j),在一維數(shù)組B中下標(biāo)k的值是：A. i(i-1)/2+j-1 B . i(i-1)/2+jC. i(i+1)/2+j-1d. i(i+1)/2+ja1,1a2,1a2,2an,1 an,2an

5、,n)5.具有n(n>0)個結(jié)點(diǎn)的完全二叉樹的深度為 (A)log 2(n)(B )log 2(n)(C) log 2(n)+1(D) log 2(n)+1()6.有8個結(jié)點(diǎn)的無向連通圖最少有 條邊。A. 5B. 6C. 7D. 87 .數(shù)據(jù)結(jié)構(gòu)反映了數(shù)據(jù)元素之間的Z§構(gòu)關(guān)系。鏈表是一種A ,它對于數(shù)據(jù)元素的插入和刪除 B 。通常查找線性表數(shù)據(jù)元素的方法有C 和 D 兩種方法，其中 C是一種只適合于順序存儲結(jié)構(gòu)但E 的方法:而 D 是一種對順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)均適用的方法。供選擇的答案:A:順序存儲線性表 非順序存儲非線性表 性表B：不需要移動結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針 只需移動結(jié)點(diǎn)

6、，不需改變結(jié)點(diǎn)指針順序存儲非線性表非順序存儲線不需要移動結(jié)點(diǎn)，只需改變結(jié)點(diǎn)指針 既需移動結(jié)點(diǎn)，又需改變結(jié)點(diǎn)指針C:順序查找循環(huán)查找D:順序查找隨機(jī)查找條件查找二分法查找二分法查找分塊查找效率較E:效率較低的線性查找效率較低的非線性查找效率較高的非線性查找 高的線性查找答案： A= B = C= D =E=8 .散列法存儲的基本思想是根據(jù)A 來決定 B ,碰撞(沖突)指的是 C ,處理碰撞的兩類主要方法是D 。供選擇的答案A, B:存儲地址 元素的符號非碼屬性平均檢索長度C:兩個元素具有相同序號同 不同關(guān)鍵碼值對應(yīng)到相同的存儲地址D:線性探查法和雙散列函數(shù)法除余法和折疊法答案：A= B=元素個數(shù)

7、關(guān)鍵碼值負(fù)載因子散列表空間 兩個元素的關(guān)鍵碼值不同，而非碼屬性相負(fù)載因子過大 數(shù)據(jù)元素過多 建溢出區(qū)法和不建溢出區(qū)法拉鏈法和開地址法C=D =9 .考慮具有如下性質(zhì)的二叉樹：除葉子結(jié)點(diǎn)外，每個結(jié)點(diǎn)的值都大于其左子樹上的一切結(jié)點(diǎn) 的值。并小于等于其右子樹上的一切結(jié)點(diǎn)的值?，F(xiàn)把9個數(shù)1, 2, 3,，8, 9填入下圖所示的二叉樹的 9個結(jié)點(diǎn)中，并使之具有上述性質(zhì)。此時，n1的值是 A , n2的值是 B , n9的值是 C ?，F(xiàn)欲把 J10放入此樹 并使該樹保持前述性質(zhì)，增加的一個結(jié)點(diǎn)可以放在 供選擇的答案 AC：1234789DE： n7下面 n8下面 n6下面 n1與n2之間 n6與n9之間n

8、31答案：A= B= C= D = E=D 或 E四、簡答題（每小題5分，共25分）1 .說明線性表、棧與隊的異同點(diǎn)。2 .試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結(jié)點(diǎn)序列3 .假設(shè)正讀和反讀都相同的字符序列為“回文"，例如，abba'和abcba '是回文，abcde '和 ababab '則不是回文。假設(shè)一字符序列已存入計算機(jī)，請分析用線性表、 堆棧和隊列等方式正確輸出其回文的可能性？4 .試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好？5 .給定二叉樹的兩種遍歷序列，分別是：前序遍歷序列：D, A, C,

9、E, B, H, F, G, I;中序遍歷序列：D, C, B, E, H, A, G, I, F,B的思想試畫出二叉樹B,并簡述由任意二叉樹B的前序遍歷序列和中序遍歷序列求二叉樹方法。五、閱讀理解(每小題5分，共20分)1、已知L是無表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，請寫出在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的核心語句序列。2、閱讀下列算法，若有錯，改正之。BiTree InSucc(BiTree q)已知q是指向中序線索二叉樹上某個結(jié)點(diǎn)的指針，本函數(shù)返回指向*q的后繼的指針。r=q->rchild;if(!r->rtag)while(!r->rtag)r=r-&g

10、t;rchild;return r;/ISucc1 .寫出下列程序段的輸出結(jié)果(隊列中的元素類型QElem Type為char)。void main( )Queue Q; Init Queue (Q);Char x=，e' y=，c，;EnQueue (Q, 'h '); EnQueue (Q, 'r'); EnQueue (Q, 'y');DeQueue (Q,x); EnQueue (Q,x);DeQueue (Q,x); EnQueue (Q, 'a');while(!QueueEmpty(Q) DeQueue (Q

11、,y);printf(y); ;Printf(x);2 .簡述以下算法的功能(棧和隊列的元素類型均為int)。void algo3(Queue &Q)Stack S; int d;InitStack(S);while(!QueueEmpty(Q)DeQueue (Q,d); Push(S,d);while(!StackEmpty(S)Pop(S,d); EnQueue (Q,d);六、算法設(shè)計（每小題5分，共15分。至少要寫出思路）1 .寫出在順序存儲結(jié)構(gòu)下將線性表逆轉(zhuǎn)的算法，要求使用最少的附加空間。2 .編寫程序，將若干整數(shù)從鍵盤輸入， 以單鏈表形式存儲起來， 然后計算單鏈表中結(jié)點(diǎn)的

12、個 數(shù)（其中指針P指向該鏈表的第一個結(jié)點(diǎn)）。3 . 試寫一個算法，判另讀入的一個以'為結(jié)束符的字符序列是否是“回文”。答案一、填空題（每空1分，共15分）1 .向量、棧和隊列都是 線性 結(jié)構(gòu),可以在向量的 任何位置插入和刪除元素; 對于棧只能在 棧頂 插入和刪除元素;對于隊列只能在 隊尾 插入和 隊首 刪除元 素。2 .棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為棧頂 。不允許插入和刪除運(yùn)算的一端稱為棧底 。3 .數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作對象以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。4 .在順序表中插入或刪除一個元素，需要平均移動 表中一半元素,具體移動的

13、元素個數(shù)與表長和該元素在表中的位置有關(guān)。5 .在具有n個單元的循環(huán)隊列中，隊滿時共有 n-1 個元素。8.假設(shè)在有序線性表 a20上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為1;比較兩次查找成功的結(jié)點(diǎn)數(shù)為2;比較四次查找成功的結(jié)點(diǎn)數(shù)為8:平均查找長度為3.7 。5解：顯然，平均查找長度= O （log2n） <5次（2 ）。但具體是多少次，則不應(yīng)當(dāng)按照公式ASL ±log2（n 1）來計算（即（21 Xlog 221 ）/20 =4.6次并不正確?。?。因為這是在假設(shè) n=2m-1 n的情況下推導(dǎo)出來的公式。應(yīng)當(dāng)用窮舉法羅列：全部元素的查找次數(shù)為=（1 + 2X2+4X3+8X4

14、 + 5X5） =74; ASL= 74/20=3.7!二、判斷正誤（判斷下列概念的正確性，并作出簡要的說明。）（每小題1分，共10分）（ X ） 1.線性表的每個結(jié)點(diǎn)只能是一個簡單類型，而鏈表的每個結(jié)點(diǎn)可以是一個復(fù)雜類 型。錯，線性表是邏輯結(jié)構(gòu)概念，可以順序存儲或鏈?zhǔn)酱鎯Γc元素數(shù)據(jù)類型無關(guān)。（X ） 2.在表結(jié)構(gòu)中最常用的是線性表，棧和隊列不太常用。錯，不一定吧？調(diào)用子程序或函數(shù)常用，CPU中也用隊列。（，）3.棧是一種對所有插入、 刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。（ ，）4.對于不同的使用者， 一個表結(jié)構(gòu)既可以是棧，也可以是隊列，也可以是線性表。正確，都是線性邏

15、輯結(jié)構(gòu)，棧和隊列其實是特殊的線性表，對運(yùn)算的定義略有不同而已。（X ） 5.線性表的邏輯順序與存儲順序總是一致的(x ) 6.棧和隊列是一種非線性數(shù)據(jù)結(jié)構(gòu)。錯，他們都是線性邏輯結(jié)構(gòu)，棧和隊列其實是特殊的線性表，對運(yùn)算的定義略有不同而已。(，)7.棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。(，)8.兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機(jī)會，應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。(X ) 9.隊是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。錯，后半句不對。(X ) 10. 一個棧的輸入序列是 12345,則棧的輸出序列不可能是12345。錯

16、，有可能。三、單項選擇題(每小題1分，共20分)(C )1.數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：(A)存儲結(jié)構(gòu)(B)邏輯結(jié)構(gòu)(C)順序存儲結(jié)構(gòu)(D)鏈?zhǔn)酱鎯Y(jié)構(gòu)(C ) 2.若已知一個棧的入棧序列是1, 2, 3,，n,其輸出序列為 p1, p2, p3 ,，pn,若p1=n ,則pi為A. i B. n=i C. n-i+1D.不確定解釋：當(dāng)p1=n ,即n是最先出棧的，根據(jù)棧的原理，n必定是最后入棧的(事實上題目已經(jīng)表明了)，那么輸入順序必定是 1, 2, 3,，n,則出棧的序列是 n,，3, 2, 1。 (若不要求順序出棧，則輸出序列不確定)m0)為空

17、的條件是B . ST->top=0C . ST->top<>m0(B ) 3、判定一個棧ST (最多元素為A . ST->top<>0D. ST->top=m0)4、設(shè)矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分(如下圖所示)按行序存放在一維數(shù)組 標(biāo)k的值是：B 1, n(n-1)/2 中，對下三角部分中任一元素au(i<j),在一維數(shù)組B中下A.i(i-1)/2+j-1 B. i(i-1)/2+ja1,1a2,1a2,2an,1an,2an,nC. i(i+1)/2+j-1D. i(i+1)/2+jlog 2(n)+1(D)10g

18、2(n)+1C )5.具有n(n>0)個結(jié)點(diǎn)的完全二叉樹的深度為(A) log 2(n)(B) log 2(n)(C )(C )6.有8個結(jié)點(diǎn)的無向連通圖最少有 條邊。A. 5B. 6C. 7D. 87、答案：A = B = C = D = E=8、 答案：A=B= C= D=9、答案：A=B= C= D=E=四、簡答題（每小題4分，共20分）1 .說明線性表、棧與隊的異同點(diǎn)。劉答：相同點(diǎn)：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊 的線性表，即受限的線性表，只是對插入、刪除運(yùn)算加以限制。不同點(diǎn)：運(yùn)算規(guī)則不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)行

19、插入、刪除運(yùn)算，因而是后進(jìn)先出表LIFO;隊列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。用途不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場，隊列用于多道作業(yè)處理、指令寄存及其他運(yùn)算等等。2 .試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結(jié)點(diǎn)序歹U。答：DLR: A B D F J G K C E H I L MLDR: B F J D G K A C H E L I MLRD: J F K G D B H L M I E C A3 .假設(shè)正讀和反讀都相同的字符序列為“回文"，例如， abba'和abcba '是回文，a'bcde &#

20、39;和 ababab '則不是回文。假設(shè)一字符序列已存入計算機(jī)，請分析用線性表、 堆棧和隊列等方式正確輸出其回文的可能性？答：線性表是隨機(jī)存儲，可以實現(xiàn)，靠循環(huán)變量（j-）從表尾開始打印輸出；堆棧是后進(jìn)先出，也可以實現(xiàn)，靠正序入棧、逆序出棧即可；隊列是先進(jìn)先出，不易實現(xiàn)。哪種方式最好，要具體情況具體分析。若正文在機(jī)內(nèi)已是順序存儲，則直接用線性表從后往前讀取即可，或?qū)⒍褩ｍ旈_到數(shù)組末尾，然后直接用POP動作實現(xiàn)。（但堆棧是先減后壓還是）若正文是單鏈表形式存儲，則等同于隊列，需開輔助空間，可以從鏈?zhǔn)组_始入棧，全部 壓入后再依次輸出。4 .試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么

21、情況下用順序表比鏈表好？答： 順序存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：存儲密度大（=1?）,存儲空間利用率高。缺點(diǎn)：插入或刪除元素時不方便。鏈?zhǔn)酱鎯r，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針優(yōu)點(diǎn)：插入或刪除元素時很方便，使用靈活。缺點(diǎn)：存儲密度?。?lt;1）,存儲空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表

22、。5 .給定二叉樹的兩種遍歷序列，分別是：前序遍歷序列：D, A, C, E, B, H, F, G, I;中序遍歷序列：D, C, B, E, H, A, G,I, F,試畫出二叉樹 B,并簡述由任意二叉樹 B的前序遍歷序列和中序遍歷序列求二叉樹B的思想方法。解：方法是：由前序先確定 root ,由中序可確定root的左、右子樹。然后由其左子樹的元素 集合和右子樹的集合對應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root ,不斷遞歸，則所有元素都將被唯一確定，問題得解。五、閱讀理解(每小題5分，共20分。至少要寫出思路)已知P結(jié)點(diǎn)，則不必“順藤摸瓜”，直接鏈

23、 接即可。(4) S->next=P->next;(1) P->next=S;答：此題答案不唯一，但若從已給定序列中挑選，則限制頗多。 Q=P； (11) P=L;(8) while(P->next!=Q)P=P->next;(10) P=Q;(4) S->next=P->next;P->next=S;2、答：這是找結(jié)點(diǎn)后繼的程序。共有3處錯誤。注：當(dāng)rtag = 1時說明內(nèi)裝后繼指針，可直接返回，第一句無錯。當(dāng)rtag =0時說明內(nèi)裝右孩子指針，但孩子未必是后繼，需要計算。中序遍歷應(yīng)當(dāng)先左再根再右，所以應(yīng)當(dāng)找左子樹直到葉子處。r=r->l

24、child; 直到LTag=1 ;應(yīng)改為：while(!r-> Ltag)r=r-> Lchild;BiTree InSucc(BiTree q)已知q是指向中序線索二叉樹上某個結(jié)點(diǎn)的指針，本函數(shù)返回指向*q的后繼的指針。r=q->rchild;應(yīng)改為 r=q ;if(!r->rtag)while(!r->rtag)r=r->rchild; / 應(yīng) 改為 while(!r->Ltag) r=r->Lchild;return r;/應(yīng)改為 return r->rchild ;3 .寫出下列程序段的輸出結(jié)果(隊列中的元素類型 QElem Typ

25、e為char)。 void main( )Queue Q; Init Queue (Q);Char x=，e' y=，c，;EnQueue (Q, 'h '); EnQueue (Q, 'r'); EnQueue (Q, y);DeQueue (Q,x); EnQueue (Q,x);DeQueue (Q,x); EnQueue (Q, 'a');while(!QueueEmpty(Q) DeQueue (Q,y);printf(y); ; Printf(x);答：輸出為“char”。4 .簡述以下算法的功能(棧和隊列的元素類型均為int)。void algo3(Queue &Q)Stack S; int d;InitStack(S);wh