大學(xué)《數(shù)據(jù)結(jié)構(gòu)》期末復(fù)習(xí)試題庫及答案(JAVA)

1、PAGE PAGE 一、填空題1. 棧和隊(duì)列的共同特點(diǎn)是（只允許在端點(diǎn)處插入和刪除元素）。2. 在深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為（31）3. 算法分析的目的是（分析算法的效率以求改進(jìn)）。4. 由兩個(gè)棧共享一個(gè)存儲(chǔ)空間的好處是（節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率）。5.串的長度是（串中所含字符的個(gè)數(shù)） 。6.設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)位置的運(yùn)算稱做（模式匹配）7. N個(gè)頂點(diǎn)的連通圖中邊的條數(shù)至少為（N-1）。8.N個(gè)頂點(diǎn)的強(qiáng)連通圖的邊數(shù)至少有（N）。9.對(duì)長度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為（N）。P25910.假設(shè)線性表的長度為n，則在最壞情況下，冒泡排

2、序需要的比較次數(shù)為（n(n-1)/2） 。P29211. 在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的前驅(qū)結(jié)點(diǎn)的地址，其時(shí)間復(fù)雜度為O（n）。12. 在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有 n-1 個(gè)元素。13. 有向圖G用鄰接表矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的 出度 。14. 用Dijkstra算法求某一頂點(diǎn)到其余各頂點(diǎn)間的最短路徑是按路徑長度 遞增 的次序來得到最短路徑的。15. 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以 任意多個(gè) 。16在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的 前一個(gè) 位置。17在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng) 表中一半元素，具體移動(dòng)

3、的元素個(gè)數(shù)與 表長和該元素在表中的位置 有關(guān)。18. 線性表中結(jié)點(diǎn)的集合是 有限 的，結(jié)點(diǎn)間的關(guān)系是 一對(duì)一 的。19.數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R），其中D是 數(shù)據(jù)元素 的有限集合，R是D上的 關(guān)系 有限集合。20. 線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。21. 一個(gè)算法的效率可分為 時(shí)間 效率和 空間 效率。22. 在順序表中訪問任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為 O(1) ，因此，順序表也稱為 隨機(jī)存取 的數(shù)據(jù)結(jié)構(gòu)。23. 在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的前驅(qū)結(jié)點(diǎn)的地址，其時(shí)間復(fù)雜度為O（n）。24. 在具有n

4、個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有 n-1 個(gè)元素。25. 對(duì)于棧只能在 棧頂 插入和刪除元素；對(duì)于隊(duì)列只能在 隊(duì)尾 插入和 隊(duì)首 刪除元素。26. 一棵深度為6的滿二叉樹有 n1+n2=0+ n2= n0-1=31 個(gè)分支結(jié)點(diǎn)和 26-1 =32 個(gè)葉子。27. 有向圖G用鄰接表矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的 出度 。27. 用Dijkstra算法求某一頂點(diǎn)到其余各頂點(diǎn)間的最短路徑是按路徑長度 遞增 的次序來得到最短路徑的。29. n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接矩陣存儲(chǔ)，則空間復(fù)雜度為 O(n2) 。二、單項(xiàng)選擇題1. 線性表L（a1,a2,a3,ai,an），下列說法正確的是（）

5、 A.每個(gè)元素都有一個(gè)直接前件和直接后件 B.線性表中至少要有一個(gè)元素C.表中諸元素的排列順序必須是由小到大或由大到小D.除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且只有一個(gè)直接前趨和直接后繼（ A ）2. 算法分析的兩個(gè)主要方面是：A) 空間復(fù)雜性和時(shí)間復(fù)雜性 B) 正確性和簡(jiǎn)明性C) 可讀性和文檔性 D) 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性（ A ）3.判定一個(gè)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是 QU-front = = (QU-rear+1)% m0 QU-rear QU-front 1= = m0 QU-front = = QU-rear QU-front = = QU-rear+1（

