數(shù)據(jù)結(jié)構(gòu)試題及答案

1、、選擇題第一章 概論1 、研究數(shù)據(jù)結(jié)構(gòu)就是研究（ D ）。A. 數(shù)據(jù)的邏輯結(jié)構(gòu)B. 數(shù)據(jù)的存儲結(jié)構(gòu)C. 數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)D. 數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其基本操作（研究非數(shù)值計算的程序設(shè)計問題中，計算機(jī)操作對象以及他們之間的關(guān)系和操作）2、算法分析的兩個主要方面是（A. 空間復(fù)雜度和時間復(fù)雜度C. 可讀性和文檔性 3、具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（ 被稱為第一個的數(shù)據(jù)元素和最后一個元素， 個前驅(qū)，除了最后一個元素有唯一后繼A. 圖 B. 樹）。B. 正確性和簡單性D. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 ）。（線性結(jié)構(gòu)就是：在非空有限集合中，存在為一個 有除了第一個元素， 集合中每一個元素均只有）（鏈

2、表、棧、隊列、數(shù)組、串）C. 廣義表（線性表的推廣）D. 棧4、計算機(jī)中的算法指的是解決某一個問題的有限運算序列， 等5 個特性。它必須具備輸入、 輸出、（ B ）A. 可執(zhí)行性、可移植性和可擴(kuò)充性C. 確定性、有窮性和穩(wěn)定性5 、下面程序段的時間復(fù)雜度是（ C ）。 for（i=0;i<m;i+）for（j=0;j<n;j+）aij=i*j;A. O（m 2）B. O（n 2）B. 可執(zhí)行性、有窮性和確定性D. 易讀性、穩(wěn)定性和確定性C. O(m*n) D. O(m+n)6、算法是（ D ）。 為了解決某一問題而規(guī)定的一個有限長的操作序列A. 計算機(jī)程序 B. 解決問題的計算方法

3、 C. 排序算法D. 解決問題的 有限運算序列 7、某算法的語句執(zhí)行頻度為（ 3n+nlog 2n+n 2+8 ）, 其時間復(fù)雜度表示（ C ）。A. O（n）B. O（nlog2n）C. O（n 2）D. O（log 2n）8 、下面程序段的時間復(fù)雜度為（C ）。i=1;while(i<=n)i=i*3;A. O(n)B. O(3n) C. O(log 3n) D. O(n 3)9、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的數(shù)據(jù)元素以及它們之間的（B ）和運算等的學(xué)科。 （關(guān)系和操作） A. 結(jié)構(gòu) B. 關(guān)系 C. 運算10 、下面程序段的時間復(fù)雜度是（ A ）。 i=s=0

4、;while（s<n）i+;s+=i;A. O（n） B. O（n 2）11 、抽象數(shù)據(jù)類型的三個組成部分分別為（ A. 數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作D. 算法C. O（log 2n）D. O（n3）A ）。B. 數(shù)據(jù)元素 、邏輯 結(jié)構(gòu)和 存儲結(jié) 構(gòu)C. 數(shù)據(jù)項、數(shù)據(jù)元素和數(shù)據(jù)類型 D. 數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型12 、通常從正確性、易讀性、健壯性、高效性等4個方面評價算法的質(zhì)量，以下解釋錯誤的是( D )。A. 正確性算法應(yīng)能正確地實現(xiàn)預(yù)定的功能B. 易讀性算法應(yīng)易于閱讀和理解，以便調(diào)試、修改和擴(kuò)充C. 健壯性當(dāng)環(huán)境發(fā)生變化時，算法能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會產(chǎn)生不需要的 運行

5、結(jié)果D. 高效性即達(dá)到所需要的時間性能 空間13 、下列程序段的時間復(fù)雜度為( B)。x=n;y=0;while(x>=(y+1)*(y+1)y=y+1;A. O(n) B. O( n) C. O(1) D. O(n 2)二、填空題1 、程序段“ i=1;while(i<=n) i=i*2; ”的時間復(fù)雜度為 log2n 。2 、數(shù)據(jù)結(jié)構(gòu)的四種基本類型中， 樹形結(jié)構(gòu) 的元素是一對多關(guān)系。三、綜合題1 、將數(shù)量級 O(1),O(N),O(N 2),O(N 3),O(NLOG 2N),O(LOG 2N),O(2 N) 按增長率由小到 大排序。答案： O(1) O(log 2N) O(N

6、) O(Nlog 2N) O(N2) O(N3) O(2N)一、填空題1. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為 (D, R)，其中 D是數(shù)據(jù)元素的有限集合， R是D上的關(guān)系 有限集合。2. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯結(jié)構(gòu) 、數(shù)據(jù)的 存儲結(jié)構(gòu) 和數(shù)據(jù)的 運算 這三個方面的內(nèi) 容。3. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) 。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é)點有且只有1 個后續(xù)結(jié)

