必看!!!!!數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題及部分答案解析

1、0 一是非題1.數(shù)據(jù)結(jié)構(gòu) (應(yīng)該是抽象數(shù)據(jù)類型 )可用三元式表示（d， s，p）。其中： d 是數(shù)據(jù)對(duì)象， s是 d 上的關(guān)系， p 是對(duì)d 的基本操作集。 (f)2 簡單地說 ,數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。(t)3 判斷帶頭結(jié)點(diǎn)的非空循環(huán)單鏈表（頭指針為l ）中指針 p 所指結(jié)點(diǎn)是最后一個(gè)元素結(jié)點(diǎn)的條件是： p-next=l 。(t)4 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)具有可直接存取 ?表中任一元素的優(yōu)點(diǎn)。(f)5 線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(f)p-next= s ; s- next = p-next; 。(順序弄反了 )(f)6.在單鏈表 p 指針?biāo)附Y(jié)點(diǎn)之后插入s 結(jié)點(diǎn)的操作是

2、：7對(duì)于插入、刪除而言，線性表的鏈?zhǔn)酱鎯?chǔ)優(yōu)于順序存儲(chǔ)。(t)8. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。(f)9. 棧和隊(duì)列是操作上受限制的線性表。(t)10. 隊(duì)列是與線性表完全不同的一種數(shù)據(jù)結(jié)構(gòu)。棧和隊(duì)列是操作上受限制的線性表(f)11. 隊(duì)列是一種操作受限的線性表，凡對(duì)數(shù)據(jù)元素的操作僅限一端進(jìn)行。對(duì)列不是 (f)12. 棧和隊(duì)列也是線性表。如果需要，可對(duì)它們中的任一元素進(jìn)行操作。(f)13. 棧是限定僅在表頭進(jìn)行插入和表尾進(jìn)行刪除運(yùn)算的線性表。(f)14. 二叉樹中每個(gè)結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，而對(duì)一般的樹，則無此限制，所以，二叉樹是樹的特殊情形。 (f)15 二叉樹是一棵結(jié)點(diǎn)

3、的度最大為二的樹二叉樹和樹相互獨(dú)立 。(f)16 赫夫曼樹中結(jié)點(diǎn)個(gè)數(shù)一定是奇數(shù)。(t)17 在二叉樹的中序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其左孩子結(jié)點(diǎn)的后面。(t)18 假設(shè) b 是一棵樹， b是對(duì)應(yīng)的二叉樹。則b 的后根遍歷相當(dāng)于b 的后序遍歷后根遍歷相當(dāng)于中序遍歷 。(f)19. 通常，二叉樹的第i 層上有 2i-1 個(gè)結(jié)點(diǎn)。 應(yīng)該為 12i-1 個(gè)(f)20. 中序線索二叉樹的優(yōu)點(diǎn)是便于在中序下查找直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)。(t)21 二叉樹的先序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的前面。(t)22 由樹結(jié)點(diǎn)的先根序列和后根序列可以唯一地確定一棵樹。(t)23 鄰接多重表可以用以表

4、示無向圖，也可用以表示有向圖。 只能表示無向圖， 有向圖用十字鏈表 (f)24 可從任意有向圖中得到關(guān)于所有頂點(diǎn)的拓?fù)浯涡驇Лh(huán)圖沒有 。(f)25 有向圖的十字鏈表是將鄰接表和逆鄰接表合二為一的鏈表表示形式。(t)26 關(guān)鍵路徑是 aoe 網(wǎng)中源點(diǎn)到匯點(diǎn)的最短路徑。(f)27 連通圖 g 的生成樹是一個(gè)包含g 的所有 n 個(gè)頂點(diǎn)和 n-1 條邊的子圖。 (f)28 一個(gè)無向圖的連通分量是其極大的連通子圖。(t)29 十字鏈表可以表示無向圖，也可用以表示有向圖。(f)30 鄰接表可以表示有向圖，也可以表示無向圖。（ t ）31. 二叉排序樹的平均查找長度為o(log )。(t)32. 二叉排序樹

5、的最大查找長度與（log 2n ）同階。 (f)33 選用好的 hash 函數(shù)可避免沖突。 哈希函數(shù)有幾種處理沖突的方法(f)34 折半查找不適用于有序鏈表的查找。(t)35. 對(duì)于目前所知的排序方法，快速排序具有最好的平均性能。(t)36 對(duì)于任何待排序序列來說，快速排序均快于冒泡排序。(f)37 在最壞情況下，堆排序的時(shí)間性能是o(nlogn), 比快速排序好 (t)38 快速排序具有最好的平均時(shí)間性能，它在任何時(shí)候的時(shí)間復(fù)雜度都是o（ n log n ）。 (f)39. 字符串是數(shù)據(jù)對(duì)象特定的線性表。(t)40. 空串與空格串是相同的。(f)41. 對(duì)于一棵 m 階的 b -樹.樹中每個(gè)

