數(shù)據(jù)結(jié)構(gòu)練習(xí)-第一章-緒論

數(shù)據(jù)結(jié)構(gòu)練習(xí)第一章緒論一、選擇題1.以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？()A.隊列B.棧C.線性表D.二叉樹2．設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，那么數(shù)據(jù)結(jié)構(gòu)A是〔〕。A.線性結(jié)構(gòu) B.樹型結(jié)構(gòu) C.物理結(jié)構(gòu) D.圖型結(jié)構(gòu)3．下面程序的時間復(fù)雜為〔〕for〔i=1，s=0；i<=n；i++〕{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}A.O(n) B.O(n2) C.O(n3) D.O(n4)4．?dāng)?shù)據(jù)的最小單位是〔〕。A.數(shù)據(jù)項 B.數(shù)據(jù)類型 C.數(shù)據(jù)元素 D.數(shù)據(jù)變量5．程序段s=i=0；do{i=i+1；s=s+i；}while(i<=n)；的時間復(fù)雜度為〔〕。A.O(n) B.O(nlog2n) C.O(n2) D.O(n3/2)6．以下程序段的時間復(fù)雜度為〔〕。for(i=0；i<m；i++)for(j=0；j<t；j++)c[i][j]=0；for(i=0；i<m；i++)for(j=0；j<t；j++)for(k=0；k<n；k++)c[i][j]=c[i][j]+a[i][k]*b[k][j]；A.O(m*n*t) B.O(m+n+t) C.O(m+n*t) D.O(m*t+n)7．以下程序段的時間復(fù)雜度為〔〕。i=0，s=0；while(s<n){s=s+i；i++；}A.O(n1/2) B.O(n1/3) C.O(n) D.O(n2)8．某程序的時間復(fù)雜度為〔3n+nlog2n+n2+8〕,其數(shù)量級表示為〔〕。A．O〔n〕B．O〔nlog2n〕C．O〔n2〕D．O〔log2n〕9．線性表是一個具有n個〔〕的有限序列。A．表元素B．字符C．?dāng)?shù)據(jù)元素D．?dāng)?shù)據(jù)項10．從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為〔〕A.動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C.線性結(jié)構(gòu)、非線性結(jié)構(gòu) D.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)11．關(guān)于算法的描述，不正確的選項是〔〕A.算法最終必須由計算機(jī)程序?qū)崿F(xiàn)B.所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界C.健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)D.算法的優(yōu)劣與算法描述語言無關(guān)12．在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的根本單位是()A.數(shù)據(jù)項B.數(shù)據(jù)元素 C.數(shù)據(jù)對象 D.數(shù)據(jù)文件13．k=1;for〔i=0；i<n；i++〕for〔j=0；j<n；j++〕A［i］［j］=k++；上述程序段的時間復(fù)雜度為()A.O〔n2〕B.O〔n〕 C.O〔2n〕 D.O〔1〕14．for〔i=0；i<m；i++〕for〔j=0；j<n；j++〕A［i］［j］=i*j；上面算法的時間復(fù)雜度為()A.O(m2) B.O(n2)C.O(m×n) D.O(m+n〕15．從邏輯關(guān)系來看，數(shù)據(jù)元素的直接前驅(qū)為0個或1個的數(shù)據(jù)結(jié)構(gòu)只能是〔〕A．線性結(jié)構(gòu) B.樹形結(jié)構(gòu)C.線性結(jié)構(gòu)和樹型結(jié)構(gòu) D.線性結(jié)構(gòu)和圖狀結(jié)構(gòu)16．以下程序的時間復(fù)雜度為〔〕i=0；s=0；while〔s<n〕{i++；s=s+i；}A.O〔〕B.O〔〕C.O〔n〕 D.O〔n2〕17．?dāng)?shù)據(jù)結(jié)構(gòu)中所定義的數(shù)據(jù)元素，是用于表示數(shù)據(jù)的〔〕A.最小單位B.最大單位C.根本單位 D.不可分割的單位18．?dāng)?shù)據(jù)的四種根本存儲結(jié)構(gòu)是指〔〕A.順序存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)、直接存儲結(jié)構(gòu)、倒排存儲結(jié)構(gòu)B．順序存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、散列存儲結(jié)構(gòu)C．順序存儲結(jié)構(gòu)、非順序存儲結(jié)構(gòu)、指針存儲結(jié)構(gòu)、樹型存儲結(jié)構(gòu)D.順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、樹型存儲結(jié)構(gòu)、圖型存儲結(jié)構(gòu)19．以下四種根本的邏輯結(jié)構(gòu)中，結(jié)構(gòu)結(jié)點間不存在任何邏輯聯(lián)系的是〔〕A.集合B.線性結(jié)構(gòu)C.樹形結(jié)構(gòu) D.圖形結(jié)構(gòu)20．以下說法正確的選項是〔〕A．?dāng)?shù)據(jù)是數(shù)據(jù)元素的根本單位B．?dāng)?shù)據(jù)元素是數(shù)據(jù)項中不可分割的最小標(biāo)識單位C．?dāng)?shù)據(jù)可由假設(shè)干個數(shù)據(jù)元素構(gòu)成D．?dāng)?shù)據(jù)項可由假設(shè)干個數(shù)據(jù)元素構(gòu)成21．?dāng)?shù)據(jù)結(jié)構(gòu)的根本任務(wù)是〔〕A．邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的設(shè)計 B．?dāng)?shù)據(jù)結(jié)構(gòu)的運算實現(xiàn)C．?dāng)?shù)據(jù)結(jié)構(gòu)的評價與選擇 D．?dāng)?shù)據(jù)結(jié)構(gòu)的設(shè)計與實現(xiàn)22．一個數(shù)組元素a[i]與〔〕的表示等價。A.*(a+i)B.a+iC.*a+iD.&a+i23．對于兩個函數(shù)，假設(shè)函數(shù)名相同，但只是〔〕不同那么不是重載函數(shù)。A.參數(shù)類型B.參數(shù)個數(shù)C.函數(shù)類型24．假設(shè)需要利用形參直接訪問實參，那么應(yīng)把形參變量說明為〔〕參數(shù)A.指針B.引用C.值25．下面程序段的時間復(fù)雜度為〔〕。for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)26．執(zhí)行下面程序段時，執(zhí)行S語句的次數(shù)為〔〕。for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)S;A.n2B.n2/2C.n(n+1)D.n(n+1)/227．下面算法的時間復(fù)雜度為〔〕。intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}A.O(1)B.O(n)C.O(n2)D.O(n!)28．組成數(shù)據(jù)的根本單位是〔〕A.數(shù)據(jù)項 B.數(shù)據(jù)類型C．?dāng)?shù)據(jù)元素D．?dāng)?shù)據(jù)變量29．如某數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)元素的集合為S={A,B,C,D,E,F,G}，數(shù)據(jù)元素間的關(guān)系為R={<A,D>,<A,G>,<D,B>,<D,C>,<G,E>,<G,F>}，那么該數(shù)據(jù)結(jié)構(gòu)是一種〔〕。A．線性結(jié)構(gòu)B．樹結(jié)構(gòu)C．鏈表結(jié)構(gòu)D．隊列結(jié)構(gòu)30．下面程序段的時間復(fù)雜度為〔〕。for(i=1;i<=n;i++)for(j=i;j<=n;j++)s++;A．O(1) B．O(n)C．O(n)D．O(n)31．算法分析的目的是〔

