數(shù)據(jù)結(jié)構(gòu)與算法模擬試題

1、一、 選擇題1.在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）A.線性結(jié)構(gòu)和非線性結(jié)構(gòu) B.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)C.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2. 單鏈表中各結(jié)點(diǎn)之間的地址（） A.必須連續(xù) B.部分必須連續(xù) C.不一定連續(xù) D.以上均不對(duì)3.在一個(gè)長(zhǎng)度為n的順序表中向第i個(gè)元素（0<i<=n+1）之前插入一個(gè)新元素時(shí)，需向后移動(dòng)（）個(gè)元素。A、n-i B、n-i+1 C、n-i-1 D、i4. 插入和刪除操作只能在一端進(jìn)行的線性表，稱(chēng)為（）。 A.隊(duì)列 B.線性表 C.棧 D.循環(huán)隊(duì)列5、隊(duì)列是僅允許在（）進(jìn)行插入，而在（）進(jìn)行刪除。()A.隊(duì)尾，隊(duì)首 B.隊(duì)尾，隊(duì)尾 C.隊(duì)首，

2、隊(duì)尾 D.隊(duì)首，隊(duì)首6.鏈表適合于（）查找。 A.順序 B.二分 C.隨機(jī) D.順序或二分7.數(shù)據(jù)的基本單位是（）。A.數(shù)據(jù)元素 B.數(shù)據(jù)結(jié)構(gòu) C.數(shù)據(jù)項(xiàng) D.數(shù)據(jù)對(duì)象8.下列哪個(gè)不是算法的特性（）。A.有窮性 B.可數(shù)性 C.可行性 D.確定性9.在表長(zhǎng)為n的順序表中進(jìn)行線性查找，它的平均查找長(zhǎng)度為（）。A.ASL=n B.ASL=(n+1)/2 C.ASL=+1 D.ASL=log2n10. 一個(gè)線性表第一個(gè)元素的存儲(chǔ)地址是320，每個(gè)元素的長(zhǎng)度為3，則第五個(gè)元素的地址是(）。A.311 B.328 C.332 D.31311.設(shè)front、rear分別為循環(huán)雙向鏈表結(jié)點(diǎn)的左指針和右指針，

3、則指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是（）。 A.P=L B.P->front=L C.P=NULL D.P->rear=L12. 已知P為單鏈表中的非首尾結(jié)點(diǎn)，刪除P結(jié)點(diǎn)的后繼結(jié)點(diǎn)Q的語(yǔ)句為（）。 A.P->NEXT=Q->NEXT;FREE(Q); B.Q->NEXT=P; FREE(Q); C.Q->NEXT=P->NEXT;FREE(Q); D.P->NEXT=S;S->NEXT=P;13.循環(huán)隊(duì)列SQ隊(duì)滿的條件是（）。 A.SQ->rear=SQ->front B. (SQ->rear+1)%MAXLE

4、N=SQ->front C.SQ->rear=0 D. SQ->front=014.一組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序的方法建立的初始堆為()。A、79，46，56，38，40，80 B、84，79，56，38，40，46C、84，79，56，46，40，38 D、84，56，79，40，46，3815.排序趟數(shù)與序列原始狀態(tài)(原始排列)有關(guān)的排序方法是（）方法。A、插入排序 B、選擇排序      C、冒泡排序    D、快速排序16.下列排序方法中，（）是穩(wěn)

5、定的排序方法。A、直接選擇排序 B、二分法插入排序C、希爾排序 D、快速排序17.數(shù)據(jù)序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中()的兩趟排序后的結(jié)果。A、選擇排序 B、冒泡排序C、插入排序 D、堆排序18.對(duì)序列(15，9，7，8，20，-1，4)進(jìn)行排序，進(jìn)行一趟排序后，數(shù)據(jù)的排列變?yōu)椋?，9，-1，8，20，7，15），則采用的是（）排序。A、選擇 B、快速C、希爾 D、冒泡19.一組待排序記錄的關(guān)鍵字為（46，79，56，38，40，84），則利用快速排序，以第一個(gè)記錄為基準(zhǔn)元素得到的一次劃分結(jié)果為（ ）。A(38,40,46,56,79,84) B、(40,3

6、8,46,79,56,84)C、(40,38,46,56,79,84)D、(40,38,46,84,56,79)20.用直接插入排序?qū)ο旅嫠膫€(gè)序列進(jìn)行排序（由小到大），元素比較次數(shù)最少的是（ ）。A、94,32,40,90,80,46,21,69 B、32,40,21,46,69,94,90,80C 21,32,46,40,80,69,90,94 D、90,69,80,46,21,32,94,4021.若用冒泡排序?qū)﹃P(guān)鍵字序列（18,16,14,12,10,8）進(jìn)行從小到大的排序，所需進(jìn)行的關(guān)鍵字比較總次數(shù)是（）。A、10 B、15 C、21 D、34 22.就排序算法所用的輔助空間而言，堆排

