數(shù)據(jù)結(jié)構(gòu)與算法離線作業(yè)

1、浙江大學(xué)遠程教育學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法課程離線作業(yè)一、填空題：(【序號，章，節(jié)】。)1,1,2】線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系,圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。2,1,2】為了最快地存取數(shù)據(jù)元素，物理結(jié)構(gòu)宜采用順序存儲結(jié)構(gòu)。3,1,2存儲結(jié)構(gòu)可根據(jù)數(shù)據(jù)元素在機器中的位置是否一定連續(xù)分為順序存儲結(jié)構(gòu),鏈式存儲結(jié)構(gòu)。4,1,3】度量算法效率可通過時間復(fù)雜度來進行。5,1,3設(shè)n為正整數(shù),下面程序段中前置以記號的語句的頻度是n(n+1)/20for(i=0;i<n;i+)for(j=0;j<n;j+)if(i+j=n-1)aij=0;)6,1,3設(shè)n為正

2、整數(shù)，試確定下列各程序段中前置以記號的語句的頻度：(1)i=1;k=0;while(i<=n-1)i+;k+=10*i;/語句的頻度是_n-1)k=0;for(i=1;i<=n;i+)for(j=i;j<=n;j+)k+;/語句的頻度是n(n+1)/2)7,3,2】線性表(a1，a2,，an)有兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)，請就這兩種存儲結(jié)構(gòu)完成下列填充：順序_存儲密度較大；順序存儲利用率較高；順序存儲可以隨機存??；鏈式存儲不可以隨機存??；鏈式存儲插入和刪除操作比較方便。8,3,2從一個長度為n的順序表中刪除第i個元素（1&in時，需向前移動n-i個元素。

3、9,3,2】帶頭結(jié)點的單鏈表Head為空的條件是Head->next=NULL。10,3,2】在一個單鏈表中p所指結(jié)點（p所指不是最后結(jié)點）之后插入一個由指針s所指結(jié)點，應(yīng)執(zhí)行s->next=p->next二和p->next=s的操作。11,3,2】在一個單鏈表中刪除p所指結(jié)點時，應(yīng)執(zhí)行以下操作：q=p->next;p->data=p->next->data;p->next=p->next->next;free（q）;12,3,2帶頭結(jié)點的單循環(huán)鏈表Head的判空條件是Head->next=Head;不帶頭結(jié)點的單循環(huán)鏈表

4、的判空條件是Head=NULL;。13,3,2】已知L是帶表頭結(jié)點的非空單鏈表，且P結(jié)點既然不首元結(jié)點，也不是尾元結(jié)點試從下列提供的答案中選擇合適的語句序列。a.刪除P結(jié)點的直接前驅(qū)結(jié)點的語句序列是_1012811414b.刪除結(jié)點P的語句序列是10127314c.刪除尾元結(jié)點的語句序列是9113140(1) P=P->next;(2) P->next=P;(3) P->next=P->next->next;(4) P=P->next->next;(5) while(P!=NULL)P=P->next;(6) while(Q->next!=

5、NULL)P=Q;Q=Q->next;while(P->next!=Q)P=P->next;(8) while(P->next->next!=Q)P=P->next;(9) while(P->next->next!=NULL)P=P->next;(10) Q=P;(11) Q=P->next;(12) P=L;(13) L=L->next;(14) free(Q);14,3,3】對一個棧，給定輸入的順序是A、B、C,則全部不可能的輸出序列有不可能得到的輸出序列有CAB。15,3,3】.在棧頂指針為HS的鏈棧中，判定?？盏臈l件是h

