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

1、第1章 算法一、選擇題1. 算法的時間復(fù)雜度是指（ ）。A）執(zhí)行算法程序所需要的時間 B）算法程序中的指令條數(shù)C）算法執(zhí)行過程中所需要的基本運算次數(shù)D）算法程序的長度2. 算法的空間復(fù)雜度是指（ ）。A）算法程序的長度 B）算法程序所占的存儲空間C）算法執(zhí)行過程中所需要的存儲空間 D）算法程序中的指令條數(shù)3.下面（ ）的時間復(fù)雜度最好（即執(zhí)行時間最短）。A）O(n ) B）O() C）O(n ) D）O(n2)4.下面累加求和程序段的時間復(fù)雜度為（ ）。int sum(int a,int n) int i, s=0;for (i=0;i<n;i+) s+=ai;return s; A）O

2、(1 ) B）O( ) C）O(n ) D）O(n2)5.下面是將兩個n階矩陣a與b相加的結(jié)果存放到n階矩陣c中的算法，該算法的時間復(fù)雜度為（ ）。void matrixadd(int a,int b,c,int n) int i,j; for (i=0;i<n;i+)for(j=0;j<n;j+) cij=aij+bij;A）O(1 ) B）O() C）O( n ) D）O(n2)6.下面程序段的時間復(fù)雜度為（ ）。int i=0,s1=0,s2=0;while(i<n) if(i%2) s1+=i; else s2+=i; i+; A）O(1 ) B）O( ) C）O(n

3、 ) D）O(n2)7.下面程序段的時間復(fù)雜度為（ ）。int prime(int n) int i=1;int x=(int)sqrt(n);while(i<=x) i+;if(n%i=0)break;if(i>x) return 1;else return 0;A）O(1 ) B）O() C）O(n ) D）O() 8.下面程序段的時間復(fù)雜度為（ ）int fun(int n) int i=1,s=1; while(s<n) i+;s+=i; return i;A）O(n/2) B）O() C）O(n ) D）O()9.下面程序段的時間復(fù)雜度為（ ）int i,j,m,n

4、,a;for(i=0;i<m;i+) for(j=0;j<n;j+) aij=i*j;A）O(m2) B）O(n2 ) C）O(m*n ) D）O(m+n)10. 下面程序段的時間復(fù)雜度為（ ）int sum1(int n) int i,p=1,s=0; for(i=1;i<=n;i+) p*=i; s=s+p; return s;A）O(1 ) B）O() C）O(n ) D）O(n2)二、填空題1.算法復(fù)雜度主要包括時間復(fù)雜度和 復(fù)雜度。2.一個算法的時間復(fù)雜度的計算式為 ( 3n2+2n+5 ) / n ，其數(shù)量級表示為 。3.從一維數(shù)組an中順序查找出一個最大值元素的

5、平均時間復(fù)雜度為 ，讀取一個二維數(shù)組bmn中任一元素的時間復(fù)雜度為 。4.在下面程序段中，s = s+p語句的執(zhí)行次數(shù)為 ，p*=j 語句的執(zhí)行次數(shù)為 ，該程序段的時間復(fù)雜度為 。int i=0, s=o; while(+i <=n) int p=1; for(int j=1; j<=i ; j+ ) p*=j ; s=s+p ; 5. 通常用平均性態(tài)分析和 兩種方式來確定一個算法的工作量。三、 簡答題3. 什么是算法？4. 算法的基本特征是什么？5. 算法的兩種基本要素是什么？6. 遞歸是算法的基本方法之一，其基本思想是什么？7. 算法的描述方法有多種，試說出任意三種方法。四、編

6、寫出求下列問題的算法1.比較兩個整型數(shù)據(jù)a1與a2的大小，對于a1 > a2、a1 = a2、a1< a2這三種不同情況應(yīng)分別返回“>”、“=”、“<”字符。2.求一維double型數(shù)組an中的所有元素之乘積。3.假定一維整型數(shù)組an中的每個元素值x均在0，200區(qū)間內(nèi)，分別統(tǒng)計出落在0x < 20、20x<50、50x<80、80x<130、13 x200各區(qū)間內(nèi)的元素個數(shù)。參考答案一、單選題1.C 2.C 3.B 4.C 5.D 6.C 7.D 8.D 9.C 10.C二、填空題1. 空間 2. O(n) 3.O(n)，O(1) 4. n，n