7、序、快速排序和歸并排序的關(guān)系（）。A、堆排序<快速排序<歸并排序 B、堆排序<歸并排序<快速排序C、堆排序>歸并排序>快速排序 D、堆排序>快速排序>歸并排序23.最小生成樹(shù)的構(gòu)造可使用（）算法。 A.Dijkstra算法 B.Prim算法 C.Haffman算法 D.Floyd算法24. 具有32個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為（）。 A. 5 B.6 C.7 D.825. 在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)中，其結(jié)點(diǎn)總數(shù)為（）。A不確定 B2n C2n+1 D2n-126.下列陳述正確的是（）。 A.二叉樹(shù)是度為2的有序樹(shù) B. 二叉樹(shù)中最多只有二棵樹(shù),且

8、有左右子樹(shù)之分 C.二叉樹(shù)必有度為2的結(jié)點(diǎn) D. 二叉樹(shù)中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無(wú)左右之分27.先序?yàn)锳，B，C的二叉樹(shù)共有（）種。 A.3 B.4 C.5 D.6 28.在樹(shù)結(jié)構(gòu)中,若結(jié)點(diǎn)B有3個(gè)兄弟,A是B的父親結(jié)點(diǎn),則A的度為()。 A.3 B.4 C.5 D.6 29.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（）倍。A、1 B、2 C、3 D、430.n個(gè)頂點(diǎn)的強(qiáng)連通圖至少有（）邊。A、n B、n-1 C、n+1 D、n (n-1)31.在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（）倍；在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（）倍。A、1/2 B、2 C、1 D

9、、432.任何一個(gè)無(wú)向連通圖的最小生成樹(shù)（）。A、只有一棵 B、一棵或多棵 C、一定有多棵 D、可能不存在33.在圖的表示法中，表示形式唯一的是（）A、鄰接矩陣表示法 B、鄰接表表示法 C、逆鄰接矩陣表示法 D、逆鄰接表表示法34.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要（）條邊。 A.n B.n+1 C.n-1 D.n+235. 在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的（）。A1/2 B2 C1 D436有7個(gè)結(jié)點(diǎn)的有向完全圖有（）邊。 A.30 B.40 C.42 D.5637.假定在一棵二叉樹(shù)中，度為2的分支結(jié)點(diǎn)個(gè)數(shù)為15，度為1的分支結(jié)點(diǎn)個(gè)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為（）

10、。A、15 B、16 C、17 D、4738.設(shè)n，m為一棵樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中根遍歷時(shí)，n在m前的條件是（）。A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孫39.某二叉樹(shù)的后序遍歷序列為：DABEC，中序遍歷序列為：DEBAC，則前序遍歷序列為（ ）。A、ACBED B、DECAB C、DEABC D、CEDBA40.將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下，從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為45的結(jié)點(diǎn)的左孩子的編號(hào)為（），右孩子的編號(hào)為（）。A、46 B、47 C、91 D、9141.某樹(shù)中，若結(jié)點(diǎn)B有4個(gè)兄弟，A是B的父親結(jié)點(diǎn)，則A的度為（）。A、3 B、

