計算機學(xué)院數(shù)據(jù)結(jié)構(gòu)歷年試題

1、華南師范大學(xué)計算機科學(xué)2003-2004 學(xué)年第（一）學(xué)期期末考試試卷卷數(shù)據(jù)結(jié)構(gòu)試專業(yè)年班學(xué)號姓名華南師范大學(xué)計算機科學(xué)2003-2004 學(xué)年第（一）學(xué)期期末考試試卷卷數(shù)據(jù)結(jié)構(gòu)試專業(yè)年班學(xué)號姓名一、判斷題（正確的劃“”，錯誤的劃“”。每小題1分，共 5分（平衡二叉樹（AVL）AVL（)二、單項選擇題（每小題2分，共 10分1.前序遍歷序列和中序遍歷序列相同的非空二叉樹是（ ）B.D2.n（ 3.如果對下列線性表分別作快速排序)所需比較次數(shù)最少A C B ( D(2,1,3,4,5,6,7,84.如果以鏈表作為棧的存儲結(jié)構(gòu)，則進(jìn)行進(jìn)棧操作時（ A.必須判別是否為棧滿 B.對棧不必作任何判別 C

2、.必須判別是否為棧空 D.必須判別進(jìn)棧元素類型5. 對包含n（ A. O( log2n B. O( n C. O(n log2n D.一二三四五六教研室主任簽系教學(xué)主任簽三、填空題（每空1分，共 20分1.深度為h的完全二叉樹至少三、填空題（每空1分，共 20分1.深度為h的完全二叉樹至少序，它的一個基本問題是如何建堆，常用的建堆算法是 1964 年 Floyd 提出的含 n 個元素的序列進(jìn)行排序時，堆排序的時間復(fù)雜性是 ，所需要的附加存儲單3.在n個記錄的有序順序表中進(jìn)行折半查找，最大的比較次數(shù)個數(shù)。對于一棵所有非葉子結(jié)點均為非空左、右子樹的二叉樹，如果該則該二叉樹結(jié)點的前序序列為，該二叉樹

3、對應(yīng)的樹林包點的左孩子結(jié)點的編號，其存在的條件7.一棵高為h的滿k叉樹有如下性質(zhì)：第m層上的結(jié)點都是葉結(jié)點，其余各層上每個結(jié)點都有k棵非空子樹如果按層次順序從1開始對全部結(jié)點編號則第m層的結(jié)點數(shù)目是編號為n的結(jié)點的雙親結(jié)點（若存在）的編號是，編號為n的結(jié)點的第i個孩，編號為n的結(jié)點有右兄弟的條件是兄弟的編號四、應(yīng)用解答題（共25（42.請畫出下面廣義表的帶表頭結(jié)點的存儲結(jié)構(gòu)，D(A(x,y,L(a,b)，B(z,A(x,y,L(a,b)（6（7 分（8分1245734385866試求出1).2).求出從頂點 1 出發(fā)到其他各頂點的最短距離五（8分1245734385866試求出1).2).求出

4、從頂點 1 出發(fā)到其他各頂點的最短距離五、算法完善題（共10分btreenodestructbtreenode*lchild; int data;structbtreenodevoidprintbtree(structbtreenodeif(/ if ( ；if ( printree(bt-/ /六、算法編制題（共30分 分2.已知(k1,k2,k3,.kn)是一個堆，試寫一個算法：將（k1,k2,k3,.kn,kn+1）調(diào)整為堆。并按（9分3.靜態(tài)產(chǎn)生，此時 next00保存起來（1單鏈表中取出鏈頭結(jié)點作為存放新元素的結(jié)點使用，然后再把該結(jié)點按條件插入到單鏈表0123456789i3.靜態(tài)產(chǎn)生，此時 next00保存起來