【正文】 葉子結(jié)點(diǎn)引 出k個(gè)分支，故有k*n1個(gè)分支。(4)并譯出編碼系列1100011100010101的相應(yīng)電文。,b,c,d,e,其出現(xiàn)頻率依次為4,7,5,2,9。：一個(gè)滿k叉樹(shù)上的葉子結(jié)點(diǎn)數(shù)n0和非葉子結(jié)點(diǎn)數(shù)n1之間滿足以下關(guān)系： n0=（k1）n1+1(50,28,78,65,23,36,13,42,71）,請(qǐng)完成以下操作:(1)畫出按元素排列順序逐點(diǎn)插入所生成的二叉排序樹(shù)BT。若按層次從上到下,每層從左到右的順序從1開(kāi)始對(duì)全部結(jié)點(diǎn)編號(hào),試計(jì)算:(1)第k層結(jié)點(diǎn)數(shù)(1≤k≤h)。__________________________，可能達(dá)到的最大深度和最小深度各是多少？____________________，這些結(jié)點(diǎn)的度要么是0，要么是2。,中序序列為BFDGAEHC ,并寫出前序序列_________________。（ ）。（A）有序數(shù)據(jù)元素（B）無(wú)序數(shù)據(jù)元素（C）元素之間具有分支層次關(guān)系的數(shù)據(jù)（D）元素之間無(wú)聯(lián)系的數(shù)據(jù)、中序和后序遍歷序列中的相對(duì)次序（ ）（A）不發(fā)生改變（B）發(fā)生改變（C）,最佳方案是二叉樹(shù)采用（ ）存儲(chǔ)結(jié)構(gòu)。（A）acbed （B）decab（C）deabc （D）cedba,那么T中結(jié)點(diǎn)的前序就是T2中結(jié)點(diǎn)的（ ）（A）前序（B）中序（C）后序（D）層次序,中序遍歷的結(jié)點(diǎn)訪問(wèn)順序是dgbaechf,則其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是（ ）。printf(depth:%d\n,depth(hd))。hc=copy_GL(hd)。hd=creat_GL(amp。}return(maxdh+1)。else{q=p。amp。}}int depth(NODE *p) /*求表的深度函數(shù) */{int h,maxdh。else n=sum(p)。} NODE *tail(NODE *p) /*求表尾函數(shù) */{return(plink)。elseq =p。if(p==NULL) return(NULL)。if(ptag==1)printf())。}void prn_GL(NODE *p){if(p!=NULL){if(ptag==1){printf(()。,39。}}elseh=NULL。){htag=1。\039。char ch。}dd。d++。j++)if(a[j]!=0){count++。count=0。n)。因此,現(xiàn)本題功能的程序如下:include main(){int a[100]。 }if(!have) printf(沒(méi)有鞍點(diǎn)＼n)。i1++)for(j=0。i1m。}for(j=0。i1++)/*計(jì)算出每行的最小值元素,放入min[m]之中*/{min[i1]=a[i1][0]。因此,實(shí)現(xiàn)本題功能的程序如下:include define m 3define n 4void minmax(int a[m][n]){int i1,j,have=0。編寫下列程序:(1)求廣義表表頭和表尾的函數(shù)head()和tail()。編寫一個(gè)函數(shù)計(jì)算出1n的矩陣A的所有馬鞍點(diǎn)。,采用壓縮存儲(chǔ)方式(以行序?yàn)橹?且A[0][0]=1),則A[8][5]的地址是__________________。（A） 二維數(shù)組和三維數(shù)組（B）三元組和散列（C）三元組和十字鏈表 （D）散列和十字鏈表,只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換,就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算,這種觀點(diǎn)（ ）。（A）M[2][4]（B）M[3][4]（C）M[3][5]（D）M[4][4][8][10]中,每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié),從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi),存放該數(shù)組至少需要的單元數(shù)是（ ）。i++。amp。i=1。}NODE。free(s)。t1=t1link。while(t1!=NULL){s=(NODE *)malloc(sizeof(NODE))。if(s1==NULL) return(NULL)。}一般鏈接存儲(chǔ)： include typedef struct node{char data。\039。return(i)。for(i=0。(A)abcd (B)acbd (C)acdb (D)adcb,其特殊性表現(xiàn)在（ ）(A)可以順序存儲(chǔ) (B)數(shù)據(jù)元素是一個(gè)字符(C)可以鏈?zhǔn)酱鎯?chǔ) (D)數(shù)據(jù)元素可以是多個(gè)字符5．設(shè)串S1=‘ABCDEFG’,s2=‘PQRST’,函數(shù)CONCAT（X，Y）返回X和Y串的連接串，SUBSTR（S，I，J）返回串S從序號(hào)I開(kāi)始的J個(gè)字符組成的字串，LENGTH（S）返回串S的長(zhǎng)度，則CONCAT（SUBSTR（S1，2，LENGTH（S2）），SUBSTR（S1，LENGTH（S2），2））的結(jié)果串是（ ）（A）BCDEF (B) BCDEFG (C)BCPQRST (D)BCDEFEF 二、算法設(shè)計(jì) ,用C語(yǔ)言寫出實(shí)現(xiàn)把串s1復(fù)制到串s2的串復(fù)制函數(shù)strcpy(s1,s2)。x)。push(s2,x)。}}void dequeue(elemtype *px){elemtype x。int top1,top2。else{top2++。else {top1。 /*上溢處理*/elseif(i==1) stack[top1++]=x。,s2模擬一個(gè)隊(duì)列時(shí),如何用棧的運(yùn)算來(lái)實(shí)現(xiàn)該隊(duì)列的運(yùn)算?寫出模擬隊(duì)列的插入和刪除的C函數(shù)。三、算法設(shè)計(jì)題 [M],其中一個(gè)棧底設(shè)在stack[0]處，另一個(gè)棧底設(shè)在stack[M1]處。（A）abcd*+（B）abc+*d （C）abc*+d（D）+*abcd，a2，a3和a4依次通過(guò)一個(gè)棧，在a4進(jìn)棧前，棧的狀態(tài)，則不可能的出棧序是（　?。?A)a4，a3，a2，a1　(B)a3，a2，a4，a1 (C)a3，a1，a4，a2　(D)a3，a4，a2，a1[0..m－1]存放循環(huán)隊(duì)列中的元素，變量rear和qulen分別指示循環(huán)隊(duì)列中隊(duì)尾元素的實(shí)際位置和當(dāng)前隊(duì)列中元素的個(gè)數(shù)，隊(duì)列第一個(gè)元素的實(shí)際位置是（　?。?A)rear－qulen　(B)rear－qulen＋m　(C)m－qulen　　 (D)1＋（rear＋m－qulen）% m二、填空題,隊(duì)列的特點(diǎn)是__________________________。（A） 線性存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)（B）散列方式和索引方式（C）鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組 （D）線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)(最多元素為m0)為空的條件是（ ）。plink=NULL。q=x。}NODE。 if(head!=NULL){while(plink!=NULL)p=plink。struct node *link。rlink=rh。q=p。r=p。void analyze(NODE *a） {NODE　*rh，*qh，*r,*q,*p； int i=0，j=0；/*i為序號(hào)是奇數(shù)的結(jié)點(diǎn)個(gè)數(shù) j為序號(hào)是偶數(shù)的結(jié)點(diǎn)個(gè)數(shù) */p=a； rh=（NODE *）malloc（sizeof（NODE））；/*rh為序號(hào)是奇數(shù)的鏈表頭指針 */qh=(NODE *)malloc(sizeof(NODE))。}return(head)。blink=head。a=r。blink!=bh){r=alink。a=ah。struct node *link。 while(rlink!=NULL)r=rlink。in1。int i。}該算法的時(shí)間復(fù)雜度為O(n+m),空間復(fù)雜度為O(1)鏈接存儲(chǔ):(不帶頭結(jié)點(diǎn)的單鏈表)typedef struct node{elemtype data。}}void exchange(elemtype list[],int n,int m)。i=(l+h)/2。return(0)。if(p==NULL||ji) return(1)。jiamp。if(i==0){*head=*headnext。amp。if(nmamp。i==n) return(0)。amp。int pare(int a[],int b[]){int i=0。free(r)。}while(q!=head amp。 /* 假設(shè)循環(huán)鏈表帶有頭結(jié)點(diǎn) */while(q!=head amp。}*n=*nk。amp。snext=pnext。}if(qprice==price)qnum=qnum+num。while(qpricepriceamp。}NODE。free(q)。q=qnext。q=headnext。} else{p=q。while(q!=head){if(qdata==x){plink=qlink。}NODE。}ave=sum/i。 p=head。 struct node *link。 參考答案： 一、選擇題1. B 3. D 4. B 5. A C二、判斷題:參考答案：√√三、填空題snext=pnext。 ，并將兩個(gè)循環(huán)鏈表的長(zhǎng)度放在各自的頭結(jié)點(diǎn)的數(shù)據(jù)域中的C函數(shù)。 試編寫一個(gè)比較A和B的C函數(shù)，該函數(shù)返回 1或 0或 1，分別表示 AB或 A=B或 AB?，F(xiàn)新到m臺(tái)價(jià)格為h的電視機(jī)，試編寫算法修改原鏈表。 ,試寫出刪除并釋放數(shù)據(jù)域值為x的所有結(jié)點(diǎn)的c函數(shù)。 7. snext=null。 3. L=s。pnext=q。（ ） 三、填空題 ，在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語(yǔ)句為：_______________________ 。（ ） ，就無(wú)法構(gòu)造鏈?zhǔn)浇Y(jié)構(gòu)。 pnext=pnextnext。 （D）pnext=s。 （B） snext=pnext。 分析算法規(guī)律可知時(shí)間頻度T(n)=1+(1+2)+(1+2+3)+...+(1+2+3+…+n)由于有1/6 ≤ T（n）/ n3 ≤1，故時(shí)間復(fù)雜度為Ｏ(n3)第二章 線性表 一、選擇題 ,每個(gè)元素的長(zhǎng)度為2,則第5個(gè)元素的地址是( ) （A）110 （B）108（C）100 （D）1202. 向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)（ ）個(gè)元素。j=i。分析：該算法為一個(gè)二重循環(huán)，執(zhí)行次數(shù)為內(nèi)、外循環(huán)次數(shù)相乘，但內(nèi)循環(huán)次數(shù)不固定，與外循環(huán)有關(guān)，因些，時(shí)間頻度T(n)=1+2+3+…+n=n*(n+1)/2有 1/4≤T(n)/n2≤1，故它的時(shí)間復(fù)雜度為Ｏ(n2), 即Ｔ(n)與n2 數(shù)量級(jí)相同。 i=n。 、_______和________。 ,樹(shù)根結(jié)點(diǎn)沒(méi)有_______結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有_______個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有________結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以_________。（ ） ：有窮性、輸入、輸出、完成性和確定性。 （A） 找出數(shù)據(jù)結(jié)構(gòu)的合理性 （B）研究算法中的輸入和輸出的關(guān)系 （C）分析算法的效率以求改進(jìn)（D）分析算法的易懂性和文檔性 （①）,它必須具備輸入、輸出和（②）等5個(gè)特性。 ① （A）數(shù)據(jù)元素（B）計(jì)算方法（C）邏輯存儲(chǔ)（D）數(shù)據(jù)映像 ② （A）結(jié)構(gòu) （B）關(guān)系 （C）運(yùn)算 （D）算法 （）。（ ） 。 ,第一個(gè)結(jié)點(diǎn)____前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有______個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)______后續(xù)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有_______個(gè)后續(xù)結(jié)點(diǎn)。、_______、______、_______、_______。 四、算法分析題 參考答案：一、選擇題1. C 3. C 4. A、B 5. C 、B二、判斷題:√ √三、填空題線性、樹(shù)形、圖形、集合? ；非線性（網(wǎng)狀） 沒(méi)有；1；沒(méi)有；1 前驅(qū)；1；后繼；任意多個(gè) 任意多個(gè) 一對(duì)一；一對(duì)多；多對(duì)多有窮性；確定性；可行性；輸入；輸出 數(shù)據(jù)元素；邏輯結(jié)構(gòu)；存儲(chǔ)結(jié)構(gòu) 插入、刪除、合并等操作較方便 順序存儲(chǔ)；鏈?zhǔn)酱鎯?chǔ) 四、算法分析題for(i=1。 j++)x=x+1。i++） for (j=1。k++)x=i+jk。pnext=s。p=s。 （B）p=pnext。，正確的是（ ） （A）線性表中的元素之間隔是線性關(guān)系 （B）線性表中至少有一個(gè)元素 （C）線性表中任何一個(gè)元素有且僅有一個(gè)直接前趨 （D）線性表中任何一個(gè)元素有且僅有一個(gè)直接后繼 （ ）的有限序列（n≠0)（A）表元素 （B）字符 （C）數(shù)據(jù)元素　 （D）數(shù)據(jù)項(xiàng) 二、判斷題 ，表中元素的邏輯順序與物理順序一定相同。（ ） ，我們應(yīng)該執(zhí)行q=pnext ； pnext=qnext； free(q)。qpriornext=p。 2. p=L。 6. snext=L。 四、算法設(shè)計(jì)題 （數(shù)據(jù)域數(shù)據(jù)類型為整型）。 ，按其價(jià)格從低到高的次序構(gòu)成一個(gè)循環(huán)鏈表，每個(gè)結(jié)點(diǎn)有價(jià)格、數(shù)量和鏈指針三個(gè)域。 若n=m，且 ai= bi （0≤in ），則A=B； 若nm ，且ai=bi （0≤in ），則AB； 若存在一個(gè)j， jm ，jn ，且ai=bi （0≤ij ）， 若ajbj，則AB，否則 AB。 (a0,a1,...,an1)和（b