2022年2022年《數(shù)據(jù)結(jié)構(gòu)》習(xí)題集

1、精選學(xué)習(xí)資料 - - - 歡迎下載.數(shù)據(jù)結(jié)構(gòu)習(xí)題集第一章序論摸索題 ：1.1 簡(jiǎn)述以下術(shù)語(yǔ)：數(shù)據(jù).數(shù)據(jù)元素.數(shù)據(jù)對(duì)象.數(shù)據(jù)結(jié)構(gòu).儲(chǔ)備結(jié)構(gòu).數(shù)據(jù)類型.抽象數(shù)據(jù)類型作業(yè)題 ：1.2 設(shè)有數(shù)據(jù)結(jié)構(gòu)（ d,r）,其中 d=d1、 d2、 d3、 d4 r=r1、 r2r1= <d1、 d2>、 <d2、 d3>、 <d3、 d4>、 <d1、 d4>、 <d4、 d2>、 <d4、 d1> r2= d1、 d2、 d1、 d3、 d1、 d4、 d2、 d4、 d2、 d3 試?yán)L出其規(guī)律結(jié)構(gòu)示意圖；1.3 設(shè) n 為正整數(shù)；試寫出

2、以下程序段中用記號(hào)“”標(biāo)注的語(yǔ)句的頻度：1i=1; k=0;whilei<=n-1 k+=10*i; i+;2i=1; k=0;do k+=10*i; i+;whilei<=n-13i=1; k=0;do k+ = 10*i; i+;whilei=n;4i=1; j=0;whilei+jn ifi<j i+; else j+;.c精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載.(5) x=n; y=0; /n為不小于 1 的常數(shù)whilex>=y+1*y+1y+;6x=91; y=100;while y>0 ifx>100 x-=10; y-; else x

3、+ ;7for i=0; i<n; i+ for j=i; j<n; j+for k=j; k<n; k+1.4x+=2;試寫一算法,自大至小依次輸出次序讀入的三個(gè)整數(shù)x、y 和 z 的值；1.5已知 k 階斐波那契序列的定義為：f0=0、 f 1=0、 f k-2 =0、 f k-1 =1；fn= f n-1+ f n-2+ f n-k 、n=k、k+1、試編寫求 k 階斐波那契序列的第m項(xiàng)值的函數(shù)算法,k 和 m均以值調(diào)用的形式在函數(shù)參數(shù)表中顯現(xiàn)；其次章線性表摸索題 ：2.1 描述以下三個(gè)概念的區(qū)分：頭指針.頭結(jié)點(diǎn).首元結(jié)點(diǎn)；2.2 描述以下幾個(gè)概念：次序儲(chǔ)備結(jié)構(gòu).鏈?zhǔn)絻?chǔ)

4、備結(jié)構(gòu).次序表.有序表；作業(yè)題 ：2.3 已知次序表la 中數(shù)據(jù)元素按非遞減有序排列；試寫一個(gè)算法,將元素x 插到 la 的合適位置上,保持該表的有序性；2.4 已知單鏈表la 中數(shù)據(jù)元素按非遞減有序排列；按兩種不憐憫形,分別寫出算法,將元素x 插到 la 的合適位置上,保持該表的有序性：（1）la 帶頭結(jié)點(diǎn)；（ 2） la 不帶頭結(jié)點(diǎn)；2.5 試寫一個(gè)算法,實(shí)現(xiàn)次序表的就地逆置,即在原表的儲(chǔ)備空間將線性表（ a1、a 2、 .、 an-1、a n）逆置為 a n、a n-1 、 .、 a2、a 1 2.6 試寫一個(gè)算法,對(duì)帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)就地逆置；.c精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - -

5、 歡迎下載.2.7 已知線性表l 采納次序儲(chǔ)備結(jié)構(gòu)存放；對(duì)兩種不憐憫形分別寫出算法,刪除l 中值相同的余外元素, 使得 l 中沒(méi)有重復(fù)元素： 1l中數(shù)據(jù)元素?zé)o序排列； 2l中數(shù)據(jù)元素非遞減有序排列；2.8 將 2.7 題中 l 的儲(chǔ)備結(jié)構(gòu)改為單鏈表,寫出相應(yīng)的實(shí)現(xiàn)算法；2.9 設(shè)有兩個(gè)非遞減有序的單鏈表a 和 b；請(qǐng)寫出算法,將a 和 b“就地”歸并成一個(gè)按元素值非遞增有序的單鏈表c；2.10 設(shè)有一個(gè)長(zhǎng)度大于1 的單向循環(huán)鏈表,表中既無(wú)頭結(jié)點(diǎn),也無(wú)頭指針,s為指向表中某個(gè)結(jié)點(diǎn)的指針、 如圖 2-1 所示；試編寫一個(gè)算法,刪除鏈表中指針s 所指結(jié)點(diǎn)的直接前驅(qū)；待刪結(jié)點(diǎn)s圖 2-12.11 已知

