數(shù)據(jù)結(jié)構(gòu)考研真題及其答案-資料下載頁
2025-06-23 22:44本頁面
【正文】 執(zhí)行循環(huán)體，賦值語句A[i]執(zhí)行了一次；最壞情況出現(xiàn)在二進(jìn)制數(shù)各位均為1（最高位為零，因題目假設(shè)無溢出），這時循環(huán)體執(zhí)行了n1次，時間復(fù)雜度是O(n)，循環(huán)體平均執(zhí)行n/2次，時間復(fù)雜度仍是O(n)。22. 閱讀下列算法，指出算法A的功能和時間復(fù)雜性 PROCEDURE A (h,g:pointer)。(h,g分別為單循環(huán)鏈表（single linked circular list）中兩個結(jié)點指針)PROCEDURE B(s,q:pointer)； VAR p:pointer。 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)鏈表分解成兩個單循環(huán)鏈表：其一包括結(jié)點h到結(jié)點g的前驅(qū)結(jié)點；另一個包括結(jié)點g到結(jié)點h的前驅(qū)結(jié)點。時間復(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)時的輸出結(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時，f(5)=55，執(zhí)行過程中，輸出結(jié)果為：sum=15,sum=29,sum=41,sum=50,sum=55（每個sum= 占一行,為節(jié)省篇幅，這里省去換行）。24．設(shè)n是偶數(shù)，試計算運行下列程序段后m的值并給出該程序段的時間復(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的值等于賦值語句m:=m+1的運行次數(shù)，其計算式為25．有下列運行時間函數(shù)： （1）T1 (n)=1000。 （2）T2(n)=n2+1000n。 （3）T3(n)=3n3+100n2+n+1。分別寫出相應(yīng)的大O表示的運算時間。(1)O(1) (2)O(n2) (3)O(n3)【吉林工業(yè)大學(xué) 1999 二（12分）】26. 試給出下面兩個算法的運算時間。 （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【中科院自動化研究所 1995 二、2 （6分）】(1)O(n) (2)O(n2)27. 斐波那契數(shù)列Fn定義如下 F0=0， Fl=1， Fn=Fn1+Fn2, n=2,3... 請就此斐波那契數(shù)列，回答下列問題。 (1) (7分) 在遞歸計算Fn的時候，需要對較小的Fn1，F(xiàn)n2，…, Fl, F0精確計算多少次? (2) (5分) 如果用大O表示法，試給出遞歸計算Fn時遞歸函數(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，這也是一個斐波那契數(shù)列。可以解得：Bm=[()nm+2()nm+2] (m=0,1,2,…,n1)（2）時間復(fù)雜度為O(n)28．將下列函數(shù)，按它們在n→∝時的無窮大階數(shù)，從小到大排序。 n, nn3+7n5, nlogn, 2n/2, n3, logn, n1/2+logn, (3/2)n, ,n!, n2+logn【中科院計算所 1995 080385】從小到大排列為：logn, n1/2+logn, n, nlogn, n2+logn，n3, nn3+7n5, 2n/2, (3/2)n, n!,
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1