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