7、(n+1)/2，O(n2) 5. 最壞情況復(fù)雜性三、簡答題1. 答案：所謂算法是指解題方案的準(zhǔn)確而完整的描述。2. 答案：算法的基本特征為：1)可行性；2)確定性；3)有窮性；4)擁有足夠的情報。3. 答案：算法通常由兩種基本要素組成；一是對數(shù)據(jù)對象的運算和操作；二是算法的控制結(jié)構(gòu)。4. 答案：人們在解決一些復(fù)雜問題時，為了降低問題的復(fù)雜程度，一般總是將問題逐層分解，最后歸結(jié)為一些最簡單的問題。這種將問題逐層分解的過程，實際上并沒有對問題進(jìn)行求解。而只是當(dāng)解決了最后那些最簡單的問題后，再沿著原來分解的逆過程逐步進(jìn)行綜合，這就是遞歸的基本思想。5.答案：一個算法可以用多種方式來描述，如自然語言、

8、程序語言、流程圖等。四、算法設(shè)計1.比較兩個整型數(shù)據(jù)a1與a2的大小。char compare(int a1,int a2)if(a1>a2)return ">"elase if(a1=a2)return "=" elase return "<"2.求一維double型數(shù)組an中的所有元素之乘積。double product(dluble a,int n)double p=1;for(int i=0;i< n;i+)p=p*ai;return p;3.統(tǒng)計數(shù)組an中的每個元素值x分別落在0x<20、20x

9、<50、50x< 80、80x<130、130x200各區(qū)間內(nèi)的元素個數(shù)。int count(int a,int n,int c5) /用c5保存統(tǒng)計結(jié)果 int d5=20,50,80,130,201; /用d5保存各統(tǒng)計區(qū)間上限 int i,j; for(i=0;i<n;i+)ci=0; for(i=0;i<n;i+) if(ai<0; | ai>200) return 0; /數(shù)組中數(shù)據(jù)有錯，統(tǒng)計失敗 for(j=0;j< 5;j+) if(ai<dj) break; /查找ai所在區(qū)間 cj+; /使統(tǒng)計相應(yīng)區(qū)間的元素數(shù)增1 ret

10、urn 1; /表示統(tǒng)計成功第2章 數(shù)據(jù)結(jié)構(gòu)的基本概念一、 單選題1.一個數(shù)據(jù)結(jié)構(gòu)可形象地表示成B=(D,R)，其中D是（）的有限集合，R是D上的（）有限集合。 A）算法 B）數(shù)據(jù)元素 C）數(shù)據(jù)操作 D）邏輯結(jié)構(gòu) A）操作 B）映像 C）存儲 D）關(guān)系2. 數(shù)據(jù)結(jié)構(gòu)在計算機存儲空間中的存放形式稱為（ ）。A）數(shù)據(jù)元素之間的關(guān)系 B）數(shù)據(jù)結(jié)構(gòu)C）數(shù)據(jù)的存儲結(jié)構(gòu) D）數(shù)據(jù)的邏輯結(jié)構(gòu)3. 下列敘述中正確的是（ ）。A）一個邏輯結(jié)構(gòu)只能有一種存儲結(jié)構(gòu)B）數(shù)據(jù)邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲結(jié)構(gòu)屬于非線性結(jié)構(gòu)C）一個邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)不影響數(shù)據(jù)處理的效率D）一個邏輯結(jié)構(gòu)可以有多種存儲結(jié)

11、構(gòu)，且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率4. 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（ ）結(jié)構(gòu)。A）邏輯 B）存儲 C）邏輯和存儲 D）物理5. 在存儲數(shù)據(jù)時，通常不僅需要存儲各數(shù)據(jù)元素的值，而且還要存儲（ ）。A）數(shù)據(jù)的處理方法 B）數(shù)據(jù)元素的類型 C）數(shù)據(jù)元素之間的關(guān)系 D）數(shù)據(jù)的存儲方法6. 如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足兩個條件：有且只有一個根結(jié)點；每一個結(jié)點最多有一個前件，也最多有一個后件，則稱該數(shù)據(jù)結(jié)構(gòu)為（ ）。A）線性結(jié)構(gòu) B）非線性結(jié)構(gòu) C）物理結(jié)構(gòu) D）邏輯結(jié)構(gòu)7. 數(shù)據(jù)的（ ）包括插入、刪除、查找、更新、排序等操作類型。A）存儲結(jié)構(gòu) B）邏輯結(jié)構(gòu)C）基本運算 D）算法描述8.

