數(shù)據(jù)結(jié)構(gòu)總復習題JAVA

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

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

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

4、，隊滿時共有n-1個元素。25. 對于棧只能在 棧頂插入和刪除元素：對于隊列只能在隊尾 插入和 隊首刪除元素。26. 一棵深度為6的滿二叉樹有 n1+n2=0+ n2= n0-1=31 個分支結(jié)點和 26-1=32 個葉子。27. 有向圖G用鄰接表矩陣存儲，其第i行的所有元素之和等于頂點i的山 &。第 3頁，共 527.用Dijkstra算法求某一頂點到其余各頂點間的最短路徑是按路徑長度_讒埴_的次序來得到最短路徑的。29. n個頂點e條邊的圖，若采用鄰接矩陣存儲，則空間復雜度為O(n2)。二、單項選擇題1.線性表L= (a1,a2,a3, ai, an)下列說法正確的是()A. 每個

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

6、D . QU->front = = QU->rear+1(B ) 4.線性表L在 情況下適用于使用鏈式結(jié)構(gòu)實現(xiàn)。A .需經(jīng)常修改L中的結(jié)點值B .需不斷對L進行刪除插入C . L中含有大量的結(jié)點D.L中結(jié)點結(jié)構(gòu)復雜5. 從供選擇的答案中，選出應填入下面敘述?內(nèi)的最確切的解答,把相應編號寫在答卷的對應欄內(nèi)。設(shè)有4個數(shù)據(jù)元素al、a2、a3和a4,對他們分別進行棧操作或隊操作。在 進?；蜻M隊操作時，按 al、a2、a3、a4次序每次進入一個元素。假設(shè)?；蜿?的初始狀態(tài)都是空?，F(xiàn)要進行的棧操作是進棧兩次，出棧一次，再進棧兩次，出棧一次；這時，第一次出棧得到的元素是A,第二次出棧得到的元素

7、是B 是;類似地，考慮對這四個數(shù)據(jù)元素進行的隊操作是進隊兩次，出隊一次，再進隊兩次，出隊一次；這時，第一次出隊得到的元素是C ,第二次出隊得到的元素是 D。經(jīng)操作后，最后在棧中或隊中的元素還有E 個。供選擇的答案：AD:al a2 a3 a4E: 1230答案：A=() B=() C=()D=()E=()(B ) 6.有8個結(jié)點的無向圖最多有 條邊。A. 14B. 28C. 56D. 1127. 從供選擇的答案中，選出應填入下面敘述 內(nèi)的最確切的解答，把相應編 號寫在答卷的對應欄內(nèi)。棧是一種線性表，它的特點是 A。設(shè)用一維數(shù)組A1,n來表示一個棧,An為棧底，用整型變量 T指示當前棧頂位置，A

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

9、的關(guān)系C)分析算法的效率以求改進D)分析算法的易懂性和文檔性(A ) 7.在n個結(jié)點的順序表中，算法的時間復雜度是 O (1)的操作是：(A) 訪問第i個結(jié)點(14<n)和求第i個結(jié)點的直接前驅(qū)(2彳<n)(B) 在第i個結(jié)點后插入一個新結(jié)點(1目勺)(C) 刪除第i個結(jié)點(1 4勺)(D) 將n個結(jié)點從小到大排序第 5頁，共 5( C ) 8.若已知一個棧的入棧序列是1 , 2, 3,，n,其輸出序列為pl, p2, p3,，pn ,若 p1=n，則 pi 為A. i B. n=i C. n-i+1 D.不確定( A ) 9.判定一個隊列QU (最多元素為m0)為滿隊列的條件是A

10、. QU->front = = (QU->rear+1)% m0B. QU->rear QU->front 1= = m0C . QU->front = = QU->rearD . QU->front = = QU->rear+1(C ) 10.具有n(n>0)個結(jié)點的完全二叉樹的深度為 。(A)log2(n)(B ) L log2(n) J(C) - log2(n) _+1(D) log2(n)+1111.從供選擇的答案中，選出應填入下面敘述 內(nèi)的最確切的解答，把相應 編號寫在答卷的對應欄內(nèi)。二叉樹 A。在完全的二叉樹中，若一個結(jié)點沒有B

11、，則它必定是葉結(jié)點。每棵樹都能惟一地轉(zhuǎn)換成與它對應的二叉樹。由樹轉(zhuǎn)換成的二叉樹里，一 個結(jié)點N的左子女是N在原樹里對應結(jié)點的C ，而N的右子女是它在原樹里對應結(jié)點的D 。供選擇的答案A :是特殊的樹不是樹的特殊形式是兩棵樹的總稱有是只有二個根結(jié)點的樹形結(jié)構(gòu)B:左子結(jié)點右子結(jié)點左子結(jié)點或者沒有右子結(jié)點兄弟C D :最左子結(jié)點最右子結(jié)點最鄰近的右兄弟最鄰近的左兄弟最左的兄弟最右的兄弟答案：A=() B=( ) C=() D=( )(B ) 12.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和 的 倍。A. 1/2B. 1C. 2D. 413. 從供選擇的答案中，選出應填入下面敘述 內(nèi)的最

12、確切的解答，把相應 編號寫在答卷的對應欄內(nèi)。棧是一種線性表，它的特點是 A 。設(shè)用一維數(shù)組A1,n來表示一個棧， An為棧底，用整型變量 T指示當前棧頂位置，AT為棧頂元素。往棧中推入 (PUSH) 一個新元素時，變量 T的值 B ;從棧中彈出(POP) 一個元素 時，變量T的值 C 。設(shè)棧空時,有輸入序列a, b, c,經(jīng)過PUSH , POP, PUSH , PUSH , POP操作后，從棧中彈出的元素的序列是D ，變量T的值是 E 。供選擇的答案：A:先進先出后進先出進優(yōu)于出出優(yōu)于進 隨機進出B, C:加1減1 不變清0加2減2D： a,b b,c c,ab,a c,b a,cE:n+1

