3、點的度要么是0，要么是2。這棵二叉樹中度為2的結(jié)點有___________________個。8、在堆排序和快速排序中，若原始記錄接近正序或反序，則選用____。9、若采用鄰接表的存儲結(jié)構(gòu)，則圖的廣度優(yōu)先搜索類似于二叉樹的________遍歷。得分二、單向選擇題（每小題1.5分，共15分）1、n個頂點的強連通圖中至少含有()。A、n—l條有向邊B、n條有向邊C、n(n—1)／2條有向邊D、n(n一1)條有向邊2、在一個不帶頭結(jié)點的單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點，執(zhí)行()。A、HL＝p;p一>next＝HL;B、p一>next＝HL；HL＝p
4、;C、p一>next＝HL;p＝HL;D、p一>next＝HL一>next;HL一>next＝p;第6頁共6頁3、采用線性鏈表表示一個向量時，要求占用的存儲空間地址（）。A:必須是連續(xù)的B部分地址必須是連續(xù)的C:一定是不連續(xù)的D:可連續(xù)可不連續(xù)4、如果想在4092個數(shù)據(jù)中只需要選擇其中最小的5個，采用（）方法最好。A:起泡排序B:堆排序C:錦標賽排序D:快速排序5、在循環(huán)隊列中用數(shù)組A[0..m-1]存放隊列元素，其隊頭和隊尾指針分別為front和rear，則當前隊列中的元素個數(shù)是（）。A:(front-rear+1)%mB:(rear-front+1)%mC
5、:(front-rear+m)%mD:(rear-front+m)%m6、數(shù)組A[0..5,0..6]的每個元素占五個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)存單元中，則元素A[5，5]的地址是(?????)。A:1175???????????B:1180???????????C:1205???????????D:12107、已知廣義表LS＝((a,b,c),(d,e,f)),運用head和tail函數(shù)取出LS中原子e的運算是(????)A:head(tail(LS))?????????????????????B:tail(head(LS))C:he
6、ad(tail(head(tail(LS)))??????????D:head(tail(tail(head(LS))))8、某二叉樹的前序遍歷結(jié)點訪問順序是abdgcefh,中序遍歷的結(jié)點訪問順序是dgbaechf,則其后序遍歷的結(jié)點訪問順序是（）。A:bdgcefhaB:gdbecfhaC:bdgaechfD:gdbehfca9、在一個無向圖中,所有頂點的度數(shù)之和等于所有邊數(shù)的（）倍。A:1/2B:1C:2D:410、設(shè)串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號i的字符
7、開始的j個字符組成的子串，len(s)返回串s的長度，則con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結(jié)果串是（）。A：BCDEFB：BCDEFGC：BCPQRSTD：BCDEFEF得分三、應用題（每小題8分，共32分）1．一棵深度為h的滿m叉樹具有如下性質(zhì):第h層上的結(jié)點都是葉結(jié)點,其余各層上每個結(jié)點都有m棵非空子樹。若按層次從上到下,每層從左到右的順序從1開始對全部結(jié)點編號,試計算:(1)第k層結(jié)點數(shù)(1≤k≤h)。(2)整棵樹結(jié)點數(shù)。(3)編號為i的結(jié)點的雙親結(jié)點的編號。(4)編號為i的結(jié)點的第j個孩子結(jié)點(若有)
8、的編號。答題勿超裝訂線--------