〕A.找出數(shù)據(jù)結(jié)構(gòu)的合理性

B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改良

D.分析算法的易懂性和文檔特點32．算法的計算量的大小稱為計算的〔〕。A．效率B.復(fù)雜性C.現(xiàn)實性D.難度33．多項選擇：一個算法具有〔〕等特點。A．可行性B.至少有一個輸入量C.確定性D.健壯性34．下面說法錯誤的選項是〔〕(1)算法原地工作的含義是指不需要任何額外的輔助空間〔2〕在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時間上總是優(yōu)于復(fù)雜度O(2n)的算法〔3〕所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界〔4〕同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低A．(1)B.(1),(2)C.(1),(4)D.(3)35．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以將之分為()。A．動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)D.線性結(jié)構(gòu)和非線性結(jié)構(gòu)36．以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)〔〕。A．廣義表B.二叉樹C.稀疏矩陣D.串37．?dāng)?shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系被稱為()。A．?dāng)?shù)據(jù)的存儲結(jié)構(gòu)B.數(shù)據(jù)的根本操作C.程序的算法D.數(shù)據(jù)的邏輯結(jié)構(gòu)38．在下面的程序段中，對x的賦值語句的頻度為〔〕FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)39．以下哪個數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類型〔〕A．棧B．廣義表C．有向圖D．字符串40．以下數(shù)據(jù)中，〔〕是非線性數(shù)據(jù)結(jié)構(gòu)。A．棧B.隊列C.完全二叉樹D.堆41．以下屬于邏輯結(jié)構(gòu)的是〔〕。A．順序表B.哈希表C.有序表D.單鏈表42．計算算法的時間復(fù)雜度是屬于一種()。A.事前統(tǒng)計的方法B.事前分析估算的方法C.事后統(tǒng)計的方法D.事后分析估算的方法43．可以用()定義一個完整的數(shù)據(jù)結(jié)構(gòu):A.數(shù)據(jù)元素B.數(shù)據(jù)對象C.數(shù)據(jù)關(guān)系D.抽象數(shù)據(jù)類型44．多項選擇：數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容涉及()。A.數(shù)據(jù)如何組織B.數(shù)據(jù)如何存儲C.數(shù)據(jù)的運算如何實現(xiàn)D.算法用什么語言來描述45．算法分析的目的是〔〕。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改良D.分析算法的易懂性和文檔性46．多項選擇：設(shè)計一個“好”的算法應(yīng)考慮到達(dá)的目標(biāo)有〔〕。A.是可行的B.是健壯的C.無二義性D.可讀性好47．計算機(jī)中的算法指的是解決某一個問題的有限運算序列，它必須具備輸入、輸出、〔B〕等5個特性。A.可執(zhí)行性、可移植性和可擴(kuò)充性B.可執(zhí)行性、有窮性和確定性C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和確定性48．具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是〔D〕A.圖B.樹C.廣義表D.棧49．算法分析的目的是〔C〕A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改良D.分析算法的易懂性和文檔特點二、填空題1．通常從四個方面評價算法的質(zhì)量：_________、_________、_________和_________。正確性易讀性強(qiáng)壯性高效率2．一個算法的時間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級表示為________。O(n)3．?dāng)?shù)據(jù)的物理結(jié)構(gòu)主要包括_____________和______________兩種情況。順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)4．?dāng)?shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種根本類型：___________、__________和___________。線性結(jié)構(gòu)，樹型結(jié)構(gòu)，圖型結(jié)構(gòu)5．for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的時間復(fù)雜度為_________。O(n)6．?dāng)?shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)元素之間抽象化的相互關(guān)系和這種關(guān)系在計算機(jī)中的存儲結(jié)構(gòu)表示，根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有以下四類根本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、和。7．評價算法的標(biāo)準(zhǔn)很多，通常是以執(zhí)行算法所需要的和所占用的來判別一個算法的優(yōu)劣。8.數(shù)據(jù)的存儲結(jié)構(gòu)被分為____________、___________、____________和____________四種。順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)9．一個算法應(yīng)具備的5個特性為、、、、。有窮性、確定性、可行性、輸入、輸出10．在任何問題中，數(shù)據(jù)元素都不是孤立的，它們之間總存在某種關(guān)系，通常稱這種關(guān)系為________。邏輯關(guān)系11．存儲結(jié)點通常有四種根本存儲方式，即順序存儲方式、索引存儲方式、_______和散列存儲方式。鏈?zhǔn)酱鎯?2．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)通常包括集合、線性結(jié)構(gòu)、____________和圖狀結(jié)構(gòu)。樹結(jié)構(gòu)13．如果操作不改變原邏輯結(jié)構(gòu)的“值”，而只是從中提取某些信息作為運算結(jié)果，那么稱該類運算為__________型運算。引用14．在數(shù)據(jù)結(jié)構(gòu)中，各個結(jié)點按邏輯關(guān)系互相纏繞，任意兩個結(jié)點可以鄰接的結(jié)構(gòu)稱為_______。圖結(jié)構(gòu)15．每個存儲結(jié)點只含一個數(shù)據(jù)元素，所有存儲結(jié)點連續(xù)存放。此外增設(shè)一個索引表，索引表中的索引指示各存儲結(jié)點的存儲位置或位置區(qū)間端點。按這種方式組織起來的存儲結(jié)構(gòu)稱為_______。索引結(jié)構(gòu)16．通常從正確性、易讀性、________和高效率等4個方面評價算法〔包括程序〕的質(zhì)量。健壯17．順序表的存儲密度為___100%_____，而鏈表的存儲密度為__<100%______。18．表示邏輯關(guān)系的存儲結(jié)構(gòu)可以有四種方式，即順序存儲方式、鏈?zhǔn)酱鎯Ψ绞健______________和散列存儲方式。索引存儲方式19．?dāng)?shù)據(jù)表示和__________是程序設(shè)計者所要考慮的兩項根本任務(wù)。算法設(shè)計20．在線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點之間分別存在著________、________和________的聯(lián)系。1:1、1:N、M:N21．一種抽象數(shù)據(jù)類型包括__________和__________兩個局部。數(shù)據(jù)定義、操作聲明22．當(dāng)一個形參類型的長度較大時，應(yīng)最好說明為_________，以節(jié)省參數(shù)值的傳輸時間和存儲參數(shù)的空間。引用形參(或指針形參)23．當(dāng)需要用一個形參訪問對應(yīng)的實參時，那么該形參應(yīng)說明為__________。引用類型(或指針類型)24．在函數(shù)中對引用形參的修改就是對相應(yīng)__________的修改，對__________形參的修改只局限在該函數(shù)的內(nèi)部，不會反映到對應(yīng)的實參上。實參、值25．當(dāng)需要進(jìn)行標(biāo)準(zhǔn)I/O操作時，那么應(yīng)在程序文件中包含________________頭文件，當(dāng)需要進(jìn)行文件I/O操作時，那么應(yīng)在程序文件中包含________________頭文件。iostream.h、fstream.h26．在包含有________________頭文件的程序文件中，使用________________能夠產(chǎn)生出0～20之間的一個隨機(jī)整數(shù)。stdlib.h、rand()%2127．一個數(shù)組a所占有的存儲空間的大小即數(shù)組長度為____________，下標(biāo)為i的元素a[i]的存儲地址為__________，或者為______________________________。sizeof(a)、a+i*sizeof(a[0])、a+i28．函數(shù)重載要求____________、____________或____________有所不同。參數(shù)類型、數(shù)量、次序29．對于雙目操作符，其重載函數(shù)帶有__________個參數(shù)，其中至少有一個為____________的類型。2、用戶自定義30．假設(shè)對象ra和rb中至少有一個是屬于用戶定義的類型，那么執(zhí)行ra==rb時，需要調(diào)用__________重載函數(shù)，該函數(shù)的第一個參數(shù)應(yīng)與__________的類型相同，第二個參數(shù)應(yīng)與__________的類型相同。==、ra、rb31．從一維數(shù)組a[n]中順序查找出一個最大值元素的時間復(fù)雜度為________，輸出一個二維數(shù)組b[m][n]中所有元素值的時間復(fù)雜度為________。O(n)、O(m*n)32．在下面程序段中，s=s+p語句的執(zhí)行次數(shù)為________，p*=j語句的執(zhí)行次數(shù)為________，該程序段的時間復(fù)雜度為________。inti=0,s=0;while(++i<=n){intp=1;for(intj=1;j<=i;j++)p*=j;s=s+p;}n、n(n+1)/2、O(n2)33．一個算法的時間復(fù)雜度為(3n2+2nlog2n+4n-7)/(5n)，其數(shù)量級表示為________。O(n)34．?dāng)?shù)據(jù)結(jié)構(gòu)講述的三大關(guān)系是、、。一對一的線性關(guān)系一對多的樹關(guān)系多對多的圖關(guān)系35．某算法的執(zhí)行時間為n+n2,n代表問題規(guī)模，那么該算法的時間復(fù)雜度是。．O(n2);36．?dāng)?shù)據(jù)結(jié)構(gòu)有線性結(jié)構(gòu)、樹結(jié)構(gòu)、、等幾種邏輯結(jié)構(gòu)。圖結(jié)構(gòu);集合;37.數(shù)據(jù)結(jié)構(gòu)中，非線性邏輯結(jié)構(gòu)有、、。集合、樹、圖38.數(shù)據(jù)的邏輯結(jié)構(gòu)是指。數(shù)據(jù)的組織形式，即數(shù)據(jù)元素之間邏輯關(guān)系的總體。而邏輯關(guān)系是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式或稱“鄰接關(guān)系”。39.一個數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中稱為存儲結(jié)構(gòu)。表示〔又稱映像〕。40.數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是算法的時間復(fù)雜度和空間復(fù)雜度。41.一個算法具有5個特性:〔1〕、〔2〕、〔3〕，有零個或多個輸入、有一個或多個輸出?！?〕有窮性〔2〕確定性〔3〕可行性。42.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是()。i.i:=1;b)WHILEi<nBEGINFORj:=1TOnDOx:=x+1;i:=i*2END；c)nlog2n43.下面程序段的時間復(fù)雜度為________。(n>1)i.sum=1；ii.for(i=0;sum<n;i++)sum+=1;O(n)44.設(shè)m.n均為自然數(shù)，m可表示為一些不超過n的自然數(shù)之和，f(m,n)為這種表示方式的數(shù)目。例f(5,3)=5，有5種表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。a)①以下是該函數(shù)的程序段，請將未完成的局部填入，使之完整1.intf(m,n)a)intm,n;2.{if(m==1)return(1);if(n==1){return(2);}if(m<n){returnf(m,m);}if(m==n){return1+(3);}returnf(m,n-1)+f(m-n,(4));}②執(zhí)行程序，f(6,4)=。①(1)1(2)1(3)f(m,n-1)(4)n②945.設(shè)有兩個算法在同一機(jī)器上運行，其執(zhí)行時間分別為100n2和2n，要使前者快于后者，n至少為〔〕。(當(dāng)n<=14時,100n2>2n,而n>=15時100n2<2n)46.作為一個算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目，或與此數(shù)目有關(guān)的其他參數(shù)，稱為________。問題規(guī)模_三、判斷題1．()如果某數(shù)據(jù)結(jié)構(gòu)的每一個元素最多只有一個直接前驅(qū)，那么其必為線性表?！?．()一個程序的時間復(fù)雜度是指該程序運行時間與問題規(guī)模的對應(yīng)關(guān)系√3．〔〕數(shù)據(jù)元素是數(shù)據(jù)的最小單元。×4．〔〕數(shù)據(jù)的根本單位是數(shù)據(jù)項。╳5．〔〕數(shù)組元素之間的關(guān)系，既不是線性的，也不是樹形的。√6．〔〕算法和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的?！?．〔〕算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計算機(jī)有關(guān)?！了摹⒑喆痤}1．簡述以下概念數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)類型，數(shù)據(jù)結(jié)構(gòu)，邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)，算法?！窘獯稹繑?shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符，以及所有能輸入到計算機(jī)中并被計算機(jī)程序識別和處理的符號的集合。數(shù)據(jù)元素是數(shù)據(jù)的根本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點、頂點、記錄等。數(shù)據(jù)類型是對數(shù)據(jù)的取值范圍、數(shù)據(jù)元素之間的結(jié)構(gòu)以及允許施加操作的一種總體描述。每一種計算機(jī)程序設(shè)計語言都定義有自己的數(shù)據(jù)類型?！皵?shù)據(jù)結(jié)構(gòu)”這一術(shù)語有兩種含義，一是作為一門課程的名稱；二是作為一個科學(xué)的概念。作為科學(xué)概念，目前尚無公認(rèn)定義，一般認(rèn)為，討論數(shù)據(jù)結(jié)構(gòu)要包括三個方面，一是數(shù)據(jù)的邏輯結(jié)構(gòu)，二是數(shù)據(jù)的存儲結(jié)構(gòu)，三是對數(shù)據(jù)進(jìn)行的操作〔運算〕。而數(shù)據(jù)類型是值的集合和操作的集合，可以看作是已實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)，后者是前者的一種簡化情況。數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系〔即數(shù)據(jù)元素之間的關(guān)聯(lián)方式或“鄰接關(guān)系”〕，數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示，包括數(shù)據(jù)元素的表示及其關(guān)系的表示。數(shù)據(jù)的運算是對數(shù)據(jù)定義的一組操作，運算是定義在邏輯結(jié)構(gòu)上的，和存儲結(jié)構(gòu)無關(guān)，而運算的實現(xiàn)那么依賴于存儲結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示稱為物理結(jié)構(gòu)，又稱存儲結(jié)構(gòu)。是邏輯結(jié)構(gòu)在存儲器中的映像，包括數(shù)據(jù)元素的表示和關(guān)系的表示。邏輯結(jié)構(gòu)與計算機(jī)無關(guān)。算法是對特定問題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個或多個操作。一個算法應(yīng)該具有以下特性：有窮性、確定性、可行性、輸入和輸出。2．

