數(shù)據(jù)結(jié)構(gòu)考研真題和答案-資料下載頁(yè)
2025-06-23 22:44本頁(yè)面
【正文】 er。 BEGIN p:=s。 WHILE p^.nextq DO p:=p^.next。 p^.next:=s。 END。(of B)BEGINB(h,g)。 B(g,h)。END。（of A）【東南大學(xué) 1999 二（10分）】該算法功能是將原單循環(huán)鏈表分解成兩個(gè)單循環(huán)鏈表：其一包括結(jié)點(diǎn)h到結(jié)點(diǎn)g的前驅(qū)結(jié)點(diǎn)；另一個(gè)包括結(jié)點(diǎn)g到結(jié)點(diǎn)h的前驅(qū)結(jié)點(diǎn)。時(shí)間復(fù)雜度是O(n)。23. 調(diào)用下列C函數(shù)f(n)或PASACAL函數(shù)f(n) 回答下列問題 :（1） 試指出f(n)值的大小，并寫出f(n) 值的推導(dǎo)過程。（2） 假定n= 5，試指出f(5)值的大小和執(zhí)行f(5)時(shí)的輸出結(jié)果 。 C函數(shù)： int f(int n) { int i,j，k,sum= 0。 for(i=l。 in+1。i++) {for(j=n。ji1。 j) for(k=1。kj+1。k++ ) sum++。 printf(sum=%d\n,sum)；} return (sum)。} 【華中理工大學(xué) 2000 六（10分）】第一層FOR循環(huán)判斷n+1次，往下執(zhí)行n次，第二層FOR執(zhí)行次數(shù)為(n+(n1)+(n2)+…+1)，第三層循環(huán)體受第一層循環(huán)和第二層循環(huán)的控制，其執(zhí)行次數(shù)如下表： i= 1 2 3 … n j=n n n n … n j=n1 n1 n1 n1 … … … … …j=3 3 3j=2 2 2j=1 1執(zhí)行次數(shù)為(1+2+…+n)+(2+3+…+n)+…+n=n*n(n+1)/2n(n21)/6。在n=5時(shí)，f(5)=55，執(zhí)行過程中，輸出結(jié)果為：sum=15,sum=29,sum=41,sum=50,sum=55（每個(gè)sum= 占一行,為節(jié)省篇幅，這里省去換行）。24．設(shè)n是偶數(shù)，試計(jì)算運(yùn)行下列程序段后m的值并給出該程序段的時(shí)間復(fù)雜度。m:=0。FOR i:=1 TO n DO FOR j:=2*i TO n DO m:=m+1?！灸暇┼]電大學(xué) 2000 一、1】O(n2),m的值等于賦值語(yǔ)句m:=m+1的運(yùn)行次數(shù)，其計(jì)算式為25．有下列運(yùn)行時(shí)間函數(shù)： （1）T1 (n)=1000。 （2）T2(n)=n2+1000n。 （3）T3(n)=3n3+100n2+n+1。分別寫出相應(yīng)的大O表示的運(yùn)算時(shí)間。(1)O(1) (2)O(n2) (3)O(n3)【吉林工業(yè)大學(xué) 1999 二（12分）】26. 試給出下面兩個(gè)算法的運(yùn)算時(shí)間。 （1） for i←1 to n do x ← x+1 END（2） for i← 1 to n do for j←1 to n do x← x+1 end end【中科院自動(dòng)化研究所 1995 二、2 （6分）】(1)O(n) (2)O(n2)27. 斐波那契數(shù)列Fn定義如下 F0=0， Fl=1， Fn=Fn1+Fn2, n=2,3... 請(qǐng)就此斐波那契數(shù)列，回答下列問題。 (1) (7分) 在遞歸計(jì)算Fn的時(shí)候，需要對(duì)較小的Fn1，F(xiàn)n2，…, Fl, F0精確計(jì)算多少次? (2) (5分) 如果用大O表示法，試給出遞歸計(jì)算Fn時(shí)遞歸函數(shù)的時(shí)間復(fù)雜度錄多少?【清華大學(xué) 2000 二（12分）】（1）由斐波那契數(shù)列的定義可得：Fn=Fn1+Fn2 =2Fn2+Fn3 =3Fn3+2Fn4 =5Fn4+3Fn5 =8Fn5+5Fn6 …… =pF1+qF0設(shè)Fm的執(zhí)行次數(shù)為Bm(m=0、…、n1)，由以上等式可知，F(xiàn)n1被執(zhí)行一次，即Bn1=1；Fn2被執(zhí)行兩次，即Bn2=2；直至F1被執(zhí)行p次、F0被執(zhí)行q次，即B1=p，B0=q。Bm的執(zhí)行次數(shù)為前兩等式第一因式系數(shù)之和，即Bm=Bm1+Bm2，再有Bn1=1和Bn2=2，這也是一個(gè)斐波那契數(shù)列?？梢越獾茫築m=[()nm+2()nm+2] (m=0,1,2,…,n1)（2）時(shí)間復(fù)雜度為O(n)28．將下列函數(shù)，按它們?cè)趎→∝時(shí)的無(wú)窮大階數(shù)，從小到大排序。 n, nn3+7n5, nlogn, 2n/2, n3, logn, n1/2+logn, (3/2)n, ,n!, n2+logn【中科院計(jì)算所 1995 080385】從小到大排列為：logn, n1/2+logn, n, nlogn, n2+logn，n3, nn3+7n5, 2n/2, (3/2)n, n!, 單純的課本內(nèi)容，并不能滿足學(xué)生的需要，通過補(bǔ)充，達(dá)到內(nèi)容的完善 教育之通病是教用腦的人不用手，不教用手的人用腦，所以一無(wú)所能。教育革命的對(duì)策是手腦聯(lián)盟，結(jié)果是手與腦的力量都可以大到不可思議。歡迎您的光臨，！希望您提出您寶貴的意見，你的意見是我進(jìn)步的動(dòng)力。贈(zèng)語(yǔ)； 如果我們做與不做都會(huì)有人笑，如果做不好與做得好還會(huì)有人笑，那么我們索性就做得更好，來給人笑吧！ 現(xiàn)在你不玩命的學(xué)，以后命玩你。我不知道年少輕狂，我只知道勝者為王。不要做金錢、權(quán)利的奴隸；應(yīng)學(xué)會(huì)做“金錢、權(quán)利”的主人。什么時(shí)候離光明最近？那就是你覺得黑暗太黑的時(shí)候。最值得欣賞的風(fēng)景，是自己奮斗的足跡。壓力不是有人比你努力，而是那些比你牛幾倍的人依然比你努力。 參考
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1