普通高等院校十四五應(yīng)用型人才培養(yǎng)系列教材

“”

數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)驗(yàn)指導(dǎo)

周瑞英張穎章昊主編

◎

內(nèi)容簡介

本書是數(shù)據(jù)結(jié)構(gòu)語言版張穎等主編中國鐵道出版社有限公司出版的配套教

《(C)》(,)

材主要包括習(xí)題解析與實(shí)驗(yàn)指導(dǎo)兩篇其中習(xí)題解析篇選取了近年數(shù)據(jù)結(jié)構(gòu)的考研真題

,,10

和對(duì)應(yīng)主教材的章節(jié)習(xí)題實(shí)驗(yàn)指導(dǎo)篇?jiǎng)t是針對(duì)重要知識(shí)點(diǎn)設(shè)置上機(jī)實(shí)驗(yàn)題目及其解析主要

;,

包括語言預(yù)備知識(shí)結(jié)構(gòu)體指針函數(shù)算法效率分析與對(duì)比基于順序表單鏈表的學(xué)生

C(、、)、、/

成績管理基于循環(huán)鏈表的約瑟夫環(huán)問題基于棧的后綴算術(shù)表達(dá)式求值基于鏈隊(duì)列的舞伴

、、、

配對(duì)問題以及樹圖排序算法等內(nèi)容本書內(nèi)容豐富講解深入淺出引導(dǎo)讀者系統(tǒng)地掌握

,、、。,,

數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識(shí)精選的習(xí)題具有典型性幫助讀者舉一反三開拓解題思路最后通過上

;,,;

機(jī)實(shí)驗(yàn)及其解析提升編程的思維方法和能力

,、。

本書適合作為普通高等院校數(shù)據(jù)結(jié)構(gòu)課程的上機(jī)實(shí)驗(yàn)指導(dǎo)教材也可作為編程愛好者

“”,

的自學(xué)用書

。

圖書在版編目CIP數(shù)據(jù)

()

數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)驗(yàn)指導(dǎo)周瑞英張穎章昊

/,,

主編北京中國鐵道出版社有限公司

.—:,2022.4

普通高等院校十四五應(yīng)用型人才培養(yǎng)系列教材

“”

ISBN978-7-113-28948-5

數(shù)周張章數(shù)據(jù)

Ⅰ.①…Ⅱ.①…②…③…Ⅲ.①

結(jié)構(gòu)高等學(xué)校教學(xué)參考資料

--Ⅳ.①TP311.12

中國版本圖書館數(shù)據(jù)核字第號(hào)

CIP(2022)039839

書名:數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)驗(yàn)指導(dǎo)

作者:周瑞英張穎章昊

策劃:魏娜編輯部電話:

(010)63549508

責(zé)任編輯:陸慧萍徐盼欣

封面設(shè)計(jì):劉穎

責(zé)任校對(duì):孫玫

責(zé)任印制:樊啟鵬

出版發(fā)行:中國鐵道出版社有限公司北京市西城區(qū)右安門西街號(hào)

(100054,8)

印刷:三河市國英印務(wù)有限公司

版次:年月第版年月第次印刷

202241202241

開本:印張:字?jǐn)?shù):千

787mm×1092mm1/1617.25429

書號(hào):

ISBN978-7-113-28948-5

定價(jià):元

46.00

版權(quán)所有侵權(quán)必究

凡購買鐵道版圖書如有印制質(zhì)量問題請(qǐng)與本社讀者服務(wù)部聯(lián)系調(diào)換電話

,,。:(010)51873174

打擊盜版舉報(bào)電話

:(010)63549461

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)及相關(guān)專業(yè)的核心基礎(chǔ)課程是一門理論與實(shí)踐并

“”,

重的課程該課程理論性較強(qiáng)原理和算法比較抽象對(duì)于具有程序設(shè)計(jì)基礎(chǔ)的學(xué)生來

。,,

說做習(xí)題尤其做算法設(shè)計(jì)題時(shí)往往困難重重有時(shí)甚至無從下手這在編者多年的教學(xué)

,,,

中感受頗深本書的編寫宗旨是力圖通過大量的典型習(xí)題解析和實(shí)驗(yàn)指導(dǎo)幫助學(xué)生快

。,

速掌握并靈活運(yùn)用數(shù)據(jù)結(jié)構(gòu)的基本理論和算法輔助教師講授課程和指導(dǎo)學(xué)生實(shí)踐

,。

