北郵C++數(shù)據(jù)結(jié)構(gòu)課后習(xí)題習(xí)題3習(xí)題與講解

習(xí)題31．填空題（部分答案）（1）棧的進(jìn)出原則是（先出（LIFO）先進(jìn)（2）設(shè)32位計(jì)算機(jī)系統(tǒng)中，空棧S存儲int型數(shù)據(jù)，棧頂指針為1024H。經(jīng)過操作序列push(1)，push(2)，pop，push(5)，push(7)，pop，push(6)之后，棧___________），棧底元素為（___________），棧的___________），輸出___________），棧___________）H。：6132,71030（3）兩棧其數(shù)組大小為100，數(shù)組下標(biāo)從0開始。top1和top2分別為棧2的棧1為空的___________），棧2為空的條件為（___________），棧1或棧2滿的___________）。：top1==-1top2==100top1+1==top2（4）一個(gè)隊(duì)列的順序是1234，則隊(duì)列的：1234（5）設(shè)循環(huán)隊(duì)列___________），隊(duì)列的進(jìn)出原則是（___________）。答案：后進(jìn)先出（FIFO）頂元素為（高度為（序列是（頂指針為（答案共享存儲空間，1和棧頂元素下標(biāo)，則棧條件為（條件為（答案入隊(duì)輸出順序是（___________）。答案數(shù)組大小為100，隊(duì)頭指針為front，隊(duì)尾指針為rear；約定front指向隊(duì)前一個(gè)位置，該位置永遠(yuǎn)不存放數(shù)據(jù)。則入隊(duì)操作時(shí)，修改rear=（___________），___________），隊(duì)滿的判別條件___________），若front=60,rear=20，頭元素的出隊(duì)操作修改front=（___________），隊(duì)空的___________）。若front=20，rear=60，則隊(duì)列___________）。：(rear+1)%100(front+1)%100rear==front(rear+1)%100=front4060（6）樸素模式匹配算法中，起始下標(biāo)均為1，變量i=100，j=10，分i回溯為（___________），j判別條件為（為（長度為（則隊(duì)列長度為（答案每個(gè)串的別表示主串和模式串當(dāng)前比較的字符元素下標(biāo)，若本次比較兩字符不同，則回溯為（___________）。：921（7）用循環(huán)鏈表表示的隊(duì)列長度為n，若只設(shè)頭指針，則出隊(duì)（___________）和（___________）。：O(1)O(n)（8）一般來說，數(shù)組不執(zhí)行（（___________）方法存來儲數(shù)組。通常有兩種存儲方式：（：刪除插入順序存儲行優(yōu)先存儲列優(yōu)先存儲（9）設(shè)8行8列的二維數(shù)組起始元素為A[0][0]，按行優(yōu)先存儲到起始元素下標(biāo)為0的一維數(shù)組B中，則元素B[23]在原二維數(shù)組中為（___________）。若該二維數(shù)組為上三角矩陣，按行優(yōu)先壓縮存儲上三角元素到起始元素下標(biāo)為0的一維數(shù)組C中，則元素C[23]即為原陣中的（___________）元素。：A[2][7]A[3][5]（10）設(shè)二維數(shù)組A為6行8列，按行優(yōu)先存儲，每個(gè)元素占6字節(jié)，存儲器按字節(jié)編址。已知A的起始存儲地址為1000H，數(shù)組A占用的___________）字節(jié)，數(shù)組A的最后一個(gè)元素的___________），該元素的第一個(gè)字節(jié)地址為（___________）答案和入隊(duì)的時(shí)間復(fù)雜度分別為答案___________）和（所以通常采用___________）操作，___________）。___________）和（答案矩答案存儲空間大小為（下標(biāo)為（

H，元素A[1][4]的第一個(gè)字節(jié)的地址為（答案：288A[5][7]111AH1048H（11）10行100列的二維數(shù)組A按行優(yōu)先存儲，其元素分別為A[1][1]~A[10][100]，每個(gè)4字節(jié)，已知Loc(A[6][7])=10000H，則Loc(A[4][19])=（）。答案：FD10H（12）設(shè)C++中存儲三維數(shù)組___________）H。（提示：下標(biāo)從0開始計(jì)）元素占A，則第一個(gè)元素為a，若按行優(yōu)先存儲，則a前面共mnp000ijk有（___________）個(gè)元素；若按列優(yōu)先存儲，則a前面共有（___________）個(gè)元素。ijk答案：inp+jp+ki+mj+mnk（13）常見的稀疏矩陣壓縮方法有：（___________）和（___________）。答案：三元組表十字鏈表2．選擇題（1）將一個(gè)遞歸算法改為對應(yīng)的非遞歸算法時(shí)，通常需要使用（）。A.數(shù)組B.棧C.隊(duì)列D.二叉樹（2）四個(gè)元素1、2、3、4依次進(jìn)棧，出棧次序不可能出現(xiàn)（）情況。A.1234B.4132C.1432D.4321（3）設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是1~n，其頭尾指針分別為f和r，則其元素個(gè)數(shù)為（）。A.r-fB.r-f+1C.(r-f)modn+1D.(r-f+n)modn說明：這里的數(shù)組不是指C++數(shù)組，也就說假定數(shù)組長度依然為n，而不是n+1。（4）設(shè)有兩個(gè)串s1和s2，求s2在s1中次首出現(xiàn)的位置的運(yùn)算稱為（）。A.連接B.模式匹配C.求子串D.求串長置一個(gè)鍵盤緩沖區(qū)，該（5）為了解決計(jì)算機(jī)主機(jī)和鍵盤輸入之間速度不匹配問題，通常設(shè)緩沖區(qū)應(yīng)該是一個(gè)（）結(jié)構(gòu)。A.棧B.隊(duì)列（6）STL中的雙端隊(duì)列為（）。A.順序容器B.容器適配器C.迭代器適配器（7）STL中的（）允許用戶為隊(duì)列中的元素設(shè)置優(yōu)先A.隊(duì)列適配器B.雙端隊(duì)列C.優(yōu)先級隊(duì)列適配器D.棧適配器（8）string類型不支持以（）的方式操作容器，因此不能使用front、back和pop_backC.數(shù)組D.線性表D.泛函適配器級。操作。A.線性表B.隊(duì)列C.棧D.串3.問答題（1）根據(jù)下面的矩陣，寫出矩陣轉(zhuǎn)置后的三元組表，起始行列值為1。01290000000050030000140001300000180000015000000

