數(shù)據(jù)結(jié)構(gòu)與STL課后答案北郵

1、習(xí)題11. 填空題（1）（_）是指數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。通常人們認(rèn)為它包含三個方面的內(nèi)容，分別為數(shù)據(jù)的（_）、（_）及其運算。答案：數(shù)據(jù)結(jié)構(gòu) 邏輯結(jié)構(gòu) 存儲結(jié)構(gòu)（2）（_）是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行處理。答案：數(shù)據(jù)元素（3）數(shù)據(jù)元素之間的不同邏輯關(guān)系代表不同的邏輯結(jié)構(gòu)，常見的邏輯結(jié)構(gòu)有（_）、（_）、（_）和（_）。答案：集合 線形結(jié)構(gòu) 樹結(jié)構(gòu) 圖結(jié)構(gòu)（4）數(shù)據(jù)的存儲結(jié)構(gòu)考慮的是如何在計算機中存儲各個數(shù)據(jù)元素，并且同時兼顧數(shù)據(jù)元素間的邏輯關(guān)系。基本的存儲結(jié)構(gòu)通常有兩大類：（_）和（_）。答案：順序存儲結(jié)構(gòu) 鏈?zhǔn)酱鎯Y(jié)構(gòu)（5）通常一個問題可以有多種不同的

2、算法，但每個算法必須滿足5個準(zhǔn)則：輸入、輸出、（_）、（_）和（_）。答案：有窮性 確定性 可行性（6）通常通過衡量算法的（_）復(fù)雜度和（_）復(fù)雜度來判定一個算法的好壞。答案：時間 空間（7）常見時間復(fù)雜性的量級有：常數(shù)階O（_）、對數(shù)階O（_）、線性階O（_）、線性對數(shù)階O（_）、平方階O（_）、和指數(shù)階O（_）。通常認(rèn)為，當(dāng)問題規(guī)模較大時，具有（_）量級的算法是不可計算的。答案：1 logn n nlogn n2 2n 指數(shù)（8）STL提供的標(biāo)準(zhǔn)容器有順序容器、（_）和（_）。答案：排序容器 哈希容器（9）算法可認(rèn)為是STL的精髓，所有算法都是采用（_）的形式提供的。答案：函數(shù)模版（10）

3、通常認(rèn)為STL由空間管理器、迭代器、泛函、適配器、（_）和（_）等六部分構(gòu)成，其中前面四部分服務(wù)于后面兩部分。答案：容器 算法2. 選擇題（1）以下結(jié)構(gòu)中，（ ）屬于線性結(jié)構(gòu)。A. 樹B. 圖C. 串D. 集合（2）算法描述的方法有很多種，常常將（ ）稱為算法語言。A. 自然語言B. 流程圖C. 偽代碼D. 程序設(shè)計語言（3）現(xiàn)實生活中的家族譜，可認(rèn)為是一種（ ）結(jié)構(gòu)。A. 樹B. 圖C. 集合D. 線性表（4）手機中存儲的電話號碼簿，可認(rèn)為是一種（ ）結(jié)構(gòu)。A. 樹B. 圖C. 集合D. 線性表（5）NP問題是（ ）。A. 非多項式時間問題，即非P問題B. 非確定性多項式時間問題C. P問題

4、的子集D. 與P問題不相交的（6）以下（ ）不屬于STL的順序容器。A. 向量（vector）B. 列表（list）C. 隊列（queue）D.雙端隊列（deque）（7）下面帶有標(biāo)記的語句的頻度(n>10)是（ ）。 for(int i=0;i<n-1;i+) for(int j=i+1;j<n;j+) cout<<i<<j<<endl;A. n*(n-1)/2 B. n*n/2 C. n*(n+1)/2 D. 不確定分析：3. 分析以下程序段的時間復(fù)雜度。（1）for (i=l; i<=n; i+) k+;for (j=1; j&

5、lt;=n; j+)m += k; （2）for (i=l; i<=n; i+) k+; for (j=1; j<=n; j+) m += k;（3）i=1; while (i<=n)i *= 2;（4）i=1; while (i<=n)i += 2;（5）k=100,i=10; do if (i<n) break;i+;while (i<k);（6）for (i=0; i<100; i+)for (j=0; j<i; j+)sum += j;（7）y=0; while (y*y*y <= n) y+;（8）int i=0; while(i

6、<n && ai!=k) i+;return i=n?-1:i ;答案： (1) O(n2) (2) O(n) (3) O(logn) (4) O(n) (5) O(1) (6) O(1) (7) O(n1/3) (8) O(n)4. 將整數(shù)設(shè)計為一個類，將整數(shù)相關(guān)的常見數(shù)學(xué)運算設(shè)計為類的接口并進行實現(xiàn)，如求與給定值的最大公約數(shù)、最小公倍數(shù)、枚舉所有因子等。解：#include "math.h"#include "vector"using std:vector;/定義自然數(shù)類class NaturalNumberpublic: Na

