一、單項選擇題
1．在表長為n的順序表上做插入運算，平均要移動的結點數為 (c)
a．n／4 b．n／3 c．n／2 d．n
2．順序表中有19個元素，第乙個元素的位址為200，且每個元素佔乙個位元組，則第14個元素的儲存位址為 (b)
a．212 b．213 c．214 d．215
3．由頂點v1，v2。，v3構成的圖的鄰接矩陣為則該圖中頂點v1的出度為 (c)
a．0 b．1 c．2 d．3
4．元素的進棧次序為a，b，c，d，e，則退棧中不可能的序列是(c)
a． a，b，c，d，e b． b，c，d，e，a
c． e，a，b，c，d d． e，d，c，b，a
5．由帶權為9，2，5，7的四個葉子結點構造一棵哈夫曼樹，該樹的帶權路徑長度為(c)
a．23 b．37 c．44 d．46
6．在已知尾指標的單迴圈鍊錶中，插入乙個新結點使之成為首結點，其演算法的時間複雜度為(a)
a．0(1) b．0(log2n) c．o(n) d．o(n2)
7．已知乙個有序表為(13，18，24，35，47，50，62，83，90，115，134)，當二分查詢值為90的元素時，查詢成功時需比較的次數為 (b)
a．1 b．2 c．3 d．4
8．在查詢順序表各結點概率相等的情況下，順序按值查詢某個元素的演算法時間複雜度為(b)
a．o(1) b．o(n) c．od．o(log2n)
9．下列各項鍵值序列中不是堆的為(c)
a．(5，23，16，68，94，72，71，73}
b．c．d．10．**性表的下列儲存結構中進行插入、刪除運算，花費時間最多的是(c)
a．單鏈表 b．雙鏈表 c．順序表 d．單迴圈鍊錶
11．在棧中進行插入和刪除操作的一端稱為(a)
a．棧頂 b．棧底 c．任意位置 d．指定位置
12．用n個值構造一棵二叉排序樹，它的最大高度為(b)
a．n／2 b．ncd．log2n
13．氣泡排序的時間複雜度是(a)
a．o(n2) b．o(nlog2n) c．o(n) d．o(log2n)
14．設無向圖的鄰接表如下圖所示，則該圖的邊數為(b)
a．4 b．5 c．10 d．20
15．帶表頭結點鏈佇列的隊頭和隊尾指標分別為front和rear，則判斷隊空的條件為(a)
a．front==rearb．front!=null
c．rear!=nulld．front==null
二、填空題
16．下列程式段的時間複雜度為 0(n
i=0；s=0；
while(i
17．資料的邏輯結構被分為集合結構、 線性結構 、樹形結構和圖狀結構4種。
18．線性表中所含結點的個數稱為線性表的長度(表長)
19．向乙個棧頂指標為top的鏈棧中插入乙個新結點*p時，應執行 p->next=top和top=p操作。
20．設乙個順序棧s，元素s1，s2，s3，s4，s5，s6依次進棧，如果6個元素的退棧順序為s2，s3，s4，s6，s5，s1，則順序棧的容量至少為 3 。
21．若滿二叉樹的結點數為n，則其高度為 +1
22．在一棵具有n個結點的完全二叉樹中，從樹根起，自上而下、從左到右地給所有結點編號。若編號為i的結點有父結點，那麼其父結點的編號為
23．深度為k的二叉樹，結點數最多有 2k-1 個。
24．某二叉樹的後根遍歷為abkcbpm，則該二叉樹的根為 m
25．在乙個具有n個頂點的無向圖中，頂點的度最大可達 n-1
26．有向圖g的鄰接矩陣為a，如果圖中存在弧，則a[i][j]的值為 1 。
27．順序查詢演算法的平均查詢長度為
28．二路歸併排序的平均時間複雜度為 o(nlog2n)
三、應用題
29 某通訊電文由a,b,c,d,e,f六個字元編碼組成，每個字元編碼在電文**現的次數分別是6,5,9,10,20,1，試畫出這六個字元編碼所用的哈夫曼樹。
解：編碼用的哈夫曼樹如下圖所示：
30．已知一棵二叉樹的順序儲存結構如下圖所示，其中a表示虛結點，試構造該二叉樹。
解31．下圖中二叉排序樹的各結點的值為1～9，標出各結點的值。
解32．寫出下圖所示的有向圖的鄰接矩陣及該圖的所有拓撲排序序列。
解 拓撲排序序列只有1種：cabedf
33．寫出鍵值(83，40，63，13，84，35，96，57，39，79，61，15)應用二路歸併排序演算法從小到大排序後各趟的結果。
解： (40，83)(13，63)(35，84)(57，96)(39，79)(15，61)
(13，40，63，83)(35，57，84，96)(15，39，61，79)
(13，35，40，57，63，83，84，96)(15，39，61，79)
(13，15，35，39，40，57，61，63，79，83，84，96)
四、演算法設計題
34．若兩棵二叉樹b1和b2皆為空，或者皆不空且b1的左、右子樹和b2的左、右子樹分別相似，則稱二叉樹b1和b2相似。試編寫演算法，判別給定兩棵二叉樹是否相似。
解： int bitree_sim(bitree b1，bitree b2)//判斷兩棵樹是否相似的遞迴演算法
//insert_sqlist
初三綜合2答案
08福建莆田26題解析 1 解法一 設拋物線的解析式為y a x 3 x 4 因為b 0，4 在拋物線上，所以4 a 0 3 0 4 解得a 1 3 所以拋物線解析式為 2 連線dq，在rt aob中，所以ad ab 5，ac ad cd 3 4 7，cd ac ad 7 5 2 因為bd垂直平分p...
資陽理科綜合試題含答案
資陽市高中2014級第二次診斷性考試 理科綜合能力測試 注意事項 1 本試卷分第 卷 選擇題 和第 卷 非選擇題 兩部分。答題前，考生務必將自己的姓名 准考證號填寫在答題卡上，並將條形碼貼在答題卡上對應的虛線框內。2 回答第 卷時，選出每小題答案後，用鉛筆把答題卡上對應題目的答案標號塗黑。如需改動，...
高三理科數學綜合測試題附答案
數學檢測卷 理 一 選擇題 1 若集合，則 a.b.c d.2 直線關於軸對稱的直線方程為 ab.cd.3.若函式的乙個正數零點附近的函式值用二分法計算，其參考資料如下 那麼方程的乙個近似根 精確到0.1 為 a 1.2 b 1.3 c 1.4 d 1.5 4.設,若,則的值等於 a.b.1 c.2...