6、ead->next=NULL016,3,3】下列程序把十進制數(shù)轉(zhuǎn)換為十六進制數(shù)，請?zhí)顚懞线m的語句成分。voidconversion10_16()InitStack(&s);scanf("d,&N);while(N)Push(s,N%16);N=N/16;while(!StackEmpty(s)Pop(s,e);if(e<=9)printf("d,e);elseprintf("0+,eA');/*conversion*/17,3,4若用一個大小為6個元素的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear=0和front=3。當從隊列中刪除一個元

7、素，再加入兩個元素后，rear和front的值分別是N和4018,3,4】堆棧和隊列都是線性表，堆棧是后進先出的線性表，而隊列是先進先出的線性表。19,3,4若用一個大小為6個元素的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear=0和front=3。當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別是2和4。20,4,2已知一棵樹邊的集合是<a,d>,vd,c>,vd,j>,ve,a>,vf,g>,vd,b>,vg,h>,vg,i>,ve,f>。那么根結(jié)點是e:結(jié)點b的雙親是d:結(jié)點a的子孫有bcdj,樹的深度是4,樹的度是二

8、,結(jié)點g在樹的第3層。21,4,3從概念上講，樹與二叉樹是二種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本的目的是樹可采用二叉樹的存儲結(jié)構(gòu)并利用二叉樹的已有算法解決樹的有關(guān)問題022,4,3】滿三叉樹的第i層的結(jié)點個數(shù)為f,深度為h時該樹中共有必1結(jié)點023,4,3】已知一棵完全二叉樹有56個葉子結(jié)點，從上到下、從左到右對它的結(jié)點進行編號，根結(jié)點為1號。則該完全二叉樹總共結(jié)點有111個:有7層；第91號結(jié)點的雙親結(jié)點是45號:第63號結(jié)點的左孩子結(jié)點是126號。24,4,3】下列表示的圖中，共有5一個是樹；有_3個是二叉樹；有2個是完全二叉樹n、最小深度為log2n+125,4,4】n個結(jié)點的二叉排

9、序樹的最大深度是26,4,3】如果某二叉樹的后序遍歷序列是ABCDEFGHI,中序遍歷序歹是ACBIDFEHG，則其先序遍歷序列的第一個字母是I.最后一個字母是G。27,4,3】下列二叉樹的中序遍歷序列是DBNGOAEC；后序遍歷序歹U是DNOGBECA28,5,4設(shè)HASH表的大小為n(n=10),HASH函數(shù)為h(x)=x%7,如果二次探測再散列方法Hi=(H(key)+di)mod10(di=12,22,32)解決沖突，在HASH表中依次插入關(guān)鍵字1,14,55,20,84,27以后，關(guān)鍵字1、20和27所在地址的下標分別是J、7和5。插入上述6個元素的平均比較次數(shù)是2029,6,3設(shè)無

10、權(quán)圖G的鄰接矩陣為A,若(vi,vj)屬于圖G的邊集合，則對應(yīng)元素Aij等于/_,22、設(shè)無向圖G的鄰接矩陣為A,若Aij等于0,則A皿i等于0030,6,3若一個圖用鄰接矩陣表示，則刪除從第i個頂點出發(fā)的所有邊的方法是矩陣第i行全部置為零。31,6,2】設(shè)一個圖G=V,A,V=a,b,c,d,e,f,A=<a,b>,<b,e>,<a,e>,<c,a>,<e,d>,<d,f>,<f,c>。那么頂點e的入度是2:出度是1:通過頂點f的簡單回路有2條:就連通性而言，該圖是強連通圖;它的強連通分量有1個:其生成樹可能

11、的最大深度是5o32,7,1】排序過程一般需經(jīng)過兩個基本操作，它們是比較和移動。33,7,2在對一組關(guān)鍵字是(54,38,96,45,15,72,60,23,83的記錄進行直接插入排序時，當把第七個記錄(關(guān)鍵字是60)插入到有序表時，為尋找插入位置需比較3次34,7,4】插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序、和基數(shù)排序方法中，不穩(wěn)定的排序方法有希爾排序、快速排序、堆排序。二、綜合題(選自教材數(shù)據(jù)結(jié)構(gòu)各章習(xí)題，采用word文件格式上傳)1,1,3】試分析下面一段代碼的時間復(fù)雜度:if(A>B)for(i=0;i<N;i+)for(j=N*N;j>i;j-)A

12、+=B;)elsefor(i=0;i<N*2;i+)for(j=N*2;j>i;j-)A+=B;)分析：ifA>B為真，則for語句的外循環(huán)N次，內(nèi)循環(huán)為N(N-1)次，因此時間復(fù)雜度為O(N*N(N-1),也就是N的三次方。1)ifA>B為假，則for語句的外循環(huán)2N次，內(nèi)循環(huán)為N次，因此時間復(fù)雜度為O(2N*N),也就是N的平方。2,1,3測試例1.3中秦九韶算法與直接法的效率差別。令f(x)=1+Z100xi/i,計算f(1.1)的值。利用clock()函數(shù)得到兩種算法在同一機器上的運行時間。運行結(jié)果：#include<stdio.h>#include

