時間：120分鐘滿分：100分
一、 選擇題(每小題1分，共20分)
1．以下資料結構中， 是線性結構。
a）隊 b）樹 c二叉樹 d）圖
2．5個頂點的無向圖最多有條邊。
a、5 b、10 c、20d、25
3．下面是順序儲存結構的優點。
a）儲存密度大 b）插入運算方便 c查詢方便 d）適合各種邏輯結構的儲存表示
4．下面關於串的敘述中， 是不正確的。
a）串是字元的有限序列b）空串是由空格構成的串
c）模式匹配是串的一種重要運算 d）串既可以採用順序儲存，也可以採用鏈式儲存
5． 的鄰接矩陣是對稱矩陣。
a）有向圖 b）無向圖 c）aov網 d）aoe網
6．用鏈式方式儲存的佇列，在進行刪除運算時
a）僅修改頭指標b）僅修改尾指標
c）頭、尾指標都要修改 d）頭、尾指標可能都要修改
7．二叉樹的先序遍歷和中序遍歷如下，則該二叉樹右子樹的樹根是
先序序列：efhigjk中序序列：hfiejkg
a）e b）f c）g d）h
8．下面方法可以判斷出乙個有向圖中是否有環。
a）深度優先遍歷b）拓樸排序c）求最短路徑d）求關鍵路徑
9． 若**性表中採用折半查詢法查詢元素，該線性表應該 。
a）元素按值有序b）採用順序儲存結構
c）元素按值有序，且採用順序儲存結構 d）元素按值有序，且採用鏈式儲存結構
10．從未排序序列中依次取出乙個元素與已排序序列中的元素依次進行比較，然後將其放在已排序序列的合適位置，該排序方法稱為排序法。
a）插入 b）選擇 c）冒泡 d）都不是
11．在乙個長度為n的順序儲存的線性表中，向第i個元素（1≤i≤n+1）插入乙個新元素時，需要從後向前依次後移個元素。
a、n-i b、n-i-1 c、n-i+1 d、i
12．乙個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是
a、edcbab、decba c、dceabd、abcde
13．從鄰接矩陣可以看出，該圖共有頂點。
a、9 b、3 c、6d、1
14．上題中，若是有向圖，則有條弧。
a、5 b、4 c、3d、2
15．n個節點的完全二叉樹，編號為i的節點是葉子結點的條件是
a、ind、2*i>n
16．向乙個有128個元素的順序表中插入乙個新元素並保持原來順序不變，平均要移動
個元素。
a、64.5b、64c、63d、65
17．在乙個單鏈表hl中，若要在指標q所指結點的後面插入乙個由指標p所指向的結點，則執行
a、q->next=p->next; p->next=qb、p->next=q->next; q=p;
c、p->next=p->next; q->next=qd、p->next=q->next; q->nxet=p;
18．對乙個滿二叉樹，m個樹葉，n個結點，深度為h，則有
a、n=h+mb、h+m=2n
c、m=h-1d、n=2-1
19．假定乙個鏈隊的隊首和隊尾指標分別為front和rear，則判斷隊空的條件為
a、front==rearb、front!=null
c、rear!=nulld、front==null
20．在所有排序方法中，關鍵字比較的次數與記錄的初始排列次序無關的是
a、選擇排序b、氣泡排序 c、插入排序d、希爾排序
二、判斷題：（判斷下列各題正誤，正確的在題目後面的括號內寫「對」，錯誤的在題目後面的括號內寫「錯」。每小題2分，共10分）
（ ）1. 棧和佇列都是非線性資料結構
（ ）2. 完全二叉樹可以用順序儲存結構進行儲存。
（ ）3. 資料元素是資料的最小單位。(基本單位)
（ ）4. 含尾指標的單鏈迴圈表可以被用於佇列操作。
（ ）5. 資料結構包含資料的邏輯結構、資料的儲存結構以及資料集合上定義的運算。
三、填空題（每空2分，共10分）
1、 **性表的單鏈表儲存結構中，每個結點包含兩個域，乙個叫資料（值） 域，
另乙個叫指標域 。
2、 設字串s1=『abcdefg』，s2=『pqrst』，則運算
s=concat（sub（s1，2，len（s2）），sub（s1，len（s2），2））後的串值為 bcdef ef
3、 佇列的插入操作在隊尾進行，棧的刪除操作在棧頂進行。
四、回答下列問題（每小題8分，共40分）
1． 分別給出對下圖進行深度優先和廣度優先遍歷的結果。
1．深度：125963784 （不唯一）
廣度：123456789 （不唯一）
2．已知序列（12，4，17，10，7，30），用直接選擇排序法對其進行遞增排序，寫出每一趟的排序結果。
2．第1趟：4 12 17 10 7 30
第2趟：4 7 17 10 12 30
第3趟：4 7 10 17 12 30
第4趟：4 7 10 12 17 30
第5趟：4 7 10 12 17 30
3．一批資料有如下的邏輯結構b=(k ,r),其中
k={}, r=, r={} ,
試用圖示法表示其邏輯結構。
4．已知一棵非空二叉樹，其按中序和後序遍歷的結果分別為：
中序：cgbahedjfi 後序：gbchejifda
請畫出這棵二叉樹，並寫出其前序遍歷的結果。
前序遍歷結果:acbgdehfji
5．已知字元：c1，c2，c3，c4，c5，c6的權分別為：17，5，16，4，8，11，請構造相應的赫夫曼樹，並給出相應字元的赫夫曼編碼。
c1:10 c2:1111 c3:01 c4:1110 c5:110 c6:00
五、編寫演算法（每小題10分，共20分）
要求: 1、說明演算法中使用的主要資料結構、變數；2、用c可
1．設有乙個由正整數組成的無序無頭結點的單鏈表，編寫子程式(或函式)找到其最小值。
2． 氣泡排序。
1． struc node
int minn(node *p)
p=p->next;}
return(x);
}2． int n;
int p[n];
void sort(int p,n)}
資料結構試題及答案
資料結構試卷 一 一 單選題 每題 2 分，共20分 1.棧和佇列的共同特點是 a a.只允許在端點處插入和刪除元素 b.都是先進後出 c.都是先進先出 d.沒有共同點 2.用鏈結方式儲存的佇列，在進行插入運算時 d a.僅修改頭指標b.頭 尾指標都要修改 c.僅修改尾指標d.頭 尾指標可能都要修改...
資料結構試題及答案
2 二維陣列是陣列元素為一維陣列的線性表，因此它是線性結構。3 順序錶用一維陣列作為儲存結構，因此順序表是一維陣列。4 通常使用兩個類來協同表示單鏈表，即鍊錶的結點類和鍊錶類。5 棧和佇列都是順序訪問的的線性表，但它們對訪問位置的限制不同。6 在使用字尾表表示實現計算器時用到乙個棧的例項，其作用是暫...
資料結構試題及答案
資料結構 自考複習思考試題 一 單選題 從選擇的答案中選出正確的答案，將其字母編號填入下列敘述中的括號內。每小題 3分，共24分 1 向乙個有127個元素原順序表中插入乙個新元素並儲存原來順序不變，平均要移動 個元素。a 8 b 63.5 c 63 d 7 2 設有乙個二維數a m n 假設a 0 ...