本書既是數(shù)據(jù)結(jié)構(gòu)語言版的配套教材同時(shí)又自成體系可作為參加自學(xué)考

《(C)》,,

試研究生入學(xué)考試計(jì)算機(jī)國家等級(jí)考試的復(fù)習(xí)參考書

、、。

本書根據(jù)數(shù)據(jù)結(jié)構(gòu)課程的實(shí)際教學(xué)情況在長期的教學(xué)實(shí)踐中整理和設(shè)計(jì)了大量

“”,

的習(xí)題和實(shí)驗(yàn)本書由兩篇組成第篇是習(xí)題解析全面覆蓋了數(shù)據(jù)結(jié)構(gòu)知識(shí)體系的

。,1,

各知識(shí)點(diǎn)共分章每章按照兩個(gè)模塊編寫習(xí)題答案及解析第篇是實(shí)驗(yàn)指導(dǎo)包

,9,:、;2,

含個(gè)實(shí)驗(yàn)題目每個(gè)實(shí)驗(yàn)按照實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)要求實(shí)驗(yàn)分析代碼實(shí)現(xiàn)實(shí)驗(yàn)結(jié)果編

22,、、、、

寫代碼實(shí)現(xiàn)全部采用語言另外根據(jù)多年的教學(xué)經(jīng)驗(yàn)鑒于學(xué)生普遍缺少動(dòng)態(tài)數(shù)組

,C。,,

等知識(shí)故特別增加了語言預(yù)備知識(shí)實(shí)驗(yàn)

,C。

習(xí)題答案及解析和實(shí)驗(yàn)代碼實(shí)現(xiàn)只供學(xué)習(xí)者作為參考切不可完全依賴于它如果

,。

在未做習(xí)題之前就先看答案那就與編者的初衷背道而馳了為此編者特將答案及解

,。,

析與題目相分離希望學(xué)習(xí)者在深入思考后再查看答案解析另外各實(shí)驗(yàn)題目的算法

,。,

實(shí)現(xiàn)有多種本書提供的實(shí)驗(yàn)代碼實(shí)現(xiàn)并不一定是唯一的學(xué)習(xí)者可以針對(duì)實(shí)驗(yàn)要求多

,。

加思考設(shè)計(jì)出不同的程序并加以比較和分析

,,。

本書得到全國高等院校計(jì)算機(jī)基礎(chǔ)教育研究會(huì)課題新工科背景下的應(yīng)用型本科計(jì)

“

算機(jī)專業(yè)課程體系建設(shè)河北省教育廳第二批河北省新工科研究與

”(2020-AFCEC-396)、

實(shí)踐項(xiàng)目應(yīng)用型本科計(jì)算機(jī)專業(yè)通專融合課程體系構(gòu)建河北省省

“”(2020GJXGK057)、

屬高?；究蒲袠I(yè)務(wù)費(fèi)項(xiàng)目后疫情時(shí)代雙線混合教學(xué)中高校教師教學(xué)勝任力提升策略

“

研究華北理工大學(xué)輕工學(xué)院年校級(jí)教育教學(xué)改革研究與實(shí)踐項(xiàng)目

”(JSQ2021011)、2020

探索基于的混合教學(xué)模式之路計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)課程的教改實(shí)踐

“OBE———”

項(xiàng)目的資助

(qgjg202010)。

盡管編者在寫作過程中非常認(rèn)真和努力但由于編者水平有限書中難免存在疏漏

,,

和不足之處懇請(qǐng)廣大讀者批評(píng)指正

,。

編者

年月

202111

第1篇習(xí)題解析………………………1

第1章數(shù)據(jù)結(jié)構(gòu)概述…………

2

習(xí)題………………

1.12

答案及解析………

1.28

第2章線性表…………………

14

習(xí)題………………

2.114

答案及解析……………………

2.222

第3章棧和隊(duì)列………………

43

習(xí)題………………

3.143

答案及解析……………………

3.249

第4章串………………………

61

習(xí)題………………

4.161

答案及解析……………………

4.263

第5章數(shù)組和廣義表…………

68

習(xí)題………………

5.168

答案及解析……………………

5.271

第6章樹和二叉樹……………

75

習(xí)題………………

6.175

答案及解析……………………

6.282

第7章圖………………………

98

習(xí)題………………

7.198

答案及解析……………………

7.2107

第8章查找……………………

120

習(xí)題……………

8.1120

答案及解析……………………

8.2124

第9章排序……………………

131

習(xí)題……………

