資料結構試題
課程**：02331
一、單項選擇題（本大題共15小題，每小題2分，共30分）
在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其**填寫在題後的括號內。錯選、多選或未選均無分。
1．按值可否分解，資料型別通常可分為兩類，它們是（ ）
a．靜態型別和動態型別 b．原子型別和表型別
c．原子型別和結構型別 d．陣列型別和指標型別
2．對於三個函式f(n)=2008n3+8n2+96000，g(n)=8n3+8n+2008和h(n)=8888nlogn+3n2，下列陳述中不成立的是（ ）
a．f(n)是0(g(n)) b．g(n)是0(f(n))
c．h(n)是0(nlogn) d．h(n)是0(n2)
3．指標p、q和r依次指向某迴圈鍊錶中三個相鄰的結點，交換結點*q和結點*r在表中次序的程式段是（ ）
a．p->next=r； q->next=r->next； r->next=q；
b．p->next=r； r->next=q； q->next=r->next；
c．r->next=q； q->next=r->next； p->next=r；
d．r->next=q； p->next=r； q->next=r->next；
4．若進棧次序為a，b，c，且進棧和出棧可以穿插進行，則可能出現的含3個元素的出棧序列個數是（ ）
a．3 b．5
c．6 d．7
5．假設以陣列a［n］存放迴圈佇列的元素，其頭指標front指向隊頭元素的前乙個位置、尾指標rear指向隊尾元素所在的儲存位置，則在少用乙個元素空間的前提下，佇列滿的判定條件為（ ）
a．rear= =front b．(front+1)％n= =rear
c．rear+1= =front d．(rear+1)％n= =front
6．串的操作函式str定義為：
int str(char*s)
則str(″abcde″)的返回值是（ ）
a．3 b．4
c．5 d．6
7．二維陣列a［10］［6］採用行優先的儲存方法，若每個元素佔4個儲存單元，已知元素a［3］［4］的儲存位址為1000，則元素a［4］［3］的儲存位址為（ ）
a．1020 b．1024
c．1036 d．1240
8．對廣義表l= (a，())執行操作tail(l)的結果是（ ）
a．() b．(())
c．a d．(a)
9．已知二叉樹的中序序列和後序序列均為abcdef，則該二叉樹的先序序列為（ ）
a．fedcba b．abcdef
c．fdecba d．fbdcea
10．已知森林f=，各棵樹ti(i=1，2，3，4，5)中所含結點的個數分別為7，3，5，l，2，則與f對應的二叉樹的右子樹中的結點個數為（ ）
a．2 b．3
c．8 d．11
11．若非連通無向圖g含有21條邊，則g的頂點個數至少為（ ）
a．7 b．8
c．21 d．22
12．如圖所示的有向圖的拓撲序列是（ ）
a．c，d，b，a，e
b．c，a，d，b，e
c．c，d，e，a，b
d．c，a，b，d，e
13．對關鍵字序列(6，1，4，3，7，2，8，5)進行快速排序時，以第1個元素為基準的一次劃分的結果為（ ）
a．(5，1，4，3，6，2，8，7) b．(5，1，4，3，2，6，7，8)
c．(5，1，4，3，2，6，8，7) d．(8，7，6，5，4，3，2，1)
14．分塊查詢方法將表分為多塊，並要求（ ）
a．塊內有序 b．塊間有序
c．各塊等長 d．鏈式儲存
15．便於進行布林查詢的檔案組織方式是（ ）
a．順序檔案 b．索引檔案
c．雜湊檔案 d．多關鍵字檔案
二、填空題（本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分）
請在每個空格中填上正確答案。錯填、不填均無分。
16．資料的鏈式儲存結構的特點是借助________表示資料元素之間的邏輯關係。
17．如果需要對線性表頻繁進行________或________操作，則不宜採用順序儲存結構。
18．如圖所示，可以利用乙個向量空間同時實現兩個型別相同的棧。其中棧1為空的條件是top1=0，棧2為空的條件是top2=n-1，則「棧滿」的判定條件是________。
19．靜態儲存分配的順序串在進行插入、置換和________等操作時可能發生越界。
20．廣義表l=（a，（b，( )））的深度為________。
21．任意一棵完全二叉樹中，度為1的結點數最多為________。
22．求最小生成樹的克魯斯卡爾(kruskal)演算法耗用的時間與圖中________的數目正相關。
23．在5階b-樹中，每個結點至多含4個關鍵字，除根結點之外，其他結點至少含________個關鍵字。
24．若序列中關鍵字相同的記錄在排序前後的相對次序不變，則稱該排序演算法是________的。
25．常用的索引順序檔案是________檔案和________檔案。
三、解答題(本大題共4小題，每小題5分，共20分)
26．如圖所示，在n×n矩陣a中，所有下標值滿足關係式i+j＜n+l的元素aij的值均為0，現將a中其它元素按行優先順序依次儲存到長度為n(n+1)/2的一維陣列sa中，其中元素a1，n儲存在sa［0］。
(1)設n=10，元素a4，9儲存在sa［p］，寫出下標p的值；
(2)設元素ai，j儲存在sa［k］中，寫出由i,j和n計算k的一般公式。
27．由字符集及其在電文中出現的頻度構建的哈夫曼樹如圖所示。已知某段電文的哈夫曼編碼為111000010100，請根據該哈夫曼樹進行解碼，寫出原來的電文。
28．已知無向圖g的鄰接表如圖所示，
(1)畫出該無向圖；
(2)畫出該圖的廣度優先生成森林。
29．對序列(48，37，63，96，22，31，50，55，11)進行公升序的堆排序，寫出構建的初始(大根)堆及前兩趟重建堆之後的序列狀態。
初始堆：
第1趟：
第2趟：
四、演算法閱讀題(本大題共4小題，每小題5分，共20分)
30．閱讀下列演算法，並回答問題：
(1)無向圖g如圖所示，寫出演算法
f30(&g)的返回值；
(2)簡述演算法f30的功能。
#define maxnum 20
int visited[maxnum]；
void dfs(graph *g，int i)；
/*從頂點vi出發進行深度優先搜尋，訪問頂點vj時置visited[j]為1*/
int f30(graph *g)
return k；
}31．假設學生成績按學號增序儲存在帶頭結點的單鏈表中，型別定義如下：
typedef struct node lnode， *linklist；
閱讀演算法f31，並回答問題：
(1)設結點結構為，成績鍊錶a和b如圖所示，畫出執行演算法
f31(a，b)後a所指的鍊錶；
(2)簡述演算法f31的功能。
void f31(linklist a, linklist b)}}
32．閱讀下列演算法，並回答問題：
(1)設串s=「oneworldonedream」，t=＂one＂，pos是一維整型陣列，寫出演算法
f32(s，t，pos)執行之後得到的返回值和pos中的值；
(2)簡述演算法f32的功能。
int strlen(char*s)； /*返回串s的長度*/
int index(char*st，char*t)；
／*若串t在串st中出現，則返回在串st中首次出現的下標值，否則返回-1*/
int f32(char*s, char*t, int pos［］)
}while(i+1t<=1s && j >=0);
return k;
}33．二叉排序樹的儲存結構定義為以下型別：
typedef int keytype;
typedef struct node bstnode, *bstree；
閱讀演算法f33，並回答問題：
(1)對如圖所示的二叉排序樹t，寫出f33(t，8)
返回的指標所指結點的關鍵字；
(2)在哪些情況下演算法f33返回空指標?
(3)簡述演算法f33的功能。
bstnode *f33(bstree t, keytype x)
{ bstnode *p;
全國高等教育自學考試資料結構
全國2012年10月高等教育自學考試 資料結構導論試題及答案 課程 02142 請考生按規定用筆將所有試題的答案塗 寫在答題紙上。選擇題部分 注意事項 1.答題前，考生務必將自己的考試課程名稱 姓名 准考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規定的位置上。2.每小題選出答案後，用2b鉛筆把答題紙上...
全國高等教育自學考試資料結構
全國2013年10月高等教育自學考試 資料結構試題 課程 02331 請考生按規定用筆將所有試題的答案塗 寫在答題紙上。選擇題部分 注意事項 1.答題前，考生務必將自己的考試課程名稱 姓名 准考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規定的位置上。2.每小題選出答案後，用2b鉛筆把答題紙上對應題目的...
全國高等教育自學考試資料結構試題
全國2007年10月高等教育自學考試 資料結構試題 課程 02331 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.下面程式段的時間複雜度為 s 0 for i 1 i for j ...