【正文】 （6）在圖形結(jié)構(gòu)中，每個結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后繼結(jié)點(diǎn)數(shù)可以是（ ）。答：j=0，第1次循環(huán)：j=1，s=10。i=n。max1,int amp。 答：B（4）鏈?zhǔn)酱鎯Y(jié)構(gòu)所占存儲空間（ ）。其優(yōu)點(diǎn)是插入或刪除元素時很方便，使用靈活；缺點(diǎn)是存儲密度小，存儲空間利用率低。因此④最節(jié)省運(yùn)算時間。L) //L為引用型參數(shù){ int i,j=0,k。 e=[0]。 q=qnext。用p遍歷原單鏈表A的所有數(shù)據(jù)結(jié)點(diǎn)，若為偶數(shù)結(jié)點(diǎn)，將其鏈到A中，若為奇數(shù)結(jié)點(diǎn)，將其鏈到B中。解：先建立一個待插入的結(jié)點(diǎn)，然后依次與鏈表中的各結(jié)點(diǎn)的數(shù)據(jù)域比較大小，找到插入該結(jié)點(diǎn)的位置，最后插入該結(jié)點(diǎn)。 }}（8）有一個單鏈表L，其中可能出現(xiàn)值域重復(fù)的結(jié)點(diǎn)，設(shè)計(jì)一個算法刪除值域重復(fù)的結(jié)點(diǎn)。并分析算法的時間復(fù)雜度。 if (p==NULL) //未找到值為x的結(jié)點(diǎn) return 0。 pnext=Lnext。 tc=s。 tc=s。 q!=NULL) { if (pdataqdata) p=pnext。amp。 ElemType a[]={1,3,6,8,10,20}。 printf(求A、B差集E\n)。 答：A（8）元素A、B、C、D順序連續(xù)進(jìn)入隊(duì)列qu后，隊(duì)頭元素是（ ① ），隊(duì)尾元素是（ ② ）。（3）有5個元素，其進(jìn)棧次序?yàn)锳、B、C、D、E，在各種可能的出棧次序中，以元素C、D最先出棧（即C第一個且D第二個出棧）的次序有（ ）。答：相同點(diǎn)：都屬地線性結(jié)構(gòu)，都可以用順序存儲或鏈表存儲；棧和隊(duì)列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運(yùn)算加以限制。 //初始化臨時棧 if (StackEmpty(st)) //空棧返回0 return 0。 []=pdata。 ==1對應(yīng)的算法如下：//初始化隊(duì)列算法void InitQueue1(QueueType amp。qu,ElemType amp。 s=(QNode *)malloc(sizeof(QNode))。 rearnext=qnext。}void DestroyStack(LStack *amp。x) //出棧運(yùn)算算法{ LStack *p。I39。 printf(各序列判斷結(jié)果如下:\n)。4. 算法設(shè)計(jì)題（1）設(shè)計(jì)一個算法RepChar(s,x,y)，將順序串s中所有字符x替換成字符y。 } } return 1。解：采用Index算法思路設(shè)計(jì)由順序串s、t產(chǎn)生最大公共子串str。 } i++。DispStr(str)。 答：①L ②J ③C ④I（7）稀疏矩陣一般的壓縮存儲方法有兩種，即（ ）。 while (A[j]==0) j。 }}（3）如果矩陣A中存在這樣的一個元素A[i][j]滿足條件：A[i][j]是第i行中值最小的元素，且又是第j列中值最大的元素，則稱之為該矩陣的一個馬鞍點(diǎn)。i++) if (A[i][j]max[j]) max[j]=A[i][j]。 minmax(a)。typedef struct{ ElemType *p。 [k]=x。 for (i=0。 Getij(B,i,j,y)。 Setij(B,0,1,2)。 答：C（2）樹是結(jié)點(diǎn)的有限集合，它（ ① ）根結(jié)點(diǎn)，記為T。log2(i+1)答：① 2h1 ② 2h1 ③ 2h1。（4）證明完全二叉樹的每棵子樹也都是完全二叉樹。答：①31 ②32（3）設(shè)一棵完全二叉樹有700個結(jié)點(diǎn)，則共有（ ）個葉子結(jié)點(diǎn)。A. n=h+m B. h+m=2n C. m=h1 D. n=2h1答：D（10）完全二叉樹中，編號為i的結(jié)點(diǎn)的層次是（ ）。 DestroyMat(A)。 printf(A:\n)。i。 x=[k]。amp。}上機(jī)實(shí)驗(yàn)題5采用一維動態(tài)數(shù)組模擬二維數(shù)組的操作，即將一個二維數(shù)組的元素存放在一個一維數(shù)組中，一維數(shù)組的空間根據(jù)二維數(shù)組的大小動態(tài)分配。i++) for (j=0。jn。ji。解：從前向后找為零的元素A[i]，從后向前找非零的元素A[j]，將A[i]和A[j]進(jìn)行交換。那么，這個數(shù)組的體積是（ ① ）個字節(jié)。DispStr(t)。 if (tlenmlen) //將較大長度者賦給midx與mlen { midx=i。 p=pnext。對應(yīng)算法如下：int increase(LinkString *s){ LinkString *p=snext,*q。答：O(n)3. 簡答題（1）設(shè)s為一個長度為n的串，其中的字符各不相同，則s中的互異的非平凡子串（非空且不同于s本身）的個數(shù)是多少？答：由串s的特性可知，1個字符的子串有n個，2個字符的子串有n1個，3個字符的子串有n2個，…，n2個字符的子串有3個，n1個字符的子串有2個。 //棧為空時返回1,否則返回0}void main(){ char str1[]=IOIIOIOO。 InitStack(ls)。 //創(chuàng)建結(jié)點(diǎn)*p用于存放x pnext=ls。 struct node *next。 free(rear)。 //鏈隊(duì)結(jié)點(diǎn)類型//初始化隊(duì)列void InitQueue(QNode *amp。 []=x。初始時tag=0，進(jìn)行成功的插入操作后tag=1，進(jìn)行成功的刪除操作后tag=0；因?yàn)橹挥性诓迦氩僮骱箨?duì)列才有可能滿，只有在刪除操作后隊(duì)列才有可能空，因此，這樣的隊(duì)列的基本要素如下：初始時：tag=0，front=rear隊(duì)空條件：== amp。 } st。對應(yīng)算法如下：int GetBottom(SqStack st,ElemType amp。（8）設(shè)有數(shù)組A[0..m]作為循環(huán)隊(duì)列的存儲空間，front為隊(duì)頭指針（它指向隊(duì)首元素的前一位置），rear為隊(duì)尾指針（它指向隊(duì)尾元素的位置），則元素出隊(duì)并保存到x中的操作是（ ）。 答：C2. 填空題（1）棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為（ ① ）。 答：C（4）已知一個棧的進(jìn)棧序列是1，2，3，…，n，其輸出序列的第一個元素是i（1≤i≤n）則第j（1≤j≤n）個出棧元素是（ ）。 printf(求A、B交集C\n)。 tc=s。 tc=L3。 p=L1next。 q=qnext。amp。對應(yīng)的算法如下：void Reverse(SLink *amp。對應(yīng)的算法如下：int swap(DLink *L,ElemType x){ DLink *p=Lnext,*q。 r=rnext。 xpdata) //若x小于p所指結(jié)點(diǎn)的data域值 if (xpdata) { q=p。 p=pnext。 } else return 0。L,ElemType x){ SLink *p=L,*q=pnext。解：在有序順序表L中，所有重復(fù)的元素應(yīng)是相鄰存放的，用k保存不重復(fù)出現(xiàn)的元素個數(shù)，[0..0]，置e=[0]，用i從1開始遍歷L的所有元素：[i]≠e時，[k]中，k增1，置e=[i]，最后將L的length置為k。（2）設(shè)計(jì)一個算法從順序表中刪除重復(fù)的元素，并使剩余元素間的相對次序保持不變。插入結(jié)點(diǎn)需找到前驅(qū)結(jié)點(diǎn)，所以在尾結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)，需找到尾結(jié)點(diǎn)，對應(yīng)的時間復(fù)雜度為O(n)。答：03. 簡答題（1）試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn)。 printf(最大元素值=%d,次大元素值=%d\n,max1,max2)。}答：由于內(nèi)循環(huán)j的取值范圍，所以i≤n/2，則，該程序段的時間復(fù)雜度為O(n2)。答：語句s的執(zhí)行次數(shù)。 s=s+10*j。答：①邏輯結(jié)構(gòu) ②存儲結(jié)構(gòu) ③運(yùn)算（2）數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是 ① 和 ② 。答：①線性結(jié)構(gòu) ②非線性結(jié)構(gòu)（3）數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D是 ① 的有限集合，R是D上的 ② 有限集合。} while (jn amp。（7）設(shè)n為問題規(guī)模，求以下算法的時間復(fù)雜度。上機(jī)實(shí)驗(yàn)題1有一個整型數(shù)組a，其中含有n個元素，設(shè)計(jì)盡可能好的算法求其中的最大元素和次大元素，并采用相關(guān)數(shù)據(jù)測試。}練習(xí)題21. 單項(xiàng)選擇題（1）數(shù)據(jù)在計(jì)算機(jī)存儲器內(nèi)表示時，物理地址與邏輯地址相對順序相同并且是連續(xù)的，稱之為（ ）。在什么情況下用順序表比鏈表好？答：順序存儲結(jié)構(gòu)中，相鄰數(shù)據(jù)元素的存放地址也相鄰，并要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。在僅有頭指針不帶頭結(jié)點(diǎn)的循環(huán)單鏈表中，刪除第一個結(jié)點(diǎn)的時間復(fù)雜度O(n)，因?yàn)閯h除第一個結(jié)點(diǎn)后還要將其改為循環(huán)單鏈表；在尾結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)的時間復(fù)雜度也為O(n)。解：對于順序表L，用i從1開始遍歷其元素，[0..j]（j的初值為0）中沒有重復(fù)的元素。對應(yīng)的算法如下：void delsame1(SqList amp。 //p指向*q的前驅(qū)結(jié)點(diǎn) while (q!=NULL amp。 } return 1。 } } ranext=rbnext=NULL。 p=pnext。 } } p=pnext。 while (p!=NULL amp。L){ SLink *p=Lnext,*q。 q!=NULL) { if (pdataqdata) { s=(SLink *)malloc(sizeof(SLink))。 } } while (p!=NULL) { s=(SLink *)malloc(sizeof(SLink))。 q=L2next。 p=L1next。 p=pnext。 InterSection(A,B,D)。 +1 答：D（5）設(shè)順序棧st的棧頂指針top的初始時為1，?？臻g大小為MaxSize，則判定st棧為棧空的條件為（ ）。不允許插入和刪除運(yùn)算的一端稱為（ ② ）。答：front=(front+1)%(m+1)。x){ ElemType e。 //定義一個順序棧 =1。amp。 =1。rear){ rear=NULL。 rear=NULL。} LStack。 //插入*p結(jié)點(diǎn)作為棧頂結(jié)點(diǎn) ls=p。 //鏈棧ls初始化 for (i=0。 char str2[]=IOOIOIIO。所以，非平凡子串的個數(shù)=n+(n1)+(n2)+…+2=。 if (p!=NULL) { while (pnext!=NULL) { q=pnext。 } if (nmax) max=n。 mlen=tlen。 printf(求s、t的最大公共子串str\n)。假設(shè)存儲數(shù)組元素A[1,0]的第一個字節(jié)的地址是0，則存儲數(shù)組A的最后一個元素的第一個字節(jié)的地址是（ ② ）。對應(yīng)的算法如下：void move(ElemType A[],int n){ int i=0,j=n1。j++) { tmp=A[i*n+j]。j++) //計(jì)算出每列的最大值元素，放入max[1..n]之中 { max[j]=A[0][j]。jn。設(shè)計(jì)一個算法實(shí)現(xiàn)兩個二維數(shù)組的相加運(yùn)算。 j=0 amp。 return 1。i++) for (j=0。 DispMat(A)。 DestroyMat(B)。A. i B. 233。答：350（4）設(shè)一棵完全二叉樹具有1000個結(jié)點(diǎn)，則此完全二叉樹有（ ① ）個葉子結(jié)點(diǎn)，有（ ② ）個度為2的結(jié)點(diǎn)，有（ ③ ）個單分支結(jié)點(diǎn)。證明：讓T是一棵完全二叉樹，S是它的一棵子樹。答：2i1（6）深度為h的完全二叉樹至少有（ ① ）個結(jié)點(diǎn)，至多有（ ② ）個結(jié)點(diǎn)，若按自上而下，從左到右次序給結(jié)點(diǎn)編號（從1開始），則編號最小的葉子結(jié)點(diǎn)的編號是（ ③ ）。 C. 235。}練習(xí)題61. 單項(xiàng)選擇題（1）樹最適合用來表示（ ）。 Setij(B,0,0,2)。j++) { Getij(A,i,j,x)。 //參數(shù)錯誤返回0}void DispMat(Mat2 M) //輸出二維數(shù)組{ int i,j,k。 j) { k=i*+j。解：對應(yīng)的程序如下：include include typedef int ElemType。a[i][j])。im。 A[j*n+i]=tmp。 while (ij) { while (A[i]!=0) i++。若按列存儲，則A[5,7]的第一個字節(jié)的地址是（ ④ ）。 printf(str:)。 //繼續(xù)掃描t中第j+tlen字符之后的字符 } else j++。}上機(jī)實(shí)驗(yàn)題4兩個非空串s和t采用順序存儲結(jié)構(gòu)存儲，設(shè)計(jì)一個算法求這兩個串最大公共子串，并用相關(guān)數(shù)據(jù)進(jìn)行測試。 else //逆序時返回0 return 0。答：所有可能的條件為：（1）s1和s2為空串（2）s1或s2其中之一為空串（3）s1和s2為相同的串（4）若兩串長度不等，則長串由整數(shù)個短串組成。 char str