13、<time.h>#include<math.h>clock_tstart,stop;doubleduration;#defineMAXN10#defineMAXK1e7doublef1(intn,doublea,doublex)(inti;doublep=a0;for(i=1;i<=n;i+)p+=(ai*pow(x,i);returnp;doublef2(intn,doublea,doublex)(inti;doublep=an;for(i=n;i>0;i-)p=ai-1+x*p;returnp;voidrun(double(*f)(int,double*

14、,double),doublea,intcase_n)(inti;start=clock();for(i=0;i<MAXK;i+)(*f)(MAXN-1,a,1.1);stop=clock();duration=(double)(stop-start)/CLK_TCK;printf("ticks%d=%fn",case_n,(double)(stop-start);printf("duration%d=%6.2en”,case_n,duration);intmain()inti;doubleaMAXN;for(i=0;i<MAXN;i+)ai=(dou

15、ble)i;run(f1,a,1);run(f2,a,2);return0;運行結(jié)果：ticks1=10654.000000duration1=1.07e+001ticks2=796.000000duration2=7.96e-0013,1,3】試分析最大子列和算法1.3的空間復(fù)雜度。若記整體時間復(fù)雜度為T(N)0通過遞歸實現(xiàn)“分”的復(fù)雜度為2T(N/2)。求跨分界線的最大子列和有兩個簡單的for循環(huán)，所用步驟一共不超過N,可以在O(N)時間完成。其他步驟都只需要常數(shù)O(1)T二0；T(N)=2T(N/2)+0(N)=22T(N/2)/2)+0(N/2)+0(N)=22T(N/22)+20(N

16、)=,=2kT(N/2k)+k0(N)不斷對分到N/2k=1,即2k=N,可得到T(N)=NT(1)+logN0(N)=0(NIogN)4,1,3】試給出判斷N是否為質(zhì)數(shù)的0(JN)的算法。#include<stdio.h>#include<math.h>intis_prime(intn)inti;if(n!=2&&n%2=0|n=1)return0;10if(n=2)return1;for(i=3;i<=sqrt(double)n);i+=2)if(n%i=0)return0;return1;voidmain()intnum,result;pri

17、ntf("pleaseinputthenum:");scanf("%d”,&num);result=is_prime(num);if(result)printf("%disaprimen",num);elseprintf("%disnotaprimen",num);執(zhí)行結(jié)果：11ttinclude<stdio.h>Kinclude<math.h>int15_priie(intn)inti;5,2,2】請編寫程序，輸入整數(shù)n和a,輸出S=a+aa+aaa+aa-a（n個a）的結(jié)果。#includ

18、e<stdio.h>voidmain()inta,b,n,i,s=0;printf("請輸入整數(shù)n和a:n"）;scanf("%d%d",&n,&a);b=a;for(i=1;i<=n;i+)s+=a;個a)=%dn",s);a=a*10+b;printf("S=a+aa+aaa+,+aa,a(n12執(zhí)行結(jié)果:ilinclude<5tdlo.h>voidnain()intaFb,n,i,5=0；printf(,請輸入整數(shù)n和:二l-月dq口一一,h”'C:testDebugCppi

19、.exe¥請輸入整數(shù)n和息：106S=a+aa+ai*a+,+aa,a<n個a)=-1182S2!7192Pressanykeytocontinue6,2,3】請編寫遞歸函數(shù)，輸出123.n的全排列(n小于10),并觀察n逐步增大時程序的運行時間。#include<stdio.h>#include<time.h>voidpailie(int*data,intn,intcurr)inti;if(curr=n-1)for(i=0;i<n;+i)printf("%d",datai);printf("n");else

20、for(i=curr;i<n;+i)intt;t=datacurr,datacurr=datai,datai=t;13pailie(data,n,curr+1);t=datacurr,datacurr=datai,datai=t;)intmain()clock_tend;clock_tstart=clock();intn=0;inti=0;intas10;scanf("%d",&n);for(i=0;i<n;+i)asi=i+1;)pailie(as,n,0);end=clock();printf("Thetimewas:%dn",(

21、end-start)/CLK_TCK);return0;14執(zhí)行結(jié)果:include<stdio-h>Ninclude<tine.h>voidpailie(int*dataTintn,intcurr)(-&<4.一'C:testDebugCppl,xe*613425613542&13524E132546132456143526143256145326145236142536142居615432“5423615342&1S3246152346152436124536124356125436125m461235461234sThetim

22、ewas：3Q7,3,2給定一個順序存儲的線性表L=(ai,a2,，an),請設(shè)計一個算法刪除所有值大于min而且小于max的元素#include<stdio.h>voiddels(inta口,int*n,intmin,intmax)inti,j,k;15for(i=j=k=0;i<*n;i+)if(ai>min&&ai<max)k+;elseaj+=ai;*n-=k;intmain()inta14=67,57,76,78,99,90,96,87,93,76,68,79,24,98;intmax,min,n=14,i;printf("原有

23、的數(shù):n");for(i=0;i<n;i+)16printf("nminmax=");scanf("%d%d",&min,&max);dels(a,&n,min,max);printf("刪除后的數(shù):n");for(i=0;i<n;i+)printf("%d",ai);return0;執(zhí)行結(jié)果:17ttinclude<stdio.h>uoiddls<int*nTintmin,intmax)<inti,j,l<8,3,2給定一個順序存儲的線性

24、表L=(ai,a2,，aj,請設(shè)計一個算法查中最長的遞增子序找該線性表中最長遞增子序列。例如，(1,9,2,5,7,3,4,6,8,0)列為(3,4,6,8)#include<stdio.h>structnodeintb;/存儲當前數(shù)的數(shù)值intk;記錄該數(shù)開始的遞增情況)s100001;intmain()inti,j;intn;18intmaxi=1,c;scanf("%d",&n);for(i=0;i<n;i+)scanf("%d",&si.b);for(i=0;i<n;i+)si.k=1;for(i=0;i&

25、lt;n-1;i+)for(j=i+1;j<n;j+)/判斷是否為遞增的，后面的大于前面的，即為遞增if(sj.b>sj-1.b)si.k+;elsebreak;for(i=0;i<n;i+)if(si.k>maxi)/連續(xù)遞增的數(shù)的個數(shù)大于當前最大值19c=i;/從i開始的序列)for(i=c;i<c+maxi-1;i+)printf("%d",si.b);printf("%dn",sc+maxi-1.b);return0;)執(zhí)行結(jié)果：'C:tfstDebugCppl.exe"in垣一8anykeytoc

