數(shù)據(jù)結(jié)構(gòu)作業(yè)10-11

數(shù)據(jù)結(jié)構(gòu)第十次作業(yè)1習(xí)題8.2總存儲(chǔ)量675MB，分布在15個(gè)盤面上，每個(gè)盤面有612磁道，每個(gè)磁道144個(gè)扇區(qū)，每個(gè)扇區(qū)512字節(jié)。每簇有8個(gè)扇區(qū)，磁盤轉(zhuǎn)速為3600rpm，磁道到磁道的尋道時(shí)間為20ms，平均尋道時(shí)間為80ms，現(xiàn)在假設(shè)磁盤上有一個(gè)大小為360KB的文件。一般情況下，讀取文件中的所有數(shù)據(jù)要花多少時(shí)間？假定文件中的第一個(gè)磁道隨機(jī)位于磁盤中的某一個(gè)位置，整個(gè)文件放在一組相鄰磁道內(nèi)，文件完全填充它所占據(jù)的磁道。試給出你的計(jì)算。磁盤一次讀取時(shí)間由尋道時(shí)間延遲時(shí)間和傳輸時(shí)間決定其中r為磁盤每秒鐘的轉(zhuǎn)速，b為每次讀取的字節(jié)數(shù)，N為一個(gè)磁道上的字節(jié)數(shù)尋道時(shí)間：將磁頭移動(dòng)到指定磁道所需要的時(shí)間延遲時(shí)間：磁頭定位到某一磁道相關(guān)扇區(qū)所需要的時(shí)間，T=1/2*r傳輸時(shí)間：從磁盤讀出或向磁盤寫入數(shù)據(jù)所經(jīng)歷的時(shí)間，T=b/rN360KB的文件存放需要多少個(gè)扇區(qū)?多少個(gè)簇？720個(gè)sectors90個(gè)cluster一般情況90*80ms+90*（1/2+8/144）*0.0166s=7288.18ms連續(xù)存放360KB文件放多少個(gè)track？720/144=5第一個(gè)磁道：80ms+（1/2+1/1）*0.0166s=104.9ms后面4個(gè)磁道：20ms+1.5*0.0166s=44.9ms總時(shí)間：104.9+44.9*4=284.5ms612磁道——144扇區(qū)——512字節(jié)每簇8個(gè)扇區(qū)轉(zhuǎn)一圈時(shí)間為60*1000/3600=0.0166磁道到磁道尋道時(shí)間為20ms平均尋道時(shí)間80ms2.第三版習(xí)題8.17假設(shè)一條記錄長(zhǎng)為32個(gè)字節(jié)，一個(gè)塊長(zhǎng)為1024個(gè)字節(jié)(因此每個(gè)塊共有32條記錄)，工作主存是1MB(還有用于I/O緩沖區(qū)、程序變量等的額外存儲(chǔ)空間)。對(duì)于使用置換選擇方法和一趟掃描多路歸并的最大的文件，預(yù)計(jì)的大小是多少？解釋你是怎么得到這個(gè)結(jié)果的。答案：工作主存是1MB，塊長(zhǎng)是1KB，因此工作內(nèi)存有1024塊。在平均情況下，如果工作內(nèi)存的大小為M，使用置換選擇可以創(chuàng)建長(zhǎng)度為2M的順串，即使用置換選擇方法文件最大為2MB(見第二版課本P185);假定為置換選擇方法分配B個(gè)塊，（順串平均長(zhǎng)度就是2B個(gè)塊），接下來，進(jìn)行一個(gè)B路歸并，在一次多路歸并中，平均可以處理具有2B2個(gè)塊的文件，在一趟二路歸并中，平均可以處理具有2B(2+1)個(gè)塊大小的文件，即為2*10243B=2*210*3=2*230=2G3.Writeafunctiontomergetwolinkedlists.Elementsininputlistshavebeensortedfromlowesttohighest.Theoutputlistshouldbesortedfromhighesttolowest.Youralgorithmshouldruninlineartimeonthelengthoftheoutputlist.寫一個(gè)函數(shù)去合并兩個(gè)鏈表，兩個(gè)鏈表中的元素在初始狀態(tài)是有序的，并且是從小到大的順序排列，合并完成后的鏈表要求有序并且從高到低排列，算法的時(shí)間復(fù)雜度應(yīng)為O(n).答案：1.對(duì)L1，L2元素依次拿來比較，找到較小的一個(gè)，使用頭插法放置L中，相應(yīng)找下一個(gè)元素； 2.直到L1與L2有一個(gè)為空時(shí)，說明比較結(jié)束，那么把非空鏈表中的元素依次使用頭插法加入至L中即可。代碼如下：Linkmerge(LinkL1,LinkL2)//最后數(shù)據(jù)存放在新鏈表L，要求逆序采用頭插法{ Linkp,q,L,m,temp; p=L1->next;q=L2->next; L->next=null;m=null; while(p&&q) {

