第第頁《數(shù)據(jù)結構與算法》期末考試試題及答案一、選擇題A、94,32,40,90,80,46,21,691.在規(guī)律上可以把數(shù)據(jù)結構分A.P-NE*T=Q-NE*T;FREE(Q);B、32,40,21,46,69,94,90,80成〔A〕B.Q-NE*T=P;FREE(Q);C21,32,46,40,80,69,90,94A.線性結構和非線性結構D、90,69,80,46,21,32,94,40B.動態(tài)結構和靜態(tài)結構C.Q-NE*T=P-NE*T;FREE(Q);21.假設用冒泡排序?qū)﹃P鍵字序C.緊湊結構和非緊湊結構D.P-NE*T=S;S-NE*T=P;列〔18,16,14,12,10,8〕進行從D.內(nèi)部結構和外部結構2.單鏈表中各結點之間的地址〔C〕A.需要連續(xù)B.部分需要連續(xù)C.不肯定連續(xù)D.以上均不對3.在一個長度為n的順次表中向第i個元素〔0i=n+1〕之前插入一個新元素時，需向后移動〔B〕個元素。A、n-iB、n-i+1C、n-i-1D、i4.插入和刪除操作只能在一端進行的線性表，稱為〔C〕。A.隊列B.線性表C.棧D.循環(huán)隊列5、隊列是僅允許在〔〕進行插入，而在〔〕進行刪除。(A)A.隊尾，隊首B.隊尾，隊尾C.隊首，隊尾D.隊首，隊首6.鏈表適合于〔A〕查找。A.順次B.二分C.隨機D.順次或二分7.數(shù)據(jù)的基本單位是〔A〕。A.數(shù)據(jù)元素B.數(shù)據(jù)結構C.數(shù)據(jù)項D.數(shù)據(jù)對象8.以下哪個不是算法的特性〔B〕。A.有窮性B.可數(shù)性C.可行性D.確定性9.在表長為n的順次表中進行線性查找，它的平均查找長度為〔B〕。A.ASL=nB.ASL=(n+1)/2C.ASL=n+1D.ASL=log2n10.一個線性表第一個元素的存儲地址是320，每個元素的長度為3，那么第五個元素的地址是(C〕。A.311B.328C.332D.31311.設front、rear分別為循環(huán)雙向鏈表結點的左指針和右指針，那么指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是〔D〕。A.P==LB.P-front==LC.P==NULLD.P-rear==L12.已知P為單鏈表中的非首尾結點，刪除P結點的后繼結點Q的語句為〔A〕。

13.循環(huán)隊列SQ隊滿的條件是〔B〕。A.SQ-rear==SQ-frontB.(SQ-rear+1)%MA*LEN==SQ-frontC.SQ-rear==0D.SQ-front==014.一組記錄的排序碼為〔46，79，56，38，40，84〕，那么利用堆排序的方法建立的初始堆為(B)。A、79，46，56，38，40，80B、84，79，56，38，40，46C、84，79，56，46，40，38D、84，56，79，40，46，3815.排序趟數(shù)與序列原始狀態(tài)(原始排列)有關的排序方法是〔ACD〕方法。A、插入排序B、選擇排序C、冒泡排序D、快速排序16.以下排序方法中，〔B〕是穩(wěn)定的排序方法。A、徑直選擇排序B、二分法插入排序C、希爾排序D、快速排序17.數(shù)據(jù)序列〔8，9，10，4，5，6，20，1，2〕只能是以下排序算法中(C)的兩趟排序后的結果。A、選擇排序B、冒泡排序C、插入排序D、堆排序18.對序列(15，9，7，8，20，-1，4)進行排序，進行一趟排序后，數(shù)據(jù)的排列變?yōu)椤?，9，-1，8，20，7，15〕，那么采納的是〔C〕排序。A、選擇B、快速C、希爾D、冒泡19.一組待排序記錄的關鍵字為〔46，79，56，38，40，84〕，那么利用快速排序，以第一個記錄為基準元素得到的一次劃分結果為〔C〕。A(38,40,46,56,79,84)B、(40,38,46,79,56,84)C、(40,38,46,56,79,84)D、(40,38,46,84,56,79)20.用徑直插入排序?qū)ο旅嫠膫€序列進行排序〔由小到大〕，元素比較次數(shù)最少的是〔C〕。小到大的排序，所需進行的關鍵字比較總次數(shù)是〔B〕。A、10B、15C、21

