(完整word版)數(shù)據(jù)結(jié)構(gòu)習題

1、、選擇題第 1章 概論1. 要求同一邏輯結(jié)構(gòu)的所有數(shù)據(jù)元素具有相同的特性，這意味著（A、數(shù)據(jù)元素具有同一的特點。B、不僅數(shù)據(jù)元素包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)數(shù)據(jù)項的類型要一致。C、每個數(shù)據(jù)元素都一樣。D、數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等。2. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的（ 的（ B ） 和運算的學科。（1） A、操作對象B、計算方法C、邏輯存儲（2） A、結(jié)構(gòu)B、關(guān)系C、運算3. 數(shù)據(jù)結(jié)構(gòu)被形式的定義為 （D , R），其中D是（B） 的有限集合。（ 1 ） A 、算法（2）A、操作4. 在數(shù)據(jù)結(jié)構(gòu)中，c） ）以及它們之間數(shù)據(jù)映象 算法）的有限集合， R 是

2、D 上（ （ D ） ）D、D、A、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)C、線性結(jié)構(gòu)和非線性結(jié)構(gòu)5.A、6.B、數(shù)據(jù)元素C、數(shù)據(jù)操作B、映象C、存儲從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ CB、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)D、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)A ）的存儲結(jié)構(gòu)。C、索引存取D、D、A、線性 -表的順序存儲結(jié)構(gòu)是一種（ 隨機存取B、順序存取算法分析的目的是（ C ） 找出數(shù)據(jù)結(jié)構(gòu)的合理性D、邏輯結(jié)構(gòu) 關(guān)系Hash 存取C、分析算法的效率以求改進 7. 計算機算法指的是（C）（1） A、C、（ 2） A、B、C、D、計算方法 解決某一問題的有限運算序列 可行性、 可行性、 確定性、 易讀性、B、研究算法中的輸入和輸出的關(guān)系D、分析算

3、法的易懂性和文檔性 ）。它必需具備輸入、輸出和（ （B） ）等五個特征。B、排序方法D、調(diào)度方法可移植性和可擴充性確定性和有窮性有窮性和穩(wěn)定性 穩(wěn)定性和安全性8.A、 C、 9.A、線性表若采用鏈表存儲結(jié)構(gòu)時，必須是連續(xù)的B、一定是不連續(xù)的D、在以下的敘述中，正確的是（要求內(nèi)存中可用存儲單元的地址（ 部分地址必須是連續(xù)的 連續(xù)不連續(xù)都可以B ）D）線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈式存儲結(jié)構(gòu) 二維數(shù)組是它的每個數(shù)據(jù)元素為一個線性表的線性表 棧的操作方式是先進先出D、隊列的操作方式是先進后出B、C、10. 根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，以下四類基本的邏輯結(jié)構(gòu)反映了四類基本的21數(shù)據(jù)組織形式。以下解釋錯

4、誤的是(A )A、集合中任何兩個結(jié)點之間都有邏輯關(guān)系但組織形式松散B、 線性結(jié)構(gòu)中結(jié)點按邏輯關(guān)系依次排列形成一條”鎖鏈”C、樹形結(jié)構(gòu)具有分支、層次特性，其形態(tài)有點像自然界中的樹D、圖狀結(jié)構(gòu)中的各個結(jié)點按邏輯關(guān)系互相纏繞，任何兩個結(jié)點都可以鄰接11. 以下說法正確的是(D )A、數(shù)據(jù)元素是數(shù)據(jù)的最小單位B數(shù)據(jù)項是數(shù)據(jù)的基本單位C數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合D數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合二、判斷題1. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。02. 數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。13. 數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素，數(shù)據(jù)項在計算機中的映象分別稱為存儲結(jié)構(gòu)，結(jié)點，數(shù)據(jù)域。14. 數(shù)據(jù)項是數(shù)據(jù)的基本單位。0

5、5. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的。16. 數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)在計算機中實際的存儲形式。17. 算法和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。08. 順序存儲結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)屬于動態(tài)結(jié)構(gòu)。0三、填空題1. 所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)元素之間的邏輯關(guān)系。2. 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括三方面的內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、對數(shù)據(jù)施加的操作。3. 數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合|、線性結(jié)構(gòu)1、樹形結(jié)構(gòu)I和圖狀構(gòu)圖四種類型。4. 在線性結(jié)構(gòu)中，開始結(jié)點 沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有_1個結(jié)點。5.