if(p->data<=q->data)

{

temp->data=p->data;//存入數(shù)據(jù)

temp->next=m; //使用頭插法建立鏈表

L->next=temp;//頭插法

m=temp;//頭插法

p=p->next;

}

else

{

temp->data=q->data;//存入數(shù)據(jù)

temp->next=m;L->next=temp;m=temp;

q=q->next;

} }//while while(p) { temp->data=p->data;//存入數(shù)據(jù) temp->next=m;L->next=temp;m=temp; p=p->next;

} while(q) { temp->data=q->data;//存入數(shù)據(jù) temp->next=m;L->next=temp;m=temp; q=q->next;

} returnL;};4.兩個(gè)單鏈表L1和L2中的元素類型相同，要求從L1中刪除那些同時(shí)在L2中出現(xiàn)的元素。若L1中有重復(fù)元素，要求只保留一個(gè)。分析所設(shè)計(jì)的算法的時(shí)間復(fù)雜度。Linkmerge(LinkL1,LinkL2){ Linkp,q,temp,pre; p=L1->next;temp=p->next;pre=L1;//從L1的第二個(gè)元素開始比較 while(p)//對(duì)L1依次遍歷，刪除相同元素 { while(temp)

if(p->data!=temp->data)temp=temp->next;

else{pre->next=pre->next->next;break;}

pre=p;p=p->next;//記錄當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)便于刪除 }

pre=L1;p=L1->next; temp=L2->next;//從L2的第一個(gè)元素開始比較 while(p)//對(duì)L1中的元素，依次與L2中比較，刪除相同元素 { while(temp)

if(p->data!=temp->data)temp=temp->next;

else{p->next=p->next->next;break;}

pre=p;p=p->next;//記錄當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)便于刪除 } returnL1；};時(shí)間復(fù)雜度為O(n2)(假設(shè)鏈表L1與L2的規(guī)模均為n)第十一次作業(yè)-查找9.6假定值A(chǔ)到H存儲(chǔ)在一個(gè)自組織線性表中，開始按照升序存放，對(duì)于9.2小節(jié)建議的三種自組織啟發(fā)式規(guī)則，按照下面順序訪問線性表，給出結(jié)果線性表和需要的比較總數(shù)：ＤＨＨＧＨＥＧＨＧＨＥＣＥＨＧ自組織線性表根據(jù)實(shí)際的記錄訪問模式在線性表中修改記錄順利。使用自啟發(fā)規(guī)則決定如何重新排列線性表。1．若在線性表中采用折半查找法查找元素，該線性表應(yīng)該（C）。A）元素按值有序 B）采用順序存儲(chǔ)結(jié)構(gòu)C）元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu)D）元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2．在下列查找方法中，平均查找速度是快的是（B）。A）順序查找 B）折半查找 C）分塊查找 D）二叉排序樹查找3．在關(guān)鍵字隨機(jī)分布的情況下，用二叉排序樹的方法進(jìn)行查找，其查找長(zhǎng)度與(B

）量級(jí)相當(dāng)。A）順序查找 B）折半查找 C）分塊查找 D）前面都不正確1.保持一個(gè)線性表按照訪問頻率排序的最顯然的方式是為每條記錄保存一個(gè)訪問計(jì)數(shù)。一直按照這個(gè)順序維護(hù)記錄，稱為計(jì)數(shù)方法(Count)2.如果找到一個(gè)記錄就將其放在線性表的最前面，而把后面的記錄后退一個(gè)位置。3.把找到的記錄與它在線性表中的前一條記錄交換位置，稱為轉(zhuǎn)置(transpose)9.13假定把關(guān)鍵碼K散列到有n個(gè)槽(從0到n-1編號(hào))的散列表中。對(duì)于下面的每一個(gè)函數(shù)h(K)，這個(gè)函數(shù)作為散列函數(shù)可以接受嗎?(即對(duì)于插入和檢索，散列程序能否正常工作)？如果可以的話，它是一個(gè)好的散列函數(shù)嗎？函數(shù)Random(n)返回一個(gè)0到n-1之間的隨機(jī)整數(shù)(包括這兩個(gè)數(shù)在內(nèi))。(a)h(k)=k/n,其中k和n都是整數(shù)；(b)h(k)=1；(c)h(k)=(k+Random(n))modn；(d)h(k)=kmodn，其中n是一個(gè)素?cái)?shù)；答案：(a)不可以。若k大于n平方,那么k/n的值就會(huì)超出n,超出范圍。(b)可以。但是所有的數(shù)據(jù)都散列到相同的槽位中(c)不可以。因?yàn)椴捎秒S機(jī)數(shù)，那么插進(jìn)去之后，檢索不到，因?yàn)椴恢来嗽厥鞘褂昧耸裁磾?shù)據(jù)進(jìn)行插入的(d)可以9.14假定一個(gè)有7個(gè)槽的散列表(槽從0到6編號(hào))。如果將散列函數(shù)h(k)=kmod7和線性探測(cè)用于一組數(shù)字3，12，9，2，給出最后的結(jié)果散列表。在插入值為2的關(guān)鍵碼之后，列出每一個(gè)空槽作為下一個(gè)被填充槽的概率。9.16使用閉散列，利用雙散列的方法解決沖突，把下面的關(guān)鍵碼插入到一個(gè)有13個(gè)槽的散列表中(槽從0到12編號(hào))。使用的散列函數(shù)H1和H2在下面定義。給出插入8個(gè)關(guān)鍵碼值后的散列表。一定要說明如何使用H1和H2進(jìn)行散列。函數(shù)Rew(k)顛倒10進(jìn)制數(shù)k各個(gè)位的數(shù)字，例如Rew(37)=73,Rew(7)=7。H1(k)=kmod13.H2(k)=(Rew(k+1)mod11).答案：雙散列：di=i*Hash2(key)，當(dāng)通過第一個(gè)散列函數(shù)得到的地址發(fā)生沖突之后，則利用第二個(gè)散列函數(shù)計(jì)算該關(guān)鍵字的地址增量，在雙散列中，最多經(jīng)過m次探測(cè)就會(huì)遍歷表中所有的位置，會(huì)到H0的位置。Hi=（H（key）+di）%mH1：2,8,5,7,6,5,1,1H2：3,9,1,1,2,3,1,5插入過程：2------>2成功8------>8成功31----->5成功20----->7成功19----->6成功18----->5沖突；使用H1()+H2()=5+3=8

沖突

使用H1+H2+H2=5+3+3=11

成功53----->1成功27----->1沖突；使用H1()+H2()=1+5=6

沖突,

使用H1+H2()+H2()=1+5+5=11

沖突

使用H1()+H2()+H2()+H2()=(1+5+5+5)%13=3

成功1．已知關(guān)鍵字序列{23，13，5，28，14，25}，試構(gòu)造二叉排序樹。

23

/

\

13

28

/

\

/

5

14

25

2.已知一組關(guān)鍵字為（19，14，23，1，68，20，84，27，55，