課程**：02331
一、單項選擇題(本大題共15小題，每小題2分，共30分)
在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其**填寫在題後的括號內。錯選、多選或未選均無分。
1.每個結點有且僅有乙個直接前趨和多個(或無)直接後繼(第乙個結點除外)的資料結構稱為（ ）
a.樹狀結構 b.網狀結構
c.線性結構 d.層次結構
2.某線性表中最常用的操作是在最後乙個元素之後插入元素和刪除第乙個元素，則最節省運算時間的儲存結構是（ ）
a.單鏈表 b.雙鏈表
c.僅有頭指標的單迴圈鍊錶 d.僅有尾指標的單迴圈鍊錶
3.已知乙個棧的入棧序列是1，2，3，…，n，其輸出序列為pl，p2，p3….，pn，若p1是n，則pi是（ ）
a.i b.n-i
c.n-i+l d.不確定
4.下面關於串的敘述中，正確的是（ ）
a.串是一種特殊的線性表 b.串中元素只能是字母
c.空串就是空白串 d.串的長度必須大於零
5.無向完全圖g有n個結點，則它的邊的總數為（ ）
a.n2 b.n(n-1)
c.n(n-1)/2 d.(n-1)
6.若一棵二叉樹有10個度為2的結點，5個度為1的結點，則度為0的結點數是（ ）
a.9 b.11
c.15 d.不確定
7.如圖所示，在下面的4個序列中，不符合深度優先遍歷的序列是（ ）
a.acfdeb
b.aebdfc
c.aedfbc
d.aefdbc
8.無論待排序列是否有序，排序演算法時間複雜度都是o(n2)的排序方法是（ ）
a.快速排序 b.歸併排序
c.氣泡排序 d.直接選擇排序
9.已知二叉排序樹g，要輸出其結點的有序序列，則採用的遍歷方法是（ ）
a.按層遍歷 b.前序遍歷
c.中序遍歷 d.後序遍歷
10.用isam和vsam組織的檔案都屬於（ ）
a.雜湊檔案 b.索引順序檔案
c.索引非順序檔案 d.多關鍵字檔案
11.對序列(15，9，7，8，20，-1，4)進行排序，第一趟排序後的序列變為(4，9，-1，8，20，7，15)，則採用的排序方法是（ ）
a.選擇 b.快速
c.希爾 d.冒泡
12.當採用分塊查詢時，資料的組織方式為（ ）
a.資料分成若干塊，每塊內資料有序
b.資料分成若干塊，每塊中資料個數必須相同
c.資料分成若干塊，每塊內資料有序，塊間是否有序均可
d.資料分成若干塊，每塊內資料不必有序，但塊間必須有序
13.下述編碼中不是字首碼的是（ ）
a.(00，01，10，11) b.(0，1，00，11)
c.(0，10，110，111) d.(1，01，000，001)
14.若乙個棧以向量v[1..n]儲存，初始棧頂指標top為n+l，則x進棧的正確操作是（ ）
b.v[top]=x；top=top+1
d.v[top]=x；top=top-1
15.在乙個以head為頭結點指標的非空單迴圈鍊錶中，指標p指向鏈尾結點的條件是（ ）
a.p - > data = - 1 b.p - > next = null
c.p - > next - > next=head d.p - > next = head
二、填空題(本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分)請在每個空格中填上正確答案。錯填、不填均無分。
16.在資料的邏輯結構和儲存結構中，與計算機無關的是______。
17.線性表l=(a1,a2,…，an)用陣列表示，假定刪除表中任一元素的概率相同，則刪除乙個元素平均需要移動元素的個數是______。
18.設迴圈佇列的容量為50(序號從0到49)，現經過一系列的入隊和出隊運算後，有①front=11，rear=29；②front=29，rear=11；在這兩種情況下，迴圈佇列中的元素個數分別是______和______。
19.設t和p是兩個給定的串，在t中尋找等於p的子串的過程稱為______。
20.已知三對角矩陣a[10][10]的每個元素佔2個單元，現將其三條對角線上的元素逐行儲存在起始位址為 1000 的連續的記憶體單元中，則元素 a[6][7] 的位址為______。
21.若以(4，5，6，7，8)作為葉子結點的權值構造哈夫曼樹，則其帶權路徑長度是______。
22.有向圖g如圖所示，它的兩個拓撲排序序列分別為______和______。
23.一組記錄的關鍵字為(46，79，56，38，40，84)，則利用快速排序的方法，以第乙個記錄為基準得到的一次劃分結果為______。
24.已知廣義表a=(x，((a，b)，c，))，函式head(head(tail(a)))的運算結果是______。
25.索引順序檔案既可以順序訪問，也可以______。
三、解答題(本大題共4小題，每小題5分，共20分)
26.對關鍵字序列(26，18，60，14，7，45，13，32)進行降序的堆排序，寫出構建的初始堆(小根堆)及前兩趟重建堆之後序列狀態。
初始堆：
第一趟：
第二趟：
27.設雜湊函式為h (key)=key ％ 11，雜湊位址空間為0··10，對關鍵字序列(27，13，55，32，18，49，24，38，43)用線性探查法解決衝突，構建雜湊表。現已有前4個關鍵字構建的雜湊表如下所示，請將剩餘5個關鍵字填入表中相應的位置。
28.已知一棵二叉樹的前序遍歷和中序遍歷序列分別為：abcdefg和cbdaegf，請畫出此二叉樹，並給出後序遍歷序列。
29.已知如圖所示的帶權無向圖，請畫出用普里姆演算法從頂點1開始的最小生成樹的構造過程。
四、演算法閱讀題(本大題共4小題，每小題5分，共20分)
30.閱讀下列演算法，並回答下列問題：
(1)簡述該演算法的功能；
(2)寫出分別輸入字串："abcba"和"abcbde"，呼叫演算法函式的返回值。
int symmetry(void)
(1)(2)
31.下列演算法是利用二分查詢方法在遞減有序表r中插入元素x，並保持表r的有序性。請在空缺處填入適當的內容，使其成為乙個完整的演算法。
typedef struct rectype；
typedef rectype seqlist [maxlen]
void bininsert(seqlist r,int *n，rectype x)
for (i=*n；i>=low；i--)
r[i+1]=r[i]；
3++(*n)；
}(1)
(2)(3)
32.閱讀下列演算法，並回答下列問題：
(1)簡述該演算法中標號s1所指示的迴圈語句的功能；
(2)簡述該演算法中標號s2所指示的迴圈語句的功能。
linklist insertmnode(linklist head，char x，int m)
p->next=q；
}return head；
}(1)
(2)33.閱讀下列演算法，並回答下列問題：
(1)該演算法採用的是何種排序方法?
(2)演算法中的r[n+1]的作用是什麼?
typedef struct rectype；
typedef rectype seqlist[maxlen]；
void sort(seqlist r，int n)
}(1)
(2)五、演算法設計題(本題10分)
34.假設以單鏈表表示線性表，單鏈表的型別定義如下：
typedef struct node linknode，* linklist；
編寫演算法，在乙個頭指標為head且帶頭結點的單鏈表中，刪除所有結點資料域值為x的結點。函式原型為：linklist delnode (linklist head，datatype x)
自學考試資料結構試題
課程 02331 請考生按規定用筆將所有試題的答案塗 寫在答題紙上。選擇題部分 注意事項 1.答題前，考生務必將自己的考試課程名稱 姓名 准考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規定的位置上。2.每小題選出答案後，用2b鉛筆把答題紙上對應題目的答案標號塗黑。如需改動，用橡皮擦乾淨後，再選塗其他答...
自學考試資料結構導論試題
全國2007年1月高等教育自學考試 資料結構導論試題 課程 02142 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1 關於棧和佇列的說法中正確的是 a 棧和佇列都是線性結構 b.棧是...
全國高等教育自學考試資料結構試題
全國2007年10月高等教育自學考試 資料結構試題 課程 02331 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.下面程式段的時間複雜度為 s 0 for i 1 i for j ...