6、線性表用帶頭結(jié)點(diǎn)的單鏈表表示,表中結(jié)點(diǎn)由三類字符組成：字母.數(shù)字和其他字符； 試編寫算法, 將該線性鏈表分割成三個(gè)循環(huán)單鏈表,每個(gè)循環(huán)單鏈表中均只含有一類字符；2.12 已知線性表用次序儲(chǔ)備結(jié)構(gòu)表示,表中數(shù)據(jù)元素為n 個(gè)正整數(shù)；試寫一算法,分別該表中的奇數(shù)和偶數(shù), 使得全部奇數(shù)集中放在左側(cè), 偶數(shù)集中放在右側(cè)；要求： 1 不借助幫助數(shù)組 ;2時(shí)間復(fù)雜度為on ；2.13 設(shè)以帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表表示的線性表l=a 1、a 2、a 3、.、an ；試寫一時(shí)間復(fù)雜度為on 的算法,將l 改造為 l=a 1、a 3、.、an、.、a4、a 2 ；第三章棧和隊(duì)列摸索題 ：3.1 簡(jiǎn)述棧和線性表的差別

7、；3.2 假如進(jìn)棧序列為a.b.c.d,寫出全部可能的出棧序列；.c精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載.3.3 簡(jiǎn)述棧和隊(duì)列的相同點(diǎn)和差異；3.4 已知棧 s 中存放了 8 個(gè)數(shù)據(jù)元素,自棧底至棧頂依次為1、2、3、4、5、6、7、8；（ 1）寫出在執(zhí)行了函數(shù)調(diào)用algo1s 后, s 中的元素序列；（ 2）在（ 1）的基礎(chǔ)上,又執(zhí)行了函數(shù)調(diào)用algo2s、5,寫出此時(shí)s 中的元素序列；void algo1stack &s int a10、 i、 n=0;while.stackemptys n+; pops、 an; fori=1; i<=n; i+ pushs、 a

8、i;void algo2stack &s、 int e stack t;int d; initstackt;while.emptystacks pops、d;ifd.=e pusht、d;while.stackemptyt popt、d;pushs、d;3.5 已知隊(duì)列q 中自隊(duì)頭至隊(duì)尾依次存放著1、2、3、4、5、6、7、8；寫出在執(zhí)行了函數(shù)調(diào)用 algo3q 后, q中的元素序列；void algo3queue &qstack s; int d;initstacks;.c精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載.while.queueemptyq dequeueq、d

9、; pushs、d;while.stackemptys pops、d; enqueueq、d;作業(yè)題：3.6 試寫一個(gè)算法, 識(shí)別依次讀入的一個(gè)以為終止符的字符序列為否為形如 “序列 1&序列 2”模式的字符序列；其中,序列 1 和序列 2 中都不包含字符 &、 且序列 2 為序列 1 的逆序；例如,“ a+b&b+a”為屬于該模式的字符序列,而“ 1 3&3 1”就不為；3.7 假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含三種符號(hào)：圓括號(hào)“ ”和“ ”.方括號(hào)“ ”和“ ”.花括號(hào)“ ”和“ ”,且這三種括號(hào)可按任意次序嵌套使用；編寫判別給定表達(dá)式中所含的括號(hào)為否正確配對(duì)的算

