數(shù)據(jù)結(jié)構(gòu)本科考試例

2006年《數(shù)據(jù)結(jié)構(gòu)》期終考試試卷(A)班級學號姓名班級學號姓名一、簡答題(每小題6分，共30分)假設一個線性鏈表的類名為linkedList，鏈表結(jié)點的類名為ListNode，它包含兩個數(shù)據(jù)成員data和link。data存儲該結(jié)點的數(shù)據(jù)，link是鏈接指針。下面給定一段遞歸打印一個鏈表中所有結(jié)點中數(shù)據(jù)的算法：voidPrintList(ListNode*L){if(L!=NULL){cout<<L->data<<endl;PrintList(L->link);}試問此程序在什么情況下不實用？給出具體修改后的可實用的程序？⑴此程序在內(nèi)存容量不足時不適用。因為需要一個遞歸工作棧。當鏈表越長，遞歸工作棧的深度越深，需要的存儲越多?？刹捎梅沁f歸算法節(jié)省存儲。voidPrintList(ListNode*L){while(L!=NULL){cout<<L->data<<endl;L=L->link;如果每個結(jié)點占用2個磁盤塊因而需要2次磁盤訪問才能實現(xiàn)讀寫，那么在一棵有n個關(guān)鍵碼的2m階B樹中，每次搜索需要的最大磁盤訪問次數(shù)是多少？⑵在2m階B樹中關(guān)鍵碼個數(shù)n與B樹高度h之間的關(guān)系為hWlog((n+1)/2)+1,那么每次搜索最大磁盤訪問次數(shù)為2hmax=2logm((n+1)/2)+2。給定一棵保存有n個關(guān)鍵碼的m階B樹。從某一非葉結(jié)點中刪除一個關(guān)鍵碼需要的最大磁盤訪問次數(shù)是多少？⑶在m階B樹中關(guān)鍵碼個數(shù)n與B樹最大高度h的關(guān)系為h=log「血2]((n+1)/2)+1。若設尋找被刪關(guān)鍵碼所在非葉結(jié)點讀盤次數(shù)為h’，被刪關(guān)鍵碼是結(jié)點中的&則從該結(jié)點的p.出發(fā)沿最左鏈到葉結(jié)點的讀盤次數(shù)為hh’。當把問題轉(zhuǎn)化為刪除葉結(jié)點的k0時，可能會引起結(jié)點的調(diào)整或合并。極端情況是從葉結(jié)點到根結(jié)點的路徑上所有結(jié)點都要調(diào)整，除根結(jié)點外每一層讀入1個兄弟結(jié)點，寫出2個結(jié)點，根結(jié)點寫出1個結(jié)點，假設內(nèi)存有足夠空間，搜索時讀入的盤塊仍然保存在內(nèi)存，則結(jié)點調(diào)整時共讀寫盤3(h1)+1。總共的磁盤訪問次數(shù)為h’+(hh’)+3(h1)+1=4h2=4(log「m/2l((n+1)/2)+1)2==4%刃血+1)/2)+2給定一個有n個數(shù)據(jù)元素的序列，各元素的值隨機分布。若要將該序列的數(shù)據(jù)調(diào)整成為一個堆，那么需要執(zhí)行的數(shù)據(jù)比較次數(shù)最多是多少？(4)設堆的高度為h=「log2(n+1)]，當每次調(diào)用siftDown算法時都要從子樹的根結(jié)點調(diào)整到葉結(jié)點，假設某子樹的根在第i層(1WiWh1)，第h層的葉結(jié)點不參加比較。從子樹根結(jié)點到葉結(jié)點需要比較hi層，每層需要2次比較：橫向在兩個子女里選一個，再縱向做父子結(jié)點的比較。因此，在堆中總的比較次數(shù)為因為2h-1WnW2卜1，且，則設有兩個分別有n個數(shù)據(jù)元素的有序表，現(xiàn)要對它們進行兩路歸并，生成一個有2n個數(shù)據(jù)元素的有序表。試問最大數(shù)據(jù)比較次數(shù)是多少？最少數(shù)據(jù)比較次數(shù)是多少？(5)兩個長度為n的有序表，當其中一個有序表的數(shù)據(jù)全部都小于另一個有序表的數(shù)據(jù)時，關(guān)鍵碼的比較次數(shù)達到最小(=n)。而當兩個有序表的數(shù)據(jù)交錯排列時，關(guān)鍵碼的比較次數(shù)達到最大(=2n-1)。二、簡作題(每小題5分，共15分)針對如下的帶權(quán)無向圖其中，每條邊上所注的芻為該邊的編號，冒號后面是該邊所對應的權(quán)值。使用Prim算法，從頂點A出發(fā)求出上圖的最小生成樹。要求給出生成樹構(gòu)造過程中依次選擇出來的邊的序列(用邊的編號表示)，權(quán)值相等時編號小的邊優(yōu)先。(不必畫圖)使用Kruskal算法求出上圖的最小生成樹。要求給出生成樹構(gòu)造過程中依次選擇出來的邊的序列(用邊的編號表示)，權(quán)值相等時編號小的邊優(yōu)先。(不必畫圖)(3)上面求出的最小生成樹是唯一的嗎？試舉理由說明。使用Prim算法(2)e1：3⑶這樣選A最小生成限定了選擇的機會。假e，:3He8：4ei7：e1：3⑶這樣選A最小生成限定了選擇的機會。假e，:3He8：4ei7：7―弓苛一ioB'、勺:4X3e~:211："Ze12：6Cei3：1時先選編號小的，7.限定在具有相等權(quán)'值的華中的選擇次序，結(jié)果可能e1e5e9e7e11e15e13e2/p>