D、3422.就排序算法所用的幫助空間而言，堆排序、快速排序和歸并排序的關系〔A〕。A、堆排序快速排序歸并排序B、堆排序歸并排序快速排序C、堆排序歸并排序快速排序D、堆排序快速排序歸并排序23.最小生成樹的構造可運用〔B〕算法。A.Dijkstra算法

B.Prim算法C.Haffman算法D.Floyd算法24.具有32個結點的完全二叉樹的深度為〔B〕。A.5B.6C.7

D.825.在有n個葉子結點的哈夫曼樹中，其結點總數(shù)為〔D〕。A．不確定B．2nC．2n+1D．2n-126.以下陳述正確的選項是〔B〕。A.二叉樹是度為2的有序樹B.二叉樹中最多只有二棵樹,且有左右子樹之分C.二叉樹必有度為2的結點D.二叉樹中結點只有一個孩子時無左右之分27.先序為A，B，C的二叉樹共有〔A〕種。A.3B.4C.5D.628.在樹結構中,假設結點B有3個兄弟,A是B的父親結點,那么A

的度為(B)。

A.3B.4C.5D.629.在一個圖中，全部頂點的度數(shù)之和等于全部邊數(shù)的〔B〕倍。A、1B、2C、3D、430.n個頂點的強連通圖至少有〔A〕邊。A、nB、n-1C、n+1D、n(n-1)31.在一個無向圖中，全部頂點的度數(shù)之和等于全部邊數(shù)的〔C〕倍；在一個有向圖中，全部頂點的入度之和等于全部頂點出度之和的〔C〕倍。A、1/2B、2C、1

