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

1、一、選擇題1 .在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（A）A.線性結(jié)構(gòu)和非線性結(jié)構(gòu)B.動態(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)之間的地址（C）A.必須連續(xù)B.部分必須連續(xù)C.不一定連續(xù)D.以上均不對3 .在一個(gè)長度為n的順序表中向第i個(gè)元素（0<i<=n+1）之前插入一個(gè)新元素時(shí)，需向后移動（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ì)首

2、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ù)對象8 .下列哪個(gè)不是算法的特性（B）。A.有窮性B.可數(shù)性C.可行性D.確定性9 .在表長為n的順序表中進(jìn)行線性查找，它的平均查找長度為（B）。iA.ASL=nB.ASL=（n+1）/2C.ASL='n+1D.ASL=log2n10 .一個(gè)線性表第一個(gè)元素的存儲地址是320,每個(gè)元素的長度為3,則第五個(gè)元素的地址是（C）。A.311B.328C.332D.31311 .設(shè)front、rear分別為循環(huán)雙向鏈表結(jié)點(diǎn)的左指針和右指針，則指針P所指的元素

3、是雙循環(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的語句為（A）。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ì)滿的條件是（B）。A.SQ->rear=SQ->frontB.（SQ->rear+1）%MAXLEN=SQ->front23

4、.最小生成樹的構(gòu)造可使用（B）算法。A.Dijkstra算法B.Prim算法C.Haffman算法D.Floyd算法24 .具有32個(gè)結(jié)點(diǎn)的完全二叉樹的深度為（B）。A.5B.6C.7D.825 .在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中，其結(jié)點(diǎn)總數(shù)為（D）。A.不確定B.2nC.2n+1D.2n-126 .下列陳述正確的是（B）。A.二叉樹是度為2的有序樹B.二叉樹中最多只有二棵樹，且有左右子樹之分C.二叉樹必有度為2的結(jié)點(diǎn)D.二叉樹中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無左右之分27 .先序?yàn)锳,B,C的二叉樹共有（A）種。A.3B.4C.5D.628 .在樹結(jié)構(gòu)中，若結(jié)點(diǎn)B有3個(gè)兄弟,A是B的父親結(jié)點(diǎn)，則A的度為（B

5、）。第1頁共8頁A.3B.4C.5D.629 .在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（B）倍。A1B、2C、3D、430 .n個(gè)頂點(diǎn)的強(qiáng)連通圖至少有（A邊。AnB、n-1C、n+1D、n（n-1）31 .在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（C）倍；在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（C）倍。A1/2B、2C、1D、432 .任何一個(gè)無向連通圖的最小生成樹（B）。A、只有一棵B、一棵或多棵C一定有多棵D、可能不存在33 .在圖的表本法中，表木形式唯一"的是（A）A、鄰接矩陣表示法B、鄰接表表示法C逆鄰接矩陣表示法D、逆鄰接表表示法34 .在一

