李云清揭安全數(shù)據(jù)結構答案

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

2、和存儲結構都相同，但是它們的運算集合中有一個運算的定義不一樣，它們是否可以認作是同一個數(shù)據(jù)結構？為什么？【答】：不能，運算集合是數(shù)據(jù)結構的重要組成部分，不同的運算集合所確定的數(shù)據(jù)結構是不一樣的，例如，棧與隊列它們的邏輯結構與存儲結構可以相同，但由于它們的運算集合不一樣，所以它們是兩種不同的數(shù)據(jù)結構。1.4線性結構的特點是什么？非線性結構的特點是什么？的時間復雜度，大寫O符號給出了函數(shù)f的一個上限。其它義如下：3定義：f(n)=O(g(n

3、))當且僅當存在正的常數(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ù)）。表11列出了一些常用的g函數(shù)及其名稱。對于表11中的對數(shù)函數(shù)logn，沒有給出對數(shù)基，原因是對于任何大于1的常數(shù)a和b都

4、有l(wèi)ogan=logbnlogba所以logan和logbn都有一個相對的乘法系數(shù)1logba，其中a是一個常量。表11常用的漸進函數(shù)1.9算法的空間復雜度指的是什么？如何表示？【答】：算法的空間復雜度是指算法在執(zhí)行過程中占用的額外的輔助空間的個數(shù)?？梢詫⑺硎緸閱栴}規(guī)模的函數(shù)，并通過大寫O符號表示空間復雜度。1.10對于下面的程序段，分析帶下劃線的語句的執(zhí)行次數(shù)，并給出它們的時間復雜度T(n)。（1）i（2）f(i=0ini)if(a