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.8b.15
c.16d.32
10.下列編碼中屬字首碼的是( )
a.c.
11.如果某圖的鄰接矩陣是對角線元素均為零的上三角矩陣，則此圖是( )
a.有向完全圖b.連通圖
c.強連通圖d.有向無環圖
12.對n個關鍵字的序列進行快速排序，平均情況下的空間複雜度為( )
a.o(1b.o(logn)
c.o(nd.o(n logn)
13.對錶長為n的順序表進行順序查詢，在查詢概率相等的情況下，查詢成功的平均查詢長度為( )
ab.cd.n
14.對於雜湊函式h(key)=key%13,被稱為同義詞的關鍵字是( )
a.35和41b.23和39
c.15和44d.25和51
15.稠密索引是在索引表中( )
a.為每個記錄建立乙個索引項b.為每個頁塊建立乙個索引項
c.為每組記錄建立乙個索引項d.為每個字段建立乙個索引項
二、填空題（每小題2分，若有兩個空格，每個空格1分，共20分）
16.當問題的規模n趨向無窮大時，演算法執行時間t(n)的數量級被稱為演算法的________。
17.在鍊錶的結點中，資料元素所佔的儲存量和整個結點所佔的儲存量之比稱作________。
18.已知鏈棧的結點結構為棧頂指標為top，則實現將指標p所指結點插入棧頂的語句依次為________和________。
19.空串的長度是________；空格串的長度是________。
20.假設乙個6階的下三角矩陣b按列優先順序壓縮儲存在一維陣列a中，其中a［0］儲存矩陣的第乙個元素b11,則a［14］儲存的元素是________。
21.在一棵度為3的樹中，度為2的結點個數是1，度為0的結點個數是6，則度為3的結點個數是________。
22.如圖所示的有向無環圖可以排出________種不同的拓撲序列。
23.利用篩選法將關鍵字序列(37，66，48，29，31，75)建成的大根堆為
24.對長度為20的有序表進行二分查詢的判定樹的高度為________。
25.在多重表檔案中，次關鍵字索引的組織方式是將________的記錄鏈結成乙個鍊錶。
三、解答題(每小題5分，共20分)
26.對於單鏈表、單迴圈鍊錶和雙向鍊錶，如果僅僅知道乙個指向鍊錶中某結點的指標p，能否將p所指結點的資料元素與其確實存在的直接前驅交換?請對每一種鍊錶作出判斷，若可以，寫出程式段；否則說明理由。
單鏈表和單迴圈鍊錶的結點結構為
雙向鍊錶的結點結構為
(1)單鏈表
(2)單迴圈鍊錶
(3)雙向鍊錶
27.假設通訊電文使用的字符集為，字元的哈夫曼編碼依次為：0110，10，110，111，00，0111和010。
(1)請根據哈夫曼編碼畫出此哈夫曼樹，並在葉子結點中標註相應字元；
(2)若這些字元在電文中出現的頻度分別為：3，35，13，15，20，5和9，求該哈夫曼樹的帶權路徑長度。
28.當採用鄰接表作為圖的儲存結構時，也可將鄰接表中的頂點表由順序結構改為鍊錶結構。
(1)請分別畫出這種鄰接表的頂點鍊錶結點和邊表結點，並說明結點中各個域的作用；
(2)對如圖所示的有向圖畫出這種鄰接表。
29.已知4階b-樹如圖所示。
(1)分別畫出將關鍵字23和89相繼插入之後的b-樹。
(2)畫出從插入之前的b-樹中刪除關鍵字51之後的b-樹。
四、演算法閱讀題(每小題5分，共20分)
30.閱讀下列函式algo,並回答問題：
(1)假設佇列q中的元素為(2,4,5,7,8),其中「2」為隊頭元素。寫出執行函式呼叫algo(&q)後的佇列q；
(2)簡述演算法algo的功能。
void algo(queue *q)
(1)(2)
31.閱讀下列函式f，並回答問題：
(1)已知如圖所示的二叉樹以二叉鍊錶作儲存結構，rt為指向根結點的指標。寫出執行函式呼叫f(rt)的輸出結果。
(2)說明函式f的功能。
void f(bintree t)
}}(1)(2)
32.已知鄰接表的頂點表結點結構為
邊表結點edgenode的結構為
下列演算法計算有向圖g中頂點vi的入度。請在空缺處填入合適的內容，使其成為乙個完整的演算法。
int finddegree(algraph *g,int i)//algraph為圖的鄰接表型別
p=p->next;
}}return degree;
}(1)
(2)(3)
33.已知單鏈表的結點結構為
下列演算法對帶頭結點的單鏈表l進行簡單選擇排序，使得l中的元素按值從小到大排列。
請在空缺處填入合適的內容，使其成為完整的演算法。
void selectsort(linkedlist l)
if( (3) )
(4) ;
}}(1)(2)
(3)(4)
五、演算法設計題(本題10分)
34.設線性表a=(a1,a2,a3,…,an)以帶頭結點的單鏈表作為儲存結構。編寫乙個函式，對a進行調整，使得當n為奇數時a=(a2,a4,…,an-1,a1,a3,…,an)，當n為偶數時a=(a2,a4,…,an,a1,a3,…,an-1)。
全國自考試題資料結構試卷
全國2008年1月高等教育自學考試 資料結構試題 課程 02331 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.邏輯上通常可以將資料結構分為 a.動態結構和靜態結構 b.順序結構和...
自考資料結構試題真題
全國2012年1月高等教育自學考試 課程 02331 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.每個結點有且僅有乙個直接前趨和多個 或無 直接後繼 第乙個結點除外 的資料結構稱為...
全國自考資料結構導論考試試題,答案,筆記
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個結點的二叉樹的二叉鍊錶儲存...