6、 B ）4 線性表在 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。.需經(jīng)常修改中的結(jié)點(diǎn)值 .需不斷對(duì)進(jìn)行刪除插入 .中含有大量的結(jié)點(diǎn) .中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜5. 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。設(shè)有4個(gè)數(shù)據(jù)元素a1、a2、a3和a4，對(duì)他們分別進(jìn)行棧操作或隊(duì)操作。在進(jìn)?；蜻M(jìn)隊(duì)操作時(shí)，按a1、a2、a3、a4次序每次進(jìn)入一個(gè)元素。假設(shè)?；蜿?duì)的初始狀態(tài)都是空?，F(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次，出棧一次，再進(jìn)棧兩次，出棧一次；這時(shí)，第一次出棧得到的元素是 A ，第二次出棧得到的元素是 B 是；類似地，考慮對(duì)這四個(gè)數(shù)據(jù)元素進(jìn)行的隊(duì)操作是進(jìn)隊(duì)兩次，出隊(duì)一次，再進(jìn)隊(duì)兩次，出

7、隊(duì)一次；這時(shí)，第一次出隊(duì)得到的元素是 C ，第二次出隊(duì)得到的元素是 D 。經(jīng)操作后，最后在棧中或隊(duì)中的元素還有 E 個(gè)。供選擇的答案：AD：a1 a2 a3 a4E： 1 2 3 0答案：A=（） B=（ ） C= （ ） D（ ） E=（） （ B ）6. 有8個(gè)結(jié)點(diǎn)的無向圖最多有 條邊。 A14 B. 28 C. 56 D. 112 7從供選擇的答案中，選出應(yīng)填入下面敘述 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。棧是一種線性表，它的特點(diǎn)是 A 。設(shè)用一維數(shù)組A1,n來表示一個(gè)棧，An為棧底，用整型變量T指示當(dāng)前棧頂位置，AT為棧頂元素。往棧中推入（PUSH）一個(gè)新元素時(shí)，變量T的值

8、 B ；從棧中彈出（POP）一個(gè)元素時(shí)，變量T的值 C 。設(shè)?？諘r(shí)，有輸入序列a，b，c，經(jīng)過PUSH，POP，PUSH，PUSH，POP操作后，從棧中彈出的元素的序列是 D ，變量T的值是 E 。供選擇的答案：A： 先進(jìn)先出 后進(jìn)先出 進(jìn)優(yōu)于出 出優(yōu)于進(jìn) 隨機(jī)進(jìn)出B，C： 加1 減1 不變 清0 加2 減2D： a,b b,c c,ab,a c,b a,cE： n+1 n+2 n n-1 n-2答案：A=（） B=（） C= （ ） D（） E=（）（ C ）6. 算法分析的目的是：A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 研究算法中的輸入和輸出的關(guān)系C) 分析算法的效率以求改進(jìn) D) 分析算法的易

9、懂性和文檔性（ A ）7. 在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O（1）的操作是：訪問第i個(gè)結(jié)點(diǎn)（1in）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2in） 在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1in）刪除第i個(gè)結(jié)點(diǎn)（1in）將n個(gè)結(jié)點(diǎn)從小到大排序（ C ）8.若已知一個(gè)棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為i n=i n-i+1 不確定（ A ）9.判定一個(gè)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是 QU-front = = (QU-rear+1)% m0 QU-rear QU-front 1= = m0 QU-front = = QU-rear QU-fron

