【正文】 第2章 線性表1．選擇題（1）順序表中第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ ）。A．110 B．108 C．100 D．120答案：B解釋：順序表中的數(shù)據(jù)連續(xù)存儲，所以第5個元素的地址為：100+2*4=108。（3） 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動 的元素個數(shù)為（ ）。A．8 B． C．63 D．7答案：B解釋：平均要移動的元素個數(shù)為：n/2。（4）鏈接存儲的存儲結構所占存儲空間（ ）。A．分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針B．只有一部分，存放結點值C．只有一部分，存儲表示結點間關系的指針D．分兩部分，一部分存放結點值，另一部分存放結點所占單元數(shù)答案：A（5）線性表若采用鏈式存儲結構時，要求內(nèi)存中可用存儲單元的地址（ ）。A．必須是連續(xù)的 B．部分地址必須是連續(xù)的C．一定是不連續(xù)的 D．連續(xù)或不連續(xù)都可以答案：D（6）線性表Ｌ在（ ）情況下適用于使用鏈式結構實現(xiàn)。A．需經(jīng)常修改Ｌ中的結點值 Ｂ．需不斷對Ｌ進行刪除插入 C．Ｌ中含有大量的結點 Ｄ．Ｌ中結點結構復雜答案：B解釋：鏈表最大的優(yōu)點在于插入和刪除時不需要移動數(shù)據(jù)，直接修改指針即可。（7）單鏈表的存儲密度（ ）。A．大于1 B．等于1 C．小于1 D．不能確定答案：C解釋：存儲密度是指一個結點數(shù)據(jù)本身所占的存儲空間和整個結點所占的存儲空間之比，假設單鏈表一個結點本身所占的空間為D，指針域所占的空間為N，則存儲密度為：D/(D+N)，一定小于1。（8）將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是（ ）。A．n B．2n1 C．2n D．n1答案：A解釋：當?shù)谝粋€有序表中所有的元素都小于（或大于）第二個表中的元素，只需要用第二個表中的第一個元素依次與第一個表的元素比較，總計比較n次。（9）在一個長度為n的順序表中，在第i個元素（1≤i≤n+1）之前插入一個新元素時須向后移動（ ）個元素。A．ni B．ni+1 C．ni1 D．I答案：B(10) 線性表L=(a1，a2,……an)，下列說法正確的是（ ）。A．每個元素都有一個直接前驅和一個直接后繼B．線性表中至少有一個元素C．表中諸元素的排列必須是由小到大或由大到小D．除第一個和最后一個元素外，其余每個元素都有一個且僅有一個直接前驅和直接后繼。答案：D (12) 以下說法錯誤的是（ ）。 A．求表長、定位這兩種運算在采用順序存儲結構時實現(xiàn)的效率不比采用鏈式存儲結構時實現(xiàn)的效率低B．順序存儲的線性表可以隨機存取C．由于順序存儲要求連續(xù)的存儲區(qū)域，所以在存儲管理上不夠靈活D．線性表的鏈式存儲結構優(yōu)于順序存儲結構 答案：D解釋：鏈式存儲結構和順序存儲結構各有優(yōu)缺點，有不同的適用場合。(13) 在單鏈表中，要將s所指結點插入到p所指結點之后，其語句應為（ ）。A．snext=p+1。 pnext=s。B．(*p).next=s。 (*s).next=(*p).next。C．snext=pnext。 pnext=snext。D．snext=pnext。 pnext=s。 答案：D (14) 在雙向鏈表存儲結構中，刪除p所指的結點時須修改指針（ ）。A．pnextprior=pprior。 ppriornext=pnext。B．pnext=pnextnext。 pnextprior=p。C．ppriornext=p。 pprior=ppriorprior。D．pprior=pnextnext。 pnext=ppriorprior。答案：A(15) 在雙向循環(huán)鏈表中，在p指針所指的結點后插入q所指向的新結點，其修改指針的操作是（ ）。A．pnext=q。 qprior=p。 pnextprior=q。 qnext=q。B．pnext=q。 pnextprior=q。 qprior=p。 qnext=pnext。C．qprior=p。 qnext=pnext。 pnextprior=q。 pnext=q。D．qprior=p。 qnext=pnext。 pnext=q。 pnextprior=q。答案：C2．算法設計題（1）將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中不允許有重復的數(shù)據(jù)。 [算法描述]void MergeList(LinkList amp。La,LinkList amp。Lb,LinkList amp。Lc){//合并鏈表La和Lb，合并后的新表使用頭指針Lc指向 pa=Lanext。 pb=Lbnext。 //pa和pb分別是鏈表La和Lb的工作指針,初始化為相應鏈表的第一個結點 Lc=pc=La。 //用La的頭結點作為Lc的頭結點 while(pa amp。amp。 pb){if(padatapbdata){pcnext=pa。pc=pa。pa=panext。} //取較小者La中的元素，將pa鏈接在pc的后面，pa指針后移 else if(padatapbdata) {pcnext=pb。 pc=pb。 pb=pbnext。} //取較小者Lb中的元素，將pb鏈接在pc的后面，pb指針后移 else //相等時取La中的元素，刪除Lb中的元素{pcnext=pa。pc=pa。pa=panext。 q=pbnext。delete pb 。pb =q。} } pcnext=pa?pa:pb。 //插入剩余段 delete Lb。 //釋放Lb的頭結點} （6）設計一個算法，通過一趟遍歷在單鏈表中確定值最大的結點。 [算法描述]ElemType Max (LinkList L ){ if(Lnext==NULL) return NULL。 pmax=Lnext。 //假定第一個結點中數(shù)據(jù)具有最大值 p=Lnextnext。 while(p != NULL ){//如果下一個結點存在 if(pdata pmaxdata) pmax=p。//如果p的值大于pmax的值，則重新賦值 p=pnext。//遍歷鏈表 } return pmaxdata。第3章 棧和隊列1．選擇題（1）若讓元素1，2，3，4，5依次進棧，則出棧次序不可能出現(xiàn)在（ ）種情況。A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1答案：C解釋：棧是后進先出的線性表，不難發(fā)現(xiàn)C選項中元素1比元素2先出棧，違背了棧的后進先出原則，所以不可能出現(xiàn)C選項所示的情況。（2）若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為（ ）。A．i B．ni C．ni+1 D．不確定答案：C解釋：棧是后進先出的線性表，一個棧的入棧序列是1，2，3，…，n，而輸出序列的第一個元素為n，說明1，2，3，…，n一次性全部進棧，再進行輸出，所以p1=n，p2=n1，…，pi=ni+1。（3）數(shù)組Ｑ［ｎ］用來表示一個循環(huán)隊列，ｆ為當前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數(shù)小于ｎ，計算隊列中元素個數(shù)的公式為（ ）。A．rf B．(n+fr)%n C．n+rf D．（n+rf)%n答案：D解釋：對于非循環(huán)隊列，尾指針和頭指針的差值便是隊列的長度，而對于循環(huán)隊列，差值可能為負數(shù)，所以需要將差值加上MAXSIZE（本題為n），然后與MAXSIZE（本題為n）求余，即（n+rf)%n。（4）鏈式棧結點為：(data,link)，并將刪除結點的值保存到x中,則應執(zhí)行操作（ ）。A．x=topdata。top=toplink； B．top=toplink。x=toplink； C．x=top。top=toplink； D．x=toplink；答案：A解釋：x=topdata將結點的值保存到x中，top=toplink棧頂指針指向棧頂下一結點，即摘除棧頂結點。（5）設有一個遞歸算法如下 int fact(int n) { //n大于等于0 if(n=0) return 1。 else return n*fact(n1)。 }則計算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（ ）。A．n+1 B．n1 C． n D． n+2答案：A解釋：特殊值法。設n=0，易知僅調(diào)用一次fact(n)函數(shù)，故選A。（6）棧在（ ）中有所應用。A．遞歸調(diào)用 B．函數(shù)調(diào)用 C．表達式求值 D．前三個選項都有答案：D解釋：遞歸調(diào)用、函數(shù)調(diào)用、表達式求值均用到了棧的后進先出性質。（7）為解決計算機主機與打印機間速度不匹配問題，通常設一個打印數(shù)據(jù)緩沖區(qū)。主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結構應該是（ ）。A．隊列 B．棧 C． 線性表 D．有序表答案：A解釋：解決緩沖區(qū)問題應利用一種先進先出的線性表，而隊列正是一種先進先出的線性表。（8）設棧S和隊列Q的初始狀態(tài)為空，元素eeeee5和e6依次進入棧S，一個元素出棧后即進入Q，若6個元素出隊的序列是eeeee5和e1，則棧S的容量至少應該是（?。?。A．2 B．3 C．4 D． 6答案：B解釋：元素出隊的序列是eeeee5和e1，可知元素入隊的序列是eeeee5和e1，即元素出棧的序列也是eeeee5和e1，而元素eeeee5和e6依次進入棧，易知棧S中最多同時存在3個元素，故棧S的容量至少為3。（9）若一個棧以向量V[1..n]存儲，初始棧頂指針top設為n+1，則元素x進棧的正確操作是( )。A．top++。 V[top]=x。 B．V[top]=x。 top++。C．top。 V[top]=x。 D．V[top]=x。 top。答案：C解釋：初始棧頂指針top為n+1，說明元素從數(shù)組向量的高端地址進棧，又因為元素存儲在向量空間V[1..n]中，所以進棧時top指針先下移變?yōu)閚，之后將元素x存儲在V[n]。（10）設計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（?。?shù)據(jù)結構最佳。A．線性表的順序存儲結構 B．隊列 C. 線性表的鏈式存儲結構 D. 棧答案：D解釋：利用棧的后進先出原則。（11）用鏈接方式存儲的隊列，在進行刪除運算時（?。?。A. 僅修改頭指針 B. 僅修改尾指針C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改答案：D解釋：一般情況下只修改頭指針，但是，當刪除的是隊列中最后一個元素時，隊尾指針也丟失了，因此需對隊尾指針重新賦值。（12）循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操作為（　）。A. rear=rear+1 B. rear=