D、4無左右之分無序區(qū)〔初始為空〕的第一個32.任何一個無向連通圖的最C、二叉樹中必有度為2的結點記錄交換的排序方法，稱為選小生成樹〔B〕。A、只有一棵B、一棵或多棵C、肯定有多棵D、可能不存在33.在圖的表示法中，表示形式唯一的是〔A〕A、鄰接矩陣表示法B、鄰接表表示法C、逆鄰接矩陣表示法D、逆鄰接表表示法34.在一個具有n個頂點的無向圖中，要連通全部頂點至少需要〔C〕條邊。A.nB.n+1C.n-1D.n+235.在一個圖中，全部頂點的度數(shù)之和等于圖的邊數(shù)的〔B〕。A．1/2B．2C．1D．436．有7個結點的有向完全圖有〔C〕邊。A.30B.40C.42D.5637.假定在一棵二叉樹中，度為2的分支結點個數(shù)為15，度為1的分支結點個數(shù)為30個，那么葉子結點數(shù)為〔B〕。A、15B、16C、17D、4738.設n，m為一棵樹上的兩個結點，在中根遍歷時，n在m前的條件是〔C〕。A、n在m右方B、n是m祖先C、n在m左方D、n是m子孫39.某二叉樹的后序遍歷序列為：DABEC，中序遍歷序列為：DEBAC，那么前序遍歷序列為〔D〕。A、ACBEDB、DECABC、DEABCD、CEDBA40.將一棵有100個結點的完全二叉樹從上到下，從左到右依次對結點編號，根結點的編號為1，那么編號為45的結點的左孩子的編號為〔90〕，右孩子的編號為〔91〕。A、46B、47C、91D、9141.某樹中，假設結點B有4個兄弟，A是B的父親結點，那么A的度為〔C〕。A、3B、4C、5D、642.以下表達正確的選項是〔D〕A、二叉樹是度為2的有序樹B、二叉樹結點只有一個孩子時D、二叉樹中最多只有兩棵子樹，且有左右之分43.由帶權為9、2、5、7的四個葉子結點構造一棵哈夫曼樹，該樹的帶樹路徑長度為〔D〕。A、23B、37C、46D、4444．在圖的表示方法中，表示形式是唯一的是〔C〕。A.鄰接表B.逆鄰接表C.鄰接矩陣D.其他44.以下關鍵字序列中，構成大根堆的是(D)A.5，8，1，3，9，6，2，7B.9，8，1，7，5，6，2，33C.9，8，6，3，5，l，2，7D.9，8，6，7，5，1，2，345.對序列(15，9，7，8，20，-1，4)進行排序，進行一趟排序后，數(shù)據(jù)的排列變?yōu)椤?，9，-1，8，20，7，15〕，那么采納的是〔C〕排序。A.選擇B.快速C.希爾D.冒泡46.設n，m為一棵樹上的兩個結點，在中根遍歷時，n在m前的條件是〔C〕。A.n在m右方B.n是m祖先C.n在m左方D.n是m子孫二、填空題1.樹和圖都屬于非線性結構。2.順次表中規(guī)律上相鄰的元素在物理位置上也相鄰。3.雙向鏈表有兩個指針域，一個指向前趨，另一個指向__后繼__。4.假設進棧的次序是A,B,C,D,E,寫出兩種出棧順次_ABCDE、EDCBA。5.隊列存取數(shù)據(jù)應遵循的原那么是先進先出。6.有20個結點的完全二叉樹，編號為7的結點的父結點編號為3。7.兩個序列分別為：L1={3，50，41，42，55，65，70，75}，L2={3，50，41，42，65，55，.10，5}，用冒泡排序法對L1和L2進行排序，交換次數(shù)較少的是序列：L1。8.在排序方法中，從無序序列中選擇關鍵字最小的記錄，與擇排序。9.有向圖的邊也稱為弧，用鄰接矩陣存儲有向圖，其第i行的全部元素之和等于頂點i的出度。10．樹轉(zhuǎn)換成的二叉樹，其根結點的右子樹肯定為空。11.二叉排序樹是一種動態(tài)查找表。12.對一組記錄〔50，40，95，20，15，70，60，45，80〕進行徑直插入排序時，當把第7條記錄60插入到有序表中時，為查找插入位置需比較15次。13.在樹形結構中，樹根結點沒有〔前驅(qū)〕結點，其余每個結點有且只有1個前驅(qū)結點；葉子結點沒有后繼結點，其余結點的后繼結點可以任意多個。14.在具有n個結點的二叉樹中，有n+1個空指針。15.深度為k的完全二叉樹至

少有2k-1個結點，至多有2k

-1個結點，假設按自上而下，從左到右次序給結點從1開始編號，那么編號最小的葉子結點的編號是。16.由a，b，c三個結點構成的二叉樹，共有30種不同形態(tài)，假設是構成樹，共有9種形態(tài)。17.樹所對應的二叉樹其根結點的右子樹肯定為空。18.已知完全二叉樹的第8層有8個結點，那么其葉結點數(shù)是68三、綜合應用題。2.已知完全二叉樹的第8層有4個結點，請計算它的葉子結點數(shù)和總結點數(shù)。〔寫出計算過程〕。〔6分〕解：由題意可知，該完全二叉樹有八層，其中第一層結點數(shù)為：1第二層結點數(shù)為：2第三層結點數(shù)為：4第四層結點數(shù)為：8第五層結點數(shù)為：16第六層結點數(shù)為：32第七層結點數(shù)為：64第八層結點數(shù)為：4由于第八層結點數(shù)為4，且為完全二叉樹，那么第八層四個結點為葉子結點，第七層前兩個結點有子結點，其余62個結點無子結點，那么第七層的后62個結點為葉子結點，故葉子結點數(shù)有4+62=66總結點數(shù)為1+2+4+8+16+32+64+4=131