6、在樹形結(jié)構(gòu)中，樹根結(jié)點只有_1，其余每個結(jié)點有且只有 _1前驅(qū)結(jié)點；葉子結(jié)點沒有后繼結(jié)點，其余每個結(jié)點的后繼結(jié)點可以_任意個 。6. 在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點可以有任意個。7. 算法的五個重要特性是_有窮性、_確定性、_可行性 、一輸入、輸出。8. 下列程序段的時間復雜度是 。for (i=1;i=n ;i+)Aij=0；9. 下列程序段的時間復雜度是 。s=0;for(i=1;i=n ;i+)for(j=1;j=n ;j+) s=s+Bij;sum=s;10. 存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)的物理 實現(xiàn)。11. 從數(shù)據(jù)結(jié)構(gòu)的觀點看，通常所說的”數(shù)據(jù)應(yīng)分成三個不同的層次，即數(shù)據(jù)、_數(shù)據(jù)元

7、素_和_數(shù)據(jù)項_。12根據(jù)需要，數(shù)據(jù)元素又被稱為結(jié)點、 記錄、 元素或_頂點_。13. 通常，存儲結(jié)點之間可以有_順序存儲、鏈式存儲、索引存儲、散列存儲 、四種關(guān)聯(lián)方式，稱為四種基本存儲方式。14. 通常從_正確性、可讀性、健壯性、高效性 、等幾方面評價算法的(包括程序)的質(zhì)量。15. 一個算法的時空性能是指該算法的_時間復雜度 和空間復雜度，前者是算法包含的 _計算量 ，后者是算法需要的_存儲量。16. 在一般情況下，一個算法的時間復雜性是_問題規(guī)模的函數(shù)。17. 常見時間復雜性的量級有：常數(shù)階 0)、對數(shù)階0(_ log 2 n)、線性階0(n)、平方階0(n2)、和指數(shù)階0(2n)。通常

8、認為，具有指數(shù)階量級的算法是_不可行的。18. 數(shù)據(jù)結(jié)構(gòu)的基本任務(wù)是數(shù)據(jù)結(jié)構(gòu)的設(shè)計和 實現(xiàn)。19. 數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合。20. 抽象數(shù)據(jù)類型是指一個數(shù)學模型以及定義在該模型上的一組操作。四、應(yīng)用題1. 分析下列程序段的時間復雜度。i=1 ；WHILE （ i=n ）i=i*2 ；2. 敘述算法定義及其重要特性。3. 簡述下列術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)對象。4. 邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是什么關(guān)系？5. 將數(shù)量級 210，n, n2, n3, nlog2n，log2n，2n， n , n!，2 3 n，n23,按增長率進行排列。6. 設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為：D=k1,k2,k3,

