全國2023年1月高等教育自學考試
資料結構導論試題
課程**：02142
一、單項選擇題(本大題共15小題，每小題2分，共30分)
在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其**填寫在題後的括號內。錯選、多選或未選均無分。
1．關於棧和佇列的說法中正確的是（ ）
a．棧和佇列都是線性結構
b.棧是線性結構，佇列不是線性結構
c.棧不是線性結構，佇列是線性結構
d.棧和佇列都不是線性結構
2．關於儲存相同資料元素的說法中正確的是（ ）
a．順序儲存比鏈式儲存少佔空間
b.順序儲存比鏈式儲存多佔空間
c.順序儲存和鏈式儲存都要求占用整塊儲存空間
d.鏈式儲存比順序儲存難於擴充空間
3．從邏輯關係來看，資料元素的直接前驅為0個或1個的資料結構只能是（ ）
a．線性結構 b.樹形結構
c.線性結構和樹型結構 d.線性結構和圖狀結構
4．已知乙個單鏈表中，指標q指向指標p的前趨結點，若在指標q所指結點和指標p所指結點之間插入指標s所指結點，則需執行（ ）
a．q→next=s；p→next=s；
5．在長度為n的線性表中刪除乙個指標p所指結點的時間複雜度是（ ）
a．o(n)
6．設乙個棧的輸入序列是a，b，c，d，則所得到的輸出序列（輸入過程中允許出棧）不可能出現的是（ ）
a．a，b，c，d
7．關於串的敘述中，正確的是（ ）
a．空串是只含有零個字元的串
b.空串是只含有空格字元的串
c.空串是含有零個字元或含有空格字元的串
d.串是含有乙個或多個字元的有窮序列
8．在具有m個單元的迴圈佇列中，隊頭指標為front，隊尾指標為rear，則隊滿的條件是（ ）
a．front==rear b.(front+1)%m==rear
d.(rear+1)%m==front
9．設有二維陣列a［n］［n］表示如下：， 則a［i］［i］（0≤i≤n-1）的值為（ ）
a．i*(i-1)/2
c.(i+2)*(i+1)/2
10．高度為h的完全二叉樹中，結點數最多為（ ）
a．2h-1 b.2h+1
c.2h-1 d.2h
11．由m棵結點數為n的樹組成的森林，將其轉化為一棵二叉樹，則該二叉樹中根結點的右子樹上具有的結點個數是（ ）
a．mn
12．在乙個具有n個頂點的無向圖中，每個頂點度的最大值為（ ）
a．nd.2(n-1)
13．關於無向圖的鄰接矩陣的說法中正確的是（ ）
a．矩陣中非全零元素的行數等於圖中的頂點數
b.第i行上與第i列上非零元素總和等於頂點vi的度數
c.矩陣中的非零元素個數等於圖的邊數
d.第i行上非零元素個數和第i列上非零元素個數一定相等
14．設一組記錄的關鍵字key值為，雜湊函式為h(key)=key mod 13，則它的開雜湊表中雜湊位址為1的鏈中的結點個數是（ ）
a．1 b.2
ｃ．3 d.4
15．設有一組初始關鍵字值序列為（49，81，55，36，44，88），則利用快速排序的方法，以第乙個關鍵字值為基準得到的一次劃分為（ ）
a．36，44，49，55，81，88 b.44，36，49，55，81，88
c.44，36，49，81，55，88 d.44，36，49，55，88，81
二、填空題(本大題共13小題，每小題2分，共26分)
請在每小題的空格中填上正確答案。錯填、不填均無分。
16．在資料結構中，各個結點按邏輯關係互相纏繞，任意兩個結點可以鄰接的結構稱為_______。
17．每個儲存結點只含乙個資料元素，所有儲存結點連續存放。此外增設乙個索引表，索引表中的索引指示各儲存結點的儲存位置或位置區間端點。按這種方式組織起來的儲存結構稱為_______。
18．在順序表上讀表元演算法的時間複雜度為_______。
19．雙鏈表中前驅指標為prior，後繼指標為next，在指標p所指結點前插入指標s所指的結點，需執行下列語句：
s→next=p;s→prior=p→prior;p→prior=s;_______;
20．設陣列a［0..8］［0..8］的起始元素位置為a，每個元素佔2 l個儲存單元，按行序為主序儲存。
若元素a［i］［j］的儲存位置為a+66 l，則元素a［j］［i］的儲存位置為_______。
21．有4個結點且深度為4的二叉樹的形態共有_______種。
22．某二叉樹的先根遍歷序列為ijklmno，中根遍歷序列為jlkinmo，則該二叉樹中根結點的右孩子是_______。
23．第乙個頂點和最後乙個頂點相同的路徑稱為迴路或者環，除第乙個頂點和最後乙個頂點外，其餘頂點都不重複的迴路，稱為_______。
24．乙個具有10個頂點的完全無向圖中有_______條邊。
25．一棵平衡二叉樹中任一結點的平衡因子只可能是_______。
26．二分查詢的時間複雜度為_______。
27．二路歸併排序演算法的時間複雜度為_______。
28．檔案的基本訪問單位是_______。
三、應用題(本大題共5小題，每小題6分，共30分)
29．有一字串序列為5*-x-y/x+2，利用棧的運算將其輸出結果變為5x-*yx+/-2，試寫出該操作的入棧和出棧過程（採用push(a)表示a入棧，pop(a)表示a出棧）。
30．某二叉樹的先根遍歷序列為abijcdfghe，中根遍歷序列為ijbadgfhce，試畫出該二叉樹，並寫出它的後序遍歷序列。
31．用氣泡排序演算法對資料序列（49，38，65，97，76，134，27，49）進行排序，寫出整個氣泡排序的每一趟過程。
32．題32圖所示二叉樹是否為平衡二叉樹？若是，說明理由；若不是，將其轉換為平衡二叉樹。
題32圖
33．已知連通網的鄰接矩陣a=， 試畫出它所表示的連通網並畫出該連通網的最小生成樹。
四、演算法設計題(本大題共2小題，每小題7分，共14分)
34．設單鏈表的結點結構如下：
struct node
試編寫乙個函式int count(struct node *head,datatype x)統計單鏈表中資料域為x的結點個數。
35．試寫出直接插入排序演算法。
全國2023年10月高等教育自學考試
資料結構導論試題
課程**：02142
一、單項選擇題(本大題共15小題，每小題2分，共30分)
在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其**填寫在題後的括號內。錯選、多選或未選均無分。
1.在資料結構中，從邏輯上可以把資料結構分成( )
a.線性結構和非線性結構 b.緊湊結構和非緊湊結構
c.動態結構和靜態結構 d.內部結構和外部結構
for（j=0；ja［i］［j］=i*j；
上面演算法的時間複雜度為( )
3.設順序表有9個元素，則在第3個元素前插入乙個元素所需移動元素的個數為( )
a.5 b.6
c.7 d.9
4.設p為指向雙向迴圈鍊錶中某個結點的指標，p所指向的結點的兩個鏈域分別用p→llink和p→rlink表示，則同樣表示p指標所指向結點的表示式是( )
5.乙個向量第乙個元素的儲存位址是100，每個元素的長度為2，則第5個元素的儲存位址是( )
a. 110 b. 108
c. 100 d. 120
6.設有乙個棧，按a、b、c、d的順序進棧，則可能為出棧序列的是( )
7.在乙個具有n個單元的順序棧中，假定以位址低端（即0單元）作為棧底，以top為棧頂指標，則當做出棧處理時，top變化為( )
不變8.除根結點外，樹上每個結點( )
a.可有任意多個孩子、乙個雙親 b.可有任意多個孩子、任意多個雙親
c.可有乙個孩子、任意多個雙親 d.只有乙個孩子、乙個雙親
9.題9圖中樹的度為( )
a.2b.3c.5
d.8題9圖
10.有4個頂點的無向完全圖的邊數為( )
a.6 b.12
c.16 d.20
11.設圖的鄰接矩陣為，則該圖為( )
a.有向圖 b.無向圖
c.強連通圖 d.完全圖
12.在對查詢表的查詢過程中，若被查詢的資料元素不存在，則把該資料元素插入到集合中。這種方式主要適合於( )
a.靜態查詢表 b.動態查詢表
c.靜態查詢表與動態查詢表 d.靜態查詢表或動態查詢表
13.用雜湊函式求元素在雜湊表中的儲存位置時，可能會出現不同的關鍵字得到相同雜湊函式值的衝突現象。可用於解決上述問題的是( )
a.線性探測法 b.除留餘數法
c.平方取中法 d.摺疊法
14.排序演算法中，第一趟排序後，任一元素都不能確定其最終位置的演算法是( )
a.選擇排序 b.插入排序
c.氣泡排序 d.快速排序
15.在排序方法中，從未排序序列中挑選元素，並將其依次放入已排序序列（初始時為空）的一端的方法，稱為( )
a.希爾排序 b.歸併排序
c.插入排序 d.選擇排序
二、填空題(本大題共13小題，每小題2分，共26分)
請在每小題的空格中填上正確答案。錯填、不填均無分。
自學考試資料結構試題
課程 02331 請考生按規定用筆將所有試題的答案塗 寫在答題紙上。選擇題部分 注意事項 1.答題前，考生務必將自己的考試課程名稱 姓名 准考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規定的位置上。2.每小題選出答案後，用2b鉛筆把答題紙上對應題目的答案標號塗黑。如需改動，用橡皮擦乾淨後，再選塗其他答...
全國高等教育自學考試資料結構導論試題
全國2003年10月高等教育自學考試資料結構導論試題 課程 02142 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在 題後的括號內。錯選 多選或未選均無分。1 下列說法正確的是 a 資料是資料元素的基本單位 b 資料元素是...
全國自學考試資料結構試題
課程 02331 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.每個結點有且僅有乙個直接前趨和多個 或無 直接後繼 第乙個結點除外 的資料結構稱為 a.樹狀結構 b.網狀結構 c.線...