數(shù)據(jù)結(jié)構(gòu)第2階段測(cè)試題

1、階段測(cè)試題2數(shù)據(jù)結(jié)構(gòu)第第二階段測(cè)試卷江南大學(xué)現(xiàn)代遠(yuǎn)程教育第五章至第七章數(shù)據(jù)結(jié)構(gòu)時(shí)間：（總分100分）考試科目：90分鐘學(xué)習(xí)中心（教學(xué)點(diǎn)）批次：層次：專業(yè)：學(xué)號(hào)：身份證號(hào)：姓名：得分：分30每題3分，共-、選擇題（）的三對(duì)角矩陣，按行優(yōu)Al100,1.1001將一個(gè)，中的元素A66中，先存入一維數(shù)組Bl298則A）0（65在數(shù)組B中的位置K=198D、196C、197A.195B、o）（a,（b,（）,c）2、廣義表的深度為（4D、C、3A、1B、2。）3、下列敘述中錯(cuò)誤的是（二樹的度與該樹中結(jié)點(diǎn)的度的最大值相等B、A、叉樹就是度為2的有序樹的4個(gè)度為2C、有5個(gè)葉子結(jié)點(diǎn)的二叉樹中必有D、滿二叉

2、樹一定是完全二叉樹結(jié)點(diǎn)）個(gè)結(jié)點(diǎn)。4、一棵二叉樹中第6層上最多有（D、64B、31C、32A、2。）5、由樹轉(zhuǎn)換而得的二叉樹，根結(jié)點(diǎn)（C、左右子樹B、沒有右子樹A、沒有左子樹都有D、視樹的形態(tài)而定）個(gè)結(jié)點(diǎn)。k的二叉樹最少有（、一棵iWj為6k-ik2D、2-1E、k+1B、k-lA.kC、個(gè)頂點(diǎn)的有向圖最多有（、含7n）條弧。2D、nC、n（n+l）A、nB、n（n-1）8>設(shè)對(duì)下圖從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷,則（）是可能得到的遍歷序列。A、acfgdebB>abcdefgC>acdgbefD、abefgcdoio?則圖G中共有A=9、設(shè)圖G的鄰接矩陣?101?010?()個(gè)

3、頂點(diǎn)。93A、IB、C、4D、)nlO>具有個(gè)頂點(diǎn)的有向強(qiáng)連通圖最少有(條弧。n(n-1)/2A、n(n-1)B>n-lnC>D、分10(二、)試將下圖中的樹轉(zhuǎn)化為二叉樹。FH分10（三、）試寫出對(duì)如下無向圖從頂點(diǎn)A出發(fā)進(jìn)行廣度優(yōu)先遍歷可能得到的所有遍歷序列。分15()四、設(shè)有向網(wǎng)如下，試用迪杰斯特拉算法求從頂點(diǎn)A出發(fā)到其余各頂點(diǎn)的最短路徑4F682分15（五、）一棵深度為H的滿k叉樹有如下性質(zhì)：第H層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹。若按層次順序從1開始對(duì)全部結(jié)點(diǎn)編號(hào)，則：第i層上有多少個(gè)結(jié)點(diǎn)？編號(hào)為P的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)（若存在）的編號(hào)是多少？編

4、號(hào)為P的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的編號(hào)是多少？分20（六、）試設(shè)計(jì)算法，對(duì)以鄰接矩陣存儲(chǔ)的無向圖進(jìn)行深度優(yōu)先遍歷。答案一、選擇題、A1C2、B3、C4、B5、B6B7、8AB9、10B試將下圖中的樹轉(zhuǎn)化為二叉樹。二試寫出對(duì)如下無向圖從頂點(diǎn)A出發(fā)進(jìn)行廣度優(yōu)三先遍歷可能得到的所有遍歷序列o如下，四、F6答：ABCEGHFDABCEHGFDACBGHEDFACBHGEDF試用迪杰斯特拉算法求從頂點(diǎn)A設(shè)有向網(wǎng)出發(fā)到其余各頂點(diǎn)的最短路徑。6答：DPATPATDPATDPATDHHHHA00/0/0/AC118AC11BEBBO2/2C2AC2AC/2ACACACD3ADD375ACDACD3/364AC

5、444E0°/ACEE65ACFACF55F656ACFAC6AC6G66G3G3DPATPATDPATDHHH0/0/AO/B18ACD1/ACD1/ACDEGEBEGAC2ACC2/2/ACD3/ACD3/ACD3/ACDE4/ACD4/ACD4/ACDEEEF5/ACF5/ACF5/ACFG6ACF6ACF6/ACF2G0GEGE第H層上一棵深度為H的滿k叉樹有如下性質(zhì)：五、的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹。若按層次順序從1開始對(duì)全部結(jié)點(diǎn)編號(hào)，則：第i層上有多少個(gè)結(jié)點(diǎn)？編號(hào)為P的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)（若存在）的編號(hào)是多少？編號(hào)為P的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）

6、的編號(hào)是多少？答:第1層有1個(gè)結(jié)點(diǎn)，第i層結(jié)點(diǎn)數(shù)=第11層結(jié)6）二個(gè)*k（2WiWH點(diǎn)數(shù)個(gè)結(jié)點(diǎn)的孩子都編了號(hào)當(dāng)根結(jié)點(diǎn)以及前面的P-1ip的第之后,才開始為結(jié)點(diǎn)P的孩子編號(hào)。結(jié)點(diǎn)個(gè)孩子的編號(hào)為(1+(P1)*k)+io若P=1,則為根結(jié)點(diǎn)，無雙親，否則可設(shè)雙親結(jié)點(diǎn)編號(hào)為s,由可知結(jié)點(diǎn)S的孩子結(jié)點(diǎn)的編號(hào)范圍為(s1)2krlp?p 得可整*k+2（sl）*k+k數(shù)，又由S+1,為即7s?kk2?kp?o試設(shè)計(jì)算法，對(duì)以鄰接矩陣存儲(chǔ)的無向圖進(jìn)行深六、度優(yōu)先遍歷。答：intdepth(BiTreet)if(!t)return0;if(t->lchild)有左子樹if(t->rchild)左、右子樹均有hl=depth(t->lchild);求左子樹高度hr=depth(t->rchild);求右子樹高度returnhl>hr?hl+l:hr+l;else只有左子樹retu