數(shù)據(jù)的邏輯結(jié)構(gòu)分哪幾種，為什么說邏輯結(jié)構(gòu)是數(shù)據(jù)組織的主要方面？【解答】數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)?！惨部梢苑譃榧?、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形即網(wǎng)狀結(jié)構(gòu)〕。邏輯結(jié)構(gòu)是數(shù)據(jù)組織的某種“本質(zhì)性”的東西：〔1〕邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容無關(guān)?！?〕邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對位置無關(guān)?！?〕邏輯結(jié)構(gòu)與所含數(shù)據(jù)元素的個數(shù)無關(guān)。3．試舉一個數(shù)據(jù)結(jié)構(gòu)的例子，表達(dá)其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算三方面的內(nèi)容?！窘獯稹繉W(xué)生成績表，邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，可以順序存儲〔也可以鏈?zhǔn)酱鎯Α?，運算可以有插入、刪除、查詢，等等。4．簡述算法的五個特性，對算法設(shè)計的要求?！窘獯稹克惴ǖ奈鍌€特性是：有窮性、確定性、可行性、零至多個輸入和一至多個輸出。對算法設(shè)計的要求：正確性，易讀性，健壯性，和高的時空間效率〔運算速度快，存儲空間小〕。5．設(shè)n是正整數(shù)，求以下程序段中帶@記號的語句的執(zhí)行次數(shù)。(1)i=1;k=0;