7、點。6. 在樹形結(jié)構(gòu)中，樹根結(jié)點沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有 1 個前驅(qū)結(jié)點；葉子結(jié) 點沒有 后續(xù)結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點數(shù)可以 任意多個 。7. 在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以 任意多個 。8數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別是順序、鏈?zhǔn)?、索引、散列?. 數(shù)據(jù)的運算最常用的有 5 種，它們分別是 插入、刪除、修改、查找、排序 。10. 一個算法的效率可分為 時間效率和 空間效率。11. 任何一個 C 程序都由 一個主函數(shù) 和若干個被調(diào)用的其它函數(shù)組成。二、單項選擇題B ) 1.非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：A )一對多關(guān)系B)多對多關(guān)系C)

8、多對一關(guān)系D)一對關(guān)系C ) 2. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的 結(jié)構(gòu)；歡迎下載51A) 存儲 B) 物理 C) 邏輯D) 物理和存儲C ) 3. 算法分析的目的是：B) 研究算法中的輸入和輸出的關(guān)系D) 分析算法的易懂性和文檔性A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性C) 分析算法的效率以求改進(jìn)A )4. 算法分析的兩個主要方面 5 是：B) 正確性和簡明性D) 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性A) 空間復(fù)雜性和時間復(fù)雜性C) 可讀性和文檔性C ) 5. 計算機(jī)算法指的是：A) 計算方法度方法B) 排序方法 C) 解決問題的有限運算序列 D) 調(diào)B ) 6. 計算機(jī)算法必須具備輸入、輸出和等 5 個特

9、性。A) 可行性、可移植性和可擴(kuò)充性C) 確定性、有窮性和穩(wěn)定性B) 可行性、確定性和有窮性D) 易讀性、穩(wěn)定性和安全性三、簡答題1.數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個概念之間有區(qū)別嗎？ 答：簡單地說，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組 元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素， 而且還在其上定 義了一組操作。2. 簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點。答：線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是一對一的， 非線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是多對多的。四、分析下面各程序段的時間復(fù)雜度1. for (i=0; i<n; i+)for (j=0; j<m; j+)Aij=0;2. s=0;for (

10、i=0; i<n; i+) for(j=0; j<n; j+) s+=Bij;sum=s;3. x=0;for(i=1; i<n; i+) for (j=1; j<=n-i; j+) x+;4. i=1;while(i<=n) i=i*3;五、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu) S=( D,R)，試按各小題所給條件畫出這些邏輯結(jié)構(gòu)的圖 示，并確定其是哪種邏輯結(jié)構(gòu)。1. D=d1,d2,d3,d4R=(d1,d2),(d2,d3),(d3,d4) 線性表2 D=d1,d2, ,d9 R=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5),

11、(d6,d7),(d8,d9) 樹3 D=d1,d2, ,d9 R=(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6) 有向圖第二章 線性表一、選擇題1 、若長度為 n 的線性表采用順序存儲結(jié)構(gòu)， 雜度（ ）。A. O（log 2n）B.O（1）2、若一個線性表中最常用的操作是取第i存儲方式最節(jié)省時間。A. 順序表 B. 單鏈表3 、具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（ ）。A. 圖4、在一個長度為 個元素。A. n-i在其第 i 個位置插入一個新元素算法的時間復(fù)C. O（n

12、）個元素和找第C.D.O（n 2）i 個元素的前趨元素， 則采用（雙鏈表D. 單循環(huán)鏈表B. 樹 n 的順序表中，在第B. n-i+15 、非空的循環(huán)單鏈表 head 的尾結(jié)點A. p->next=headC. p=NULL6、鏈表不具有的特點是（A. 可隨機(jī)訪問任一元素C. 不必事先估計存儲空間）。D. 棧C. 廣義表個元素之前插入一個新元素時，需向后移動（C. n-i-1D. i滿足( )。B. p->next=NULLD. p=headB. 插入刪除不需要移動元素D. 所需空間與線性表長度成正比7 、在雙向循環(huán)鏈表中，在 p 指針?biāo)傅慕Y(jié)點后插入一個指針 q 所指向的新結(jié)點，

13、修改指針的 操作是（ ）。A. p->next=q;q->prior=p;p->next->prior=q;q->next=q;B. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C. q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;D. q->next=p->next;q->prior=p;p->next=q;p->next=q;8 、線性表