一、選擇題A、94,32,40,90,80,46,21,691.在規(guī)律上可以把數(shù)據(jù)結構分A.P-NE*T=Q-NE*T;FREE(Q);B、32,40,21,46,69,94,90,80成〔A〕B.Q-NE*T=P;FREE(Q);C21,32,46,40,80,69,90,94A.線性結構和非線性結構D、90,69,80,46,21,32,94,40B.動態(tài)結構和靜態(tài)結構C.Q-NE*T=P-NE*T;FREE(Q);21.假設用冒泡排序?qū)﹃P鍵字序C.緊湊結構和非緊湊結構D.P-NE*T=S;S-NE*T=P;列〔18,16,14,12,10,8〕進行從D.內(nèi)部結構和外部結構2.單鏈表中各結點之間的地址〔C〕A.需要連續(xù)B.部分需要連續(xù)C.不肯定連續(xù)D.以上均不對3.在一個長度為n的順次表中向第i個元素〔0i=n+1〕之前插入一個新元素時，需向后移動〔B〕個元素。A、n-iB、n-i+1C、n-i-1D、i4.插入和刪除操作只能在一端進行的線性表，稱為〔C〕。A.隊列B.線性表C.棧D.循環(huán)隊列5、隊列是僅允許在〔〕進行插入，而在〔〕進行刪除。(A)A.隊尾，隊首B.隊尾，隊尾C.隊首，隊尾D.隊首，隊首6.鏈表適合于〔A〕查找。A.順次B.二分C.隨機D.順次或二分7.數(shù)據(jù)的基本單位是〔A〕。A.數(shù)據(jù)元素B.數(shù)據(jù)結構C.數(shù)據(jù)項D.數(shù)據(jù)對象8.以下哪個不是算法的特性〔B〕。A.有窮性B.可數(shù)性C.可行性D.確定性9.在表長為n的順次表中進行線性查找，它的平均查找長度為〔B〕。A.ASL=nB.ASL=(n+1)/2C.ASL=n+1D.ASL=log2n10.一個線性表第一個元素的存儲地址是320，每個元素的長度為3，那么第五個元素的地址是(C〕。A.311B.328C.332D.31311.設front、rear分別為循環(huán)雙向鏈表結點的左指針和右指針，那么指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是〔D〕。A.P==LB.P-front==LC.P==NULLD.P-rear==L12.已知P為單鏈表中的非首尾結點，刪除P結點的后繼結點Q的語句為〔A〕。

13.循環(huán)隊列SQ隊滿的條件是〔B〕。A.SQ-rear==SQ-frontB.(SQ-rear+1)%MA*LEN==SQ-frontC.SQ-rear==0D.SQ-front==014.一組記錄的排序碼為〔46，79，56，38，40，84〕，那么利用堆排序的方法建立的初始堆為(B)。A、79，46，56，38，40，80B、84，79，56，38，40，46C、84，79，56，46，40，38D、84，56，79，40，46，3815.排序趟數(shù)與序列原始狀態(tài)(原始排列)有關的排序方法是〔ACD〕方法。A、插入排序B、選擇排序C、冒泡排序D、快速排序16.以下排序方法中，〔B〕是穩(wěn)定的排序方法。A、徑直選擇排序B、二分法插入排序C、希爾排序D、快速排序17.數(shù)據(jù)序列〔8，9，10，4，5，6，20，1，2〕只能是以下排序算法中(C)的兩趟排序后的結果。A、選擇排序B、冒泡排序C、插入排序D、堆排序18.對序列(15，9，7，8，20，-1，4)進行排序，進行一趟排序后，數(shù)據(jù)的排列變?yōu)椤?，9，-1，8，20，7，15〕，那么采納的是〔C〕排序。A、選擇B、快速C、希爾D、冒泡19.一組待排序記錄的關鍵字為〔46，79，56，38，40，84〕，那么利用快速排序，以第一個記錄為基準元素得到的一次劃分結果為〔C〕。A(38,40,46,56,79,84)B、(40,38,46,79,56,84)C、(40,38,46,56,79,84)D、(40,38,46,84,56,79)20.用徑直插入排序?qū)ο旅嫠膫€序列進行排序〔由小到大〕，元素比較次數(shù)最少的是〔C〕。小到大的排序，所需進行的關鍵字比較總次數(shù)是〔B〕。A、10B、