就可能不唯一了。三、簡作題(共10分)假設一個散列表中已裝入100個表項并采用線性探查法解決沖突，要求搜索到表中已有表項時的平均搜索次數(shù)不超過4，插入表中沒有的表項時找到插入位置的平均探查次數(shù)不超過50.5。請根據(jù)上述要求確定散列表的容量，并用除留余數(shù)法設計相應的散列函數(shù)。三、簡作題(共10分)由前一式得到，由后一式得到，綜合得因n=100,有，，可取m=117。用除留余數(shù)法設計散列函數(shù)：Hash(key)=key%113 (注：117不是質(zhì)數(shù)，117=9*13)四、算法設計題(每小題5分，共15分)設中序線索化二叉樹的類聲明如下：template<classType>〃中序線索化二叉樹的結(jié)點類〃線索標志〃線索或子女指針〃結(jié)點中所包含的數(shù)據(jù)〃中序線索化二叉樹類〃中序線索化二叉樹的結(jié)點類〃線索標志〃線索或子女指針〃結(jié)點中所包含的數(shù)據(jù)〃中序線索化二叉樹類intleftThread,rightThread;ThreadNode<Type>*leftChild,*rightChild;Typedata;}；template<classType>classinOrderThreadTree{public:ThreadNode<Type>*getRoot(){returnroot;}〃其他公共成員函數(shù)private:ThreadNode<Type>*root; //樹的根指針};試依據(jù)上述類聲明，分別編寫下面的函數(shù)。ThreadNode<Type>*getPreorderFirst(ThreadNode<Type>*p);〃尋找以p為根指針的中序線索化二叉樹在前序下的第一個結(jié)點。ThreadNode<Type>*getPreorderNext(ThreadNode<Type>*p)〃尋找結(jié)點*p的在中序線索化二叉樹中前序下的后繼結(jié)點。voidpreorder(inOrderThreadTree<Type>&T);〃應用以上兩個操作，在中序線索化二叉樹上做前序遍歷。四、 算法設計題(每小題5分，共15分)tamplate<classType>ThreadNode<Type>*getPreorderFirst(ThreadNode<Type>*p){returnp;}template<classType>ThreadNode<Type>*getPreorderNext(ThreadNode<Type>*p){if(p->leftThread==0)returnp->leftChild;if(p->rightThread==0)returnp->rightChild;while(p->rightThread!=0&&p->rightChild!=NULL)p=p->rightChild;returnp->rightChild;⑶}template<classType>voidpreorder(inOrderThreadTree<Type>&T)(ThreadNode<Type>*p=getRoot();p=getPreorderFirst(p);while(p!=NULL){cout<<p->data<<endl;p=getPreorderNext(p);}}五、 算法分析題(每小題5分，共15分)下面給出一個排序算法，其中n是數(shù)組A[]中元素總數(shù)。template<classType>voidunknown(Typea[],intn){intd=1,j;while(d<n/3)d=3*d+1;while(d>0){for(inti=d;i<n;i++){Typetemp=a[i];j=i;while(j>=d&&a[j-d]>temp){a[j]=a[j-d];j-=d;}a[j]=temp;

d/=3;閱讀此算法，說明它的功能。對于下面給出的整數(shù)數(shù)組，追蹤第一趟while(d>0)內(nèi)的每次for循環(huán)結(jié)束時數(shù)組中數(shù)據(jù)的變化。(為清楚起見，本次循環(huán)未涉及的不移動的數(shù)據(jù)可以不寫出，每行僅寫出一個for循環(huán)的變化)以上各次循環(huán)的數(shù)據(jù)移動次數(shù)分別是多少。五、算法分析題(每小題5分，共15分)希爾排序第一趟while循環(huán)內(nèi)各for循環(huán)結(jié)束時數(shù)組中數(shù)據(jù)的變化：步a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]移動次數(shù)77 44 99 66 33 55 88 22 44 1177 44 99 66 33 55 88 22 44 11各趟數(shù)據(jù)移動次數(shù)見表的最右一欄。六、算法設計題(每小題5各趟數(shù)據(jù)移動次數(shù)見表的最右一欄。六、算法設計題(每小題5分，共15分)下面是隊列和棧的類聲明：template<classType>classqueue{public:queue();queue(constqueue&qu);queue&operator=(constqueue&qu);boolisEmpty();Type&getFront();voidpush(constType&item);voidpop();// 〃隊列的構(gòu)造函數(shù)〃隊列的復制構(gòu)造函數(shù)〃賦值操作〃判斷隊列空否，=1為空,=0不空〃返回隊頭元素的值〃將新元素插入到隊列的隊尾//從隊列的隊頭刪除元素〃其他成員函數(shù)template<classType>template<classType>classstack{public:stack();boolisEmpty();voidpush(conststack&item);voidpop();Type&getTop();〃棧的構(gòu)造函數(shù)〃判斷?？辗?。=1?？?，=0不空〃將新元素進?！ｍ斣赝藯！ǚ祷貤ｍ斣氐闹翟嚴脳：完犃械某蓡T函數(shù)，編寫以下針對隊列的函數(shù)的實現(xiàn)代碼(要求非遞歸實現(xiàn))?！澳孓D(zhuǎn)”函數(shù)template<classType>voidreverse(queue<Type>&Q);(5分)“判等”函數(shù)boolqueue::operator==(constqueue&Q);(5分)“清空”函數(shù)voidqueue::clear();(5分)六、算法設計題(每小題5分，共15分)⑴#include“stack”template<classType>voidreverse(queue<Type>&Q){ 〃普通函數(shù)stack<Type>S;Typetmp;while(!Q.isEmpty()){tmp=Q.getFront();Q.Pop();S.Push(tmp);}while(!S.isEmpty()){tmp=S.getTop();S.Pop();Q.EnQueue();}};boolqueue::operator==(constqueue&Q){ 〃成員函數(shù)queue<Type>Q1,Q2;Typet1,t2;boolfinished=true;while(!is.Empty()){t1=getFront();Pop();Q1.Push(t1);//從左隊列退出，進臨時隊列t2=Q.getFront();Q.Pop();Q2.Push(t2);//從右隊列退出，進臨時隊列if(t1!=t2){finished=false;b