12、 數(shù)據(jù)的存儲結(jié)構(gòu)是指（ ）。A）數(shù)據(jù)所占的存儲空間 B）數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示C）存儲在外存中的數(shù)據(jù) D）數(shù)據(jù)在計算機中的順序存儲方式9. 在決定選取何種存儲結(jié)構(gòu)時，一般不考慮（ ）。A）結(jié)點個數(shù)的多少 B）各結(jié)點的值如何C）對數(shù)據(jù)有哪些運算 D）所用編程語言實現(xiàn)這種結(jié)構(gòu)是否方便10.以下說法正確的是（ ）。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)11.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ）。A）動態(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)

13、和外部結(jié)構(gòu)12.通常要求同一邏輯結(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ù)要相等二、填空題1.數(shù)據(jù)的基本單位是 ，數(shù)據(jù)的最小單位是 。2. 一種數(shù)據(jù)的邏輯結(jié)構(gòu)，根據(jù)需要可以表示成順序、 、 和散列四種基本存儲結(jié)構(gòu)。3. 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，可將數(shù)據(jù)分為 兩大類型。4. 在一個線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點后還應(yīng)是 。5.一種數(shù)據(jù)結(jié)構(gòu)的元素集合為D，它在D上的二元關(guān)系R為：D=a,b,c,d,e,f,g,

14、hR=<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>則該數(shù)據(jù)結(jié)構(gòu)具有 結(jié)構(gòu)。6.一種數(shù)據(jù)結(jié)構(gòu)的元素集合為D，它在D上的二元關(guān)系R為：D=a,b,c,d,e,f,g,hR=<d,b>,<d,g>,<b,a>,<b,c>,<g,e>,<g,h>,<e,f>則該數(shù)據(jù)結(jié)構(gòu)具有 結(jié)構(gòu)。7.數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，其中的非線性結(jié)構(gòu)有 兩種基本類型。三、 簡答題1. 數(shù)據(jù)結(jié)構(gòu)主要研究的三個問

15、題是什么？2. 一個數(shù)據(jù)結(jié)構(gòu)應(yīng)包含兩方面的信息是什么？3. 簡述數(shù)據(jù)存儲結(jié)構(gòu)中的順序存儲方式。4. 簡述數(shù)據(jù)存儲結(jié)構(gòu)中的鏈?zhǔn)酱鎯Ψ绞絽⒖即鸢敢?、單選題1.B，D 2. C 3.D 4.A 5.C 6.A 7.C 8.B 9.B 10.D 11.C 12.B二、填空題1. 數(shù)據(jù)元素，數(shù)據(jù)項 2. 鏈?zhǔn)健⑺饕?3. 線性結(jié)構(gòu)與非線性結(jié)構(gòu) 4. 線性結(jié)構(gòu)5. 線性 6.非線性（或樹形）7. 樹和圖三、簡答題1. 答案：數(shù)據(jù)結(jié)構(gòu)主要研究的三個問題是：數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲結(jié)構(gòu)，對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運算。2. 答案：一個數(shù)據(jù)結(jié)構(gòu)應(yīng)包含兩方面的信息：表示數(shù)據(jù)元素的信息；表示各數(shù)據(jù)元素之間的前后件關(guān)系。

16、3. 答案：在數(shù)據(jù)的存儲結(jié)構(gòu)中，順序存儲方式的含義如下：順序存儲方式：把邏輯上相鄰的數(shù)據(jù)元素存儲在物理位置也相鄰的存儲單元里，數(shù)據(jù)元素之間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。4. 答案：在數(shù)據(jù)的存儲結(jié)構(gòu)中，鏈?zhǔn)酱鎯Ψ绞降暮x如下：鏈?zhǔn)酱鎯Ψ绞剑菏褂弥羔槺硎緮?shù)據(jù)元素之間的邏輯關(guān)系，各個數(shù)據(jù)元素的存儲位置可以隨意，不要求邏輯上相鄰的數(shù)據(jù)元素在物理位置上也相鄰。第3章 線性表及其存儲結(jié)構(gòu)一、 單選題1. 在一個長度為n的順序存儲的線性表中，向第i個元素（1 i n+1）位置插入一個新元素時，需要從后向前依次后移（ ）個元素。A）n-i B）ni+1 C）ni-1 D）i2. 在一個長度為n的順序存

17、儲的線性表中，刪除第i個元素（1 i n+1）時，需要從前向后依次前移（ ）個元素。A）n-i B）ni+1 C）ni-1 D）i3. 在一個長度為n的順序表中，存在值為x的元素。在此表中用順序搜索法，查找值為x的元素，在等概率情況下，查找成功時的平均查找長度為（ ）。A）n B）n/2 C）(n+1)/2 D）(n - 1)/24. 在一個長度為n的順序表中，刪除值為x的元素時，需要比較元素的次數(shù)和移動元素次數(shù)的和為（ ）。A）n/2 B）(n+1)/2 C）n D）n+15. 在一個順序表的表尾，插入一個元素時的時間復(fù)雜度為（ ）。A）O(1) B）O() C）O(n) D）O(n2)6.

