2023年4月自考02331數(shù)據(jù)結(jié)構(gòu)試題及答案含解析

數(shù)據(jù)結(jié)構(gòu)年月真題

0233120234

1、【單選題】算法的空間復(fù)雜度表示的是

算法的可讀性

算法的難易程度

A:

執(zhí)行算法所耗費的時間

B:

執(zhí)行算法所耗費的存儲空間

C:

答D:案：D

解析：那么，又如何來評價這些算法的優(yōu)劣，進(jìn)而從中選擇好的算法呢？顯然，算法的

“正硒性”是首先要考慮的。所謂一個算法的正確性，是指對于一切合法的輸入數(shù)據(jù)，該

算法經(jīng)過有限時間的執(zhí)行都能得到正確的結(jié)果。此外，應(yīng)主要考慮如下幾點：（1）執(zhí)行

算法所耗費的時間，即時間復(fù)雜性。（2）執(zhí)行算法所耗費的存儲空間，主要是輔助空

間，即空間復(fù)雜性。（3）算法應(yīng)易于理解、易于編程，易于調(diào)試等，即可讀性和可操作

性。P37

2、【單選題】對需要頻繁插入和刪除元素的線性表，適合的存儲方式是

順序存儲

鏈?zhǔn)酱鎯?/p>

A:

索引存儲

B:

散列存儲

C:

答D:案：B

解析：鏈?zhǔn)酱鎯κ菍τ谛枰l繁插入和刪除元素的線性表來說比較適合的存儲方式。鏈?zhǔn)?/p>

存儲使用指針將元素按照順序連接起來，每個元素包含一個指向下一個元素的指針，這樣

在插入和刪除元素時只需要改變指針的指向，而不需要移動其他元素。相比之下，順序存

儲需要移動元素來騰出空間或填補(bǔ)空缺，效率較低。因此，對于需要頻繁插入和刪除元素

的線性表，鏈?zhǔn)酱鎯Ψ绞礁痈咝А?/p>

3、【單選題】線性表的兩個元素，如果邏輯上相鄰，則

順序存儲和鏈?zhǔn)酱鎯r都一定相鄰

順序存儲和鏈?zhǔn)酱鎯r都一定不相鄰

A:

順序存儲時一定相鄰，鏈?zhǔn)酱鎯r不一定相鄰

B:

順序存儲時不一定相鄰，鏈?zhǔn)酱鎯r一定相鄰

C:

答D:案：C

解析：對于順序存儲方式，線性表中邏輯上相鄰的兩個元素在物理存儲上也是相鄰的，即

它們在內(nèi)存中是連續(xù)存儲的。這是因為順序存儲方式將線性表的元素按照順序依次存放在

一塊連續(xù)的內(nèi)存空間中。而對于鏈?zhǔn)酱鎯Ψ绞?，線性表中邏輯上相鄰的兩個元素在物理存

儲上不一定相鄰，它們可以在內(nèi)存中的任意位置。鏈?zhǔn)酱鎯Ψ绞绞褂弥羔槍⒃剡B接起

來，每個元素包含一個指向下一個元素的指針，因此元素的物理存儲位置可以是離散的。

因此，順序存儲方式適合于需要頻繁訪問元素的場景，而鏈?zhǔn)酱鎯Ψ绞竭m合于需要頻繁插

入和刪除元素的場景。

4、【單選題】在頭指針為head的單鏈表中，判斷指針變量p指向終端結(jié)點的條件是

p->next->next==head

p->next==head

A:

p->next->next==NULL

B:

p->next==NULL

C:

答D:案：D

5、【單選題】若棧的進(jìn)棧序列為5,4,3,2,1，則經(jīng)過出入棧操作可能獲得的出棧序列是

4,5,1,3,2

3,5,4,2,1

A:

2,1,3,5,4

B:

4,3,5,1,2

C:

答D:案：D

6、【單選題】在三維數(shù)組a[7][4][10]中，每個數(shù)組元素占用2個存儲單元，所有數(shù)組元素

存放在一個連續(xù)的存儲空間中，則該數(shù)組需要的存儲單元總數(shù)是