6、結(jié)點(diǎn)至多有m 個(gè)關(guān)鍵字 .除根之外的所有非終端結(jié)點(diǎn)至少有 m/2 個(gè)關(guān)鍵字。 (f)42. 當(dāng)二叉排序樹是一棵平衡二叉樹時(shí)，其平均查找長度為o(log2n) 。(t)43. 廣義表的表頭和表尾都是廣義表。(f)44二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。(t)選擇題。1 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成( c)。a. 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)b. 順序組織和鏈接組織c. 線性結(jié)構(gòu)和非線性結(jié)構(gòu)d. 基本類型和組合類型2 線性表 l 在(b)情況下適于使用鏈表結(jié)構(gòu)實(shí)現(xiàn)。a. 不需修改 l 的結(jié)構(gòu)b. 需不斷對(duì) l 進(jìn)行刪除、插入c. 需經(jīng)常修改 l 中結(jié)點(diǎn)值d. l 中含有大量結(jié)點(diǎn)3 帶頭結(jié)點(diǎn)的單鏈表l 為空的

7、判斷條件是b。 帶頭結(jié)點(diǎn)的循環(huán)鏈表l 為空的判斷條件是c。a. l=nullb. l-next=nullc. l-next=ld. l!=null4 若順序表中各結(jié)點(diǎn)的查找概率不等，則可用如下策略提高順序查找的效率：若找到指定的結(jié)點(diǎn)，將該結(jié)點(diǎn)與其后繼（若存在）結(jié)點(diǎn)交換位置，使得經(jīng)常被查找的結(jié)點(diǎn)逐漸移至表尾。以下為據(jù)此策略編寫的算法，請(qǐng)選擇適當(dāng)?shù)膬?nèi)容，完成此功能。順序表的存儲(chǔ)結(jié)構(gòu)為：typedef structelemtype *elem; / 數(shù)據(jù)元素存儲(chǔ)空間， 0 號(hào)單元作監(jiān)視哨intlength; / 表長度sstable;int search_seq(sstable st,keytype

8、 key) / 在順序表 st 中順序查找關(guān)鍵字等于key 的數(shù)據(jù)元素。/若找到，則將該元素與其后繼交換位置，并返回其在表中的位置，否則為0。st.elem0.key=key;i=st.length; while(st.elemi.key!=key)f; if(g)st.elemie st.elemi+1 ；return i;a. i0b. i=0c. ist.lengthd. inext 非空，此時(shí)若要?jiǎng)h除指針p 所指的結(jié)點(diǎn)，可以通過如下方法進(jìn)行：將p 所指結(jié)點(diǎn)的后繼的元素值復(fù)制到該結(jié)點(diǎn)，然后刪除其后繼結(jié)點(diǎn)。相應(yīng)的語句序列為：p-data =p-next-data; p-next = p-n

9、ext-next;free(p -next) 換指針的同時(shí)還要交換數(shù)據(jù)3 線性表的順序存儲(chǔ)結(jié)構(gòu)是以數(shù)組下標(biāo)來表示數(shù)據(jù)元素之間的邏輯關(guān)系的。4 已知 p 是單鏈表中某一結(jié)點(diǎn)的指針，p 既不是首元結(jié)點(diǎn)也不是尾元結(jié)點(diǎn)，q 是 p 的 前 驅(qū)結(jié)點(diǎn)指針。當(dāng)刪除p 結(jié)點(diǎn)時(shí)，鏈表的鏈接可用語句（q-netx = p-next）實(shí)現(xiàn)。5 已知某樹的先根遍歷次序?yàn)閍bcdefg 后根遍歷次序?yàn)閏debgfa。若將該樹轉(zhuǎn)換為二叉樹,其后序遍歷次序?yàn)椋ǎ?。層次遍歷次序?yàn)椋ǎ? 已知某二叉樹的先序遍歷次序?yàn)閍fbcdeg 后序遍歷次序?yàn)?cedbgfa。其后序遍歷次序?yàn)椋ǎ?。層次遍歷次序?yàn)椋ǎ-17 在二叉樹的

10、第 i 層上至少有1個(gè)結(jié)點(diǎn) , 至多有 2_個(gè)結(jié)點(diǎn) ,深度為 k 的二叉樹至多有i_2_-1_個(gè)結(jié)點(diǎn) .8 對(duì)樹的遍歷有先序遍歷樹和后序遍歷樹。若以二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu),則樹的先序遍歷可借用二叉樹的遍歷算法來實(shí)現(xiàn) ,而樹的后序遍歷可借用二叉樹的中序遍歷遍歷算法來實(shí)現(xiàn)。9 設(shè)高度為 h 的二叉樹上只有度為0 和度為 2 的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少是2*h - 1，至多是滿樹。10 對(duì)任何一棵二叉樹(n0 = n2 +1t,若其終端結(jié)點(diǎn)數(shù)為)。n0.度為 2 的結(jié)點(diǎn)為n2,則 n0 與 n2 的關(guān)系為11 如果對(duì)完全二叉樹中結(jié)點(diǎn)從1 開始按層進(jìn)行編號(hào)，設(shè)最大編號(hào)為n；那么，可以斷定