7、turalNumber(unsigned long int n=0):num(n)unsigned long int GreatestCommonDivisor(NaturalNumber & nn);/求解最大公約數(shù)unsigned long int LeaseCommonMultiple(NaturalNumber & nn);/求解最小公約數(shù)int GetFactors(vector <unsigned long int> & factors);/求所有因子，存儲在factors中，函數(shù)返回因子個數(shù)unsigned long int GetNumber

8、()return num;/其它外部接口private:unsigned long int EUCLID(NaturalNumber & n); /歐幾里德算法求解最大公約數(shù)unsigned long int num; /存儲真正的自然數(shù);/返回歐幾里德算法求解最大公約數(shù)unsigned long int NaturalNumber : EUCLID(NaturalNumber & nn)unsigned long int m = (num > nn.num) ? num : nn.num; /較大的自然數(shù)賦值給munsigned long int n = (num &l

9、t; nn.num) ? num : nn.num; /較小的自然數(shù)賦值給nunsigned long int r = m % n;while (r != 0)m = n; n = r; r = m % n;return n;/返回最大公約數(shù)unsigned long int NaturalNumber : GreatestCommonDivisor(NaturalNumber & nn)return EUCLID(nn);/返回最小公倍數(shù)unsigned long int NaturalNumber : LeaseCommonMultiple(NaturalNumber &

10、nn)unsigned long int temp = EUCLID(nn);return num * nn.GetNumber() / temp;int NaturalNumber : GetFactors( vector <unsigned long int> & factors )int t=0;int m = sqrt(double)num);vector <unsigned long int> bigfactors;for (unsigned long int i=1;i<m;i+)if ( 0 = num%i ) t+=2; factors.p

