數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題目

1、.1 緒論沈陽(yáng)理工大學(xué)應(yīng)用技術(shù)學(xué)院信息與控制學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)教研室2011-5-8數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：緒論單選題1、在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的數(shù)據(jù)叫_結(jié)構(gòu)。A存儲(chǔ)|B物理|C邏輯|D物理和存儲(chǔ)2、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成_。A動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)|B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)|C線性結(jié)構(gòu)和非線性結(jié)構(gòu)|D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)圖3、數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指_。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)|數(shù)據(jù)結(jié)構(gòu)|數(shù)據(jù)的邏輯結(jié)構(gòu)|數(shù)據(jù)元素之間的關(guān)系4、在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的_結(jié)構(gòu)。邏輯|存儲(chǔ)|邏輯和存儲(chǔ)|物理5、在以下的敘述中，正確的是_。線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)|二維

2、數(shù)組是其數(shù)據(jù)元素為線性表的線性表|棧的操作方式是先進(jìn)先出|隊(duì)列的操作方式是先進(jìn)后出6、在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮_。各結(jié)點(diǎn)的值如何|結(jié)束個(gè)數(shù)的多少|(zhì)對(duì)數(shù)據(jù)有哪些運(yùn)算|所用編程語(yǔ)言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便7、在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)_。數(shù)據(jù)的處理方法|數(shù)據(jù)元素的類型|數(shù)據(jù)元素之間的關(guān)系|數(shù)據(jù)的存儲(chǔ)方法8、下面說(shuō)法錯(cuò)誤的是_。(1)算法原地工作的含義是指不需要任何額外的輔助空間(2)在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度O(2n)的算法(3)所謂時(shí)間復(fù)雜度是指最壞情況下，估計(jì)算法執(zhí)行時(shí)間的一個(gè)上界(4)同一個(gè)算法，實(shí)現(xiàn)語(yǔ)句的級(jí)別越高，執(zhí)行

3、效率越低(1)|(1)、(2)|(1)、(4)|(3)9、通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性。這意味著_。數(shù)據(jù)元素具有同一特點(diǎn)|不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)的數(shù)據(jù)項(xiàng)的類型要一致|每個(gè)數(shù)據(jù)元素都一樣|數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等10、以下說(shuō)法正確的是_。數(shù)據(jù)元素是數(shù)據(jù)的最小單位|數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位|數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項(xiàng)的集合|一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)11、_是數(shù)據(jù)的最小單元,_是數(shù)據(jù)的基本單位.數(shù)據(jù)項(xiàng)|數(shù)據(jù)元素|信息項(xiàng)|表元素12、數(shù)據(jù)結(jié)構(gòu)是指_以及它們之間的_.(1)數(shù)據(jù)元素 (2)結(jié)構(gòu)|(1)計(jì)算方法 (2)關(guān)系|(1)邏

4、輯存儲(chǔ) (2)運(yùn)算|(1)數(shù)據(jù)映像 (2)算法13、計(jì)算機(jī)所處理的數(shù)據(jù)一般具備某種內(nèi)在的關(guān)系,這是的指_.數(shù)據(jù)和數(shù)據(jù)之間存在的某種關(guān)系|元素和元素之間存在某種關(guān)系|元素內(nèi)部具有某種結(jié)構(gòu)|數(shù)據(jù)項(xiàng)和數(shù)據(jù)項(xiàng)之間存在某種關(guān)系14、數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為_(kāi)兩類.動(dòng)態(tài)結(jié)構(gòu)和表態(tài)結(jié)構(gòu)|緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)|線性結(jié)構(gòu)和非線性結(jié)構(gòu)|內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)15、數(shù)據(jù)的邏輯結(jié)構(gòu)是指_關(guān)系的整體.數(shù)據(jù)元素之間邏輯|數(shù)據(jù)項(xiàng)之間邏輯|數(shù)據(jù)類型之間|存儲(chǔ)結(jié)構(gòu)之間16、在存儲(chǔ)數(shù)據(jù)時(shí),通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值,而且還要存儲(chǔ)_.數(shù)據(jù)的處理方法|數(shù)據(jù)元素的類型|數(shù)據(jù)元素之間的關(guān)系|數(shù)據(jù)的存儲(chǔ)方法17、在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)中,一個(gè)存儲(chǔ)結(jié)

5、點(diǎn)存儲(chǔ)一個(gè)_.數(shù)據(jù)項(xiàng)|數(shù)據(jù)元素|數(shù)據(jù)結(jié)構(gòu)|數(shù)據(jù)類型18、在計(jì)算機(jī)的存儲(chǔ)器中表示時(shí),物理地址和邏輯地址直接對(duì)應(yīng)并且是連續(xù)的,稱之為_(kāi).邏輯結(jié)構(gòu)|順序存儲(chǔ)結(jié)構(gòu)|鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)|以上都對(duì)19、數(shù)據(jù)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí),要求_.每個(gè)結(jié)點(diǎn)用占一片連續(xù)的存儲(chǔ)區(qū)域|所有結(jié)點(diǎn)占用一片連續(xù)的存儲(chǔ)區(qū)域|結(jié)點(diǎn)的最后一個(gè)數(shù)據(jù)域是指針類型|每個(gè)結(jié)點(diǎn)有多少個(gè)后繼,就設(shè)多少個(gè)指針域20、數(shù)據(jù)的運(yùn)算_.效率與采用何種存儲(chǔ)結(jié)構(gòu)有關(guān)|是根據(jù)存儲(chǔ)結(jié)構(gòu)來(lái)定義的|有算術(shù)運(yùn)算和關(guān)系運(yùn)算兩大類|必須用程序設(shè)計(jì)語(yǔ)言來(lái)描述21、下列說(shuō)法中,不正確的是_.數(shù)據(jù)元素是數(shù)據(jù)的基本單位|數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)識(shí)單位|數(shù)據(jù)可由若干個(gè)數(shù)據(jù)元素構(gòu)成|

