【正文】 )的是（ A ）。 A. 線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)　 B. 線性表的順序存儲(chǔ)結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況 C. 線性表的鏈表存儲(chǔ)結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況 D. 線性表的鏈表存儲(chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)1在表長為n的順序表中，當(dāng)在任何位置刪除一個(gè)元素的概率相同時(shí)，刪除一個(gè)元素所需移動(dòng)的平均個(gè)數(shù)為（ A ）。 B. pnext=snext。 D. pnext=s。 B. pnext=pnextnext。A. p指向頭結(jié)點(diǎn)　 B. p指向尾結(jié)點(diǎn) C. p的直接后繼是頭結(jié)點(diǎn) D. p的直接后繼是尾結(jié)點(diǎn)設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為（data,next）。答案：Lprior==Lnext==L帶頭結(jié)點(diǎn)的單鏈表head為空的條件是 。 對(duì)在具有頭結(jié)點(diǎn)的單鏈表中，頭指針指向鏈表的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)。錯(cuò)鏈?zhǔn)酱鎯?chǔ)的線性表可以隨機(jī)存取。 while(pamp。}if(!p||ji) return ERROR。int ListInsert(LinkList L,int i,ElemType e){ LNode *p,*s。 while((p!=NULL)amp。 } if(p==NULL||ji1) return ERROR。 (2) 。 if(i1||iLlength) return ERROR。 （2） 。 int j。amp。 q=pnext。 return OK。 node *p。 } return(n)。 p=headnext。 qnext=p。} }試編寫一個(gè)算法，將一個(gè)順序表逆置，并使用最少的輔助存儲(chǔ)空間實(shí)現(xiàn)。Invert_list(Sqlist *L)/*將順序表進(jìn)行逆置*/{ int i。i++){ t=Lelem[i]。答案：void merge(Lnode *L1, Lnode *L2) {Lnode *p,*q 。 pnext =L2。 q=pnext。if(rdata=pdata) {rnext=p。amp。 snext=r。 p=head。 }設(shè)單鏈表的長度（數(shù)據(jù)結(jié)點(diǎn)數(shù)）為N，則該算法的時(shí)間主要花費(fèi)在查找鏈表最后一個(gè)結(jié)點(diǎn)上（算法中的while循環(huán)），所以該算法的時(shí)間復(fù)雜度為O（N）。Alength=0。}}答案： (1) (a2, a4, …, ) (2)將循環(huán)單鏈表中偶數(shù)結(jié)點(diǎn)位置的元素值寫入順序表A設(shè)順序表va中的數(shù)據(jù)元數(shù)遞增有序。 if(x=va[n1])va[n]=x。j=I。 }試編寫一個(gè)算法，在一個(gè)遞增有序排列的單鏈表中插入一個(gè)新結(jié)點(diǎn)x，并保持有序。typedef struct Linknode *Link。 scanf(%d,amp。amp。 snext=NULL。 /*為插入的結(jié)點(diǎn)建立鏈接關(guān)系*/ snext=pointernext。閱讀算法f2，設(shè)順序表L=(3,7,3,2,1,1,8,7,3),寫出執(zhí)行算法f2后的線性表L的數(shù)據(jù)元素，并描述該算法的功能。iLlength。 Ldata[i]!=Ldata[j]。 }}Llength=k。 if(!head) return ERROR。amp。 p=head。p=qnext。給定兩個(gè)整數(shù)a和b，且ab，編寫算法刪除鏈表L中元素值大于a且小于b的所有結(jié)點(diǎn)。 q=p。if(p==head){head=pnext。 }else{qnext=pnext。 p=pnext。 }Sqlist。amp。} else { Celem[k]= Belem[j]。 i++。 k++。A. 順序表 B. 鏈表 C. 隊(duì)列 D. 棧帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（ B ）。A. 1和5 B. 2和4 C. 4和2 D. 5和1隊(duì)列的插入操作是在（ A ）。Stop++。表達(dá)式a*(b+c)d的后綴表達(dá)式是（ B ）。 A. 3，4，5，1，2 B. 2，4，1，3，5 C. 3，5，4，2，1 D. 1，3，5，2，41判定一個(gè)順序棧S（?？臻g大小為n）為空的條件是（ A ）。rear=s。 A. 1，2，3，4　 B. 4，3，2，1 C. 1，4，3，2 D. 3，4，1，21依次在初始為空的隊(duì)列中插入元素a,b,c,d以后，緊接著做了兩次刪除操作，此時(shí)的隊(duì)頭元素是（ C ）。A. 線性表的順序存儲(chǔ)結(jié)構(gòu) B. 隊(duì)列 C. 棧 D. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2當(dāng)用大小為N的數(shù)組存儲(chǔ)順序循環(huán)隊(duì)列時(shí)，該隊(duì)列的最大長度為（ C ）。A. 3，2，1　 B. 2，1，3 C. 3，1，2 D. 1，3，22循環(huán)隊(duì)列用數(shù)組A[0，m1]存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是（ A ）?！?棧和隊(duì)列都是（ C ）。答案：3一個(gè)循環(huán)隊(duì)列Q的存儲(chǔ)空間大小為M,其隊(duì)頭和隊(duì)尾指針分別為front和rear，則循環(huán)隊(duì)列中元素的個(gè)數(shù)為 。答案：15三、判斷題棧和隊(duì)列都是受限的線性結(jié)構(gòu)。 //構(gòu)造空棧 int StackEmpty(SqStack *S)。void conversion(){ InitStack(S)。 N=N/8。}}//conversion答案：（1）Push(S,N%8) （2）!StackEmpty(S)寫出算法的功能。 return OK。void f2(Queue *Q){ DataType e。 }}答案：（1）6,4,2,5,3,1 （2）將隊(duì)列倒置五、綜合題假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭指針，請寫出相應(yīng)的入隊(duì)列算法（用函數(shù)實(shí)現(xiàn)）。newdata=e。 }已知Q是一個(gè)非空隊(duì)列，S是一個(gè)空棧。 元素e入棧ElemType pop(SqStack s)。 出隊(duì)，返回隊(duì)頭元素int isEmpty(Queue q)。push(SqStack s, ElemTypex)。答案：出棧的可能序列： ABCD ABDC ACDB ACBD ADCB BACD BADC BCAD BCDA CBDA CBAD CDBA DCBA第四章 串一、選擇題設(shè)有兩個(gè)串S1和S2，求串S2在S1中首次出現(xiàn)位置的運(yùn)算稱作（ C ）。 A. O(m) B. O(n) C. O(m*n) D. O(nlog2m)空串和空格串（ B ）。A. ‘ijing’ B. ‘jingamp。（ 對(duì) ）完全二叉樹某結(jié)點(diǎn)有右子樹，則必然有左子樹。答案：對(duì)應(yīng)位置的字符也相同四、程序填空題函數(shù)kmp實(shí)現(xiàn)串的模式匹配，請?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。jtlen) if(j==1||sdata[i]==tdata[j]){ i++。 else return(1)。amp。j=0。int function(SqString *s1,SqString *s2){ int i。is1length。int fun(sqstring *s,sqstring *t,int start){ int i=start1,j=0。j++。 else return 1。A. 二維數(shù)組和三維數(shù)組 B. 三元組和散列表 C. 三元組和十字鏈表 D. 散列表和十字鏈表一個(gè)非空廣義表的表頭（ D ）。A. 正確 B. 錯(cuò)誤 C. 無法確定 D. 以上均不對(duì)廣義表(a,b,c)的表尾是（ B ）。A. 13　 B. 33 C. 18 D. 401設(shè)矩陣A是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角部分按行序存放在一維數(shù)組B[1,n(n1)/2]中，對(duì)下三角部分中任一元素ai,j(i=j)，在一維數(shù)組B的下標(biāo)位置k的值是（ A ）。 A. B. C. D. 1以下有關(guān)廣義表的表述中，正確的是（ A ）。（ 對(duì) ）稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。廣義表運(yùn)算式HEAD(TAIL((a,b,c),(x,y,z)))的結(jié)果是：(x,y,z) 。答案：第六章 樹一、選擇題二叉樹的深度為k，則二叉樹最多有（ C ）個(gè)結(jié)點(diǎn)。A. adbce B. decab C. debac D. abcde在一棵具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（ A ）。A. 67　 B. 68 C. 69 D. 70將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的左孩子編號(hào)為（ A ）。A. 有序數(shù)據(jù)元素 B. 無序數(shù)據(jù)元素 C. 元素之間具有分支層次關(guān)系的數(shù)據(jù) D. 元素之間無聯(lián)系的數(shù)據(jù)1表達(dá)式A*(B+C)/(DE+F)的后綴表達(dá)式是（ C ）。tleft==NULL D. 以上都不對(duì)1任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（ A ）。A. R[2i1] B. R[2i+1] C. R[2i] D. R[2/i]1下面說法中正確的是（ D ）。A. 51 B. 23 C. 53 D. 74二、判斷題（ 對(duì) ）存在這樣的二叉樹，對(duì)它采用任何次序的遍歷，結(jié)果相同。（ 對(duì) ）一個(gè)含有n個(gè)結(jié)點(diǎn)的完全二叉樹，它的高度是235。三、填空題具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度是 235。在一棵二叉樹中，度為0的結(jié)點(diǎn)的個(gè)數(shù)是n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，則有n0= n2+1 。 printf(“%c”,btdata)。 else{ hl=depth(tlchild)。 } }寫出下面算法的功能。 tdata=btdata。 tright=t1。 function(prchild)。請為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。答案：(1)樹形態(tài)： (2)帶權(quán)路徑長度：WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=79已知一棵二叉樹的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF。a,b,c,d,e，它們的出現(xiàn)頻率依次為9，試構(gòu)造哈夫曼樹，并給出每個(gè)字符的哈夫曼編碼。答案： } }第七章 圖一、選擇題1對(duì)于具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則該矩陣的大小為（ B ）。 A. 廣度優(yōu)先遍歷 B. 拓?fù)渑判? C. 求最短路徑 D. 求關(guān)鍵路徑帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度等于A中（ B ）。A. N2 B. N1 C. N D. N+1鄰接表是圖的一種（ B ）。A. 入邊 B. 出邊 C. 入邊和出邊 D. 不是出邊也不是入邊1設(shè)G1=(V1,E1)和G2=(V2,E2)為兩個(gè)圖，如果V1205。A. 將鄰接矩陣的第i行刪除 B. 將鄰接矩陣的第i行元素全部置為0 C. 將鄰接矩陣的第i列刪除 D. 將鄰接矩陣的第i列元素全部置為01任一個(gè)有向圖的拓?fù)湫蛄校? D ）。A. 第i行非165。且非0的元素個(gè)數(shù)1采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于二叉樹的（ D ）。A. 從源點(diǎn)到匯點(diǎn)的最長路徑　 B. 從源點(diǎn)到匯點(diǎn)的最短路徑 C. 最長的回路 D. 最短的回路2以下說法正確的是（ B ）。A. 廣度優(yōu)先搜索算法 B. 最小生成樹算法 C. 最短路徑算法 D. 拓?fù)渑判蛩惴?任何一個(gè)無向連通圖的最小生成樹（ B ）種。A. 16 B. 4 C. 0 D. 23無向圖中一個(gè)頂點(diǎn)的度是指圖中（ B ）。答案：鄰接矩陣遍歷圖的基本方法有深度優(yōu)先搜索和廣度優(yōu)先搜索，其中 是一個(gè)遞歸過程。答案：第i列上非無窮元素的個(gè)數(shù)之和 n個(gè)頂點(diǎn)的無向圖最多有 邊。 錯(cuò)一個(gè)圖的廣度優(yōu)先搜索樹是惟一