11、ush_back(i);bigfactors.push_back(num/i);if ( m*m = num ) t+; factors.push_back(m);vector <unsigned long int> :iterator it=bigfactors.end();if (bigfactors.size() doit-;factors.push_back(*it);while (it!=bigfactors.begin();return t;void main()NaturalNumber p(1);int xx = p.GreatestCommonDivisor(Na

12、turalNumber(120);int yy = p.LeaseCommonMultiple(NaturalNumber(120);vector <unsigned long int> f;int t = p.GetFactors(f);習(xí)題21. 填空題（1）在一個單鏈表中，已知每個結(jié)點包含data和next兩個域，q所指結(jié)點是p所指結(jié)點的直接前驅(qū)，若在q和p之間插入s所指結(jié)點，則執(zhí)行（_）和（_）操作。答案：q->next = s; s->next = p; 或 s->next=q->next; q->next = s;（2）表長為n的順序表，當(dāng)

13、在任何位置上插入或刪除一個元素的概率相等時，插入一個元素所需移動元素的平均個數(shù)為（_），刪除一個元素需要移動元素的平均個數(shù)為（_）。答案：n/2 (n-1)/2（3）表長為0的線性表稱為（_）。答案：空表（4）動態(tài)內(nèi)存管理是操作系統(tǒng)的基本功能之一，其作用是響應(yīng)用戶程序?qū)?nèi)存的（_）和（_）請求。答案：申請 釋放（5）順序表多采用（_）實現(xiàn)的，是一種隨機存取結(jié)構(gòu)，對表中任意結(jié)點存取操作的時間復(fù)雜度為（_）。而查找鏈表中的結(jié)節(jié)，需要從頭指針起順著鏈掃描才能得到，平均時間復(fù)雜度為（_）。因此，若線性表的操作主要是進行查找，很少進行插入或刪除操作時，采用（_）表比較合適。答案：數(shù)組 O(1) O(n)

14、 順序（6）在鏈表某個位置上進行插入和刪除操作，只需要修改（_）即可，而無須移動大量元素，操作的時間復(fù)雜度為（_）。而在順序表中進行插入和刪除操作，往往要移動大量元素，平均移動元素的數(shù)目為（_），平均時間復(fù)雜度為（_）。因此，若對線性表進行頻繁的插入和刪除操作時，采用（_）表相對合適。若插入和刪除主要發(fā)生在表頭和表尾，則采用（_）表更為合適。答案：指針 O(1) 表長的一半 O(n) 鏈 循環(huán)鏈 （7）靜態(tài)鏈表一般采用（_）存儲的鏈表結(jié)構(gòu)。答案：數(shù)組（8）對于32位計算機環(huán)境，若單鏈表中的數(shù)據(jù)類型為整性，則其存儲密度為（_），而若為雙鏈表，則存儲密度為（_）。若采用順序表存儲數(shù)據(jù)，則其存儲密度

15、為（_）。答案：50% 33% 1（9）向量是最常用的容器，STL中向量使用（_）實現(xiàn)，因此向量具有（_）表的所有特點，可以快速隨機存取任意元素。答案：數(shù)組 順序（10）操作系統(tǒng)在運行之初，有一塊很大的連續(xù)內(nèi)存塊供用戶程序申請，通常稱之為內(nèi)存池或（_）。答案：堆（11）循環(huán)鏈表與單鏈表的區(qū)別僅僅在于其尾結(jié)點的鏈域值不是（_），而是一個指向（_）的指針。答案：NULL(或空指針) 頭結(jié)點2. 選擇題（1）線性表的順序存儲結(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu)。A. 隨機存取 索引存取 B. 順序存取 隨機存取C. 隨機存取 順序存取 D. 索引存取 散列存取（2）

16、在雙向鏈表p所指結(jié)點之前插入s所指結(jié)點的操作是（ ）。A. p->left=s; s->right=p; p->left->right =s; s->left=p->left;B. p->right=s; p->right->left=s; s->left=p; s->right=p->right;C. s->right=p; s->left=p->left; p->left=s; p->left->right =s;D. s->right=p; s->left=p->

17、left; p->left->right =s; p->left=s;（3）若鏈表是利用C+指針來存儲結(jié)點的地址，結(jié)點空間的分配和收回都是由操作符new和delete動態(tài)執(zhí)行的，則稱該鏈表為（ ）鏈表A. 單向B. 雙向 C. 靜態(tài) D. 動態(tài)（4）將線性表存儲到計算機中可以采用多種不同的方法，按順序存儲方法存儲的線性表稱為（ ），按鏈?zhǔn)酱鎯Ψ椒ù鎯Φ木€性表稱為（ ）。A. 數(shù)組 單鏈表B. 順序表 鏈表C. 向量 靜態(tài)鏈表D. 靜態(tài)鏈表 動態(tài)鏈表（5）（ ）是STL中線性表的鏈?zhǔn)酱鎯π问?，STL標(biāo)準(zhǔn)庫中一般采用（ ）實現(xiàn)。A. vector 數(shù)組B. list 單鏈表C.

18、list 雙向循環(huán)鏈表D. vector 單鏈表（6）順序表的類型定義可經(jīng)編譯轉(zhuǎn)換為機器級。假定每個結(jié)點變量占用k(k>=1)個字節(jié)，b是順序表的第一個存儲結(jié)點的第一個單元的內(nèi)存地址，那么，第i個結(jié)點ai的存儲地址為（ ）。A. b+kiB. b+k(i-1)C. b+k(i+1) D. b-1+ki（7）在循環(huán)鏈表中，若不使用頭指針而改設(shè)為尾指針（rear），則頭結(jié)點和尾結(jié)點的存儲位置分別是（ ）。A. real和rear->next->next B. rear->next 和rearC. rear->next->next和rearD. rear和rear

19、->next（8）有時為了敘述方便，可以對一些概念進行簡稱，以下說法錯誤的是（ ）。A. 將“指針型變量”簡稱為“指針”B. 將“頭指針變量”簡稱為“頭指針”C. 將“修改某指針型變量的值” 簡稱為“修改某指針”D. 將“p中指針?biāo)附Y(jié)點” 簡稱為“P值”（9）以下說法錯誤的是（ ）。A. 對循環(huán)鏈表來說，從表中任一結(jié)點出發(fā)都能通過向前或向后操作而掃描整個循環(huán)鏈表。B. 對單鏈表來說，只有從頭結(jié)點開始才能掃描表中全部結(jié)點。C. 雙鏈表的特點是找結(jié)點的前趨和后繼都很容易。D. 對雙鏈表來說，結(jié)點*P的存儲位置既存放在其前趨結(jié)點的后繼指針域中，也存放在它的后繼結(jié)點的前趨指針域中。（10）以下