18、 在一個順序表的任意位置，插入一個元素的時間復(fù)雜度為（ ）。A）O(1) B）O() C）O(n) D）O(n/2)7. 線性表的順序存儲比鏈?zhǔn)酱鎯ψ钣欣谶M(jìn)行（ ）操作。A）查找 B）表尾插入或刪除C）按值插入或刪除 D）表頭插入或刪除8. 線性表的鏈?zhǔn)酱鎯Ρ软樞虼鎯ψ钣欣谶M(jìn)行（ ）操作。A）查找 B）表尾插入或刪除C）按值插入或刪除 D）表頭插入或刪除9. 在一個單鏈表中，若要在pre所指向的結(jié)點之后插入一個新結(jié)點，則相繼修改（ ）個指針域的值。A）2 B）1 C）3 D）410. 在帶表頭結(jié)點的單鏈表中，插入一個新結(jié)點所用算法的時間復(fù)雜度為（ ）。A）O(1) B）O() C）O(n)

19、 D）O(n/2)11.以下關(guān)于線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的敘述中，正確的是（ ）。A）存儲密度大B）邏輯上相鄰的結(jié)點物理上不必相鄰C）可以通過計算直接確定第i個結(jié)點的存儲地址D）插入、刪除運算操作不方便12.帶頭結(jié)點的單鏈表H為空的判定條件是（ ）。A）H=NULL B）H->next=NULLC）H->next=H D）H!=NULL13.不帶頭結(jié)點的單鏈表H為空的判定條件是（ ）。A）H=NULL B）H->next=NULLC）H->next=H D）H!=NULL14.在一個帶頭結(jié)點的單鏈表H中，若要向表頭插入一個由指針p指向的新結(jié)點，則應(yīng)執(zhí)行的操作是（ ）A）H=

20、p;p->next=H; B）p->next=H;H=p;C）p->next=H;p=H; D）p->next=H->next; H->next=p;15.非空的循環(huán)單鏈表H的尾結(jié)點（由p所指向）滿足（ ）。A）p=NULL B）p->next=NULLC）p->next=H D）p=H16.鏈表不具備的特點是（ ）。A）插入刪除不需要移動元素 B）可隨機地訪問任一結(jié)點C）不必事先估計存儲空間 D）所需空間與其長度成正比17.設(shè)線性表有n個元素，以下算法中，（ ）在順序表上實現(xiàn)比在鏈表上實現(xiàn)的效率更高。A）輸出第i（0in-1）個元素B）交換第0

21、個元素與第1個元素的值C）順序輸出這n個元素的值D）輸出與給定值x相等的元素在線性表中的序號18.設(shè)線性表中有2n個元素，以下算法中，（ ）在單鏈表上實現(xiàn)要比在順序表上實現(xiàn)效率更高。A）刪除所有值為X 的元素B）在最后一個元素的后面插入一個新元素C）順序輸出前k個元素D）交換第i個元素和第2ni-1個元素的值（i = 0，1，n-1）二、填空題1. 在線性表中，第一個結(jié)點 前件，其余每個結(jié)點有且只有 個前件；最后一個結(jié)點 后件，其余每個結(jié)點有且只有 個后件。2. 數(shù)據(jù)元素在線性表中的位置只取決于它們自己的 。 3. 線性表中結(jié)點的個數(shù) n 稱為線性表的 。當(dāng) n=0時，稱為 。4. 用一維數(shù)組

22、存放線性表時，數(shù)組的基本類型要與線性表中數(shù)據(jù)元素的類型 。5. 線性表的順序存儲結(jié)構(gòu)存在插入、刪除操作時需 數(shù)據(jù)元素的缺點。6. 線性表的兩種存儲結(jié)構(gòu)分別是 和 。7. 線性表的順序存儲結(jié)構(gòu)稱為 ；線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為 。8. 對線性單鏈表進(jìn)行插入操作時，沒有發(fā)生數(shù)據(jù)元素的 ，只是改變了有關(guān)結(jié)點的 。 9. 在線性單鏈表中刪除一個元素后，不需要 表中的數(shù)據(jù)元素，只需改變被刪除元素所在結(jié)點的 的指針域即可。10. 在帶表頭結(jié)點的單鏈表中，查找第i個結(jié)點。只能從單鏈表的 ，沿著結(jié)點的 ，直到搜索到第i個結(jié)點為止。11. 在單鏈表中，若一個元素所在結(jié)點的地址為p，則其后繼（件）結(jié)點的地址為 。1