6、數(shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成22、_不是算法的基本特性.可行性|長(zhǎng)度有限|在規(guī)定的時(shí)間內(nèi)完成|確定性23、計(jì)算機(jī)中算法指的是解決某一問(wèn)題的有限運(yùn)算序列,它必須具備輸入、輸出、_.可行性、可移植性和可擴(kuò)充性|可行性、有窮性和確定性|確定性、有窮性和穩(wěn)定性|易讀性、穩(wěn)定性和確定性24、以下不屬于算法特性的是_.可行性|有輸入|確定性|健壯性25、下面關(guān)于算法的說(shuō)法正確的是_.算法最終必須由程序?qū)崿F(xiàn)|算法的有窮性是對(duì)于任意的一組輸入值必須在有窮步驟后結(jié)束|算法的可行性是指指令不能有二義性|以上幾個(gè)都是錯(cuò)誤的26、算法的時(shí)間復(fù)雜度與_有關(guān)問(wèn)題規(guī)模|計(jì)算機(jī)硬件性能|編譯程序質(zhì)量|程序設(shè)計(jì)語(yǔ)言27、算法分

7、析的主要任務(wù)是分析_.算法是否具有較好的可讀性|算法中是否存在語(yǔ)法錯(cuò)誤|算法的功能是否符合設(shè)計(jì)要求|算法的執(zhí)行時(shí)間和問(wèn)題規(guī)模之間的關(guān)系28、某算法的時(shí)間復(fù)雜度為O(n2),表明該算法的_.問(wèn)題規(guī)模是n2|執(zhí)行時(shí)間等于n2|執(zhí)行時(shí)間與n2成正比|問(wèn)題規(guī)模與n2成正比29、算法分析的目的是_.找出數(shù)據(jù)結(jié)構(gòu)的合理性|研究算法中輸入和輸出關(guān)系|分析算法的效率以求改進(jìn)|分析算法的易讀性和文檔性30、線性表是具有n個(gè)_的有限序列。表元素|字符|數(shù)據(jù)元素|數(shù)據(jù)項(xiàng)31、線性表是_。一個(gè)有限序列，可以為空|一個(gè)有限序列，不可以為空|一個(gè)無(wú)限序列，可以為空|一個(gè)無(wú)限序列，不可以為空32、線性表采用鏈表存儲(chǔ)時(shí)，其地

8、址_。必須是連續(xù)的|一定是不連續(xù)的|部分地址必須是連續(xù)的|連續(xù)與否均可以33、鏈表不具備的特點(diǎn)是_?？呻S機(jī)訪問(wèn)任一結(jié)點(diǎn)|插入刪除不需要移動(dòng)元素|不必事先估計(jì)存儲(chǔ)空間|所需空間與其長(zhǎng)度成正比34、線性表的靜態(tài)存儲(chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)相比優(yōu)點(diǎn)是_。所有的操作算法實(shí)現(xiàn)簡(jiǎn)單|便于隨機(jī)存取|便于插入和刪除|便于利用零散的存儲(chǔ)器空間35、設(shè)線性表有n個(gè)元素，以下操作中，_在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更高。輸出第i(1<=i<=n)個(gè)元素值|交換第1個(gè)元素與第2個(gè)元素的值|順序輸出這n個(gè)元素的值|輸出與給定值x相等的元素在線性表中的序號(hào)36、對(duì)于一個(gè)線性表，既要求能夠較快地進(jìn)行插入和刪除，又要

9、求存儲(chǔ)結(jié)構(gòu)能夠反映數(shù)據(jù)元素之間的邏輯關(guān)系，則應(yīng)采用_存儲(chǔ)結(jié)構(gòu)。順序|鏈?zhǔn)絴散列|索引37、設(shè)線性表中有2n個(gè)元素，以下操作中，_在單鏈表上實(shí)現(xiàn)要比在順序表上實(shí)現(xiàn)效率更高。刪除指定的元素|在最后一個(gè)元素的后面插入一個(gè)新元素|順序輸出前k個(gè)元素|交換第i個(gè)元素和第2n-i-1個(gè)元素的值(i=0，1，n-1)38、需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是_。單鏈表|靜態(tài)鏈表|線性鏈表|順序存儲(chǔ)結(jié)構(gòu)39、如果最常用其所長(zhǎng)的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用_結(jié)構(gòu)方式最節(jié)省時(shí)間。單鏈表|雙鏈表|單循環(huán)鏈表|順序表40、與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是_。插入、刪除操作更簡(jiǎn)單|可以