20、說法正確的是（ ）。A. 順序存儲方式的優(yōu)點是存儲密度大、且插入、刪除運算效率高。B. 鏈表的每個結(jié)點中都至少包含一個指針。C. 線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)。D. 順序存儲結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)，鏈?zhǔn)浇Y(jié)構(gòu)屬于動態(tài)結(jié)構(gòu)。說明:靜態(tài)鏈表是鏈?zhǔn)浇Y(jié)構(gòu),但屬于靜態(tài)存儲結(jié)構(gòu).鏈表的每個結(jié)點中都至少包含一個指針。原題中,“恰好”改為了”至少”。（11）單鏈表中，增加頭結(jié)點的目的是為了 ( )A. 使單鏈表至少有一個結(jié)點 B. 標(biāo)示表結(jié)點中首結(jié)點的位置C. 方便運算的實現(xiàn) D. 說明單鏈表是線性表的鏈?zhǔn)酱鎯崿F(xiàn)3. 程序選擇題（1）已知L指向帶表頭結(jié)點的非空單鏈表的頭結(jié)點，且P結(jié)點既不是首結(jié)點，也不是尾結(jié)

21、點，試從下列提供的答案中選擇合適的語句序列：a.刪除P結(jié)點的直接后繼結(jié)點的語句序列是（_）b.刪除P結(jié)點的直接前驅(qū)結(jié)點的語句序列是（_）c.刪除P結(jié)點的語句序列是（_）d.刪除首結(jié)點的語句序列是（_）e.刪除尾結(jié)點的語句序列是（_）(1) delete Q;(8) P->next = P->next->next(2) Q = P(9) P = P->next(3) L = L->next(10) while(P->next != Q) P = P->next;(4) P = L(11) while(P != NULL) P = P->next;

22、(5) Q = P->next(12) while(Q->next != NULL) P = Q ; Q = Q->next;(6) P->next = P(13) while(P->next->next != NULL) P = P->next;(7) P = P->next->next(14) while(P->next->next != Q) P = P->next; 答案: a. 5 8 1 b. 2 4 14 5 8 1 c. 2 4 10 8 1 d. 4 5 8 1 e. 4 13 5 8 1（2）已知p結(jié)點

23、是某雙向鏈表的中間結(jié)點，試從下面語句(1)(18)中選擇合適的語句序列，完成ae要求的操作。a. 在p結(jié)點后插入s結(jié)點的語句序列是_。b. 在p結(jié)點前插入s結(jié)點的語句序列是_。c. 刪除p結(jié)點的直接后繼結(jié)點的語句序列是_。d. 刪除p結(jié)點的直接前驅(qū)結(jié)點的語句序列是_。e. 刪除p結(jié)點的語句序列是_。(1) p->next = p->next->next;(10) p->prior->next = p;(2) p->prior = p->prior->prior;(11) p->next->prior = p;(3) p->nex

24、t = s;(12) p->next->prior = s;(4) p->prior = s;(13) p->prior->next = s;(5) s->next = p;(14)p->next->prior = p->prior;(6) s->prior = p;(15) q=p->next;(7) s->next = p->next;(16) q=p->prior;(8) s->prior = p->prior;(17) delete p;(9) p->prior->next =

25、p->next;(18) delete q;答案: a. 7 6 12 3 b. 5 8 13 4 c. 15 1 11 18 d. 16 2 10 18 e. 14 9 174分析以下各程序段的執(zhí)行結(jié)果。（1）程序段一vector <int> ivec(2,100); ivec.push_back (3); ivec.insert (ivec.begin (),10);vector <int>:iterator it = ivec.begin();ivec.erase (+it);ivec.pop_back();ivec.insert(ivec.end(),20

26、);for ( it = ivec.begin (); it != ivec.end(); it+ )cout << *it <<" " cout << endl;答案:10 100 20 分析:開始時容器中有100 100，然后為100 100 3，10 100 100 3，10 100 3，10 100，10 100 20（2）程序段二int a=1,2,3,4,5;vector <int> ivec(a, a+5);cout << "1.size: " << ivec.size

27、() << endl;ivec.resize(100);cout << "2.size: " << ivec.size() << endl;for (int j=0; j<95; j+) ivec.insert(ivec.end(),j);cout << "3.size: " << ivec.size() << endl;ivec.resize(100);ivec.reserve (20); cout << "4.size: " &l