14、采用鏈?zhǔn)酱鎯r，結(jié)點的存儲地址（ ）。A. 必須是連續(xù)的 B. 必須是不連續(xù)的）個元素。D. i+1C. 連續(xù)與否均可 D. 和頭結(jié)點的存儲地址相連續(xù) 9、在一個長度為 n 的順序表中刪除第 i 個元素，需要向前移動（A. n-iB. n-i+1C. n-i-110 、線性表是 n 個（ ）的有限序列。A. 表元素 B. 字符 C. 數(shù)據(jù)元素 D. 數(shù)據(jù)項11 、從表中任一結(jié)點出發(fā)，都能掃描整個表的是（ ）。A. 單鏈表 B. 順序表 C. 循環(huán)鏈表 D. 靜態(tài)鏈表12 、在具有 n個結(jié)點的單鏈表上查找值為 x 的元素時，其時間復(fù)雜度為（ ）。A. O（n） B. O（1）C. O（n 2）D

15、. O（n-1）13 、線性表 L=（a1,a2, ,an） ，下列說法正確的是（ ）。A. 每個元素都有一個直接前驅(qū)和一個直接后繼B. 線性表中至少要有一個元素C. 表中諸元素的排列順序必須是由小到大或由大到小D. 除第一個和最后一個元素外， 其余每個元素都由一個且僅有一個直接前驅(qū)和直接后 繼14 、一個順序表的第一個元素的存儲地址是90 ，每個元素的長度為2 ，則第 6 個元素的存儲地址是（ ）。A. 98B. 100C. 102D. 10615 、在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費的時間最少的是（ ）。A. 單鏈表 B. 雙鏈表 C. 循環(huán)鏈表 D. 順序表 16 、在一個單鏈表中，

16、若刪除 p所指向結(jié)點的后續(xù)結(jié)點，則執(zhí)行（）。A. p->next=p->next->next;B. p=p->next;p->next=p->next->next;C. p =p->next;17 、將長度為 n 的單鏈表連接在長度為A. O（1）B. O（n）18 、線性表的順序存儲結(jié)構(gòu)是一種（A. 隨機(jī)存取B. 順序存取）。D. p=p->next->next;m的單鏈表之后的算法的時間復(fù)雜度為（C. O（m）D. O（m+n）存儲結(jié)構(gòu)。C. 索引存取D. 散列存取19 、順序表中，插入一個元素所需移動的元素平均數(shù)是（）。A. (

17、n-1)/2B. n C. n+1 D. (n+1)/210 、循環(huán)鏈表的主要優(yōu)點是（）。A. 不再需要頭指針B. 已知某結(jié)點位置后能容易找到其直接前驅(qū)C. 在進(jìn)行插入、刪除運算時能保證鏈表不斷開D. 在表中任一結(jié)點出發(fā)都能掃描整個鏈表）。B.head->next=NULL11 、不帶頭結(jié)點的單鏈表 head 為空的判定條件是（ A. head=NULLC. head->next=head D. head!=NULL12 、在下列對順序表進(jìn)行的操作中，算法時間復(fù)雜度為 O（1） 的是（ ）。A. 訪問第 i個元素的前驅(qū)（ 1<i n） B. 在 第 i 個 元 素 之 后 插

18、 入 一 個 新 元 素 （1 i n ）C. 刪除第 i個元素 （1 i n ） D. 對順序表中元素進(jìn)行排序13 、已知指針 p和q分別指向某單鏈表中第一個結(jié)點和最后一個結(jié)點。假設(shè)指針 s指向另一個單鏈表中某個結(jié)點，則在 s 所指結(jié)點之后插入上述鏈表應(yīng)執(zhí)行的語句為（ ）。A. q->next=s->next ； s->next=p ；B. s->next=p ； q->next=s->next ；C. p->next=s->next ； s->next=q ；D. s->next=q； p->next=s->next；

19、14、在以下的敘述中，正確的是（）。A. 線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B. 線性表的順序存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況C. 線性表的鏈表存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況D. 線性表的鏈表存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)15、在表長為 n 的順序表中， 當(dāng)在任何位置刪除一個元素的概率相同時， 刪除一個元素所需 移動的平均個數(shù)為（ ）。A. （n-1）/2B. n/2 C. （n+1）/2 D. n16、在一個單鏈表中， 已知 q 所指結(jié)點是 p 所指結(jié)點的前驅(qū)結(jié)點， 若在 q 和 p 之間插入一個 結(jié)點 s，則執(zhí)行（）。A. s->next=p->next; p