Row1Col3Item-316151218921253134135526314矩陣行數(shù)：7矩陣列數(shù)：6非零元素個(gè)數(shù)：8（2）對于如下稀疏矩陣，請寫出對應(yīng)的三元組順序表，若采用順序取，直接存的算法進(jìn)行轉(zhuǎn)置運(yùn)算，引入輔助數(shù)組number[]和position[]，分別表示矩陣各列的非零元素個(gè)數(shù)和矩陣中各列第一個(gè)非零元素在轉(zhuǎn)置矩陣中的位置，請寫出數(shù)組中的各元素（所有數(shù)組起始元素下標(biāo)為0）。002030000015原矩陣0000Row0Col2Item2Col010101221313103Number[col]Position[col]22-1523行數(shù)：4列數(shù)：4非零元素個(gè)數(shù)：4（3）對于上題中的稀疏矩陣，寫出對應(yīng)的三元組表和十字鏈表。三元組表：Row0Col2Item210322-1523行數(shù)：4列數(shù)：4非零元素個(gè)數(shù)：4十字鏈表：40123411201100012022132322-12354.算法設(shè)計(jì)（1）設(shè)計(jì)一個(gè)算法判斷算數(shù)表達(dá)式的圓括號是否正確配對。（2）假定用帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)置一個(gè)指針指向隊(duì)尾元素，試設(shè)計(jì)該隊(duì)列類，完成相應(yīng)的入隊(duì)、出隊(duì)、置空隊(duì)、求隊(duì)長等操作接口。（3）設(shè)計(jì)算法把一個(gè)十進(jìn)制數(shù)轉(zhuǎn)換為任意指定進(jìn)制數(shù)。（4）設(shè)有一個(gè)背包可以放入的物品重量為S，現(xiàn)有n件物品，重量分別為w，w2，……，1wn。問能否從這n件物品在一種符合上述要求的解此決背包問題的算法。問題分析：背包問題是一個(gè)經(jīng)典的NP問題，態(tài)規(guī)劃的本質(zhì)，故不少教材都把它作為動態(tài)規(guī)劃部分的背包問題，除此之外，還有許多由此衍生出來的很多復(fù)雜的背包中選擇若干件放入此背包，使得放入的重量之和正好為S。如果存選擇，則稱此背包問題有解，否則此問題無解，試用遞歸和非遞歸兩種方法設(shè)計(jì)背包它既簡單形象容易理解，又在某種程度上能夠揭示動第一道例題。本題目是最簡單的01問題。本題中，最容易想到的就是假定背包中已放入了部分物品，現(xiàn)將第i件物品試著放入背去，說明都不能放入，說明以前放入的物品不合次放入的物品，繼續(xù)試剩余的物品。包中，如果可以放進(jìn)去，背包的重量在原來的基礎(chǔ)上增加了wi；如果不可以放進(jìn)加入后太重了，換下一件物品。如果所有的剩余物品適，拿出上一遞歸解法：設(shè)背包函數(shù)為knapsack(ints,intn)，參數(shù)ints為剩余重量，intn為剩余物品數(shù)，返回值表示背包分配是否成功。（1）如果s==0，表示分配成（2）如果s<0或者n<0，表示太重，或者物品分配完（3）執(zhí)行knapsack(s–wi,n-1)，測試當(dāng)前這件物品放入是否成（3.1）如果成功，說明當(dāng)前這件物品放入剛好最終分配成功。功，返回1；畢，返回0；功。（4）返回knapsack(s,n-1)，說明當(dāng)前物品不合適，減小剩余物品數(shù)，繼續(xù)測試。測試代碼：/*簡單的背包問題遞歸解*/#include"stdio.h"#defineN6/*物品數(shù)量*/#defineS8/*背包大小*/intW[N+1]={0,1,2,3,4,5,6};/*數(shù)據(jù)，各物品重量，W[0]不使用*//*背包函數(shù)knapsack()參數(shù)ints剩余重量intn剩余物品數(shù)返回int背包分配是否成功*/intknapsack(ints,intn){if(s==0)/*分配結(jié)束，成功*/return1;if(s<0||(s>0&&n<1))/*沒有可用空間，或者物品分配完畢*/return0;if(knapsack(s-W[n],n-1)){/*遞歸*/printf("%-4d",W[n]);/*輸出*/return1;}returnknapsack(s,n-1);}intmain(){if(knapsack(S,N))/*遞歸調(diào)用*/printf("\nOK!\n");printf("Failed!");elsereturn1;}/*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個(gè)）出棧（3.3）令i=k+1，返回（2）代碼：#include"stdio.h"#defineN6/*物品數(shù)量#defineS8/*背包大小intW[N+1]={0,1,2,3,4,5,6};/*數(shù)據(jù)，各物品重量，W[0]不使用*/*/*/intstack[1000]={0};intvalue=0;intsize=0;knapsackstack(){inti=1;while(1){for(intj=i;j<=N;j++){if(value+W[j]<=S){s