26、ontinme20pop,push)順9,3,3】如果有1、2、3、4、5按順序入棧，不同的堆棧操作(序可得到不同的堆棧輸出序列。請問共有多少種不同的輸出序列？為什么?共有34種不同的輸出序列12345123541243512543132451325414325154322134521435215432314523154234152345123541243152435124531254313214532154324513254134215342513452135421432154325143521453215432110,3,2】請編寫程序?qū)⒅芯Y表達式轉(zhuǎn)換為后綴表達式。#include<

27、iostream>#include<stack>#include<string>usingnamespacestd;intprior(charop)if(op='+'|op='-')return1;if(op='*'|op='/')return2;return0;21)stringmiddletolast(stringmiddle)(stack<char>op;stringans;for(inti=0;i<middle.size();i+)(charc=middlei;if(c>

28、;='0'&&c<二'9')(ans.append(1,c);)else(if(c='(')op.push('(');else(if(c=')')22while(op.top()!='(')(ans.append(1,op.top();op.pop();)op.pop();)else(if(op.empty()(op.push(c);)else(if(prior(c)>prior(op.top()op.push(c);else(while(!op.empty()&

29、&prior(c)<=prior(op.top()23ans.append(1,op.top();op.pop();)op.push(c);)while(!op.empty()(ans.append(1,op.top();op.pop();)returnans;)intmain()24stringmdata,res;cin>>mdata;res=middletolast(mdata);for(inti=0;i<res.size();i+)(if(i=0)cout<<resi;elsecout<<''<<resi

30、;cout<<endl;return0;11,4,3】設(shè)二叉樹的存儲結(jié)構(gòu)如下:12345678910Lchild0012375r801011dataJHFDBACEGIRchild0009400000data為其中根結(jié)點的指針值為6,Lchild,Rchild分別為結(jié)點的左、右孩子指針域,數(shù)據(jù)域。25(1)畫出二叉樹的邏輯結(jié)構(gòu)A(2)寫出該樹的前序、中序和后序遍歷的序列前序遍歷：ABCEDFHGIJ中序遍歷：ECBHFDJIGA后續(xù)遍歷：ECHFJIGDBA12,4,4】可以生成如下二叉排序樹的關(guān)鍵字的初始排列有幾種？請寫出其中的任意4答：可以生成如上二叉排序樹的關(guān)鍵字的初始排列有

31、30種任寫4個序列如下：(5,7,6,4,2,1,3)(5,7,6,4,2,3,1)261171342216511516422137(5,4,2,3,7,6,1)(5,4,2,1,7,6,3)13,4,5給定關(guān)鍵字序列（11、7、16、4、22、13、5）,請回答:（1）畫出依次插入到一棵空的二叉排序樹后的最終二叉樹（6分）;27畫出依次把給定序列關(guān)鍵字插入一棵空的平衡二叉樹后的結(jié)果（4分）;14,4,6】假設(shè)一個文本使用的字符集為a,b,c,d,e,f,g,字符的哈夫曼編碼依次為0110,10,110,111,00,0111,010。(1)請根據(jù)哈夫曼編碼畫出此哈夫曼樹，并在葉子結(jié)點中標注相

32、應(yīng)的字符；010101、/、e010g)()(cd011fclaf(2)若這些字符在文本中出現(xiàn)的頻率分別為：3,35,13,15,20,5,9,求該哈夫曼樹的帶權(quán)路徑長度。帶權(quán)路徑長度值為：4*(3+5)+3*(9+13+15)+2*(20+35)=2532815,5,3】用公式5.6計算一下你的身份證號碼的散列值是多少。#include<stdio.h>voidmain()ints256;int*p;doubleseed=5.6;doubleh=0;scanf("%s",s);for(p=s;*p;p+)h=h*seed+*p;printf("%ll

33、un",h);執(zhí)行結(jié)果:C:testDebugCppl.exe*2916,5,4】設(shè)有一組關(guān)鍵字29,01,13,15,56,20,87,27,69,9,10,74,散列函數(shù)為：H(key)=key%17，采用平方探測方法解決沖突。試在0到18的散列地址空間中對該關(guān)鍵字序列構(gòu)造散列表。首先將各個數(shù)除以17取余數(shù)：(6,2,7,1,2,7,7,6)可見20,85與46沖突，58與71沖突。將7+1再對13取余，直到無沖突，類似的6+1對13取余，最后可得H(71)=6;H(28)=2;H(14)=1;H(2)=3;H(20)=8;H(85=9;H(58)=10);哈希表存儲結(jié)構(gòu)：012

34、345678910142827146208558平均查找長度=(1x4+2x2+3x1+4x1)/8=15/817,5,4】將關(guān)鍵字序列(7,8,30,11,18,9,14)散列存儲到散列列表中，散列表的存儲空間是一個下標從0開始的一個一維數(shù)組。處理沖突采用線性探測法，散列函數(shù)為：H(key)=(keyX3)modTableSize,要求裝入因子為0.7。關(guān)鍵字78301118914散列地址1403472線性探測法構(gòu)建列表的過程012345678930插入77插入88插入3030插入1111插入185d1=1插入97插入141418,6,3】已知一個無向圖的頂點集為V0,Vi,，V7,其鄰接矩

35、陣如下所示:V0ViV2V3V4V5V6V7二01011001010101000001000100010001000、1000010000100010000010010001j(1)畫出該圖的圖形;31(2)給出從V0出發(fā)的深度優(yōu)先遍歷序和廣度優(yōu)先遍歷序深度優(yōu)先序列V0,V1,V2,V5,V4,V6,V3,V7廣度優(yōu)先序歹UV0V1V3V4V2V6V5V719,6,3】已知有向圖如右圖所示，請給出該圖的(D(2)每個頂點的入度和出度；各頂點的入/出度如下：頂點1:3/0;頂點2:2/2;頂點3:1/2;頂點4:1/2;頂點5:2/1;頂點6:2/3鄰接矩陣；(6)2、4)12341561100

36、000010°1003010001400101151000006110010(3)鄰接表;1固I322>143624k3k565161255(4)逆鄰接表；1 >2562 3»63 44 25 4466 >3>4(5)各個強連通分量20,6,3】試利用Dijkstra算法求下圖在從頂點A到其它頂點的最短距離及對應(yīng)的路徑，寫出計算過程中各步狀態(tài)。最短路徑A到B:A-B,大小為1533A到C:A-C,大小為2A到D:A-D,大小為12A到E:A-CE,大小為10A到F:ACF,大小為6A到G:A-DG,大小為1521,6,3給出如下圖所示的具有7個結(jié)點的

37、網(wǎng)Go請:(1)畫出該網(wǎng)的鄰接矩陣；012345601234560130005100400630004030400072004001500071025632520(2)采用Prim算法，從4號結(jié)點開始，給出該網(wǎng)的最小生成樹(畫出Prim算法的執(zhí)行過程及最小生成樹的生成示意圖)。voidprim(MGraphg,intv0,int&sum)intlowcostMAXSIZE,vsetMAXSIZE;34/pre存入前驅(qū)結(jié)點數(shù)組intv,preMAXSIZE;inti,j,k,min;v=v0;初始起點for(i=1;i<=g.n;i+)lowcosti=g.edgesv0i;/lowcost附數(shù)組prei=v0;vseti=0;vsetv0=1;sum=0;for(i=1;imin=INF;for(j=1;j<=g.n;j+)if(vsetj=0&&lowcostjmin=lowcostj;k=j;vsetk=1;/將此結(jié)點并入到所夠造的生成樹中v=k;if(min!=INF)printf("邊的起點為：d終點為：d權(quán)值為%dn",prev,v,min);sum+=min;elsebreak;for(j=1;j<=g.n;j+)/并入新結(jié)點后修改剩下的結(jié)點到生成樹的權(quán)值if(vsetj