10、t = = QU-rear+1（ C ）10. 具有n(n0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 。() log2(n) () log2(n) () log2(n) +1 () log2(n)+111.從供選擇的答案中，選出應(yīng)填入下面敘述 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。二叉樹 A 。在完全的二叉樹中，若一個(gè)結(jié)點(diǎn)沒有 B ，則它必定是葉結(jié)點(diǎn)。每棵樹都能惟一地轉(zhuǎn)換成與它對(duì)應(yīng)的二叉樹。由樹轉(zhuǎn)換成的二叉樹里，一個(gè)結(jié)點(diǎn)N的左子女是N在原樹里對(duì)應(yīng)結(jié)點(diǎn)的 C ，而N的右子女是它在原樹里對(duì)應(yīng)結(jié)點(diǎn)的 D 。供選擇的答案A： 是特殊的樹 不是樹的特殊形式 是兩棵樹的總稱 有是只有二個(gè)根結(jié)點(diǎn)的樹形結(jié)構(gòu) B

11、: 左子結(jié)點(diǎn) 右子結(jié)點(diǎn) 左子結(jié)點(diǎn)或者沒有右子結(jié)點(diǎn) 兄弟CD： 最左子結(jié)點(diǎn) 最右子結(jié)點(diǎn) 最鄰近的右兄弟 最鄰近的左兄弟 最左的兄弟 最右的兄弟答案：A=（） B=（ ） C= （ ） D（ ） （ B ）12. 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 倍。 A1/2 B. 1 C. 2 D. 4 13從供選擇的答案中，選出應(yīng)填入下面敘述 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。棧是一種線性表，它的特點(diǎn)是 A 。設(shè)用一維數(shù)組A1,n來表示一個(gè)棧，An為棧底，用整型變量T指示當(dāng)前棧頂位置，AT為棧頂元素。往棧中推入（PUSH）一個(gè)新元素時(shí)，變量T的值 B ；從棧中彈出（P

12、OP）一個(gè)元素時(shí)，變量T的值 C 。設(shè)?？諘r(shí)，有輸入序列a，b，c，經(jīng)過PUSH，POP，PUSH，PUSH，POP操作后，從棧中彈出的元素的序列是 D ，變量T的值是 E 。供選擇的答案：A： 先進(jìn)先出 后進(jìn)先出 進(jìn)優(yōu)于出 出優(yōu)于進(jìn) 隨機(jī)進(jìn)出B，C： 加1 減1 不變 清0 加2 減2D： a,b b,c c,ab,a c,b a,cE： n+1 n+2 n n-1 n-2答案：A=（） B=（） C= （ ） D（） E=（）三、判斷題（ ）1. 鏈表的刪除算法很簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)的各個(gè)單元向前移動(dòng)。（ ）2. 鏈表的刪除算法很簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)

13、后，計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)的各個(gè)單元向前移動(dòng)。（ ）3. 棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。（ ）4. 棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。（ ）5. 若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹鏈表中只有n1個(gè)非空指針域。（ ）6.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于1。 （ ）7. 圖的深度優(yōu)先遍歷序列是惟一的。（ ）8用普里姆(Prim)算法求具有n個(gè)頂點(diǎn)e條邊的圖的最小生成樹的時(shí)間復(fù)雜度為 O(n2) ；（ ）9在線性結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)有且只有 1個(gè)前驅(qū)結(jié)點(diǎn)和1個(gè)后續(xù)結(jié)點(diǎn)。（ ）10. 數(shù)據(jù)的運(yùn)算最常用的有5種，它們分別是插

14、入 、 刪除、修改、 查找 、排序。（ ）11. 鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。 （ ）12. 順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。 （ ）13. 棧和隊(duì)列都是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。（ ）14. 棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。（ ）15. 若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹鏈表中只有n1個(gè)空指針域。（ ）16.平衡二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于1。 （ ）17. 圖的深度優(yōu)先遍歷序列不是惟一的。（ ）18用普里姆(Prim)算法求具有n個(gè)頂點(diǎn)e條邊的圖的最小生成樹的時(shí)間復(fù)雜

15、度為 O(n2) ；（ ）19.對(duì)于一棵非空二叉樹，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有2i1個(gè)結(jié)點(diǎn)。（ ）20. 數(shù)據(jù)的運(yùn)算最常用的有5種，它們分別是插入 、 刪除、修改、 查找 、排序。四、簡(jiǎn)單應(yīng)用題用二元組表示的數(shù)據(jù)結(jié)構(gòu)如下，畫出其邏輯圖表示，并指出其屬于何種結(jié)構(gòu)。DS= D=a,b,c,d,e,f,g,h,S=R,R=,解答：abcdefgh它是一種線性結(jié)構(gòu)。2設(shè)s1=”There is a books on the desk.”,s2=”note”,則Insert(s1,12,s2)和Delete(s1,11,6)的結(jié)果分別是什么？Insert(s1,12,s2)的結(jié)果為s1