20、->next=s;B. p->next=s->next;s->next=p;C. q->next=s;s->next=p;D. p->next=s;s->next=q;17、在單鏈表中，指針 p指向元素為 x 的結(jié)點，實現(xiàn)刪除 x的后繼的語句是（ ）。A. p=p->next;B. p->next=p->next->next;C. p->next=p;D. p=p->next->next;18 、在頭指針為 head 且表長大于 1的單循環(huán)鏈表中，指針 p 指向表中某個結(jié)點，若 p->next-&g

21、t;next=head ，則（ ）。A. p指向頭結(jié)點B. p 指向尾結(jié)點 C. p的直接后繼是頭結(jié)點D. p的直接后繼是尾結(jié)點、填空題1、設(shè)單鏈表的結(jié)點結(jié)構(gòu)為 （ data,next）。已知指針 p 指向單鏈表中的結(jié)點， q指向新結(jié)點，欲將 q 插入到 p結(jié)點之后， 答案： q->next=p->next 2、線性表的邏輯結(jié)構(gòu)是 度。則需要執(zhí)行的語句： q-next=p-next,p-next=q p->next=q線性結(jié)構(gòu) ，其所含元素的個數(shù)稱為線性表的答案： 線性結(jié)構(gòu) 長度寫出帶頭結(jié)點的雙向循環(huán)鏈表L 為 空 表 的 條 件L-prior=L-next=L 。答案： L

22、->prior=L->next=L4 、帶頭結(jié)點的單鏈表 head 為空的條件是 head-next=null 答案： head->next=NULL5 、在一個單鏈表中刪除 p 所指結(jié)點的后繼結(jié)點時，應(yīng)執(zhí)行以下操作： q = p->next;p->next=_q-next _; 答案： q->next三、判斷題1、單鏈表不是一種隨機(jī)存儲結(jié)構(gòu)。2 、在具有頭結(jié)點的單鏈表中，頭指針指向鏈表的第一個數(shù)據(jù)結(jié)點（的存儲位置）。3、用循環(huán)單鏈表表示的鏈隊列中，可以不設(shè)隊頭指針，僅在隊尾設(shè)置隊尾指針。4、順序存儲方式只能用于存儲線性結(jié)構(gòu)。5 、在線性表的順序存儲結(jié)構(gòu)中，

23、 邏輯上相鄰的兩個元素但是在物理位置上不一定是相鄰的。6、鏈?zhǔn)酱鎯Φ木€性表可以隨機(jī)存取。四、程序分析填空題1 、函數(shù) GetElem 實現(xiàn)返回單鏈表的第 i 個元素，請在空格處將算法補(bǔ)充完整。 int GetElem(LinkList L,int i,Elemtype *e)LinkList p； int j ；p=L->next;j=1;while(p&&j<i)p=p-next (1) ;+j;if(!p|j>i) return ERROR;*e= p-data (2) ;return OK;答案： (1) p=p->next (2)p->da

24、ta2、函數(shù)實現(xiàn)單鏈表的插入算法，請在空格處將算法補(bǔ)充完整。int ListInsert(LinkList L,int i,ElemType e)LNode *p,*s;int j;p=L;j=0;while(p!=NULL)&&(j<i-1)p=p->next;j+;if(p=NULL|j>i-1) return ERROR;s=(LNode *)malloc(sizeof(LNode);s->data=e;(1) s-next=p-next ;(2) p-next=s ;return OK;/*ListInsert*/答案： (1) s->ne

25、xt=p->next (2)p->next=s3 、函數(shù) ListDelete_sq實現(xiàn)順序表刪除算法，請在空格處將算法補(bǔ)充完整。int ListDelete_sq(Sqlist *L,int i)int k;if(i<1|i>L->length) return ERROR;for(k=i-1;k<L->length-1;k+)L->slistk= L->slistk+1 (1 ) ;2 ) -L->Lengthreturn OK;答案：( 1) L->slistk+1( 2) -L->Length4、函數(shù)實現(xiàn)單鏈表的刪除

