全國2023年10月高等教育自學考試
資料結構導論試題及答案
課程**：02142
請考生按規定用筆將所有試題的答案塗、寫在答題紙上。
選擇題部分
注意事項：
1.答題前，考生務必將自己的考試課程名稱、姓名、准考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規定的位置上。
2.每小題選出答案後，用2b鉛筆把答題紙上對應題目的答案標號塗黑。如需改動，用橡皮擦乾淨後，再選塗其他答案標號。不能答在試題卷上。
一、單項選擇題(本大題共15小題，每小題2分，共30分)
在每小題列出的四個備選項中只有乙個是符合題目要求的。錯選、多選或未選均無分。1.
下面幾種演算法時間複雜度階數中，值最大的是da.o(nlog2n)b.o(n2)c.
o(n)
d.o(2n)
2.即使輸入非法資料，演算法也能適當地做出反應或進行處理，不會產生預料不到的執行結果，這種演算法好壞的評價因素稱為ca.正確性b.易讀性c.健壯性
d.時空性
3.設順序表的長度為100，則在第40個元素之後插入乙個元素所需移動元素的個數為ba.40b.60c.61
d.100
4.設帶頭結點的單迴圈鍊錶的頭指標為head，則判斷該鍊錶是否為空的條件是aa.head->next==headb.
head->next==nullc.head!=null
d.head==null
5.在鏈棧的運算中，不需要．．．判斷棧是否為空的是ba.出棧b.進棧
c.取棧頂元素
d.求鏈棧的元素個數
6.乙個佇列的輸入序列是a，b，c，d，則該佇列的輸出序列是aa.a，b，c，db.b，c，d，ac.d，c，b，a
d.c，d，b，a
7.以行序為主序的二維陣列a［3］［5］中，第乙個元素a［0］［0］的儲存位址是100，每個元素佔2個儲存單元，
則a［1］［2］的儲存位址是ca.100b.108c.114
d.116
8.對任何一棵二叉樹t，若葉結點數為5個，則度為2的結點個數為aa.4b.5c.6
d.無法確定
9.m個葉結點的哈夫曼樹中，其結點總數為da.mb.2m+1c.2m
d.2m-110.二叉樹的中序遍歷序列中，結點p排在結點q之前的條件是aa.在二叉樹中p在q的左邊b.在二叉樹中p在q的右邊c.在二叉樹中p是q的祖先
d.在二叉樹中p是q的子孫
11.有10個頂點的無向完全圖的邊數是ba.11b.45c.55
d.90
12.在帶權有向圖中求兩個結點之間的最短路徑可以採用的演算法是aa.迪傑斯特拉（dijkstra）演算法b.克魯斯卡爾（kruskal）演算法c.普里姆（prim）演算法
d.深度優先搜尋（dfs）演算法
13.二分查詢（binarysearch）演算法的時間複雜度是da.o（n2）b.o（nlog2n）c.o（n）
d.o（log2n）
14.在一棵初始時為空的二叉樹中，依次插入鍵值序列50，72，43，85，75，20，38，45，65，60，構造對應的二叉排序樹以後，查詢元素60要進行的比較次數是ca.2b.
3c.4
d.515.快速排序屬於ba.插入排序b.交換排序c.選擇排序d.歸併排序
非選擇題部分
注意事項：
用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。
二、填空題(本大題共13小題，每小題2分，共26分)
猜你喜歡ic考勤系統學php
16.下面演算法程式段的時間複雜度為____。
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)for(k=1;k<=n;k++)x++；
17.所有儲存結點存放在乙個連續的儲存區里，利用結點在儲存器中的相對位置來表示資料元素之間的邏輯關係。這種儲存方式是___順序儲存方式___。
18.單鏈表中指標p指向結點a，若要刪除a之後的結點（存在且不釋放儲存空間），則需要修改指標的操作為p->next=__
___。
19.在帶有頭結點的單鏈表head中，首結點的指標為_head->next___。20.在棧結構中，允許插入和刪除的一端稱為__棧頂___。
21.c程式中，將對稱矩陣a［n］［n］的下三角元素壓縮儲存到n(n+1)/2個元素的一維陣列m中，設a［i］［j］（i≥j）存放在陣列m［k］中，則k的值（用i,j表示）為____。
22.具有64個結點的完全二叉樹的深度為___7__。
23.某二叉樹的先序遍歷序列為ajklmno，中序遍歷序列為jlkanmo，則根結點a的右子樹中的結點個數為_3___。24.
三個頂點v1,v2,v3的圖的鄰接矩陣為011101000
，則該圖中頂點v2的出度為__2__。
25.除第乙個頂點和最後乙個頂點相同外，其餘頂點不重複的迴路，稱為__簡單迴路或簡單環____。
26.在順序查詢、二分查詢、雜湊查詢和索引順序查詢四種查詢方法中，平均查詢長度與元素個數沒有關係的查詢方法是_雜湊查詢____。
27.堆排序演算法的時間複雜度為__
____。
28.如果要將序列建成堆，則只需把60與__18____相互交換。
三、應用題(本大題共5小題，每小題6分，共30分)
29.如題29圖所示，在棧的輸入端依次輸入元素a，b，c，試寫出在棧的輸出端可以得到的所有輸出序列，並給出每個序列的操作過程（用push（a）表示a進棧，pop(a)表示a出棧）。
答：30.將題30圖所示的一棵樹轉換為對應的二叉樹。
題30圖
答：31.已知含五個頂點a，b，c，d，e的連通帶權圖的鄰接矩陣如題31圖所示，試畫出它所表示的連通帶權圖及該連通帶權圖的最小生成樹。
答：32.題32圖所示二叉排序樹的各結點的值為1~10中的數，試標出各結點的數值。
33.設雜湊函式h（key）=keymod11(mod表示求餘運算)，給出鍵值序列為66,13,41,15,44,6,68,17,26,31,39,46,用鏈位址法解決衝突，試畫出相應的雜湊表，並計算在等概率情況下查詢成功時的平均查詢長度。
四、演算法設計題(本大題共2小題，每小題7分，共14分)34.帶頭結點的單鏈表的結點結構如下：
typedefstructnodenode,*linklist;
試編寫單鏈表的刪除運算演算法voiddeletelinklist(linklisthead，inti)
全國高等教育自學考試資料結構
全國2013年10月高等教育自學考試 資料結構試題 課程 02331 請考生按規定用筆將所有試題的答案塗 寫在答題紙上。選擇題部分 注意事項 1.答題前，考生務必將自己的考試課程名稱 姓名 准考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規定的位置上。2.每小題選出答案後，用2b鉛筆把答題紙上對應題目的...
全國高等教育自學考試資料結構試題
全國2007年10月高等教育自學考試 資料結構試題 課程 02331 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.下面程式段的時間複雜度為 s 0 for i 1 i for j ...
全國高等教育自學考試資料結構試題
資料結構試題 課程 02331 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1 按值可否分解，資料型別通常可分為兩類，它們是 a 靜態型別和動態型別 b 原子型別和表型別 c 原子型別...