上傳人：l***

認(rèn)證信息

認(rèn)證類型：個(gè)人認(rèn)證

認(rèn)證主體：李**（實(shí)名認(rèn)證）

IP屬地：天津

IP屬地：天津 上傳時(shí)間：2023-02-06 格式：DOCX 頁數(shù)：9 大?。?3.08KB 積分：20 舉報(bào) 版權(quán)申訴

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

就可能不唯一了。三、簡作題(共10分)假設(shè)一個(gè)散列表中已裝入100個(gè)表項(xiàng)并采用線性探查法解決沖突，要求搜索到表中已有表項(xiàng)時(shí)的平均搜索次數(shù)不超過4，插入表中沒有的表項(xiàng)時(shí)找到插入位置的平均探查次數(shù)不超過50.5。請(qǐng)根據(jù)上述要求確定散列表的容量，并用除留余數(shù)法設(shè)計(jì)相應(yīng)的散列函數(shù)。三、簡作題(共10分)由前一式得到，由后一式得到，綜合得因n=100,有，，可取m=117。用除留余數(shù)法設(shè)計(jì)散列函數(shù)：Hash(key)=key%113 (注：117不是質(zhì)數(shù)，117=9*13)四、算法設(shè)計(jì)題(每小題5分，共15分)設(shè)中序線索化二叉樹的類聲明如下：template<classType>〃中序線索化二叉樹的結(jié)點(diǎn)類〃線索標(biāo)志〃線索或子女指針〃結(jié)點(diǎn)中所包含的數(shù)據(jù)〃中序線索化二叉樹類〃中序線索化二叉樹的結(jié)點(diǎn)類〃線索標(biāo)志〃線索或子女指針〃結(jié)點(diǎn)中所包含的數(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為根指針的中序線索化二叉樹在前序下的第一個(gè)結(jié)點(diǎn)。ThreadNode<Type>*getPreorderNext(ThreadNode<Type>*p)〃尋找結(jié)點(diǎn)*p的在中序線索化二叉樹中前序下的后繼結(jié)點(diǎn)。voidpreorder(inOrderThreadTree<Type>&T);〃應(yīng)用以上兩個(gè)操作，在中序線索化二叉樹上做前序遍歷。四、 算法設(shè)計(jì)題(每小題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分)下面給出一個(gè)排序算法，其中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;閱讀此算法，說明它的功能。對(duì)于下面給出的整數(shù)數(shù)組，追蹤第一趟while(d>0)內(nèi)的每次for循環(huán)結(jié)束時(shí)數(shù)組中數(shù)據(jù)的變化。(為清楚起見，本次循環(huán)未涉及的不移動(dòng)的數(shù)據(jù)可以不寫出，每行僅寫出一個(gè)for循環(huán)的變化)以上各次循環(huán)的數(shù)據(jù)移動(dòng)次數(shù)分別是多少。五、算法分析題(每小題5分，共15分)希爾排序第一趟while循環(huán)內(nèi)各for循環(huán)結(jié)束時(shí)數(shù)組中數(shù)據(jù)的變化：步a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]移動(dòng)次數(shù)77 44 99 66 33 55 88 22 44 1177 44 99 66 33 55 88 22 44 11各趟數(shù)據(jù)移動(dòng)次數(shù)見表的最右一欄。六、算法設(shè)計(jì)題(每小題5各趟數(shù)據(jù)移動(dòng)次數(shù)見表的最右一欄。六、算法設(shè)計(jì)題(每小題5分，共15分)下面是隊(duì)列和棧的類聲明：template<classType>classqueue{public:queue();queue(constqueue&qu);queue&operator=(constqueue&qu);boolisEmpty();Type&getFront();voidpush(constType&item);voidpop();// 〃隊(duì)列的構(gòu)造函數(shù)〃隊(duì)列的復(fù)制構(gòu)造函數(shù)〃賦值操作〃判斷隊(duì)列空否，=1為空,=0不空〃返回隊(duì)頭元素的值〃將新元素插入到隊(duì)列的隊(duì)尾//從隊(duì)列的隊(duì)頭刪除元素〃其他成員函數(shù)template<classType>template<classType>classstack{public:stack();boolisEmpty();voidpush(conststack&item);voidpop();Type&getTop();〃棧的構(gòu)造函數(shù)〃判斷?？辗?。=1?？?，=0不空〃將新元素進(jìn)?！ｍ斣赝藯！ǚ祷貤ｍ斣氐闹翟?yán)脳：完?duì)列的成員函數(shù)，編寫以下針對(duì)隊(duì)列的函數(shù)的實(shí)現(xiàn)代碼(要求非遞歸實(shí)現(xiàn))?！澳孓D(zhuǎn)”函數(shù)template<classType>voidreverse(queue<Type>&Q);(5分)“判等”函數(shù)boolqueue::operator==(constqueue&Q);(5分)“清空”函數(shù)voidqueue::clear();(5分)六、算法設(shè)計(jì)題(每小題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);//從左隊(duì)列退出，進(jìn)臨時(shí)隊(duì)列t2=Q.getFront();Q.Pop();Q2.Push(t2);//從右隊(duì)列退出，進(jìn)臨時(shí)隊(duì)列if(t1!=t2){finished=false;b