資料結構複習題 2023年6月
一、單項選擇題
1．鏈棧和順序棧相比，有乙個較明顯的優點是( )。
a.通常不會出現棧滿的情況 b. 通常不會出現棧空的情況
c.插入操作更加方便c.刪除操作更加方便
2．若待排序物件序列在排序前已按其排序碼遞增順序排序，則採用（ ）
方法比較次數最少。
a．直接插入排序b．分劃交換排序
c．歸併排序d．直接選擇排序
3．深度為n的二叉樹中所含葉子結點的個數最多為（ ）個。
a.2n c.2n-1 d.2n-1
4．在乙個有向圖中，所有頂點的入度之和等於所有頂點出度之和的( )倍。
a.1/2b. 1c.2d.4
5．按照二叉樹的定義,具有3個結點的二叉樹有( )種。
a. 3b. 4c. 5d. 6
6．棧和佇列都是（ ）。
a.順序儲存的線性表b.鏈式儲存的線性表
c.限制訪問點的線性結構 d.限制訪問點的非線性結構
7．串是（ ）。
a.一些符號構成的序列 b.一些字母構成的序列
c.乙個以上字元構成的序列 d.任意有限個字元構成的序列
8．在乙個具有n個頂點的無向圖中,要連通全部頂點至少需要( )條邊。
9．對有n個記錄的有序表採用二分查詢，其平均查詢長度的量級為（ ）。
a. o(log2n) b. o(nlog2n) c. o(n)
10．在乙個單鏈表中，若刪除(*p)結點的後繼結點，則執行( )。
a．p->next=p->next->next ;
b．p=p->next; p->next=p->next->next ;
c．p->next=p->next ;
d．p =p->next->next ;
11．鄰接表的儲存結構下圖的深度優先遍歷類似於二叉樹的( )。
a．先序遍歷 b. 中序遍歷 c. 後序遍歷 d. 按層遍歷
12．某二叉樹的前序和後序序列正好相反，則該二叉樹一定是( )二叉樹。
a．空或只有乙個結點b．高度等於其結點數
c．任意結點無左孩子d．任意結點無右孩子
13．設輸入序列為1,2,3,4,5，借助乙個棧可以得到的輸出序列是( )。
a．2,4,1,3,5b．3,4,1,5,2
c．3,2,4,1,5d．4,1,3,2,5
14．稀疏矩陣一般採用( )方法壓縮儲存。
a.三維陣列 b.單鏈表 c.三元組表 d.雜湊表
15．二維陣列a[5][6]的每個元素佔5個單元，將其按行優先順序儲存在起始
位址為1000的連續的記憶體單元中，則元素a[4][5]的儲存位址為（ ）。
a．1140 b．1145 c．1120 d．1125
16.具有n個頂點的有向圖最多可包含( )條有向邊。
a．n-1 b．n c．n(n-1)/2 d．n(n-1)
17.用分劃交換排序方法對包含有n個關鍵的序列進行排序，最壞情況下執
行的時間雜度為( )。
a. o(n) b. o(log2n) c. o(nlog2n) d. o(n2)
18.下面4個序列中，只有（ ）滿足堆的定義。
a. 13,27,49,76,76,38,85,97 b. 76,38,27,49,76,85,13,97
c. 13,76,49,76,27,38,85,97 d. 13,27,38,76,49,85,76,97
19.對稀疏矩陣進行壓縮儲存是為了（ ）。
a. 便於進行矩陣運算b. 便於輸入和輸出
c. 節省儲存空間d. 降低運算的時間複雜度
20.乙個遞迴的定義可以用遞迴過程求解，也可以用非遞迴過程求解，但單
從執行時間來看，通常遞迴過程比非遞迴過程（ ）。
a．較快 b．較慢 c．相同 d．不確定
二、填空題
1．在雙鏈表中每個結點有兩個指標域，乙個指向________，另乙個指向
2．對於順序儲存的棧，因為棧的空間是有限的，在進行_______運算時，
可能發生棧的上溢，在進行_______運算時，可能發生棧的下溢。
3．乙個演算法的時間複雜度為（5n2＋4nlog2n+8n）/(7n),其數量級表示為
________。
4．演算法分析的兩個主要方面是和
5．佇列中允許進行插入的一端稱為
6．設無向圖g的頂點數為n，則g最少有條邊。
7．二叉樹的遍歷方式有三種：先根遍歷
8.拓撲排序輸出的頂點數小於有向圖的頂點數，則該圖一定存在_______。
9.在n個結點的順序表中插入乙個結點需平均移動________個結點，具體
移動次數取決於
10.在有序表(15,24,23,48,45,62,85)中二分查詢關鍵詞23時所需進行的
關鍵詞比較次數為______。
11.若一棵二叉樹有10個葉結點，則該二叉樹中度為2的結點個數為
12.一般樹的儲存結構有雙親表示法、孩子兄弟表示法和
13．從邏輯關係上講，資料結構主要分為兩大類：線性結構和
14．在n個結點的順序表中刪除乙個結點需平均移動個結點，具
體移動次數取決於
15．在單鏈表中要在已知結點*p，之前插入一結點，仍需找到
其時間複雜度為而在雙鏈表中，完成同樣的操作其時間復
雜度為________。
16．採用二叉鍊錶儲存結構，具有n個結點的二叉樹一共有個指標域，
其中________指標域非空。
17．圖的儲存結構最常用的有和鄰接矩陣。
18．折半查詢方法適用於這樣的表：表中的記錄必須其儲存結構
必須是19.在棧的順序實現中，設棧頂指標為top，棧空的條件為
20.深度為8的（根的層次號為1）滿二叉樹有個結點。
三、應用題
1．將下圖中的二叉樹，轉換成相應的森林。
2．已知某二叉樹的後序序列為：dabec,中序序列為：debac,給出它的前序序列。
3．應用二路歸併排序演算法，對鍵值序列49,38,65,97,76,13,27,45從
小到大進行排序，試寫出每趟排序的結果。
4．給定表（55,36,56,6,64,32,8,41），按資料元素在表中的次序構造一棵
二叉排序樹。
5．利用普里姆（prim）演算法和克魯斯卡爾（kruskal）演算法求出下圖的最小支撐樹。
6．已知乙個圖如下所示，若從頂點0出發求出其深度優先搜尋序列和廣度優先搜尋序列。
7．應用直接插入排序演算法，對鍵值序列49,38,65,97,76,13,27,45從小到
大進行排序，試寫出每趟排序的結果。
四、演算法設計題
1．假設線性表用帶表頭結點的單向鍊錶表示，試寫出刪除表中所有data域值為零的元素的演算法。
2．設一棵二叉樹以二叉鍊錶為儲存結構，其中data域中存放乙個整數，bt指向二叉樹的根結點。設計乙個演算法求此二叉樹上data域的值為最大的結點。
資料結構複習題
1.資料結構可用三元式表示 d，s，p 其中 d是資料物件，s是d上的關係，p是對d的基本操作集。f 2 簡單地說,資料結構是帶有結構的資料元素的集合。t 3 判斷帶頭結點的非空迴圈單鏈表 頭指標為l 中指標p所指結點是最後乙個元素結點的條件是 p next l。t 4 線性表的鏈式儲存結構具有可直...
資料結構複習題
1 如果以鍊錶作為棧的儲存結構，則退棧操作時 a.必須判別棧是否滿 b.對棧不作任何判別 c.必須判別棧是否空 d.判別棧元素的型別 2 設陣列data 0.m 作為迴圈佇列sq的儲存空間，front為隊頭指標，rear為隊尾指標，則執行出隊操作的語句為 a.front front 1 b.fron...
資料結構複習題
13 14 1 資料結構 複習題 2013.12.一 判斷題 1.邊數很少的稀疏圖，適宜用鄰接矩陣表示。2.對於同一組記錄，生成二叉搜尋樹的形態與插入記錄的次序無關。3.有迴路的有向圖不能完成拓撲排序。4.對乙個連通圖進行一次深度優先搜尋可以遍訪圖中的所有頂點。5.乙個無向連通圖的生成樹是圖的極小的...