單項選擇題
1.資料的（b）包括集合、線性、樹和圖4種基本型別
a．儲存結構b．邏輯結構c．基本運算d．演算法描述
2.對乙個長度為n的順序表，在第i個元素（1≤i≤n+1）之前插入乙個新元素時需向右移動（b）個元素。
a．n-ib．n-i+1c．n-i-1d．i
3下面程式的時間複雜度為（c ）。
for(i=0;i for(j=0;ja[i][j]=i*j;
a.o(m2b. o(n2c. o(n*m) d.o(n+m)
4長度為n的線性表採用順序儲存結構，在其第i個位置插入乙個新元素的演算法時間複雜度為（c）。若沒說明在第幾個位置插入，則其複雜度為d
a．o(0) b．o(1) c．o(n) d．o(n2)
5.資料結構就是研究（ d ）。
a．資料的邏輯結構b．資料的儲存結構
c．資料的邏輯結構和儲存結構
d．資料的邏輯結構、儲存結構及其資料在運算上的實現
6下面關於演算法的說法，錯誤的是（ d ）。
a．演算法最終必須由電腦程式實現
b．為解決某問題的演算法和為該問題編寫的程式含義是相同的
c．演算法的可行性是指指令不能有二義性
d．以上三種說法都錯誤
7線性表l=（a1，a2 ，……an，）下列說法正確的是（ d ）。
a．每個元素都有乙個直接前驅和乙個直接後繼
b．線性表中至少要有乙個元素
c．表中所有元素的排列順序必須是由小到大或由大到小
d．除第乙個和最後乙個元素外，其餘每個元素都有且僅有乙個直接前驅和乙個直接後繼
8．下面關於線性表敘述錯誤的是（ b ）。
a．線性表採用順序儲存，必須占用一段位址連續的單元
b．線性表採用順序儲存，便於進行插入和刪除操作
c．線性表採用鏈式儲存，不必占用一段位址連續的單元
d．線性表採用鏈式儲存，便於進行插入和刪除操作
9用鍊錶表示線性表的優點是（c）
a．便於隨機訪問b．儲存空間比順序儲存方式少
c．便於插入和刪除d．資料元素的儲存順序與邏輯順序相同
10若某線性表中最常用的操作是取第i 個元素和找第i個元素的前趨元素，則採用（ d ）儲存方式最節省時間。
a．單鏈表b．雙鏈表c．單向迴圈d．順序表
11.若佇列採用順序儲存結構，元素的排列順序（b）
a．與元素值的大小有關b．由元素進入佇列的先後順序決定
c．與隊頭指標和隊尾指標的取值有關 d．與作為順序儲存結構的陣列大小有關
12.三個元素按照a,b,c的順序入棧，下列哪乙個是不合法的出棧序列？（b）
a. abcb. cabc. acbd. bac
13假定乙個順序迴圈佇列儲存於長度為n的一維陣列中，其隊頭和隊尾指標分別用front和rear表示，則判斷隊滿的條件是（a）
a．（rear+1）%n==frontb．front+1==rear
c．rear==（front-1）%nd．rear==（front+1）%n
14假定乙個順序迴圈佇列的隊頭和隊尾指標分別用front和rear表示，則判隊空的條件是（d）。
a．（front+1）%n==rearb．front==rear+1
c．front==0d．front==rear
15.深度為5（假設空樹的深度為0）的二叉樹至多有（ c ）結點。
a．64b．32c．31d．63
16乙個具有n個頂點的無向完全圖的邊數為（ b ）
a．n(n+1)/2b．n(n-1)/2c．n(n-1d．n(n+1)
17後序遍歷序列為g d b e f c a,中序遍歷序列為d g b a e c f，則前序遍歷序列為（ ）。
a．a b g d c e f b．a b d g c f e c．b d g c e fad．a b d g c e f
18 如果以鍊錶作為棧的儲存結構，則出棧操作時（ c ）
a．必須判別棧是否滿b．對棧不作任何判別
c．必須判別棧是否空d．判別棧元素的型別
19線性表採用鏈式儲存時，其位址（ d ）。
a．必須連續 b．部分位址必須連續
c．必須連續 d．連續與否均可
20資料的（ b ）包括集合、線性、樹和圖4種基本型別。
a．儲存結構 b．邏輯結構 c．基本運算 d．演算法描述
21一棵完全二叉樹上有15個結點，其深度是不超過（c）的最大整數。
a．2b．3c．4d．a~c項都不對
22若某線性表中最常用的操作是在最後乙個元素之後插入乙個元素和刪除最後乙個元素，則採用（ d ）儲存方式最節省運算時間。
a．單鏈表b．雙鏈表 c．帶頭結點的雙迴圈鍊錶 d．容量足夠大的順序表
23.二叉樹中第5層上的結點個數最多為_c___
a.8b.15
c.16d.32
24.深度為5的二叉樹至多有（ d ）結點。
a．64b．32
c．31d．63
25.將一棵有100個結點的完全二叉樹從上到下，從左到右依次對結點進行編號，根結點的編號為1，則編號為49的結點的左孩子的編號為__a____。
a.98b.99
c.50d.48
26．已知廣義表的表頭為a，表尾為(b,c)，則此廣義表為___b_____
a.（a,(b,cb.（a,b,c）
c.((a),b,cd.(( a,b,c))
填空題1.對於給定的n個元素，可以構造出的邏輯結構有（集合）、（線性）、（樹）、（ 圖 ）4種。
2資料元素在計算機中的方式稱為儲存結構。
3線性結構中的元素之間存在（一對一）關係，樹形結構中元素之間存在（ 一對多 ）關係，圖形結構中的元素之間存在（ 多對多 ）關係。
4設單鏈表的結點結構為（data，*next），已知指標p指向單鏈表中x結點，指標q指向y的新結點，若將結點y插入到結點x之後，則需要執行以下兩條語句（ q->next=p->next ）， （ p->next=q ）。
5資料的（ 邏輯 ）結構與資料元素本身的內容和形式無關。
6乙個演算法的好壞取決於該演算法的（ 時間複雜度 ）和（ 空間複雜度 ）。
7資料結構中評價演算法的兩個重要指標是（ 時間複雜度 ）、空間複雜度。
8乙個迴圈佇列儲存於下標由0開始且長度為m的一維陣列中，假定隊頭和隊尾指標分別為front和rear，則判斷隊空的條件為（（rear+1）%n==front）。則判斷隊滿的條件為（ front==rear ）。
9 佇列的插入操作是在佇列的（ 隊尾 ）進行，刪除操作是在佇列的（ 隊頭 ）進行。
10堆疊的邏輯特點是（ 先進後出 ），佇列的邏輯特點是（ 先進先出 ）。
11堆疊的邏輯特點是（ 先進後出 ），佇列的邏輯特點是（ 先進先出 ）。二者的共同點是只允許在它們的（ 端點 ）處插入和刪除資料元素。
12堆疊操作設輸入元素的順序為1,2,3,4,5，要在棧的輸出端得到43521，則應進行棧的基本運算表示應為：push（s,1），push(s,2)，push(s,3)，push(s,4)，pop(s)，（ pop(s) ），（ push(s,5) ），pop(s)，pop(s)，pop(s)。
13設有乙個鏈隊，結點結構為data|next，front為隊頭指標，rear為隊尾指標，當執行入隊操作時需執行下列語句：malloc(p)；p->data=x; p->next=null
13、一棵二叉樹有67個結點,這些結點的度要麼是0，要麼是2。這棵二叉樹中度數為2的結點有個。
14、乙個哈夫曼(huffman)樹有19個結點，則其葉結點的個數是
15、一棵深度為6的滿二叉樹有 31 個分支結點和 32 個葉子。
16、設二叉樹結點的先序序列為abdecfgh，中序序列為debafchg,則二叉樹的後序序列是
17. 克魯斯卡爾演算法的時間複雜度為（ ），適合求的最小生成樹。
18.空串是（），其長度等於
19.空格串是（），其長度等於
20.兩個字串相等的充分必要條件是（）。
21寫出模式串p=「abaabcac」的next函數值串行為（）
22、設有一稀疏圖g，則g採用儲存結構較省空間。
23、已知廣義表a=((a,b,c),(d,e,f)),則運算head(head (tail（a
24．一棵深度為6的滿二叉樹有個分支結點和個葉子。
25．在對一組記錄（54，38，96，23，15，72，60，45，83）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置至少需比較次。
應用題1．什麼是線性結構？線性結構的特點是什麼？ 列舉？
2.什麼是樹形結構？樹形結構的特點是什麼？
3.什麼是圖結構？
4.已知二叉樹的前序abcdefghij和中序cdbfeaihgj，試構造出相應的二叉樹。
5.已知一棵二叉樹的後序遍歷序列為eicbgahdf，中序遍歷序列為ecifbagdh，請畫出這棵二叉樹，
7. 對於乙個有10000個結點的二叉樹，樹葉最多有多少個？最少有多少個？
8寫出某個有向圖的頂點v和弧e的鄰接矩陣。
9已知某二叉樹，寫出前序遍歷、中序遍歷和後序遍歷
10根據普里姆演算法思想，畫出構造該無向帶權圖最小生成樹的過程。（5分）
11的有向帶權圖，根據狄克斯特拉演算法思想，畫出生成從頂點a到其餘各項頂點最短路徑的過程。
資料結構複習題
1.資料結構可用三元式表示 d，s，p 其中 d是資料物件，s是d上的關係，p是對d的基本操作集。f 2 簡單地說,資料結構是帶有結構的資料元素的集合。t 3 判斷帶頭結點的非空迴圈單鏈表 頭指標為l 中指標p所指結點是最後乙個元素結點的條件是 p next l。t 4 線性表的鏈式儲存結構具有可直...
資料結構複習題
資料結構複習題 2004年6月 一 單項選擇題 1 鏈棧和順序棧相比，有乙個較明顯的優點是 a.通常不會出現棧滿的情況 b.通常不會出現棧空的情況 c.插入操作更加方便c.刪除操作更加方便 2 若待排序物件序列在排序前已按其排序碼遞增順序排序，則採用 方法比較次數最少。a 直接插入排序b 分劃交換排...
資料結構複習題
1 如果以鍊錶作為棧的儲存結構，則退棧操作時 a.必須判別棧是否滿 b.對棧不作任何判別 c.必須判別棧是否空 d.判別棧元素的型別 2 設陣列data 0.m 作為迴圈佇列sq的儲存空間，front為隊頭指標，rear為隊尾指標，則執行出隊操作的語句為 a.front front 1 b.fron...