數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題附答案

1、一.是非題1.數(shù)據(jù)結(jié)構(gòu)應(yīng)該是抽象數(shù)據(jù)類型可用三元式表示D,S,P.其中：D是數(shù)據(jù)對(duì)象,S是D上的關(guān)系,P是對(duì)D的根本操作集.f2簡單地說,數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合.t3判斷帶頭結(jié)點(diǎn)的非空循環(huán)單鏈表頭指針為L中指針p所指結(jié)點(diǎn)是最后一個(gè)元素結(jié)點(diǎn)的條件是：p-next=Lot4線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)具有可直接存取表中任一元素的優(yōu)點(diǎn).f5 線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu).f6 .在單鏈表P指針?biāo)附Y(jié)點(diǎn)之后插入S結(jié)點(diǎn)的操作是：P-next=S；S-next=P-next；of順序弄反了S-next=P-next；P-next=S；7 對(duì)于插入、刪除而言,線性表的錐式存儲(chǔ)優(yōu)于順序存儲(chǔ).t8

2、.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大,且插入、刪除運(yùn)算效率高.f9 .棧和隊(duì)列是操作上受限制的線性表.t10 .隊(duì)列是與線性表完全不同的一種數(shù)據(jù)結(jié)構(gòu).f棧和隊(duì)列是操作上受限制的線性表11 .隊(duì)列是一種操作受限的線性表,凡對(duì)數(shù)據(jù)元素的操作僅限=next=nullC.L-next=LD.L!=null4假設(shè)順序表中各結(jié)點(diǎn)的查找概率不等,那么可用如下策略提升順序查找的效率：假設(shè)找到指定的結(jié)點(diǎn),將該結(jié)點(diǎn)與其后繼假設(shè)存在結(jié)點(diǎn)交換位置,使得經(jīng)常被查找的結(jié)點(diǎn)逐漸移至表尾.以下為據(jù)此策略編寫的算法,請(qǐng)選擇適當(dāng)?shù)膬?nèi)容,完成此功能.順序表的存儲(chǔ)結(jié)構(gòu)為：typedefstructElemType*elem；ey=key

3、；i=;whileEi.key!-key)fif(G)i一-Hl；returni；)A.i0B.i=0C.iD.inext非空,此時(shí)假設(shè)要?jiǎng)h除指針p所指的結(jié)點(diǎn),可以通過如下方法進(jìn)行：將p所指結(jié)點(diǎn)的后繼的元素值復(fù)制到該結(jié)點(diǎn),然后刪除其后繼結(jié)點(diǎn).相應(yīng)的語句序列為：p-datap-next-data；p-noxtp-next-nexl；froe(p-noxt)；3線性表的順序存儲(chǔ)結(jié)構(gòu)是以數(shù)組三日來表示數(shù)據(jù)元素之間的邏輯關(guān)系的.4P是單鏈表中某一結(jié)點(diǎn)的指針,P既不是首元結(jié)點(diǎn)也不是尾元結(jié)點(diǎn),Q是P的前驅(qū)結(jié)點(diǎn)指針.當(dāng)刪除P結(jié)點(diǎn)時(shí),鏈表的錐接可用語句(qlnext二p-nexl)實(shí)現(xiàn).5某樹的先根遍歷次序?yàn)?/p>

4、abcdefg后根遍歷次序?yàn)閏debgfa.假設(shè)將該樹轉(zhuǎn)換為二叉樹,其后序遍歷次序?yàn)?edcgfba).層次遍歷次序?yàn)?abcfdge).6某二叉樹的先序遍歷次序?yàn)閍fbcdeg中序遍歷次序?yàn)閏edbgfao其后序遍歷次序?yàn)?edcgbfa)o層次遍歷次序?yàn)?afbcgde).7在二叉樹的第i層上至少有_個(gè)結(jié)點(diǎn),至多有一個(gè)結(jié)點(diǎn),深度為k的二叉樹至多有2-1個(gè)結(jié)點(diǎn).8對(duì)樹的遍歷有先序遍歷樹和后序遍歷樹.假設(shè)以二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu),那么樹的先序遍歷可借用二叉樹的先房遍歷算法來實(shí)現(xiàn).而樹的后序遍歷可借用二叉樹的史匠遍歷算法來實(shí)現(xiàn).9設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn),那么此類二叉樹中所包