9.1131

答案及解析……………………

9.2134

Ⅰ

數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)驗(yàn)指導(dǎo)

第2篇實(shí)驗(yàn)指導(dǎo)………………………141

實(shí)驗(yàn)語言預(yù)備知識(shí)………

0C142

實(shí)驗(yàn)億級(jí)累加和問題………

1153

實(shí)驗(yàn)數(shù)組循環(huán)移位問題……………………

2155

實(shí)驗(yàn)基于順序表的學(xué)生成績管理………

3160

實(shí)驗(yàn)基于順序表的學(xué)生信息管理………

4169

實(shí)驗(yàn)順序表的合并…………

5178

實(shí)驗(yàn)創(chuàng)建單鏈表……………

6182

實(shí)驗(yàn)基于單鏈表的學(xué)生成績管理………

7187

實(shí)驗(yàn)循環(huán)鏈表的合并………

8196

實(shí)驗(yàn)基于循環(huán)鏈表的約瑟夫環(huán)問題……

9200

實(shí)驗(yàn)單鏈表倒序查找……………………

10204

實(shí)驗(yàn)單鏈表原地逆置……………………

11210

實(shí)驗(yàn)棧的應(yīng)用：進(jìn)制轉(zhuǎn)換………………

12214

實(shí)驗(yàn)棧的應(yīng)用：表達(dá)式求值……………

13219

實(shí)驗(yàn)基于鏈隊(duì)列的舞伴配對(duì)問題………

14227

實(shí)驗(yàn)基于循環(huán)隊(duì)列的就醫(yī)管理…………

15233

實(shí)驗(yàn)串應(yīng)用：愷撒密碼…………………

16240

實(shí)驗(yàn)?zāi)Ｊ狡ヅ渌惴ā?/p>

17BF242

實(shí)驗(yàn)二叉樹遍歷…………

18245

實(shí)驗(yàn)哈夫曼編碼與譯碼…………………

19250

實(shí)驗(yàn)基于算法的最短路徑求解………………

20Dijkstra256

實(shí)驗(yàn)二叉排序樹算法……………………

21262

實(shí)驗(yàn)哈希函數(shù)的構(gòu)造……………………

22268

Ⅱ

數(shù)據(jù)結(jié)構(gòu)的基本概念和相關(guān)術(shù)語

?

重點(diǎn)數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及兩者之間的關(guān)系

?

算法基本概念、算法時(shí)間復(fù)雜度分析和空間復(fù)雜度分析

?

抽象數(shù)據(jù)類型的定義和使用

難點(diǎn)?

算法的時(shí)間復(fù)雜度分析和空間復(fù)雜度分析

?

1.1習(xí)題

一、單選題

算法是

1.()。

計(jì)算機(jī)程序解決問題的計(jì)算方法

A.B.

排序算法解決問題的有限運(yùn)算序列

C.D.

算法分析的兩個(gè)主要方面是

2.()。

空間復(fù)雜度和時(shí)間復(fù)雜度正確性和簡單性

A.B.

可讀性和文檔性數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

C.D.

數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)物理地址與邏輯地址不相同的稱為

3.,,()。

存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)

A.B.

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)

C.D.

數(shù)據(jù)在計(jì)算機(jī)內(nèi)有鏈?zhǔn)胶晚樞騼煞N存儲(chǔ)方式在存儲(chǔ)空間使用的靈活性上鏈?zhǔn)酱鎯?chǔ)比順

4.,,

序存儲(chǔ)要

()。

低高相同不確定

A.B.C.D.

順序存儲(chǔ)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由表示的

5.()。

線性結(jié)構(gòu)非線性結(jié)構(gòu)

A.B.

存儲(chǔ)位置指針

C.D.

2

第1章數(shù)據(jù)結(jié)構(gòu)概述

根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性以下解釋錯(cuò)誤的是

6.,()。

集合中任何兩個(gè)結(jié)點(diǎn)之間都有邏輯關(guān)系但組織形式松散

A.,

線性結(jié)構(gòu)中結(jié)點(diǎn)形成對(duì)的關(guān)系

B.11

樹狀結(jié)構(gòu)具有分支層次特性其形態(tài)有點(diǎn)像自然界中的樹

C.、,

圖狀結(jié)構(gòu)中的各個(gè)結(jié)點(diǎn)按邏輯關(guān)系互相纏繞任何兩個(gè)結(jié)點(diǎn)都可以鄰接

D.,