23、2. 在單鏈表中，刪除指針p所指向結(jié)點的后繼結(jié)點時，需要把 的值賦給p->next指針域。 13. 在單鏈表中指針p所指結(jié)點的后面，插入一個指針q所指的結(jié)點時，首先把 的值賦給q->next，然后把 的值賦給p->next。14. 在一個帶表頭結(jié)點的單鏈表的表頭插入或刪除，與在其他位置插入或刪除的操作過程是否相同？ 。15. 在一個不帶表頭結(jié)點的單鏈表的表頭插入或刪除，與在其他位置插入或刪除的操作過程是否相同？ 。 16. 在雙向鏈表中的每一個結(jié)點，包含有兩個指針域，一個指向 結(jié)點，另一個指向其 結(jié)點。17. 在一個雙向鏈表中，通過一個結(jié)點的prior 和 next指針域，能

24、夠分別訪問到該結(jié)點的 和 結(jié)點。 18.由于在循環(huán)鏈表中設(shè)置了一個表頭結(jié)點，因此，在任何情況下，循環(huán)鏈表中至少有一個結(jié)點存在，從而使空表與非空表的 。三、簡答題1. 非空線性表的結(jié)構(gòu)特征是什么？2線性表的順序存儲結(jié)構(gòu)具有哪兩個基本特點？3. 用一維數(shù)組存放線性表時，應(yīng)注意什么？4. 簡述線性表順序存儲的優(yōu)點和缺點。5. 什么是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)？6. 在帶頭結(jié)點的單鏈表中與在順序表中，查找與給定元素值item相等的結(jié)點的操作有何不同？7. 帶表頭結(jié)點的循環(huán)鏈表與前面所討論的單鏈表相比具有哪兩個特點？四、算法設(shè)計1. 分別編寫在順序表和鏈表中統(tǒng)計出值為x的元素個數(shù)的函數(shù)，統(tǒng)計結(jié)果由函數(shù)值返回。

25、2. 分別編寫在順序表和帶表頭結(jié)點的單鏈表中刪除其值等于x的所有元素的函數(shù)。3. 編寫在單鏈表中刪除具有重復(fù)值的多余結(jié)點，使每個結(jié)點的值均不同的函數(shù)。參考答案一、單選題1.B 2.A 3.C 4.C 5.A 6.C 7.B 8.D 9.A 10.C11.B 12.B 13.A 14.D 15.C 16.B 17.A 18.A 二、填空題1. 沒有，1，沒有，1 2. 序號3. 長度，空表 4. 相同5. 移動大量 6. 順序存儲結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)7. 順序表，線性鏈表 8. 移動，指針域9. 移動，前一個結(jié)點 10. 頭指針出發(fā)，鏈域逐個向下11. p->next 12. p->n

26、ext->next13. p->next，q 14. 相同15. 不相同 16. 前件，后件17. 前件，后件 18. 運算統(tǒng)一三、簡答題 1. 答案：非空線性表的結(jié)構(gòu)特征為： 有且只有一個根結(jié)點 a1 ,它無前件； 有且只有一個終端結(jié)點 an ,它無后件； 除根結(jié)點與終端結(jié)點外，其他所有結(jié)點有且只有一個前件，也有且只有一個后件。2. 答案：線性表的順序存儲結(jié)構(gòu)具有如下兩個基本特點： 線性表中所有元素所占的存儲空間是連續(xù)的； 線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。3. 答案：用一維數(shù)組存放線性表時，應(yīng)注意數(shù)組的基本類型，要與線性表中數(shù)據(jù)元素的類型相同，而且該一維數(shù)組

