全國2023年10月高等教育自學考試
資料結構試題
課程**：02331
一、單項選擇題（本大題共15小題，每小題2分，共30分）
在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其**填寫在題後的括號內。錯選、多選或未選均無分。
1.下面程式段的時間複雜度為( )
s=0；
for(i=1；i for(j=1；j s+=i*j；
a.o(1) b.o(logn)
c.o(n) d.o(n2)
2.已知指標p和q分別指向某單鏈表中第乙個結點和最後乙個結點。假設指標s指向
另乙個單鏈表中某個結點，則在s所指結點之後插入上述鍊錶應執行的語句為( )
a.q->next=s->next；s->next=p； b.s->next=p；q->next=s->next；
c.p->next=s->next；s->next=q； d.s->next=q；p->next=s->next；
3.在計算機內實現遞迴演算法時所需的輔助資料結構是( )
a.棧 b.佇列
c.樹 d.圖
4.假設以陣列a[m]存放迴圈佇列的元素。已知佇列的長度為length，指標rear指向隊
尾元素的下乙個儲存位置，則隊頭元素所在的儲存位置為( )
a.(rear-length+m+1)％m b.(rear-length+m)％m
c.(rear-length+m-1)％m d.(rear-length)％m
5.通常將鏈串的結點大小設定為大於1是為了( )
a.提高串匹配效率 b.提高儲存密度
c.便於插入操作 d.便於刪除操作
6.帶行表的三元組表是稀疏矩陣的一種( )
a.順序儲存結構 b.鏈式儲存結構
c.索引儲存結構 d.雜湊儲存結構
7.表頭和表尾均為空表的廣義表是( )
a.() b.(())
cd.(()，())
8.用二叉鍊錶表示具有n個結點的二叉樹時，值為空的指標域的個數為( )
a.n-1 b.n
c.n+l d.2n
9.為便於判別有向圖中是否存在迴路，可借助於( )
a.廣度優先搜尋演算法 b.最小生成樹演算法
c.最短路徑演算法 d.拓撲排序演算法
10.連通網的最小生成樹是其所有生成樹中( )
a.頂點集最小的生成樹 b.邊集最小的生成樹
c.頂點權值之和最小的生成樹 d.邊的權值之和最小的生成樹
11.按排序過程中依據的原則分類，快速排序屬於( )
a.插入類的排序方法 b.選擇類的排序方法
c.交換類的排序方法 d.歸併類的排序方法
12.下列關鍵字序列中，構成小根堆的是( )
a.b.
c.d.
13.在長度為32的有序表中進行二分查詢時，所需進行的關鍵字比較次數最多為( )
a.4 b.5
c.6 d.7
14.假設在構建雜湊表時，採用線性探測解決衝突。若連續插入的n個關鍵字都是同義
詞，則查詢其中最後插入的關鍵字時，所需進行的比較次數為( )
a.n-1 b.n
c.n+l d.n+2
15.雜湊檔案也稱為( )
a.順序檔案 b.索引檔案
c.直接訪問檔案 d.間接訪問檔案
二、填空題(本大題共10小題，每小題2分，共20分)
請在每小題的空格中填上正確答案。錯填、不填均無分。
16.資料的邏輯結構描述資料元素之間的與儲存方式無關。
17.在乙個長度為100的順序表中刪除第10個元素時，需移動個元素。
18.佇列的隊尾位置通常是隨著操作而變化的。
19.兩個空串聯接得到的串的長度為
20.設對稱矩陣a壓縮儲存在一維陣列b中，其中矩陣的第乙個元素a11儲存在b[0]，元素a52儲存在b[11]，則矩陣元素a36儲存在b中。
21.已知一棵哈夫曼樹含有60個葉子結點，
則該樹中共有個非葉子結點。
22.如圖所示的有向圖中含有
個強連通分量。
23.已知一組關鍵字為，其中每相鄰兩個關鍵字構成乙個有序子串行。對這些子串行進行一趟兩兩歸併的結果是
24.從空樹起，依次插入關鍵字1l，27，35，48，52，66和73構造所得的二叉排序樹，在等概率查詢的假設下，查詢成功時的平均查詢長度為
25.控制區間和控制區域是檔案的邏輯儲存單位。
三、解答題(本大題共4小題，每小題5分，共20分)
26.利用廣義表的head和tail操作，可從廣義表
l=((a，b)，(c，d))
中分解得到原子c，其操作表示式為
head(head(tail(l)))；
分別寫出從下列廣義表中分解得到b的操作表示式。
(1)l1=(a.，b，c，d)；
(2)l2=(((a)，(b)，(c)，(d)))。
(1)(2)27.畫出與如圖所示森林對應的二叉樹。
28.已知有向圖g的定義如下：
g=(v，e)
v=e=(1)畫出g的圖形；
(2)寫出g的全部拓撲序列。
(1)(2)29.已知3階b-樹如圖所示。
(1)畫出將關鍵字88插入之後的b-樹；
(2)畫出將關鍵字47和66依次插入之後的b-樹。
(1)(2)
四、演算法閱讀題(本大題共4小題，每小題5分，共20分)
30.假設某個不設頭指標的無頭結點單向迴圈鍊錶的長度大於1，s為指向鍊錶中某個結點的指標。演算法f 30的功能是，刪除並返回鍊錶中指標s所指結點的前驅。
請在空缺處填入合適的內容，使其成為完整的演算法。
typedef struct node *linklist；
datatype f 30(linklist s)
pre ->next= (3) ;
e=p->data;
free(p);
return e;
}(1)
(2)(3)
31.演算法f31的功能是清空帶頭結點的鏈佇列q。請在空缺處填入合適的內容，使其成為乙個完整的演算法。
typedef struct nodequeuenode；
typedef struct linkqueue；
void f 31(linkqueue*q)
(1)(2)
(3)32.假設採用動態儲存分配的順序串hstring作為串的儲存結構。該型別實現的串操作函式原型說明如下：
void strinit(hstring s)；／／置s為空串
int strlen(hstring s)；／／求串s的長度
void strcpy(hstring to，hstring from)；／／將串from複製到串to
void strcat(hstring to，hstring from)；／／將串from聯接到串to的末尾
int strcmp(hstring sl，hstring s2)；
／／比較串sl和s2的大小，當s1s2時，
／／返回值小於0，等於0或大於0
hstring substr(hstring s，int i，int m)；
／／返回串s中從第i(0≤i≤strlen(s)-m)個字元起長度為m的子串
閱讀下列演算法f 32，並回答問題：
(1)設串s=″abcdabcd″，t=″bcd″，v=″bcda″，寫出執行f 32(s，t，v)之後的s；
(2)簡述演算法f 32的功能。
void f 32 (hstring s, hstring t, hstring v)
} strcat(news,substr(s,pos,n-pos)) ;
strcpy(s,news)
}(1)
(2)33.假設以二叉鍊錶作為二叉樹的儲存結構，其型別定義如下：
typedef struct node {
char data;
全國高等教育自學考試資料結構
全國2012年10月高等教育自學考試 資料結構導論試題及答案 課程 02142 請考生按規定用筆將所有試題的答案塗 寫在答題紙上。選擇題部分 注意事項 1.答題前，考生務必將自己的考試課程名稱 姓名 准考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規定的位置上。2.每小題選出答案後，用2b鉛筆把答題紙上...
全國高等教育自學考試資料結構
全國2013年10月高等教育自學考試 資料結構試題 課程 02331 請考生按規定用筆將所有試題的答案塗 寫在答題紙上。選擇題部分 注意事項 1.答題前，考生務必將自己的考試課程名稱 姓名 准考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規定的位置上。2.每小題選出答案後，用2b鉛筆把答題紙上對應題目的...
全國高等教育自學考試資料結構試題
資料結構試題 課程 02331 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1 按值可否分解，資料型別通常可分為兩類，它們是 a 靜態型別和動態型別 b 原子型別和表型別 c 原子型別...