26、算法，請在空格處將算法補(bǔ)充完整。 int ListDelete(LinkList L,int i,ElemType p-next=q-next( 2 ); s=q->data;free(q);return OK;/*listDelete*/答案： (1)p->next!=NULL (2)p->next=q->next5、寫出算法的功能。int L(head)node * head;int n=0;node *p;p=head;while(p!=NULL) p=p->next;n+;return(n); 答案：求單鏈表 head的長度五、綜合題1、編寫算法，實現(xiàn)帶頭

27、結(jié)點單鏈表的逆置算法。 答案： void invent(Lnode *head)Lnode *p,*q;if(!head->next) return ERROR;p=head->next; q=p->next; p->next =NULL; while(q)p=q; q=q->next; p->next=head->next; head->next=p;s)LNode *p,*q;int j;p=L;j=0;while( p-next!=null ( 1 ) )&&(j<i-1) p=p->next;j+;if(p-&

28、gt;next=NULL|j>i-1) return ERROR; q=p->next;2、有兩個循環(huán)鏈表，鏈頭指針分別為L1 和 L2 ，要求寫出算法將 L2 鏈表鏈到 L1 鏈表之后，且連接后仍保持循環(huán)鏈表形式。答案： void merge(Lnode *L1, Lnode *L2)Lnode *p,*q ; while(p->next!=L1) p=p->next;while(q->next!=L2) q=q->next;q->next=L1; p->next =L2;3、設(shè)一個帶頭結(jié)點的單向鏈表的頭指針為head，設(shè)計算法，將鏈表的記錄，

29、按照data 域的值遞增排序。答案： void assending(Lnode *head)Lnode *p,*q , *r, *s;p=head->next; q=p->next; p->next=NULL; while(q)r=q; q=q->next; if(r->data<=p->data)r->next=p; head->next=r; p=r; elsewhile(!p && r->data>p->data) s=p; p=p->next; r->next=p; s->next

30、=r; p=head->next; 4、編寫算法 ,將一個頭指針為 head 不帶頭結(jié)點的單鏈表改造為一個單向循環(huán)鏈表，并分析 算法的時間復(fù)雜度。答案：void linklist_c(Lnode *head) Lnode *p; p=head;if(!p) return ERROR; while(p->next!=NULL) p=p->next;p->next=head;設(shè)單鏈表的長度(數(shù)據(jù)結(jié)點數(shù))為 N，則該算法的時間主要花費在查找鏈表最后一個結(jié)點上 (算法中的 while 循環(huán))，所以該算法的時間復(fù)雜度為 O( N)。5 、已知 head 為帶頭結(jié)點的單循環(huán)鏈表的頭

31、指針，鏈表中的數(shù)據(jù)元素依次為( a1 ， a2,a3,a4, ,an ) ,A 為指向空的順序表的指針。閱讀以下程序段，并回答問題： (1 )寫出執(zhí)行下列程序段后的順序表 A中的數(shù)據(jù)元素；(2 )簡要敘述該程序段的功能。 if(head->next!=head) p=head->next;A->length=0; while(p->next!=head) p=p->next;A->dataA->length +=p->data; if(p->next!=head)p=p->next; 答案：(1) (a2, a4, , ) (2)將循

32、環(huán)單鏈表中偶數(shù)結(jié)點位置的元素值寫入順序表A6、設(shè)順序表 va中的數(shù)據(jù)元數(shù)遞增有序。試寫一算法，將 x 插入到順序表的適當(dāng)位置上，以 保持該表的有序性。答案：void Insert_sq(Sqlist va, ElemType x)int i, j, n; n=length(va); if(x>=vai) van=x;else i=0; while(x>vai) i+; for(j=n-1;j>=I;j-) vaj+1=vaj;vai=x; n+;7、假設(shè)線性表采用順序存儲結(jié)構(gòu)，表中元素值為整型。閱讀算法 f2 ，設(shè)順序表 L=(3,7,3,2,1,1,8,7,3), 寫出執(zhí)行

33、算法 f2 后的線性表 L 的數(shù)據(jù)元素， 并描述該算法的功 能。void f2(SeqList *L) int i,j,k; k=0; for(i=0;i<L->length;i+) for(j=0;j<k && L->datai!=L->dataj;j+); if(j=k)if(k!=i)L->datak=L->datai;k+; L->length=k;答案：(3,7,2,1,8) 刪除順序表中重復(fù)的元素8、已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一算法，刪除表 中所有大于 x 且小于 y 的元素(若表中

34、存在這樣的元素)同時釋放被刪除結(jié)點空間。 答案：void Delete_list(Lnode *head, ElemType x, ElemType y)Lnode *p, *q;if(!head) return ERROR;p=head; q=p; while(!p)if(p->data>x) && (p->data<y)i+; if(p=head)head=p->next; free(p);p=head; q=p; else q->next=p->next; free(p); p=q->next; else q=p; p=p-

35、>next; 9、在帶頭結(jié)點的循環(huán)鏈表 L 中，結(jié)點的數(shù)據(jù)元素為整型，且按值遞增有序存放。給定兩個 整數(shù) a 和 b，且 a<b，編寫算法刪除鏈表 L 中元素值大于 a且小于 b 的所有結(jié)點。第三章 棧和隊列、選擇題1、一個棧的輸入序列為： a，b，c，d，e ，則棧的不可能輸出的序列是（）。A. a,b,c,d,eB. d,e,c,b,aC. d,c,e,a,bD. e,d,c,b,a2 、判斷一個循環(huán)隊列 Q（最多 n 個元素）為滿的條件是（）。A. Q->rear=Q->frontB. Q->rear=Q->front+1C. Q->front=