關(guān)于邏輯結(jié)構(gòu)以下說法錯(cuò)誤的是

7.,()。

邏輯結(jié)構(gòu)是獨(dú)立于計(jì)算機(jī)的

A.

運(yùn)算的定義與邏輯結(jié)構(gòu)無關(guān)

B.

同一邏輯結(jié)構(gòu)可以采用不同的存儲(chǔ)結(jié)構(gòu)

C.

一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)

D.

邏輯結(jié)構(gòu)是數(shù)據(jù)組織的某種本質(zhì)性的東西

E.“”

有以下程序段

8.:

for(i=n-1;i>=0;i--)

for(j=1;j<=n;j++)

if(A[j]>A[j+1])

A[j]與A[j+1]對(duì)換;

其中n為正整數(shù)則最后一行的語句頻度在最壞情況下是

,()。

O(n)O(n2)O(n3)O(nn)

A.B.C.D.log2

下面程序片段的算法時(shí)間復(fù)雜度是

9.()。

intsum1(intn)

{inti,p=1,s=0;

for(i=1;i<=n;i++)

{p*=i;

s+=p;

}

returns;

}

O(n)O(n)OnO(n)

A.2B.C.()D.log2

下面程序片段的算法時(shí)間復(fù)雜度是

10.()。

intsum2(intn)

{intp,s=0;

inti,j;

for(i=1;i<=n;i++)

{p=1;

for(j=1;j<=i;j++)

p*=j;

s+=p;

}

returns;

}

3

數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)驗(yàn)指導(dǎo)

n

O(n2)O()OnO(n)

A.B.2C.()D.log2

下面程序片段的算法時(shí)間復(fù)雜度是

11.()。

intfun(intn)

{inti=1,s=1;

while(s<n)

s+=++i;

returni;

}

O(n2)O(n)OnO(n)

A.B.C.()D.log2

從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為兩大類

12.()。

動(dòng)態(tài)結(jié)構(gòu)靜態(tài)結(jié)構(gòu)順序結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)

A.、B.、

線性結(jié)構(gòu)非線性結(jié)構(gòu)初等結(jié)構(gòu)構(gòu)造型結(jié)構(gòu)

C.、D.、

線性結(jié)構(gòu)的順序存儲(chǔ)結(jié)構(gòu)是一種的存儲(chǔ)結(jié)構(gòu)線性結(jié)構(gòu)的鏈?zhǔn)酱鎯?chǔ)是一種的存

13.(①),(②)

儲(chǔ)結(jié)構(gòu)

。

隨機(jī)存取順序存取索引存取散列存取

A.B.C.D.

算法的時(shí)間復(fù)雜度取決于

14.()。

問題的規(guī)模待處理數(shù)據(jù)的初態(tài)

A.B.

和機(jī)器的運(yùn)行速度

C.ABD.

下面程序的時(shí)間復(fù)雜度為

15.()。

for(i=0;i<m;i++)

for(j=0;j<n;j++)

A[i][j]=i*j;

O(m2)O(n2)O(mn)(mn)

A.B.C.×D.+

在下面的程序段中對(duì)的賦值語句的頻度為

16.,x()。

for(k=1;k<=n;k++)

for(j=1;j<=n;j++)x=x+1;

n

O()OnO(n2)O(n)

A.2B.()C.D.log2

采用順序存儲(chǔ)結(jié)構(gòu)表示數(shù)據(jù)時(shí)相鄰的數(shù)據(jù)元素的存儲(chǔ)地址

17.,()。

一定連續(xù)一定不連續(xù)

A.B.

不一定連續(xù)部分連續(xù)部分不連續(xù)

C.D.,

與數(shù)據(jù)元素本身的形式內(nèi)容相對(duì)位置個(gè)數(shù)無關(guān)的是數(shù)據(jù)的

18.、、、()。

存儲(chǔ)結(jié)構(gòu)存儲(chǔ)實(shí)現(xiàn)邏輯結(jié)構(gòu)運(yùn)算實(shí)現(xiàn)

A.B.C.D.

以下數(shù)據(jù)結(jié)構(gòu)中是非線性數(shù)據(jù)結(jié)構(gòu)

19.,()。

樹字符串隊(duì)列棧

A.B.C.D.

某算法的語句執(zhí)行頻度為(nnnn2)其時(shí)間復(fù)雜度表示

20.3+log2++8,()。

O(n)O(n)On2O(n)

A.B.log2C.()D.log2

以下程序段中語句的語句頻度為