(2)i=1;j=0;

while(i<n)

while(i+j<=n)

{k=k+50*i;i++;

@

{if(i>j)j++;

@

}

elsei++;

}

@

(3)x=y=0;

(4)x=91;y=100;

for(i=0;i<n;i++)

@

while(y>0)

for(j=0;j<n;j++)

@

if(x>100)

{x++;

@

{x=x-10;y--;

@

for(k=0;k<n;k++)@

}

y++;

@

elsex++;

@

}

【解答】(1)n-1

(2)i=

n/2(上取整〕

，j=n/2〔下取整〕

(3)n+1,n(n+1),n2,(n+1)n2,n3

(4)100,10006．?dāng)?shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型有什么區(qū)別？【解答】“數(shù)據(jù)結(jié)構(gòu)”這一術(shù)語有兩種含義，一是作為一門課程的名稱；二是作為一個科學(xué)的概念。作為科學(xué)概念，目前尚無公認(rèn)定義，一般認(rèn)為，討論數(shù)據(jù)結(jié)構(gòu)要包括三個方面，一是數(shù)據(jù)的邏輯結(jié)構(gòu)，二是數(shù)據(jù)的存儲結(jié)構(gòu)，三是對數(shù)據(jù)進(jìn)行的操作〔運算〕。而數(shù)據(jù)類型是值的集合和操作的集合，可以看作是已實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)，后者是前者的一種簡化情況。7．下面程序段的時間復(fù)雜度是什么？for(i=0;i<n;i++)for(j=0;,j<m;j++)a[i][j]=0;【解答】O(m*n)8．運算是數(shù)據(jù)結(jié)構(gòu)的一個重要方面。試舉一例，說明兩個數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲方式完全相同，只是對于運算的定義不同。因而兩個結(jié)構(gòu)具有顯著不同的特性，是兩個不同的結(jié)構(gòu)?！窘獯稹織：完犃械倪壿嫿Y(jié)構(gòu)相同，其存儲表示也可相同〔順序存儲和鏈?zhǔn)酱鎯Α?，但由于其運算集合不同而成為不同的數(shù)據(jù)結(jié)構(gòu)。9．試舉一例，說明對相同的邏輯結(jié)構(gòu),同一種運算在不同的存儲方式下實現(xiàn)，其運算效率不同?！窘獯稹烤€性表中的插入、刪除操作，在順序存儲方式下平均移動近一半的元素，時間復(fù)雜度為O〔n〕；而在鏈?zhǔn)酱鎯Ψ绞较?，插入和刪除時間復(fù)雜度都是O〔1〕。10．有實現(xiàn)同一功能的兩個算法A1和A2，其中A1的時間復(fù)雜度為Tl=O(2n)，A2的時間復(fù)雜度為T2=O(n2)，僅就時間復(fù)雜度而言，請具體分析這兩個算法哪一個好?！窘獯稹繉λ惴ˋ1和A2的時間復(fù)雜度T1和T2取對數(shù)，得nlog2和2logn。顯然，當(dāng)n<4時，算法A1好于A2；當(dāng)n=4時，兩個算法時間復(fù)雜度相同；當(dāng)n>4時，算法A2好于A1。11．設(shè)n是偶數(shù)，且有程序段：Fori:=1tonDoif2*i<=nThenForj:=2*itonDoy:=y+i*j;那么語句“y:=y+i*j”的執(zhí)行次數(shù)多少？要求列出計算公式?！窘獯稹縩2/4。語句“y:=y+i*j”在“i=1”時執(zhí)行n-1次，在“i=2”時執(zhí)行n-3次，……，最后當(dāng)“i=n/2”時執(zhí)行1次，當(dāng)“i>n/2(n-1)+(n-3)+…+3+1=(n/2)2=n2/4第一層for循環(huán)判斷n+1次，往下執(zhí)行n次，第二層for執(zhí)行次數(shù)為(n+(n-1)+(n-2)+…+1)，第三層循環(huán)體受第一層循環(huán)和第二層循環(huán)的控制，其執(zhí)行次數(shù)如下表：i=123…nj=nnnn…nj=n-1n-1n-1n-1……………j=333j=222j=1112．調(diào)用以下C函數(shù)f(n)(編者注：略去PASACAL函數(shù)f(n))答復(fù)以下問題:試指出f(n)值的大小，并寫出f(n)值的推導(dǎo)過程;假定n=5，試指出f(5)值的大小和執(zhí)行f(5)時的輸出結(jié)果。C函數(shù)：intf(intn){inti,j，k,sum=0;for(i=l;i<n+1;i++){for(j=n;j>i-1;j--)1.for(k=1;k<j+1;k++)2.sum++;3.printf("sum=%d\n",sum)；}return(sum);}【解答】執(zhí)行次數(shù)為(1+2+…+n)+(2+3+…+n)+…+n=n*n(n+1)/2-n(n2-1)/6。在n=5時，f(5)=55，執(zhí)行過程中，輸出結(jié)果為：sum=15sum=29sum=41sum=50sum=5513．設(shè)n是偶數(shù)，試計算運行以下程序段后m的值并給出該程序段的時間復(fù)雜度。m:=0;FORi:=1TOnDOFORj:=2*iTOnDOm:=m+1;【解答】O(n2),m的值等于賦值語句m:=m+1的運行次數(shù)，其計算式為五、應(yīng)用題第一章緒論1．在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A[0].next，試寫出該線性表。A01234567data605078903440next3572041【解答】線性表為：〔78，50，40，60，34，90〕2.設(shè)指針變量p指向雙向鏈表中結(jié)點A，指針變量q指向被插入結(jié)點B，要求給出在結(jié)點A的后面插入結(jié)點B的操作序列〔設(shè)雙向鏈表中結(jié)點的兩個指針域分別為llink和rlink〕?！窘獯稹縬->llink=p;q->rlink=p->rlink;p->rlink->ll