數(shù)據(jù)結構1000題內(nèi)容

第1章緒論一、選擇題1.算法的計算量的大小稱為計算的（）。(北京郵電大學2000二、3（20/8分）)A．效率B.復雜性C.現(xiàn)實性D.難度2.算法的時間復雜度取決于（）(中科院計算所1998二、1（2分）)A．問題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.A和B3.計算機算法指的是（1），它必須具備（2）這三個特性。(1)A．計算方法B.排序方法C.解決問題的步驟序列D.調(diào)度方法(2)A．可執(zhí)行性、可移植性、可擴充性B.可執(zhí)行性、確定性、有窮性C.確定性、有窮性、穩(wěn)定性D.易讀性、穩(wěn)定性、安全性(南京理工大學1999一、1（2分）(武漢交通科技大學1996一、1（4分）)4．一個算法應該是（）。(中山大學1998二、1（2分）)A．程序B．問題求解步驟的描述C．要滿足五個基本特性D．A和C.5.下面關于算法說法錯誤的是（）(南京理工大學2000一、1（1.5分）)A．算法最終必須由計算機程序實現(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是相同的C.算法的可行性是指指令不能有二義性D.以上幾個都是錯誤的6.下面說法錯誤的是（）(南京理工大學2000一、2（1.5分）)(1）算法原地工作的含義是指不需要任何額外的輔助空間（2）在相同的規(guī)模n下，復雜度O(n)的算法在時間上總是優(yōu)于復雜度O(2n)的算法（3）所謂時間復雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界（4）同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低A．(1)B.(1),(2)C.(1),(4)D.(3)7．從邏輯上可以把數(shù)據(jù)結構分為（）兩大類。(武漢交通科技大學1996一、4（2分）)A．動態(tài)結構、靜態(tài)結構B．順序結構、鏈式結構C．線性結構、非線性結構D．初等結構、構造型結構8．以下與數(shù)據(jù)的存儲結構無關的術語是（）。(北方交通大學2000二、1（2分）)A．循環(huán)隊列B.鏈表C.哈希表D.棧9．以下數(shù)據(jù)結構中，哪一個是線性結構（）？(北方交通大學2001一、1（2分）)A．廣義表B.二叉樹C.稀疏矩陣D.串10．以下那一個術語與數(shù)據(jù)的存儲結構無關？（）(北方交通大學2001一、2（2分）)A．棧B.哈希表C.線索樹D.雙向鏈表11．在下面的程序段中，對x的賦值語句的頻度為（）(北京工商大學2001一、10（3分）)FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)12．程序段FORi:=n-1DOWNTO1DOFORj:=1TOiDOIFA[j]>A[j+1]THENA[j]與A[j+1]對換；其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（）A.O（n）B.O(nlogn)C.O(n3)D.O(n2)(南京理工大學1998一、1(2分))13．以下哪個數(shù)據(jù)結構不是多型數(shù)據(jù)類型（）(中山大學1999一、3（1分）)A．棧B．廣義表C．有向圖D．字符串14．以下數(shù)據(jù)結構中，（）是非線性數(shù)據(jù)結構(中山大學1999一、4)A．樹B．字符串C．隊D．棧15.下列數(shù)據(jù)中，（）是非線性數(shù)據(jù)結構。(北京理工大學2001六、1（2分）)A．棧B.隊列C.完全二叉樹D.堆16．連續(xù)存儲設計時，存儲單元的地址（）。(中山大學1999一、1（1分）)A．一定連續(xù)B．一定不連續(xù)C．不一定連續(xù)D．部分連續(xù)，部分不連續(xù)17．以下屬于邏輯結構的是（）。(西安電子科技大學應用2001一、1)A．順序表B.哈希表C.有序表D.單鏈表二、判斷題1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。()(北京郵電大學1998一、1（2分）)(青島大學2000一、1（1分）)(上海交通大學1998一、1)(山東師范大學2001一、1（2分）)2.記錄是數(shù)據(jù)處理的最小單位。()(上海海運學院1998一、5（1分）)3.數(shù)據(jù)的邏輯結構是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系；()(北京郵電大學2002一、1（1分）)4．算法的優(yōu)劣與算法描述語言無關，但與所用計算機有關。()(大連海事大學2001一、10（1分）)5．健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。()(大連海事大學2001一、11（1分）)6．算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言來描述，則算法實際上就是程序了。()(西安交通大學1996二、7（3分）)7．程序一定是算法。()(燕山大學1998二、2（2分）并改錯)8．數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。()(山東師范大學2001一、2（2分）)9.數(shù)據(jù)結構的抽象操作的定義與具體實現(xiàn)有關。()(華南理工大學2002一、1（1分）)10.在順序存儲結構中，有時也存儲數(shù)據(jù)結構中元素之間的關系。()(華南理工大學2002一、2（1分）)11.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。()(上海海運學院1999一、1（1分）)12.數(shù)據(jù)結構的基本操作的設置的最重要的準則是，實現(xiàn)應用程序與存儲結構的獨立。()(華南理工大學2002一、5（1分）)13.數(shù)據(jù)的邏輯結構說明數(shù)據(jù)元素之間的順序關系,它依賴于計算機的儲存結構.()(上海海運學院1998一、1（1分）)三、填空1．數(shù)據(jù)的物理結構包括的表示和的表示。(燕山大學1998一、1（2分）)2.對于給定的n個元素,可以構造出的邏輯結構有（1），（2），（3），__（4）_四種。(中科院計算所1999二、1（4分）)3．數(shù)據(jù)的邏輯結構是指。(北京郵電大學2001二、1（2分）)4．一個數(shù)據(jù)結構在計算機中稱為存儲結構。(華中理工大學2000一、1（1分）)5．抽象數(shù)據(jù)類型的定義僅取決于它的一組__（1）_，而與_（2）_無關，即不論其內(nèi)部結構如何變化，只要它的_（3）_不變，都不影響其外部使用。(山東大學2001三、3（2分）)6．數(shù)據(jù)結構中評價算法的兩個重要指標是(北京理工大學2001七、1（2分）)7.數(shù)據(jù)結構是研討數(shù)據(jù)的_（1）_和_（2）_，以及它們之間的相互關系，并對與這種結構定義相應的_（3）_，設計出相應的（4）_。(西安電子科技大學1998二、2（3分）)8．一個算法具有5個特性:（1）、（2）、（3），有零個或多個輸入、有一個或多個輸出。(華中理工大學2000一、2（5分）)(燕山大學1998一、2（5分）)9．已知如下程序段FORi:=nDOWNTO1DO{語句1}BEGINx:=x+1；{語句2}（5）a[i]:=a[i]+i*i;（6）perm(a,k+1,n);END;END;設k的初值等于1。(北京郵電大學1997二（10分）)20.分析下面程序段中循環(huán)語句的執(zhí)行次數(shù)。i:=0;s:=0;n:=100;REPEATi:=i+1;s:=s+10*i;UNTILNOT((i<n)AND(s<n));(北京郵電大學1998四、1（5分）)21．下列算法對一n位二進制數(shù)加1，假如無溢出，該算法的最壞時間復雜性是什么？并分析它的平均時間復雜性。TYPEnum=ARRAY[1..n]of[0..1]；PROCEDUREInc（VARa：num）；VARi：integer；BEGINi：=n；WHILEA[i]=1DOBEGINA[i]：=0；i：=i-1；END；END；A[i]：=1；ENDInc；(東南大學1998三(8分)1994二（15分）)22.閱讀下列算法，指出算法A的功能和時間復雜性PROCEDUREA(h,g:pointer);(h,g分別為單循環(huán)鏈表（singlelinkedcircularlist）中兩個結點指針)PROCEDUREB(s,q:pointer)；VARp:pointer;BEGINp:=s;WHILEp^.next<>qDOp:=p^.next;p^.next:=s;END;(ofB)BEGINB(h,g);B(g,h);END;（ofA）(東南大學1999二（10分）)23.調(diào)用下列C函數(shù)f(n)或PASACAL函數(shù)f(n)回答下列問題:（1）試指出f(n)值的大小，并寫出f(n)值的推導過程;（2）假定n=5，試指出f(5)值的大小和執(zhí)行f(5)時的輸出結果。C函數(shù)：intf(intn){inti,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);}(華中理工大學2000六（10分）)24．設n是偶數(shù)，試計算運行下列程序段后m的值并給出該程序段的時間復雜度。m:=0;FORi:=1TOnDOFORj:=2*iTOnDOm:=m+1;(南京郵電大學2000一、1)25．有下列運行時間函數(shù)：（1）T1(n)=1000;（2）T2(n)=n2+1000n;（3）T3(n)=3n3+100n2+n+1;分別寫出相應的大O表示的運算時間。(吉林工業(yè)大學1999二（12分）)26.試給出下面兩個算法的運算時間。（1）fori←1tondox←x+1END（2）fori←1tondoforj←1tondox←x+1endend(中科院自動化研究所1995二、2（6分）)27.斐波那契數(shù)列Fn定義如下F0=0，F(xiàn)l=1，F(xiàn)n=Fn-1+Fn-2,