10、進(jìn)行隨機(jī)訪問(wèn)|可以省略表頭指針或表尾指針|訪問(wèn)前后相鄰結(jié)點(diǎn)更靈活41、數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指_.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)|數(shù)據(jù)結(jié)構(gòu)|數(shù)據(jù)的邏輯結(jié)構(gòu)|數(shù)據(jù)元素之間的關(guān)系42、下面程序段的時(shí)間復(fù)雜度為_(kāi)O(m)| O(n)|O(m*n)|O(m+n) for(int i=0;i<m;i+) for(int j=0;j<n;j+) aij=i*j;數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題答案：緒論單選題1、存儲(chǔ)|物理|邏輯|物理和存儲(chǔ) C1C 2C 3A 4A 5B 6A 7C 8A 9B 10D 11AB 12AB 13B 14C 2、動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)|緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)|線性結(jié)構(gòu)和非線性結(jié)構(gòu)|內(nèi)部結(jié)構(gòu)和外

11、部結(jié)構(gòu)圖 ? A C3、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)|數(shù)據(jù)結(jié)構(gòu)|數(shù)據(jù)的邏輯結(jié)構(gòu)|數(shù)據(jù)元素之間的關(guān)系 A4、邏輯|存儲(chǔ)|邏輯和存儲(chǔ)|物理 A5、線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)|二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表|棧的操作方式是先進(jìn)先出|隊(duì)列的操作方式是先進(jìn)后出 B6、各結(jié)點(diǎn)的值如何|結(jié)束個(gè)數(shù)的多少|(zhì)對(duì)數(shù)據(jù)有哪些運(yùn)算|所用編程語(yǔ)言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便 A7、數(shù)據(jù)的處理方法|數(shù)據(jù)元素的類型|數(shù)據(jù)元素之間的關(guān)系|數(shù)據(jù)的存儲(chǔ)方法 C8、(1)|(1)、(2)|(1)、(4)|(3) A9、數(shù)據(jù)元素具有同一特點(diǎn)|不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)的數(shù)據(jù)項(xiàng)的類型要一致|每個(gè)數(shù)據(jù)元素都一樣|數(shù)據(jù)元素所

12、包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等 B10、數(shù)據(jù)元素是數(shù)據(jù)的最小單位|數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位|數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項(xiàng)的集合|一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu) D11、數(shù)據(jù)項(xiàng)|數(shù)據(jù)元素|信息項(xiàng)|表元素 A|B12、(1)數(shù)據(jù)元素 (2)結(jié)構(gòu)|(1)計(jì)算方法 (2)關(guān)系|(1)邏輯存儲(chǔ) (2)運(yùn)算|(1)數(shù)據(jù)映像 (2)算法 A|B13、數(shù)據(jù)和數(shù)據(jù)之間存在的某種關(guān)系|元素和元素之間存在某種關(guān)系|元素內(nèi)部具有某種結(jié)構(gòu)|數(shù)據(jù)項(xiàng)和數(shù)據(jù)項(xiàng)之間存在某種關(guān)系 B14、動(dòng)態(tài)結(jié)構(gòu)和表態(tài)結(jié)構(gòu)|緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)|線性結(jié)構(gòu)和非線性結(jié)構(gòu)|內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) C 15A 16C 17B 18B 19A 20A21D

13、 22B 23B 24D 25B 26A 27D 28C 29C 30C 31A 32D 33A 34C 35A 36B 37A 38B 39B 40D 41A 42C15、數(shù)據(jù)元素之間邏輯|數(shù)據(jù)項(xiàng)之間邏輯|數(shù)據(jù)類型之間|存儲(chǔ)結(jié)構(gòu)之間 A16、數(shù)據(jù)的處理方法|數(shù)據(jù)元素的類型|數(shù)據(jù)元素之間的關(guān)系|數(shù)據(jù)的存儲(chǔ)方法 C17、數(shù)據(jù)項(xiàng)|數(shù)據(jù)元素|數(shù)據(jù)結(jié)構(gòu)|數(shù)據(jù)類型 B18、邏輯結(jié)構(gòu)|順序存儲(chǔ)結(jié)構(gòu)|鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)|以上都對(duì) B19、每個(gè)結(jié)點(diǎn)用占一片連續(xù)的存儲(chǔ)區(qū)域|所有結(jié)點(diǎn)占用一片連續(xù)的存儲(chǔ)區(qū)域|結(jié)點(diǎn)的最后一個(gè)數(shù)據(jù)域是指針類型|每個(gè)結(jié)點(diǎn)有多少個(gè)后繼,就設(shè)多少個(gè)指針域 A20、效率與采用何種存儲(chǔ)結(jié)構(gòu)有關(guān)|是根據(jù)

14、存儲(chǔ)結(jié)構(gòu)來(lái)定義的|有算術(shù)運(yùn)算和關(guān)系運(yùn)算兩大類|必須用程序設(shè)計(jì)語(yǔ)言來(lái)描述 A21、數(shù)據(jù)元素是數(shù)據(jù)的基本單位|數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)識(shí)單位|數(shù)據(jù)可由若干個(gè)數(shù)據(jù)元素構(gòu)成|數(shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成 D22、可行性|長(zhǎng)度有限|在規(guī)定的時(shí)間內(nèi)完成|確定性 B23、可行性、可移植性和可擴(kuò)充性|可行性、有窮性和確定性|確定性、有窮性和穩(wěn)定性|易讀性、穩(wěn)定性和確定性 B24、可行性|有輸入|確定性|健壯性 D25、算法最終必須由程序?qū)崿F(xiàn)|算法的有窮性是對(duì)于任意的一組輸入值必須在有窮步驟后結(jié)束|算法的可行性是指指令不能有二義性|以上幾個(gè)都是錯(cuò)誤的 B26、問(wèn)題規(guī)模|計(jì)算機(jī)硬件性能|編譯程序質(zhì)量|程序