560

280

A:

42

B:

21

C:

答D:案：A

7、【單選題】下列廣義表中，表長為3的是

((a,b,c))

(a,(b,c),(d,e,f))

A:

(a,b,c,(d,e,f)

B:

(a,(b,c,d,e,f)

C:

答D:案：B

8、【單選題】深度為k(k≥1)的滿二叉樹所包含的結(jié)點數(shù)是

k+1

2k

A:

2k-1

B:

2k+1

C:

答D:案：C

9、【單選題】下列選項中，能唯一確定一棵二叉樹的兩個遍歷序列是

前序遍歷序列和層次遍歷序列

后序遍歷序列和層次遍歷序列

A:

前序遍歷序列和中序遍歷序列

B:

前序遍歷序列和后序遍歷序列

C:

答D:案：C

10、【單選題】下列關(guān)于連通的無向帶權(quán)圖G的敘述中，正確的是

圖G的生成樹至少含有一個回路

圖G的最小生成樹總是唯一的

A:

圖G的鄰接矩陣不一定是對稱矩陣

B:

圖G的生成樹的邊數(shù)等于頂點數(shù)減1

C:

答D:案：D

11、【單選題】下列排序方法中，不穩(wěn)定的是

堆排序

冒泡排序

A:

歸并排序

B:

直接插入排序

C:

答D:案：A

12、【單選題】對圖進(jìn)行拓?fù)渑判?，可以得到的拓?fù)湫蛄惺?/p>

BADCEB

BACDEA

A:

ACBDED>E

B:

ABDCE

C:

答D:案：D

13、【單選題】下列選項中，能使用二分查找算法的是

順序存儲的線性表(4,16,5,6,55,89,34,25)

順序存儲的線性表(4,5,6,16,25,34,55,89)

A:

散列存儲的線性表(4,5,6,16,25,34,55,89)

B:

鏈?zhǔn)酱鎯Φ木€性表(4,5,6,16,25,34,55,89)

C:

答D:案：B

14、【單選題】在下列查找算法中，平均查找長度與數(shù)據(jù)規(guī)模基本無關(guān)的是

順序查找

散列查找

A:

二分查找

B:

B樹中的查找

C:

答D:案：B

15、【單選題】假設(shè)散列表長m=10,散列函數(shù)H(key)=key%9。表中已有3個結(jié)點：

H(23)=5,H(31)=4,H(17)=8,其余位置為空?，F(xiàn)采用線性探查法處理沖突，依次存儲關(guān)鍵字4

和36時需要探查的次數(shù)分別是

1和1

2和1

A:

3和1

B:

1和3

C:

答D:案：C

16、【問答題】設(shè)循環(huán)隊列保存在數(shù)組Q[N]中，front和rear分別為隊頭和隊尾指針，初

始時front=rear=0,約定指針rear指向的單元始終為空，請用C語言分別描述下列操作：(1)

將數(shù)據(jù)元素x入隊。(2)將隊首元素出隊，并保存到變量myData中。(3)計算隊列中當(dāng)前數(shù)據(jù)

元素的個數(shù)，并保存到變量DLenth中。

答案：(1)數(shù)據(jù)元素X入隊:if((rear+1)%N==front)printf("Queueoverflow")

else{Q[rear]=x;rear=(rear+1)%N;}(2)隊首元素出隊并保存到變量myData.中:

if(rear==front)printf(“Queueempty”)else{myData=Q[front];

front=(front+1)%N;}(3)當(dāng)前隊列長度DLenth=(N+rear-front)%N(或

DLenth=(rear>=front)?rear-front:N+rear-front)

17、【問答題】已知稀疏矩陣M如下，采用三元組表存儲。

(1)請給出三元組表的類型定義。

(2)寫出矩陣M按列優(yōu)先存儲的三元組表。

答案：

18、【問答題】已知待排序記錄的關(guān)鍵字序列為(45,37,75,18,53,31,48,37)，請回答下列