9、 ,k9R=,畫出這個邏輯結(jié)構(gòu)的圖示，并確定相對于關(guān)系 R,哪些結(jié)點是開始結(jié)點，哪些結(jié)點是終端結(jié)點？7. 設(shè)有如圖1.1所示的邏輯結(jié)構(gòu)圖，給出它的邏輯結(jié)構(gòu)，并說出它是什么類型的邏輯結(jié)構(gòu)。8. 分析下列程序的時間復雜度(設(shè) n 為正整數(shù))(1) int rec(int n)if(n=1) return(1);else return(n*rec(n-1);(2) x=91;y=100;while(y0)if(x10) y-;(3) i=1;j=0;while(i+jj) j+; else i+;(4) x=n;y=0; while(x=(y+1)*(y+1) y+;9. 設(shè) n 為正數(shù)。試確定下列

10、各程序段中前置以記號的語句的頻度：( 1) i=1;k=0;while(i=n-1) k+=10*i; i+;(2) k=0;for(i=1;i=n;i+)for(j=i;jnext=NULLC、head-next=headD 、 head!=NULL10.非空循環(huán)單鏈表head的尾結(jié)點*p滿足（C）A、p-next=NULLB 、 p=NULLC、p-next=headD、 p=head11.在循環(huán)雙鏈表的*p 結(jié)點之后插入 *s 結(jié)點的操作是（D ）A 、 p-next=s; s-prior=p; p-next-prior=s; s-next=p-next;B 、 p-next=s; p-

11、next-prior=s; s-prior=p; s-next=p-next;C、 s-prior=p; s-next=p-next;p-next：=s; p-next-prior=s;D 、 s-prior =p; snext=pnext; pnext-prior =s;p-next=s;12. 在一個單鏈表中，已知*q結(jié)點是*p結(jié)點的前驅(qū)結(jié)點，若在*q和*p之間插入結(jié)點*s，則 執(zhí)行（ C ）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;13. 在

12、一個單鏈表中，若*p結(jié)點不是最后結(jié)點，在*p之后插入結(jié)點*s，則執(zhí)行（B ）A 、s-next=p;p-next=s;B、s-next=p-next; p-next=s;C、s-next= p-next; p=s;D 、 p-next=s; s-next=p;14. 若某線性表中最常用的操作是取第 i 個元素和找第 i 個元素的前趨元素，則采用（ A ）存儲方式最節(jié)省時間。A、順序表B、單鏈表C、雙鏈表D、單循環(huán)鏈表15. 設(shè) rear 是指向非空帶頭結(jié)點的循環(huán)單鏈表的尾指針，則刪除表中第一元素的操作可表 示為( D )A 、 p=rear; rear=rear-next; free(p)B

13、、 rear=rear-next; free(rear);C、 rear=rear-next-next;free(rear);D 、 p=rear-next-next;rear-next-next=p-next;free(p);16. 在一個單鏈表中，若刪除 *p 結(jié)點的后繼結(jié)點，則執(zhí)行( A )A、 q=pf next; pnext=q next; free(q);B、p=p-next; p-next= p-next-next;free(p);C、p-next= p-next;free(p-next);D、p= p-next-next;free(p-next);17. 設(shè)指針 P 指向雙鏈表

14、的某一結(jié)點，則雙鏈表結(jié)構(gòu)的對稱性可用( C )式來刻畫A 、 p-prior-next=p-next-nextB、p-prior-prior=p-next-priorC、p-prior-next=p-next-priorD、p-next-next=p-prior-prior18. 在循環(huán)鏈表中，將頭指針改設(shè)為尾指針 rear 后，其頭結(jié)點和尾結(jié)點的存儲位置分別是 ( B )A 、 rear 和 rear-next-nextB、rear-next 和 rearC、rear-next-next 和 rearD、rear 和 rear-next19. 循環(huán)鏈表主要優(yōu)點是( D )A、不再需要頭指針了

15、B、已知某個結(jié)點的位置后，能夠容易找到它的直接前趨C、在進行插入、刪除運算時，能更好地保證鏈表不斷開D、從表中任一結(jié)點出發(fā)都能掃描到整個鏈表20. 在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費時間最少的是( D )A、單鏈表B、雙鏈表C、循環(huán)鏈表D、順序表二、判斷題1. 順序存儲的線性表可以隨機存取。 A2. 順序存儲的線性表的插入和刪除操作不需要付出很大的代價，因為平均每次操作只有近一半的元素需要移動。 B3. 線性表中的元素可以是各種各樣的， 但同一線性表中的數(shù)據(jù)元素具有相同的特性， 因此 是屬于同一數(shù)據(jù)對象。 A4. 在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上不一定相鄰。B5.

16、 在線性表的鏈式存儲結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。A6. 在單鏈表中，可以從頭結(jié)點進行查找任何一個元素。 A7. 線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。 B8. 在線性表的順序存儲結(jié)構(gòu)中， 插入和刪除元素時， 移動元素的個數(shù)與該元素的位置有關(guān)。A9. 在單鏈表中，要取得某個元素， 只要知道該元素的指針即可， 因此，單鏈表是隨機存取10.1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.1.的存儲結(jié)構(gòu)。B順序存儲方式只能用于存儲線性結(jié)構(gòu)。B填空題為了便于討論，有時將含 n(n0)個結(jié)點的線性結(jié)構(gòu)表示成(a1, a2,an)，其中每個

17、 ai 代表一個_結(jié)點 。a1稱為_第一個 結(jié)點，an稱為_最后一個 結(jié)點，i稱為 ai在線性表中的 位置。對任意一對相鄰結(jié)點 ai、a十1(K in),ai稱為ai十1的直接前驅(qū), a十1稱為 ai的直接_后繼。線性結(jié)構(gòu)的基本特征是：若至少含有一個結(jié)點，則除起始結(jié)點沒有直接_前驅(qū)外，其他結(jié)點有且僅有一個直接 _前驅(qū)_;除終端結(jié)點沒有直接_后繼外，其它結(jié)點有且僅有一個直接后繼.所有結(jié)點按1對1的鄰接關(guān)系構(gòu)成的整體就是線性_結(jié)構(gòu)。線性表的邏輯結(jié)構(gòu)是_線性結(jié)構(gòu)。其所含結(jié)點的個數(shù)稱為線性表的_長度。在單鏈表中，刪除 p所指結(jié)點的直接后繼的操作是_ q=ptnext; p宀next=q宀next;fr

18、ee(q);。非空的循環(huán)單鏈表 head的尾結(jié)點(由指針 p所指)滿足 _ p next=head。rear是指向非空帶頭結(jié)點的循環(huán)單鏈表的尾指針，則刪除起始結(jié)點的操作可表示為_p=rearT n ext; q=p t n ext;p t n ext=q t n ext; free(q)。對于一個具有 n個結(jié)點的單鏈表，在p所指結(jié)點后插入一個結(jié)點的是時間復雜度為，在給定值為x的結(jié)點后插入新結(jié)點的時間復雜度為 。單鏈表表示法的基本思想是用指針表示結(jié)點間的邏輯關(guān)系。在順序表中插入或刪除一個元素，需要平均移動一半元素，具體移動的元素個數(shù)與_兀素位置有天。向一個長度為n的向量的第i個元素(1 i n+

19、1)之前插入一個元素時，需向后移動n - i+1個元素。向一個長度為n的向量中刪除第i個元素(1 inext=head后，該單 鏈表構(gòu)成單循環(huán)鏈表 。在單鏈表中，若 p和s是兩個指針，且滿足p-next與s相同，則語句p-next=s-next作用是一刪除s指向的結(jié)點。設(shè)r指向單循環(huán)鏈表的最后一個結(jié)點，要在最后一個結(jié)點之后插入s所指的結(jié)點，需執(zhí)行的三條語句是 _ st next=r-next; r-next=s; r=s;。在單鏈表中，指針 p所指結(jié)點為最后一個結(jié)點的條件是_ pt next=NULL。在雙循環(huán)鏈表中，若要在指針p所指節(jié)點前插入s所指的節(jié)點，則需執(zhí)行下列語句：s_next=p

20、;s_prior=p_prior ;_ pt prior t next=s ;p-prior=s ;20. 在單鏈表中的 p 所指結(jié)點之前插入一個 s 所指結(jié)點時，可進行下列操作： s-next= ；p-next=s;temp=p-data； p-data=；s-data=；四、應(yīng)用題1. 描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，首元結(jié)點(第一個元素結(jié)點) 。2. 何時選用順序表、何時選用鏈表作為線性表的存儲結(jié)構(gòu)為宜？3. 在順序表中插入和刪除一個結(jié)點需平均移動多少個結(jié)點？具體的移動次數(shù)取決于哪兩 個因素？4. 為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好？5. 雙鏈表和單循環(huán)鏈表中， 若僅

21、知道指針 p 指向某個結(jié)點， 不知道頭指針， 能否將結(jié)點 *p 從相應(yīng)的鏈表中刪除？若可以，其時間復雜度各為多少？6. 下列算法的功能是什么？ LinkedList test1(LinkedList L) /L 是無頭結(jié)點的單鏈表 ListNode *q , *p;if(L&L-next)q=L ; L=L-next; p=L; while(p-next) p=p-next; p-next=q; q-next=NULL;return L;7. 如果有 n 個線性表同時共存， 并且在處理過程中各表的長度會發(fā)生動態(tài)變化， 線性表的 總長度也會自動地改變。在此情況下，應(yīng)選擇哪一種存儲結(jié)構(gòu)。為什么？8

22、. 若線性表的總數(shù)基本穩(wěn)定， 且很少進行插入刪除操作， 但要求以最快的方式存取線性表 的元素，應(yīng)該用哪種存儲結(jié)構(gòu)。為什么？9. 設(shè)有多項式 a(x)=9+8x+9x 4+5x10 b(x)=-2x+22x 7-5x 10 ( 1) 用單鏈表給出 a(x)、b(x) 的存儲表示；(2) 設(shè)c (x)=a(x)+b(x)，求得c(x)并用單鏈表給出其存儲表示。第 3章 棧和隊列、選擇題1. 設(shè)有一順序棧S,元素 s1,s2,s3,s4,s5,s6依次進棧，如果 6個元素出棧的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應(yīng)該是(b )A 、 2B 、 3C、 5D、 62. 若一個棧的輸

23、入序列是a,b,c，則通過入、出棧操作可能得到a,b,c的不同排列個數(shù)為0maxsize-1a1a2a3(b )A、4B、5C、63.設(shè)有一順序棧已經(jīng)含有3個兀素，如圖的出棧序列是(a)A、a3,a1,a4,a2B、a3,a2,a4,a1D、73.1所示元素a4正等待進棧。下列不可能出現(xiàn)C、a3,a4,a2,a1D、a4,a3,a2,a1Top圖3.14. 鏈棧和順序棧相比，有一個比較明顯的優(yōu)勢是(a )A、通常不會出現(xiàn)棧滿的情況B、通常不會出現(xiàn)棧空的情況C、插入操作更容易實現(xiàn)D、刪除操作更加容易實現(xiàn)5. 若一個棧的輸入序列是1,2,3,4,n，輸出序列的第一個元素是n,則第i個輸出元素是(c

24、 )A、不確定B、 n-iC、n-i+1D、n-i-16. 以下說法正確的是(a )A、 因鏈棧本身沒有容量限制，故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧滿情況B、 因順序棧本身沒有容量限制，故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧滿情況C、對于鏈棧而言，在棧滿狀態(tài)下，如果此時再作進棧運算，則會發(fā)生“上溢”D、 對于順序棧而言在棧滿狀態(tài)下如果此時再作進棧運算，則會發(fā)生“下溢”。7. 順序隊列的入隊操作應(yīng)為( a )A、sq.rear=sq.rear+1; sq.datasq.rear=x;B、sq.datasq.rear=x; sq.rear=sq.rear+1;C、sq.rear=(sq.rear+1)

25、% maxsize; sq.datasq.rear=x;D、sq.datasqrear=x; sq.rear=(sq.rear+1)% maxsize;8. 循環(huán)隊列的入隊操作應(yīng)為( c )A、sq.rear=sq.rear+1; sq.datasq.rear=xB、sq.datasq.rear=x;sq.rear=sq.rear+1;C、sq.rear=(sq.rear+1)% maxsiae; sq.datasq.rear=x;D、sq.datasq.rear=x; sq.rear=(sq.rear+1)% maxsize;9. 順序隊列的出隊操作為(b )A、sq.front=(sq.f

26、ront+1)% maxsize ;B 、sq.front=sq.front+1 ;C、sq.rear=(sq.rear+1)% maxsize ;D、sq.rear=sq.rear+1 ;10. 循環(huán)隊列的出隊操作為(a )A、sq.front=(sq.front+1)% maxsize ;B 、sq.front=sq.front+1 ;C、sq.rear=(sq.rear+1)% maxsize ;D、sq.rear=sq.rear+1;11. 循環(huán)隊列的隊滿條件為(c )A、(sq.rear+1) % maxsize = =(sq.fr on t+1) % maxsize;B、(sq.r

27、ear+1) % maxsize = =sq.front+1C 、 (sq.rear+1) % maxsize = =sq.frontD 、 sq.rear = =sq.front12. 循環(huán)隊列的隊空條件為( d )A 、 (sq.rear+1) % maxsize = =(sq.front+1) % maxsize ；B 、 (sq.rear+1) % maxsize = =sq.front+1 ；C 、 (sq.rear+1) % maxsize = =sq.front ；,則退棧操作時（ c ） B 、判別棧元素的類型 D、 對棧不做任何判別D 、 sq.rear = = sq.fro

28、nt ；13. 如果以鏈表作為棧的存儲結(jié)構(gòu) A 、必須判別棧是否滿C、必須判別棧是否空14. 向一個棧頂指針為 Top 的鏈棧中插入一個 s 所指結(jié)點時，其操作步驟為（ c ）A 、 Top-next=s;B 、s-next=Top-next;Top-next=s;C 、 s-next=Top;Top=s; D 、 s-next=Top;Top=Top-next;15. 從棧頂指針為 Top 的鏈棧中刪除一個結(jié)點， 并將被刪節(jié)點的值保存到 x 中，其操作步驟 為（ a ）A 、 x=Top-data;Top=Top-next;B 、 Top=Top-next;x=Top-data;C 、 x=

29、Top;Top=Top-next;D 、 x=Top-data;16. 在一個鏈隊中，若 f,r 分別為隊首、隊尾指針，則插入s 所指結(jié)點的操作為（b ）A 、 f-next=s;f=s; B 、 r-next=s;r=s;C 、 s-next=r;r=s;D 、 s-next=f;f=s;17. 一個棧的入棧序列是a,b,c,d,e則棧的不可能的輸出序列是( c )A 、 e d c b aB、 d e c b aC、 d c e a bD、 a b c d eD 、 3，2，4，1 ）數(shù)據(jù)結(jié)構(gòu)最佳。18. 一個隊列的入隊序列是1，2，3，4，則隊列的可能的輸出系列是（b ）A、4，3，2，

30、1B、 1，2，3，4C、 1，4，3，219. 設(shè)計一個判別表達式中左、 右括號是否配對出現(xiàn)的算法， 采用（ bA、線性表的順序存儲結(jié)構(gòu)B、棧C 、隊列D、線性表的鏈式存儲結(jié)構(gòu)20. 若以 1234 作為雙端隊列的輸入序列，則既不能由輸入受限雙端隊列得到，也不能由輸 出受限雙端隊列得到的輸出序列是（ c ）A、 1234B、 4132 C、 4231 D、 4213二、判斷題1. 在順序棧棧滿情況下，不能做進棧運算，否則會產(chǎn)生“上溢” 。 a2. 鏈棧與順序棧相比的一個優(yōu)點是鏈棧插入和刪除操作更加方便。b3. 若一個棧的輸入序列為1,2, 3,，n,其輸出序列的第一個元素為n,則其輸出序列的

31、每個元素 ai 一定滿足 ai=i+1（i=1,2,n）。b4. 在鏈隊列中,即使不設(shè)置尾指針也能進行入隊操作。a5. 在對鏈隊列（帶頭指針）做出隊操作時,不會改變front 指針的值。 a6. 循環(huán)隊列中元素個數(shù)為 rear- front 。 b7. 一個棧的輸入序列是 1,2,3,4,則在棧的輸出序列中可以得到4,3,1,2。 b8. 一個棧的輸入序列是 1,2,3,4,則在棧的輸出序列中可以得到1,2,3,4。 a9. 若以鏈表作為棧的存儲結(jié)構(gòu),則進棧需要判斷棧是否滿。b10. 若以鏈表作為棧的存儲結(jié)構(gòu),則出棧需要判斷棧是否空。a填空題1. 向一個棧頂指針為Top的鏈棧中插入一個s所指的

32、結(jié)點時，其進行的操作是_s-n ext=Top; Top=s。2. 從棧頂指針為 Top的鏈棧中刪除一個結(jié)點，并將結(jié)點保存在x中，進行的操作是_x=Top-data;。在具有n個單元的循環(huán)隊列中，隊滿時共有_ n-1個元素。3. 假設(shè)以S和X分別表示進棧和退棧操作，則對輸入序列 a,b,c,d,e進行一系列棧操作SSXSXSSXXX 之后，得到的輸出序列為b c e d a。4. 設(shè)有數(shù)組A0.m作為循環(huán)隊列的存儲空間，front為隊頭指針，rear為隊尾指針，則元素 x 執(zhí)行入隊操作的 語句是_if(rear+1)%(m+1)!=front)rear=(rear+1) % (m+1);Are

33、ar=x; 。5. 在一個鏈隊列中，如f,r分別為隊首，隊尾指針，貝U插入s所指結(jié)點的操作是 _ r-next=s;r=s;。6. 棧的邏輯特點是后進先出 ,隊列的邏輯特點是_先進先出 ,二者共同特點是操作受限。a) _?？梢宰鳛閷崿F(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。b) 在隊列中，新插入的結(jié)點只能添加到隊尾7.鏈隊在一定范圍內(nèi)不會出現(xiàn)隊滿的情況。當lq.front= =lq.rear時，隊中無兀素，此時隊空。8. 設(shè)一個鏈棧的棧頂指針為ls，棧中結(jié)點的格式為| data next ，?？盏臈l件是;如果棧不為空，則退棧操作為p=ls;free(p)。9. 對帶有頭結(jié)點的鏈隊列l(wèi)q,判定隊列中只有一個

34、數(shù)據(jù)元素的條件是 。10. 設(shè)有一個空棧，現(xiàn)在輸入序列為1, 2, 3, 4, 5,經(jīng)過push, push, pop, push, pop,push，后棧頂指針所指元素是 411. 設(shè)用一維數(shù)組 A1.n來表示一個棧，令An為棧底。用整型變量t來指示當前棧頂?shù)奈恢茫珹t為棧頂元素。往棧中壓入一個新元素時，變量t的值減1，從棧中彈出一個元素時，變量t的值加1。設(shè)空棧時，有輸入序列a,b,c經(jīng)過push,pop, push, push, pop操作后，從棧中彈出的元素是 c四、應(yīng)用題1. 試證明：若借助棧由輸入序列 1, 2, 3,n得到輸出序列p1, p2,pn(它 是輸入序列的一個排列)，則

35、在輸出序列中不可能出現(xiàn)這樣的情形： 存在著ijk,使pipj1) printf(i-);10. 試將下列遞歸過程改寫為非遞歸過程void digui(int *sum)scanf(x);if(x=0) sum=0;else digui(sum);sum+=x; printf(sum);第 4章 串一、 選擇題1. 串是一種特殊的線性表,其特殊性表現(xiàn)在（ b ）A、可以順序存儲B、數(shù)據(jù)元素是一個字符C可以鏈接存儲B、數(shù)據(jù)元素可以是多個字符2. 設(shè)有兩個串P和Q求Q在P中首次出現(xiàn)的位置的運算稱為（b ）A、連接 B、模式匹配C 、求子串D、求串長3. 設(shè)串 S仁ABCDEFG，S2= PQRST，