36、(Q->rear+1)%nD. Q->front=(Q->rear-1)%n3、設(shè)計一個判別表達(dá)式中括號是否配對的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。A. 順序表 B. 鏈表 C. 隊列 D. 棧 4 、帶頭結(jié)點的單鏈表 head 為空的判定條件是（ ）。A. head=NULLC. head->next!=NULL5 、一個棧的輸入序列為： 1,2,3,4A. 1243 B. 2134B. head->next=NULLD. head!=NULL，則棧的不可能輸出的序列是( )。C. 1432 D. 4312E. 32146、若用一個大小為 6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)

37、 rear 和 front 的值分別為 0，3。當(dāng)從隊列中刪除一個元素，再加入兩個元素后，A. 1 和5 B. 2 7 、隊列的插入操作是在（）。A. 隊尾 B. 隊頭 8、循環(huán)隊列的隊頭和隊尾指針分別為A. front=rearrear 和 front 的值分別為（ 和4C. 4 和2）。D. 5 和 1C. 隊列任意位置 D. 隊頭元素后 front 和 rear ，則判斷循環(huán)隊列為空的條件是 （ B. front=0）。C. rear=0 D. front=rear+1 個順序棧 S，其棧頂指針為 top ，則將元素 e 入棧的操作是（A. *S->top=e;S->top+

38、;C. *S->top=e 表達(dá)式 a*（b+c）-d 的后綴表達(dá)式是（A. abcd+-B. abc+*d-將遞歸算法轉(zhuǎn)換成對應(yīng)的非遞歸算法時，A. 隊列 B. 棧 棧的插入和刪除操作在（A. 棧底 五節(jié)車廂以編號A. 3 ， 4，5，1，C. 3 ， 5，4，2 ， 判定一個順序棧 SA. S->top=0C. S->top=n 在一個鏈隊列中，）。A. front=front->nextC. rear->next=s;rear=s; 一個隊列的入隊序列是 1，2 ，3 ，4，則隊列的出隊序列是（A. 1 ，2，3，4B. 4 ，3，2，1C. 1 ，4，3，

39、2D. 3 ，4，1，2依次在初始為空的隊列中插入元素 a,b,c,d 以后，緊接著做了兩次刪除操作，此時的 隊頭元素是（A. aB. bC. c18 、正常情況下，刪除非空的順序存儲結(jié)構(gòu)的堆棧的棧頂元素，A. top 不變 B. top=0 C. top=top+119 、判斷一個循環(huán)隊列 Q（空間大小為 M）為空的條件是（A. Q->front=Q->rearB. Q->rear-Q->front-1=MC. Q->front+1=Q->rearD. Q->rear+1=Q->front20、設(shè)計一個判別表達(dá)式中左右括號是否配對出現(xiàn)的算法，采

40、用（A. 線性表的順序存儲結(jié)構(gòu) B. 隊列 C. 棧 儲結(jié)構(gòu)21、當(dāng)用大小為 N的數(shù)組存儲順序循環(huán)隊列時，該隊列的最大長度為（A. NB. N+19、）。10 、11 、12 、13、14 、15 、（16 、17 、）。）。B. S->top+;*S->top=e;D. S->top=e;)。C. abc*+d- 通常需要使用（ C. 鏈表)D.D. -+*abcd 來保存中間結(jié)果。 樹B. 棧頂1，2，3，2C. 任意位置4 ，5順序進(jìn)入鐵路調(diào)度站（棧）B. 2 ，4，1 ，3，5D. 1 ，3，5 ，2，4指定位置D.，可以得到（）的編組。1 ?？臻g大小為 n ）為空的

41、條件是B. S->top!=0D. S->top!=n和 rear 分別為頭指針和尾指針，則插入一個結(jié)點front22、隊列的刪除操作是在（）。A. 隊首 B. 隊尾）。s 的操作為B. s->next=rear;rear=s D. s->next=front;front=s;C. N-1C. 隊前）。D. d 棧頂指針 top 的變化是（D. top=top-1）。) D.數(shù)據(jù)結(jié)構(gòu)最佳。線性表的鏈?zhǔn)剑. N-2D.隊后）。23、若讓元素 1， 2，3依次進(jìn)棧，則出棧次序不可能是（）。A. 3，2，1B. 2，1，3C. 3， 1，2D. 1， 3，224 、循環(huán)隊

