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

1、、選擇題第 1章 概論1. 要求同一邏輯結(jié)構(gòu)的所有數(shù)據(jù)元素具有相同的特性，這意味著（A、數(shù)據(jù)元素具有同一的特點(diǎn)。B、不僅數(shù)據(jù)元素包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對應(yīng)數(shù)據(jù)項(xiàng)的類型要一致。C、每個(gè)數(shù)據(jù)元素都一樣。D、數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等。2. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的（ 的（ B ） 和運(yùn)算的學(xué)科。（1） A、操作對象B、計(jì)算方法C、邏輯存儲（2） A、結(jié)構(gòu)B、關(guān)系C、運(yùn)算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、動(dòng)態(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)是一種（ 隨機(jī)存取B、順序存取算法分析的目的是（ C ） 找出數(shù)據(jù)結(jié)構(gòu)的合理性D、邏輯結(jié)構(gòu) 關(guān)系Hash 存取C、分析算法的效率以求改進(jìn) 7. 計(jì)算機(jī)算法指的是（C）（1） A、C、（ 2） A、B、C、D、計(jì)算方法 解決某一問題的有限運(yùn)算序列 可行性、 可行性、 確定性、 易讀性、B、研究算法中的輸入和輸出的關(guān)系D、分析算

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

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

5、5. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的。16. 數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)在計(jì)算機(jī)中實(shí)際的存儲形式。17. 算法和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。08. 順序存儲結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)屬于動(dòng)態(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é)點(diǎn) 沒有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有_1個(gè)結(jié)點(diǎn)。5.

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

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

8、認(rèn)為，具有指數(shù)階量級的算法是_不可行的。18. 數(shù)據(jù)結(jié)構(gòu)的基本任務(wù)是數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)和 實(shí)現(xiàn)。19. 數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合。20. 抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。四、應(yīng)用題1. 分析下列程序段的時(shí)間復(fù)雜度。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,按增長率進(jìn)行排列。6. 設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為：D=k1,k2,k3,

9、 ,k9R=,畫出這個(gè)邏輯結(jié)構(gòu)的圖示，并確定相對于關(guān)系 R,哪些結(jié)點(diǎn)是開始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)？7. 設(shè)有如圖1.1所示的邏輯結(jié)構(gòu)圖，給出它的邏輯結(jié)構(gòu)，并說出它是什么類型的邏輯結(jié)構(gòu)。8. 分析下列程序的時(shí)間復(fù)雜度(設(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é)點(diǎn)*p滿足（C）A、p-next=NULLB 、 p=NULLC、p-next=headD、 p=head11.在循環(huán)雙鏈表的*p 結(jié)點(diǎn)之后插入 *s 結(jié)點(diǎn)的操作是（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. 在一個(gè)單鏈表中，已知*q結(jié)點(diǎn)是*p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在*q和*p之間插入結(jié)點(diǎn)*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、一個(gè)單鏈表中，若*p結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在*p之后插入結(jié)點(diǎn)*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 個(gè)元素和找第 i 個(gè)元素的前趨元素，則采用（ A ）存儲方式最節(jié)省時(shí)間。A、順序表B、單鏈表C、雙鏈表D、單循環(huán)鏈表15. 設(shè) rear 是指向非空帶頭結(jié)點(diǎn)的循環(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. 在一個(gè)單鏈表中，若刪除 *p 結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(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é)點(diǎn)，則雙鏈表結(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é)點(diǎn)和尾結(jié)點(diǎn)的存儲位置分別是 ( B )A 、 rear 和 rear-next-nextB、rear-next 和 rearC、rear-next-next 和 rearD、rear 和 rear-next19. 循環(huán)鏈表主要優(yōu)點(diǎn)是( D )A、不再需要頭指針了

15、B、已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到它的直接前趨C、在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好地保證鏈表不斷開D、從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表20. 在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費(fèi)時(shí)間最少的是( D )A、單鏈表B、雙鏈表C、循環(huán)鏈表D、順序表二、判斷題1. 順序存儲的線性表可以隨機(jī)存取。 A2. 順序存儲的線性表的插入和刪除操作不需要付出很大的代價(jià)，因?yàn)槠骄看尾僮髦挥薪话氲脑匦枰苿?dòng)。 B3. 線性表中的元素可以是各種各樣的， 但同一線性表中的數(shù)據(jù)元素具有相同的特性， 因此 是屬于同一數(shù)據(jù)對象。 A4. 在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上不一定相鄰。B5.