11、4 C、5 D、642.下列敘述正確的是（）A、二叉樹(shù)是度為2的有序樹(shù) B、二叉樹(shù)結(jié)點(diǎn)只有一個(gè)孩子時(shí)無(wú)左右之分 C、二叉樹(shù)中必有度為2的結(jié)點(diǎn) D、二叉樹(shù)中最多只有兩棵子樹(shù)，且有左右之分43.由帶權(quán)為9、2、5、7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹(shù)，該樹(shù)的帶樹(shù)路徑長(zhǎng)度為（）。A、23 B、37 C、46 D、4444在圖的表示方法中，表示形式是唯一的是（）。 A.鄰接表 B.逆鄰接表 C.鄰接矩陣 D.其他44.下列關(guān)鍵字序列中，構(gòu)成大根堆的是() A.5，8，1，3，9，6，2，7 B.9，8，1，7，5，6，2，33 C.9，8，6，3，5，l，2，7 D.9，8，6，7，5，1，2，3 45.

12、對(duì)序列(15，9，7，8，20，-1，4)進(jìn)行排序，進(jìn)行一趟排序后，數(shù)據(jù)的排列變?yōu)椋?，9，-1，8，20，7，15），則采用的是（）排序。A.選擇 B.快速 C.希爾 D.冒泡46.設(shè)n，m為一棵樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中根遍歷時(shí)，n在m前的條件是（）。A.n在m右方 B.n是m祖先 C.n在m左方 D.n是m子孫二、填空題1.樹(shù)和 都屬于非線性結(jié)構(gòu)。2.順序表中邏輯上相鄰的元素在物理位置上 相鄰。3.雙向鏈表有兩個(gè)指針域，一個(gè)指向前趨，另一個(gè)指向_。4.若進(jìn)棧的次序是A,B,C,D,E,寫(xiě)出兩種出棧順序_。5.隊(duì)列存取數(shù)據(jù)應(yīng)遵循的原則是_。6.有20個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，編號(hào)為7的結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)

13、為 。7.兩個(gè)序列分別為：L1=3，50，41，42，55，65，70，75，L2=3，50，41，42，65，55，.10，5，用冒泡排序法對(duì)L1和L2進(jìn)行排序，交換次數(shù)較少的是序列： 。8.在排序方法中，從無(wú)序序列中選擇關(guān)鍵字最小的記錄，與無(wú)序區(qū)（初始為空）的第一個(gè)記錄交換的排序方法，稱(chēng)為 _排序。9.有向圖的邊也稱(chēng)為 _，用鄰接矩陣存儲(chǔ)有向圖，其第i行的所有元素之和等于頂點(diǎn)i的 。10樹(shù)轉(zhuǎn)換成的二叉樹(shù)，其根結(jié)點(diǎn)的 子樹(shù)一定為空。11.二叉排序樹(shù)是一種 查找表。12.對(duì)一組記錄（50，40，95，20，15，70，60，45，80）進(jìn)行直接插入排序時(shí)，當(dāng)把第7條記錄60插入到有序表中時(shí)，為

14、尋找插入位置需比較 次。13.在樹(shù)形結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有（前驅(qū)）結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有 結(jié)點(diǎn)，其余結(jié)點(diǎn)的后繼結(jié)點(diǎn)可以_。14.在具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中，有_個(gè)空指針。15.深度為k的完全二叉樹(shù)至少有_個(gè)結(jié)點(diǎn)，至多有_個(gè)結(jié)點(diǎn)，若按自上而下，從左到右次序給結(jié)點(diǎn)從1開(kāi)始編號(hào)，則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是_。16.由a，b，c三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹(shù)，共有 種不同形態(tài)，若是構(gòu)成樹(shù)，共有_ 種形態(tài)。17.樹(shù)所對(duì)應(yīng)的二叉樹(shù)其根結(jié)點(diǎn)的 子樹(shù)一定為空。18.已知完全二叉樹(shù)的第8層有8個(gè)結(jié)點(diǎn)，則其葉結(jié)點(diǎn)數(shù)是 三、綜合應(yīng)用題。2.已知完全二叉樹(shù)的第8層有4個(gè)結(jié)點(diǎn)，請(qǐng)計(jì)算它的葉子結(jié)點(diǎn)數(shù)和總

