數(shù)據(jù)結(jié)構(gòu)考研分類復(fù)習(xí)真題第一章緒論之應(yīng)用題_跨考網(wǎng)

　　2. 數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有幾種表示方法？各有什么特點(diǎn)？【燕山大學(xué)1999 二、2（4分）】

　　3. 數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何相同和不同之處，抽象數(shù)據(jù)類型的主要特點(diǎn)是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？【北京郵電大學(xué) 1994 一（8分）】

??????? 4. 回答問題（每題2分）【山東工業(yè)大學(xué) 1997 一 （8分）】

　?。?）在數(shù)據(jù)結(jié)構(gòu)課程中，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)的運(yùn)算之間存在著怎樣的關(guān)系？

　?。?）若邏輯結(jié)構(gòu)相同但存儲(chǔ)結(jié)構(gòu)不同，則為不同的數(shù)據(jù)結(jié)構(gòu)。這樣的說法對(duì)嗎？舉例說明之。

　?。?）在給定的邏輯結(jié)構(gòu)及其存儲(chǔ)表示上可以定義不同的運(yùn)算集合，從而得到不同的數(shù)據(jù)結(jié)構(gòu)。這樣說法對(duì)嗎？舉例說明之。

　　（4）評(píng)價(jià)各種不同數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)是什么？

　　5．評(píng)價(jià)一個(gè)好的算法，您是從哪幾方面來考慮的？【大連海事大學(xué) 1996? 二、3 （2分）】【中山大學(xué) 1998 三、1 （5分）】

　　6．解釋和比較以下各組概念【華南師范大學(xué) 2000 一（10分）】

　?。?）抽象數(shù)據(jù)類型及數(shù)據(jù)類型

　?。?）數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)

　　（3）抽象數(shù)據(jù)類型【哈爾濱工業(yè)大學(xué) 2000 一、1（3分）】

　　（4）算法的時(shí)間復(fù)雜性 【河海大學(xué) 1998 一、2（3分）】

　　（5）算法【吉林工業(yè)大學(xué)1999? 一、1（2分）】

　　（6）頻度【吉林工業(yè)大學(xué) 1999 一、2（2分）】

??? 　7. 根據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系，一般有哪幾類基本的數(shù)據(jù)結(jié)構(gòu)？【北京科技大學(xué) 1998 一、1】【同濟(jì)大學(xué) 1998】

　　8．對(duì)于一個(gè)數(shù)據(jù)結(jié)構(gòu)，一般包括哪三個(gè)方面的討論？【北京科技大學(xué) 1999 一、1（2分）】

　　9. 當(dāng)你為解決某一問題而選擇數(shù)據(jù)結(jié)構(gòu)時(shí)，應(yīng)從哪些方面考慮？【西安電子北京科技大學(xué) 2000】

　　10. 若將數(shù)據(jù)結(jié)構(gòu)定義為一個(gè)二元組（D，R）,說明符號(hào)D，R 應(yīng)分別表示什么？【北京科技大學(xué) 2001 一、1（2分）】

　　11．?dāng)?shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型有什么區(qū)別？【哈爾濱工業(yè)大學(xué)? 2001 三、1（3分）】

　　12．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)由哪四種基本的存儲(chǔ)方法實(shí)現(xiàn)？【山東科技大學(xué) 2001 一、1（4分）】

　　13．若有100個(gè)學(xué)生，每個(gè)學(xué)生有學(xué)號(hào)，姓名，平均成績，采用什么樣的數(shù)據(jù)結(jié)構(gòu)最方便，寫出這些結(jié)構(gòu)？【山東師范大學(xué) 1996 二、2（2分）】

　　14. 運(yùn)算是數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要方面。試舉一例，說明兩個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)方式完全相同，只是對(duì)于運(yùn)算的定義不同。因而兩個(gè)結(jié)構(gòu)具有顯著不同的特性，是兩個(gè)不同的結(jié)構(gòu)。【北京大學(xué) 1998一、1（5分）】

　　15. 在編制管理通訊錄的程序時(shí), 什么樣的數(shù)據(jù)結(jié)構(gòu)合適? 為什么?【 長沙鐵道學(xué)院1998四、3(6分)】

　　16. 試舉一例，說明對(duì)相同的邏輯結(jié)構(gòu),同一種運(yùn)算在不同的存儲(chǔ)方式下實(shí)現(xiàn)，其運(yùn)算效率不同?！?a target="_blank">北京理工大學(xué) 2000 三、1（4.5分）】

　　17. 有實(shí)現(xiàn)同一功能的兩個(gè)算法A1和A2，其中A1的時(shí)間復(fù)雜度為Tl=O(2n)，A2的時(shí)間復(fù)雜度為T2=O(n2)，僅就時(shí)間復(fù)雜度而言，請(qǐng)具體分析這兩個(gè)算法哪一個(gè)好。【北京航空航天大學(xué) 2000 二（10分）】

???　18．設(shè)計(jì)一數(shù)據(jù)結(jié)構(gòu)，用來表示某一銀行儲(chǔ)戶的基本信息： 賬號(hào)、姓名、開戶年月日、儲(chǔ)蓄類型、存入累加數(shù)、利息、帳面總數(shù)?！?a target="_blank">浙江大學(xué) 1994 一 、3（5分）】