11、編號(hào)為 i (i1) 的結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為 (i/2 向下取整)；所有編號(hào)（in/2 ）的結(jié)點(diǎn)為葉子結(jié)點(diǎn)。12 n個(gè)頂點(diǎn)的連通圖至少有條邊，至多有n*(n-1)/2條邊，此時(shí)即是完全圖條邊。13 對(duì)于圖的存儲(chǔ)結(jié)構(gòu)有（數(shù)組表示法）、（ 鄰接表法） (十字鏈表法) (鄰接多重表法)等方法。14 在一個(gè)無向圖的鄰接表中， 若表結(jié)點(diǎn)的個(gè)數(shù)是m，則圖中邊的條數(shù)是m/2條。15 若有序表中關(guān)鍵字序列為：12， 22， 33， 44， 55， 66， 77， 88，99 對(duì)其進(jìn)行折半查找，則在等概率情況下，查找成功時(shí)的平均查找長度是（）。查找 99 時(shí)需進(jìn)行（）次比較。16 在哈希表中，處理沖突的方法有開放

12、定址法，再哈希表法，鏈地址法等。17 在二叉樹的第i 層上至少有個(gè)結(jié)點(diǎn) , 至多有個(gè)結(jié)點(diǎn) ,深度為 k 的二叉樹至多有個(gè)結(jié)點(diǎn) .18 對(duì)于一棵高度為 k 的二叉排序樹，結(jié)點(diǎn)數(shù)最少可有個(gè)，最多可有個(gè)。19 用中序遍歷遍歷對(duì)二叉排序樹進(jìn)行訪問可得到有序序列。20 已知 hash 函數(shù)為 h （k ） =k mod 13，散列地址為 0 -14 ，用二次探測(cè)再散列處理沖突，關(guān)鍵字（ 23，34， 56，24， 75，12， 49, 52， 36， 92）的分布如圖，則平均成功的查找長度為（）、平均失敗的查找長度為（）。01234567891011121314523692563423247512492

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

14、reordertraverse(bitree t,status(*visit)(telemtype e) /先序非遞歸遍歷二叉樹。initstack ( s );push ( s,t );while ( !stackempty( s ) )while ( gettop( s, p )&_p)if (!visit (p-data ) ) return error; push(s,p-lchild);pop ( s , p );if(!stackempty(s)pop(s, p); push( s, p-rchild );return ok;26 (算法填空 )下列算法試圖完成在數(shù)組a 中搜索有無

15、關(guān)鍵字key，若有， 返回?cái)?shù)組下標(biāo) ,若無，返回 -1。在“”處填上合適的內(nèi)容,完成該算法。intbinarysearch (keytype a , int low,int high, keytype key )while(low = high) middle = (low+high) /2;if (amiddle = key)return middle;if(key amiddle)high = middle -1;elselow = middle + 1;return -1; /end of binarysearch27 (算法填空 )下列函數(shù)為堆排序中的堆調(diào)整過程（調(diào)整 h.rs 的關(guān)鍵

16、字， 使 h.rs.m 成為一小頂堆） 。請(qǐng)?jiān)凇啊碧幪钌虾线m的內(nèi)容,完成該算法。void heapadjust( heaptype h , int s , int m ) rc=h.rs;for (j=2*s;j=m;j*=2) if (jrj) +j; if (rc h.rj) break;h.rs=h.rj; s=j;h.rs =rc;/heapadjust圖示結(jié)構(gòu)題1 已知在電文中只出現(xiàn)頻率為( 5,26,7,23,20,19 ) 的個(gè)字符， 畫出你建的哈夫曼樹，并給出其哈夫曼編碼。2.已知某二叉樹的后序遍歷和中序遍歷次序分別為dbfgeca和 bdacfeg請(qǐng)畫出該二叉樹， 并為之建立

17、先序線索 沒有左子樹， 則建立該節(jié)點(diǎn)的前驅(qū)， 若沒有右子樹， 這指向該節(jié)點(diǎn)的后繼。3 已知某二叉樹的先序遍歷次序?yàn)椋篴,b,c,d,e,f,g.中序遍歷次序?yàn)椋篵,a,d,f,e,g,c畫出該二叉樹，并在該二叉樹上建立中序線索。4 某二叉樹的中序遍歷次序?yàn)閎egfdac ， 先序遍歷次序?yàn)?abdefgc 。試畫出該二叉樹，并為之建立中序線索（圖示之）。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%，請(qǐng)給出各

