數(shù)據(jù)結構習題

1、緒論習題(一)1. 數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址和邏輯地址相同并且是連續(xù)的，稱之為（ ）。 A. 存儲結構 B. 邏輯結構 C. 順序存儲結構 D. 鏈式存儲結構2. 每一個存儲結點不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是（ ）存儲方式。A. 順序 B. 鏈式 C. 索引 D. 散列3. 以下任何兩個結點之間都沒有邏輯關系的是（ ）。A. 圖形結構 B. 線性結構 C. 樹形結構 D. 集合4. 算法在發(fā)生非法操作時可以作出處理的特性稱為算法的（ ）。A. 正確性 B. 易讀性 C. 健壯性 D. 高效性 緒論練習（二）1.數(shù)據(jù)邏輯結構除了集合以外，還包括：線性結構、樹形結構

2、和 圖形結構 。2.樹形結構結構中的元素之間存在 一對多 的關系。3.數(shù)據(jù)結構被定義為(D，R)，其中D是數(shù)據(jù)的有限集合，R是D上的 關系 的有限集合。5.若一個算法中的語句頻度之和為T（n）=6n+3nlog2n，則算法的時間復雜度為 O(nlog2n) 。線性表習題（一）2.已知一個順序存儲的線性表，設每個結點占m個存儲單元，若第一個結點的地址為B，則第i個結點的地址為（ ）。A B+(i-1)*m BB+i*m C B-i*m D B+(i+1)*m3.兩個指針P和Q，分別指向單鏈表的兩個元素，P所指元素是Q所指元素前驅的條件是（ ）。AP-next=Q-next BP-next= Q

3、CQ-next= P DP= Q5.等概率情況下，在有n個結點的順序表上做插入結點運算，需平均移動結點的數(shù)目為（ ）。An B(n-1)/2 C n/2 D(n+1)/26.在（ ）的運算中，使用順序表比鏈表好。A插入 B根據(jù)序號查找 C 刪除 D根據(jù)元素查找線性表習題（二）1.鏈表相對于順序表的優(yōu)點是： 插入、刪除 方便。2.順序表中訪問任意一個結點的時間復雜度均為 O(1) 。3.在單鏈表中要在已知結點*P之前插入一個新結點，需找到*P的直接前趨結點的地址，其查找的時間復雜度為 O(n) 。4.單鏈表中需知道 頭指針 才能遍歷整個鏈表。5.在一個長度為n的順序表中刪除第i個元素，要移動 n

4、-i 個元素。6.在一個長度為n的順序表中，如果要在第i個元素前插入一個元素，要后移 n-i+1 個元素。7.雙鏈表中，設p是指向其中待刪除的結點，則需要執(zhí)行的操作為： p-prior-next=p-next 。 棧和隊列習題（一）1.在有n個元素的棧中，進棧操作的時間復雜度為 O(1) 。2.在棧結構中，允許插入、刪除的一端稱為 棧頂 。3.若進棧的次序是A、B、C、D、E，執(zhí)行三次出棧操作以后，棧頂元素為 B 。4.解決順序隊列“假溢出”的方法是采用 循環(huán)隊列 。5.設循環(huán)隊列的容量為40（序號從0到39），現(xiàn)經(jīng)過一系列的入隊和出隊運算后，有 front=11，rear=19，則循環(huán)隊列中

5、還有 8 個元素。6.設循環(huán)隊列的頭指針front指向隊首元素，尾指針rear指向隊尾元素后的一個空閑元素，隊列的最大空間為MAXLEN，則隊滿標志為： front=(rear+1)%MAXLEN 。棧和隊列練習（二）1.設有編號為1，2，3，4的四輛列車，順序進入一個棧結構的站臺，下列不可能的出站順序為( )A1234 B1243 C1324 D14232.從一個棧頂指針為top的鏈棧中刪除一個結點時，用x保存被刪除的結點，應執(zhí)行下列 ( )命令。 Ax=top;top=top-next; Btop=top-next;x=top-data; Cx=top-data; Dx=top-data;

6、top=top-next;3.在一個棧頂指針為HS的鏈棧中，將一個S指針所指的結點入棧，應執(zhí)行下列( )命令。 AHS-next=S; BS-next=HS-next;HS-next=S; CS-next=HS-next;HS=S; DS-next=HS;HS=HS-next;4. 設有一個順序棧S，元素A,B,C,D,E,F,依次進棧，如果六個元素出棧的順序是B，D，C，F(xiàn)，E，A，則棧的容量至少應是( )。 A3 B4 C5 D 6棧和隊列練習（二）5.若進隊的序列為：A，B，C，D，則出隊的序列是（ ）。AB，C，D，ABA，C，B，D CA，B，C，DDC，B，D，A6.四個元素按：A

7、，B，C，D順序連續(xù)進隊Q，執(zhí)行一次OutQueue(Q)操作后，隊頭元素是（ ）。A A B B C C D D8.設鏈棧中結點的結構：data為數(shù)據(jù)域，next為指針域，且top是棧頂指針。若想在鏈棧的棧頂插入一個由指針s所指的結點，則應執(zhí)行下列（ ）操作。 As-next=top-next；top-next=s； Btop-next=s； Cs-next=top；top=top-next； Ds-next=top；top=s；樹習題（一）1.不相交的樹的聚集稱之為 森林 。 2.深度為k的完全二叉樹至少有 2k-1 個結點。至多有 2k-1 個結點。3.在一棵二叉樹中，度為零的結點的個數(shù)