16、=”There is a notebooks on the desk.”Delete(s1,11,6)的結(jié)果為s1=”There is a oks on the desk.”3.已知一棵二叉樹的先序遍歷的序列為STUWV，中序遍歷的序列為UWTVS，則其后序遍歷的序列是什么？解答：WUVTS4有一段電文“CASTTATASA” （“”代表空格），根據(jù)每個(gè)字符的頻度構(gòu)造其哈夫曼（Huffman）樹，給每個(gè)字符進(jìn)行哈夫曼編碼。解答：C 000 S 001 T 01 10 A 115設(shè)有一組關(guān)鍵字19,1,23,14,55,20,84,27,68,11,10,77,采用散列函數(shù)：H(key)=key

17、%13采用開放地址法的線性探測(cè)再散列方法解決沖突，試在018的散列地址空間中對(duì)該關(guān)鍵字序列構(gòu)造散列表。解答：0123456789101112131415161718114552768192084231110776.采用二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，寫出求二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)并打印出葉子結(jié)點(diǎn)的算法。/求葉子結(jié)點(diǎn)的個(gè)數(shù)并打印出葉子結(jié)點(diǎn)int LeafCount(BTNode *p)if(!p) return 0;else if(!p-lchild &!p-rchild ) Print(p-data );return 1;else return LeafCount(p-lchild )+LeafCo

18、unt(p-rchild );7.假設(shè)圖用鄰接矩陣表示,設(shè)計(jì)一個(gè)算法,判定從頂點(diǎn)vi到頂點(diǎn)vj是否可達(dá)。int visitedMAXVEX;void connected(AdjMaxix adj,int i,int j,int &c)int k;if(i=j) c=1;elsek=0;c=0;while(kadj.n & c=0)if(adj.edgesik=1 & visitedk=0)visitedk=1;connected(adj,k,j,c);elsek+;8.寫出實(shí)現(xiàn)折半查找的算法或程序代碼。/折半查找template int BinarySearch(StaticTable &R,

19、 const KeyType key)int low = 0,high = R.m_size - 1; /low表示所查區(qū)間的下界，high表示所查區(qū)間的上界while(low key) high = mid-1; /在前半?yún)^(qū)間繼續(xù)查找else low = mid +1; /在后半?yún)^(qū)間繼續(xù)查找return -1; /查找失敗9.用二元組表示的數(shù)據(jù)結(jié)構(gòu)如下，畫出其邏輯圖表示，并指出其屬于何種結(jié)構(gòu)。DS= D=a,b,c,d,e,f ,S=R1,R2,R1=,R2=,解答：(樹略)它是一種樹性結(jié)構(gòu)。10描述34，28，81，79，22進(jìn)行簡(jiǎn)單排序的過程。初始 第一趟 第二趟第三趟 第四趟34 32

20、 22 22 2228 28 28 28 2881 81 81 34 3479 79 79 79 7922 34 34 81 8111.已知一棵二叉樹的后序遍歷的序列為WUVTS，中序遍歷的序列為UWTVS，則其先序遍歷的序列是什么？解答：STUWV12有一段電文“BESTTETESE” （“”代表空格），根據(jù)每個(gè)字符的頻度構(gòu)造其哈夫曼（Huffman）樹，給每個(gè)字符進(jìn)行哈夫曼編碼。解答：B 000 S 001 T 01 10 E 1114對(duì)給定的數(shù)列R=7，16，4，8，20，9，6，18，5構(gòu)造一棵二叉排序樹，并給出按中序遍歷得到的數(shù)列R1。解答：4，5，6，7，8，9，16，18，2014.采用二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，寫出求二叉樹中結(jié)點(diǎn)總個(gè)數(shù)的算法。/求二叉樹結(jié)點(diǎn)的個(gè)數(shù)int Count(BTNode *p)if(!p) return 0;elsereturn Count(p-lchild)+Co