李云清揭安全系統(tǒng)大數(shù)據(jù)結(jié)構(gòu)問題詳解

《李云清揭安全系統(tǒng)大數(shù)據(jù)結(jié)構(gòu)問題詳解》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、1數(shù)據(jù)結(jié)構(gòu)（C語言版）（第2版）習(xí)題解析揭安全李云清楊慶紅江西師范大學(xué)計算機信息工程學(xué)院聯(lián)系方式：janquan@163.com（習(xí)題答案僅供參考）2第1章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)？【答】：數(shù)據(jù)結(jié)構(gòu)是指按一定的邏輯結(jié)構(gòu)組成的一批數(shù)據(jù)，使用某種存儲結(jié)構(gòu)將這批數(shù)據(jù)存儲于計算機中，并在這些數(shù)據(jù)上定義了一個運算集合。1.2數(shù)據(jù)結(jié)構(gòu)涉及哪幾個方面？【答】：數(shù)據(jù)結(jié)構(gòu)涉及三個方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算集合。1.3兩個數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)都相同，但是它們的運算集合中有一個運算的定義不一樣，它們是否可以認作是同一個數(shù)據(jù)結(jié)構(gòu)？為什么？【答】：不能，運算集合是數(shù)據(jù)結(jié)

2、構(gòu)的重要組成部分，不同的運算集合所確定的數(shù)據(jù)結(jié)構(gòu)是不一樣的，例如，棧與隊列它們的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)可以相同，但由于它們的運算集合不一樣，所以它們是兩種不同的數(shù)據(jù)結(jié)構(gòu)。1.4線性結(jié)構(gòu)的特點是什么？非線性結(jié)構(gòu)的特點是什么？【答】：線性結(jié)構(gòu)元素之間的關(guān)系是一對一的，在線性結(jié)構(gòu)中只有一個開始結(jié)點和一個終端結(jié)點，其他的每一個結(jié)點有且僅有一個前驅(qū)和一個后繼結(jié)點。而非線性結(jié)構(gòu)則沒有這個特點，元素之間的關(guān)系可以是一對多的或多對多的。1.5數(shù)據(jù)結(jié)構(gòu)的存儲方式有哪幾種？【答】：數(shù)據(jù)結(jié)構(gòu)的存儲方式有順序存儲、鏈式存儲、散列存儲和索引存儲等四種方式。1.6算法有哪些特點？它和程序的主要區(qū)別是什么？【答】：

3、算法具有（1）有窮性（2）確定性（3）0個或多個輸入（4）1個或多個輸出（5）可行性等特征。程序是算法的一種描述方式，通過程序可以在計算機上實現(xiàn)算法。1.7抽象數(shù)據(jù)類型的是什么？它有什么特點？【答】：抽象數(shù)據(jù)類型是數(shù)據(jù)類型的進一步抽象，是大家熟知的基本數(shù)據(jù)類型的延伸和發(fā)展。抽象數(shù)據(jù)類型是與表示無關(guān)的數(shù)據(jù)類型，是一個數(shù)據(jù)模型及定義在該模型上的一組運算。對一個抽象數(shù)據(jù)類型進行定義時，必須給出它的名字及各運算的運算符名，即函數(shù)名，并且規(guī)定這些函數(shù)的參數(shù)性質(zhì)。一旦定義了一個抽象數(shù)據(jù)類型及具體實現(xiàn)，程序設(shè)計中就可以像使用基本數(shù)據(jù)類型那樣，十分方便地使用抽象數(shù)據(jù)類型。抽象數(shù)據(jù)類型的設(shè)計者根據(jù)這

4、些描述給出操作的具體實現(xiàn)，抽象數(shù)據(jù)類型的使用者依據(jù)這些描述使用抽象數(shù)據(jù)類型。1.8算法的時間復(fù)雜度指的是什么？如何表示？【答】：算法執(zhí)行時間的度量不是采用算法執(zhí)行的絕對時間來計算的，因為一個算法在不同的機器上執(zhí)行所花的時間不一樣，在不同時刻也會由于計算機資源占用情況的不同，使得算法在同一臺計算機上執(zhí)行的時間也不一樣，另外，算法執(zhí)行的時間還與輸入數(shù)據(jù)的狀態(tài)有關(guān)，所以對于算法的時間復(fù)雜性，采用算法執(zhí)行過程中其基本操作的執(zhí)行次數(shù)，稱為計算量來度量。算法中基本操作的執(zhí)行次數(shù)一般是與問題規(guī)模有關(guān)的，對于結(jié)點個數(shù)為n的數(shù)據(jù)處理問題，用T(n)表示算法基本操作的執(zhí)行次數(shù)。為了評價算法的執(zhí)行效率，

5、通常采用大寫O符號表示算法的時間復(fù)雜度，大寫O符號給出了函數(shù)f的一個上限。其它義如下：3定義：f(n)=O(g(n))當且僅當存在正的常數(shù)c和n0，使得對于所有的n≥n0，有f(n)≤cg(n)。上述定義表明，函數(shù)f頂多是函數(shù)g的c倍，除非n小于n0。因此對于足夠大的n(如n≥n0)，g是f的一個上限（不考慮常數(shù)因子c）。在為函數(shù)f提供一個上限函數(shù)g時，通常使用比較簡單的函數(shù)形式。比較典型的形式是含有n的單個項（帶一個常數(shù)系數(shù)）。表1-1列出了一些常用的g函數(shù)及其名稱。對于表1-1中的對數(shù)函數(shù)logn，沒有給出對數(shù)基，原因是對于任何大于1的常數(shù)a和b都有l(wèi)ogan=logbn/lo

6、gba,所以logan和logbn都有一個相對的乘法系數(shù)1/logba，其中a是一個常量。表1-1常用的漸進函數(shù)1.9算法的空間復(fù)雜度指的是什么？如何表示？【答】：算法的空間復(fù)雜度是指算法在執(zhí)行過程中占用的額外的輔助空間的個數(shù)。可以將它表示為問題規(guī)模的函數(shù)，并通過大寫O符號表示空間復(fù)雜度。1.10對于下面的程序段，分析帶下劃線的語句的執(zhí)行次數(shù)，并給出它們的時間復(fù)雜度T(n)。（1）i++;（2）for(i=0;i

7、;i<=n-1;i++){k=i;for(j=i+1;j<=n;j++)if(a[j]>a[j+1])k=j;t=a[k];a[k]=a[i];a[i]=t;}（5）for(i=0;i