5、含的結(jié)點(diǎn)數(shù)至少是2*hl,至多是滿樹.10對(duì)任何一棵二叉樹假設(shè)其終端結(jié)點(diǎn)數(shù)為nO度為2的結(jié)點(diǎn)為n2,那么nO與n2的關(guān)系為(n0=n2+l)o11如果對(duì)完全二叉樹中結(jié)點(diǎn)從1開始按層進(jìn)行編號(hào),設(shè)最大編號(hào)為n；那么,可以斷定編號(hào)為i(il)的結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為(i/2向下取整)；所有編號(hào)(in/2)的結(jié)點(diǎn)為葉子結(jié)點(diǎn)O12n個(gè)頂點(diǎn)的連通圖至少有支條邊,至多有n(n-l)/2條邊.13對(duì)于圖的存儲(chǔ)結(jié)構(gòu)有(數(shù)組表示法)、(表法)、(十字捱表法)、(鄰接多重表法)等方法.14在一個(gè)無向圖的鄰接表中,假設(shè)表結(jié)點(diǎn)的個(gè)數(shù)是m,那么圖中邊的條數(shù)是m/2條.15假設(shè)有序表中關(guān)鍵字序列為：12,22,33,44,55

6、,66,77,88,99對(duì)其進(jìn)行折半查找,那么在等概率情況下,查找成功時(shí)的平均查找長度是(3).查找99時(shí)需進(jìn)行(2)次比擬.16在哈希表中,處理沖突的方法有開放定址法,再哈希法,鏈地址法等.17在二叉樹的第i層上至少有L個(gè)結(jié)點(diǎn),至多有2二個(gè)結(jié)點(diǎn),深度為k的二叉樹至多有2-1個(gè)結(jié)點(diǎn).18對(duì)于一棵高度為K的二叉排序樹,結(jié)點(diǎn)數(shù)最少可有個(gè),最多可有個(gè).19用史工遍歷對(duì)二叉排序樹進(jìn)行訪問可得到有序序列.20Hash函數(shù)為HK=Kmod13,散列地址為014,用二次探測再散列處理沖突,關(guān)鍵字23,34,56,24,75,12,49,52,36,92的分布如圖,那么平均成功的查找長度為八平均失敗的查找長度

7、為.012345678910111213145236925634232475124921一棵m階的B-樹,第一層至少有一個(gè)結(jié)點(diǎn)；第二層至少有2個(gè)結(jié)點(diǎn),除根之外的所有非終端結(jié)點(diǎn)至少有廠m/21棵子樹,樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹.22在哈希表中,處理沖突的方法有開放定址法,再哈一,一.一至23哈希表的查找效率取決于哈希函數(shù)是否均勻處理沖突的方法和哈希表的裝填因子.24高度為4包含不帶關(guān)鍵字的葉子結(jié)點(diǎn)層的7階B樹最少有廠m最T個(gè)關(guān)鍵字,最多有m-l個(gè)關(guān)鍵字;如果其中的某結(jié)點(diǎn)正好有2個(gè)兒子,那么,該結(jié)點(diǎn)必定是結(jié)點(diǎn).25對(duì)n個(gè)元素的序列進(jìn)行內(nèi)部排序,假設(shè)用起泡排序法,最少的比擬次數(shù)是匚L最多的比較次數(shù)是

8、nn-D/2.25算法填空StatusPreordertraverseBitreeT,Status*VisitTelemtypeem成為一小頂堆.請(qǐng)?jiān)凇疤幪钌线m宜的內(nèi)容,完成該算法.VoidheapadjustheaptypeH,ints,intmrc=s；forj=2*s；j=m；j*=2ifjjbreak；s=j；s=j；s-rc;知某二叉樹的后序遍歷和中序遍歷次序分別為DBFGECA和BDACFEG請(qǐng)畫出該二叉樹,并為之建立先序線索.3某二叉樹的先序遍歷次序?yàn)椋篴,b,c,d,e,f,g.中序遍歷次序?yàn)椋篵,a,d,f,e,g,c畫出該二叉樹,并在該二叉樹上建立中序線索.4某二叉樹的中序

9、遍歷次序?yàn)锽EGFDAC,先序遍歷次序?yàn)锳BDEFGC.試畫出該二叉樹,并為之建立中序線索圖示之.5某二叉樹的后序遍歷和中序遍歷次序分別為FBEDGCA和FBADECG,請(qǐng)構(gòu)造并畫出該二叉樹.6設(shè)某一電文只出現(xiàn)a,b,c,d,e,f,g7個(gè)字母；出現(xiàn)頻率分別為30%,10%,05%,04%,13%,18%及20機(jī)請(qǐng)給出各字母的哈夫曼編碼.7將圖示森林轉(zhuǎn)換為二叉樹,并對(duì)該二叉樹先序全序線索化.8將圖示森林轉(zhuǎn)換為二叉樹,并對(duì)該二叉樹中序全序線索化.de9某二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)表示如下:012345678910111213141516171819ABCD*EFGHI試畫出此二叉樹的圖形表示.

