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

就可能不唯一了。三、簡作題(共10分)假設一個散列表中已裝入100個表項并采用線性探查法解決沖突，要求搜索到表中已有表項時的平均搜索次數不超過4，插入表中沒有的表項時找到插入位置的平均探查次數不超過50.5。請根據上述要求確定散列表的容量，并用除留余數法設計相應的散列函數。三、簡作題(共10分)由前一式得到，由后一式得到，綜合得因n=100,有，，可取m=117。用除留余數法設計散列函數：Hash(key)=key%113 (注：117不是質數，117=9*13)四、算法設計題(每小題5分，共15分)設中序線索化二叉樹的類聲明如下：template<classType>〃中序線索化二叉樹的結點類〃線索標志〃線索或子女指針〃結點中所包含的數據〃中序線索化二叉樹類〃中序線索化二叉樹的結點類〃線索標志〃線索或子女指針〃結點中所包含的數據〃中序線索化二叉樹類intleftThread,rightThread;ThreadNode<Type>*leftChild,*rightChild;Typedata;}；template<classType>classinOrderThreadTree{public:ThreadNode<Type>*getRoot(){returnroot;}〃其他公共成員函數private:ThreadNode<Type>*root; //樹的根指針};試依據上述類聲明，分別編寫下面的函數。ThreadNode<Type>*getPreorderFirst(ThreadNode<Type>*p);〃尋找以p為根指針的中序線索化二叉樹在前序下的第一個結點。ThreadNode<Type>*getPreorderNext(ThreadNode<Type>*p)〃尋找結點*p的在中序線索化二叉樹中前序下的后繼結點。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是數組A[]中元素總數。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;閱讀此算法，說明它的功能。對于下面給出的整數數組，追蹤第一趟while(d>0)內的每次for循環結束時數組中數據的變化。(為清楚起見，本次循環未涉及的不移動的數據可以不寫出，每行僅寫出一個for循環的變化)以上各次循環的數據移動次數分別是多少。五、算法分析題(每小題5分，共15分)希爾排序第一趟while循環內各for循環結束時數組中數據的變化：步a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]移動次數77 44 99 66 33 55 88 22 44 1177 44 99 66 33 55 88 22 44 11各趟數據移動次數見表的最右一欄。六、算法設計題(每小題5各趟數據移動次數見表的最右一欄。六、算法設計題(每小題5分，共15分)下面是隊列和棧的類聲明：template<classType>classqueue{public:queue();queue(constqueue&qu);queue&operator=(constqueue&qu);boolisEmpty();Type&getFront();voidpush(constType&item);voidpop();// 〃隊列的構造函數〃隊列的復制構造函數〃賦值操作〃判斷隊列空否，=1為空,=0不空〃返回隊頭元素的值〃將新元素插入到隊列的隊尾//從隊列的隊頭刪除元素〃其他成員函數template<classType>template<classType>classstack{public:stack();boolisEmpty();voidpush(conststack&item);voidpop();Type&getTop();〃棧的構造函數〃判斷棧空否。=1棧空，=0不空〃將新元素進棧〃棧頂元素退棧〃返回棧頂元素的值試利用棧和隊列的成員函數，編寫以下針對隊列的函數的實現代碼(要求非遞歸實現)。“逆轉”函數template<classType>voidreverse(queue<Type>&Q);(5分)“判等”函數boolqueue::operator==(constqueue&Q);(5分)“清空”函數voidqueue::clear();(5分)六、算法設計題(每小題5分，共15分)⑴#include“stack”template<classType>voidreverse(queue<Type>&Q){ 〃普通函數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){ 〃成員函數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