10、法（已知表達(dá)式已存入數(shù)據(jù)元素為字符的次序表中）；3.8 設(shè)表達(dá)式由單字母變量. 雙目運(yùn)算符和圓括號(hào)組成 （如:“a*b+c-d/e）”；試寫一個(gè)算法,將一個(gè)書(shū)寫正確的表達(dá)式轉(zhuǎn)換為逆波蘭式；3.9 試用類 c 寫一個(gè)算法,對(duì)逆波蘭式求值；3.10 假設(shè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表表示隊(duì)列,只設(shè)一個(gè)尾指針指向隊(duì)尾元素,不設(shè)頭指針；試編寫相應(yīng)的隊(duì)列初始化.入隊(duì)和出隊(duì)的算法；3.11 假設(shè)將循環(huán)隊(duì)列定義為： 以 rear 和 length 分別指示隊(duì)尾元素和隊(duì)列長(zhǎng)度；試給出此循環(huán)隊(duì)列的隊(duì)滿條件, 并寫出相應(yīng)的入隊(duì)和出隊(duì)算法 （在出隊(duì)算法中要傳遞回隊(duì)頭元素的值） ；3.12 試寫一個(gè)算法： 判別讀入的一個(gè)以

11、為終止符的字符序列為否為“回文”（所謂“回文”為指正讀和反讀都相同的字符序列,如“xxyzyxx ”為回文,而 “ abcab”就不為回文）；.c精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載.第五章多維數(shù)組5.1 已知多維數(shù)組 a2233 按行優(yōu)先方式儲(chǔ)備；試按儲(chǔ)備位置的先后次序,列出全部數(shù)組元素 aijkl序列（為了簡(jiǎn)化表達(dá),可以只列出形如 “ i、j、k、 l ”的序列,如元素 a0021 可表示為“ 0、0、2、1 ” ）；5.2 假設(shè)有一個(gè)二維數(shù)組a0.50.7,每個(gè)元素占6 個(gè)字節(jié),首元素 a00的地址為 1000,求： 1a的體積；(2) 最終一個(gè)元素a57的地址；(3) 按行主

12、序方式儲(chǔ)備時(shí),a24的地址；(4) 按列主序方式儲(chǔ)備時(shí),a24的地址；5.3 設(shè)有上三角矩陣an×n,精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載a11a12 a22ca13 a23a33.a1n a2 n a3n.ann精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載將其上三角的元素逐行存于數(shù)組b0.m-1中（m充分大）,使得 bk=a ij 且 kf 1i+f2j+c；試推導(dǎo)出函數(shù)f 1.f 2 和常數(shù) c（要求 f 1 和 f 2 中不含常數(shù)項(xiàng)）；5.4 設(shè)有一個(gè)準(zhǔn)對(duì)角矩陣精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載a11a 21a12 a22a33 a43a34a44.a2

13、m1、2m 1a2m1、 2m精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載a2m、 2 m 1a2m、 2 m按以下方式存于一維數(shù)組b4m中：0123456k4m-24m-1.c精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載.a11a12a21a22a33a34a43.aij.a2m-1、2ma2m、2m寫出由一對(duì)下標(biāo) i、j求 k 的轉(zhuǎn)換公式；5.5 已知稀疏矩陣a4×5 如下：01005230600000004007a(1) 用三元組表作為儲(chǔ)備結(jié)構(gòu),繪出相應(yīng)的三元組表示意圖；(2) 用十字鏈表作為儲(chǔ)備結(jié)構(gòu),繪出相應(yīng)的十字鏈表示意圖；5.6 設(shè)稀疏矩陣 a 和 b 均以三元組次序

14、表作為儲(chǔ)備結(jié)構(gòu)； 試寫出運(yùn)算矩陣相加 c a b 的算法,其中, c 為另設(shè)的.存放結(jié)果的三元組表（提示：可用類似于兩個(gè)有序次序表歸并的處理方法） ；5.7 試編寫一個(gè)算法, 實(shí)現(xiàn)以三元組的形式打印用十字鏈表表示的稀疏矩陣中全部非零元素及其下標(biāo)；5.8 試編寫一個(gè)算法,實(shí)現(xiàn)以矩形陣列的形式打印用十字鏈表表示的稀疏矩陣；第六章 樹(shù)和二叉樹(shù)6.1 試分別繪出具有 3 個(gè)結(jié)點(diǎn)的樹(shù)和 3 個(gè)結(jié)點(diǎn)的二叉樹(shù)的全部不同形狀；6.2 設(shè)結(jié)點(diǎn) x 為二叉樹(shù)上一個(gè)度為 1 的結(jié)點(diǎn), x有幾個(gè)子樹(shù)？6.3 描述滿意以下條件的二叉樹(shù)形狀：(1) 先序遍歷序列與中序遍歷序列相同；(2) 后序遍歷序列與中序遍歷序列相同；

15、(3) 先序遍歷序列與后序遍歷序列相同；6.4 一個(gè)深度為 h 的滿 k 叉樹(shù)有如下性質(zhì)： 第 h層上全部結(jié)點(diǎn)都為葉子結(jié)點(diǎn), 其余各層上每個(gè)結(jié)點(diǎn)都有 k 棵非空子樹(shù)；假如從 1 開(kāi)頭按自上而下. 自左向右的次序?qū)θ拷Y(jié)點(diǎn)編號(hào),問(wèn)：(1) 各層的結(jié)點(diǎn)數(shù)目為多少？(2) 編號(hào)為 i 的結(jié)點(diǎn)的父結(jié)點(diǎn) 如存在 的編號(hào)為多少？.c精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載.3編號(hào)為 i的結(jié)點(diǎn)的第j 個(gè)孩子 如存在 的編號(hào)為多少？4編號(hào)為 i的結(jié)點(diǎn)有右兄弟的條件為什么？其右兄弟的編號(hào)為多少？6.5 已知一棵度為k 的樹(shù)中有n1 個(gè)度為1 的結(jié)點(diǎn), n2 個(gè)度為 2 的結(jié)點(diǎn), .,nk 個(gè)度為 k 的結(jié)