問題。(1)畫出其對應(yīng)的完全二叉樹T。(2)將T調(diào)整為對應(yīng)的大根堆，給出大根堆序列。

答案：

19、【問答題】將百分制成績分成五個等級，已知成績的對應(yīng)關(guān)系及分布情況如下表所

示。請回答下列問題。

(1)根據(jù)哈夫曼樹的基本原理，畫出成績評定判定樹T。

(2)求樹T的WPL。

答案：

20、【問答題】單鏈表類型定義如下：typedefstructnode{DataTypedata;struct

node*next;}LinkNode;typedefLinkNode*Linklist;函數(shù)f30的功能是刪除帶頭結(jié)

點的單鏈表中data值為x的全部結(jié)點，請在空白處填上適當(dāng)內(nèi)容將算法補(bǔ)充完整。void

f30(Linklisthead,DataTypex){LinkNode*p,*q,*s;p=head;q=（1）;

while(q!=NULL)if(（2）){s=q;q=q->next;p->next=q;free(s);}else{p=q;

q=（3）;}}

答案：(1)p->next(2)q->data==x(3)q->next

21、【問答題】二叉樹的二叉鏈表類型定義如下：

#definecharDataType

typedefstructnode{

DataTypedata;

structnode*lchild,*rchild;

}BinTNode;

typedefBinTNode*BinTree;

閱讀下列函數(shù)并回答問題。

voidf31(BinTreebt){

if(bt!=NULL){

f31(bt->rchild);

f31(bt->lchild);

printf("%c",bt->data);

}

}

(1)給出如圖所示的二叉樹T,寫出執(zhí)行函數(shù)f31(T)后得到的輸出序列。

(2)對于二叉樹中的任意結(jié)點N及它的左子樹L和它的右子樹R,f31的遍歷次序是什么？

答案：(1)FDECBA(2)RLN次序(或先序遍歷的逆)

22、【問答題】閱讀下列函數(shù)并回答問題。voidf32(intr[],intN){inti,j,temp;

for(i=1;i{temp=r[i];j=i-1;while(temp{r[j+1]=r[j];j=j-1;}

r[j+1]=temp;}}(1)若t[8]=(3,12,5,78,6,9,4,35),寫出執(zhí)行函數(shù)f32(t,8)后數(shù)組t

中的各元素。(2)函數(shù)f32的功能是什么？

答案：(1)3,4,5,6,9,12,35,78(2)直接插入排序

23、【問答題】函數(shù)f33實現(xiàn)二分查找，請回答下列問題。(1)在空白處補(bǔ)充適當(dāng)內(nèi)容，

使函數(shù)功能完整。(2)如果待查序列R為(4,5,6,16,25,34,55,89)，分別給出執(zhí)行

f33(R,9,8)和f33(R,34,8)的返回值。intf33(SeqListR[],KeyTypek,intn){int

low=0,mid,high=n-1;while(low<=high){mid=(low+high)/2;if(R[mid].key==k)

returnmid;if(（1）)high=mid-1elselow=mid+1;}return-1;}

答案：(1)R[mid].key>k(2)-1和5

24、【問答題】二叉樹的二叉鏈表類型定義如下：typedefstructnode{intdata;

structnode*lchild,*rchild;}BinNode;typedefBinNode*BinTree;編寫函數(shù)

f34(BinTreeBt),返回二叉樹Bt中數(shù)據(jù)元素的最大值。函數(shù)的原型為：intf34(BinTree

Bt)。

答案：#defineMin-65525intf34(BinTreeBT){intlvalue,rvalue,maxvalue;

if(BT==NULL)returnMin;if(BT!=NULL){lvalue=f34(BT->lchild);

rvalue=f34(BT->rchild);maxvalue=(lvalue>rvalue)?lvalue:rvalue;

maxvalue=(maxvalue>BT->data)?maxvalue:BT->data;returnmaxvalue;}

25、【填空題】順序存儲和鏈接存儲方法中，無需連續(xù)分配存儲空間的是（）。

答案：鏈接存儲

26、【填空題】設(shè)順序表首元素的存儲地址是4000，每個數(shù)據(jù)元素占