數據結構與算法習題及答案(已修改)

　

【正文】 第1章 緒論習題1．簡述下列概念：數據、數據元素、數據項、數據對象、數據結構、邏輯結構、存儲結構、抽象數據類型。2．試舉一個數據結構的例子，敘述其邏輯結構和存儲結構兩方面的含義和相互關系。3．簡述邏輯結構的四種基本關系并畫出它們的關系圖。4．存儲結構由哪兩種基本的存儲方法實現？5．選擇題（1）在數據結構中，從邏輯上可以把數據結構分成（ ）。A．動態結構和靜態結構 B．緊湊結構和非緊湊結構C．線性結構和非線性結構 D．內部結構和外部結構（2）與數據元素本身的形式、內容、相對位置、個數無關的是數據的（ ）。A．存儲結構 B．存儲實現C．邏輯結構 D．運算實現（3）通常要求同一邏輯結構中的所有數據元素具有相同的特性，這意味著（ ）。 A．數據具有同一特點B．不僅數據元素所包含的數據項的個數要相同，而且對應數據項的類型要一致C．每個數據元素都一樣D．數據元素所包含的數據項的個數要相等（4）以下說法正確的是（ ）。A．數據元素是數據的最小單位B．數據項是數據的基本單位C．數據結構是帶有結構的各數據項的集合D．一些表面上很不相同的數據可以有相同的邏輯結構（5）以下與數據的存儲結構無關的術語是（ ）。A．順序隊列 B. 鏈表 C. 有序表 D. 鏈棧（6）以下數據結構中，（ ）是非線性數據結構A．樹 B．字符串 C．隊 D．棧6．試分析下面各程序段的時間復雜度。（1）x=90。 y=100。while(y0)if(x100) {x=x10。y。}else x++。（2）for (i=0。 in。 i++)for (j=0。 jm。 j++)a[i][j]=0。（3）s=0。 for i=0。 in。 i++)for(j=0。 jn。 j++) s+=B[i][j]。sum=s。（4）i=1。 while(i=n) i=i*3。（5）x=0。for(i=1。 in。 i++) for (j=1。 j=ni。 j++)x++。（6）x=n。 //n1y=0。while(x≥(y+1)* (y+1)) y++。（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因為x++共執行了n1+n2+……＋1= n(n1)/2，所以執行時間為O（n2）（6）O()第2章 線性表1．選擇題（1）一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ ）。A．110 B．108 C．100 D．120（2）在n個結點的順序表中，算法的時間復雜度是O(1)的操作是（ ）。A．訪問第i個結點（1≤i≤n）和求第i個結點的直接前驅（2≤i≤n） B．在第i個結點后插入一個新結點（1≤i≤n）C．刪除第i個結點（1≤i≤n）D．將n個結點從小到大排序（3） 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動 的元素個數為（ ）。A．8 B． C．63 D．7（4）鏈接存儲的存儲結構所占存儲空間（ ）。A．分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針B．只有一部分，存放結點值C．只有一部分，存儲表示結點間關系的指針D．分兩部分，一部分存放結點值，另一部分存放結點所占單元數（5）線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址（ ）。A．必須是連續的 B．部分地址必須是連續的C．一定是不連續的 D．連續或不連續都可以（6）線性表Ｌ在（ ）情況下適用于使用鏈式結構實現。A．需經常修改Ｌ中的結點值 Ｂ．需不斷對Ｌ進行刪除插入 C．Ｌ中含有大量的結點 Ｄ．Ｌ中結點結構復雜（7）單鏈表的存儲密度（ ）。A．大于1 B．等于1 C．小于1 D．不能確定（8）將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數是（ ）。A．n B．2n1 C．2n D．n1（9）在一個長度為n的順序表中，在第i個元素（1≤i≤n+1）之前插入一個新元素時須向后移動（ ）個元素。A．ni B．ni+1 C．ni1 D．i(10) 線性表L=(a1，a2,……an)，下列說法正確的是（ ）。A．每個元素都有一個直接前驅和一個直接后繼B．線性表中至少有一個元素C．表中諸元素的排列必須是由小到大或由大到小D．除第一個和最后一個元素外，其余每個元素都有一個且僅有一個直接前驅和直接后繼。(11) 若指定有n個元素的向量，則建立一個有序單鏈表的時間復雜性的量級是（ ）。A．O(1) B．O(n) C．O(n2) D．O(nlog2n)(12) 以下說法錯誤的是（ ）。A．求表長、定位這兩種運算在采用順序存儲結構時實現的效率不比采用鏈式存儲結構時實現的效率低B．順序存儲的線性表可以隨機存取C．由于順序存儲要求連續的存儲區域，所以在存儲管理上不夠靈活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。 (14) 在雙向鏈表存儲結構中，刪除p所指的結點時須修改指針（ ）。A．pnextprior=pprior。 ppriornext=pnext。B．pnext=pnextnext。 pnextprior=p。C．ppriornext=p。 pprior=ppriorprior。D．pprior=pnextnext。 pnext=ppriorprior。(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。2．算法設計題（1）將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中不允許有重復的數據。void MergeList_L(LinkList amp。La,LinkList amp。Lb,LinkList amp。Lc){ pa=Lanext。 pb=Lbnext。 Lc=pc=La。 //用La的頭結點作為Lc的頭結點 while(pa amp。amp。 pb){ if(padatapbdata){ pcnext=pa。pc=pa。pa=panext。} else if(padatapbdata) {pcnext=pb。 pc=pb。 pb=pbnext。} else {// 相等時取La的元素，刪除Lb的元素 pcnext=pa。pc=pa。pa=panext。 q=pbnext。delete pb 。pb =q。} } pcnext=pa?pa:pb。 //插入剩余段 delete Lb。 //釋放Lb的頭結點} （2）將兩個非遞減的有序鏈表合并為一個非遞增的有序鏈表。要求結果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中允許有重復的數據。void union(LinkListamp。 La, LinkListamp。 Lb, LinkListamp。 Lc, ) { pa = Lanext。 pb = Lbnext。 // 初始化 Lc=pc=La。 //用La的頭結點作為Lc的頭結點 Lcnext = NULL。 while ( pa || pb ) { if ( !pa ) { q = pb。 pb = pbnext。 } else if ( !pb ) { q = pa。 pa = panext。 } else if (padata = pbdata ) { q = pa。 pa = panext。 } else { q = pb。 pb = pbnext。 } qnext = Lcnext。 Lcnext = q。 // 插入 } delete Lb。 //釋放Lb的頭結點} （3）已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。請設計算法求出A與B的交集，并存放于A鏈表中。void Mix(LinkListamp。 La, LinkListamp。 Lb, LinkListamp。 Lc, ) {pa=lanext。pb=lbnext。∥設工作指針pa和pb；Lc=pc=La。 //用La的頭結點作為Lc的頭結點while(paamp。amp。pb) if(padata==pbdata)∥交集并入結果表中。 { pcnext=pa。pc=pa。pa=panext。 u=pb。pb=pbnext。 delete u。} else if(padatapbdata) {u=pa。pa=panext。 delete u。}else {u=pb。 pb=pbnext。 delete u。}while(pa){ u=pa。 pa=panext。 delete u。}∥ 釋放結點空間while(pb) {u=pb。 pb=pbnext。 delete u。}∥釋放結點空間pcnext=null。∥置鏈表尾標記。delete Lb。 ∥注： 本算法中也可對B表不作釋放空間的處理（4）已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。請設計算法求出兩個集合A和B 的差集（即僅由在A中出現而不在B中出現的元素所構成的集合），并以同樣的形式存儲，同時返回該集合的元素個數。void Difference（LinkedList A，B，*n）∥A和B均是帶頭結點的遞增有序的單鏈表，分別存儲了一個集合，本算法求兩集合的差集，存儲于單鏈表A中，*n是結果集合中元素個數，調用時為0{p=Anext； ∥p和q分別是鏈表A和B的工作指針。 q=Bnext； pre=A； ∥pre為A中p所指結點的前驅結點的指針。 while（p!=null amp。amp。 q!=null）if（pdataqdata）{pre=p；p=pnext；*n++；} ∥ A鏈表中當前結點指針后移。else if（pdataqdata）q=qnext； ∥B鏈表中當前結點指針后移。else {prenext=pnext； ∥處理A，B中元素值相同的結點，應刪除。 u=p； p=pnext； delete u；} ∥刪除結點（5）設計算法將一個帶頭結點的單鏈表A分解為兩個具有相同結構的鏈表B、C，其中B表的結點為A表中值小于零的結點，而C表的結點為A表中值大于零的結點（鏈表A的元素類型為整型，要求B、C表利用A表的結點）。（6）設計一個算法，通過一趟遍歷在單鏈表中確定值最大的結點。ElemType Max (LinkList L ){ if(Lnext==NULL) return NULL。 pmax=Lnext。 //假定第一個結點中數據具有最大值 p=Lnextnext。 while(p != NULL ){//如果下一個結點存在 if(pdata pmaxdata) pmax=p。 p=pnext。 } return pmaxdata。（7）設計一個算法，通過遍歷一趟，將鏈表中所有結點的鏈接方向逆轉，仍利用原表的存儲空間。void inverse(LinkList amp。L) { // 逆置帶頭結點的單鏈表 L p=Lnext。 Lnext=NULL。 while ( p) { q=pnext。 // q指向*p的后繼 pnext=Lnext。 Lnext=p。 // *p插入在頭結點之后