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