28、t;< ivec.size() << endl;答案：1.size:5 2.size:100 3.size:195 4.size:100 （3）程序段三int a=1,2,3,4,5;list <int> ilist(3,2); ilist.assign(a,a+5);ilist.pop_back (); /1 2 3 4ilist.insert (ilist.end(),7);/1 2 3 4 7ilist.pop_front (); /2 3 4 7ilist.front ()=20; /20 3 4 7ilist.sort(); /3 4 7 20for (

29、 list<int>:iterator it = ilist.begin (); it != ilist.end(); it+ )cout << *it <<" " cout << endl;答案：3 4 7 205算法設(shè)計（1）分別編程實現(xiàn)順序表類和鏈表類，并設(shè)計完整的測試程序?qū)γ總€接口進行測試。（2）設(shè)A=（a1,a2,a3,.an）和B=(b1,b2,. .,bm)是兩個線性表（假定所含數(shù)據(jù)元素均為整數(shù)）。若n=m且ai=bi(i=1,. .,n),則稱A=B;若ai=bi(i=1,. .,j)且aj+1<bj+1

30、（j<n<=m）, 則稱A<B;在其他情況下均稱A>B。試編寫一個比較A和B的算法，當(dāng)A<B,A=B或A>B是分別輸出-1，0或者1。（3）假設(shè)有兩個按數(shù)據(jù)元素值遞增有序排列的線性表A和B，均以單鏈表作存儲結(jié)構(gòu)。編寫算法將A表和B表歸并成一個按元素值遞減有序（即非遞增有序，允許值相同）排列的線性表C，并要求利用原表(即A表和B表的)結(jié)點空間存放表C。（4）試分別以順序表和單鏈表作為存儲結(jié)構(gòu)，各寫一個實現(xiàn)線性表的就地（即使用盡可能少的附加空間）逆置的算法，在原表的存儲空間內(nèi)將線性表（a1，a2,，an-1，an)逆置為（an，an-1，a2，a1)。（5）假設(shè)

31、在長度大于1的循環(huán)鏈表中，既無頭結(jié)點也無頭指針。s為指向鏈表中某個結(jié)點的指針，試編寫算法刪除結(jié)點*s的直接前趨結(jié)點。答案：template <class T>void DeletePreNode (Node <T> * s)Node <T> * p = s;/得到s的結(jié)點的前一個結(jié)點的前一個結(jié)點while (p->next->next != s) p=p->next;/刪除p->next指向的結(jié)點Node <T> * q = p->next;p->next = s;delete q;（6）已知一單鏈表中的數(shù)據(jù)元

32、素含有三類字符(即:字母字符、數(shù)字字符和其它字符)。試編寫算法，構(gòu)造三個循環(huán)鏈表，使每個循環(huán)鏈表中只含同一類的字符，且利用原表中的結(jié)點空間作為這三個表的結(jié)點空間(頭結(jié)點可另辟空間)。（7）Josephus環(huán)問題：任給正整數(shù)n、k，按下述方法可得排列1，2，n的一個置換：將數(shù)字1，2，n環(huán)形排列（如圖2-36所示），按順時針方向從1開始計數(shù)，計滿k時輸出該位置上的數(shù)字（并從環(huán)中刪去該數(shù)字），然后從下一個數(shù)字開始繼續(xù)計數(shù)，直到環(huán)中所有數(shù)字均被輸出為止。例如，n=10，k=3時，輸出的置換是3，6，9，2，7，1，8，5，10，4。試編寫一算法，對輸入的任意正整數(shù)n、k，輸出相應(yīng)的置換數(shù)字序列。圖2

33、-36 Josephus環(huán)習(xí)題31 填空題（1）棧的進出原則是（_），隊列的進出原則是（_）。答案：后進先出（LIFO） 先進先出（FIFO）（2）設(shè)32位計算機系統(tǒng)中，空棧S存儲int型數(shù)據(jù)，棧頂指針為1024H。經(jīng)過操作序列 push(1)，push(2)，pop，push(5)，push(7)，pop，push(6)之后，棧頂元素為（_），棧底元素為（_），棧的高度為（_），輸出序列是（_），棧頂指針為（_）H。答案：6 1 3 2,7 1030（3）兩棧共享存儲空間，其數(shù)組大小為100，數(shù)組下標(biāo)從0開始。top1和top2分別為棧1和棧2的棧頂元素下標(biāo)，則棧1為空的條件為（_），棧2為

