【正文】 例如， ABC 變?yōu)?BCA 的操作步驟為 XXSXSS。 12．對帶有頭結(jié)點(diǎn)的鏈隊 lq，判定隊列中只有一個數(shù)據(jù)元素的條件是 __lqfrontnext= lqrear___。___。 三、填空題 1．向一個棧頂指針為 Top 的鏈棧中插入一個 s 所指的結(jié)點(diǎn) 時，其進(jìn)行的操作是 __ snext=Top； Top =s； __。 A．線性表的順序存儲結(jié)構(gòu) *B．棧 C．隊列 D．線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 二、判斷題 √ 1．在順序棧棧滿情況下，不能再入棧，否則會產(chǎn)生“上溢”。 A． (sq． rear+1)％ maxsize==(sq． front+1)％ maxsize； B． (sq． rear+1)％ maxsize==sq． front+1； *C． (sq． rear+1)％ maxsize==sq． front； D． sq． rear==sq． front； 12．循環(huán)隊列的隊空條件為 ( )。 13 *A． =+1； []=x。 ／／刪除 q q=p— next； } } 第三節(jié) 棧和隊列 一、選擇題 1．設(shè)有一順序棧 s，元素 s1， s2， s3， s4， s5， s6 依次入棧，如果 6 個元素出棧的順序是 s2， s3， s4， s6， s5， s1，則棧的容量至少應(yīng)該是 ( )。q!=NULL) {if(pexp==qexp)／／兩結(jié)點(diǎn)的指數(shù)相同時，將兩系數(shù)相加生成新結(jié)點(diǎn)插入 c 中 {x=pcoef+qcoef； if(x!=0){s=(PLink)malloc(sizeof(struct PNode))； scoef=x； sexp=pexp； rnext=s； r=s； } p=pnext； q=qnext； } else if(pexpqexp)／／兩結(jié)點(diǎn)的指數(shù)不同時，將較小系數(shù)的結(jié)點(diǎn)復(fù)制成新結(jié)點(diǎn)插入 c 中 {s=(PLink)malloc(sizeof(struct PNode))； scoef=qcoef； sexp=qexp； rnext=s； r=s； q=qnext； } else {s=(PLink)malloc(sizeof(struct PNode))； scoef=pcoef； sexp=pexp； rnext=s； r=s； p=pnext； } } while(p!=NULL) ／／復(fù)制 A 的余下部分 {s=(PLink)malloc(sizeof(struct PNode))； scoef=pcoef； sexp=pexp； rnext=s： r=s； p=pnext； } while(ql=NULL) ／／復(fù)制 B 的余下部分 {s=(PLink)malloc(sizeof(struct PNode))； scoef=qcoef； sexp=qexp； rnext=s； r=s； q=qnext； } rnext=NULL； ／／最后結(jié)點(diǎn)的 next 域置為空 12 s=pc； pc=pcnext； ／／刪除 c 的頭結(jié)點(diǎn) free(s)； return pc。 答： typedef struct PNode {int coef； ／／系數(shù) int exp； ／／指數(shù) struct PNode *next； }*PLink； PLink CreatPoly( ) {／／建立多項式 head=(PLink)malloc(sizeof(struct PNode))； r=head； printf(”輸入系數(shù)和指數(shù)：” )； scanf(amp。pdata!=x)p=pnext； if(pdata==x) {ppriornext=pnext； pnextprior=pprior； free(p)； } else{printf(”沒有值為 x 的結(jié)點(diǎn)” )； exit(0)； } } 16．設(shè)有一個雙循環(huán)鏈表，其中有一結(jié)點(diǎn)的指針為 p，編寫算法將 p 與其右邊的一個結(jié)點(diǎn)進(jìn)行交換。 i++；／／跳過相同的元素 } } while(iAlength) Adata[m++]=Adata[i++]； ／／ A 的剩余元素重新存儲 A1ength=m； } 15．雙循環(huán)鏈表中，設(shè)計滿足下列條件的算法。iamp。amp。 答：分析：因為既不知道此單循環(huán)鏈表的頭指針，也不知道其尾指針，所以找 s 的前驅(qū)就只能從 s 開始，順次向后尋找。pnext!=NULL) {q=p— next； ／／ q 指向偶數(shù)序號的結(jié)點(diǎn) p— next=q— next； ／／將 q 從 A 表中刪除 r— next=q； ／／將 q 結(jié)點(diǎn)鏈接到 B 鏈表的末尾 r=q； ／／ r 總是指向 B 鏈表的最后 — amp。然后在 lb 中找到第 j 個結(jié)點(diǎn)，將 p 所指向的 la表中的第 i個及 q所指向的最后一個共 len個結(jié)點(diǎn)插入到 lb中。jn) {if([i][j]) ／／ A 中當(dāng)前元素較小 {Cdata[k]=[il； i++； ] else {Cdata[k]=[j]。 while(p!=NULLamp。(x=Ldata[i])) i++； ／／找正確的插入位置 for(k=Llength1。 Ldata[i]=[j]。 五、 算法設(shè)計題 假設(shè)算法中用到的順序表和鏈表結(jié)構(gòu)如下： define maxsize 100。 while(pnext) p=pnext； pnext=q。具體移動的次數(shù)取決于表長和插入、刪除的結(jié)點(diǎn)的位置。 19．在雙循環(huán)鏈表中，若要在指 p 所指結(jié)點(diǎn)前插入 s 所指的結(jié)點(diǎn)，則需執(zhí)行下列語句： snext=p； sprior=pprior； __ ppriornext __=s； pprior=s； 20．在單鏈表中，若要在 p 所指結(jié)點(diǎn)之前插入 s 所指的結(jié)點(diǎn)，可進(jìn)行下列操作： snext=___ pnext __； pnext=s； temp=pdata； pdata=__ sdata ___； sdata=__ temp _； 四、應(yīng)用題 1．描述以下三個概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn) (第一個元素結(jié)點(diǎn) )。 10． 在順序表中插入或刪除一個元素，平均需要移動 _一半 _元素，具體移動的元素個數(shù)與 __元素的位置 _有關(guān)。 2．線性結(jié)構(gòu)的基本特征是：若至少含有一個結(jié)點(diǎn)，則除起始結(jié)點(diǎn)沒有直接 __前驅(qū) _外，其他結(jié)點(diǎn)有且僅有一個直接 __前驅(qū) _；除終端結(jié)點(diǎn)沒有直接 __后繼 _外，其他結(jié)點(diǎn)有且僅有一個直接 _后繼 __。 √ 6．在單鏈表中，可以從頭結(jié)點(diǎn)開始查找任何一個元素。 A ． ppriornext==pnextnext B ． ppriorprior==pnextprior *C ． ppriornext==pnextprior D． pnextnext==ppriorprior 18．在循環(huán)鏈表中，將頭指針改設(shè)為尾指針 rear 后，其頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的存儲位置分別是 ( )。 snext=q； 13. 在一個單鏈表中，若 *p 結(jié)點(diǎn)不是最后結(jié)點(diǎn)。 A．無需為表示結(jié)點(diǎn)間的 邏輯關(guān)系而增加額外的存儲空間 B．可以方便地隨機(jī)存取表中的任一結(jié)點(diǎn) *C．插入和刪除操作較方便 D．由于順序表要求占用連續(xù)的空間，存儲分配只能預(yù)先進(jìn)行 (靜態(tài)分配 ) 7．在含有 n 個結(jié)點(diǎn)的順序存儲的線性表中，在任一結(jié)點(diǎn)前插入一個結(jié)點(diǎn)所需移動結(jié)點(diǎn)的平均次數(shù)為 ( )。 (1)int rec(int n) {if(n==1)return(1)； else return(n*rec(n1))； } (2)x=91； y=100； While (y0) if(x10) y； (3)i=1； j=0； while(i+j=n) if(ij)j++； else i++。 4．邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是什么關(guān)系？ 答：在數(shù)據(jù)結(jié)構(gòu)中，邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是密切相關(guān)的，存儲結(jié)構(gòu)不僅將數(shù)據(jù)元素存儲到計算機(jī)中，而且還要表示各數(shù)據(jù)元素之間的邏輯關(guān)系。其中每一條指令表示一個或多個操作。 17．常見時間復(fù)雜度的量級有：常數(shù)階 O(__1_)、對數(shù)階 O(__log2n___)、線性階 O(__n__)、平方階 O(_n2_)和指數(shù)階 O(__2n_)。 for (i=1； i=n； i++) A[i， i]=0； 9．下列程序段的時間復(fù)雜度是 __ O（ n2） ___。 三、填空題 1．所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)元素之間的 ____邏輯關(guān)系 _____。 A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位 B．?dāng)?shù)據(jù)項是數(shù)據(jù)的基本單位 C．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合 *D．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合 二、判斷題 ╳ 1．?dāng)?shù)據(jù)元素是 數(shù)據(jù)的最小單位。 (1) A．算法 *B．?dāng)?shù)據(jù)元素 C．?dāng)?shù)據(jù)操作 D．邏輯結(jié)構(gòu) (2)A．操作 B．映像 C．存儲 *D．關(guān)系 4．在數(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)和外部結(jié)構(gòu) 5．線性表的順序存儲結(jié)構(gòu)是一種 ( )的存儲結(jié) 構(gòu)。 √ 2．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。 2， 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括三方面的內(nèi)容 ___數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、對數(shù)據(jù)施加的操作 ___。 S=0； for(i=1； i=n； i++) for(j=1； j=n； j++) s=s+B[i,j]； sum=s； 10．存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)的 ___物理 __實(shí)現(xiàn)。通常認(rèn)為，具有指數(shù)階量級的算法是 __不可行 __的。算法應(yīng)該具有下列特性：可行性、確定性、有窮性、輸入和輸出。邏輯結(jié)構(gòu)與計算機(jī)無關(guān)，存儲結(jié)構(gòu)是數(shù)據(jù) 元素之間的關(guān)系在計算機(jī)中的表示。 (4)x=n； y=0； while(x=(y+1)*(y+1)) y++； 答： (1) O(n) (2) O(1) (3) O(n) (4) O(n1/2) 9． 設(shè) n 為正數(shù)。 4 A． n *B． n/2 C． (n1)/2 D． (n+1)/2 8．在含有 n 個結(jié)點(diǎn)的順序存儲的線性表中，刪除一個結(jié)點(diǎn)所需移動結(jié)點(diǎn)的平均次數(shù)為 ( )。在 *p 之后插入結(jié)點(diǎn) *s，則執(zhí)行 ( )。 A． rear 和 rearnextnext *B． rearnext 和 rear C． rearnextnext 和 rear D． rear 和 rearnext 19．循環(huán)鏈表的主要優(yōu)點(diǎn)是 ( )。 ╳ 7．線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。 5 3．所有結(jié)點(diǎn)按一對一的鄰接關(guān)系構(gòu)成的整體就是 __線性 __結(jié)構(gòu)。 11．在一個長度為 n 的向量的第 i(1≤ i≤ n+1)個元素之前插入一個元素時，需向后移動 ___ ni+1__個元素。 答：首元結(jié)點(diǎn)是指鏈表中存儲的線性表中的第一個數(shù)據(jù)元素的結(jié)點(diǎn)。 4．為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指 針更好？ 答：單循環(huán)鏈表中無論設(shè)置尾指針還是頭指針都可以遍歷表中任一個結(jié)點(diǎn)，但設(shè)置尾指針時，若在表尾進(jìn)行插入或刪除操作可在 O(1)時間內(nèi)完成，同樣在表頭進(jìn)行插入或刪除操作也可在 O(1)時間內(nèi)完成。 qnext=NULL； } return L； } 答：如果長度大于 1，則將首元結(jié)點(diǎn)刪除并插入到表尾。 Typedef struct node1 {datatype data[maxsize]。 Ldata[j]=t。k=i； k) ／／元素從后往前依次后移 Ldata[k+1]=Ldata[k]； Ldata[i]=x； ／／ x 插入到正確位置 Llength++； ) L 是一個遞減有序表，試寫一個算法將 x 插入其中后仍保持 L 的有序性。amp。j++； } ／／ B 中當(dāng)前元素較小 k++； } if (i==m) for(t=j；