　　19. 寫出下面算法中帶標(biāo)號(hào)語句的頻度。【北京郵電大學(xué) 1997二（10分）】

　　TYPE? ar=ARRAY[1..n] OF datatype;
　　PROCEDURE??? perm? ( a: ar; k, n: integer);
　　VAR?? x: datatype;???? i:integer;
　　BEGIN
　?。?）IF k=n
　　THEN BEGIN
　　（2）FOR? i:=1? TO? n DO
　?。?）write (a[i]);
　　writeln;
　　END
　　ELSE BEGIN
　　（4） FOR?? i:=k? TO? n? DO
　?。?）a[i]:=a[i]+i*i;
　?。?） perm (a, k+1, n);
　　END;
　　END;

　　設(shè)k的初值等于1。

　　20. 分析下面程序段中循環(huán)語句的執(zhí)行次數(shù)?！颈本┼]電大學(xué) 1998 四、1（5分）】

　　i:=0;s:=0;n:=100;
　　REPEAT
　　i:=i+1;
　　s:=s+10*i;
　　UNTIL? NOT((i<n) AND (s<n));

　　21．下列算法對(duì)一n位二進(jìn)制數(shù)加1，假如無溢出，該算法的最壞時(shí)間復(fù)雜性是什么？并分析它的平均時(shí)間復(fù)雜性?！?a target="_blank">東南大學(xué)1998 三 (8分)? 1994 二（15分）】

　　TYPE? num=ARRAY [1..n] of [0..1]；
　　PROCEDURE? Inc （VAR a：num）；
　　VAR? i：integer；
　　BEGIN? i：=n；
　　WHILE? A[i]=1? DO
　　BEGIN? A[i]：=0；? i：=i-1；END；
　　END；
　　A[i]：=1；
　　END Inc；

　　22. 閱讀下列算法，指出算法A的功能和時(shí)間復(fù)雜性【東南大學(xué) 1999 二（10分）】

　PROCEDURE? A (h,g:pointer);
　　(h,g分別為單循環(huán)鏈表（single linked? circular list）中兩個(gè)結(jié)點(diǎn)指針)
　　PROCEDURE? B(s,q:pointer)；
　　VAR p:pointer;
　　BEGIN
　　p:=s;
　　WHILE p^.next<>q DO p:=p^.next;
　　p^.next:=s;
　　END;(of B)
　　BEGIN
　　B(h,g);? B(g,h);
　　END;（of A）

　　23. 調(diào)用下列C函數(shù)f(n)或PASACAL函數(shù)f(n)?? 回答下列問題 :【華中理工大學(xué) 2000 六（10分）】

　?。?） 試指出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; i<n+1;i++)
　　{for(j=n;j>i-1; j--)
　　for(k=1;k<j+1;k++ )
　　sum++;
　　printf("sum=%d\n",sum)；
　　}
　　return (sum);
　　}

　　24．設(shè)n是偶數(shù)，試計(jì)算運(yùn)行下列程序段后m的值并給出該程序段的時(shí)間復(fù)雜度。【南京郵電大學(xué) 2000 一、1】

　　m:=0;
　　FOR? i:=1? TO? n? DO
　　FOR? j:=2*i? TO? n? DO
　　m:=m+1;

???　25．有下列運(yùn)行時(shí)間函數(shù)：【吉林工業(yè)大學(xué) 1999? 二（12分）】

　?。?）T1 (n)=1000;??? （2）T2(n)=n2+1000n;???? （3）T3(n)=3n3+100n2+n+1;

　　分別寫出相應(yīng)的大O表示的運(yùn)算時(shí)間。

　　26. 試給出下面兩個(gè)算法的運(yùn)算時(shí)間?！局锌圃鹤詣?dòng)化研究所 1995 二、2 （6分）】

　?。?）? for? i←1?? to?? n?? do
　　x ← x+1
　　END

　?。?）? for i← 1?? to? n? do
　　for? j←1? to? n? do
　　x← x+1
　　end
　　end

　　27. 斐波那契數(shù)列Fn定義如下【清華大學(xué) 2000 二（12分）】

　　F0=0，? F1=1， Fn=Fn-1+Fn-2,?? n=2,3...

　　請(qǐng)就此斐波那契數(shù)列，回答下列問題。

　　(1)? (7分) 在遞歸計(jì)算Fn的時(shí)候，需要對(duì)較小的Fn-1，F(xiàn)n-2，…, F1, F0精確計(jì)算多少次?

　　(2)? (5分) 如果用大O表示法，試給出遞歸計(jì)算Fn時(shí)遞歸函數(shù)的時(shí)間復(fù)雜度錄多少?

　　28．將下列函數(shù)，按它們?cè)趎→∝時(shí)的無窮大階數(shù)，從小到大排序。【中科院計(jì)算所 1995 】

　　n, n-n3+7n5, nlogn, 2n/2, n3, logn, n1/2+logn, (3/2)n,,n!, n2+logn