6、個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(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 .假定在一棵二叉樹中，度為2的分支結(jié)點(diǎn)個(gè)數(shù)為15,度為1的分支結(jié)點(diǎn)個(gè)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為（B）。A15B、16C、17D、4738 .設(shè)n,m為一棵樹上的兩個(gè)結(jié)點(diǎn)，在中根遍歷時(shí)，n在m前的條件是（C）。An在m右方B、n是m祖先Cn在m左方D、n是m子孫39 .某二叉樹的后序遍歷序列為：DABEC中序遍歷序列為：DEBAC則前序

7、遍歷序列為（D）。AACBEDB、DECABCDEABCD、CEDBA40 .將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對結(jié)點(diǎn)編號，根結(jié)點(diǎn)的編號為1,則編號為45的結(jié)點(diǎn)的左孩子的編號為（90）,右孩子的編號為（91）。A46B、47C、91D、9141 .某樹中，若結(jié)點(diǎn)B有4個(gè)兄弟，A是B的父親結(jié)點(diǎn)，則A的度為（C）。A3B、4C、5D、642 .下列敘述正確的是（D）A、二叉樹是度為2的有序樹B、二叉樹結(jié)點(diǎn)只有一個(gè)孩子時(shí)無左右之分C二叉樹中必有度為2的結(jié)點(diǎn)D二叉樹中最多只有兩棵子樹，且有左右之分43 .由帶權(quán)為9、2、5、7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶樹路徑長度為（D

8、）。A23B、37C46D、4444 .在圖的表示方法中，表示形式是唯一的是（C）。A.鄰接表B.逆鄰接表C.鄰接矩陣D.其他46.設(shè)n,m為一棵樹上的兩個(gè)結(jié)點(diǎn)，在中根遍歷時(shí)，n在m前的條件是（C）。第2頁共8頁A.n在m右方B.n是m祖先C.n在m左方D.n是m子孫二、填空題1 .樹和圖都屬于非線性結(jié)構(gòu)。2 .順序表中邏輯上相鄰的元素在物理位置上也相鄰。3 .雙向鏈表有兩個(gè)指針域，一個(gè)指向前趨，另一個(gè)指向后繼_。4 .若進(jìn)棧的次序是A,B,C,D,E,寫出兩種出棧順序_ABCDEEDCBA5 .隊(duì)列存取數(shù)據(jù)應(yīng)遵循的原則是先進(jìn)先出。6 .有20個(gè)結(jié)點(diǎn)的完全二叉樹，編號為7的結(jié)點(diǎn)的父結(jié)點(diǎn)編號為3

9、。7 .兩個(gè)序列分別為:L1=3,50,41,42,55,65,70,75,L2=3,50,41,42,65,55,.9 .有向圖的邊也稱為衛(wèi)，用鄰接矩陣存儲有向圖，其第i行的所有元素之和等于頂點(diǎn)i的出度。10 .樹轉(zhuǎn)換成的二叉樹，其根結(jié)點(diǎn)的右子樹一定為空。11 .二叉排序樹是一種動態(tài)查找表。12 .對一組記錄（50,40,95,20,15,70,60,45,80）進(jìn)行直接插入排序時(shí)，當(dāng)把第7條記錄60插入到有序表中時(shí)，為尋找插入位置需比較15次。13 .在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有（前驅(qū)）結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有J個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有后繼結(jié)點(diǎn),其余結(jié)點(diǎn)的后繼結(jié)點(diǎn)可以任意多個(gè)。14 .在具

10、有n個(gè)結(jié)點(diǎn)的二叉樹中，有n+1個(gè)空指針。15 .深度為k的完全二叉樹至少有疆個(gè)結(jié)點(diǎn)，至多有2二1個(gè)結(jié)點(diǎn)，若按自上而下，從左到右次序給結(jié)點(diǎn)從1開始編號，則編號最小的葉子結(jié)點(diǎn)的編號是n/2+1q16 .由a,b,c三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹，共有J0種不同形態(tài)，若是構(gòu)成樹，共有9_種形態(tài)。17 .樹所對應(yīng)的二叉樹其根結(jié)點(diǎn)的業(yè)_子樹一定為空。18 .已知完全二叉樹的第8層有8個(gè)結(jié)點(diǎn)，則其葉結(jié)點(diǎn)數(shù)是68三、綜合應(yīng)用題。2 .已知完全二叉樹的第8層有4個(gè)結(jié)點(diǎn)，請計(jì)算它的葉子結(jié)點(diǎn)數(shù)和總結(jié)點(diǎn)數(shù)。（寫出計(jì)算過程）。（6分）解：由題意可知，該完全二叉樹有八層，其中第一層結(jié)點(diǎn)數(shù)為：1第二層結(jié)點(diǎn)數(shù)為：2第三層結(jié)點(diǎn)數(shù)為：4

11、第四層結(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因?yàn)榈诎藢咏Y(jié)點(diǎn)數(shù)為4,且為完全二叉樹，則第八層四個(gè)結(jié)點(diǎn)為葉子結(jié)點(diǎn)，第七層前兩個(gè)結(jié)點(diǎn)有子結(jié)點(diǎn)，其余62個(gè)結(jié)點(diǎn)無子結(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=1316 .一棵具有6層的滿二叉樹中結(jié)點(diǎn)數(shù)為多少？請寫出計(jì)算公式。解：2k-1=26-1=637 .給定一個(gè)權(quán)集W=4,8,6,9,18,畫出相應(yīng)的哈夫曼樹，并計(jì)算WPL第3頁共8頁8 .已知二叉樹的先序遍歷序列為：ABDGHCEFI,中序遍歷的序列為：GDHBAECIF請完成

12、以下各畫出此二叉樹。寫出它的后序遍歷序列。BCDEGH題:(1)(2)(3)將此A10.給定一個(gè)權(quán)集W=4,長度WPL2樹看作森林的二叉樹表示，試將它還原為森林。(2)其后序遍歷的序列為：GHDBEIFCA(3)5,7,8,6,12,18,試畫出相應(yīng)的哈夫曼樹，并計(jì)算其帶權(quán)徑WPL=(12+18)*2+(6+7+8)*3+(4+5)*4=15911.假設(shè)用于通信的電文僅由現(xiàn)的頻率分別為7、19、2、6、A、B、C、DE、32、3、21、10。aF、G試為這12.已知一個(gè)無向圖的頂點(diǎn)集為a,b,c,d,e其鄰接矩陣如下，畫出草圖，寫出從頂點(diǎn)(2)深度優(yōu)先搜索：abdce廣度優(yōu)先搜索：abedc出

13、發(fā)按深度優(yōu)先搜索進(jìn)行遍歷的結(jié)點(diǎn)序列。(答案不呵一)(答案屁一)13.網(wǎng)G的鄰接矩陣如下，試畫出該圖，并畫出它的一棵最小生成樹。0810110803013103040第4頁共8頁11040130四、算法設(shè)計(jì)題1、單向鏈表中，在p指針?biāo)赶虻慕Y(jié)點(diǎn)前插入一個(gè)元素x,寫出相關(guān)算法，并畫出圖形進(jìn)行描述。解：#include<stdio.h>#include<malloc.h>typedefintDataType;typedefstructnodeDataTypedata;structnode*next;Listnode;intInsert(Listnode*head,DataTy

14、pea,intb)這個(gè)是插入算法Listnode*p,*h,*s;intk=1;p=head;h=head->next;while(h!=NULL&&k<=b-1)k+;p=h;h=h->next;if(p=NULL)printf("插入失敗")；return0;s=(Listnode*)malloc(sizeof(Listnode);s->data=a;s->next=h;p->next=s;第5頁共8頁return1;)voidmain()(Listnode*H,*p;intx,y;H=(Listnode*)mallo

15、c(sizeof(Listnode);H->next=NULL;printf("請輸入將被存入鏈表中的數(shù)(。為結(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("請輸入將被插入的數(shù)：n");scanf("%d",&x);printf(&

16、quot;請輸入將被插入的數(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;)print

17、f("n");)第6頁共8頁圖27。在結(jié)點(diǎn)p之后插入結(jié)點(diǎn)32、在單鏈表中刪除第i個(gè)結(jié)點(diǎn)，若刪除成功返回1,否則返回0,并要求畫出圖形進(jìn)行描述。解：#include<iostream>#include<iomanip>template<classT>classSeqListpublic:TDelete(inti);Tdata5;intlength;template<classT>TSeqList<T>:Delete(inti)intj;Tx;if(length=0)throw"下溢"if(i<

18、;1|i>length)throw"位置異常"；x=datai-1;for(j=i;j<length;j+)dataj-1=dataj;length-;returnx;intDelElem(LinkList*L,inti,datatype*x)LinkList*p;p=GetList(L,i-1);/*調(diào)用按序號查找第i-1個(gè)元素地址p函數(shù)*/if(p!=NULL&&p->next!=NULL)Del_Elem(p,x);/*調(diào)用刪除已知結(jié)點(diǎn)p之后結(jié)點(diǎn)函數(shù)*/return1;elsereturn0;第7頁共8頁)intmain()(SeqList<int>a;cout<<"請輸入單鏈表的長度：length="cin>>a.length;cout<<"請輸入單鏈表中的數(shù)據(jù)："for(