27、的長度，通常要定義得比線性表的實際長度大一些，以便對線性表進(jìn)行各種運算。4. 答案：線性表順序存儲結(jié)構(gòu)的優(yōu)點是：簡單、存儲密度大、空間利用率高，對表中任意元素可直接確定其存儲地址，隨機訪問存取效率高。缺點是，在順序表中進(jìn)行插入與刪除操作時，需大量移動數(shù)據(jù)元素，時間開銷大；再者，在順序存儲結(jié)構(gòu)下，線性表的長度估計困難，并且當(dāng)有多個順序表同時共享計算機的存儲空間時，不便于對存儲空間進(jìn)行動態(tài)分配。5. 答案：假設(shè)數(shù)據(jù)結(jié)構(gòu)中的每一個數(shù)據(jù)結(jié)點對應(yīng)于一個存儲單元，這種存儲單元稱為存儲結(jié)點，簡稱結(jié)點。若每個結(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域。其中指針用于

28、指向該結(jié)點的前一個或后一個結(jié)點（即前件或后件）。通過每個結(jié)點的指針域，將n個結(jié)點按其邏輯順序連接在一起而構(gòu)成的數(shù)據(jù)存儲結(jié)構(gòu)，稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。6答案：在帶表頭結(jié)點的單鏈表中進(jìn)行查找操作，不能像在順序表中那樣根據(jù)序號直接訪問表中的元素，而只能依據(jù)給定數(shù)據(jù)元素值item，在帶表頭結(jié)點的單鏈表中從頭指針出發(fā)，沿著結(jié)點的鏈域逐個向下進(jìn)行查找。若查找成功，則返回首次找到的結(jié)點的地址。若查找失敗，則返回NULL。 7答案：帶表頭結(jié)點的循環(huán)鏈表與前面所討論的單鏈表相比具有以下兩個特點： 循環(huán)鏈表的頭結(jié)點的數(shù)據(jù)域為任意或者根據(jù)需要來設(shè)置，頭結(jié)點的指針域指向線性表的第一個元素的結(jié)點（首結(jié)點）。頭指針指向表頭結(jié)點

29、。 循環(huán)鏈表中最后一個結(jié)點的指針域不是NULL，而是指向表頭結(jié)點。即在循環(huán)鏈表中，沒有空指針，所有結(jié)點的指針構(gòu)成了一個環(huán)狀鏈。四、算法設(shè)計1. 算法由函數(shù)Count1( ) 和Count2( )所示：/ Count1( )從順序表上統(tǒng)計出值為x的元素個數(shù)的算法 int Count1(SeqList &L,ElemType x ) /使用&的參數(shù)L為引用參數(shù) int i=0,j; for(j=0;j<L.length;j+) if(L.listj=x)i+; return i; / Count2從單鏈表上統(tǒng)計出值為x的元素個數(shù)的算法 int Count2(LinkList

30、&H,ElemTtype x) node *p=H.head->next; /將指向第1個結(jié)點的指針賦給p int i=0; /將i作為統(tǒng)計變量 while(p!=NULL) if(p->data=x)i+; p=p->next; return i;2. 算法由函數(shù)Delete1( )和Delete2( ) 所示：/Delete1( )從順序表中刪除具有給定值x的所有元素 void Delete1(SeqList &L,ElemType x) int j,i=0; while(i<L.length) if(L.listi=x) for(j=i+1;j&l

31、t;L.length;j+) L.listj-1=L.listj; L.length-; else i+; / Delete2( )從單鏈表中刪除具有給定值x的所有元素 void Delete2(LinkList &H,ElemType x) node *q,*p=H.head; /將指向附加頭結(jié)點的指針賦給p while(p->next!=NULL) q=p->next; if(q->data=x) p->next=q->next; /刪除p 的后繼結(jié)點，即q 結(jié)點 delete q; else p=p->next; 3. 算法由Delete3(

32、)所示：/ Delete3( )從單鏈表中刪除具有重復(fù)值的多余結(jié)點，可使所有結(jié)點的值均不同 void Delete3(LinkList &H) node *p=H.head; /p鏈表的第1個結(jié)點 while(p!=NULL) node *t1=p,*t2=p->next; /t2指向待處理的結(jié)點 while(t2!=NULL) if(t2->data=p->data) /刪除t2結(jié)點 t1->next=t2->next; delete t2; t2=t1->next; /t2指向新的結(jié)點 else t1=t2; t2=t2->next; p=

33、p->next; /p指向下一個結(jié)點 第4章 棧和隊列一、單選題1.下列敘述中正確的是（ ）。A）線性表是線性結(jié)構(gòu) B）棧與隊列是非線性結(jié)構(gòu)C）線性鏈表是非線性結(jié)構(gòu) D）樹是線性結(jié)構(gòu)2.下列關(guān)于棧的敘述中正確的是（ ）。A）在棧中只能插入數(shù)據(jù) B）在棧中只能刪除數(shù)據(jù)C）棧是先進(jìn)先出的線性表 D）棧是先進(jìn)后出的線性表3.棧的插入和刪除操作在（ ）進(jìn)行。A）棧頂 B）棧底 C）任意位置 D）指定位置4.當(dāng)利用大小為N的一維數(shù)組，順序存儲一個棧時，用top表示棧頂指針（指示器），用top=N表示?？眨瑒t向這個棧插入一個元素時，首先應(yīng)執(zhí)行（ ）語句修改top指針。A）top+; B）top-;

34、C）top=0; D）top=N-1;5. 利用數(shù)組aN順序存儲一個棧時，用top表示棧頂元素的下標(biāo)位置，用top=-1表示棧空，用top=N-1表示棧滿，則該數(shù)組所能存儲棧的最大長度為（ ）。A）N-1 B）N C）N+1 D）N+2 6. 利用數(shù)組aN順序存儲一個棧時，用top表示棧頂指針，用top=N+1表示?？眨瑒t該數(shù)組所能存儲棧的最大長度為為N，則表示棧滿的條件為（ ）。A）top=1; B）top=-1;C）top=0; D）top>1;7. 利用數(shù)組aN順序存儲一個棧時，用top表示棧頂指針，用top=-1表示?？眨⒁阎獥Ｎ礉M，當(dāng)元素x進(jìn)棧時所執(zhí)行的操作是（ ）。A）a-

35、top=x; B）atop-=x; C）a+top=x; D）atop+=x;8. 利用數(shù)組aN順序存儲一個棧時，用top表示棧頂指針，用top=-1表示棧空，并已知棧未空，當(dāng)退棧并返回棧頂元素時所執(zhí)行的操作是（ ）。A）return a-top; B）return atop-; C）return a+top; D）return atop+;9. 假定一個鏈棧的棧頂指針用top表示，則該鏈棧為空的條件是（ ）。A）top!=NULL; B）top=top->next;C）top=NULL; D）top!=top->next;10.假定一個鏈棧的棧頂指針用top表示，每個結(jié)點的結(jié)構(gòu)由

36、一個數(shù)據(jù)域data和一個指針域組成，當(dāng)p指向的結(jié)點進(jìn)棧時，執(zhí)行的操作為（ ）。A）p->next=top;top=top->next; B）top=p;p->next=top;C）p->next=top->next;top->next=p; D）p->next=top;top=p;11.假定一個鏈棧的棧頂指針用top表示，每個結(jié)點的結(jié)構(gòu)由一個數(shù)據(jù)域data和一個指針域組成，退棧時所執(zhí)行的指針操作為（ ）。A）p->next=top; B）top=top->data;C）top=top->next; D）top->next=top

37、->next->next;12.若讓元素1，2，3依次進(jìn)棧，則出棧次數(shù)不可能出現(xiàn)（ ）的情況。A）3，2，1 B）2，1，3 C）3，1，2 D）1，3，213.若讓元素1，2，3，4依次進(jìn)棧，則出棧次序不可能出現(xiàn)（ ）的情況。A）3，2，1，4 B）2，1，4，3 C）4，3，2，1 D）1，4，2，314.下列關(guān)于隊列的敘述中正確的是（ ）。A）在隊列中只能插入數(shù)據(jù) B）在隊列中只能刪除數(shù)據(jù)C）對列是先進(jìn)先出的線性表 D）隊列是先進(jìn)后出的線性表15.在一個順序循環(huán)隊列中，隊頭指針指向隊頭元素的（ ）位置。A）前一個 B）后一個 C）當(dāng)前 D）最后16. 在一個順序循環(huán)隊列中，隊

38、尾指針指向隊尾元素的（ ）位置。A）前一個 B）后一個 C）當(dāng)前 D）最后17.從一個順序循環(huán)隊列中刪除元素時，首先需要( )。A）前移隊頭指針 B）取出隊尾指針?biāo)肝恢蒙系脑谻）后移隊頭指針 D）取出隊頭指針?biāo)肝恢蒙系脑?8.假設(shè)一個順序循環(huán)隊列的隊頭指針和隊尾指針分別用front和rear表示，則判別隊空的條件為（ ）。A）front+1=rear B）rear+1=frontC）front=0 D）front=rear19.假設(shè)一個順序循環(huán)隊列存儲于數(shù)組aN中，其隊頭指針和隊尾指針分別用front和rear表示，則判斷隊列滿的條件為（ ）。A）(rear-1)%N=front B）

