數(shù)據(jù)結構模擬試卷和答案(編輯修改稿)
2025-07-19 17:06 本頁面
【文章內容簡介】 進行查找時，最大比較次數(shù)是（ ）。[A] 25[B] 50[C] 10[D] 7若需要利用形參直接訪問實參，則應把形參變量說明為（ ）參數(shù)。 [A] 指針[B] 引用[C] 傳值[D] 常值已知單鏈表A長度為m，單鏈表B長度為n，若將B聯(lián)接在A的末尾，其時間復雜度應為（ ）。[A] O(1)[B] O(m)[C] O(n)[D] O(m+n)在一棵高度為h(假定樹根結點的層號為0)的完全二叉樹中，所含結點個數(shù)不小于（ ）。[A] 2h1[B] 2h+1[C] 2h1[D] 2h假定一個鏈式隊列的隊頭和隊尾指針分別為front和rear，則判斷隊空的條件為（ ）。[A] front == rear[B] front != NULL[C] rear != NULL[D] front == NULL在一棵樹中，（ ）沒有前驅結點。 [A] 分支結點[B] 葉結點[C] 樹根結點[D] 空結點二、【判斷題】(本大題共10小題，每小題2分，共20分)正確的填T，錯誤的填F，填在答題卷相應題號處。1線性表的邏輯順序與物理順序總是一致的。 （ ）1在鏈式存儲的棧的頭部必須要設頭結點。 （ ）1在二叉樹中插入結點，則該項二叉樹便不再是二叉樹。 （ ）1由二叉樹結點的先序序列和后序序列可以唯一確定一棵二叉樹。 （ ）1棧和隊列也是線性表。如果需要，可對它們中的任一元素進行操作。 （ ）1用樹的前序遍歷序列和中序遍歷序列可以導出樹的后序遍歷序列。 （ ）1即使對不含相同元素的同一輸入序列進行兩組不同的、合法的入棧和出棧組合操作，所得到的序列也一定相同。 （ ）1哈夫曼(Huffman)樹是帶權路徑長度最短的樹。路徑上權值較大的結點離根較近。（ ）1對于任一個圖，從某頂點出發(fā)進行一次深度或廣度優(yōu)先搜索，可以訪問圖中每一個頂點。 （ ）帶權的無向連通圖的最小生成樹是唯一的。 （ ）三、【填空題】（本大題共10小空，每小空2分，共20分）請將答案填寫在答題卷相應題號處。2如果n個頂點的圖是一個環(huán)，則它有（ ）棵生成樹。2設在等概率情形下, 對有n個元素的順序表進行插入（插入位置i取0到n范圍內的整數(shù)）, 平均需要移動（ ）個元素。2具有96個結點的完全二叉樹的高度為（ ）。2如果一棵樹有n1個度為1的結點, 有n2個度為2的結點, … , nm個度為m的結點, 則度為0的結點有（ ）個。2若二叉樹的中序序列與后序序列相同，則該二叉樹是空樹或（ ）。2若一棵完全二叉樹有500個結點，則該二叉樹的深度為（ ）。2用鄰接矩陣表示無向圖時，若圖中有1000個頂點，1000條邊，則形成的鄰接矩陣有（ ）矩陣元素。2給定序列{100，86，48，73，35，39，42，57，66，21}，按堆結構的定義，則它一定是（ ）堆。2當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表的元素是，應采用（ ）存儲結構。向一個長度為n的順序表的第i個元素(1≤i≤n+1)之前插入一個元素時，需向后移動（ ）個元素。四、【應用題】（本大題共5小題，每小題8分，共40分）請將答案填寫在答題卷相應題號處。3已知某二叉樹中序遍歷的結果是ABC，試畫出其可能的二叉樹五種形態(tài)。3一個一維整數(shù)數(shù)組A[m]中有n (n≤m)個非空整數(shù)，它們相繼存放于數(shù)組的前端并已按非遞減順序排列，在數(shù)組A[m]中插入一個新的整數(shù)x，并使得插入后仍保持非遞減有序。要求x 插在值相等的整數(shù)后面。編寫相應的函數(shù)實現(xiàn)。3假設字符A,B,C,D,E,,，寫出A,B,C,D,E,F的Huffman（哈夫曼）編碼。3一顆二叉樹的中序序列和后序序列分別是DCBAEFG和DCBGFEA, 請畫出該二叉樹并給出先序序列。3設有一個輸入數(shù)據(jù)的序列是 { 46, 25, 78, 62, 12, 37, 70, 29 }, 試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉搜索樹。《數(shù)據(jù)結構》模擬試卷二 答案一、【單項選擇題】(本大題共10小題，每小題2分，共20分)題號12345678910答案CAAADBCDDC二、【判斷題】(本大題共10小題，每小題2分，共20分)題號11121314151617181920答案FFFFFTFTFF三、【填空題】（本大題共10小空，每小空2分，共20分）2( n )；2( n/2 )；2( 7 )；2( n2+2n3+…..+(m1)nm+1 )；2( 只有根節(jié)點的二叉樹 )；2(
畢業(yè)設計相關推薦
鄂ICP備17016276號-1