《數(shù)據(jù)結(jié)構(gòu)與算法》期末考試試題及答案

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

13.循環(huán)隊(duì)列SQ隊(duì)滿的條件是〔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)(原始排列)有關(guān)的排序方法是〔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)的兩趟排序后的結(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〕，那么采納的是〔C〕排序。A、選擇B、快速C、希爾D、冒泡19.一組待排序記錄的關(guān)鍵字為〔46，79，56，38，40，84〕，那么利用快速排序，以第一個(gè)記錄為基準(zhǔn)元素得到的一次劃分結(jié)果為〔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ū)ο旅嫠膫€(gè)序列進(jìn)行排序〔由小到大〕，元素比較次數(shù)最少的是〔C〕。小到大的排序，所需進(jìn)行的關(guān)鍵字比較總次數(shù)是〔B〕。A、10B、15C、21

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

B.Prim算法C.Haffman算法D.Floyd算法24.具有32個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為〔B〕。A.5B.6C.7

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

的度為(B)。

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

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

少有2k-1個(gè)結(jié)點(diǎn)，至多有2k

-1個(gè)結(jié)點(diǎn)，假設(shè)按自上而下，從左到右次序給結(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ù)，共有30種不同形態(tài)，假設(shè)是構(gòu)成樹(shù)，共有9種形態(tài)。17.樹(shù)所對(duì)應(yīng)的二叉樹(shù)其根結(jié)點(diǎn)的右子樹(shù)肯定為空。18.已知完全二叉樹(shù)的第8層有8個(gè)結(jié)點(diǎn)，那么其葉結(jié)點(diǎn)數(shù)是68三、綜合應(yīng)用題。2.已知完全二叉樹(shù)的第8層有4個(gè)結(jié)點(diǎn)，請(qǐng)計(jì)算它的葉子結(jié)點(diǎn)數(shù)和總結(jié)點(diǎn)數(shù)。〔寫(xiě)出計(jì)算過(guò)程〕?！?分〕解：由題意可知，該完全二叉樹(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ù)為：16第六層結(jié)點(diǎn)數(shù)為：32第七層結(jié)點(diǎn)數(shù)為：64第八層結(jié)點(diǎn)數(shù)為：4由于第八層結(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=131

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

13.循環(huán)隊(duì)列SQ隊(duì)滿的條件是〔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)(原始排列)有關(guān)的排序方法是〔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)的兩趟排序后的結(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〕，那么采納的是〔C〕排序。A、選擇B、快速C、希爾D、冒泡19.一組待排序記錄的關(guān)鍵字為〔46，79，56，38，40，84〕，那么利用快速排序，以第一個(gè)記錄為基準(zhǔn)元素得到的一次劃分結(jié)果為〔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ū)ο旅嫠膫€(gè)序列進(jìn)行排序〔由小到大〕，元素比較次數(shù)最少的是〔C〕。小到大的排序，所需進(jìn)行的關(guān)鍵字比較總次數(shù)是〔B〕。A、10B、