39、(rear+1)%N=frontC）(front-1)%N=rear D）(front+1)%N=rear20. 假設(shè)一個順序循環(huán)隊列存儲于數(shù)組aN中，其隊頭指針和隊尾指針分別用front和rear表示，已知隊列未滿，當(dāng)元素x入隊時所執(zhí)行的操作為（ ）。A）a+rear%N=x; B）ar+%N=x;C）a-rear%N=x; D）arear-%N=x;21. 假設(shè)一個順序循環(huán)隊列存儲于數(shù)組aN中，其隊頭指針和隊尾指針分別用front和rear表示，已知隊列未滿，當(dāng)出隊并返回隊頭元素時所執(zhí)行的操作為（ ）。A）return a+rear%N; B）return a-rear%N;C）retur

40、n a+front%N; D）return afront+%N;22.假設(shè)一個鏈接隊列的隊頭指針和隊尾指針分別為front和rear，則判別隊列空的條件為（ ）。A）front=rear B）front!=NULLC）rear!=NULL D）front=NULL23. 假設(shè)一個鏈接隊列的隊頭指針和隊尾指針分別為front和rear，每個結(jié)點由一個數(shù)值域data和一個指針域next構(gòu)成，當(dāng)出隊時，所進(jìn)行的指針操作為（ ）。A）front=front->next; B）front->next=rear;rear=rear->next;C）rear=rear->next;