16、 在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。A6. 在單鏈表中，可以從頭結(jié)點(diǎn)進(jìn)行查找任何一個(gè)元素。 A7. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。 B8. 在線性表的順序存儲結(jié)構(gòu)中， 插入和刪除元素時(shí)， 移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。A9. 在單鏈表中，要取得某個(gè)元素， 只要知道該元素的指針即可， 因此，單鏈表是隨機(jī)存取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填空題為了便于討論，有時(shí)將含 n(n0)個(gè)結(jié)點(diǎn)的線性結(jié)構(gòu)表示成(a1, a2,an)，其中每個(gè)

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

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

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

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

21、知道指針 p 指向某個(gè)結(jié)點(diǎn)， 不知道頭指針， 能否將結(jié)點(diǎn) *p 從相應(yīng)的鏈表中刪除？若可以，其時(shí)間復(fù)雜度各為多少？6. 下列算法的功能是什么？ LinkedList test1(LinkedList L) /L 是無頭結(jié)點(diǎn)的單鏈表 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 個(gè)線性表同時(shí)共存， 并且在處理過程中各表的長度會(huì)發(fā)生動(dòng)態(tài)變化， 線性表的 總長度也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選擇哪一種存儲結(jié)構(gòu)。為什么？8

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

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

24、 )A、不確定B、 n-iC、n-i+1D、n-i-16. 以下說法正確的是(a )A、 因鏈棧本身沒有容量限制，故在用戶內(nèi)存空間的范圍內(nèi)不會(huì)出現(xiàn)棧滿情況B、 因順序棧本身沒有容量限制，故在用戶內(nèi)存空間的范圍內(nèi)不會(huì)出現(xiàn)棧滿情況C、對于鏈棧而言，在棧滿狀態(tài)下，如果此時(shí)再作進(jìn)棧運(yùn)算，則會(huì)發(fā)生“上溢”D、 對于順序棧而言在棧滿狀態(tài)下如果此時(shí)再作進(jìn)棧運(yùn)算，則會(huì)發(fā)生“下溢”。7. 順序隊(duì)列的入隊(duì)操作應(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)隊(duì)列的入隊(duì)操作應(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. 順序隊(duì)列的出隊(duì)操作為(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)隊(duì)列的出隊(duì)操作為(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)隊(duì)列的隊(duì)滿條件為(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)隊(duì)列的隊(duì)空條件為( 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 ；,則退棧操作時(shí)（ c ） B 、判別棧元素的類型 D、 對棧不做任何判別D 、 sq.rear = = sq.fro

28、nt ；13. 如果以鏈表作為棧的存儲結(jié)構(gòu) A 、必須判別棧是否滿C、必須判別棧是否空14. 向一個(gè)棧頂指針為 Top 的鏈棧中插入一個(gè) s 所指結(jié)點(diǎn)時(shí)，其操作步驟為（ 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 的鏈棧中刪除一個(gè)結(jié)點(diǎn)， 并將被刪節(jié)點(diǎn)的值保存到 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. 在一個(gè)鏈隊(duì)中，若 f,r 分別為隊(duì)首、隊(duì)尾指針，則插入s 所指結(jié)點(diǎn)的操作為（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. 一個(gè)棧的入棧序列是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. 一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則隊(duì)列的可能的輸出系列是（b ）A、4，3，2，

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

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

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

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

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

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ù)元素是一個(gè)字符C可以鏈接存儲B、數(shù)據(jù)元素可以是多個(gè)字符2. 設(shè)有兩個(gè)串P和Q求Q在P中首次出現(xiàn)的位置的運(yù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個(gè)字符組成的子串，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ù)的時(shí)間復(fù)雜度在最壞的情況下為O（n*m ），因此子串定位函數(shù)沒有實(shí)際利用價(jià)值。 b

37、2. 設(shè)有兩個(gè)串p和q,其中q是p的子串，把q在p中首次出現(xiàn)的位置作為子串 q在p中 的位置的算法稱為匹配。 a3. KMP 算法的最大特點(diǎn)是指示主串的指針不需要回朔。 a三、填空題1. 兩個(gè)串相等的充分必要條件是_兩個(gè)串長度相等且各個(gè)對應(yīng)位置的字符也相等。2. 空串是_零個(gè)字符的串 ,其長度等于 _0。3. 空格串是 _有一個(gè)或多個(gè)空格組成的串 ,其長度等于 _串中空格字符的個(gè)數(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è)有兩個(gè)串q和p,求q

38、在p中首次出現(xiàn)的算法叫_匹配 _。7.串的連接運(yùn)算不滿足 _交換律 ,滿足 _結(jié)合律 _。8.模式串 t= abcaabbcabcabcaabdab的next 函數(shù)值為 _0111223112345。四、應(yīng)用題1. 空串和空格串有何區(qū)別？字符串中的空格符有什么意義？空串在串處理中有何作用？2. 字符串 s1=abcdefghijklmnopqrstuvw ,由如下運(yùn)算分別得到 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 。試用連接,求子串和置換等基本運(yùn)算,將 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. 計(jì)算下列

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

43、則 A3,4,5 的存儲地址是（ a ）A、 438 B、 358 C、 360 D、 3624. 二維數(shù)組 A 中，每個(gè)元素的長度為 4個(gè)字節(jié)，行下標(biāo)從 0到 4，列下標(biāo)從 0到 5，A 按 行優(yōu)先存儲時(shí)元素 A3,5 的地址與 A 按列優(yōu)先存儲時(shí)元素（ b ）的地址相同。A、 A2,4B、 A3,4 C、 A3,5D、 A4,45.對矩陣壓縮存儲是為了（ bA、方便運(yùn)算B、節(jié)省空間）C、方便存儲D、提高運(yùn)算速度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)，運(yùn)用GetHead和GetTail函數(shù)取出LS中的兀素e的運(yùn)算是（ 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ù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系，即不是線性的也不是樹形的。b4. 插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也會(huì)經(jīng)常使 用。b5. 使用三元組表表示稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲空間。a6. 廣義表是由零個(gè)或多個(gè)原子或子表所組成的有限序列，所以廣義表可能為空表。a7. 線性表可以看成是廣義表的特例，如果廣義表中的每個(gè)元素是原子，則廣義表便成為線性表。a& 廣義表中原子個(gè)數(shù)即為廣義表的長度。b9. 廣義表中元素的個(gè)數(shù)即為廣義表的深度。b三、填空題1. 二維數(shù)組 A1.1O, 1.20采用列序?yàn)橹餍蚍绞酱鎯?，每個(gè)元素占一個(gè)存儲單元，并且A1,1的存儲地址是 200,則A6,12的地址是 315。2. 有一個(gè)10階對稱矩陣A采用壓縮存儲方式(以行序?yàn)橹餍蚍绞酱鎯?存儲其下三角元素，且第一個(gè)元素A1,1的存儲地址為1,則A4,5的地址是_14, A8,3的地址是 31。3.下三角矩陣 A1.N,1.N的下三角元素已壓縮到一維數(shù)組S1.N* ( N+1 ) /2+1中，若按行序?yàn)橹餍虼鎯?，則 Ai,j對應(yīng)的 S 中的存儲位置是i(i 1).cJ J當(dāng)i jk2kN(N 1)1,當(dāng)ij2002030004.已知一個(gè)