16、點(diǎn),問(wèn)該樹(shù)中有多少個(gè)葉子結(jié)點(diǎn)？6.6 已知在一棵含有n 個(gè)結(jié)點(diǎn)的樹(shù)中, 只有度為 k 的分支結(jié)點(diǎn)和度為0 的葉子結(jié)點(diǎn)；試求該樹(shù)含有的葉子結(jié)點(diǎn)的數(shù)目；6.7 設(shè) n 和 m為二叉樹(shù)中兩個(gè)結(jié)點(diǎn),用“1”.“0”.和“”（分別表示確定,否定和不肯定）填寫下表：精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載已知問(wèn)先序遍歷時(shí)n 在 m之前？中序遍歷時(shí)n 在 m之前？后序遍歷時(shí)n 在 m之前？精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載n 在 m左方n 在 m右方n 為 m祖先n 為 m 子（注：假如離n 和 m 的最近的共同祖先x 存在, 且 n 位于 x 的左子樹(shù)中, m 位于 x 的右子樹(shù)中,就稱

17、“n 在 m 的左方”或“m 在 n 的右方”；）6.8 已知一棵樹(shù)如圖6-1 所示,畫(huà)出與該樹(shù)對(duì)應(yīng)的二叉樹(shù),并寫出該樹(shù)的先根遍歷序列和后根遍歷序列；abcdefghijk圖 6-1.c精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載.6.9 將如圖 6-2 所示的森林轉(zhuǎn)化為對(duì)應(yīng)的二叉樹(shù)；a iklb jmnc deofgh圖 6-26.10 畫(huà)出和以下二叉樹(shù)（如圖6-3 所示）相應(yīng)的森林；aaaabbbcbcccdefghijkl圖 6-36.11 已知某二叉樹(shù)的中序序列為dcbgeahfijk ,后序序列為dcegbfhkjia ；請(qǐng)畫(huà)出該二叉樹(shù)；6.12 已知樹(shù)t的先根遍歷拜訪序列為gfk

18、daiebchj ,后根遍歷拜訪序列為diaekfcjhbg ；請(qǐng)畫(huà)出樹(shù)t；.c精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載.6.13 已知森林f 的先根遍歷拜訪序列為abcdefghijkl ,中根遍歷拜訪序列為 cbefdgajiklh ；請(qǐng)畫(huà)出這個(gè)森林f；6.14 假設(shè)某個(gè)電文由 a、b、c、d、e、f、g、h8個(gè)字母組成, 每個(gè)字母在電文中顯現(xiàn)的次數(shù)分別為 7、19、2、6、32、3、21、10,試解答以下問(wèn)題：(1) 畫(huà)出出 huffman 樹(shù)；(2) 寫出每個(gè)字母的huffman 編碼；(3) 在對(duì)該電文進(jìn)行最優(yōu)二進(jìn)制編碼處理后,電文的二進(jìn)制位數(shù)；6.15 寫出復(fù)制一棵二叉樹(shù)的算

19、法；6.16 試編寫算法,實(shí)現(xiàn)將二叉樹(shù)全部結(jié)點(diǎn)的左右子樹(shù)互換；6.17 寫出按層次遍歷二叉樹(shù)的算法；6.18 寫出判定給定二叉樹(shù)為否為完全二叉樹(shù)的算法；6.19 寫出判定兩棵給定二叉樹(shù)為否相像的算法；注：兩棵二叉樹(shù)b1 和 b2 相像為指： b1 和 b2 皆空,或者皆不空且b1 的左.右子樹(shù)和 b2 的左.右子樹(shù)分別相像；6.20 利用棧的基本操作,寫出二叉樹(shù)先序遍歷的非遞歸算法；6.21 寫出統(tǒng)計(jì)樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)的算法,樹(shù)用孩子兄弟鏈表表示；6.22 寫出運(yùn)算樹(shù)的深度的算法,樹(shù)用孩子兄弟鏈表表示；6.23 寫出運(yùn)算二叉樹(shù)第k 層結(jié)點(diǎn)數(shù)的算法；6.24 寫出運(yùn)算二叉樹(shù)深度的算法；第七章圖v1

