數(shù)據(jù)結(jié)構(gòu)習(xí)題

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

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

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

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

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

6、top=top-next;3.在一個(gè)棧頂指針為HS的鏈棧中，將一個(gè)S指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行下列( )命令。 AHS-next=S; BS-next=HS-next;HS-next=S; CS-next=HS-next;HS=S; DS-next=HS;HS=HS-next;4. 設(shè)有一個(gè)順序棧S，元素A,B,C,D,E,F,依次進(jìn)棧，如果六個(gè)元素出棧的順序是B，D，C，F(xiàn)，E，A，則棧的容量至少應(yīng)是( )。 A3 B4 C5 D 6棧和隊(duì)列練習(xí)（二）5.若進(jìn)隊(duì)的序列為：A，B，C，D，則出隊(duì)的序列是（ ）。AB，C，D，ABA，C，B，D CA，B，C，DDC，B，D，A6.四個(gè)元素按：A

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

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

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

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

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

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

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