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

1、一、選擇題1 .在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成AA.線性結(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é)點之間的地址CA.必須連續(xù)B.局部必須連續(xù)C.不一定連續(xù)D.以上均不對3 .在一個長度為n的順序表中向第i個元素0<i<=n+1之前插入一個新元素時,需向后移動B個元素.A、n-iB、n-i+1C、n-i-1D、i4 .插入和刪除操作只能在一端進(jìn)行的線性表,稱為C.A.隊列B.線性表C.棧D.循環(huán)隊列5、隊列是僅允許在進(jìn)行插入,而在進(jìn)行刪除.AA.隊尾,隊首B.隊尾,隊尾C.隊首,隊尾D.隊首,隊首6 .鏈表適合于A查找.A.順序

2、B.二分C.隨機(jī)D.順序或二分7 .數(shù)據(jù)的根本單位是A.A.數(shù)據(jù)元素B.數(shù)據(jù)結(jié)構(gòu)C.數(shù)據(jù)項D.數(shù)據(jù)對象8 .以下哪個不是算法的特性B.A.有窮性B.可數(shù)性C.可行性D.確定性9 .在表長為n的順序表中進(jìn)行線性查找,它的平均查找長度為B.iA.ASL=nB.ASL=n+1/2C.ASL='n+1D.ASL=log2n10 .一個線性表第一個元素的存儲地址是320,每個元素的長度為3,那么第五個元素的地址是C.A.311B.328C.332D.31311 .設(shè)front、rear分別為循環(huán)雙向鏈表結(jié)點的左指針和右指針,那么指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是D.A.P=LB.P-

3、>front=LC.P=NULLD.P->rear=L12 .P為單鏈表中的非首尾結(jié)點,刪除P結(jié)點的后繼結(jié)點Q的語句為A.A.P->NEXT=Q->NEXT;FREEQ;B.Q->NEXT=P;FREEQ;C.Q->NEXT=P->NEXT;FREEQ;D.P->NEXT=S;S->NEXT=P;13 .循環(huán)隊列SQ隊滿的條件是B.A.SQ->rear=SQ->frontB.SQ->rear+1%MAXLEN=SQ->front23 .最小生成樹的構(gòu)造可使用B算法.A.Dijkstra算法B.Prim算法C.Haff

4、man算法D.Floyd算法24 .具有32個結(jié)點的完全二叉樹的深度為B.A.5B.6C.7D.825 .在有n個葉子結(jié)點的哈夫曼樹中,其結(jié)點總數(shù)為D.A.不確定B.2nC.2n+1D.2n-126 .以下陳述正確的選項是B.A.二叉樹是度為2的有序樹B.二叉樹中最多只有二棵樹,且有左右子樹之分C.二叉樹必有度為2的結(jié)點D.二叉樹中結(jié)點只有一個孩子時無左右之分27 .先序為A,B,C的二叉樹共有A種.A.3B.4C.5D.628 .在樹結(jié)構(gòu)中,假設(shè)結(jié)點B有3個兄弟,A是B的父親結(jié)點,那么A的度為B.A.3B.4C.5D.629 .在一個圖中,所有頂點的度數(shù)之和等于所有邊數(shù)的B倍.A1B、2C、

5、3D、430 .n個頂點的強(qiáng)連通圖至少有A邊.AnB、n-1C、n+1D、nn-131 .在一個無向圖中,所有頂點的度數(shù)之和等于所有邊數(shù)的C倍；在一個有向圖中,所有頂點的入度之和等于所有頂點出度之和的C倍.A1/2B、2C、1D、432 .任何一個無向連通圖的最小生成樹B.A、只有一棵B、一棵或多棵C一定有多棵D、可能不存在33 .在圖的表本法中,表木形式唯一"的是AA、鄰接矩陣表示法B、鄰接表表示法C逆鄰接矩陣表示法D、逆鄰接表表示法34 .在一個具有n個頂點的無向圖中,要連通全部頂點至少需要C條邊.A.nB.n+1C.n-1D.n+235 .在一個圖中,所有頂點的度數(shù)之和等于圖的