20、v57.1 已知有向圖如圖7-1 所示,請(qǐng)給出該圖的v6精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載(1) 鄰接矩陣示意圖(2) 鄰接表示意圖(3) 逆鄰接表v2v4v3精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載.c圖 7-1精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載.(4) 全部強(qiáng)連通重量7.2 已知圖 g的鄰接矩陣如圖7-2 所示；寫出該圖從頂點(diǎn)1 動(dòng)身的深度優(yōu)先搜尋序列和廣度優(yōu)先搜尋序列,并畫(huà)出相應(yīng)的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)；12345678910100000010102001000100030001000100400001000105000001000161100000

21、000700100000018100100001090000101001101000010000圖 7-27.3 無(wú)向帶權(quán)圖如圖7-3 所示,(1) 畫(huà)出它的鄰接矩陣,并按prim 算法求其最小生成樹(shù)；(2) 畫(huà)出它的鄰接表,并按kruskal算法求其最小生成樹(shù)9e3b746f5a5d2553gc465h圖 7-37.4 有向圖如圖7-4 所示,試寫出其全部可能的拓?fù)湫蛄校?c精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載.v1v2v3v4v5v6圖 7-47.5 試?yán)?dijkstra 算法求圖 7-5 中頂點(diǎn) a 到其他各頂點(diǎn)之間的最短路徑；要求寫出執(zhí)行算法過(guò)程中,數(shù)組d.p 和 s 各

22、步的狀態(tài)；4b6e15892acg410f125d3圖 7-57.6 試在鄰接矩陣儲(chǔ)備結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：insertvexg、v,insertarcg、v、w、 deletevexg、v和 deletearcg、v、w；7.7 試在鄰接表儲(chǔ)備結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：insertvexg、v,insertarcg、v、w、 deletevexg、v和 deletearcg、v、w；7.8 設(shè)具有 n 個(gè)頂點(diǎn)的有向圖用鄰接表儲(chǔ)備；試寫出運(yùn)算全部頂點(diǎn)入度的算法,可將每個(gè)頂點(diǎn)的入度值分別存入一維數(shù)組int indegreen中；7.9 假設(shè)有向圖以鄰接表作為儲(chǔ)備結(jié)構(gòu)；試基于圖的深度優(yōu)先搜尋策略寫

23、一算法,判定有向圖中為否存在由頂點(diǎn)vi 至頂點(diǎn) vji.=j的路徑；7.10 假設(shè)有向圖以鄰接表作為儲(chǔ)備結(jié)構(gòu)；試基于圖的廣度優(yōu)先搜尋策略寫一算法,判定有向圖中為否存在由頂點(diǎn)vi 至頂點(diǎn) vji.=j的路徑；7.11 以鄰接表作為儲(chǔ)備結(jié)構(gòu),實(shí)現(xiàn)求單源最短路徑的dijkstra算法；.c精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載.第九章查找9.1 如對(duì)大小均為n 的有序次序表和無(wú)序次序表分別進(jìn)行次序查找,試在以下三種情形下分別爭(zhēng)論兩者在等概率時(shí)平均查找長(zhǎng)度為否相同？1查找不勝利,即表中沒(méi)有關(guān)鍵字等于給的值k 的記錄；2查找勝利,且表中只有一個(gè)關(guān)鍵字等于給定值k 的記錄；3查找勝利,且表中有如干

24、個(gè)關(guān)鍵字等于給定值k 的記錄,要求找出全部這些記錄；9.2 試分別寫出在對(duì)有序線性表a、b、c、d、e、f、g中進(jìn)行折半查找, 查值等于 e. f 和 g 的元素時(shí),先后與哪些元素進(jìn)行了比較；9.3 畫(huà)出對(duì)長(zhǎng)度為13 的有序表進(jìn)行折半查找的判定樹(shù),并分別求其等概率時(shí)查找勝利和查找失敗的asl；9.4 已知如下所示長(zhǎng)度為12 的表：jan、 feb、 mar、 apr、 may、 jun、 july、 aug、 sep、 oct、 nov、 dec表中,每個(gè)元素的查找概率分別為：0.1、0.25、0.05、0.13、0.01、0.06、0.11、0.07、0.02、0.03、0.1、0.07(1) 如對(duì)該表進(jìn)行次序查找,求查找勝利的平均查找長(zhǎng)