一、單項選擇題（每小題2分，共30分）
1.資料結構中，與所使用的計算機無關的是資料的（ ）結構。
a. 邏輯 b. 物理 c. 儲存d. 邏輯與物理
2.下述各類表中可以隨機訪問的是（ ）。
a. 單向鍊錶 b. 雙向鍊錶 c.單向迴圈鍊錶 d.順序表
3.在乙個長度為n的順序表中為了刪除第5個元素，從前到後依次移動了15個元素。則原順序表的長度為（ ）。
a. 21b. 20c. 19d. 25
4.元素2，4，6按順序依次進棧，則該棧的不可能的輸出序列是（ ）。
a. 6 4 2 b. 6 2 4 c. 4 2 6 d. 2 6 4
5.乙個佇列的入隊序列是5，6，7，8，則佇列的輸出序列是（ ）。
a. 5 6 7 8b. 8 7 6 5
c. 7 8 6 5d.可能有多種情況
6. 串函式strcmp（「d」，「d」）的值為（ ）。
a．0b．1c．-1d．3
7．在乙個單鏈表中，p、q分別指向表中兩個相鄰的結點，且q所指結點是p所指結點的直接後繼，現要刪除q所指結點，可用語句（ ）。
a．p=qnext b．pnext=q c．pnext=qnext d．qnext=null
8.設一棵哈夫曼樹共有n個非葉結點，則該樹一共有（ ）個結點。
a. 2*n-1 b. 2*n +1 c. 2*n d. 2*(n-1)
9.對如圖1所示二叉樹進行中序遍歷，結果是（ ）。
a. dfebagc b. defbagc c. defbacg
10 . 任何乙個無向連通圖的最小生成樹（ ）。
a.至少有一棵 b.只有一棵 c.一定有多棵 d.可能不存在
11．設有乙個10階的對稱矩陣a，採用壓縮儲存的方式，將其下三角部分以行序為主序儲存到一維陣列b中（陣列下標從1開始），則矩陣中元素a8,5在一維陣列b中的下標是（ ）。
a．33b．32c．85d．41
12 . 一組記錄的關鍵字序列為（37，70，47，29，31，85），利用快速排序，以第乙個關鍵字為分割元素，經過一次劃分後結果為（ ）。
a．31，29，37，85，47，70 b．29，31，37，47，70，85
c．31，29，37，70，47，85 d．31，29，37，47，70，85
13 . 對n個元素進行氣泡排序，要求按公升序排列，程式中設定某一趟冒泡沒有出現元素交換，就結束排序過程。對某n個元素的排序共進行了3n-6次元素間的比較就完成了排序，則（ ）。
a.原序列是公升序排列
b.原序列是降序排列
c.對序列只進行了2趟冒泡
d. 對序列只進行了3趟冒泡
14．在乙個棧頂指標為top的鏈棧中刪除乙個結點時，用x儲存被刪除的結點，應執行（ ）。
>data;top=top->next; b. top=top->next ; x=top;
>nextd. x=top->data;
15．串函式strcat（a,b）的功能是進行串（ ）。
a．比較 b．複製 c．賦值 d．連線
二、填空題（每小題2分，共24分）
1．在乙個單向鍊錶中p所指結點之後插入乙個s所指的新結點，應執行s->next=p->next；和______操作。
2．根據資料元素間關係的不同特性，通常可分為四類基本結構。
3．在乙個鏈隊中，設f和r分別為隊頭和隊尾指標，則刪除乙個結點的操作為結點的指標域為next)
4.________遍歷二叉排序樹可得到乙個有序序列。
5.一棵有2n-1個結點的二叉樹，其每乙個非葉結點的度數都為2，則該樹共有_______個葉結點。
6.如圖1所示的二叉樹，其中序遍歷序列為
圖17.對稀疏矩陣進行壓縮儲存，矩陣中每個非零元素所對應的三元組包括該元素的和________三項資訊。
8 . 有乙個有序表,用折半查詢法查詢值為82的結點，經________次比較後查詢成功。
9 .圖的深度優先搜尋和廣度優先搜尋序列不是唯一的。此斷言是______的。(回答正確或不正確)
10．雜湊法既是一種儲存方法，又是一種
11．44.在對一組記錄(55,39,97,22,16,73,65,47,88)進行直接插入排序時，當把第7個記錄65插入到有序表時，為尋找插入位置需比較_________次。
12．棧和佇列的操作特點分別是________和
三、綜合題（每小題10分，共30分）
1．已知序列 ，
（1）試給出用歸併排序法對該序列作公升序排序時的每一趟的結果。
（2）對上述序列用堆排序的方法建立初始堆（要求小根堆，以二叉樹描述建堆過程）。
2．設有序表為（13，19，25，36，48，51，63，84，91，116，135，200），元素的下標依次為1,2,……,12.
（1）說出有哪幾個元素需要經過3次元素間的比較才能成功查到
（2）畫出對上述有序表進行折半查詢所對應的判定樹（樹結點用下標表示）
（3）設查詢元素5，需要進行多少次元素間的比較才能確定不能查到.
3． (1) 設有查詢表,依次取表中資料，構造一棵二叉排序樹.
（2）說明如何通過序列的二叉排序樹得到相應序列的排序結果，對上述二叉排序給出中序遍歷的結果.
四、程式填空題（每空2分，共16分）
1．以下冒泡法程式對存放在a[1]，a[2]，……，a[n]中的序列進行氣泡排序，完成程式中的空格部分，其中n是元素個數，程式按公升序排列。
void bsort (node a[ ], int)
if(flag= =0)break;}}
程式中flag的功能是（5
7．以下程式是後序遍歷二叉樹的遞迴演算法的程式，完成程式中空格部分（樹結構中左、右指標域分別為left和right，資料域為data，其資料型別為字元型，bt指向根結點）。
void postorder (struct btree node *bt)
}試題答案；
一、單項選擇題（每小題2分，共30分）
1．a 2．d 3．b 4．b 5．a 6．c 7．c 8．b 9．a 10．a
11．a 12．d 13．d 14．a 15．d
二、填空題（每小題2分，共24分）
>next=s;
2.集合、線性、樹形、圖狀
3. f=f->next;
4.中序
6. dgbaechhif
7.行號、列號、元素值
8.4次
9.正確
10．查詢方法
11．3次
12．先進後出先進先出
三、綜合題（每小題10分，共30分）
1．(1) 初始 11，19，5，4，7，13，2，10
第一趟 [ 11，19][4，5][7，13][2，10]
第二趟 [4，5，11，19][2，7，10，，13]
第三趟 [2，4，5，7，10，11，13，19]
(2)2．
(1)13,36,63,135
(2)(3)3次
3． (1)
(2)中序遍歷
中序 2，3，4，5，6，7，14，16，18
四、程式填空題（每空2分，共16分）
1．（1）j<=n-1
（2）i<=n-j
（3）a[i]=a[i+1]
（4）a[i+1]=temp
（5）當某趟冒泡中沒有出現交換則已排好序，結束迴圈
2．（1） postorder(btleft)
（2）postorder(btright)
（3） printf(「%c」,btdata)
資料結構模擬試題
4 假設一棵二叉樹先序遍歷序列是abcedfghij和中序序列是ecdbfaihjg，則該樹中第二層最左邊的結點為根的層次為1 5 若線索二叉樹中t所指結點滿足條件t ltag thread，則t lchild域指示結點的若t rtag link，則t rchild域指示結點的 6 在序列 2，8，...
資料結構模擬試題二
3.已知某圖的鄰接表儲存結構如下 那麼針對該鄰接表的深度優先遍歷結果為廣度優先遍歷結果為 4.設根結點處在第一層，那麼具有n個結點的完全二叉樹，其高度為 5.快速排序方法的最壞時間複雜度為平均時間複雜度為 6.給定表 55,63,44,38,75,80,31,56 用篩選法建立初始堆，則初始堆表為 ...
資料結構試題,模擬考試題
資料結構試題 單選題在資料結構的討論中把資料結構從邏輯上分為 c a 內部結構與外部結構b 靜態結構與動態結構 c 線性結構與非線性結構d 緊湊結構與非緊湊結構。2 採用線性鍊錶表示乙個向量時，要求占用的儲存空間位址 d a 必須是連續的b 部分位址必須是連續的 c 一定是不連續的d 可連續可不連續...