c. 後進先出的線性表 d.隨意進出的線性表
8.10階上三角矩陣壓縮儲存時需儲存的元素個數為( b )
a.11 b.56
c.100 d.101
9.深度為k（k≥1）的二叉樹，結點數最多有( b )
a.2k 個 b.(2k -1)個
c.2k-1個 d.(2k+1)個
10.具有12個結點的二叉樹的二叉鍊錶儲存結構中，空鏈域null的個數為( b )
a. 11 b.13 注：孩子有n-1個，空子域有n+1個，指標域有2n個。
c. 23 d. 25
11.具有n個頂點的無向圖的邊數最多為( c )
a.n+1 b.n(n+1)
c.n(n-1)/2 d.2n(n+1)
12.三個頂點v1,v2,v3的圖的鄰接矩陣為，該圖中頂點v3的入度為( b )
a. 0 b. 1
c. 2 d. 3
13.順序儲存的**中有60000個元素，已按關鍵字值公升序排列，假定對每個元素進行查詢的概率是相同的，且每個元素的關鍵字值不相同。用順序查詢法查詢時，平均比較次數約為( b )
a.20000 b.30000
c.40000 d.60000
14.外儲存器的主要特點是( b )
a.容量小和訪問速度低 b.容量大和訪問速度低
c.容量大和訪問速度高 d.容量小和訪問速度高
15.在待排資料基本有序的前提下，效率最高的排序演算法是( a )
a.直接插入排序 b.直接選擇排序
c.快速排序 d.歸併排序
二、填空題(本大題共13小題，每小題2分，共26分)
請在每小題的空格中填上正確答案。錯填、不填均無分。
16.資料的不可分割的最小標識單位是__資料項____，它通常不具有完整確定的實際意義，或不被當作乙個整體對待。
17.運算分為加工型運算和引用型運算，讀取操作是__引用____ 運算。
18.帶有頭結點的單向迴圈鍊錶l（l為頭指標）中，指標p所指結點為尾結點的條件是 _p->next=l_____。
19.在雙鏈表中，前趨指標和後繼指標分別為prior和next。若使指標p往後移動兩個結點，則需執行語句 _p=p->next->next____。
注：1.向乙個棧頂指標hs的棧中插入乙個*s指標，須執行的操作為；s->next=hs; hs=s;
2.單列表中指標p要刪除其後面的a結點（直接後繼）需要執行的操作為：p->next=p->next->next
下乙個下乙個原則）
20.元素s1，s2，s3，s4，s5，s6依次進入順序棧s，如果6個元素的退棧順序為s2，s3，s4，s6，s5，s1，則順序棧的容量至少為 _3_____。
21. 稀疏矩陣一般採用的壓縮儲存方法是_三元組表_____ 。
22. 在一棵樹中，___根___ 結點沒有雙親。
23.一棵具有n個結點的完全二叉樹中，從樹根起，自上而下、自左至右給所有結點編號。設根結點編號為1，若編號為i的結點有父結點，那麼其父結點的編號為 __i/2 __。
注：左孩子：為2i，，右孩子為2i+1.
24.二叉樹的二叉鍊錶儲存結構中判斷指標p所指結點為葉子結點的條件是_（p->lchild=null）&&（p->rchild=null）_____。
25.邊稀疏的無向圖採用 __鄰接表___儲存較省空間。
注：有向圖採用鄰接矩陣。
26.除第乙個頂點和最後乙個頂點相同外，其餘頂點不重複的迴路，稱為 _（簡單）迴路或（簡單）環____。
27.二分查詢演算法的時間複雜度是 __o（log2n）____。
28.要將序列建成堆，則只需把18與 ___51___相互交換。
三、應用題(本大題共5小題，每小題6分，共30分)
29.將題29圖所示的一棵二叉樹轉換成對應的森林。
t1t2t3
題29圖
30.給定權值｛3，9，13，5，7｝，構造相應的哈夫曼（huffman）樹，並計算其帶權路徑長度。
答：（1）由題可得哈夫曼樹如下：
31.寫出題31圖的鄰接矩陣和每個頂點的入度與出度。
題31圖
32. 二叉排序樹的各結點的值依次為20~28，請在題32圖中標出各結點的值。
題32圖
33.用氣泡排序法對資料序列（55，38，65，97，76，138，27，49）進行排序，寫出排序過程中的各趟結果。
答：初始關鍵字（55 38 65 97 76 138 27 49）
第一趟排序（38 55 65 76 97 27 49 138）
第二趟排序（38 55 65 76 27 49 97 138）
第三趟排序（38 55 65 27 49 76 97 138）
第四趟排序（38 55 27 49 65 76 97 138）
第五趟排序（38 27 49 55 65 76 97 138）
第六趟排序（27 38 49 55 65 76 97 138）
四、演算法設計題(本大題共2小題，每小題7分，共14分)
34.設線性表a =（a1， a2， …,am），b=（b1, b2, …,bn），試寫乙個按下列規則合併a，b為線性表c的演算法，使得
c=（a1, b1, …, am ,bm ,bm+1, …,bn） 當m≤n時；
或者 c=（a1, b1, …, an ,bn ,an+1, …,am） 當m>n時。
線性表a，b和c均以帶頭結點的單鏈表作為儲存結構，且c表利用a表和b表中的結點空間構成。（注意：單鏈表的長度值m和n均未顯式儲存。）
statuslistmerge_l(linklist&a,linklist&b,linklist&c)
if(!pa)qb->next=pb;
pb=b;free(pb);returnok;}
35. 二叉樹的二叉鍊錶型別定義如下：
typedef struct btnode bitreptr;
寫出後根遍歷根指標為t的二叉樹的遞迴演算法( void postorder (bitreptr *t) )。
void postorder(bitreptr*t)}
資料結構導論自考試題
全國2008年10月高等教育自學考試 課程 02142 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.從邏輯上可以把資料結構分為 a.動態結構 靜態結構 b.順序結構 鏈式結構 c....
全國自考試題資料結構試卷
全國2008年1月高等教育自學考試 資料結構試題 課程 02331 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.邏輯上通常可以將資料結構分為 a.動態結構和靜態結構 b.順序結構和...
02331自考全國資料結構試題
a.a,b,cb.a,b,c c.a b,cd.a,b,c 8.二維陣列a按行優先順序儲存，其中每個元素佔1個儲存單元。若a 1 1 的儲存位址為420，a 3 3 的儲存位址為446，則a 5 5 的儲存位址為 a.470b.471 c.472d.473 9.二叉樹中第5層上的結點個數最多為 a....