數據結構(c語言版)第2版習題答案—嚴蔚敏(簡化版)(已修改)

　

【正文】 第2章 線性表1．選擇題（1）順序表中第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ ）。A．110 B．108 C．100 D．120答案：B解釋：順序表中的數據連續存儲，所以第5個元素的地址為：100+2*4=108。（3） 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動 的元素個數為（ ）。A．8 B． C．63 D．7答案：B解釋：平均要移動的元素個數為：n/2。（4）鏈接存儲的存儲結構所占存儲空間（ ）。A．分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針B．只有一部分，存放結點值C．只有一部分，存儲表示結點間關系的指針D．分兩部分，一部分存放結點值，另一部分存放結點所占單元數答案：A（5）線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址（ ）。A．必須是連續的 B．部分地址必須是連續的C．一定是不連續的 D．連續或不連續都可以答案：D（6）線性表Ｌ在（ ）情況下適用于使用鏈式結構實現。A．需經常修改Ｌ中的結點值 Ｂ．需不斷對Ｌ進行刪除插入 C．Ｌ中含有大量的結點 Ｄ．Ｌ中結點結構復雜答案：B解釋：鏈表最大的優點在于插入和刪除時不需要移動數據，直接修改指針即可。（7）單鏈表的存儲密度（ ）。A．大于1 B．等于1 C．小于1 D．不能確定答案：C解釋：存儲密度是指一個結點數據本身所占的存儲空間和整個結點所占的存儲空間之比，假設單鏈表一個結點本身所占的空間為D，指針域所占的空間為N，則存儲密度為：D/(D+N)，一定小于1。（8）將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數是（ ）。A．n B．2n1 C．2n D．n1答案：A解釋：當第一個有序表中所有的元素都小于（或大于）第二個表中的元素，只需要用第二個表中的第一個元素依次與第一個表的元素比較，總計比較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．求表長、定位這兩種運算在采用順序存儲結構時實現的效率不比采用鏈式存儲結構時實現的效率低B．順序存儲的線性表可以隨機存取C．由于順序存儲要求連續的存儲區域，所以在存儲管理上不夠靈活D．線性表的鏈式存儲結構優于順序存儲結構 答案：D解釋：鏈式存儲結構和順序存儲結構各有優缺點，有不同的適用場合。(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) 在雙向循環鏈表中，在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）將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中不允許有重復的數據。 [算法描述]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。 //假定第一個結點中數據具有最大值 p=Lnextnext。 while(p != NULL ){//如果下一個結點存在 if(pdata pmaxdata) pmax=p。//如果p的值大于pmax的值，則重新賦值 p=pnext。//遍歷鏈表 } return pmaxdata。第3章 棧和隊列1．選擇題（1）若讓元素1，2，3，4，5依次進棧，則出棧次序不可能出現在（ ）種情況。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解釋：棧是后進先出的線性表，不難發現C選項中元素1比元素2先出棧，違背了棧的后進先出原則，所以不可能出現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）數組Ｑ［ｎ］用來表示一個循環隊列，ｆ為當前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數小于ｎ，計算隊列中元素個數的公式為（ ）。A．rf B．(n+fr)%n C．n+rf D．（n+rf)%n答案：D解釋：對于非循環隊列，尾指針和頭指針的差值便是隊列的長度，而對于循環隊列，差值可能為負數，所以需要將差值加上MAXSIZE（本題為n），然后與MAXSIZE（本題為n）求余，即（n+rf)%n。（4）鏈式棧結點為：(data,link)，并將刪除結點的值保存到x中,則應執行操作（ ）。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)需要調用該函數的次數為（ ）。A．n+1 B．n1 C． n D． n+2答案：A解釋：特殊值法。設n=0，易知僅調用一次fact(n)函數，故選A。（6）棧在（ ）中有所應用。A．遞歸調用 B．函數調用 C．表達式求值 D．前三個選項都有答案：D解釋：遞歸調用、函數調用、表達式求值均用到了棧的后進先出性質。（7）為解決計算機主機與打印機間速度不匹配問題，通常設一個打印數據緩沖區。主機將要輸出的數據依次寫入該緩沖區，而打印機則依次從該緩沖區中取出數據。該緩沖區的邏輯結構應該是（ ）。A．隊列 B．棧 C． 線性表 D．有序表答案：A解釋：解決緩沖區問題應利用一種先進先出的線性表，而隊列正是一種先進先出的線性表。（8）設棧S和隊列Q的初始狀態為空，元素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，說明元素從數組向量的高端地址進棧，又因為元素存儲在向量空間V[1..n]中，所以進棧時top指針先下移變為n，之后將元素x存儲在V[n]。（10）設計一個判別表達式中左，右括號是否配對出現的算法，采用（　）數據結構最佳。A．線性表的順序存儲結構 B．隊列 C. 線性表的鏈式存儲結構 D. 棧答案：D解釋：利用棧的后進先出原則。（11）用鏈接方式存儲的隊列，在進行刪除運算時（　）。A. 僅修改頭指針 B. 僅修改尾指針C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改答案：D解釋：一般情況下只修改頭指針，但是，當刪除的是隊列中最后一個元素時，隊尾指針也丟失了，因此需對隊尾指針重新賦值。（12）循環隊列存儲在數組A[0..m]中，則入隊時的操作為（　）。A. rear=rear+1 B. rear=