15、設(shè)計(jì)語(yǔ)言 A27、算法是否具有較好的可讀性|算法中是否存在語(yǔ)法錯(cuò)誤|算法的功能是否符合設(shè)計(jì)要求|算法的執(zhí)行時(shí)間和問(wèn)題規(guī)模之間的關(guān)系 D28、問(wèn)題規(guī)模是n2|執(zhí)行時(shí)間等于n2|執(zhí)行時(shí)間與n2成正比|問(wèn)題規(guī)模與n2成正比 C29、找出數(shù)據(jù)結(jié)構(gòu)的合理性|研究算法中輸入和輸出關(guān)系|分析算法的效率以求改進(jìn)|分析算法的易讀性和文檔性 C30、表元素|字符|數(shù)據(jù)元素|數(shù)據(jù)項(xiàng) C31、一個(gè)有限序列，可以為空|一個(gè)有限序列，不可以為空|一個(gè)無(wú)限序列，可以為空|一個(gè)無(wú)限序列，不可以為空 A32、必須是連續(xù)的|一定是不連續(xù)的|部分地址必須是連續(xù)的|連續(xù)與否均可以 D33、可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)|插入刪除不需要移動(dòng)元素|

16、不必事先估計(jì)存儲(chǔ)空間|所需空間與其長(zhǎng)度成正比 A34、所有的操作算法實(shí)現(xiàn)簡(jiǎn)單|便于隨機(jī)存取|便于插入和刪除|便于利用零散的存儲(chǔ)器空間C 35、輸出第i(1<=i<=n)個(gè)元素值|交換第1個(gè)元素與第2個(gè)元素的值|順序輸出這n個(gè)元素的值|輸出與給定值x相等的元素在線性表中的序號(hào) A36、順序|鏈?zhǔn)絴散列|索引 B37、刪除指定的元素|在最后一個(gè)元素的后面插入一個(gè)新元素|順序輸出前k個(gè)元素|交換第i個(gè)元素和第2n-i-1個(gè)元素的值(i=0，1，n-1) A38、單鏈表|靜態(tài)鏈表|線性鏈表|順序存儲(chǔ)結(jié)構(gòu) B39、單鏈表|雙鏈表|單循環(huán)鏈表|順序表 D40、插入、刪除操作更簡(jiǎn)單|可以進(jìn)行隨機(jī)

17、訪問(wèn)|可以省略表頭指針或表尾指針|訪問(wèn)前后相鄰結(jié)點(diǎn)更靈活 D41、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)|數(shù)據(jù)結(jié)構(gòu)|數(shù)據(jù)的邏輯結(jié)構(gòu)|數(shù)據(jù)元素之間的關(guān)系 A42、O(m|O(m*n)|O(m+n) C數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：緒論判斷題1、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。2、數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位。3、數(shù)據(jù)元素是數(shù)據(jù)的最小單位4、數(shù)據(jù)對(duì)象就是一組任意數(shù)據(jù)元素的集合5、任何數(shù)據(jù)結(jié)構(gòu)都具備3個(gè)基本運(yùn)算: 插入、刪除和查找.6、數(shù)據(jù)是由一些類型相同的數(shù)據(jù)元素構(gòu)成的7、數(shù)據(jù)是邏輯結(jié)構(gòu)與各數(shù)據(jù)元素在計(jì)算機(jī)中如何存儲(chǔ)有關(guān)8、如果數(shù)據(jù)元素值發(fā)生改變,則數(shù)據(jù)的邏輯結(jié)構(gòu)也隨之改變.9、邏輯結(jié)構(gòu)相同的數(shù)據(jù),可以采用多種不同的存儲(chǔ)方法.10、邏輯結(jié)構(gòu)相同的

18、數(shù)據(jù),結(jié)點(diǎn)類型也一定相同11、邏輯結(jié)構(gòu)不相同的數(shù)據(jù),必須采用不同的存儲(chǔ)方式來(lái)存儲(chǔ)12、數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系.13、算法的優(yōu)劣與算法描述語(yǔ)言有無(wú)關(guān)，但與所有計(jì)算機(jī)有關(guān)。14、算法可以用不同的語(yǔ)言描述，如果用C或Pascal等高級(jí)語(yǔ)言來(lái)描述，則算法實(shí)際上就是程序了。15、程序一定是算法。16、算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)。F19、健壯的算法不會(huì)因非法入輸數(shù)據(jù)而出現(xiàn)莫名其妙的執(zhí)行結(jié)果。數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題答案：緒論判斷題1、False2、False3、False4、False5、False6、True7、False8、False9、True10、False11、False12、F

19、alse13、False14、False15、False16、False19、True數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：緒論算法分析題1、求兩個(gè)n階矩形的乘法C=A*B,其算法如下:#define MAX 100void maxtrixmult(int ,float aMAXMAX,bMAXMAX,float cMAXMAX) int i,j,k; float x; for(i=1;i<=n;i+) / for (j=1;j<=n;j+) / x=0; / for(k=1;k<=n;k+) / x+=aik*bkj; / cij=x; / 計(jì)算各語(yǔ)句的頻度,并分析該算法的時(shí)間復(fù)雜度。2、設(shè)n是

