【正文】 2，則第6個(gè)元素的存儲(chǔ)地址是（ ）。B. p=pnext。1將長(zhǎng)度為n的單鏈表連接在長(zhǎng)度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為（ ）。A. 不再需要頭指針 B. 已知某結(jié)點(diǎn)位置后能容易找到其直接前驅(qū) C. 在進(jìn)行插入、刪除運(yùn)算時(shí)能保證鏈表不斷開(kāi) D. 在表中任一結(jié)點(diǎn)出發(fā)都能掃描整個(gè)鏈表 1不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（ ）。A. qnext=snext；snext=p； B. snext=p；qnext=snext； C. pnext=snext；snext=q； D. snext=q；pnext=snext；1在以下的敘述中，正確的是（ ）。 pnext=s。snext=p。A. p=pnext。1在頭指針為head且表長(zhǎng)大于1的單循環(huán)鏈表中，指針p指向表中某個(gè)結(jié)點(diǎn)，若pnextnext==head，則（ ）。答案：線性結(jié)構(gòu) 長(zhǎng)度寫(xiě)出帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L為空表的條件 。答案：qnext 三、判斷題單鏈表不是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。O在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素但是在物理位置上不一定是相鄰的。j=1。++j。}答案：(1)p=pnext (2)pdata函數(shù)實(shí)現(xiàn)單鏈表的插入算法，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。j=0。j++。 (1) 。int ListDelete_sq(Sqlist *L,int i){ int k。k++) Lslist[k]= （1） 。int ListDelete(LinkList L,int i,ElemType *s){ LNode *p,*q。 while(( （1） )amp。 } if(pnext==NULL||ji1) return ERROR。 free(q)。 int n=0。 n++。 if(!headnext) return ERROR。 while(q) {p=q。} }有兩個(gè)循環(huán)鏈表，鏈頭指針?lè)謩e為L(zhǎng)1和L2，要求寫(xiě)出算法將L2鏈表鏈到L1鏈表之后，且連接后仍保持循環(huán)鏈表形式。qnext=L1。 p=headnext。 q=qnext。 }else{while(!p amp。 }rnext=p。答案：void linklist_c(Lnode *head) {Lnode *p。pnext=head。if(headnext!=head){p=headnext。if(pnext!=head)p=pnext。 n=length(va[])。for(j=n1。 }n++。k=0。jk amp。 if(j==k){ if(k!=i)Ldata[k]=Ldata[i]。試寫(xiě)一算法，刪除表中所有大于x且小于y的元素（若表中存在這樣的元素）同時(shí)釋放被刪除結(jié)點(diǎn)空間。 q=p。if(p==head){head=pnext。 }else{qnext=pnext。 p=pnext。A. a,b,c,d,e B. d,e,c,b,a C. d,c,e,a,b D. e,d,c,b,a判斷一個(gè)循環(huán)隊(duì)列Q（最多n個(gè)元素）為滿的條件是（ ）。A. 1243 B. 2134 C. 1432 D. 4312 E. 3214若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)rear和front的值分別為0，3。A. front==rear B. front==0 C. rear==0 D. front=rear+1一個(gè)順序棧S，其棧頂指針為top，則將元素e入棧的操作是（ ）。*Stop=e。A. 隊(duì)列 B. 棧 C. 鏈表 D. 樹(shù)1棧的插入和刪除操作在（ ）。A. front=frontnext B. snext=rear。front=s。A. top不變 B. top=0 C. top=top+1 D. top=top11判斷一個(gè)循環(huán)隊(duì)列Q（空間大小為M）為空的條件是（ ）。A. 隊(duì)首　 B. 隊(duì)尾 C. 隊(duì)前 D. 隊(duì)后2若讓元素1，2，3依次進(jìn)棧，則出棧次序不可能是（ ）。A. 堆棧 B. 隊(duì)列 C. 數(shù)組 D. 線性表2棧和隊(duì)列都是（ ）。答案：3一個(gè)循環(huán)隊(duì)列Q的存儲(chǔ)空間大小為M,其隊(duì)頭和隊(duì)尾指針?lè)謩e為front和rear，則循環(huán)隊(duì)列中元素的個(gè)數(shù)為： 。三、判斷題棧和隊(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)寫(xiě)出算法的功能。 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è)頭指針，請(qǐng)寫(xiě)出相應(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。（√ ）完全二叉樹(shù)某結(jié)點(diǎn)有右子樹(shù)，則必然有左子樹(shù)。四、程序填空題函數(shù)kmp實(shí)現(xiàn)串的模式匹配，請(qǐng)?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. 無(wú)法確定 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的值是（ B ）。A. B. C. D. 1以下有關(guān)廣義表的表述中，正確的是（ A ）。（√ ）稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。廣義表運(yùn)算式HEAD(TAIL((a,b,c),(x,y,z)))的結(jié)果是： (x,y,z) 。答案：第六章 樹(shù)一、選擇題二叉樹(shù)的深度為k，則二叉樹(shù)最多有（ C ）個(gè)結(jié)點(diǎn)。A. adbce B. decab C. debac D. abcde在一棵具有5層的滿二叉樹(shù)中結(jié)點(diǎn)總數(shù)為（A）。A. 67　 B. 68 C. 69 D. 70將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層上從左到右依次對(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. 無(wú)序數(shù)據(jù)元素 C. 元素之間具有分支層次關(guān)系的數(shù)據(jù) D. 元素之間無(wú)聯(lián)系的數(shù)據(jù)1表達(dá)式A*(B+C)/(DE+F)的后綴表達(dá)式是（ C ）。tleft==NULL D. 以上都不對(duì)1任何一棵二叉樹(shù)的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（ ）。A. R[2i1] B. R[2i+1] C. R[2i] D. R[2/i]1下面說(shuō)法中正確的是（ ）。A. 51 B. 23 C. 53 D. 74二、判斷題（ ）存在這樣的二叉樹(shù)，對(duì)它采用任何次序的遍歷，結(jié)果相同。（√ ）一個(gè)含有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，它的高度是235。三、填空題具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度是 235。在一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)的個(gè)數(shù)是n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，則有n0= N2+1 。 printf(“%c”,btdata)。 else{ hl=depth(tlchild)。 } }寫(xiě)出下面算法的功能。 tdata=btdata。 tright=t1。 function(prchild)。假設(shè)用于通訊的電文僅由8個(gè)字母A、B、C、D、E、F、G、H組成，字母在電文中出現(xiàn)的頻率分別為：。答案： WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69已知權(quán)值集合為{5,7,2,3,6,9}，要求給出哈夫曼樹(shù)，并計(jì)算帶權(quán)路徑長(zhǎng)度WPL。答案： 有一分電文共使用5個(gè)字符。 答案：先序：FDBACEGIHJ 中序：ABCDEFGHIJ 后序：ACBEDHJIGF六、編程題編寫(xiě)求一棵二叉樹(shù)中結(jié)點(diǎn)總數(shù)的算法。count_preorder(tlchild)。A. 從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑　 B. 從源點(diǎn)到匯點(diǎn)的最短路徑 C. 最長(zhǎng)的回路 D. 最短的回路下面（ ）可以判斷出一個(gè)有向圖中是否有環(huán)（回路）。A. 對(duì)稱矩陣 B. 零矩陣 C. 上三角矩陣 D. 對(duì)角矩陣當(dāng)利用大小為N的數(shù)組存儲(chǔ)循環(huán)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度是（ ）。 A. 頂點(diǎn)序列 B. 邊序列 C. 權(quán)值總和 D. 邊的條數(shù) 1在有向圖的逆鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（ ）鄰接點(diǎn)。A. G1是G2的子圖 B. G2是G1的子圖 C. G1是G2的連通分量 D. G2是G1的連通分量1已知一個(gè)有向圖的鄰接矩陣表示，要?jiǎng)h除所有從第i個(gè)結(jié)點(diǎn)發(fā)出的邊，應(yīng)（ ）。A. 連通圖的深度優(yōu)先搜索是一個(gè)遞歸過(guò)程 B. 圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特征 C. 非連通圖不能用深度優(yōu)先搜索法 D. 圖的遍歷要求每一頂點(diǎn)僅被訪問(wèn)一次1帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度為A中：（ ）。且非0的元素個(gè)數(shù) D. 第i列非165。A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5 C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v22關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（ ）。A. 有向圖 B. 無(wú)向圖 C. 強(qiáng)連通圖 D. 完全圖2為便于判別有向圖中是否存在回路，可借助于（ ）。A. k1　 B. k2 C. k1+k2 D. k1k2一個(gè)具有8個(gè)頂點(diǎn)的有向圖中，所有頂點(diǎn)的入度之和與所有頂點(diǎn)的出度之和的差等于（ ）。答案：極小連通子圖一個(gè)圖的 表示法是惟一的。答案：拓?fù)渑判蛞阎粋€(gè)圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是 。三、判斷題圖的連通分量是無(wú)向圖的極小連通子圖。O存儲(chǔ)圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點(diǎn)個(gè)數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。O圖的生成樹(shù)是惟一的。 int arcs[N][N]。 visited[i]=TRUE。amp。答案：(1)廣度優(yōu)先遍歷