8、為n0，度為2的結點的個數(shù)為 n2，則有 n0=n2+1 。4.一棵有n（n0）個結點的滿二叉樹共有 (n+1)/2 個葉子和 (n-1)/2 個非終端結點。5.高度為k且有2k-1個結點的二叉樹稱為 滿 二叉樹。樹習題（一） 7. 如圖所示，二叉樹的中序遍歷是 BLEACWXD ：BCDELAXW樹習題（二）1.某二叉樹先序遍歷的結點序列是abdgcefh，中序遍歷的結點序列是dgbaechf，則其后序遍歷的結點序列是 。 A、bdgcefha B、gdbecfha C、bdgaechf D、gdbehfca2.某二叉樹后序遍歷結果為dabec,中序遍歷結果為debac,那么二叉樹的先序遍歷

9、序列是 。A. acbed B. decab C.deabc D.cedba3.高度為6的滿二叉樹，總共有的結點數(shù)是 。 A、15 B、63 C、20 D、25 4.具有10個葉結點的二叉樹中有 個度為2的結點。 A、8 B、9 C、10 D、11樹習題（三）假設用于通訊的電文僅有六個符號（a1,a2,a3,a4,a5,a6)，符號在電文中出現(xiàn)的概率分別為0.13,0.18,0.16,0.07,0.32,0.14.試為這六個字母設計哈夫曼編碼，寫出構造哈夫曼樹過程和編碼過程。圖習題（一）1.設無向圖的頂點個數(shù)為n，則該圖最多有（）條邊。A.n-1 B.n(n-1)/2 C.n(n+1)/2 D

10、.n22.一個n個頂點的連通無向圖，其邊的個數(shù)至少為（）。A.n-1 B.n C.n+1 D.2n3.有8個結點的有向完全圖有（）條邊。A.14 B. 28 C.56 D.112 4.已知圖的鄰接表如下所示，根據(jù)算法，則從頂點0出發(fā)按深度優(yōu)先遍歷的結點序列是（） A. 0 1 3 2 B.0 2 3 1 C.0 3 2 1 D. 0 1 2 3圖習題（一）5. 已知圖的鄰接表如下所示，根據(jù)算法，則從頂點0出發(fā)按廣度優(yōu)先遍歷的結點序列是（）A.0 3 2 1 B.0 1 2 3 C. 0 1 3 2 D. 0 3 1 26. 圖的深度優(yōu)先遍歷類似于二叉樹的（）。A.先序遍歷 B.中序遍歷 C.后

11、序遍歷 D.層次遍歷 圖習題（二）1. 在有向圖中，以頂點v為終點的邊的數(shù)目成為v的_入度_.3. 有n個頂點的強連通有向圖G至少有_n_條弧。4. 有向圖G用鄰接表矩陣存儲，其第i行的所有元素之和等于頂點i的_出度_.5. 圖的存儲結構表示有_鄰接矩陣_,_鄰接表_,十字鏈表、鄰接多重表等多種存儲結構。圖習題（三） 1. 已知如圖所示的有向圖，請給出該圖的： （1）每個頂點的入/出度；（2）鄰接矩陣；（3）鄰接表（4）逆鄰接表圖習題（三） 2.已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別畫出自頂點1出發(fā)進行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。圖習題（三） 1.已知已個 AOV 網(wǎng)如

12、圖所示，寫出所有拓撲序列。圖習題（三） 1.如圖所示是一個無向網(wǎng)圖，請分別按Prim算法和Kruskal算法求最小生成樹。查找習題（一）1已知一個有序表為（12，18，24，35，47，50，62，83，90，115，134），當折半查找值為 90 的元 素時，經(jīng)過（ ）次比較后查找成功。A 2 B 3C 4D 52已知 10 個元素（54，28，16，73，62，95，60，26，43），按照依次插入的方法生成一棵二叉排序樹，查找值為 62 的結點所需比較次數(shù)為（ ）。A 2B 3C 4D 53已知數(shù)據(jù)元素為（34，76，45，18，26，54，92，65），按照依次插入結點的方法生成一棵二

13、叉排序樹，則該樹的深度為（ ）。A 4B 5C 6D 74按（ ）遍歷二叉排序樹得到的序列是一個有序序列。A 前序 B 中序 C 后序 D 層次5在散列函數(shù) H(k)= k mod m 中，一般來講，m 應?。?）。A 奇數(shù) B 偶數(shù) C 素數(shù) D 充分大的數(shù)查找習題（三）1.已知關鍵碼序列為（Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec），散列表的地址空間為 016，設散列函數(shù)為 H(x)= ，其中 i 為關鍵碼中第一個字母在字母表中的序號，采用線性探測法和鏈地址法處理沖突，試分別構造散列表，并求等概率情況下查找成功的平均查找長度。排序習題（一）2.一組記錄的關鍵碼為46, 79, 56, 38, 40, 84，則利用快速排序的方法，以第一個記錄為基準得到的一 次劃分結果為（ ）。A 40, 38, 46, 56, 79, 84 B 40, 38, 46, 79, 56, 84C 40,