20、偶數(shù),試計(jì)算運(yùn)行下列程序段后m的值并給出該程序段的時(shí)間復(fù)雜度。m=0;for(i=1;i<=n;i+) for(j=2*1;j<=n;j+) m+; 3、閱讀下列算法:void suan_fa(int n) int i,j,k,s,x; for (s=0,i=0;i<n;i+) for (j=i;j<n;j+) s+; i=1;j=n;x=0; while (i<j) i+; j-; x+=2; pirntf("s=%d,x=%d",s,x);(1) 分析算法中語(yǔ)句"s+;"的執(zhí)行次數(shù); (2) 分析算法中語(yǔ)句"x

21、+=2;"的執(zhí)行次數(shù); (3) 分析該算法的時(shí)間復(fù)雜度; (4) 假定n=5, 試指出執(zhí)行該算法的輸出結(jié)果。6、設(shè)n是偶數(shù),試計(jì)算運(yùn)行下列程序段后m的值并給出該程序段的時(shí)間復(fù)雜度。int m=0,i,j;for (i=1;i<=n;i+) for (j=2*i;j<=n;j+) m+; m=n*n/4 O()數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題答案：緒論算法分析題1、答： 語(yǔ)句 頻度f(wàn)or(i=1;i<=n;i+) / n+1 for (j=1;j<=n;j+) / n(n+1)x=0; / n2for(k=1;k<=n;k+) / n2(n+1)x+=aik*bkj; /

22、n3cij=x; / n2所以：f(n)n+1+ n(n+1)+ n2+ n2(n+1)+ n3+ n2=2n3+4n2+2n+1=O( n3 )2、答：m+n(n-1) O(n2)3、分析算法中語(yǔ)句”s+;”的執(zhí)行次數(shù)：n+（n-1）+(n-2)+1=n(n+1)/2分析算法中語(yǔ)句”x+=2;”的執(zhí)行次數(shù): n/2分析該算法的時(shí)間復(fù)雜度: O(n2) 假定n=5，試指出執(zhí)行該算法的輸出結(jié)果: s=15, x=46、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：緒論填空題1、一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中_映像_稱為存儲(chǔ)結(jié)構(gòu)。2、數(shù)據(jù)邏輯結(jié)構(gòu)包括 、 和 三種類型，樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為_(kāi)。3、在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)_前驅(qū)結(jié)點(diǎn)

23、，其余每個(gè)結(jié)點(diǎn)有且只有_個(gè)前驅(qū)結(jié)點(diǎn)：最后一個(gè)結(jié)點(diǎn)_后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有_個(gè)后續(xù)結(jié)點(diǎn)。4、在樹(shù)形結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有_結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有_個(gè)前驅(qū)結(jié)點(diǎn):葉子結(jié)點(diǎn)沒(méi)有_結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)后的后續(xù)結(jié)點(diǎn)可以_5、在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以_任意多個(gè)_。6、線性結(jié)構(gòu)中元素之間存在_一對(duì)一_關(guān)系，樹(shù)形結(jié)構(gòu)中元素之間存在_一對(duì)多_關(guān)系，圖形結(jié)構(gòu)中元素之間存在_多對(duì)多_關(guān)系。7、算法的5個(gè)重要特性是_、_、_、輸入和輸出。8、算法可以用不同的語(yǔ)言描述，如果用C語(yǔ)言或PASCAL語(yǔ)言等高級(jí)語(yǔ)言來(lái)描述，則算法實(shí)現(xiàn)上就是程序了。這個(gè)斷言是_。9、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)在計(jì)