15、結(jié)點(diǎn)數(shù)。（寫(xiě)出計(jì)算過(guò)程）。（6分）解：由題意可知，該完全二叉樹(shù)有八層，其中第一層結(jié)點(diǎn)數(shù)為：1 第二層結(jié)點(diǎn)數(shù)為：2第三層結(jié)點(diǎn)數(shù)為：4 第四層結(jié)點(diǎn)數(shù)為：8第五層結(jié)點(diǎn)數(shù)為：1 第六層結(jié)點(diǎn)數(shù)為：32 第七層結(jié)點(diǎn)數(shù)為：6 第八層結(jié)點(diǎn)數(shù)為：4因?yàn)榈诎藢咏Y(jié)點(diǎn)數(shù)為4，且為完全二叉樹(shù)，則第八層四個(gè)結(jié)點(diǎn)為葉子結(jié)點(diǎn)，第七層前兩個(gè)結(jié)點(diǎn)有子結(jié)點(diǎn)，其余62個(gè)結(jié)點(diǎn)無(wú)子結(jié)點(diǎn)，則第七層的后62個(gè)結(jié)點(diǎn)為葉子結(jié)點(diǎn)，故葉子結(jié)點(diǎn)數(shù)有4+62=66總結(jié)點(diǎn)數(shù)為1+2+4+8+16+32+64+4=1313.已知數(shù)據(jù)序列10,8,18,15,7,16，寫(xiě)出采用直接插入算法排序時(shí)，每一趟排序的結(jié)果。（6分）解：直接插入排序過(guò)程如下所示初始列：

16、（10），8,18,15,7,16 第一趟：（8,10）,18,15,7,16第二趟：（8,10,18），15,7,16 第三趟：（8,10,15,18），7,16第四趟：（7,8,10,15,18），16 第五趟：（7,8,10,15,16,18）6.一棵具有6層的滿二叉樹(shù)中結(jié)點(diǎn)數(shù)為多少？請(qǐng)寫(xiě)出計(jì)算公式。解：637.給定一個(gè)權(quán)集W=4,8,6,9,18，畫(huà)出相應(yīng)的哈夫曼樹(shù)，并計(jì)算WPL。 8.已知二叉樹(shù)的先序遍歷序列為:ABDGHCEFI,中序遍歷的序列為：GDHBAECIF。請(qǐng)完成以下各題：（1）畫(huà)出此二叉樹(shù)。（2）寫(xiě)出它的后序遍歷序列。GHABDCEFI（3）將此二叉樹(shù)看作森林的二叉樹(shù)表

17、示，試將它還原為森林。（1）（2）其后序遍歷的序列為：G H D B E I F C A （3） 8-1.對(duì)下面的帶權(quán)無(wú)向圖：124365（1）畫(huà)出鄰接矩陣。55（2）畫(huà)出它的一棵最小生成樹(shù)。 1 10 4 637 5解：（1）124365 0 5 5 0 0 0 （2）最小生成樹(shù) 5 0 1 10 0 0 邊為紅色的 5 1 0 0 4 6 0 10 0 0 3 0 0 0 4 3 0 5 0 0 6 0 5 09.有一組關(guān)鍵字14,15,30,28,5,10,寫(xiě)出冒泡排序過(guò)程的圖示。解：第一趟排序結(jié)果：14,15,28,5,10，（30）第二趟排序結(jié)果：14,15,5,10，（28,30）

18、第三趟排序結(jié)果：14,5,10，（15,28,30）第四趟排序結(jié)果：5,10，（14,15,28,30）第五趟排序結(jié)果：5，（10,14,15,28,30）第六趟排序結(jié)果：（5,10,14,15,28,30） 351325D12660181798D45710.給定一個(gè)權(quán)集W=4，5，7，8，6，12，18，試畫(huà)出相應(yīng)的哈夫曼樹(shù)，并計(jì)算其帶權(quán)徑長(zhǎng)度WPL。WPL=(12+18)*2+(6+7+8)*3+(4+5)*4=15911.假設(shè)用于通信的電文僅由A、B、C、D、E、F、G、H等8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、6、32、3、21、10。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。1