34、空的條件為（_），棧1或棧2滿的條件為（_）。/空棧的條件答案：top1=-1 top2=100 top1+1=top2（4）一個隊列的入隊順序是1234，則隊列的輸出順序是（_）。答案：1234（5）設(shè)循環(huán)隊列數(shù)組大小為100，隊頭指針為front，隊尾指針為rear；約定front指向隊頭元素的前一個位置，該位置永遠(yuǎn)不存放數(shù)據(jù)。則入隊操作時，修改rear=（_），出隊操作修改front=（_），隊空的判別條件為（_），隊滿的判別條件為（_）。若front=20，rear=60，則隊列長度為（_），若front=60,rear=20，則隊列長度為（_）。 /循環(huán)隊列答案：(rear+1)%1

35、00 (front+1)%100 rear=front (rear+1)%100=front 40 60（6）樸素模式匹配算法中，每個串的起始下標(biāo)均為1，變量i=100，j=10，分別表示主串和模式串當(dāng)前比較的字符元素下標(biāo)，若本次比較兩字符不同，則i回溯為（_），j回溯為（_）。答案：92 1（7）用循環(huán)鏈表表示的隊列長度為n，若只設(shè)頭指針，則出隊和入隊的時間復(fù)雜度分別為（_）和（_）。答案：O(1) O(n)2 選擇題（1）將一個遞歸算法改為對應(yīng)的非遞歸算法時，通常需要使用（ ）。A. 數(shù)組B. 棧 C. 隊列D. 二叉樹（2）四個元素1、2、3、4依次進棧，出棧次序不可能出現(xiàn)（ ）情況。A

36、. 1 2 3 4 B. 4 1 3 2 C. 1 4 3 2 D. 4 3 2 1（3）設(shè)循環(huán)隊列中數(shù)組的下標(biāo)范圍是1n，其頭尾指針分別為f和r，則其元素個數(shù)為（ ）。A. r-f B. r-f+1 C. (r-f) mod n +1 D. (r-f+n) mod n說明：這里的數(shù)組不是指C+數(shù)組，也就說假定數(shù)組長度依然為n，而不是n+1。（4）10行100列的二維數(shù)組A按行優(yōu)先存儲，其元素分別為A11 A10100，每個元素占4字節(jié)，已知Loc(A67)=10000H，則Loc(A419)=（ ）。A. FC11H B. 9248H C. 2F00H D. FD10H（5）設(shè)有兩個串s1和

37、s2，求s2在s1中首次出現(xiàn)的位置的運算稱為（ ）。A. 連接 B. 模式匹配 C. 求子串 D. 求串長（6）為了解決計算機主機和鍵盤輸入之間速度不匹配問題，通常設(shè)置一個鍵盤緩沖區(qū)，該緩沖區(qū)應(yīng)該是一個（ ）結(jié)構(gòu)。A. 棧 B. 隊列 C. 數(shù)組 D. 線性表（7）STL中的雙端隊列為（ ）。A. 順序容器B. 容器適配器C. 迭代器適配器D. 泛函適配器（8）STL中的（ ）允許用戶為隊列中的元素設(shè)置優(yōu)先級。A. 隊列適配器B. 雙端隊列C. 優(yōu)先級隊列適配器D. 棧適配器（9）string類型不支持以（ ）的方式操作容器，因此不能使用front、back和pop_back操作。A. 線性表

38、B.隊列C. 棧D. 串3 算法設(shè)計（1）設(shè)計一個算法判斷算數(shù)表達(dá)式的圓括號是否正確配對。（2）假定用帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)置一個指針指向隊尾元素，試設(shè)計該隊列類，完成相應(yīng)的入隊、出隊、置空隊、求隊長等操作接口。（3）設(shè)計算法把一個十進制數(shù)轉(zhuǎn)換為任意指定進制數(shù)。（4）設(shè)有一個背包可以放入的物品重量為S，現(xiàn)有n件物品，重量分別為w1，w2，wn。問能否從這n件物品中選擇若干件放入此背包，使得放入的重量之和正好為S。如果存在一種符合上述要求的選擇，則稱此背包問題有解，否則此問題無解，試用遞歸和非遞歸兩種方法設(shè)計解決此背包問題的算法。背包問題分析：背包問題是一個經(jīng)典的NP問題，它既簡單