6、邊數(shù)的B.A.1/2B.2C.1D.436 .有7個結(jié)點的有向完全圖有C邊.A.30B.40C.42D.5637 .假定在一棵二叉樹中,度為2的分支結(jié)點個數(shù)為15,度為1的分支結(jié)點個數(shù)為30個,那么葉子結(jié)點數(shù)為B.A15B、16C、17D、4738 .設(shè)n,m為一棵樹上的兩個結(jié)點,在中根遍歷時,n在m前的條件是C.An在m右方B、n是m祖先Cn在m左方D、n是m子孫39 .某二叉樹的后序遍歷序列為：DABEC中序遍歷序列為：DEBAC那么前序遍歷序列為D.AACBEDB、DECABCDEABCD、CEDBA40 .將一棵有100個結(jié)點的完全二叉樹從上到下,從左到右依次對結(jié)點編號,根結(jié)點的編號為

7、1,那么編號為45的結(jié)點的左孩子的編號為90,右孩子的編號為91.A46B、47C、91D、9141 .某樹中,假設(shè)結(jié)點B有4個兄弟,A是B的父親結(jié)點,那么A的度為C.A3B、4C、5D、642 .以下表達(dá)正確的選項是DA、二叉樹是度為2的有序樹B、二叉樹結(jié)點只有一個孩子時無左右之分C二叉樹中必有度為2的結(jié)點D二叉樹中最多只有兩棵子樹,且有左右之分43 .由帶權(quán)為9、2、5、7的四個葉子結(jié)點構(gòu)造一棵哈夫曼樹,該樹的帶樹路徑長度為D.A23B、37C46D、4444 .在圖的表示方法中,表示形式是唯一的是C.A.鄰接表B.逆鄰接表C.鄰接矩陣D.其他46.設(shè)n,m為一棵樹上的兩個結(jié)點,在中根遍歷

8、時,n在m前的條件是C.A.n在m右方B.n是m祖先C.n在m左方D.n是m子孫二、填空題1 .樹和圖都屬于非線性結(jié)構(gòu).2 .順序表中邏輯上相鄰的元素在物理位置上也相鄰.3 .雙向鏈表有兩個指針域,一個指向前趨,另一個指向后繼_.4 .假設(shè)進(jìn)棧的次序是A,B,C,D,E,寫出兩種出棧順序_ABCDEEDCBA5 .隊列存取數(shù)據(jù)應(yīng)遵循的原那么是先進(jìn)先出.6 .有20個結(jié)點的完全二叉樹,編號為7的結(jié)點的父結(jié)點編號為3.7 .兩個序列分別為:L1=3,50,41,42,55,65,70,75,L2=3,50,41,42,65,55,.9 .有向圖的邊也稱為衛(wèi),用鄰接矩陣存儲有向圖,其第i行的所有元素

9、之和等于頂點i的出度.10 .樹轉(zhuǎn)換成的二叉樹,其根結(jié)點的右子樹一定為空.11 .二叉排序樹是一種動態(tài)查找表.12 .對一組記錄50,40,95,20,15,70,60,45,80進(jìn)行直接插入排序時,當(dāng)把第7條記錄60插入到有序表中時,為尋找插入位置需比擬15次.13 .在樹形結(jié)構(gòu)中,樹根結(jié)點沒有前驅(qū)結(jié)點,其余每個結(jié)點有且只有J個前驅(qū)結(jié)點；葉子結(jié)點沒有后繼結(jié)點,其余結(jié)點的后繼結(jié)點可以任意多個.14 .在具有n個結(jié)點的二叉樹中,有n+1個空指針.15 .深度為k的完全二叉樹至少有疆個結(jié)點,至多有2二1個結(jié)點,假設(shè)按自上而下,從左到右次序給結(jié)點從1開始編號,那么編號最小的葉子結(jié)點的編號是n/2+1

10、q16 .由a,b,c三個結(jié)點構(gòu)成的二叉樹,共有J0種不同形態(tài),假設(shè)是構(gòu)成樹,共有9_種形態(tài).17 .樹所對應(yīng)的二叉樹其根結(jié)點的業(yè)_子樹一定為空.18 .完全二叉樹的第8層有8個結(jié)點,那么其葉結(jié)點數(shù)是68三、綜合應(yīng)用題.2 .完全二叉樹的第8層有4個結(jié)點,請計算它的葉子結(jié)點數(shù)和總結(jié)點數(shù).寫出計算過程.6分解：由題意可知,該完全二叉樹有八層,其中第一層結(jié)點數(shù)為：1第二層結(jié)點數(shù)為：2第三層結(jié)點數(shù)為：4第四層結(jié)點數(shù)為：8第五層結(jié)點數(shù)為：16第六層結(jié)點數(shù)為：32第七層結(jié)點數(shù)為：64第八層結(jié)點數(shù)為：4由于第八層結(jié)點數(shù)為4,且為完全二叉樹,那么第八層四個結(jié)點為葉子結(jié)點,第七層前兩個結(jié)點有子結(jié)點,其余62個