42、列用數(shù)組 A0 ，m-1 存放其元素值，已知其頭尾指針分別是 front 和 rear ，則 當(dāng)前隊列中的元素個數(shù)是（ ）。A. (rear-front+m)%mB. rear-front+1C. rear-front-1D. rear-front25 、在解決計算機(jī)主機(jī)和打印機(jī)之間速度不匹配問題時，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)， 應(yīng)該是一個（ ）結(jié)構(gòu)。A. 堆棧 B. 隊列而打印機(jī)則從該緩沖區(qū)中取走數(shù)據(jù)打印。 該緩沖區(qū)C. 數(shù)組 D. 線性表26 、棧和隊列都是（ ）。A. 鏈?zhǔn)酱鎯Φ木€性結(jié)構(gòu)C. 限制存取點的線性結(jié)構(gòu)B. 鏈?zhǔn)酱鎯Φ姆蔷€性結(jié)構(gòu)D. 限制存取

43、點的非線性結(jié)構(gòu)27 、在一個鏈隊列中，假定 front 和 rear分別為隊頭指針和隊尾指針，刪除一個結(jié)點的操作是 （ ）。A. front=front->nextC. rear->next=frontB. rear= rear->nextD. front->next=rear28、隊和棧的主要區(qū)別是（）。A. 邏輯結(jié)構(gòu)不同B. 存儲結(jié)構(gòu)不同C. 所包含的運算個數(shù)不同D. 限定插入和刪除的位置不同二、填空題1 、設(shè)棧 S和隊列 Q的初始狀態(tài)為空，元素 e1,e2,e3,e4,e5,e6 依次通過棧 S，一個元素出 棧后即進(jìn)入隊列 Q，若 6個元素出隊的序列是 e2,e4

44、,e3,e6,e5,e1 ，則棧的容量至少應(yīng)該 答案： 32、一個循環(huán)隊列 Q的存儲空間大小為 M, 其隊頭和隊尾指針分別為 front 和rear ，則循環(huán)隊 列中元素的個數(shù)為： 。答案： （rear-front+M）%M3 、在具有 n 個元素的循環(huán)隊列中，隊滿時具有個元素。答案： n-14、設(shè)循環(huán)隊列的容量為 70 ，現(xiàn)經(jīng)過一系列的入隊和出隊操作后， front 為20 ，rear 為11 ， 則隊列中元素的個數(shù)為 。答案： 615、已知循環(huán)隊列的存儲空間大小為 20，且當(dāng)前隊列的頭指針和尾指針的值分別為8和 3，且該隊列的當(dāng)前的長度為 。三、判斷題1、棧和隊列都是受限的線性結(jié)構(gòu)。2、在

45、單鏈表中，要訪問某個結(jié)點，只要知道該結(jié)點的地址即可；因此，單鏈表是一種隨機(jī) 存取結(jié)構(gòu)。3、以鏈表作為棧的存儲結(jié)構(gòu)，出棧操作必須判別?？盏那闆r。四、程序分析填空題1、已知棧的基本操作函數(shù)：int InitStack(SqStack *S); /構(gòu)造空棧int StackEmpty(SqStack *S);/判斷?？読nt Push(SqStack *S,ElemType e);/入棧int Pop(SqStack *S,ElemType *e);/出棧 函數(shù) conversion 實現(xiàn)十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)，請將函數(shù)補(bǔ)充完整。void conversion()InitStack(S);scanf

46、( “%d”,&N);while(N)( 1);N=N/8;while( 2) )Pop(S,&e); printf( “%d”,e);/conversion 答案：( 1) Push(S,N%8)( 2) !StackEmpty(S)2、寫出算法的功能。int function(SqQueue *Q,ElemType *e)if(Q->front=Q->rear)return ERROR;*e=Q->baseQ->front;Q->front=(Q->front+1)%MAXSIZE;return OK;3 、閱讀算法 f2, 并回答下列問