24、算機(jī)中的映射(或表示)分別稱為存儲(chǔ)結(jié)構(gòu)、結(jié)點(diǎn)和數(shù)據(jù)域。這個(gè)斷言是_。10、下面程序段的時(shí)間復(fù)雜度是_。 for (i=0;i<n;i+) for(j=0;j<m;j+) Aij=0;11、下面程序段的時(shí)間復(fù)雜度是_O(sqrt(n)_。 i=s=0; while(s<n) i+; s+=i; 12、下面程序段的時(shí)間復(fù)雜度是_。s=0;for (i=0;i<n;i+) for (j=0;j<n;j+) s+=Bij;sum=s;13、下面程序段的時(shí)間復(fù)雜度是_O(log3n)_。i=1;while(i<=n) i=i*3;14、有如下遞歸函數(shù)fact(n),分

25、析其時(shí)間復(fù)雜度。int fact(int n) if (n<=1) return 1; else return (n*fact(n-1);15、指出下列各算法的時(shí)間復(fù)雜度(1) prime(int n) int i=2; while(n%i!=0 && i<sqrt(n) i+; if (i*1.0>sqrt(n) printf "是一素?cái)?shù)" else printf "不是一素?cái)?shù)" O(sqrt(n)(2) sum1(int n) int p=1,sum=0,i; for (i=1;i<=n;i+) p*=i; s

26、um+=p; returm (sum); (3) sum2(int n) int sum=0,i,j; for (i=1;i<=n;i+) p=1; for (j=1;j<=i;j+) p*=j; sum+=p; return (sum); 16、數(shù)據(jù)的邏輯結(jié)構(gòu)是指_.17、一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的_表示_稱為存儲(chǔ)結(jié)構(gòu).18、順序存儲(chǔ)方法是把邏輯上_相鄰的結(jié)點(diǎn)_存儲(chǔ)在物理位置上_相鄰的存儲(chǔ)單元_里;鏈?zhǔn)酱鎯?chǔ)方法中結(jié)點(diǎn)間的邏輯關(guān)系是由 附加的指針字段表示_的.19、數(shù)據(jù)結(jié)構(gòu)是指研究數(shù)據(jù)的_存儲(chǔ)結(jié)構(gòu)_和_邏輯結(jié)構(gòu)_以及它們之間的相互關(guān)系,并對(duì)這種結(jié)構(gòu)定義相應(yīng)的_運(yùn)算_,設(shè)計(jì)出相應(yīng)的_算

27、法_,從而確保經(jīng)過(guò)這些運(yùn)算后所得到的新結(jié)構(gòu)是原來(lái)的結(jié)構(gòu)類型.20、一個(gè)算法具有5個(gè)特性:_、_、_、輸入和輸出。21、算法的執(zhí)行時(shí)間是_的函數(shù)。22、數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯上描述數(shù)據(jù),它與數(shù)據(jù)的_存儲(chǔ)結(jié)構(gòu)、物理結(jié)構(gòu)_無(wú)關(guān),是獨(dú)立于計(jì)算機(jī)的.23、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_(kāi)、_、_和_種。24、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為_(kāi)、_、_和_種。25、在線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點(diǎn)之間分別存在著_1:1_、_1：N_、_M:N_的聯(lián)系。26、一種抽象數(shù)據(jù)類型包括_數(shù)據(jù)_和_操作_兩個(gè)部分。27、從一維數(shù)組an中順序查找出一個(gè)最大值元素的時(shí)間復(fù)雜度為_(kāi)，輸出一個(gè)二維數(shù)組bmn中所有元素值的時(shí)間復(fù)雜

28、度為_(kāi)28、在下面程序段中，s=s+p語(yǔ)句的執(zhí)行次數(shù)為_(kāi)n_，p*=j語(yǔ)句的執(zhí)行次數(shù)為_(kāi)n*(n+1)/2_，該程序段的時(shí)間復(fù)雜度為_(kāi)O(n*n)_。int i=0,s=0;while(+i<=n) int p=1;for(int j=1;j<=i;j+)p*=j;s=s+p;29、一個(gè)算法的時(shí)間復(fù)雜度為（3*n*n+2nlog2n+4n-7)/(5n)，其數(shù)量級(jí)表示為_(kāi)O(n)_。30、從一個(gè)數(shù)組a10中順序查找元素時(shí)，假定查找每個(gè)元素的概率都相同，則進(jìn)行一次查找運(yùn)算時(shí)的平均查找長(zhǎng)度（即同元素的平均比較次數(shù)）為_(kāi)。31、從一個(gè)數(shù)組a7中順序查找元素時(shí)，假定查找第1個(gè)元素a0的概率

29、為1/3，查找第2個(gè)元素a1的概率為1/4，其找其余元素的概率均相同，則在查找成功時(shí)同元素的平均比較次數(shù)為_(kāi)35/12_。32、對(duì)于一個(gè)n*n的矩陣的任意矩陣元素aij，按行存儲(chǔ)時(shí)和按列存儲(chǔ)時(shí)的地址之差是_(i-j)*(n-1)*d_。設(shè)兩種存儲(chǔ)時(shí)的開(kāi)始存儲(chǔ)地址均為(0,0)，每個(gè)元素所占存儲(chǔ)單元數(shù)均為d。33、設(shè)有一個(gè)二維數(shù)組A1020，按行存放于一個(gè)連續(xù)的存儲(chǔ)空間中，A00的存儲(chǔ)地址是200，每個(gè)數(shù)組元素占1個(gè)存儲(chǔ)字，則A62的存儲(chǔ)字地址是_34、設(shè)有一個(gè)二維數(shù)組A1020，按列為主序存放于一個(gè)連續(xù)的存儲(chǔ)空間中，A00的存儲(chǔ)地址是200，每個(gè)數(shù)組元素占1個(gè)存儲(chǔ)字，則A62的存儲(chǔ)字地址是_。

30、37、在線性表的單鏈接存儲(chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)包含有兩個(gè)域，一個(gè)叫_，另一個(gè)叫_域。數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題答案：緒論填空題1、映射2、線性結(jié)構(gòu)|樹(shù)形結(jié)構(gòu)|圖形結(jié)構(gòu)|非線性結(jié)構(gòu)3、沒(méi)有|1|沒(méi)有|14、前驅(qū)|1|后續(xù)|任意多個(gè)5、任意多個(gè)6、一對(duì)一|一對(duì)多|多對(duì)多7、有窮性|確定性|可行性8、錯(cuò)誤9、正確10、O(n*m)11、O(n)12、O(n2)13、O(log3n)14、O(n)15、O(n)|O(n)|O(n2)16、數(shù)據(jù)元素之間的邏輯關(guān)系17、映像?表示?映像或表示18、相鄰的結(jié)點(diǎn)|相鄰的存儲(chǔ)單元|附加的指針字段表示19、存儲(chǔ)結(jié)構(gòu)?物理結(jié)構(gòu)|邏輯結(jié)構(gòu)|運(yùn)算|算法20、可行性|有窮性|確定性21、

31、問(wèn)題規(guī)模22、存儲(chǔ)結(jié)構(gòu)、物理結(jié)構(gòu)23、集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖形結(jié)構(gòu)（次序無(wú)先后）24、順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)（次序無(wú)先后）25、1:1|1:N|M:N26、數(shù)據(jù)|操作27、O(n) | O(m*n)28、n| n(n+1)/229、O(n)30、5.531、35/1232、(i-j)*(n-1)*d33、32234、22637、值|指針數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：緒論問(wèn)答題1、當(dāng)你為解決某一問(wèn)題而選擇數(shù)據(jù)結(jié)構(gòu)時(shí),應(yīng)從哪些方面考慮?2、簡(jiǎn)述邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系.3、數(shù)據(jù)運(yùn)算是數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要方面,試舉例說(shuō)明兩個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)方式完全相同,只是對(duì)于運(yùn)算的定義不同,因而