13、n+2n n-1n-2答案：A=() B=() C=()D=()E=()三、判斷題(x ) 1.鏈表的刪除算法很簡單，因為當刪除鏈中某個結(jié)點后，計算機會白 動地將后續(xù)的各個單元向前移動。(x ) 2.鏈表的刪除算法很簡單，因為當刪除鏈中某個結(jié)點后，計算機會白 動地將后續(xù)的各個單元向前移動。(V ) 3.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表， 是一種后進先出型結(jié)構(gòu)。( V ) 4.棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。(V) 5.若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在 n個結(jié)點的二叉樹鏈表中只 有n 1個非空指針域。(X) 6.二叉樹中每個結(jié)點的兩棵子樹的高度差等于1。

14、(x ) 7.圖的深度優(yōu)先遍歷序列是惟一的。(V) 8.用普里姆(Prim)算法求具有n個頂點e條邊的圖的最小生成樹的時 間復雜度為 O(n2);(X) 9.在線性結(jié)構(gòu)中，每個結(jié)點有且只有1個前驅(qū)結(jié)點和1個后續(xù)結(jié)點。(V) 10.數(shù)據(jù)的運算最常用的有5種，它們分別是插入、刪除、修改、查 找、排序。(x ) 11.鏈表的每個結(jié)點中都恰好包含一個指針。(x ) 12.順序表結(jié)構(gòu)適宜于進行順序存取，而鏈表適宜于進行隨機存取。(X ) 13.棧和隊列都是一種對所有插入、刪除操作限于在表的一端進行的 線性表，是一種后進先出型結(jié)構(gòu)。( V ) 14.棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。(X)

15、 15.若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個結(jié)點的二叉樹鏈表中只有n 1個空指針域。(V) 16.平衡二叉樹中每個結(jié)點的兩棵子樹的高度差等于 1。(V) 17.圖的深度優(yōu)先遍歷序列不是惟一的。(V) 18.用普里姆(Prim)算法求具有n個頂點e條邊的圖的最小生成樹的時 間復雜度為O(n2);(x) 19.對于一棵非空二叉樹，它的根結(jié)點作為第一層，則它的第i層上最多能有2i 1個結(jié)點。(V) 20.數(shù)據(jù)的運算最常用的有5種，它們分別是插入、刪除、修改、查 找、排序。四、簡單應用題1、用二元組表示的數(shù)據(jù)結(jié)構(gòu)如下，畫出其邏輯圖表示，并指出其屬于何種結(jié)構(gòu)。DS=<D,S> D=a,b,

16、c,d,e,f,g,h,S=R,R=<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>解答：af -c-dwT-gf第 9頁，共 5它是一種線性結(jié)構(gòu)。2 .設(shè) s1 = 'There is a books on the desk. ”,s2= "note:貝U Insert(s1,12,s2)和 Delete(s1,11,6)的結(jié)果分別是什么？Insert(s1,12,s2)的結(jié)果為 s1 = "There is a notebooks on the

17、desk. ”Delete(s1,11,6)的結(jié)果為 s1 = "There is a oks on the desk. ”3. 已知一棵二叉樹的先序遍歷的序列為 STUWV，中序遍歷的序列為UWTVS, 則其后序遍歷的序列是什么？解答：WUVTS4. 有一段電文“CAST CTAT CAESA”(“口”代表空格跟據(jù)每個字符的頻度構(gòu)造 其哈夫曼(Huffman )樹，給每個字符進行哈夫曼編碼。解答：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%13采用開放地

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

19、LeafCount(p->lchild )+LeafCount(p->rchild );7.假設(shè)圖用鄰接矩陣表示，設(shè)計一個算法，判定從頂點vi到頂點vj是否可達int visitedMAXVEX;void connected(AdjMaxix adj,int i,int j,int &c)(int k;if(i=j) c=1;else(k=0;c=0;while(k<adj.n && c=0)if(adj.edgesik=1 && visitedk=0)(visitedk=1;connected(adj,k,j,c);elsek+;8.

20、 寫出實現(xiàn)折半查找的算法或程序代碼。折半查找template <class ElemType,class KeyType>int BinarySearch(StaticTable<ElemType, KeyType> &R, const KeyType key)(int low = 0,high = R.m_size - 1;/low 表示所查區(qū)間的下界，high表示所查區(qū)間的上界while(low <= high) (int mid= (low + high)/2;if (R.m_data mid = key)return mid;查找成功else if

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

22、28282881818134347979797979223434818111.已知一棵二叉樹的后序遍歷的序列為 WUVTS ,中序遍歷的序列為UWTVS , 則其先序遍歷的序列是什么？解答：STUWV12 .有一段電文“BEST CTET王CSE ”(“口”代表空格)B據(jù)每個字符的頻度構(gòu)造其哈夫曼(Huffman )樹，給每個字符進行哈夫曼編碼。解答：B 000 S 001 T 01 10 E 1114.對給定的數(shù)列R=7, 16, 4, 8, 20 , 9, 6, 18, 5構(gòu)造一棵二叉排序樹，并給出按中序遍歷得到的數(shù)列 R1。解答：4, 5, 6, 7, 8, 9, 16, 18, 2014. 采用二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，寫出求二叉樹中結(jié)點總個數(shù)的算法。/求二叉樹結(jié)點的個數(shù)int Count(BTNode<char> *p)if(!p) return 0;elsereturn Count(p->lchild)+Count(p->rchild )+1;15. 假設(shè)圖用鄰接矩陣表示，設(shè)計一個算法，判定從頂點vi到頂點vj是否存在