39、形象容易理解，又在某種程度上能夠揭示動態(tài)規(guī)劃的本質(zhì)，故不少教材都把它作為動態(tài)規(guī)劃部分的第一道例題。本題目是最簡單的01背包問題，除此之外，還有許多由此衍生出來的很多復(fù)雜的背包問題。本題中，最容易想到的就是假定背包中已放入了部分物品，現(xiàn)將第i件物品試著放入背包中，如果可以放進去，背包的重量在原來的基礎(chǔ)上增加了wi；如果不可以放進去，說明加入后太重了，換下一件物品。如果所有的剩余物品都不能放入，說明以前放入的物品不合適，拿出上一次放入的物品，繼續(xù)試剩余的物品。遞歸解法：設(shè)背包函數(shù)為knapsack(int s, int n)，參數(shù)int s 為剩余重量，int n 為剩余物品數(shù)，返回值表示背包分配

40、是否成功。（1） 如果s=0，表示分配成功，返回1；（2） 如果s<0 或者 n<0，表示太重，或者物品分配完畢，返回0；（3） 執(zhí)行knapsack( s wi, n-1)，測試當(dāng)前這件物品放入是否成功。（3.1） 如果成功，說明當(dāng)前這件物品放入剛好最終分配成功。（4） 返回knapsack( s , n-1)，說明當(dāng)前物品不合適，減小剩余物品數(shù)，繼續(xù)測試。測試代碼：/*簡單的背包問題遞歸解*/#include"stdio.h"#define N 6 /*物品數(shù)量*/#define S 8 /*背包大小*/ int WN+1=0,1,2,3,4,5,6;/*數(shù)

