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