10、2將此二叉樹看作森林的二叉樹表示,試將它復(fù)原為森林.10某有向圖如下圖：1給出其十字鏈表存儲(chǔ)結(jié)構(gòu)2給出其深度優(yōu)先遍歷次序.3給出其廣度優(yōu)先遍歷次序.4給出各強(qiáng)連通分量.11設(shè)輸入序列為20,45,30,89,70,38,62,19,依次插入到一棵2-3樹中(初始狀態(tài)為空),請(qǐng)畫出該B-樹.12右圖為一棵3階B一樹.(20,25)1)畫出在該樹上插入元素15/|后的B一樹.(10,14)(21)(35)2)接著,再刪除元素35,畫出刪除后的B樹.13Hash函數(shù)為H(K)=Kmod13,散列地址為0-14,用線性探測再散列處理沖突,給出關(guān)鍵字(56,34,68,23,16,70,48,35,83

11、,12,14,57)在散列地址的分布.并指出平均成功的查找長度是多少01234567891011121314114根據(jù)插入次序(20,30,70,60,10,100,110,90,80.)建立平衡的二叉排序樹.15設(shè)哈希表長為16,哈希函數(shù)為H(key)=keymod13,用開放定址法的二次探測再散列處理沖突(di=l)-I2,22,-*32,-32),依次存入12個(gè)元素:56,82,17,24,36,21,83,96,13,34,57,50o請(qǐng)畫出它們?cè)诒碇械姆植记樾?16待排序序列為：25,12,9,20,7,31,24,35,17,10,試寫出：(1) .雄排序初始建堆(大頂堆)的結(jié)果；

12、(2) .以第一個(gè)元素為樞軸的快速排序一趟掃描的結(jié)果；(3) .希爾排序第一趟(精量為5)的結(jié)果.算法設(shè)計(jì)題1設(shè)有一個(gè)帶頭結(jié)點(diǎn)、元素按值遞增有序的單銖表,結(jié)點(diǎn)的類型定義如下：typedefstructLNodeintdata；structLNode*next；LNode,LinkList；編寫算法,刪除其中所有值相同的多余元素結(jié)點(diǎn)2某線性表中元素以降序排列,現(xiàn)要插入一個(gè)元素X,插入后該線性元素仍保持降序.線性表采用帶頭結(jié)點(diǎn)單鏈表方式存貯.口請(qǐng)編寫該插入算法.3編寫在一有序順序表中插入數(shù)據(jù)元素X的算法INSERT(L,X).4寫一算法,Delete(linklist&L,X),刪除單鏈表中所有值

13、為X的結(jié)點(diǎn).單錐表結(jié)點(diǎn)的類型定義如下：typedefstructLNode(intdata；structLNode*next；LNode,*Linklist；5寫一算法,Contrarydinklist&L),對(duì)一帶頭結(jié)點(diǎn)且僅設(shè)尾指針L的循環(huán)單錐表就地逆置.(即表頭變表尾,表尾變表頭.)6線性表中的元素以值遞增有序排列,并以帶頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)結(jié)構(gòu).試寫一高效的算法,刪除表中所有值大于mink且小于maxk的元素(假設(shè)表中存在這樣的元素)同時(shí)釋放被刪結(jié)點(diǎn)空間,并分析你的算法的時(shí)間復(fù)雜度.單鏈表結(jié)點(diǎn)的類型定義如下：typedefstructLNodeintdata；structLNode*ne

14、xt；LNode,*Linklist；7寫一算法,將帶頭結(jié)點(diǎn)的有序單鏈表A和B合并成一新的有序表C.(注：不破壞A和B的原有結(jié)構(gòu).)Merge(LinklistA,LinklistB,Linklist&C)8寫一算法Oplinklist(linklistLtinti；intj)刪除單鏈表中第i個(gè)元素,并將之插入至原表中的第j個(gè)元素之前.9寫出求單鏈表長度算法intlength(linklistL)10假設(shè)將循環(huán)隊(duì)列Q的結(jié)構(gòu)定義為：#definem100最大隊(duì)列長度typedefstructQElemType*base；存儲(chǔ)空間基址intrear；尾指針,假設(shè)隊(duì)列不空,指向隊(duì)尾元素intleng

15、th；當(dāng)前隊(duì)列的長度,即元素個(gè)數(shù)SqQueue；試寫出相應(yīng)初始化、入隊(duì)列和出隊(duì)列的三個(gè)函數(shù).11二叉樹用二叉徒表存儲(chǔ)表示.typedefstructBiTNodeTelemTypedata；StructBiTNode*lchildr*rchild；BiTNode,*BiTree；試編寫銷毀二叉樹T的算法DestroyBiTree(BiTree&T)012二叉樹用二叉徒表存儲(chǔ)表示.typedefstructBiTNodeTelemTypedata；StructBiTNode*lchildt*rchild;BiTNode,*BiTree；試編寫算法,求元素值為X的結(jié)點(diǎn)的左孩子(返回X的左孩子的指針).13設(shè)計(jì)一算法,計(jì)算給定二叉樹T中度為2的結(jié)點(diǎn)個(gè)數(shù).14編一算法：按