41、據(jù)，各物品重量，W0不使用*/ /*背包函數(shù)knapsack() 參數(shù)int s 剩余重量int n 剩余物品數(shù)返回int 背包分配是否成功*/int knapsack(int s,int n)if(s = 0)/*分配結(jié)束，成功*/return 1;if(s < 0 | (s > 0 && n < 1)/*沒有可用空間，或者物品分配完畢*/return 0;if( knapsack(s - Wn , n - 1)/*遞歸*/printf("%-4d",Wn);/*輸出*/return 1;return knapsack(s , n - 1

42、);int main()if(knapsack(S , N)/*遞歸調(diào)用*/printf("nOK!n");elseprintf("Failed!");return 1;/*main*/ 非遞歸解法：一件一件的物品往包（即棧）里放，發(fā)現(xiàn)有問題，拿出來，放其他的物品。（1）i=1（2）從第i件到第n件測試每件物品，對于第j次循環(huán)，測試第j件物品（2.1）如果該物品可以放，入棧（2.2）若棧的容量剛好達(dá)到要求，成功，打印棧元素。（2.3）繼續(xù)測試j+1件物品（3）若沒有成功（3.1）若?？?，返回失敗（3.2）將棧頂物品（設(shè)第k個）出棧（3.3）令i=k+1，

43、返回（2）代碼：#include"stdio.h"#define N 6 /*物品數(shù)量*/#define S 8 /*背包大小*/int WN+1=0,1,2,3,4,5,6;/*數(shù)據(jù)，各物品重量，W0不使用*/int stack1000=0;int value=0;int size=0;knapsackstack() int i=1;while (1)for (int j=i;j<=N;j+)if (value+Wj<=S) stacksize+=j; value+=Wj;if (value=S)printf("得到一組解：");for (

44、int p=0;p<size;p+) printf("%d ",Wstackp); printf("OK!n");break;else if (value>S) break;if (size=0) printf("Finished!");exit(0);i=stack-size+1;value-=Wi-1;void main()knapsackstack();習(xí)題41. 填空題（1）一般來說，數(shù)組不執(zhí)行（_）和（_）操作，所以通常采用（_）方法來存儲數(shù)組。通常有兩種存儲方式：（_）和（_）。答案：刪除 插入 順序存儲 行優(yōu)

45、先存儲 列優(yōu)先存儲（2）設(shè)8行8列的二維數(shù)組起始元素為A00，按行優(yōu)先存儲到起始元素下標(biāo)為0的一維數(shù)組B中，則元素B23在原二維數(shù)組中為（_）。若該二維數(shù)組為上三角矩陣，按行優(yōu)先壓縮存儲上三角元素到起始元素下標(biāo)為0的一維數(shù)組C中，則元素C23即為原矩陣中的（_）元素。答案：A27 A35（3）設(shè)二維數(shù)組A為6行8列，按行優(yōu)先存儲，每個元素占6字節(jié)，存儲器按字節(jié)編址。已知A的起始存儲地址為1000H，數(shù)組A占用的存儲空間大小為（_）字節(jié)，數(shù)組A的最后一個元素的下標(biāo)為（_），該元素的第一個字節(jié)地址為（_）H，元素A14的第一個字節(jié)的地址為（_）H。（提示：下標(biāo)從0開始計）答案：288 A57 11

46、1AH 1048H（4）設(shè)C+中存儲三維數(shù)組Amnp，則第一個元素為a000，若按行優(yōu)先存儲，則aijk前面共有（_）個元素；若按列優(yōu)先存儲，則aijk前面共有（_）個元素。答案：inp+jp+k i+mj+mnk（5）常見的稀疏矩陣壓縮方法有：（_）和（_）。答案：三元組表 十字鏈表（6）廣義表（a），（b，c），d），（e）的長度為（_），表頭為（_），表尾為（_）。答案：3 （a） （b，c），d），（e）（7）設(shè)廣義表LS（a），（b，c），d），（e），若用取表頭操作GetHead（）和取表尾操作GetTail（）進行組合操作，則取出元素b的運算為（_）。答案：GetHead(Get

47、Head(GetHead(GetTail(LS)（8）若廣義表A滿足GetHead（A）GetTail（A），則A（_）。答案：（）2. 問答題（1）根據(jù)下面的矩陣，寫出矩陣轉(zhuǎn)置后的三元組表，起始行列值為1。 RowColItem13-316152112251831934135256314矩陣行數(shù)：7矩陣列數(shù)：6非零元素個數(shù)：8（2）對于如下稀疏矩陣，請寫出對應(yīng)的三元組順序表，若采用順序取，直接存的算法進行轉(zhuǎn)置運算，引入輔助數(shù)組number和position，分別表示矩陣各列的非零元素個數(shù)和矩陣中各列第一個非零元素在轉(zhuǎn)置矩陣中的位置，請寫出數(shù)組中的各元素（所有數(shù)組起始元素下標(biāo)為0）。 原矩陣

48、Col0123Numbercol1021Positioncol0113RowColItem022 103 22-1235行數(shù)：4列數(shù)：4非零元素個數(shù)：4（3）對于上題中的稀疏矩陣，寫出對應(yīng)的三元組表和十字鏈表。 三元組表：RowColItem022 103 22-1235行數(shù)：4列數(shù)：4非零元素個數(shù)：4 十字鏈表：3. 算法設(shè)計（1）設(shè)計上三角矩陣存儲類，實現(xiàn)如下接口： 對于上三角矩陣ANN，可按行優(yōu)先壓縮存儲和按列優(yōu)先壓縮存儲。 對于給定的一維數(shù)組BM，可根據(jù)行優(yōu)先壓縮存儲或列優(yōu)先壓縮存儲還原原始的上三角矩陣。（2）針對24位真彩色BMP圖像文件，編寫程序?qū)崿F(xiàn)如下功能： 讀取24位真彩色BM

49、P圖像文件。 將原圖像轉(zhuǎn)換為24位灰度圖像，并進行保存。轉(zhuǎn)按公式如下： Grey=0.3*Red+0.59*Blue+0.11*Green 將24位灰度圖像轉(zhuǎn)換為8位灰度圖像，并進行保存。 將8位灰度圖像分別進行4鄰域和8鄰域平滑，并分別進行保存。 習(xí)題51. 填空題（1）已知二叉樹中葉子數(shù)為50，僅有一個孩子的結(jié)點數(shù)為30，則總結(jié)點數(shù)為（_）。答案：129（2）3個結(jié)點可構(gòu)成（_）棵不同形態(tài)的二叉樹。答案：5（3） 設(shè)樹的度為5，其中度為15的結(jié)點數(shù)分別為6、5、4、3、2個，則該樹共有（_）個葉子。答案：31（4）在結(jié)點個數(shù)為n（n>1）的各棵普通樹中，高度最小的樹的高度是（_），它有（_）個葉子結(jié)點，（_）個分支結(jié)點。高度最大的樹的高度是（_），它有（_）個葉子結(jié)點，（_）個分支結(jié)點。答案：2 n-1 1 n 1 n-1（5）深度為k的二叉樹，至多有（_）個結(jié)點。答案：2k-1（6）（7）有n個結(jié)點并且其