【正文】 度為（ ）。A. 隨機存取 B. 順序存取 C. 索引存取 D. 散列存取 1順序表中，插入一個元素所需移動的元素平均數是（ ）。A. 不再需要頭指針 B. 已知某結點位置后能容易找到其直接前驅 C. 在進行插入、刪除運算時能保證鏈表不斷開 D. 在表中任一結點出發(fā)都能掃描整個鏈表 1不帶頭結點的單鏈表head為空的判定條件是（ ）。 A. 訪問第i個元素的前驅（1） B. 在第i個元素之后插入一個新元素() C. 刪除第i個元素() D. 對順序表中元素進行排序1已知指針p和q分別指向某單鏈表中第一個結點和最后一個結點。A. qnext=snext；snext=p； B. snext=p；qnext=snext； C. pnext=snext；snext=q； D. snext=q；pnext=snext；1在以下的敘述中，正確的是（ ）。A. (n1)/2 B. n/2 C. (n+1)/2 D. n1在一個單鏈表中，已知q所指結點是p所指結點的前驅結點，若在q和p之間插入一個結點s，則執(zhí)行（ ）。 pnext=s。snext=p。snext=p。snext=q。A. p=pnext。 C. pnext=p。1在頭指針為head且表長大于1的單循環(huán)鏈表中，指針p指向表中某個結點，若pnextnext==head，則（ ）。已知指針p指向單鏈表中的結點，q指向新結點，欲將q插入到p結點之后，則需要執(zhí)行的語句： ； 。答案：線性結構 長度寫出帶頭結點的雙向循環(huán)鏈表L為空表的條件 。答案：headnext==NULL在一個單鏈表中刪除p所指結點的后繼結點時，應執(zhí)行以下操作：q = pnext。答案：qnext 三、判斷題單鏈表不是一種隨機存儲結構。O用循環(huán)單鏈表表示的鏈隊列中，可以不設隊頭指針，僅在隊尾設置隊尾指針。O在線性表的順序存儲結構中，邏輯上相鄰的兩個元素但是在物理位置上不一定是相鄰的。O 四、程序分析填空題函數GetElem實現(xiàn)返回單鏈表的第i個元素，請在空格處將算法補充完整。j=1。amp。++j。*e= (2) 。}答案：(1)p=pnext (2)pdata函數實現(xiàn)單鏈表的插入算法，請在空格處將算法補充完整。int j。j=0。amp。j++。 s=(LNode *)malloc(sizeof(LNode))。 (1) 。 return OK。int ListDelete_sq(Sqlist *L,int i){ int k。for(k=i1。k++) Lslist[k]= （1） 。 return OK。int ListDelete(LinkList L,int i,ElemType *s){ LNode *p,*q。 p=L。 while(( （1） )amp。(ji1)){ p=pnext。 } if(pnext==NULL||ji1) return ERROR。 （2） 。 free(q)。}/*listDelete*/答案：(1)pnext!=NULL (2)pnext=qnext寫出算法的功能。 int n=0。 p=head。 n++。 }答案：求單鏈表head的長度五、綜合題編寫算法，實現(xiàn)帶頭結點單鏈表的逆置算法。 if(!headnext) return ERROR。 q=pnext。 while(q) {p=q。 pnext=headnext。} }有兩個循環(huán)鏈表，鏈頭指針分別為L1和L2，要求寫出算法將L2鏈表鏈到L1鏈表之后，且連接后仍保持循環(huán)鏈表形式。 while(pnext!=L1)p=pnext。qnext=L1。 }設一個帶頭結點的單向鏈表的頭指針為head，設計算法，將鏈表的記錄，按照data域的值遞增排序。 p=headnext。 pnext=NULL。 q=qnext。 headnext=r。 }else{while(!p amp。 rdatapdata){s=p。 }rnext=p。}p=headnext。答案：void linklist_c(Lnode *head) {Lnode *p。 if(!p) return ERROR。pnext=head。已知head為帶頭結點的單循環(huán)鏈表的頭指針，鏈表中的數據元素依次為（a1，a2,a3,a4,…,an）,A為指向空的順序表的指針。if(headnext!=head){p=headnext。while(pnext!=head){p=pnext。if(pnext!=head)p=pnext。試寫一算法，將x插入到順序表的適當位置上，以保持該表的有序性。 n=length(va[])。else{i=0。for(j=n1。j)va[j+1]=va[j]。 }n++。閱讀算法f2，設順序表L=(3,7,3,2,1,1,8,7,3),寫出執(zhí)行算法f2后的線性表L的數據元素，并描述該算法的功能。k=0。iLlength。jk amp。 Ldata[i]!=Ldata[j]。 if(j==k){ if(k!=i)Ldata[k]=Ldata[i]。 }}Llength=k。試寫一算法，刪除表中所有大于x且小于y的元素（若表中存在這樣的元素）同時釋放被刪除結點空間。 if(!head) return ERROR。 q=p。amp。if(p==head){head=pnext。 p=head。 }else{qnext=pnext。p=qnext。 p=pnext。給定兩個整數a和b，且ab，編寫算法刪除鏈表L中元素值大于a且小于b的所有結點。A. a,b,c,d,e B. d,e,c,b,a C. d,c,e,a,b D. e,d,c,b,a判斷一個循環(huán)隊列Q（最多n個元素）為滿的條件是（ ）。A. 順序表 B. 鏈表 C. 隊列 D. 棧帶頭結點的單鏈表head為空的判定條件是（ ）。A. 1243 B. 2134 C. 1432 D. 4312 E. 3214若用一個大小為6的數組來實現(xiàn)循環(huán)隊列，且當rear和front的值分別為0，3。A. 1和5 B. 2和4 C. 4和2 D. 5和1隊列的插入操作是在（ ）。A. front==rear B. front==0 C. rear==0 D. front=rear+1一個順序棧S，其棧頂指針為top，則將元素e入棧的操作是（ ）。Stop++。*Stop=e。表達式a*(b+c)d的后綴表達式是（ ）。A. 隊列 B. 棧 C. 鏈表 D. 樹1棧的插入和刪除操作在（ ）。 A. 3，4，5，1，2 B. 2，4，1，3，5 C. 3，5，4，2，1 D. 1，3，5，2，41判定一個順序棧S（?？臻g大小為n）為空的條件是（ ）。A. front=frontnext B. snext=rear。rear=s。front=s。 A. 1，2，3，4　 B. 4，3，2，1 C. 1，4，3，2 D. 3，4，1，21依次在初始為空的隊列中插入元素a,b,c,d以后，緊接著做了兩次刪除操作，此時的隊頭元素是（ ）。A. top不變 B. top=0 C. top=top+1 D. top=top11判斷一個循環(huán)隊列Q（空間大小為M）為空的條件是（ ）。A. 線性表的順序存儲結構 B. 隊列 C. 棧 D. 線性表的鏈式存儲結構2當用大小為N的數組存儲順序循環(huán)隊列時，該隊列的最大長度為（ ）。A. 隊首　 B. 隊尾 C. 隊前 D. 隊后2若讓元素1，2，3依次進棧，則出棧次序不可能是（ ）。 A. (rearfront+m)%m B. rearfront+1 C. rearfront1 D. rearfront2在解決計算機主機和打印機之間速度不匹配問題時，通常設置一個打印數據緩沖區(qū)，主機將要輸出的數據依次寫入該緩沖區(qū)，而打印機則從該緩沖區(qū)中取走數據打印。A. 堆棧 B. 隊列 C. 數組 D. 線性表2棧和隊列都是（ ）。A. front=frontnext B. rear= rearnext C. rearnext=front D. frontnext=rear2隊和棧的主要區(qū)別是（ ）。答案：3一個循環(huán)隊列Q的存儲空間大小為M,其隊頭和隊尾指針分別為front和rear，則循環(huán)隊列中元素的個數為： 。答案：n1設循環(huán)隊列的容量為70，現(xiàn)經過一系列的入隊和出隊操作后，front為20，rear為11，則隊列中元素的個數為 。三、判斷題棧和隊列都是受限的線性結構。O以鏈表作為棧的存儲結構，出棧操作必須判別?？盏那闆r。 //構造空棧 int StackEmpty(SqStack *S)。//入棧 int Pop(SqStack *S,ElemType *e)。void conversion(){ InitStack(S)。N)。 N=N/8。e)。}}//conversion答案：（1）Push(S,N%8) （2）!StackEmpty(S)寫出算法的功能。 *e=Qbase[Qfront]。 return OK。寫出執(zhí)行算法f2后的隊列Q。void f2(Queue *Q){ DataType e。 f2(Q)。 }}答案：（1）6,4,2,5,3,1 （2）將隊列倒置五、綜合題假設以帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾結點，但不設頭指針，請寫出相應的入隊列算法（用函數實現(xiàn)）。 New=(Lnode *)malloc(sizeof(Lnode))。newdata=e。 rearnext=new。 }已知Q是一個非空隊列，S是一個空棧。棧的ADT函數有：void makeEmpty(SqStack s)。 元素e入棧ElemType pop(SqStack s)。 判斷?？贞犃械腁DT函數有：void enQueue(Queue q,ElemType e)。 出隊，返回隊頭元素int isEmpty(Queue q)。 makeEmpty(SqStack s)。push(SqStack s, ElemTypex)。 enQueue(Queue q, ElemType x)。答案：出棧的可能序列： ABCD ABDC ACDB ACBD ADCB BACD BADC BCAD BCDA CBDA CBAD CDBA DCBA第四章 串一、選擇題設有兩個串S1和S2，求串S2在S1中首次出現(xiàn)位置的運算稱作（ C ）。A. 0123 B. 1123 C. 1231 D. 1211串與普通的線性表相比較，它的特殊性體現(xiàn)在（ C ）。 A. O(m) B. O(n) C. O(m*n) D. O(nlog2m)空串和空格串（ B ）。 A. 通常以串整體作為操作對象 B. 需要更多的輔助空間 C. 算法的時間復雜度較高 D. 涉及移動的元素更多設SUBSTR(S,i,k)是求S中從第i個字符開始的連續(xù)k個字符組成的子串的操作，則對于S=’Beijingamp。A. ‘ijing’ B. ‘jingamp。N’二、判斷題（ ）造成簡單模式匹配算法BF算法執(zhí)行效率低的原因是有回溯存在。（√ ）完全二叉樹某結點有右子樹，則必然有左子樹。設s=’I︺AM︺A︺TEACHER’,其長度是____。四、程序填空題函數kmp實現(xiàn)串的模式匹配，請在空格處