數據結構(本)(網教)202301-模擬卷注：找到所考試題直接看該試題所有題目和答案即可。查找按鍵：Ctrl+F超越高度一、單選題(共10題，20分)1、設循環隊列中數組的下標范圍是「n,其頭尾指針分別尾f、r,則隊列中元素的個數為().A、r-fr-f+1(r-f+1)modn(r-f+n)modn正確答案：D2、以下哪一個不是隊列的基本運算？A、從隊尾插入一個新元素B、從隊列中刪除第i個元素C、判斷一個隊列是否為空D、讀取隊頭元素的值正確答案：B3、有一個有序表{1,3,9,12,32,41,62,75,77,86,95,100},當二分查找值為86的關鍵字時，需要比較的次數是()。A、2B、3C、4D、5正確答案：C4、棧S最多能容納4個元素。現有6個元素按A、B、C、D、E、F的順序進棧，問下列哪一個序列是可能的出棧序列？E、D、C、B、A、FB、C、E、F、A、DC、B、E、D、A、FA、D、F、E、B、C正確答案：C5、n個頂點的無向連通圖至少有()條邊。n-lnn+1D、2n正確答案：A6、設有10000個無序元素,希望用較快速度挑選出其中前15個最大元素,采用()方法最好.A、直接插入排序B、堆排序C、快速排序D、歸并排序正確答案：B7、已知一棵二叉排序樹，通過()可以得到結點的有序序列。A、前序遍歷B、中序遍歷C、后序遍歷D、線索化正確答案：B8、S="A;/document/Mary.doc"，則“/”的字符定位的位置為().A、2B、3C、1211正確答案：B9、假設有60行70列的二維數組a[l-60,1-70]以列序為主序順序存儲,其基地址為10000,每個元素占2個存儲單元,那么第32行第58列的元素a[32,58]的存儲地址為()。(無第。行第0列元素)169021690414454D、答案A,B,C均不對正確答案：A10、具有36個結點的完全二叉樹的深度為()。A、5B、6C、7D、8正確答案：B二、填空題(共10題，10分)1、進棧序列為a,b,c,則通過出棧和進棧操作可能得到的a,b,c的不同的排列序列有一種。(1.0)正確答案:第1空:52、廣義表((a,b),c,d)的表頭是一，表尾是—o(1.0)正確答案：第1空：(a,b)|(c,cl)3、假設用循環單鏈表實現隊列,若隊列非空,且隊尾指針為R,則將新結點S加入隊列時,需執行下面語句:；；。(1.0)正確答案：第1空：S->next二R->next第2空：R->next=S第3空：R=S4、具有8個頂點的有向完全圖有條弧。(1.0)正確答案：第1空:565、判定一個棧ST(最多元素為m0)為空的條件是—為滿的條件是一。(1.0)正確答案：第1空：ST->top=0第2空：ST->top=mO6、若對線性表進行的主要操作是按照下標存取而不是插入和刪J除,則該線性表宜采用一存儲結構;如果需要頻繁的插入和剜除操作,則該線性表宜采用—存儲結構。(1.0)止確答案：第1空:順序第2空:鏈式7、圖的廣度優先遍歷類似于樹的一遍歷。（1.0）正確答案：第1空:層次8、一個有n個葉子結點的哈夫曼樹中,其結點總數為一o（1.0）正確答案：第1空:2nT9、一棵具有35個結點的完全二叉樹，它的深度為—o（1.0）正確答案：第1空:610、設目標串T="cdbccadcdccbaa“，模式P=“cade”，則第次匹配成功。（1.0）正確答案：第1空:5三、判斷題（共10題，10分）1、鏈式存儲是一種隨機存取的數據結構。（1.0）正確答案：錯誤2、線性表的邏輯順序與存儲順序總是一致的。（1.0）正確答案：錯誤3、拓撲排序時,總是在有向圖中選擇入度為0的頂點輸出。（1.0）正確答案：正確4、二叉樹中所有結點，如果不存在非空左子樹，則不存在非空右子樹。（1.0）正確答案：錯誤5、用二叉鏈表法（link-rlink）存儲包含n個結點的二叉樹,結點的2n個指針區域中有n+1個為空指針。（1.0）正確答案：正確6、平衡二叉排序樹具有的特點是左子樹與右子樹的高度差的絕對值不超過1。（1.0）正確答案：正確7、圖的深度優先遍歷類似于樹的層次遍歷。（1.0）正確答案：錯誤8、在一個圖中，所有頂點的度數之和等于圖的邊數的2倍。（1.0）正確答案：正確9、棧和隊列是一種非線性數據結構。（1.0）正確答案：錯誤10、順序存儲結構只能用來存放線性結構;鏈式存儲結構只能用來存放非線性結構。（1.0）正確答案：錯誤四、簡答題（共2題，10分）1、順序隊列的“假溢出”是怎樣產生的?如何解決？（5.0）正確答案：一般的一維數組隊列的尾指針已經到了數組的上界，不能再有入隊操作，但其實數組中還有空位置，這就叫“假溢出”。采用循環隊列是解決假溢出的途徑。另外，解決循環隊滿與隊空的辦法是浪費一個元素空間，用于區別隊滿還是隊空。判斷循環隊列隊空標志是：front二rear隊滿標志是：front：（rear+l）%N,N為數組的長度。2、寫出下列程序段的輸出結果（隊列中的元素類型QElemType為char）。voidmain()QueueQ;InitQueue(Q);Charx=，e，;y=，c，;EnQueue(Q,'h');EnQueue(Q,'r');EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,'a');While(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);;Printf(x);該程序段的功能是(5.0).正確答案：char五、算法設計題(共2題，20分)1、把單鏈表A和B合并為C,A和B的元素間隔排列,且使用原存儲空間。(10.0)正確答案：voidmerge(LinklistA;LinklistB){p=A->next;q=B->next;C=A;while(p&q){s=p->next;p->next=q;//將B的元素插入if(s){t=q->next;q->next=s;〃如A非空，將A的元素插入p=s;q=t;}//while//merge)2、設計一遞歸算法，將以二叉鏈表為存儲結構的二叉樹中的葉子結點全部刪除。二叉排序樹的存儲結構如下：正確答案：voidcoutnode(BSTreeT)/*T為樹根指針{if(T){if(1->IchiId二NULL)&&(T->rchild==NULL)Free(T);/刪除度為0的結點；count_node(T->lchild);/遞歸刪除左子樹中度為0的結點數count_node(T->rchild);/遞歸刪除右子樹中度為0的結點數)六、計算題(共3題，30分)1、已知某通訊系統使用8種字符，其概率分布分別為：0.06,0.28,0.07,0.08,0.14,0.22,0.03,0.12,試設計其哈夫曼編碼(10.0)正確答案：哈夫曼不唯一，其對應編碼