21.“n++;”()。

for(i=1;i<=n;i++)

for(j=1;j<=i;j++)

4

第1章數(shù)據(jù)結(jié)構(gòu)概述

for(k=1;k<=j;k++)

x++;

nnnnnn

(+1)(2+1)(+1)(+1)

A.B.

22

nnnnnn

(+1)(2+1)(+1)(+2)

C.D.

66

以下程序段中語句的語句頻度為

22.“m++;”()。

intm=0,i,j;

for(i=1;i<=n;i++)

for(j=1;j<=2*i;j++)

m++;

n(n)nnn2

A.+1B.C.+1D.

設(shè)一維數(shù)組中有n個(gè)數(shù)組元素則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為

23.,()。

O(n)O(n)O()O(n2)

A.B.log2C.1D.

下面算法將一維數(shù)組a中的n個(gè)數(shù)逆序存放到原數(shù)組中空間復(fù)雜度為

24.,()。

for(i=0;i<n;i++)

b[i]=a[n-i-1];

for(i=0;i<n;i++)

a[i]=b[i];

O()O(n)O(n)O(n2)

A.1B.C.log2D.

下面算法將一維數(shù)組a中的n個(gè)數(shù)逆序存放到原數(shù)組中空間復(fù)雜度為

25.,()。

for(i=0;i<n/2;i++)

{t=a[i];

a[i]=a[n-i-1];

a[n-i-1]=t;

}

O()O(n)O(n)O(n2)

A.1B.C.log2D.

下列敘述中正確的是

26.()。

一個(gè)算法的空間復(fù)雜度大則其時(shí)間復(fù)雜度也必定大

A.,

一個(gè)算法的空間復(fù)雜度大則其時(shí)間復(fù)雜度必定小

B.,

一個(gè)算法的時(shí)間復(fù)雜度大則其空間復(fù)雜度必定小

C.,

上述三種說法都不對(duì)

D.

樹狀結(jié)構(gòu)是數(shù)據(jù)元素之間存在的一種

27.()。

一對(duì)一關(guān)系多對(duì)多關(guān)系多對(duì)一關(guān)系一對(duì)多關(guān)系

A.B.C.D.

設(shè)數(shù)據(jù)結(jié)構(gòu)ADR其中DRrr

28.=(,),={1,2,3,4},={},={<1,2>,<2,3>,<3,4>,

則數(shù)據(jù)結(jié)構(gòu)A是

<4,1>},()。

線性結(jié)構(gòu)樹結(jié)構(gòu)圖集合

A.B.C.D.

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān)系是由表示的

29.()。

線性結(jié)構(gòu)非線性結(jié)構(gòu)存儲(chǔ)位置指針

A.B.C.D.

某算法僅含程序段和程序段程序段的執(zhí)行次數(shù)為n3程序段的執(zhí)行次數(shù)為

30.12,13,2

5

數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)驗(yàn)指導(dǎo)

.n3則該算法的時(shí)間復(fù)雜度為

001,()。

O(n)O(n2)O(n3)O()

A.B.C.D.1

以下說法正確的是

31.()。

數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)獨(dú)立于其存儲(chǔ)結(jié)構(gòu)

A.

數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)獨(dú)立于該數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)

B.

數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)唯一地決定了該數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)

C.

數(shù)據(jù)結(jié)構(gòu)僅由其邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)決定

D.

設(shè)有如下遺產(chǎn)繼承規(guī)則丈夫和妻子可以互相繼承遺產(chǎn)子女可以繼承父親和母親的遺

32.:,

產(chǎn)子女間不能相互繼承則表示該遺產(chǎn)繼承關(guān)系最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是

,,()。

樹圖線性表集合

A.B.C.D.

年第題設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)下面程序片段的時(shí)間復(fù)雜度

33.【20111】,

是

()。

x=2;

while(x<n/2)

x=2*x;

O(n)O(n)O(nn)O(n2)

A.log2B.C.log2D.

年第題求整數(shù)nn階乘的算法如下其時(shí)間復(fù)雜度是

34.【20121】(≥0),()。

intfact(intn){

if(n<=1)

return1;

returnn*fact(n-1);

}

O(n)O(n)O(nn)O(n2)

A.log2B.C.log2D.

年第題下列程序段的時(shí)間復(fù)雜度

35.【20141】()。

count=0;

for(k=1;k<=n;k*=2)

for(j=1;j<=n;j++)

count++;

O(n)O(n)