李云清揭安全數(shù)據(jù)結(jié)構(gòu)答案

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

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

3、))當(dāng)且僅當(dāng)存在正的常數(shù)c和n0，使得對(duì)于所有的n≥n0，有f(n)≤cg(n)。上述定義表明，函數(shù)f頂多是函數(shù)g的c倍，除非n小于n0。因此對(duì)于足夠大的n(如n≥n0)，g是f的一個(gè)上限（不考慮常數(shù)因子c）。在為函數(shù)f提供一個(gè)上限函數(shù)g時(shí)，通常使用比較簡(jiǎn)單的函數(shù)形式。比較典型的形式是含有n的單個(gè)項(xiàng)（帶一個(gè)常數(shù)系數(shù)）。表11列出了一些常用的g函數(shù)及其名稱。對(duì)于表11中的對(duì)數(shù)函數(shù)logn，沒(méi)有給出對(duì)數(shù)基，原因是對(duì)于任何大于1的常數(shù)a和b都

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