19、1-1對(duì)于下面所示的圖，求出：12345（1）畫(huà)出鄰接矩陣和鄰接表（2）求出各頂點(diǎn)的入度和出度解：（1）鄰接矩陣 1 2 3 4 5鄰接表123524354154（2）ID(1)=1,OD(1)=3;ID(2)=1,OD(2)=1;ID(3)=1,OD(3)=1;ID(4)=2,OD(4)=1;ID(5)=2,OD(5)=1;12.已知一個(gè)無(wú)向圖的頂點(diǎn)集為a,b,c,d,e，其鄰接矩陣如下，畫(huà)出草圖，寫(xiě)出從頂點(diǎn)a出發(fā)按深度優(yōu)先搜索進(jìn)行遍歷的結(jié)點(diǎn)序列。 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0解：acbed（1）（2）深度優(yōu)先搜索：a b

20、 d c e （答案不唯一） 廣度優(yōu)先搜索：a b e d c （答案不唯一）13.網(wǎng)G的鄰接矩陣如下，試畫(huà)出該圖，并畫(huà)出它的一棵最小生成樹(shù)。 0 8 10 11 0 8 0 3 0 13 10 3 0 4 0 11 0 4 0 7 0 13 0 7 02543125431解： 最小生成樹(shù)： 8 11 10 8 3 4 13 7 3 4 716.寫(xiě)出圖的一種拓?fù)湫蛄?，若在它的鄰接表存?chǔ)結(jié)構(gòu)中，每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從大到小鏈接的，則按此給出惟一一種拓?fù)湫蛄小?7.對(duì)圖中所示圖分別寫(xiě)出深度優(yōu)先遍歷和廣度優(yōu)先遍歷的項(xiàng)點(diǎn)序列 18.對(duì)圖7-21中所示圖分別用克魯斯卡爾算法和普里姆算

21、法（從頂點(diǎn)2開(kāi)始）求出其最小生成樹(shù)。： 19.根據(jù)下圖，實(shí)現(xiàn)下列功能：（1）建立圖的鄰接表；（2）輸出圖的拓?fù)湫蛄?。四、算法設(shè)計(jì)題1、單向鏈表中，在p指針?biāo)赶虻慕Y(jié)點(diǎn)前插入一個(gè)元素x,寫(xiě)出相關(guān)算法,并畫(huà)出圖形進(jìn)行描述。解：#include<stdio.h>#include<malloc.h>typedef int DataType;typedef struct node DataType data; struct node *next;Listnode;int Insert(Listnode *head,DataType a,int b)/這個(gè)是插入算法 Listnod

22、e *p,*h,*s; int k=1; p=head; h=head->next; while(h!=NULL&&k<=b-1) k+; p=h; h=h->next; if(p=NULL) printf("插入失敗"); return 0; s=(Listnode *)malloc(sizeof(Listnode); s->data=a; s->next=h; p->next=s; return 1;void main() Listnode *H,*p; int x,y; H=(Listnode*)malloc(siz

23、eof(Listnode); H->next=NULL; printf("請(qǐng)輸入將被存入鏈表中的數(shù)（0為結(jié)束）："); scanf("%d",&x); while(x!=0) p=(Listnode*)malloc(sizeof(Listnode); p->data=x; p->next=H->next; H->next=p; scanf(" %d",&x); printf("請(qǐng)輸入將被插入的數(shù):n"); scanf("%d",&x); pr

24、intf("請(qǐng)輸入將被插入的數(shù)的位置：n"); scanf("%d",&y); p=H->next; printf("插入前，鏈表："); while(p!=NULL) printf("%d",p->data); p=p->next ; if(Insert(H,x,y)/這里是調(diào)用插入算法 p=H->next; printf("插入后處理后的鏈表：n"); while(p!=NULL) printf("%d",p->data); p=p->next; printf("n"); 2、在單鏈表中刪除第i個(gè)結(jié)點(diǎn),若刪除成功返回1,否則返回0,并要求畫(huà)出圖形進(jìn)行描述。解：#include<iostream>#include<iomanip>template<class T>class SeqListpublic:T Delete(int i);T data5;int length;template<