數據結構試題集含答案(編輯修改稿)

　

【文章內容簡介】 分別為0，3。當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為（ B ）。A. 1和5 B. 2和4 C. 4和2 D. 5和1隊列的插入操作是在（ A ）。A. 隊尾 B. 隊頭 C. 隊列任意位置 D. 隊頭元素后循環隊列的隊頭和隊尾指針分別為front和rear，則判斷循環隊列為空的條件是（ A ）。A. front==rear B. front==0 C. rear==0 D. front=rear+1一個順序棧S，其棧頂指針為top，則將元素e入棧的操作是（ A ）。A. *Stop=e。Stop++。 B. Stop++。*Stop=e。 C. *Stop=e D. Stop=e。表達式a*(b+c)d的后綴表達式是（ B ）。A. abcd+　 B. abc+*d C. abc*+d D. +*abcd1將遞歸算法轉換成對應的非遞歸算法時，通常需要使用（ B ）來保存中間結果。A. 隊列 B. 棧 C. 鏈表 D. 樹1棧的插入和刪除操作在（ B ）。 A. 棧底 B. 棧頂 C. 任意位置 D. 指定位置1五節車廂以編號1，2，3，4，5順序進入鐵路調度站（棧），可以得到（ C ）的編組。 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（棧空間大小為n）為空的條件是（ A ）。A. Stop==0 B. Stop!=0 C. Stop==n D. Stop!=n1在一個鏈隊列中，front和rear分別為頭指針和尾指針，則插入一個結點s的操作為（ C ）。A. front=frontnext B. snext=rear。rear=sC. rearnext=s。rear=s。 D. snext=front。front=s。1一個隊列的入隊序列是1，2，3，4，則隊列的出隊序列是（ A ）。 A. 1，2，3，4　 B. 4，3，2，1 C. 1，4，3，2 D. 3，4，1，21依次在初始為空的隊列中插入元素a,b,c,d以后，緊接著做了兩次刪除操作，此時的隊頭元素是（ C ）。A. a B. b C. c D. d1正常情況下，刪除非空的順序存儲結構的堆棧的棧頂元素，棧頂指針top的變化是（ D ）。A. top不變 B. top=0 C. top=top+1 D. top=top11判斷一個循環隊列Q（空間大小為M）為空的條件是（ A ）。A. Qfront==Qrear B. QrearQfront1==M C. Qfront+1=Qrear D. Qrear+1=Qfront設計一個判別表達式中左右括號是否配對出現的算法，采用（ C ）數據結構最佳。A. 線性表的順序存儲結構 B. 隊列 C. 棧 D. 線性表的鏈式存儲結構2當用大小為N的數組存儲順序循環隊列時，該隊列的最大長度為（ C ）。A. N　 B. N+1 C. N1 D. N2【解析：隊列的頭指針指向的是第一個元素的前一個結點，而不是指向第一個元素，一次隊列的頭指針要占用一個結點長度。】2隊列的刪除操作是在（ A ）。A. 隊首　 B. 隊尾 C. 隊前 D. 隊后2若讓元素1，2，3依次進棧，則出棧次序不可能是（ C ）。A. 3，2，1　 B. 2，1，3 C. 3，1，2 D. 1，3，22循環隊列用數組A[0，m1]存放其元素值，已知其頭尾指針分別是front和rear，則當前隊列中的元素個數是（ A ）。 A. (rearfront+m)%m B. rearfront+1 C. rearfront1 D. rearfront2在解決計算機主機和打印機之間速度不匹配問題時，通常設置一個打印數據緩沖區，主機將要輸出的數據依次寫入該緩沖區，而打印機則從該緩沖區中取走數據打印。該緩沖區應該是一個（ B ）結構。A. 堆棧 B. 隊列 C. 數組 D. 線性表【解析：先進入緩沖區的文件先被打印，選擇先進先出的結構，即隊列。】2棧和隊列都是（ C ）。A. 鏈式存儲的線性結構 B. 鏈式存儲的非線性結構 C. 限制存取點的線性結構 D. 限制存取點的非線性結構【解析：棧是只允許在棧頂進行插入和刪除操作的線性表，隊列是只允許在隊頭進行刪除，在隊尾進行刪除操作的線性表】2在一個鏈隊列中，假定front和rear分別為隊頭指針和隊尾指針，刪除一個結點的操作是（ A ）。A. front=frontnext B. rear= rearnext C. rearnext=front D. frontnext=rear2隊和棧的主要區別是（ D ）。A. 邏輯結構不同 B. 存儲結構不同C. 所包含的運算個數不同 D. 限定插入和刪除的位置不同二、填空題設棧S和隊列Q的初始狀態為空，元素e1,e2,e3,e4,e5,e6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的序列是e2,e4,e3,e6,e5,e1，則棧的容量至少應該是 。答案：3一個循環隊列Q的存儲空間大小為M,其隊頭和隊尾指針分別為front和rear，則循環隊列中元素的個數為 。答案：(rearfront+M)%M在具有n個元素的循環隊列中，隊滿時具有 個元素。答案：n1設循環隊列的容量為70，現經過一系列的入隊和出隊操作后，front為20，rear為11，則隊列中元素的個數為 。答案：61 已知循環隊列的存儲空間大小為20，且當前隊列的頭指針和尾指針的值分別為8和3，且該隊列的當前的長度為 。答案：15三、判斷題棧和隊列都是受限的線性結構。對在單鏈表中，要訪問某個結點，只要知道該結點的地址即可；因此，單鏈表是一種隨機存取結構。錯以鏈表作為棧的存儲結構，出棧操作必須判別棧空的情況。對四、程序分析填空題已知棧的基本操作函數： int InitStack(SqStack *S)。 //構造空棧 int StackEmpty(SqStack *S)。//判斷棧空 int Push(SqStack *S,ElemType e)。//入棧 int Pop(SqStack *S,ElemType *e)。//出棧函數conversion實現十進制數轉換為八進制數，請將函數補充完整。void conversion(){ InitStack(S)。 scanf(“%d”,amp。N)。 while(N){ （1） 。 N=N/8。}while( （2） ){ Pop(S,amp。e)。 printf(“%d”,e)。}}//conversion答案：（1）Push(S,N%8) （2）!StackEmpty(S)寫出算法的功能。int function(SqQueue *Q,ElemType *e){ if(Qfront==Qrear) return ERROR。 *e=Qbase[Qfront]。 Qfront=(Qfront+1)%MAXSIZE。 return OK。}答案：循環隊列出隊操作閱讀算法f2,并回答下列問題：（1）設隊列Q=（1，3，5，2，4，6）。寫出執行算法f2后的隊列Q。（2）簡述算法f2的功能。void f2(Queue *Q){ DataType e。 if (!QueueEmpty(Q)){ e=DeQueue(Q)。 f2(Q)。 EnQueue(Q,e)。 }}答案：（1）6,4,2,5,3,1 （2）將隊列倒置五、綜合題假設以帶頭結點的循環鏈表表示隊列，并且只設一個指針指向隊尾結點，但不設頭指針，請寫出相應的入隊列算法（用函數實現）。答案：void EnQueue(Lnode *rear, ElemType e) { Lnode *new。 New=(Lnode *)malloc(sizeof(Lnode))。If(!new) return ERROR。newdata=e。 newnext=rearnext。 rearnext=new。 rear =new。 }已知Q是一個非空隊列，S是一個空棧。編寫算法，僅用隊列和棧的ADT函數和少量工作變量，將隊列Q的所有元素逆置。棧的ADT函數有：void makeEmpty(SqStack s)。 置空棧void push(SqStack s,ElemType e)。 元素e入棧ElemType pop(SqStack s)。 出棧，返回棧頂元素int isEmpty(SqStack s)。 判斷棧空隊列的ADT函數有：void enQueue(Queue q,ElemType e)。 元素e入隊ElemType deQueue(Queue q)。 出隊，返回隊頭元素int isEmpty(Queue q)。 判斷隊空答案：void QueueInvent(Queue q) { ElemType x。 makeEmpty(SqStack s)。while(!isEmpty(Queue q)){x=deQueue(Queue q)。push(SqStack s, ElemTypex)。}while(!isEmpty(SqStack s)){x=pop(SqStack s)。 enQueue(Queue q, ElemType x)。} }對于一個棧，給出輸入項A,B,C,D，如果輸入項序列為A,B,C,D，試給出全部可能的輸出序列。答案：出棧的可能序列： ABCD ABDC ACDB ACBD ADCB BACD BADC BCAD BCDA CBDA CBAD CDBA DCBA第四章 串一、選擇題設有兩個串S1和S2，求串S2在S1中首次出現位置的運算稱作（ C ）。A. 連接 B. 求子串 C. 模式匹配 D. 判斷子串已知串S=’aaab’，則next數組值為（ A ）。A. 0123 B. 1123 C. 1231 D. 1211串與普通的線性表相比較，它的特殊性體現在（ C ）。A. 順序的存儲結構 B. 鏈式存儲結構 C. 數據元素是一個字符 D. 數據元素任意設串長為n，模式串長為m，則KMP算法所需的附加空間為（ A ）。 A. O(m) B. O(n) C. O(m*n) D. O(nlog2m)空串和空格串（ B ）。 A. 相同 B. 不相同 C. 可能相同 D. 無法確定與線性表相比，串的插入和刪除操作的特點是（ A ）。 A. 通常以串整體作為操作對象 B. 需要更多的輔助空間 C. 算法的時間復雜度較高 D. 涉及移動的元素更多設SUBSTR(S,i,k)是求S中從第i個字符開始的連續k個字符組成的子串的操作，則對于S=’Beijingamp。Nanjing’，SUBSTR(S,4,5)=（ B ）。A. ‘ijing’ B. ‘jingamp。’ C. ‘ingNa’ D. ‘ingamp。N’二、判斷題（ 對 ）造成簡單模式匹配算法BF算法執行效率低的原因是有回溯存在。（ 對 ）KMP算法的最大特點是指示主串的指針不需要回溯。（ 對 ）完全二叉樹某結點有右子樹，則必然有左子樹。三、填空題求子串在主串中首次出現的位置的運算稱為 。答案：模式匹配 設s=’I︺AM︺A︺TEACHER’,其長度是 。答案：14 兩個串相等的充分必要條件是兩個串的長度相等且 。答案：對應位置的字符也相同四、程序填空題函數kmp實現串的模式匹配，請在空格處將算法補充完整。int kmp(sqstring *s,sqstring *t,int start,int next[]){ int i=start1,j=0。 while(islenamp。amp。jtlen) if(j==1||sdata[i]==tdata[j]){