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

1緒論沈陽(yáng)理工大學(xué)應(yīng)用技術(shù)學(xué)院信息與控制學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)教研室2011-5-8

數(shù)據(jù)構(gòu)造復(fù)習(xí)題：緒論單選題1、在數(shù)據(jù)構(gòu)造中，與所使用的計(jì)算機(jī)無(wú)關(guān)的數(shù)據(jù)叫__C___構(gòu)造。A存儲(chǔ)|B物理|C邏輯|D物理和存儲(chǔ)2、在數(shù)據(jù)構(gòu)造中，從邏輯上能夠把數(shù)據(jù)構(gòu)造分成___C___。A動(dòng)態(tài)構(gòu)造和靜態(tài)構(gòu)造|B緊湊構(gòu)造和非緊湊構(gòu)造|C線性構(gòu)造和非線性構(gòu)造|D內(nèi)部構(gòu)造和外部構(gòu)造圖3、數(shù)據(jù)構(gòu)造在計(jì)算機(jī)內(nèi)存中的表達(dá)是指____A___。數(shù)據(jù)的存儲(chǔ)構(gòu)造|數(shù)據(jù)構(gòu)造|數(shù)據(jù)的邏輯構(gòu)造|數(shù)據(jù)元素之間的關(guān)系4、在數(shù)據(jù)構(gòu)造中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的__A____構(gòu)造。邏輯|存儲(chǔ)|邏輯和存儲(chǔ)|物理5、在下列的敘述中，對(duì)的的是__B___。線性表的線性存儲(chǔ)構(gòu)造優(yōu)于鏈表存儲(chǔ)構(gòu)造|二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表|棧的操作方式是先進(jìn)先出|隊(duì)列的操作方式是先進(jìn)后出6、在決定選用何種存儲(chǔ)構(gòu)造時(shí)，普通不考慮_______。各結(jié)點(diǎn)的值如何|結(jié)束個(gè)數(shù)的多少|(zhì)對(duì)數(shù)據(jù)有哪些運(yùn)算|所用編程語(yǔ)言實(shí)現(xiàn)這種構(gòu)造與否方便7、在存儲(chǔ)數(shù)據(jù)時(shí)，普通不僅要存儲(chǔ)各數(shù)據(jù)元素的值，并且還要存儲(chǔ)_______。數(shù)據(jù)的解決辦法|數(shù)據(jù)元素的類(lèi)型|數(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ù)雜度是指最壞狀況下，預(yù)計(jì)算法執(zhí)行時(shí)間的一種上界(4)同一種算法，實(shí)現(xiàn)語(yǔ)句的級(jí)別越高，執(zhí)行效率越低(1)|(1)、(2)|(1)、(4)|(3)9、普通規(guī)定同一邏輯構(gòu)造中的全部數(shù)據(jù)元素含有相似的特性。這意味著______。數(shù)據(jù)元素含有同一特點(diǎn)|不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相似，并且對(duì)應(yīng)的數(shù)據(jù)項(xiàng)的類(lèi)型要一致|每個(gè)數(shù)據(jù)元素都同樣|數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等10、下列說(shuō)法對(duì)的的是_______。數(shù)據(jù)元素是數(shù)據(jù)的最小單位|數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位|數(shù)據(jù)構(gòu)造是帶構(gòu)造的數(shù)據(jù)項(xiàng)的集合|某些表面上很不相似的數(shù)據(jù)能夠有相似的邏輯構(gòu)造11、____是數(shù)據(jù)的最小單元,_____是數(shù)據(jù)的基本單位.數(shù)據(jù)項(xiàng)|數(shù)據(jù)元素|信息項(xiàng)|表元素12、數(shù)據(jù)構(gòu)造是指_____以及它們之間的_____.(1)數(shù)據(jù)元素(2)構(gòu)造|(1)計(jì)算辦法(2)關(guān)系|(1)邏輯存儲(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)部含有某種構(gòu)造|數(shù)據(jù)項(xiàng)和數(shù)據(jù)項(xiàng)之間存在某種關(guān)系14、數(shù)據(jù)的邏輯構(gòu)造能夠分為_(kāi)____兩類(lèi).動(dòng)態(tài)構(gòu)造和表態(tài)構(gòu)造|緊湊構(gòu)造和非緊湊構(gòu)造|線性構(gòu)造和非線性構(gòu)造|內(nèi)部構(gòu)造和外部構(gòu)造15、數(shù)據(jù)的邏輯構(gòu)造是指_____關(guān)系的整體.數(shù)據(jù)元素之間邏輯|數(shù)據(jù)項(xiàng)之間邏輯|數(shù)據(jù)類(lèi)型之間|存儲(chǔ)構(gòu)造之間16、在存儲(chǔ)數(shù)據(jù)時(shí),普通不僅要存儲(chǔ)各數(shù)據(jù)元素的值,并且還要存儲(chǔ)_____.數(shù)據(jù)的解決辦法|數(shù)據(jù)元素的類(lèi)型|數(shù)據(jù)元素之間的關(guān)系|數(shù)據(jù)的存儲(chǔ)辦法17、在數(shù)據(jù)的存儲(chǔ)構(gòu)造中,一種存儲(chǔ)結(jié)點(diǎn)存儲(chǔ)一種_____.數(shù)據(jù)項(xiàng)|數(shù)據(jù)元素|數(shù)據(jù)構(gòu)造|數(shù)據(jù)類(lèi)型18、在計(jì)算機(jī)的存儲(chǔ)器中表達(dá)時(shí),物理地址和邏輯地址直接對(duì)應(yīng)并且是持續(xù)的,稱之為_(kāi)____.邏輯構(gòu)造|次序存儲(chǔ)構(gòu)造|鏈?zhǔn)酱鎯?chǔ)構(gòu)造|以上都對(duì)19、數(shù)據(jù)采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造時(shí),規(guī)定_____.每個(gè)結(jié)點(diǎn)用占一片持續(xù)的存儲(chǔ)區(qū)域|全部結(jié)點(diǎn)占用一片持續(xù)的存儲(chǔ)區(qū)域|結(jié)點(diǎn)的最后一種數(shù)據(jù)域是指針類(lèi)型|每個(gè)結(jié)點(diǎn)有多少個(gè)后繼,就設(shè)多少個(gè)指針域20、數(shù)據(jù)的運(yùn)算_____.效率與采用何種存儲(chǔ)構(gòu)造有關(guān)|是根據(jù)存儲(chǔ)構(gòu)造來(lái)定義的|有算術(shù)運(yùn)算和關(guān)系運(yùn)算兩大類(lèi)|必須用程序設(shè)計(jì)語(yǔ)言來(lái)描述21、下列說(shuō)法中,不對(duì)的的是_____.數(shù)據(jù)元素是數(shù)據(jù)的基本單位|數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)記單位|數(shù)據(jù)可由若干個(gè)數(shù)據(jù)元素構(gòu)成|數(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、下列不屬于算法特性的是_____.可行性|有輸入|擬定性|強(qiáng)健性25、下面有關(guān)算法的說(shuō)法對(duì)的的是_____.算法最后必須由程序?qū)崿F(xiàn)|算法的有窮性是對(duì)于任意的一組輸入值必須在有窮環(huán)節(jié)后結(jié)束|算法的可行性是指指令不能有二義性|以上幾個(gè)都是錯(cuò)誤的26、算法的時(shí)間復(fù)雜度與______有關(guān)問(wèn)題規(guī)模|計(jì)算機(jī)硬件性能|編譯程序質(zhì)量|程序設(shè)計(jì)語(yǔ)言27、算法分析的重要任務(wù)是分析_____.算法與否含有較好的可讀性|算法中與否存在語(yǔ)法錯(cuò)誤|算法的功效與否符合設(shè)計(jì)規(guī)定|算法的執(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ù)構(gòu)造的合理性|研究算法中輸入和輸出關(guān)系|分析算法的效率以求改善|分析算法的易讀性和文檔性30、線性表是含有n個(gè)______的有限序列。表元素|字符|數(shù)據(jù)元素|數(shù)據(jù)項(xiàng)31、線性表是______。一種有限序列，可覺(jué)得空|一種有限序列，不可覺(jué)得空|一種無(wú)限序列，可覺(jué)得空|一種無(wú)限序列，不可覺(jué)得空32、線性表采用鏈表存儲(chǔ)時(shí)，其地址______。必須是持續(xù)的|一定是不持續(xù)的|部分地址必須是持續(xù)的|持續(xù)與否均能夠33、鏈表不含有的特點(diǎn)是______。可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)|插入刪除不需要移動(dòng)元素|不必事先預(yù)計(jì)存儲(chǔ)空間|所需空間與其長(zhǎng)度成正比34、線性表的靜態(tài)存儲(chǔ)構(gòu)造與次序存儲(chǔ)構(gòu)造相比優(yōu)點(diǎn)是_______。全部的操作算法實(shí)現(xiàn)簡(jiǎn)樸|便于隨機(jī)存取|便于插入和刪除|便于運(yùn)用零碎的存儲(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ì)于一種線性表，既規(guī)定能夠較快地進(jìn)行插入和刪除，又規(guī)定存儲(chǔ)構(gòu)造能夠反映數(shù)據(jù)元素之間的邏輯關(guān)系，則應(yīng)采用_______存儲(chǔ)構(gòu)造。次序|鏈?zhǔn)絴散列|索引37、設(shè)線性表中有2n個(gè)元素，下列操作中，______在單鏈表上實(shí)現(xiàn)要比在次序表上實(shí)現(xiàn)效率更高。刪除指定的元素|在最后一種元素的背面插入一種新元素|次序輸出前k個(gè)元素|交換第i個(gè)元素和第2n-i-1個(gè)元素的值(i=0，1，…，n-1)38、需要分派較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)構(gòu)造是______。單鏈表|靜態(tài)鏈表|線性鏈表|次序存儲(chǔ)構(gòu)造39、如果最慣用其所長(zhǎng)的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用______構(gòu)造方式最節(jié)省時(shí)間。單鏈表|雙鏈表|單循環(huán)鏈表|次序表40、與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是______。插入、刪除操作更簡(jiǎn)樸|能夠進(jìn)行隨機(jī)訪問(wèn)|能夠省略表頭指針或表尾指針|訪問(wèn)前后相鄰結(jié)點(diǎn)更靈活41、數(shù)據(jù)構(gòu)造在計(jì)算機(jī)內(nèi)存中的表達(dá)是指______.數(shù)據(jù)的存儲(chǔ)構(gòu)造|數(shù)據(jù)構(gòu)造|數(shù)據(jù)的邏輯構(gòu)造|數(shù)據(jù)元素之間的關(guān)系42、下面程序段的時(shí)間復(fù)雜度為_(kāi)________．O(m)|O(n)|O(m*n)|O(m+n)for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;數(shù)據(jù)構(gòu)造復(fù)習(xí)題答案：緒論單選題1、存儲(chǔ)|物理|邏輯|物理和存儲(chǔ)C1C2C3A4A5B6A1C2C3A4A5B6A7C8A9B10D11AB12AB13B14C3、數(shù)據(jù)的存儲(chǔ)構(gòu)造|數(shù)據(jù)構(gòu)造|數(shù)據(jù)的邏輯構(gòu)造|數(shù)據(jù)元素之間的關(guān)系A(chǔ)4、邏輯|存儲(chǔ)|邏輯和存儲(chǔ)|物理A5、線性表的線性存儲(chǔ)構(gòu)造優(yōu)于鏈表存儲(chǔ)構(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)這種構(gòu)造與否方便A7、數(shù)據(jù)的解決辦法|數(shù)據(jù)元素的類(lèi)型|數(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)的類(lèi)型要一致|每個(gè)數(shù)據(jù)元素都同樣|數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等B10、數(shù)據(jù)元素是數(shù)據(jù)的最小單位|數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位|數(shù)據(jù)構(gòu)造是帶構(gòu)造的數(shù)據(jù)項(xiàng)的集合|某些表面上很不相似的數(shù)據(jù)能夠有相似的邏輯構(gòu)造D11、數(shù)據(jù)項(xiàng)|數(shù)據(jù)元素|信息項(xiàng)|表元素A|B12、(1)數(shù)據(jù)元素(2)構(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)部含有某種構(gòu)造|數(shù)據(jù)項(xiàng)和數(shù)據(jù)項(xiàng)之間存在某種關(guān)系B14、動(dòng)態(tài)構(gòu)造和表態(tài)構(gòu)造|緊湊構(gòu)造和非緊湊構(gòu)造|線性構(gòu)造和非線性構(gòu)造|內(nèi)部構(gòu)造和外部構(gòu)造C15A16C17B18B19A20A21D22B23B24D25B26A27D15A16C17B18B19A20A21D22B23B24D25B26A27D28C29C30C31A32D33A34C35A36B37A38B39B40D41A42C16、數(shù)據(jù)的解決辦法|數(shù)據(jù)元素的類(lèi)型|數(shù)據(jù)元素之間的關(guān)系|數(shù)據(jù)的存儲(chǔ)辦法C17、數(shù)據(jù)項(xiàng)|數(shù)據(jù)元素|數(shù)據(jù)構(gòu)造|數(shù)據(jù)類(lèi)型B18、邏輯構(gòu)造|次序存儲(chǔ)構(gòu)造|鏈?zhǔn)酱鎯?chǔ)構(gòu)造|以上都對(duì)B19、每個(gè)結(jié)點(diǎn)用占一片持續(xù)的存儲(chǔ)區(qū)域|全部結(jié)點(diǎn)占用一片持續(xù)的存儲(chǔ)區(qū)域|結(jié)點(diǎn)的最后一種數(shù)據(jù)域是指針類(lèi)型|每個(gè)結(jié)點(diǎn)有多少個(gè)后繼,就設(shè)多少個(gè)指針域A20、效率與采用何種存儲(chǔ)構(gòu)造有關(guān)|是根據(jù)存儲(chǔ)構(gòu)造來(lái)定義的|有算術(shù)運(yùn)算和關(guān)系運(yùn)算兩大類(lèi)|必須用程序設(shè)計(jì)語(yǔ)言來(lái)描述A21、數(shù)據(jù)元素是數(shù)據(jù)的基本單位|數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)記單位|數(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、可行性|有輸入|擬定性|強(qiáng)健性D25、算法最后必須由程序?qū)崿F(xiàn)|算法的有窮性是對(duì)于任意的一組輸入值必須在有窮環(huán)節(jié)后結(jié)束|算法的可行性是指指令不能有二義性|以上幾個(gè)都是錯(cuò)誤的B26、問(wèn)題規(guī)模|計(jì)算機(jī)硬件性能|編譯程序質(zhì)量|程序設(shè)計(jì)語(yǔ)言A27、算法與否含有較好的可讀性|算法中與否存在語(yǔ)法錯(cuò)誤|算法的功效與否符合設(shè)計(jì)規(guī)定|算法的執(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ù)構(gòu)造的合理性|研究算法中輸入和輸出關(guān)系|分析算法的效率以求改善|分析算法的易讀性和文檔性C30、表元素|字符|數(shù)據(jù)元素|數(shù)據(jù)項(xiàng)C31、一種有限序列，可覺(jué)得空|一種有限序列，不可覺(jué)得空|一種無(wú)限序列，可覺(jué)得空|一種無(wú)限序列，不可覺(jué)得空A32、必須是持續(xù)的|一定是不持續(xù)的|部分地址必須是持續(xù)的|持續(xù)與否均能夠D33、可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)|插入刪除不需要移動(dòng)元素|不必事先預(yù)計(jì)存儲(chǔ)空間|所需空間與其長(zhǎng)度成正比A34、全部的操作算法實(shí)現(xiàn)簡(jiǎn)樸|便于隨機(jī)存取|便于插入和刪除|便于運(yùn)用零碎的存儲(chǔ)器空間C35、輸出第i(1<=i<=n)個(gè)元素值|交換第1個(gè)元素與第2個(gè)元素的值|次序輸出這n個(gè)元素的值|輸出與給定值x相等的元素在線性表中的序號(hào)A36、次序|鏈?zhǔn)絴散列|索引B37、刪除指定的元素|在最后一種元素的背面插入一種新元素|次序輸出前k個(gè)元素|交換第i個(gè)元素和第2n-i-1個(gè)元素的值(i=0，1，…，n-1)A38、單鏈表|靜態(tài)鏈表|線性鏈表|次序存儲(chǔ)構(gòu)造B39、單鏈表|雙鏈表|單循環(huán)鏈表|次序表D40、插入、刪除操作更簡(jiǎn)樸|能夠進(jìn)行隨機(jī)訪問(wèn)|能夠省略表頭指針或表尾指針|訪問(wèn)前后相鄰結(jié)點(diǎn)更靈活D41、數(shù)據(jù)的存儲(chǔ)構(gòu)造|數(shù)據(jù)構(gòu)造|數(shù)據(jù)的邏輯構(gòu)造|數(shù)據(jù)元素之間的關(guān)系A(chǔ)42、O(m||O(m*n)|O(m+n)C數(shù)據(jù)構(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ù)構(gòu)造都含有3個(gè)基本運(yùn)算:插入、刪除和查找.6、數(shù)據(jù)是由某些類(lèi)型相似的數(shù)據(jù)元素構(gòu)成的7、數(shù)據(jù)是邏輯構(gòu)造與各數(shù)據(jù)元素在計(jì)算機(jī)中如何存儲(chǔ)有關(guān)8、如果數(shù)據(jù)元素值發(fā)生變化,則數(shù)據(jù)的邏輯構(gòu)造也隨之變化.9、邏輯構(gòu)造相似的數(shù)據(jù),能夠采用多個(gè)不同的存儲(chǔ)辦法.10、邏輯構(gòu)造相似的數(shù)據(jù),結(jié)點(diǎn)類(lèi)型也一定相似11、邏輯構(gòu)造不相似的數(shù)據(jù),必須采用不同的存儲(chǔ)方式來(lái)存儲(chǔ)12、數(shù)據(jù)的邏輯構(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)。19、強(qiáng)健的算法不會(huì)因非法入輸數(shù)據(jù)而出現(xiàn)莫名其妙的執(zhí)行成果。數(shù)據(jù)構(gòu)造復(fù)習(xí)題答案：緒論判斷題1、False2、False3、False4、False5、False6、True7、False8、False9、True10、False11、False12、False13、False14、False15、False16、False19、True數(shù)據(jù)構(gòu)造復(fù)習(xí)題：緒論算法分析題1、求兩個(gè)n階矩形的乘法C=A*B,其算法以下:#defineMAX100voidmaxtrixmult(int,floata[MAX][MAX],b[MAX][MAX],floatc[MAX][MAX]){inti,j,k;floatx;for(i=1;i<=n;i++)//①{for(j=1;j<=n;j++)//②{x=0;//③for(k=1;k<=n;k++)//④x+=a[i][k]*b[k][j];//⑤c[i][j]=x;//⑥}}}計(jì)算①～⑥各語(yǔ)句的頻度,并分析該算法的時(shí)間復(fù)雜度。2、設(shè)n是偶數(shù),試計(jì)算運(yùn)行下列程序段后m的值并給出該程序段的時(shí)間復(fù)雜度。m=0;for(i=1;i<=n;i++)for(j=2*1;j<=n;j++)m++;3、閱讀下列算法:voidsuan_fa(intn){inti,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+=2;"的執(zhí)行次數(shù);(3)分析該算法的時(shí)間復(fù)雜度;(4)假定n=5,試指出執(zhí)行該算法的輸出成果。6、設(shè)n是偶數(shù),試計(jì)算運(yùn)行下列程序段后m的值并給出該程序段的時(shí)間復(fù)雜度。intm=0,i,j;for(i=1;i<=n;i++)for(j=2*i;j<=n;j++)m++;數(shù)據(jù)構(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+=a[i][k]*b[k][j];//⑤……n3c[i][j]=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í)行該算法的輸出成果:s=15,x=46、數(shù)據(jù)構(gòu)造復(fù)習(xí)題：緒論填空題1、一種數(shù)據(jù)構(gòu)造在計(jì)算機(jī)中______稱為存儲(chǔ)構(gòu)造。2、數(shù)據(jù)邏輯構(gòu)造涉及________，_________和________三種類(lèi)型，樹(shù)形構(gòu)造和圖形構(gòu)造合稱為_(kāi)_______。3、在線性構(gòu)造中，第一種結(jié)點(diǎn)________前驅(qū)結(jié)點(diǎn)，其它每個(gè)結(jié)點(diǎn)有且只有_______個(gè)前驅(qū)結(jié)點(diǎn)：最后一種結(jié)點(diǎn)______后續(xù)結(jié)點(diǎn)，其它每個(gè)結(jié)點(diǎn)有且只有______個(gè)后續(xù)結(jié)點(diǎn)。4、在樹(shù)形構(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、在圖形構(gòu)造中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)能夠________。6、線性構(gòu)造中元素之間存在_________關(guān)系，樹(shù)形構(gòu)造中元素之間存在_______關(guān)系，圖形構(gòu)造中元素之間存在________關(guān)系。7、算法的5個(gè)重要特性是_________、__________、__________、輸入和輸出。8、算法能夠用不同的語(yǔ)言描述，如果用C語(yǔ)言或PASCAL語(yǔ)言等高級(jí)語(yǔ)言來(lái)描述，則算法實(shí)現(xiàn)上就是程序了。這個(gè)斷言是________。9、數(shù)據(jù)構(gòu)造、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)在計(jì)算機(jī)中的映射(或表達(dá))分別稱為存儲(chǔ)構(gòu)造、結(jié)點(diǎn)和數(shù)據(jù)域。這個(gè)斷言是_______。10、下面程序段的時(shí)間復(fù)雜度是_______。for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;11、下面程序段的時(shí)間復(fù)雜度是_______。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+=B[i][j];sum=s;13、下面程序段的時(shí)間復(fù)雜度是________。i=1;while(i<=n)i=i*3;14、有以下遞歸函數(shù)fact(n),分析其時(shí)間復(fù)雜度。intfact(intn){if(n<=1)return1;elsereturn(n*fact(n-1));}15、指出下列各算法的時(shí)間復(fù)雜度(1)prime(intn){inti=2;while(n%i!=0&&i<sqrt(n))i++;if(i*1.0>sqrt(n))printf"是一素?cái)?shù)";elseprintf"不是一素?cái)?shù)";}(2)sum1(intn){intp=1,sum=0,i;for(i=1;i<=n;i++){p*=i;sum+=p;}returm(sum);}(3)sum2(intn){intsum=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ù)的邏輯構(gòu)造是指_____.17、一種數(shù)據(jù)構(gòu)造在計(jì)算機(jī)中的______稱為存儲(chǔ)構(gòu)造.18、次序存儲(chǔ)辦法是把邏輯上_____存儲(chǔ)在物理位置上______里;鏈?zhǔn)酱鎯?chǔ)辦法中結(jié)點(diǎn)間的邏輯關(guān)系是由_____的.19、數(shù)據(jù)構(gòu)造是指研究數(shù)據(jù)的_____和_____以及它們之間的互有關(guān)系,并對(duì)這種構(gòu)造定義對(duì)應(yīng)的_____,設(shè)計(jì)出對(duì)應(yīng)的_____,從而確保通過(guò)這些運(yùn)算后所得到的新構(gòu)造是原來(lái)的構(gòu)造類(lèi)型.20、一種算法含有5個(gè)特性:_____、_____、_____、輸入和輸出。21、算法的執(zhí)行時(shí)間是_____的函數(shù)。22、數(shù)據(jù)的邏輯構(gòu)造是從邏輯上描述數(shù)據(jù),它與數(shù)據(jù)的______無(wú)關(guān),是獨(dú)立于計(jì)算機(jī)的.23、數(shù)據(jù)的邏輯構(gòu)造被分為_(kāi)___________、____________、____________和____________４種。24、數(shù)據(jù)的存儲(chǔ)構(gòu)造被分為_(kāi)___________、____________、____________和____________４種。25、在線性構(gòu)造、樹(shù)形構(gòu)造和圖形構(gòu)造中，前驅(qū)和后繼結(jié)點(diǎn)之間分別存在著____________、____________、____________的聯(lián)系。26、一種抽象數(shù)據(jù)類(lèi)型涉及____________和____________兩個(gè)部分。27、從一維數(shù)組a[n]中次序查找出一種最大值元素的時(shí)間復(fù)雜度為_(kāi)___________，輸出一種二維數(shù)組b[m][n]中全部元素值的時(shí)間復(fù)雜度為_(kāi)___________28、在下面程序段中，s=s+p語(yǔ)句的執(zhí)行次數(shù)為_(kāi)___________，p*=j語(yǔ)句的執(zhí)行次數(shù)為_(kāi)___________，該程序段的時(shí)間復(fù)雜度為_(kāi)___________。inti=0,s=0;while(++i<=n){intp=1;for(intj=1;j<=i;j++)p*=j;s=s+p;}29、一種算法的時(shí)間復(fù)雜度為（3*n*n+2nlog2n+4n-7)/(5n)，其數(shù)量級(jí)表達(dá)為_(kāi)___________。30、從一種數(shù)組a[10]中次序查找元素時(shí)，假定查找每個(gè)元素的概率都相似，則進(jìn)行一次查找運(yùn)算時(shí)的平均查找長(zhǎng)度（即同元素的平均比較次數(shù)）為_(kāi)___________。31、從一種數(shù)組a[7]中次序查找元素時(shí)，假定查找第1個(gè)元素a[0]的概率為1/3，查找第2個(gè)元素a[1]的概率為1/4，其找其它元素的概率均相似，則在查找成功時(shí)同元素的平均比較次數(shù)為_(kāi)___________。32、對(duì)于一種n*n的矩陣Ａ的任意矩陣元素a[i][j]，按行存儲(chǔ)時(shí)和按列存儲(chǔ)時(shí)的地址之差是____________。設(shè)兩種存儲(chǔ)時(shí)的開(kāi)始存儲(chǔ)地址均為ＬＯＣ(0,0)，每個(gè)元素所占存儲(chǔ)單元數(shù)均為d。33、設(shè)有一種二維數(shù)組A[10][20]，按行寄存于一種持續(xù)的存儲(chǔ)空間中，A[0][0]的存儲(chǔ)地址是200，每個(gè)數(shù)組元素占1個(gè)存儲(chǔ)字，則A[6][2]的存儲(chǔ)字地址是____________34、設(shè)有一種二維數(shù)組A[10][20]，按列為主序寄存于一種持續(xù)的存儲(chǔ)空間中，A[0][0]的存儲(chǔ)地址是200，每個(gè)數(shù)組元素占1個(gè)存儲(chǔ)字，則A[6][2]的存儲(chǔ)字地址是____________。37、在線性表的單鏈接存儲(chǔ)構(gòu)造中，每個(gè)結(jié)點(diǎn)包含有兩個(gè)域，一種叫____________，另一種叫____________域。數(shù)據(jù)構(gòu)造復(fù)習(xí)題答案：緒論填空題1、映射2、線性構(gòu)造|樹(shù)形構(gòu)造|圖形構(gòu)造|非線性構(gòu)造3、沒(méi)有|1|沒(méi)有|14、前驅(qū)|1|后續(xù)|任意多個(gè)5、任意多個(gè)6、一對(duì)一|一對(duì)多|多對(duì)多7、有窮性|擬定性|可行性8、錯(cuò)誤9、對(duì)的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、映像?表達(dá)?映像或表達(dá)18、相鄰的結(jié)點(diǎn)|相鄰的存儲(chǔ)單元|附加的指針字段表達(dá)19、存儲(chǔ)構(gòu)造?物理構(gòu)造|邏輯構(gòu)造|運(yùn)算|算法20、可行性|有窮性|擬定性21、問(wèn)題規(guī)模22、存儲(chǔ)構(gòu)造、物理構(gòu)造23、集合構(gòu)造、線性構(gòu)造、樹(shù)形構(gòu)造、圖形構(gòu)造（次序無(wú)先后）24、次序構(gòu)造、鏈接構(gòu)造、索引構(gòu)造、散列構(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ù)構(gòu)造復(fù)習(xí)題：緒論問(wèn)答題1、當(dāng)你為解決某一問(wèn)題而選擇數(shù)據(jù)構(gòu)造時(shí),應(yīng)從哪些方面考慮?2、簡(jiǎn)述邏輯構(gòu)造與存儲(chǔ)構(gòu)造的關(guān)系.3、數(shù)據(jù)運(yùn)算是數(shù)據(jù)構(gòu)造的一種重要方面,試舉例闡明兩個(gè)數(shù)據(jù)構(gòu)造的邏輯構(gòu)造和存儲(chǔ)方式完全相似,只是對(duì)于運(yùn)算的定義不同,因而兩個(gè)構(gòu)造含有明顯不同的特性,則這兩個(gè)數(shù)據(jù)構(gòu)造是不同的.數(shù)據(jù)構(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ù)的邏輯構(gòu)造反映數(shù)據(jù)元素之間的邏輯關(guān)系（即數(shù)據(jù)元素之間的關(guān)聯(lián)方式或“鄰接關(guān)系”），數(shù)據(jù)的存儲(chǔ)構(gòu)造是數(shù)據(jù)構(gòu)造在計(jì)算機(jī)中的表達(dá)，涉及數(shù)據(jù)元素的表達(dá)及其關(guān)系的表達(dá)。3、答：棧和隊(duì)列的邏輯構(gòu)造相似，其存儲(chǔ)表達(dá)也可相似（次序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)），但由于其運(yùn)算集合不同而成為不同的數(shù)據(jù)構(gòu)造。2線性表沈陽(yáng)理工大學(xué)應(yīng)用技術(shù)學(xué)院信息與控制學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)教研室2011-5-8

數(shù)據(jù)構(gòu)造復(fù)習(xí)題：線性表單選題1、在一種長(zhǎng)度為n的次序表中，向第i個(gè)元素(1≤i≤n+1)之前插入一種新元素時(shí)，需向后移動(dòng)_____個(gè)元素。2、從一種含有n個(gè)節(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的狀況下，需平均比較_____個(gè)結(jié)點(diǎn)。3、在一種單鏈表中，已知*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，在任何位置上插入或刪除操作都是等概率的，刪除一種元素時(shí)大概要移動(dòng)表中的_____個(gè)元素。6、線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址_____。7、設(shè)單鏈表中指針p指著結(jié)點(diǎn)m，指針f指著將要插入的新結(jié)點(diǎn)x，當(dāng)x插在鏈表中最后一種結(jié)點(diǎn)m之后時(shí)，只要先修改_____后修改p->link=f即可。8、在雙向鏈表存儲(chǔ)構(gòu)造中，刪除p所指的結(jié)點(diǎn)時(shí)需修改指針_____。9、在雙向鏈表存儲(chǔ)構(gòu)造中，刪除p所指的結(jié)點(diǎn)的前趨結(jié)點(diǎn)（若存在）時(shí)需修改指針_____。10、根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造，每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表分為單鏈表和_____。11、在線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造中，邏輯上相鄰的元素在物理位置上_____。12、鏈表不含有的特點(diǎn)是_______。13、不帶頭結(jié)點(diǎn)的單鏈表head為空的鑒定條件是______。14、帶頭結(jié)點(diǎn)的單鏈表的head為空的鑒定條件是______。15、帶頭結(jié)點(diǎn)的雙循環(huán)表L為空表的條件是______。16、非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由p所指向)滿足_______。17、在循環(huán)雙鏈表的p所指結(jié)點(diǎn)之前插入s所指結(jié)點(diǎn)的操作是_______。18、若某表最慣用的操作是在最后一種結(jié)點(diǎn)之后插入一種結(jié)點(diǎn)或刪除最后一種結(jié)點(diǎn)，則采用______存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。19、某線性表最慣用的操作是在最后一種結(jié)點(diǎn)之后插入一種結(jié)點(diǎn)或刪除第一種結(jié)點(diǎn)，故采用_____存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。20、需要分派較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)構(gòu)造是_______。21、如果最慣用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用______存儲(chǔ)方式最節(jié)省時(shí)間。22、在一種含有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一種新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是______。23、在一種長(zhǎng)度為n(n>1)的單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行________操作與鏈表的長(zhǎng)度有關(guān)。24、設(shè)線性表有n個(gè)元素，下列算法中，_______在次序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更高。25、設(shè)線性表中有2n個(gè)元素，算法_______，在單鏈表上實(shí)現(xiàn)要比在次序表上實(shí)現(xiàn)效率更高。26、與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是________。27、如果對(duì)線性表的運(yùn)算只有4種，即刪除第一種元素，刪除最后一種元素，在第一種元素前面插入新元素，在最后一種元素的背面插入新元素，則最后使用________。28、如果對(duì)線性表的運(yùn)算只有兩種，即刪除第一種元素，在最后一種元素的背面插入新元素，則最佳使用_______。29、設(shè)有兩個(gè)長(zhǎng)度為n的單鏈表，結(jié)點(diǎn)類(lèi)型相似。若以h1為表頭指針的鏈表是非循環(huán)的，以h2為表頭指針的鏈表是循環(huán)的，則_______。30、在長(zhǎng)度為n的______上，刪除第一種結(jié)點(diǎn)，其算法的時(shí)間復(fù)度為O(n)。31、將兩個(gè)各有n個(gè)元素的有序次序表歸并成一種有序次序表，其最少的比較次數(shù)是_____。32、帶頭結(jié)點(diǎn)的單鏈表L為空的鑒定條件是______。33、在一種含有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一種新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是_______。34、在一種長(zhǎng)度為n(n>1)的帶頭結(jié)點(diǎn)的單鏈表h上，，另設(shè)有尾指針r(指向尾結(jié)點(diǎn))，執(zhí)行_______操作與鏈表的長(zhǎng)度有關(guān)。35、在一種雙鏈表中，在*p結(jié)點(diǎn)之后插入結(jié)點(diǎn)*q的操作是______。36、在一種雙鏈表中，在*p結(jié)點(diǎn)之前插入*q結(jié)點(diǎn)的操作是______。37、在一種雙鏈體現(xiàn)式，刪除*p結(jié)點(diǎn)的操作是_______。38、在一種雙鏈表中，刪除*p結(jié)點(diǎn)之后的一種結(jié)點(diǎn)的操作是________。39、非空的循環(huán)單鏈表L的尾結(jié)點(diǎn)(由p所指向)滿足______。40、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是______。41、若某表最慣用的操作是在最后一種結(jié)點(diǎn)之后插入一種結(jié)點(diǎn)或刪除最后一種結(jié)點(diǎn)，則采用_________存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。42、如果對(duì)含有n(n>1)個(gè)元素的線性表的運(yùn)算只有4種:刪除第一種元素；刪除最后一種元素；在第一種元素前面插入新元素；在最后一種元素的背面插入新元素，則最佳使用________。43、某線性表最慣用的操作是在最后一種結(jié)點(diǎn)之后插入一種結(jié)點(diǎn)或刪除第一種結(jié)點(diǎn)，則采用_______存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。44、設(shè)有兩個(gè)長(zhǎng)度為n的單鏈表，結(jié)點(diǎn)類(lèi)型相似，若以h1為頭結(jié)點(diǎn)的鏈表是非循環(huán)的，以h2為頭結(jié)點(diǎn)指針的鏈表是循環(huán)的，則________。45、在長(zhǎng)度驎n(n>1)的______上，刪除第一種元素，其算法的時(shí)間復(fù)雜度為O(n)。46、元素A、B、C、D依次進(jìn)次序棧后，棧頂元素是_______，棧底元素是______。47、通過(guò)下列棧運(yùn)算后，X的值是______。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x);48、通過(guò)下列的棧運(yùn)算后，StackEmpty(s)的值是______。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y)49、設(shè)一種棧的輸入序列為A、B、C、D，則借助一種棧所得到的輸出序列不可能是______。50、若線性表最慣用的運(yùn)算是存取第i個(gè)元素及其前驅(qū)的值,則采用______存儲(chǔ)方式節(jié)省時(shí)間.51、鏈表不含有的特點(diǎn)是______.52、在一種長(zhǎng)度為n的次序存儲(chǔ)的線性表中，向第i個(gè)元素(1<=i<=n+1)位置插入一種新元素時(shí)，需要從后向前依次后移_________個(gè)元素．53、在一種長(zhǎng)度為n的次序存儲(chǔ)的線性表中，刪除第i個(gè)元素(1<=i<=n)時(shí)，需要從前向后依次前移_________個(gè)元素．54、在一種長(zhǎng)度為n的線性表中次序查找值為x的元素時(shí)，查找成功時(shí)的平均查找長(zhǎng)度（即x同元素的平均比較次數(shù)，查找每個(gè)元素的概率都相等）為（）．57、在一種單鏈表HL中，若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行_________。數(shù)據(jù)構(gòu)造復(fù)習(xí)題答案：線性表單選題1、n-1|n-i+1|n-i-1|IB2、n|n/2|(n-1)/2|(n+1)/2D3、s->next=p->next;p->next=s;|p->next=s->next;s->next=p;|q->next=s;s->next=p;|p->next=s;s->next=q;C4、一種有限序列，可覺(jué)得空。|一種有限序列，不能為空。|一種無(wú)限序列，可覺(jué)得空。|一種無(wú)限序列，不能為空。A5、n+1|n-1|(n-1)/2|nC6、必須是持續(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->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)->llink;|((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)元素|不必事先預(yù)計(jì)存儲(chǔ)空間|所需空間與其長(zhǎng)度成正比A13、head==NULL|head->next==NULL|head->next==head|head!=NULLA14、head==NULL|head->next==NULL|head->next==head|head!=NULLB15、L=NULL|L->next==NULL|L->prior==NULL|L->next==LD16、p->next==NULL|p==NULL|p->next==head|p==headC17、p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior;|p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior;|s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s;|s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;D18、單鏈表|給出表頭指針的單循環(huán)鏈表|雙鏈表|帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D19、單鏈表|僅有頭結(jié)點(diǎn)的單循環(huán)鏈表|雙鏈表|僅有尾指針的單循環(huán)鏈表D20、單鏈表|靜態(tài)鏈表|線性鏈表|次序存儲(chǔ)構(gòu)造B21、單鏈表|雙鏈表|單循環(huán)鏈表|次序表D22、O(1)|O(n)|O(n2)|O(nlog2n)B23、刪除單鏈表中的第一種元素|刪除單鏈表中的最后一種元素|在單鏈表第一種元素前插入一種新元素|在單鏈表最后一種元素后插入一種新元素B24、輸出第i(0<=i<=n-1)個(gè)元素值|交換第0個(gè)元素與第1個(gè)元素的值|次序輸出這n個(gè)元素的值|輸出與給定值x相等的元素在線性表中的序號(hào)A25、刪除全部值為x的元素|在最后一種元素的背面插入一種新元素|次序輸出前k個(gè)元素|交換第i個(gè)元素和第2n-i-1個(gè)元素的值(i=0,i,…,n-1)A26、插入、刪除操作更簡(jiǎn)樸|能夠進(jìn)行隨機(jī)訪問(wèn)|能夠省略表頭指針或表尾指針|次序訪問(wèn)相鄰結(jié)點(diǎn)更靈活D27、只有表尾指針沒(méi)有頭指針的循環(huán)單鏈表|只有表尾指針沒(méi)有表頭指針的非循環(huán)雙鏈表|只有表頭指針沒(méi)有表尾指針的循環(huán)雙鏈表|現(xiàn)有表頭指針也有表尾指針的循環(huán)單鏈表C28、只有表頭指針沒(méi)有表尾指針的循環(huán)單鏈表|只有表尾指針沒(méi)有表頭指針的循環(huán)單鏈表|非循環(huán)雙鏈表|循環(huán)雙鏈表B29、對(duì)于兩個(gè)鏈表來(lái)說(shuō)，刪除第一種結(jié)點(diǎn)的操作，其時(shí)間復(fù)雜度都是O(1)|對(duì)于兩個(gè)鏈表來(lái)說(shuō)，刪除最后一種結(jié)點(diǎn)的操作，其時(shí)間復(fù)雜度都是O(n)|循環(huán)鏈表要比非循環(huán)鏈表占用更多的內(nèi)存空間|h1和h2是不同類(lèi)型的變量B30、只有表頭指針的不帶表頭結(jié)點(diǎn)的循環(huán)單鏈表|只有表尾指針的不帶表頭結(jié)點(diǎn)的循環(huán)單鏈表|只有表尾指針的帶表頭結(jié)點(diǎn)的循環(huán)單鏈表|只有表頭指針的帶表頭結(jié)點(diǎn)的循環(huán)單鏈表A31、n|2n-1|2n|n-1A32、L==NULL|L->next==NULL|L->next==L|L!=NULLB33、O(1)|O(n)|O(n^2)|O(nlog2n)B34、刪除單鏈表中的第一種元素|刪除單鏈表中的最后一種元素|在單鏈表第一種元素前插入一種新元素|在單鏈表最后一種元素后插入一種新元素B35、q->prior=p;p->next=q;p->next->prior=q;q->next=p->next;|q->next=p->next;p->next->prior=q;p->next=q;q->prior=p;|p->next=q;q->prior=p;q->next=p->next;p->next->prior=q;|p->next->prior=q;q->next=p->next;q->prior=p;p->next=q;B36、p->prior=q;q->next=p;p->prior->next=q;q->prior=p->prior;|q->prior=p->prior;p->prior->next=q;q->next=p;p->prior=q->next;|q->next=p;p->next=q;q->prior->next=q;q->next=p;|p->prior->next=q;q->next=p;q->prior=p->prior;p->prior=q;D37、p->prior->nexxt=p->next;p->next->prior=p->prior;|p->prior=p->prior->prior;p->prior->prior=p;|p->next->prior=p;p->next=p->next->next;|p->next=p->prior->prior;p->prior=p->rprior->priorA38、p->next=p->next->next;p->next->next->prior=p;|p->next->prior=p;p->next=p->next->next;|p->next=p->next->next;p->next->prior=p;|p->next->next=p->next;p->next->pror=p;C39、p->next==NULL|p==NULL|p->next==L|p==LC40、L->==NULL|L->next->prior==NULL|L->prior==NULL|L->next==LD41、單鏈表|給出表頭指針的循環(huán)單鏈表|雙鏈表|帶頭結(jié)點(diǎn)的循環(huán)雙鏈表D42、只有尾結(jié)點(diǎn)指針沒(méi)有頭結(jié)點(diǎn)指針的循環(huán)單鏈表|只有尾結(jié)點(diǎn)指針沒(méi)有頭結(jié)點(diǎn)指針的非循環(huán)單鏈表|只有頭結(jié)點(diǎn)指針沒(méi)有尾結(jié)點(diǎn)指針的循環(huán)雙鏈表|現(xiàn)有頭結(jié)點(diǎn)指針也有尾結(jié)點(diǎn)指針的循環(huán)單鏈表C43、單鏈表|僅有頭結(jié)點(diǎn)的單循環(huán)鏈表|雙鏈表|僅有尾結(jié)點(diǎn)指針的單循環(huán)鏈表D44、對(duì)于兩個(gè)鏈表來(lái)說(shuō)，刪除第一種結(jié)點(diǎn)的操作，其時(shí)間復(fù)雜度都是O(1)|對(duì)于兩個(gè)鏈表來(lái)說(shuō)，刪除最后一種結(jié)點(diǎn)的操作，其時(shí)間復(fù)雜度都是O(n)|循環(huán)鏈表要比非循環(huán)鏈表占用更多的內(nèi)在空間|h1和h2是不同類(lèi)型的變量B45、只有首結(jié)點(diǎn)指針h的不帶頭結(jié)點(diǎn)的循環(huán)單鏈表|只有尾結(jié)點(diǎn)指針r的不帶頭結(jié)點(diǎn)的循環(huán)單鏈表|只有尾結(jié)點(diǎn)指針r的帶頭結(jié)點(diǎn)h的循環(huán)單鏈表|只有頭結(jié)點(diǎn)h的循環(huán)單鏈表A46、A|B|C|DD|A47、a|b|1|0A48、a|b|1|0C49、A、B、C、D|D、C、B、A|A、C、D、B|D、A、B、CD50、單鏈表|雙鏈表|單循環(huán)鏈表|次序表D51、可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)|插入刪除不需要移動(dòng)元素|不必事先預(yù)計(jì)存儲(chǔ)空間|所需空間與其長(zhǎng)度成正比A52、n-i|n-i+1|n-i-1|IB53、n-1|n-i+1|n-i-1|IA54、n|n/2|(n+1)/2|(n-1)/2C57、p=q->next;p->next=q->next;|p=q->next;q->next=p;|p=q->next;q-next=p->next;|q->next=q->next->next;q->next=q;C數(shù)據(jù)構(gòu)造復(fù)習(xí)題：線性表判斷題1、次序存儲(chǔ)的線性表能夠隨機(jī)存取。2、線性表中的元素能夠是多個(gè)各樣的，但同一線性表中的數(shù)據(jù)元素含有相似的特性，因此，是屬于同一數(shù)據(jù)對(duì)象。3、在單鏈表中，任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系，由于能夠從頭結(jié)點(diǎn)查找任何一種元素。4、在單鏈表中，要獲得某個(gè)元素，只要懂得該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)構(gòu)造。5、鏈表的每個(gè)結(jié)點(diǎn)中，都正好包含一種指針。6、線性表中每個(gè)元素都有一種直接前驅(qū)和直接后繼。7、線性表中全部元素的排列次序必須由小到大或由大到小。8、靜態(tài)鏈表的存儲(chǔ)空間在運(yùn)算中能夠變化大小。9、靜態(tài)鏈表現(xiàn)有次序存儲(chǔ)構(gòu)造的優(yōu)點(diǎn)，又有動(dòng)態(tài)鏈表的優(yōu)點(diǎn)。因此，它存取表中的第i個(gè)元素的時(shí)間與i無(wú)關(guān)。10、靜態(tài)鏈表中能容納元素個(gè)數(shù)的最大數(shù)在定義時(shí)就擬定了，后來(lái)不能增加。11、靜態(tài)鏈表與動(dòng)態(tài)鏈表的插入、刪除操作類(lèi)似，不需做元素的移動(dòng)。12、線性表的次序存儲(chǔ)構(gòu)造優(yōu)于鏈?zhǔn)酱鎯?chǔ)構(gòu)造。15、在雙鏈表中，能夠從任一結(jié)點(diǎn)開(kāi)始沿同一方向查找任何其它結(jié)點(diǎn)。數(shù)據(jù)構(gòu)造復(fù)習(xí)題答案：線性表判斷題1、True2、True3、False4、False5、False6、False7、False8、False9、False10、True11、True12、False15、False數(shù)據(jù)構(gòu)造復(fù)習(xí)題：線性表算法分析題1、己知一種次序表L,其中的元素按值非遞減有序排列,設(shè)計(jì)一種算法插入一種元素x后保持該次序表仍按遞減有序排列。規(guī)定算法的空間復(fù)雜度為O(1)。2、設(shè)計(jì)一種算法從次序表L中刪除全部值為X的元素。規(guī)定算法的空間復(fù)雜度為O(1)。3、從次序表L中刪除重復(fù)的元素,并使剩余元素間的對(duì)應(yīng)次序保持不變.規(guī)定本算法的空間復(fù)雜記度為O(1)。4、有一種單鏈表(不同結(jié)點(diǎn)的數(shù)據(jù)域值可能相似),其頭指針為head,設(shè)計(jì)一種算法計(jì)算數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)個(gè)數(shù)。5、己知線性表元素遞增有序,并以帶頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)構(gòu)造,設(shè)計(jì)一種高效算法,刪除表中全部值不不大于mink且不大于maxk的元素(若表中存在這樣的元素)。并分析所寫(xiě)算法的時(shí)間復(fù)雜度。6、設(shè)計(jì)一種在帶頭結(jié)點(diǎn)的單鏈表中刪除一種最小值結(jié)點(diǎn)的高效算法。7、有一種不帶頭結(jié)點(diǎn)的單鏈表L(最少有1人結(jié)點(diǎn)),其頭指針為head,設(shè)計(jì)一種算法將L逆置,即最后一種結(jié)點(diǎn)變成第一種結(jié)點(diǎn),原來(lái)倒數(shù)第二個(gè)結(jié)點(diǎn)變成第二個(gè)結(jié)點(diǎn),如此等等。8、用單鏈表表達(dá)集合,設(shè)計(jì)一種算法求兩個(gè)集合的差。規(guī)定不破壞原有的結(jié)點(diǎn)。9、用單鏈表表達(dá)集合,設(shè)計(jì)一種算法求兩個(gè)集合的并。規(guī)定不破壞原有的結(jié)點(diǎn)。10、設(shè)計(jì)一種算法,將一種頭結(jié)點(diǎn)指針為a的單鏈表A分解成兩個(gè)單鏈表A和B,其頭結(jié)點(diǎn)指針?lè)謩e為a和b,使得A鏈表中含有原鏈表A中序號(hào)為奇數(shù)的元素,而B(niǎo)鏈表中含有原鏈表A中序號(hào)為倒數(shù)的元素,且保持原來(lái)的相對(duì)次序。11、有一種單鏈表,其結(jié)點(diǎn)的元素值以遞增有序排列,設(shè)計(jì)一種算法刪除該單鏈表中多出的元素值相似的結(jié)點(diǎn)。12、己知兩個(gè)寄存整數(shù)的有序單鏈表(己按整數(shù)從小至大的次序排序),指針L1和L2分別指向這兩個(gè)單鏈表的頭結(jié)點(diǎn)。設(shè)計(jì)一種算法,將L1和L2合并成一種單鏈表,且新的鏈表仍按整數(shù)由小到大的次序排列,新的單鏈表的結(jié)點(diǎn)由L1和L2的結(jié)點(diǎn)構(gòu)成。規(guī)定合并后的單鏈表運(yùn)用原來(lái)單鏈表的存儲(chǔ)空間。13、設(shè)計(jì)一種算法,將線性表lb連接到la之后,規(guī)定其時(shí)間復(fù)雜度為O(1),占用的輔助空間盡量小。描述所用的構(gòu)造。14、設(shè)指針p指向雙鏈表中的結(jié)點(diǎn)X,指針f指向?qū)⒁迦氲男陆Y(jié)點(diǎn)Y,Y要插入在結(jié)點(diǎn)X之后,寫(xiě)出指針需要修改的有關(guān)環(huán)節(jié)。15、有一種循環(huán)雙鏈表,每個(gè)結(jié)點(diǎn)由兩個(gè)指針(prior和next)以及核心字(data)構(gòu)成,p指向其中某一結(jié)點(diǎn),設(shè)計(jì)一種算法從該循環(huán)雙鏈表中刪除p所指的結(jié)點(diǎn)。16、設(shè)有一種循環(huán)雙鏈表,其中有一結(jié)點(diǎn)的指針為p,設(shè)計(jì)一種算法將p與其后續(xù)結(jié)點(diǎn)進(jìn)行交換。19、設(shè)A和B是兩個(gè)單鏈表(帶頭結(jié)點(diǎn))，其表中元素遞增有序。設(shè)計(jì)一種算法將A和B歸并成一種按元素值遞增有序的單鏈表C，規(guī)定輔助空晨為O(1)，并分析算法的時(shí)間復(fù)雜度。數(shù)據(jù)構(gòu)造復(fù)習(xí)題答案：線性表算法分析題1、答：voidinsert(sqlist&L,ElemTypex){inti=0,j;while(i<L.Length&&L.data[i]<x)i++:for(j=L.Length-1;j>=i;j--)L.data[j+1]=L.data[j];L.data[i]=x;L.Length++;}2、voiddelnode(SqList&A,ElemTypeitem){intk=0,i=0;while(i<A.length){if(A.data[i]==item)k++;elseA.data[i-k]=A.data[i];i++;}A.length=A.length-k}3、4、intListlant(Salist&L,ElemTypee){/*帶有頭結(jié)點(diǎn)*/p=head;intn=0;while(p!=NULL){if(p->next->data==x)n++;p=p-.next;}returnn;}5、voidDelnodes(LinkList*&L,ElemTypemink,ElemTypemaxk){LinkList*p=head->next;While(p!=null&&p->data<mink)//*r為*p的前驅(qū)結(jié)點(diǎn){r=p;p=p->next;}q=p;//求值域剛好>minwhile(q!=null&&q->data>maxk)//求值域剛好<maxq=q->next;r->next=q->next;while(r!=q){r=p->next;free(p);p=r;}free(q);}6、voidDels(LinkList*&head){p=head,q=head->next;while(q->next!=null){if(p->next->data>q->next->data)p=q;q=q->next;}p->next=p->next->next;}7、voidReverse(LinkList*&head){p=head;q=p->next;//q指向p的后繼結(jié)點(diǎn)，僅為目前結(jié)點(diǎn)if(q=null)return(p);//僅有一種結(jié)點(diǎn)p->next=null;//原鏈表的首結(jié)點(diǎn)位新鏈表的尾結(jié)點(diǎn)if(q->next==null)//僅有兩個(gè)結(jié)點(diǎn){q->next=p;return(q);}r=q->next;while(r->next!=null){q->next=p;//實(shí)現(xiàn)逆置p=q;q=r;r=r->next;}q->next=p;return(r);}8、TypedefElemtypeint;TypedefstructLnode{Elemtypedata;StructLNode*next;}Lnode,*LinkList;#include<stdio.h>LinkListcreatlist(){//建立單鏈表LinkListhead,r,s;ElemTypex;head=(LinkList)malloc(sizeof(LNode));//建立單鏈表頭結(jié)點(diǎn)r=head;printf(“輸入系列整數(shù)，0標(biāo)志結(jié)束\n”);scanf(“&d”,&x);while(x){//x=0則退出while循環(huán)s=(LinkList)mslloc(sizeof(LNode));s->data=x;r->next=s;r=s;scanf(“%d”,&x);)//whiler->next=NULL;s=head;//刪除頭結(jié)點(diǎn)head=head->next;free(s);return(head);}statusListFind(LinkListL,Elemtypee){//查找元素eLinkListp;p=L;while(p&&p->data!=e)p=p->next;If(p)returnFALSE;elsereturnTRUE;}voidLis9、TypedefElemtypeint;TypedefstructLnode{Elemtypedata;StructLNode*next;}Lnode,*LinkList;voidMergeList(LinkListHa,LinkListHb,LinkList&Hc){LinkListp,q,r,s;Hc=(LinkList)malloc(sizeof(Lnode));r=Hc;p=Ha;q=Hb;while(p&&q){s=(LinkList)malloc(sizeof(Lnode));r->next=s;r=s;if(p->data<q->data){s->data=p->data;p=p->next;}elseif(p->data<q->data){s->data=q->data;q=q->next;}else{s->data=p->data;p=p->next;q=q->next;}}while(q)//把Q及之后的結(jié)點(diǎn)復(fù)制到Hc{s=(LinkList)malloc(sizeof(Lnode));s->data=q->data;r->next=s;r=s;q=q->next;}while(p)//把P后的結(jié)點(diǎn)復(fù)制到Hc{s=(LinkList)malloc(sizeof(Lnode));s->data=p->data;r->next=s;r=s;p=p->next;}r->next=NULL;s=Hc;Hc=Hc->next;free(s);//刪除頭結(jié)點(diǎn)}10、Voidpartition(LinkList&a,LinkList&b){LinkListr,p,q;p=a->next;b=(LinkList)malloc(sizeof(Lnode));q=b;While(p->next){r=p->next;p->next=r->next;r->next=NULL;q-next=r;q=q->next;p=p->next;}}11、//p掃描單鏈表。*p的值域=其后結(jié)點(diǎn)的值域，刪除后者voidDels(LinkList*&head){LinkList*p=head->next;while(p->next!=null){if(p->data==p->next->data)/改重復(fù)值的結(jié)點(diǎn){q=p->next;/q指向返回重復(fù)結(jié)點(diǎn)p->next=q->next;free(q);}elsep=p->next;}}12、voidMergelistL(LinkList&L1,LinkList&L2){LinkList*p,*q,*r,*u,*c;p=L1->next;q=L2->next;c=L1/c為合并后新鏈表的表頭指針r=L1while(p!=Null)&&(q!=Null)Swich{casep->data>q->data;/*是L2表中小者加入C表尾部{u=q->next;/*u為暫存指針，避免鏈斷r->next=q;r=q;q->next=p;q=u;}casep->data<=q->data/*將A表中小者加入到C表尾部{r=p;p=p->next;}}if(q!=Null)/如果A表已空時(shí)將B表為結(jié)束部分鏈接結(jié)束部分->cb表尾部r->next=q;return(c);}13、typedefstructslnode{Elemtypedata;structslnode*next;}slnodetype;slnodetype*p,*q,*s;voidmerge(slnodetype*la,slnodetype*lb){slnodetype*p;p=lb->next;Lb->next=la->next;la->next=p->next;free(p);}14、statasInsertDubList(DuLinkList&L,inte){malloc(f);f->data=Y;if(p->next==null){p->next=f;f->prior=p;}else{f->prior=p;p->next->prior=f;f->next=p->next;p->next=f;}}15、Statasdelete(cirLinkList&L){If(L=null)Error(‘nodata’);If(p→next=L){L→next=L;L→prior=L.Free(p);}Else{p→prior→next=→next;p→next→prior=→prior;free(p);}}16、stataschange(CirLinkList&L){If(L=null)error(‘nodata’);elseIf(p->next==null)error(‘can’tchange’)else{q=p->next;p->prior->next=q;q->prior=p->prior;p->n