11、結(jié)點無子結(jié)點,那么第七層的后62個結(jié)點為葉子結(jié)點,故葉子結(jié)點數(shù)有4+62=66總結(jié)點數(shù)為1+2+4+8+16+32+64+4=1316 .一棵具有6層的滿二叉樹中結(jié)點數(shù)為多少請寫出計算公式.解：2k-1=26-1=637 .給定一個權(quán)集W=4,8,6,9,18,畫出相應(yīng)的哈夫曼樹,并計算WPL8 .二叉樹的先序遍歷序列為：ABDGHCEFI,中序遍歷的序列為：GDHBAECIF請完成以下各畫出此二叉樹.寫出它的后序遍歷序列.BCDEGH題:(1)(2)(3)將此A2樹看作森林的二叉樹表示,試將它復(fù)原為森林.(2)其后序遍歷的序列為：GHDBEIFCA(3)10 .給定一個權(quán)集W=4,長度WPL

12、5,7,8,6,12,18,試畫出相應(yīng)的哈夫曼樹,并計算其帶權(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.F、G試為這12.一個無向圖的頂點集為a,b,c,d,e其鄰接矩陣如下,畫出草圖,寫出從頂點出發(fā)按深度優(yōu)先搜索進(jìn)行遍歷的結(jié)點序列.(答案不呵一)(答案屁一)(2)深度優(yōu)先搜索：abdce廣度優(yōu)先搜索：abedc13.網(wǎng)G的鄰接矩陣如下,試畫出該圖,并畫出它的一棵最小生成樹.081011080301310304011040130四、算法設(shè)計題1、單向鏈表中,在p指

13、針?biāo)赶虻慕Y(jié)點前插入一個元素x,寫出相關(guān)算法,并畫出圖形進(jìn)行描述.解：#include<stdio.h>#include<malloc.h>typedefintDataType;typedefstructnodeDataTypedata;structnode*next;Listnode;intInsert(Listnode*head,DataTypea,intb)這個是插入算法Listnode*p,*h,*s;intk=1;p=head;h=head->next;while(h!=NULL&&k<=b-1)k+;p=h;h=h->nex

14、t;if(p=NULL)printf("插入失敗")；return0;s=(Listnode*)malloc(sizeof(Listnode);s->data=a;s->next=h;p->next=s;return1;)voidmain()(Listnode*H,*p;intx,y;H=(Listnode*)malloc(sizeof(Listnode);H->next=NULL;printf("請輸入將被存入鏈表中的數(shù)(.為結(jié)束)：");scanf("%d",&x);while(x!=0)(p=(L

15、istnode*)malloc(sizeof(Listnode);p->data=x;p->next=H->next;H->next=p;scanf("%d",&x);)printf("請輸入將被插入的數(shù)：n");scanf("%d",&x);printf("請輸入將被插入的數(shù)的位置：n");scanf("%d",&y);p=H->next;printf("插入前,鏈表：");while(p!=NULL)(printf(&

16、quot;%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");)圖27.在結(jié)點p之后插入結(jié)點32、在單鏈表中刪除第i個結(jié)點,假設(shè)刪除成功返回1,否那么返回0,并要求畫出圖形進(jìn)行描述.解：#include<iostream>#include<ioman

17、ip>template<classT>classSeqListpublic:TDelete(inti);Tdata5;intlength;template<classT>TSeqList<T>:Delete(inti)intj;Tx;if(length=0)throw"下溢"if(i<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個元素地址p函數(shù)*/if(p!=NULL&&p->next!=NULL)Del_Elem(p,x);/*調(diào)用刪除結(jié)點p之后結(jié)點函數(shù)*/return1;elsereturn0;)intmain()(SeqList<int>a;cout<<"請輸入單鏈表的長度：length="cin>>a.length;cout<<"請輸入單鏈表中的數(shù)據(jù)："for(i