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

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

2、樹一定是完全二叉樹4、一棵二叉樹中第層上最多有（ ）個結(jié)點(diǎn)。、5、由樹轉(zhuǎn)換而得的二叉樹，根結(jié)點(diǎn)（ ）。、沒有左子樹、沒有右子樹、左右子樹都有、視樹的形態(tài)而定6、一棵高為k的二叉樹最少有（ ）個結(jié)點(diǎn)。、k-1、k、k+1、2k-1、2k-17、含n個頂點(diǎn)的有向圖最多有（ ）條弧。、n、n(n-1)、n(n+1)、n28、設(shè)對下圖從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷，則（ ）是可能得到的遍歷序列。、acfgdeb、abcdefg、acdgbef、abefgcd9、設(shè)圖的鄰接矩陣A=，則圖中共有（ ）個頂點(diǎn)。、1、3、4、910、具有n個頂點(diǎn)的有向強(qiáng)連通圖最少有（ ）條弧。、n-1、n、n(n-1)、n(n

3、-1)/2二、（10分）試將下圖中的樹轉(zhuǎn)化為二叉樹。三、（10分）試寫出對如下無向圖從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先遍歷可能得到的所有遍歷序列。四、（15分）設(shè)有向網(wǎng)如下，試用迪杰斯特拉算法求從頂點(diǎn)出發(fā)到其余各頂點(diǎn)的最短路徑。五、（15分）一棵深度為的滿叉樹有如下性質(zhì)：第層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個結(jié)點(diǎn)都有棵非空子樹。若按層次順序從開始對全部結(jié)點(diǎn)編號，則：第層上有多少個結(jié)點(diǎn)？編號為的結(jié)點(diǎn)的第個孩子結(jié)點(diǎn)（若存在）的編號是多少？編號為的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的編號是多少？六、（20分）試設(shè)計算法，對以鄰接矩陣存儲的無向圖進(jìn)行深度優(yōu)先遍歷。答案一、選擇題1、A2、C3、B4、C5、B6、B7、B8

4、、A9、B10、B二、試將下圖中的樹轉(zhuǎn)化為二叉樹。答：三、試寫出對如下無向圖從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先遍歷可能得到的所有遍歷序列。答：ABCEGHFDABCEHGFDACBGHEDFACBHGEDF四、設(shè)有向網(wǎng)如下，試用迪杰斯特拉算法求從頂點(diǎn)出發(fā)到其余各頂點(diǎn)的最短路徑。答：DPATHDPATHDPATHDPATHA0/0/0/0/B11110ACDB18ACDEBC22AC2/AC2/AC2/ACD37AD35ACD3/ACD3/ACDE4446ACDE4/ACDEF556ACF56ACF56ACFG66613ACDG613ACDGDPATHDPATHDPATHA0/0/0/B18ACDEB1/A

5、CDEG1/ACDEGC2/AC2/AC2/ACD3/ACD3/ACD3/ACDE4/ACDE4/ACDE4/ACDEF5/ACF5/ACF5/ACFG612ACFG610ACFGE6/ACFGE五、一棵深度為的滿叉樹有如下性質(zhì)：第層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個結(jié)點(diǎn)都有棵非空子樹。若按層次順序從開始對全部結(jié)點(diǎn)編號，則：第層上有多少個結(jié)點(diǎn)？編號為的結(jié)點(diǎn)的第個孩子結(jié)點(diǎn)（若存在）的編號是多少？編號為的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的編號是多少？答：第1層有1個結(jié)點(diǎn)，第i層結(jié)點(diǎn)數(shù)第i-1層結(jié)點(diǎn)數(shù)*k（2iH）=個當(dāng)根結(jié)點(diǎn)以及前面的p-1個結(jié)點(diǎn)的孩子都編了號之后，才開始為結(jié)點(diǎn)p的孩子編號。結(jié)點(diǎn)p的第i

6、個孩子的編號為（）。若，則為根結(jié)點(diǎn)，無雙親，否則可設(shè)雙親結(jié)點(diǎn)編號為，由可知結(jié)點(diǎn)的孩子結(jié)點(diǎn)的編號范圍為（）（），即，又由為整數(shù)，可得。六、試設(shè)計算法，對以鄰接矩陣存儲的無向圖進(jìn)行深度優(yōu)先遍歷。答：int depth(BiTree t) if (!t) return 0; if(t->lchild)/有左子樹 if (t->rchild) /左、右子樹均有 hl=depth(t->lchild); /求左子樹高度 hr=depth(t->rchild); /求右子樹高度 return hl>hr?hl+1:hr+1; else /只有左子樹 return depth(t->