32、兩個(gè)結(jié)構(gòu)具有顯著不同的特性,則這兩個(gè)數(shù)據(jù)結(jié)構(gòu)是不同的.數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題答案：緒論問(wèn)答題1、解答：通常從兩方面考慮：第一是算法所需的存儲(chǔ)空間量；第二是算法所需的時(shí)間。對(duì)算法所需的時(shí)間又涉及以下三點(diǎn)： （1）程序運(yùn)行時(shí)所需輸入的數(shù)據(jù)總量。 （2）計(jì)算機(jī)執(zhí)行每條指令所需的時(shí)間。 （3）程序中指令重復(fù)執(zhí)行的次數(shù)。2、答：數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系（即數(shù)據(jù)元素之間的關(guān)聯(lián)方式或“鄰接關(guān)系”），數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，包括數(shù)據(jù)元素的表示及其關(guān)系的表示。3、答：棧和隊(duì)列的邏輯結(jié)構(gòu)相同，其存儲(chǔ)表示也可相同（順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)），但由于其運(yùn)算集合不同而成為不同的數(shù)據(jù)結(jié)構(gòu)。2 線性表沈

33、陽(yáng)理工大學(xué)應(yīng)用技術(shù)學(xué)院信息與控制學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)教研室2011-5-8數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：線性表單選題1、在一個(gè)長(zhǎng)度為n的順序表中，向第i個(gè)元素(1in+1)之前插入一個(gè)新元素時(shí)，需向后移動(dòng)_個(gè)元素。2、從一個(gè)具有n個(gè)節(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較_(n+1)/2_個(gè)結(jié)點(diǎn)。3、在一個(gè)單鏈表中，已知*q結(jié)點(diǎn)是*p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在*q和*p之間插入*s結(jié)點(diǎn)， 則執(zhí)行_。4、線性表是_ 。5、對(duì)順序存儲(chǔ)的線性表，設(shè)其長(zhǎng)度為n，在任何位置上插入或刪除操作都是等概率的， 刪除一個(gè)元素時(shí)大約要移動(dòng)表中的_個(gè)元素。6、線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址_。7、設(shè)單鏈表中指針

34、p指著結(jié)點(diǎn)m，指針f指著將要插入的新結(jié)點(diǎn)x，當(dāng)x插在鏈表中最后一個(gè)結(jié)點(diǎn)m之后時(shí)，只要先修改_后修改p->link=f即可。8、在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)需修改指針_。9、在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)的前趨結(jié)點(diǎn)（若存在）時(shí)需修改指針_。10、根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表分為單鏈表和_。11、在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上_。12、鏈表不具備的特點(diǎn)是_。13、不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是_。14、帶頭結(jié)點(diǎn)的單鏈表的head為空的判定條件是_。15、帶頭結(jié)點(diǎn)的雙循環(huán)表L為空表的條件是_L->next=

35、L_。16、非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由p所指向)滿足_。17、在循環(huán)雙鏈表的p所指結(jié)點(diǎn)之前插入s所指結(jié)點(diǎn)的操作是_。18、若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用_帶頭結(jié)點(diǎn)的雙循環(huán)鏈表_存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。19、某線性表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除第一個(gè)結(jié)點(diǎn)，故采用_僅有尾指針的單循環(huán)鏈表_存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。20、需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是_。21、如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用_順序表_存儲(chǔ)方式最節(jié)省時(shí)間。22、在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍

36、然保持有序的時(shí)間復(fù)雜度是_。23、在一個(gè)長(zhǎng)度為n(n>1)的單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行_刪除單鏈表中的最后一個(gè)元素_操作與鏈表的長(zhǎng)度有關(guān)。24、設(shè)線性表有n個(gè)元素，以下算法中，_在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更高。25、設(shè)線性表中有2n個(gè)元素，算法_刪除所有值為x的元素_，在單鏈表上實(shí)現(xiàn)要比在順序表上實(shí)現(xiàn)效率更高。26、與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是_。27、如果對(duì)線性表的運(yùn)算只有4種，即刪除第一個(gè)元素，刪除最后一個(gè)元素，在第一個(gè)元素前面插入新元素，在最后一個(gè)元素的后面插入新元素，則最后使用_只有表頭指針沒(méi)有表尾指針的循環(huán)雙鏈表_。28、如果對(duì)線性表的運(yùn)算只有兩種，即刪除第一

37、個(gè)元素，在最后一個(gè)元素的后面插入新元素，則最好使用_。29、設(shè)有兩個(gè)長(zhǎng)度為n的單鏈表，結(jié)點(diǎn)類型相同。若以h1為表頭指針的鏈表是非循環(huán)的，以h2為表頭指針的鏈表是循環(huán)的，則_。30、在長(zhǎng)度為n的_上，刪除第一個(gè)結(jié)點(diǎn)，其算法的時(shí)間復(fù)度為O(n)。31、將兩個(gè)各有n個(gè)元素的有序順序表歸并成一個(gè)有序順序表，其最少的比較次數(shù)是_n_。32、帶頭結(jié)點(diǎn)的單鏈表L為空的判定條件是_。33、在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是_。34、在一個(gè)長(zhǎng)度為n(n>1)的帶頭結(jié)點(diǎn)的單鏈表h上，另設(shè)有尾指針r(指向尾結(jié)點(diǎn))，執(zhí)行_操作與鏈表的長(zhǎng)度有關(guān)。35、在一個(gè)雙鏈表中，在*p