41、D）front=front->next;front->next=rear;24.以下哪一個不是隊列的基本運算（ ）。A）從隊尾插入一個新元素 B）從隊列中刪除第i個元素C）判斷一個隊列是否為空 D）讀取隊頭元素的值25.棧和隊列的共同特點是（ ）。A）都是先進(jìn)先出 B）都是先進(jìn)后出C）都只允許在端點處插入和刪除元素 D）沒有共同點26.一個隊列的入隊序列是1，2，3，4，在隊列的出隊序列是（ ）。A）4，3，2，1 B）1，2，3，4 C）1，4，3，2 D）3，2，4，127.下列敘述中，（ ）與在循環(huán)順序隊列中插入下一個元素有關(guān)。A）與隊頭指針和隊尾指針的值有關(guān)B）只與隊尾指針

42、的值有關(guān)，與隊頭指針的值無關(guān)C）只與隊頭指針的值有關(guān)，與隊尾指針的值無關(guān)D）與曾經(jīng)進(jìn)行過多少次插入操作有關(guān)二、填空題1. 在棧中，允許插入與刪除的一端稱為 ，而不允許插入與刪除的另一端稱為 。2. 往棧中插入一個元素稱為 運算。從棧中刪除一個元素（即刪除棧頂元素）稱為 運算。 3.棧又稱為 表，隊列又稱為 表。 4.在一個用一維數(shù)組aMax表示的順序棧中，該棧所含元素的個數(shù)最少為 個，最多為 個。5.向一個順序棧插入一個元素時，首先使 后移一個位置，然后把新元素 到這個位置上。6.從一個順序棧刪除元素時，首先取出 ，然后再使 減1。7.隊列的插入操作在 進(jìn)行，刪除操作在 進(jìn)行。8.一個順序循環(huán)

43、隊列存于一維數(shù)組aMax中，假設(shè)隊頭指針和隊尾指針分別為front和rear，則判斷隊空的條件為 ，判斷隊滿的條件為 。9. 一個順序循環(huán)隊列存于一維數(shù)組aMax中，假設(shè)隊頭指針和隊尾指針分別為front和rear，則求出隊頭指針和隊尾指針的下一個位置的計算公式分別為 和 。10. 一個順序棧存儲于一維數(shù)組a 0.N-1 中，棧頂指針用top表示，當(dāng)棧頂指針等于 時，則為空棧，棧頂指針等于 時，則為滿棧。11.在一個鏈棧中，若棧頂指針等于NULL，則為 ；在一個鏈隊列中，若隊頭指針與隊尾指針的值相同，則表示該隊列為 或該隊 。12.假設(shè)一個鏈棧的棧頂指針為top，每個結(jié)點包含值域data和指針

44、域next，當(dāng)p所指向的結(jié)點入棧時，則首先執(zhí)行 操作，然后執(zhí)行 操作。13. 假設(shè)一個鏈棧的棧頂指針為top，每個結(jié)點包含值域data和指針域next，當(dāng)進(jìn)行出棧運算時（棧非空），則要把棧頂指針top修改為 的值。14.向一個順序循環(huán)隊列中插入元素時，需要首先移動 ，然后再向它所指的位置 新元素。15.在一個空鏈隊列中，假定隊頭指針和隊尾指針分別為front和rear，當(dāng)向其插入一個新結(jié)點*p時，則首先執(zhí)行 操作，然后執(zhí)行 操作。16.假設(shè)front和rear分別為一個鏈隊列的隊頭指針和隊尾指針，則該鏈隊列中只有一個結(jié)點的條件為 。 17.在一個容量為15的循環(huán)隊列中，若頭指針front=6，尾指針rear=9，則該循環(huán)隊列中共有 個元素。三、簡答題1. 什么是棧？棧組織數(shù)據(jù)的