36、函數(shù)StringConeat（X，Y）返回 X和 Y 串的連接串，SubString （ S，I，J）返回串S的從序號I的字符開始的J個字符組成的子串，StringLength （ S）返回串 S 的長度，貝U StringConeat （ SubString （ S1，2, StringLength( S2)， SubString ( S1， StringLength (S2)， 2)的結(jié)果串是( d )。 A、 BCDEFB 、 BCDEFG C 、BCDQRST D 、BCDEFEF、判斷題1 子串定位函數(shù)的時間復雜度在最壞的情況下為O（n*m ），因此子串定位函數(shù)沒有實際利用價值。 b

37、2. 設(shè)有兩個串p和q,其中q是p的子串，把q在p中首次出現(xiàn)的位置作為子串 q在p中 的位置的算法稱為匹配。 a3. KMP 算法的最大特點是指示主串的指針不需要回朔。 a三、填空題1. 兩個串相等的充分必要條件是_兩個串長度相等且各個對應(yīng)位置的字符也相等。2. 空串是_零個字符的串 ,其長度等于 _0。3. 空格串是 _有一個或多個空格組成的串 ,其長度等于 _串中空格字符的個數(shù)4.設(shè) S= 1 T AMT AT TEACHER，其長度是_14_。5.設(shè) S1= GOOD， S2=T， S3= BYE！,則S1, S2 和S3連接后的結(jié)果是_ GOODT BYE 。6.設(shè)有兩個串q和p,求q