47、題：(1)設(shè)隊列 Q=( 1，3，5，2，4，6)。寫出執(zhí)行算法 f2 后的隊列 Q; ( 2)簡述算法 f2 的功能。void f2(Queue *Q) DataType e; if (!QueueEmpty(Q) e=DeQueue(Q); f2(Q); EnQueue(Q,e); 答案：(1)6,4,2,5,3,1( 2)將隊列倒置五、綜合題但不設(shè)頭指針，1、假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列， 并且只設(shè)一個指針指向隊尾結(jié)點， 請寫出相應(yīng)的入隊列算法（用函數(shù)實現(xiàn)） 。rear答案：void EnQueue(Lnode *rear, ElemType e) Lnode *new;New=(L

48、node *)malloc(sizeof(Lnode);If(!new) return ERROR; new->data=e; new->next=rear->next; rear->next=new; rear =new;2、已知 Q是一個非空隊列， S 是一個空棧。編寫算法，僅用隊列和棧的 ADT 函數(shù)和少量工 作變量，將隊列 Q 的所有元素逆置。棧的 ADT 函數(shù)有：void makeEmpty(SqStack s);置空棧void push(SqStack s,ElemType e); 元素 e 入棧ElemType pop(SqStack s);出棧，返回棧頂

49、元素int isEmpty(SqStack s); 判斷?？?隊列的 ADT 函數(shù)有：void enQueue(Queue q,ElemType e);元素 e 入隊ElemType deQueue(Queue q);出隊，返回隊頭元素int isEmpty(Queue q); 判斷隊空 答案： void QueueInvent(Queue q) ElemType x; makeEmpty(SqStack s); while(!isEmpty(Queue q)x=deQueue(Queue q); push(SqStack s, ElemTypex); while(!isEmpty(SqSta

50、ck s)x=pop(SqStack s); enQueue(Queue q, ElemType x);3 、對于一個棧，給出輸入項 A,B,C,D ，如果輸入項序列為 A,B,C,D ，試給出全部可能的 輸出序列。答案：出棧的可能序列：ABCD ABDC ACDBACBD ADCB BACD BADCBCAD BCDACBDA CBAD CDBA DCBA第四章 串、選擇題1、設(shè)有兩個串 S1和S2 ，求串 S2在S1中首次出現(xiàn)位置的運算稱作( C )。A. 連接B. 求子串C. 模式匹配 D. 判斷子串2 、已知串 S='aaab '，則 next 數(shù)組值為（ A ）。A.

51、 0123B. 11233 、串與普通的線性表相比較，它的特殊性體現(xiàn)在（ C ）。A. 順序的存儲結(jié)構(gòu) B. 鏈?zhǔn)酱鎯Y(jié)構(gòu) 一個字符 4 、設(shè)串長為 n ，A. O（m） O（nlog 2m） 5、空串和空格串A. 相同 6、與線性表相比，串的插入和刪除操作的特點是（A. 通常以串整體作為操作對象B.C. 算法的時間復(fù)雜度較高D.C. 1231D. 1211C.數(shù)據(jù)元素是D. 數(shù)據(jù)元素任意 模式串長為 m，則 KMP 算法所需的附加空間為（ B. O（n） C.O(m*n)）。D.B )。 B.不相同C.可能相同 ）。D.無法確定需要更多的輔助空間 涉及移動的元素更多7、設(shè)SUBSTR（S,i

52、,k）是求S中從第 i個字符開始的連續(xù) k個字符組成的子串的操作，則對于S='Beijing&Nanjing ' ， SUBSTR（S,4,5）= （ B ）。A. ijing 'B. jing& 'C. ingNa 'D.ing&N '二、判斷題（ ） 1、造成簡單模式匹配算法 BF算法執(zhí)行效率低的原因是有回溯存在。（ ） 2、 KMP算法的最大特點是指示主串的指針不需要回溯。（ ） 3、完全二叉樹某結(jié)點有右子樹，則必然有左子樹。三、填空題模式匹配對應(yīng)位置字符相同1、求子串在主串中首次出現(xiàn)的位置的運算稱為2、設(shè)s=

53、9;IAM ATEACHE'R,其長度是 。3、兩個串相等的充分必要條件是兩個串的長度相等且四、程序填空題1、函數(shù) kmp 實現(xiàn)串的模式匹配，請在空格處將算法補(bǔ)充完整。 int kmp(sqstring *s,sqstring *t,int start,int next) int i=start-1,j=0;while(i<s->len&&j<t->len) if(j=-1|s->datai=t->dataj) i+;j+;else j=;if(j>=t->len)return( );elsereturn(-1);2、函數(shù)

54、實現(xiàn)串的模式匹配算法，請在空格處將算法補(bǔ)充完整。 int index_bf(sqstring*s,sqstring *t,int start)int i=start-1,j=0;while(i<s->len&&j<t->len) if(s->datai=t->dataj) i+;j+;elsei= i-j+1 ;j=0;if(j>=t->len)return i-t->len+1 ;elsereturn -1;/*listDelete*/3、寫出下面算法的功能。int function(SqString *s1,SqString *s2)int i;for(i=0;i<s1->length&&i<s1->length;i+) if(s->datai!=s2->datai) return s1->datai-s2->datai;return s1->length-s2->le