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

數(shù)據(jù)結構年月真題

0233120234

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

算法的可讀性

算法的難易程度

A:

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

B:

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

C:

答D:案：D

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

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

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

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

間，即空間復雜性。（3）算法應易于理解、易于編程，易于調試等，即可讀性和可操作

性。P37

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

順序存儲

鏈式存儲

A:

索引存儲

B:

散列存儲

C:

答D:案：B

解析：鏈式存儲是對于需要頻繁插入和刪除元素的線性表來說比較適合的存儲方式。鏈式

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

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

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

的線性表，鏈式存儲方式更加高效。

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

順序存儲和鏈式存儲時都一定相鄰

順序存儲和鏈式存儲時都一定不相鄰

A:

順序存儲時一定相鄰，鏈式存儲時不一定相鄰

B:

順序存儲時不一定相鄰，鏈式存儲時一定相鄰

C:

答D:案：C

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

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

一塊連續(xù)的內存空間中。而對于鏈式存儲方式，線性表中邏輯上相鄰的兩個元素在物理存

儲上不一定相鄰，它們可以在內存中的任意位置。鏈式存儲方式使用指針將元素連接起

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

因此，順序存儲方式適合于需要頻繁訪問元素的場景，而鏈式存儲方式適合于需要頻繁插

入和刪除元素的場景。

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

p->next->next==head

p->next==head

A:

p->next->next==NULL

B:

p->next==NULL

C:

答D:案：D

5、【單選題】若棧的進棧序列為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)的滿二叉樹所包含的結點數(shù)是

k+1

2k

A:

2k-1

B:

2k+1

C:

答D:案：C

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

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

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

A:

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

B:

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

C:

答D:案：C

10、【單選題】下列關于連通的無向帶權圖G的敘述中，正確的是

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

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

A:

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

B:

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

C:

答D:案：D

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

堆排序

冒泡排序

A:

歸并排序

B:

直接插入排序

C:

答D:案：A

12、【單選題】對圖進行拓撲排序，可以得到的拓撲序列是

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:

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

C:

答D:案：B

14、【單選題】在下列查找算法中，平均查找長度與數(shù)據(jù)規(guī)?；緹o關的是

順序查找

散列查找

A:

二分查找

B:

B樹中的查找

C:

答D:案：B

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

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

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

1和1

2和1

A:

3和1

B:

1和3

C:

答D:案：C

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

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

將數(shù)據(jù)元素x入隊。(2)將隊首元素出隊，并保存到變量myData中。(3)計算隊列中當前數(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)當前隊列長度DLenth=(N+rear-front)%N(或

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

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

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

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

答案：

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

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

答案：

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

示。請回答下列問題。

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

(2)求樹T的WPL。

答案：

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

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

點的單鏈表中data值為x的全部結點，請在空白處填上適當內容將算法補充完整。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)對于二叉樹中的任意結點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)在空白處補充適當內容，

使函數(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、【填空題】設順序表首元素的存儲地址是4000，每個數(shù)據(jù)元素占