38、結(jié)點(diǎn)之后插入結(jié)點(diǎn)*q的操作是_。36、在一個(gè)雙鏈表中，在*p結(jié)點(diǎn)之前插入*q結(jié)點(diǎn)的操作是_。37、在一個(gè)雙鏈表達(dá)式，刪除*p結(jié)點(diǎn)的操作是_。38、在一個(gè)雙鏈表中，刪除*p結(jié)點(diǎn)之后的一個(gè)結(jié)點(diǎn)的操作是_。39、非空的循環(huán)單鏈表L的尾結(jié)點(diǎn)(由p所指向)滿足_。40、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是_。41、若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用_帶頭結(jié)點(diǎn)的循環(huán)雙鏈表_存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。42、如果對(duì)含有n(n>1)個(gè)元素的線性表的運(yùn)算只有4種:刪除第一個(gè)元素；刪除最后一個(gè)元素；在第一個(gè)元素前面插入新元素；在最后一個(gè)元素的后面插入新元素，則最好使用_

39、只有頭結(jié)點(diǎn)指針沒(méi)有尾結(jié)點(diǎn)指針的循環(huán)雙鏈表_。43、某線性表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除第一個(gè)結(jié)點(diǎn)，則采用_僅有尾結(jié)點(diǎn)指針的單循環(huán)鏈表_存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。44、設(shè)有兩個(gè)長(zhǎng)度為n的單鏈表，結(jié)點(diǎn)類型相同，若以h1為頭結(jié)點(diǎn)的鏈表是非循環(huán)的，以h2為頭結(jié)點(diǎn)指針的鏈表是循環(huán)的，則_。45、在長(zhǎng)度驎n(n>1)的_只有首結(jié)點(diǎn)指針h的不帶頭結(jié)點(diǎn)的循環(huán)單鏈表_上，刪除第一個(gè)元素，其算法的時(shí)間復(fù)雜度為O(n)。46、元素A、B、C、D依次進(jìn)順序棧后，棧頂元素是_，棧底元素是_。47、經(jīng)過(guò)以下棧運(yùn)算后，X的值是_。InitStack(s);Push(s,a);Push(s,b);P

40、op(s,x);GetTop(s,x);48、經(jīng)過(guò)以下的棧運(yùn)算后，StackEmpty(s)的值是_。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y)49、設(shè)一個(gè)棧的輸入序列為A、B、C、D，則借助一個(gè)棧所得到的輸出序列不可能是_。50、若線性表最常用的運(yùn)算是存取第i個(gè)元素及其前驅(qū)的值,則采用_存儲(chǔ)方式節(jié)省時(shí)間.51、鏈表不具備的特點(diǎn)是_.52、在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表中，向第i個(gè)元素(1<=i<=n+1)位置插入一個(gè)新元素時(shí)，需要從后向前依次后移_個(gè)元素53、在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表中，刪除第i個(gè)元素(1<

41、=i<=n)時(shí)，需要從前向后依次前移_n-i_個(gè)元素54、在一個(gè)長(zhǎng)度為n的線性表中順序查找值為x的元素時(shí)，查找成功時(shí)的平均查找長(zhǎng)度（即x同元素的平均比較次數(shù)，查找每個(gè)元素的概率都相等）為（）57、在一個(gè)單鏈表HL中，若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行_。數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題答案：線性表單選題1、n-1|n-i+1|n-i-1|I B2、n|n/2|(n-1)/2|(n+1)/2 D3、s->next=p->next; p->next=s;|p->next=s->next; s->next=p;|q->next=s; s->next=p;

42、|p->next=s; s->next=q; C4、一個(gè)有限序列，可以為空。|一個(gè)有限序列，不能為空。|一個(gè)無(wú)限序列，可以為空。|一個(gè)無(wú)限序列，不能為空。 A5、n+1|n-1|(n-1)/2|n C6、必須是連續(xù)的。|部分地址必須是連續(xù)的。|一定是不連續(xù)的。|連續(xù)與否均可以。D7、f->link=p;|f->link=p->link;|p->link=f->link;|f=nil; B8、(p->rlink) ->rlink) ->link=p;p->rlink=(p->rlink) ->rlink;|(p->

43、;llink) ->rlink=p->rlink;(p->rlink) ->llink=p->llink;|p->llink=(p->llink) ->llink;(p->llink) ->llink) ->rlink=p;|(p->llink) ->llink) ->rlink=p;p->llink=(p->llink) ->llink; B9、(p->llink) ->llink) ->rlink=p;p->llink=(p->llink) ->llin

44、k;|(p->rlink) ->rlink) ->llink=p;p->rlink=(p->rlink) ->rlink;|(p->llink) ->rlink=p->rlink;(p->rlink) ->llink=p->llink;| p->llink=(p->llink) ->llink;(p->llink) ->llink) ->rlink=p; A10、循環(huán)鏈表|多重鏈表|普通鏈表|無(wú)頭結(jié)點(diǎn)鏈表 B11、一定相鄰|不一定相鄰|有時(shí)相鄰| B12、可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)|插入刪除不需要移動(dòng)元素|不