38、在p中首次出現(xiàn)的算法叫_匹配 _。7.串的連接運算不滿足 _交換律 ,滿足 _結(jié)合律 _。8.模式串 t= abcaabbcabcabcaabdab的next 函數(shù)值為 _0111223112345。四、應(yīng)用題1. 空串和空格串有何區(qū)別？字符串中的空格符有什么意義？空串在串處理中有何作用？2. 字符串 s1=abcdefghijklmnopqrstuvw ,由如下運算分別得到 s2 和 s3 ,請給出 s2 和 s3 的值。s2=StringConcat(SubString(s1,19,3),SubString(s1,4,2),SubString(s1,14,1),SubString(s1,2

39、0,1) , s3=SubString(s1, StringLength(s2), StringLength(s2)3. 設(shè) a,b,c,d 都是串，a= this is a book ,b= ese are ,c= s。求d=StringConcat(SubString(a,1,2),b,SubString(a,10,5),c)的值。4. 知 s= (xyz)* , t= (x+y)*z 。試用連接,求子串和置換等基本運算,將 s 轉(zhuǎn)化為 t ,將 t 轉(zhuǎn)化為 s 。5.令 s= aaab ,t= abcabaa ,u= abcaabbabca baacbacba。分另U求出 s,t,u 的

40、 next 函數(shù)值和 nextval 函數(shù)值。6. 設(shè) s= 11 AMTLSTUDENT,t= GOOD, q= WORKED。求 ： StringLength(s), StringLength(t),SubString(s,8,7),SubString(t,2,1),Index(s, A ), Index(s,t),StringConcat(SubString(s,6,2),StringConcat(t,SubString(s,7,8)7. 已知下列字符串a(chǎn)= THIS，f= ATSAMPLE，c= GOOD，d= NE，b=T，g= ISs=StringConcat(a,StringCo

41、ncat(SubString(f,2,7),StringConcat(b,SubString(a,3,2) ， t=Replace(f,SubString(f,3,6),c)， u=StringConcat(SubString(c,3,1),d)v=StringConcat(s,StringConcat(b,StringConcat(t,StringConcat(b,u)試問： s，t ， v ， StringLength(s) ， Index(v,g) ， Index(u,g) 各是什么？8. 已知模式串 pat= ADABBADADA, 寫出模式串的 nextval 函數(shù)值。9. 計算下列

42、串的 next 值：( 1) aaabcaaba( 2) abcabcacb( 3) babbabab第 5章 數(shù)組和廣義表一、 選擇題1. 數(shù)組通常具有的兩種基本操作是（ c ）A、建立和刪除B、索引和修改C、查找和修改D、查找和索引2. 二維數(shù)組 A10.20,5.10 采用行序為主序方式存儲，每個數(shù)據(jù)元素占4 個存儲單元，且A10 ， 5的存儲地址是 1000，則 A18,9 的存儲地址是（ a ）A、 1208 B、 1212C、 1368 D、 13643. 三維數(shù)組 A0.4,0.5,0.6 ，采用行序為主序方式存儲，每個數(shù)據(jù)元素占2 個存儲單元，且第一個元素的存儲地址是 120，

43、則 A3,4,5 的存儲地址是（ a ）A、 438 B、 358 C、 360 D、 3624. 二維數(shù)組 A 中，每個元素的長度為 4個字節(jié)，行下標從 0到 4，列下標從 0到 5，A 按 行優(yōu)先存儲時元素 A3,5 的地址與 A 按列優(yōu)先存儲時元素（ b ）的地址相同。A、 A2,4B、 A3,4 C、 A3,5D、 A4,45.對矩陣壓縮存儲是為了（ bA、方便運算B、節(jié)省空間）C、方便存儲D、提高運算速度6.稀疏矩陣一般的壓縮存儲方法有兩種，即（c）A 、二元數(shù)組和三元數(shù)組B、三元組和散列C、二兀組和十字鏈表D 、散列和十字鏈表7.廣義表（a）,a）的表頭是（b）A、 aB、 (a)

44、C、 ( )D、 (a)8.廣義表（a）的表尾是（c ）A、 aB、 (a)C、 ( )D、 (a)9.已知廣義表 LS = (a,b,c),(d,e,f)，運用GetHead和GetTail函數(shù)取出LS中的兀素e的運算是（ c）A、 GetHead(GetTail(LS)B 、 GetTail(GetHead(LS)C、 GetHead(GetTail(GetHead(GetTail(LS)D 、 GetHead(GetTail(GetTail(GetHead(LS)10. 若廣義表 A 滿足 GetHead(A)=GetTail(A) ，則 A 為( b )A、 ( ) B、 ( )C、

45、( ),( ) D、 ( ),( ),( )、判斷題1 數(shù)組是同類型值的集合。 b2 數(shù)組的存儲結(jié)構(gòu)是一組連續(xù)的內(nèi)存單元。 a3. 數(shù)組是一種復雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系，即不是線性的也不是樹形的。b4. 插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也會經(jīng)常使 用。b5. 使用三元組表表示稀疏矩陣的元素，有時并不能節(jié)省存儲空間。a6. 廣義表是由零個或多個原子或子表所組成的有限序列，所以廣義表可能為空表。a7. 線性表可以看成是廣義表的特例，如果廣義表中的每個元素是原子，則廣義表便成為線性表。a& 廣義表中原子個數(shù)即為廣義表的長度。b9. 廣義表中元素的個數(shù)即為廣義表的深度。b三、填空題1. 二維數(shù)組 A1.1O, 1.20采用列序為主序方式存儲，每個元素占一個存儲單元，并且A1,1的存儲地址是 200,則A6,12的地址是 315。2. 有一個10階對稱矩陣A采用壓縮存儲方式(以行序為主序方式存儲)存儲其下三角元素，且第一個元素A1,1的存儲地址為1,則A4,5的地址是_14, A8,3的地址是 31。3.下三角矩陣 A1.N,1.N的下三角元素已壓縮到一維數(shù)組S1.N* ( N+1 ) /2+1中，若按行序為主序存儲，則 Ai,j對應(yīng)的 S 中的存儲位置是i(i 1).cJ J當i jk2kN(N 1)1,當ij2002030004.已知一個