18、字母的哈夫曼編碼。7 將圖示森林轉(zhuǎn)換為二叉樹，并對(duì)該二叉樹先序全序線索化。adhbcef ijg klm8 將圖示森林轉(zhuǎn)換為二叉樹，并對(duì)該二叉樹中序全序線索化。1562378949 某二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)表示如下：012345678910111213141516171819abcdefghi（1） 試畫出此二叉樹的圖形表示。（2） 將此二叉樹看作森林的二叉樹表示，試將它還原為森林。10 已知某有向圖如圖所示：1） 給出其十字鏈表存儲(chǔ)結(jié)構(gòu)a2） 給出其深度優(yōu)先遍歷次序。3） 給出其廣度優(yōu)先遍歷次序。4） 給出各強(qiáng)連通分量。bcde11 設(shè)輸入序列為 20,45,30,89,70,38,6

19、2,19，依次插入到一棵 2-3 樹中(初始狀態(tài)為空)，請(qǐng)畫出該 b-樹。12 右圖為一棵 3 階 b樹。（ 20， 25） 1)畫出在該樹上插入元素15 后的 b 樹。(10， 14)（ 21）（35）2)接著，再刪除元素35，畫出刪除后的 b 樹。13 已知 hash 函數(shù)為 h （k ） =k mod 13，散列地址為 0 -14 ，用線性探測(cè)再散列處理沖突，給出關(guān)鍵字（ 56，34， 68，23， 16，70， 48， 35， 83， 12， 14， 57）在散列地址的分布。并指出平均成功的查找長度是多少?0123456789101112131414 根據(jù)插入次序（ 20， 30，70

20、， 60，10， 100，110， 90， 80。）建立平衡的二叉排序樹。15 設(shè)哈希表長為 16，哈希函數(shù)為 h(key)=key mod 13 ，用開放定址法的二次探測(cè)再散列處理沖突（ d =12， -12， 22， -22， 32， -32i ）。依次存入 12 個(gè)元素： 56， 82， 17,24,36,21,83,96,13,34,57,50 。請(qǐng)畫出它們?cè)诒碇械姆植记樾巍?6 已知待排序序列為： 25,12,9,20,7,31,24,35,17,10 ，試寫出： (1). 堆排序初始建堆 (大頂堆 )的結(jié)果；(2). 以第一個(gè)元素為樞軸的快速排序一趟掃描的結(jié)果；(3). 希爾排序第

21、一趟 (增量為 5)的結(jié)果。算法設(shè)計(jì)題1 設(shè)有一個(gè)帶頭結(jié)點(diǎn)、元素按值遞增有序的單鏈表，結(jié)點(diǎn)的類型定義如下：typedef struct lnode int data;struct lnode *next; lnode, *linklist;編寫算法，刪除其中所有值相同的多余元素結(jié)點(diǎn)2 某線性表中元素以降序排列，現(xiàn)要插入一個(gè)元素x，插入后該線性元素仍保持降序。線性表采用帶頭結(jié)點(diǎn)單鏈表方式存貯。?請(qǐng)編寫該插入算法。3 編寫在一有序順序表中插入數(shù)據(jù)元素x 的算法 insert （，）。4 寫一算法， delete(linklist &l， x) , 刪除單鏈表中所有值為x 的結(jié)點(diǎn)。單鏈表結(jié)點(diǎn)的類型定

22、義如下：typedef struct lnode int data;struct lnode *next; lnode, *linklist;5 寫一算法， contrary(linklist &l) ,對(duì)一帶頭結(jié)點(diǎn)且僅設(shè)尾指針 l 的循環(huán)單鏈表就地逆置。（即表頭變表尾，表尾變表頭。 ）6 已知線性表中的元素以值遞增有序排列， 并以帶頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)結(jié)構(gòu)。 試寫一高效的算法， 刪除表中所有值大于 mink 且小于 maxk的元素 （若表中存在這樣的元素） 同時(shí)釋放被刪結(jié)點(diǎn)空間，并分析你的算法的時(shí)間復(fù)雜度。單鏈表結(jié)點(diǎn)的類型定義如下：typedef struct lnode int data;struct lnode *next; lnode, *linklist;7 寫一算法，將帶頭結(jié)點(diǎn)的有序單鏈表a 和 b 合并成一新的有序表c。(注:不破壞 a 和 b的原有結(jié)構(gòu) .)merge(linklist a, linklist b, linklist &c )8 寫一算法 oplinklist(linklist l,int i;int j )刪除單鏈表中第i 個(gè)元素 ,并將之插入至原表中的第j 個(gè)元素之前 .9 寫出求單