【正文】 行交換。 for (i=0。 []=x。[i]（ji），[i][0..j]中任何一個元素都不相同，[i][j+1]中。i。 [k]!=[i]) k++。 //順序表長度置新值}本算法的時間復(fù)雜度為O(n2)，空間復(fù)雜度為O(1)。L) //L為引用型參數(shù){ int i,k=1。i。 } } =k。解：用p、q遍歷整個單鏈表，p指向*q的前驅(qū)結(jié)點，q用于查找第一個值為x的結(jié)點，當找到后將*q結(jié)點刪除，返回1；否則返回0。amp。 free(q)。解：判定鏈表L從第2個結(jié)點開始的每個結(jié)點的值是否比其前驅(qū)的值大。 //p指向*pre結(jié)點的后繼結(jié)點 while (p!=NULL) { if (pdata=predata) //若正序則繼續(xù)判斷下一個結(jié)點 { pre=p。}（6）有一個整數(shù)元素建立的單鏈表A，設(shè)計一個算法，將其拆分成兩個單鏈表A和B，使得A單鏈表中含有所有的偶數(shù)結(jié)點，B單鏈表中所有的奇數(shù)結(jié)點，且保持原來的相對次序。A,SLink *amp。 //建立頭結(jié)點 rb=B。 } else //奇數(shù)結(jié)點 { rbnext=p。}本算法的時間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。L,ElemType x){ SLink *s,*p,*q。 if (L==NULL || xLdata) //若單鏈表為空或x小于第1個結(jié)點date域 { snext=L。 while (p!=NULL amp。 } snext=p。解：用p遍歷單鏈表，用r遍歷*p結(jié)點之后的結(jié)點，q始終指向*r結(jié)點的直接前驅(qū)結(jié)點，若rdata==pdata，則刪除*r結(jié)點，否則q、r同步后移一個結(jié)點。 r=qnext。 r=t。 }}本算法的時間復(fù)雜度為O(n2)。用p遍歷遞增單鏈表，若*p結(jié)點的值域等于其后結(jié)點的值域，則刪除后者。 //q指向這個重復(fù)值的結(jié)點 pnext=qnext。（10）有一個雙鏈表L，設(shè)計一個算法查找第一個元素值為x的結(jié)點，將其與后繼結(jié)點進行交換。amp。 //q指向*p的后繼結(jié)點 if (q!=NULL) //*p結(jié)點不是尾結(jié)點 { ppriornext=q。 qnext=p。 //無法與后繼結(jié)點交換，返回0 }}（11）對于有n（n≥1）個數(shù)據(jù)結(jié)點的循環(huán)單鏈表L，設(shè)計一個算法將所有結(jié)點逆置。 Lnext=L。 p=q。L3) //求并集{ SLink *p,*q,*s,*tc。 q=L2next。 sdata=pdata。 } else if (pdataqdata) { s=(SLink *)malloc(sizeof(SLink))。 q=qnext。 tc=s。 sdata=pdata。 } while (q!=NULL) { s=(SLink *)malloc(sizeof(SLink))。 q=qnext。 L3=(SLink *)malloc(sizeof(SLink))。 while (p!=NULL amp。 else //pdata=qdata { s=(SLink *)malloc(sizeof(SLink))。 p=pnext。L3) //求差集{ SLink *p,*q,*s,*tc。 q=L2next。 sdata=pdata。 } else if (pdataqdata) q=qnext。 sdata=pdata。 } tcnext=NULL。 //尾插法建表 printf(集合A:)。 //尾插法建表 printf(集合B:)。 //求A、B并集C printf(集合C:)。 //求A、B并集D printf(集合D:)。 //求A、B差集E printf(集合E:)。 DestroyList(C)。 答：B（2）設(shè)一個棧的進棧序列是A、B、C、D（即元素A～D依次通過該棧），則借助該棧所得到的輸出序列不可能是（ ）。==1 !=1!=MaxSize ==MaxSize答：A（6）設(shè)順序棧st的棧頂指針top的初始時為1，?？臻g大小為MaxSize，則判定st棧為棧滿的條件是 。（9）一個隊列的入列序列為1234，則隊列可能的輸出序列是（ ）。 C.(rf)％N+1 D.(rf+N)％N答：D（13）設(shè)有4個數(shù)據(jù)元素a、b、c和d，對其分別進行棧操作或隊操作。經(jīng)操作后，最后在棧中或隊中的元素還有（ ⑤ ）個。答：①棧頂 ②棧底（2）一個棧的輸入序列是12345，的輸出序列為12345，其進棧出棧的操作為（ ）。（4）順序棧用data[0..n1]存儲數(shù)據(jù)，棧頂指針為top，其初始值為0，則元素x進棧的操作是（ ）。答：top。答：rear=(rear+1)%(m+1)。 x=A[rear]。②用途不同，棧用于子程調(diào)用和保護現(xiàn)場等，隊列用于多道作業(yè)處理、指令寄存及其他運算等等。③ 使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）。解：假定采用順序棧結(jié)構(gòu)。 SqStack tmpst。 Push(tmpst,x)。 //返回1表示成功}（2）設(shè)計一個算法，采用一個順序棧逆向輸出單鏈表L中所有元素。 struct node { ElemType data[MaxSize]。 SLink *p=Lnext。 } while (!=1) //棧不空循環(huán)，輸出棧中所有元素 { x=[]。}（3）設(shè)計一個循環(huán)隊列，用front和rear分別作為隊頭和隊尾指針，另外用一個標志tag標識隊列可能空（0）或可能滿（1），這樣加上front==rear可以作為隊空或隊滿的條件。 //隊頭和隊尾指針 int tag。 ==0隊滿條件：== amp。 =0。}//判隊滿算法int QueueFull1(QueueType qu) { return(==1 amp。qu,ElemType x){ if (QueueFull1(qu)==1) //隊滿 return 0。 //至少有一個元素,可能滿 return 1。 =(+1)%MaxSize。}（4）假設(shè)用一個循環(huán)單鏈表表示隊列，并且只設(shè)一個指針rear指向隊尾結(jié)點，但不設(shè)頭指針，設(shè)計出相應(yīng)的隊初始化、進隊、出隊和判隊空的算法。 struct node *next。}//進隊算法void EnQueue(QNode *amp。 if (rear==NULL) //原鏈隊為空 { snext=s。 rear=s。 if (rear==NULL) //隊空 return 0。 } else //原隊中有兩個或以上的結(jié)點 { q=rearnext。 } return 1。設(shè)計一個算法判定所給的操作序列是否合法。解：采用一個鏈棧來判斷操作序列是否合法，其中str為存放操作序列的字符數(shù)組，n為該數(shù)組的元素個數(shù)（這里的ElemType類型設(shè)定為char）。 //鏈棧結(jié)點類型void InitStack(LStack *amp。 if (pre==NULL) return。p=pnext。 p=(LStack *)malloc(sizeof(LStack))。}int Pop(LStack *amp。 else //棧不空時出棧元素x并返回1 { p=ls。 //釋放*p結(jié)點 return 1。 char x。in。 else if (str[i]==39。 //?？諘r返回0 } else Pop(ls,x)。 DestroyStack(ls)。 char str3[]=IIIOIOIO。 printf( %s序列%s合法的\n,str2,judge(str2,8)?是:不是)。 答：B（2）以下（ ）是abcd321ABCD串的子串。答：snext==NULL。（2）若s1和s2為串，給出使s1//s2=s2//s1成立的所有可能的條件（其中，“//”表示兩個串連接運算符）。解：因要求算法空間復(fù)雜度為O(1)，所以只能對串s直接替換。 for (i=0。解：用p和q指向鏈串s的兩個連續(xù)結(jié)點，p先指向開始結(jié)點，當qdata≥pdata時，p和q同步后移一個結(jié)點；否則返回0。 //q指向*p的后續(xù)結(jié)點 if (qdata=pdata) p=q。解：假設(shè)串用帶頭結(jié)點的單鏈表存儲串s。 while (p!=NULL) { n=1。amp。 } return max。 int midx=0,mlen=0,tlen,i=0,j,k。i+k amp。 [i+k]==[j+k]。 } j+=tlen。imlen。 //返回最大公共子串}void main(){ SqString s,t,str。DispStr(s)。 str=maxstr(s,t)。 答：A（2）對特殊矩陣采用壓縮存儲的目的主要是為了（ ）。存儲器按字節(jié)編址。若按列存儲，則A[7,1]和A[2,4]的第一個字節(jié)的地址分別是（ ④ ）和（ ⑤ ）。若按行存儲，則A[2,4]的第一個字節(jié)的地址是（ ③ ）。答：(d1c1+1)(d2c2+1)(d3c3+1)。答：326（4）二維數(shù)組A[10..20][5..10]采用行序為主方式存儲，每個元素占4個存儲單元，并且A[10][5]的存儲地址是1000，則A[18][9]的地址是（ ）。（7）稀疏矩陣的三元組表示中，每個結(jié)點對應(yīng)于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素的（ ）。 ElemType tmp。 A[i]=A[j]。因此先應(yīng)確定矩陣與一維數(shù)組的映射關(guān)系：bi,j在一維數(shù)組A中的下標為i～n+j，bj,i在一維數(shù)組A中的下標為jn+i。in。 A[i*n+j]=A[j*n+i]。解：先求出每行的最小值元素，放入min[m]之中，再求出每列的最大值元素，放入max[n]之中，若某元素既在min[i]中，又在max[j]中，則該元素A[i][j]便是馬鞍點，找出所有這樣的元素，即找到了所有馬鞍點。im。j++) if (A[i][j]min[i]) min[i]=A[i][j]。 for (i=1。im。//顯示馬鞍點 have=1。 for (i=0。j++) scanf(%d, amp。設(shè)值x在A中存在，要求比較次數(shù)不多于m+n次。amp。 break。并用相關(guān)數(shù)據(jù)進行測試。 //存放二維數(shù)組的行數(shù)和列數(shù)} Mat2。 =(ElemType *)malloc(x*y*sizeof(ElemType))。amp。amp。 //成功賦值返回1 } else return 0。amp。amp。 //成功取值返回1 } else return 0。i++) { for (j=0。 } printf(\n)。 if (!= || !=) return 0。j。 } return 1。 Setij(A,0,0,1)。 Setij(A,1,1,1)。 InitMat(B,2,3)。 Setij(B,1,0,2)。 DispMat(B)。 printf(C:\n)。 DestroyMat(C)。一個結(jié)點的子樹個數(shù)為該結(jié)點的（ ③ ）。①： ②： ③～④： 答：①B ②A ③A ④C（4）把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（ ）。 D. 二叉樹中每個結(jié)點的度均為2答：B（8）深度為5的二叉樹至多有（ ）個結(jié)點。log2i249。log2iA. 先序序列 B. 中序序列C. 中序和后序序列 D. 先序和后序序列答：C（14）一棵二叉樹的先序遍歷序列和其后序遍歷序列正好相反，則該二叉樹一定是（ ）。A. 111,110,10,01,00 B. 000,001,010,011,1C. 100,11,10,1,0 D. 001,000,01,11,10答：C2. 填空題（1）由3個結(jié)點所構(gòu)成的二叉樹有（ ）種形態(tài)。答：①500 ②499 ③1（5）一棵二叉樹的第i（i≥1）層最多有（ ）個結(jié)點。答：O(n)（8）用5個權(quán)值{3,2,4,5,1}構(gòu)造的哈夫曼（Huffman）樹的帶權(quán)路徑長度是（ ）。答：由二叉樹的性質(zhì)可知，n2=n01，在完全二叉樹中，度為1的結(jié)點數(shù)n1至多為1，所以具有n0個葉子結(jié)點的完全二叉樹結(jié)點數(shù)是n0+(n01)+1=2n0或2n01。 一棵二叉樹 二叉樹還原成的森林② 結(jié)點值為D的結(jié)點的雙親結(jié)點為結(jié)點值為A的結(jié)點，其左子樹為以C為根結(jié)點的子樹，其右子樹為空。由子樹定義可知，S是由T中某個結(jié)點及其所有