數(shù)據(jù)結(jié)構(gòu)試題

1、1 緒論 沈陽(yáng)理工大學(xué)應(yīng)用技術(shù)學(xué)院 信息與控制學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)教研室 2011-5-8 -1- 數(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、在以下的敘述中，正

2、確的是_。 線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)|二維數(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ù)元素的類(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ù)雜

3、度是指最壞情況下，估計(jì)算法執(zhí)行時(shí)間的一個(gè)上界 (4) 同一個(gè)算法，實(shí)現(xiàn)語(yǔ)句的級(jí)別越高，執(zhí)行效率越低 (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)的類(lèi)型要一致|每個(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ù)項(xiàng)是數(shù)據(jù)的最小單元, 數(shù)據(jù)元素是數(shù)據(jù)的基本單位. 數(shù)據(jù)項(xiàng)|數(shù)據(jù)

4、元素|信息項(xiàng)|表元素 12、數(shù)據(jù)結(jié)構(gòu)是指_數(shù)據(jù)元素_以及它們之間的_結(jié)構(gòu)_. (1)數(shù)據(jù)元素 (2)結(jié)構(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)部具有某種結(jié)構(gòu)|數(shù)據(jù)項(xiàng)和數(shù)據(jù)項(xiàng)之 間存在某種關(guān)系 14、數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為_(kāi)兩類(lè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ù)類(lèi)型之間|存儲(chǔ)結(jié)構(gòu)之間 16、在存

5、儲(chǔ)數(shù)據(jù)時(shí),通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值,而且還要存儲(chǔ)_. -2- 數(shù)據(jù)的處理方法|數(shù)據(jù)元素的類(lèi)型|數(shù)據(jù)元素之間的關(guān)系|數(shù)據(jù)的存儲(chǔ)方法 17、在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)中,一個(gè)存儲(chǔ)結(jié)點(diǎn)存儲(chǔ)一個(gè)_. 數(shù)據(jù)項(xiàng)|數(shù)據(jù)元素|數(shù)據(jù)結(jié)構(gòu)|數(shù)據(jù)類(lèi)型 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ù)域是指針類(lèi)型| 每個(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)

6、定義的|有算術(shù)運(yùn)算和關(guān)系運(yùn)算兩大類(lèi)|必須用程序設(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)成|數(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ō)法正確的是_. 算法最終必須由

7、程序?qū)崿F(xiàn)|算法的有窮性是對(duì)于任意的一組輸入值必須在有窮步驟后結(jié)束|算法的可行性是 指指令不能有二義性|以上幾個(gè)都是錯(cuò)誤的 26、算法的時(shí)間復(fù)雜度與_有關(guān) 問(wèn)題規(guī)模|計(jì)算機(jī)硬件性能|編譯程序質(zhì)量|程序設(shè)計(jì)語(yǔ)言 27、算法分析的主要任務(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)系|分析算法的效率以

8、求改進(jìn)|分析算法的易讀性和文檔性 30、線性表是具有 n 個(gè)_的有限序列。 表元素|字符|數(shù)據(jù)元素|數(shù)據(jù)項(xiàng) 31、線性表是_。 一個(gè)有限序列，可以為空|一個(gè)有限序列，不可以為空|一個(gè)無(wú)限序列，可以為空|一個(gè)無(wú)限序列，不可以為 空 32、線性表采用鏈表存儲(chǔ)時(shí)，其地址_。 必須是連續(xù)的|一定是不連續(xù)的|部分地址必須是連續(xù)的|連續(xù)與否均可以 33、鏈表不具備的特點(diǎn)是_。 可隨機(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ǔ)器空間 -3-

9、 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)行插入和刪除，又要求存儲(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

10、-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)單|可以進(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

11、(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、數(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ù)是由一些類(lèi)型相同的數(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)相同的數(shù)據(jù),結(jié)點(diǎn)類(lèi)型也一定相同

12、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)。F 19、健壯的算法不會(huì)因非法入輸數(shù)據(jù)而出現(xiàn)莫名其妙的執(zhí)行結(jié)果。 -4- 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：緒論 算法分析題 1、求兩個(gè) n 階矩形的乘法 C=A*B,其算法如下: #define MAX 100 void maxtrixmult(int ,float aMAX

13、MAX,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 是偶數(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

14、,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ù); -5- / / / / / / (3) 分析該算法的時(shí)間復(fù)雜度; (4) 假定 n=5, 試指出執(zhí)行該算法的輸出結(jié)果。 6、設(shè) n 是偶數(shù),試計(jì)算運(yùn)行下列程序段后 m 的值并給出該程序段的時(shí)間復(fù)雜度。 int m=0,i,j; f

15、or (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、一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中_映像_稱為存儲(chǔ)結(jié)構(gòu)。 2、數(shù)據(jù)邏輯結(jié)構(gòu)包括 、 和 三種類(lèi)型，樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為_(kāi)。 3、在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)_前驅(qū)結(jié)點(diǎn)，其余每個(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è)

16、_。 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ì)算機(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)

17、_。 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; -6- while(i<=n) i=i*3; 14、有如下遞歸函數(shù) fact(n),分析其時(shí)間復(fù)雜度。 int fact(int n) if (n<=1) return 1; else return (n*fact(n-1); 15、指出下列各算法的時(shí)間復(fù)雜度 (1) prime(int n) in

18、t 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; sum+=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; s

19、um+=p; return (sum); 16、數(shù)據(jù)的邏輯結(jié)構(gòu)是指_. -7- 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)的_算法_,從而確保經(jīng)過(guò)這些運(yùn)算后所得到的新結(jié)構(gòu)是原來(lái)的結(jié)構(gòu)類(lèi)型. 20、一個(gè)算法具有 5 個(gè)特性:_、_、_、輸入和輸出。 21、算法的執(zhí)行時(shí)間是_的函數(shù)。 22、數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯上描述數(shù)據(jù),

20、它與數(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ù)類(lèi)型包括_數(shù)據(jù)_和_操作_兩個(gè)部分。 27、 從一維數(shù)組 an中順序查找出一個(gè)最大值元素的時(shí)間復(fù)雜度為_(kāi)， 輸出一個(gè)二維數(shù)組 bmn 中所有元素值的時(shí)間復(fù)雜度為_(kāi) 28、在下面程序段中，s=s+p 語(yǔ)句的執(zhí)行次數(shù)為_(kāi)n_，p*=j 語(yǔ)句的執(zhí)行次數(shù)為 _n*(n+1)/2_，該程序段的時(shí)間復(fù)雜度為_(kāi)O(n*n)_。 i

21、nt 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的概率為 1/3，查找第 2 個(gè)元素 a1的概率 為 1/4，其找其余元素的概率均相同，則在查找成功時(shí)同元素的平均比較次數(shù)為_(kāi)35/

22、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ǔ)字地址是_。 37、在線性表的單鏈接存儲(chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)包含有兩個(gè)域，一個(gè)叫_，另一個(gè)

23、叫_ 域。 數(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)算的定義不同,因而兩個(gè)結(jié)構(gòu)具有顯著不同的特性,則這兩個(gè)數(shù)據(jù)結(jié)構(gòu)是不同的. -8- 數(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ù)的邏輯

24、結(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 線性表 沈陽(yáng)理工大學(xué)應(yīng)用技術(shù)學(xué)院 信息與控制學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)教研室 2011-5-8 -9- - 10 - 數(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í)，

25、在查找成功的情況下，需平均比較_(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è)單鏈表中指針 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、在雙

26、向鏈表存儲(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=L_。 16、非空的循環(huán)單鏈表 head 的尾結(jié)點(diǎn)(由 p 所指向)滿足_。 17、在循環(huán)雙鏈表的 p 所指結(jié)點(diǎn)之前插入 s 所指結(jié)點(diǎn)的操作是_。 18、若某表最常用

27、的操作是在最后一個(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)并仍然保持有序的時(shí)間復(fù)雜度是_。 23、在一個(gè)長(zhǎng)度為 n(n>1)的單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行_刪除單鏈表中的最后

28、一個(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)算只有兩種，即刪除第一個(gè)元素，在最后一個(gè)元素的后面插入新元素，則最好使用 _。 29、設(shè)有兩個(gè)長(zhǎng)度為

29、n 的單鏈表，結(jié)點(diǎn)類(lèi)型相同。若以 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_。 - 11 - 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 結(jié)

30、點(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è)元 素前面插入新元素；

31、在最后一個(gè)元素的后面插入新元素，則最好使用_只有頭結(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)類(lèi)型相同，若以 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ò)以下

32、棧運(yùn)算后，X 的值是_。 InitStack(s);Push(s,a);Push(s,b);Pop(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

33、)位置插入一個(gè)新元素時(shí)，需要從后向 前依次后移_個(gè)元素 53、 在一個(gè)長(zhǎng)度為 n 的順序存儲(chǔ)的線性表中， 刪除第 i 個(gè)元素(1<=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、順序存儲(chǔ)的線性表可以隨機(jī)存取。 2、線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性， 因此，是屬于同

34、一數(shù) 據(jù)對(duì)象。T 3、在單鏈表中，任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系，因?yàn)榭梢詮念^結(jié)點(diǎn)查找任何一個(gè)元素。 - 12 - 4、在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。 5、鏈表的每個(gè)結(jié)點(diǎn)中，都恰好包含一個(gè)指針。 6、線性表中每個(gè)元素都有一個(gè)直接前驅(qū)和直接后繼。 7、線性表中所有元素的排列順序必須由小到大或由大到小。 8、靜態(tài)鏈表的存儲(chǔ)空間在運(yùn)算中可以改變大小。 9、靜態(tài)鏈表既有順序存儲(chǔ)結(jié)構(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í)就確定了，以后不能增加。 1

35、1、靜態(tài)鏈表與動(dòng)態(tài)鏈表的插入、刪除操作類(lèi)似，不需做元素的移動(dòng)。 12、線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 15、在雙鏈表中，可以從任一結(jié)點(diǎn)開(kāi)始沿同一方向查找任何其他結(jié)點(diǎn)。F 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：線性表 算法分析題 1、己知一個(gè)順序表 L,其中的元素按值非遞減有序排列,設(shè)計(jì)一個(gè)算法插入一個(gè)元素 x 后保持該順序表仍按遞 減有序排列。要求算法的空間復(fù)雜度為 O(1)。 2、設(shè)計(jì)一個(gè)算法從順序表 L 中刪除所有值為 X 的元素。要求算法的空間復(fù)雜度為 O(1)。 3、從順序表 L 中刪除重復(fù)的元素,并使剩余元素間的相應(yīng)次序保持不變.要求本算法的空間復(fù)雜記度為 O(1)。 4、 有一個(gè)單鏈表(不同結(jié)點(diǎn)

36、的數(shù)據(jù)域值可能相同),其頭指針為 head,設(shè)計(jì)一個(gè)算法計(jì)算數(shù)據(jù)域?yàn)?x 的結(jié)點(diǎn)個(gè)數(shù)。 5、己知線性表元素遞增有序,并以帶頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)結(jié)構(gòu),設(shè)計(jì)一個(gè)高效算法,刪除表中所有值大于 mink 且小于 maxk 的元素(若表中存在這樣的元素)。并分析所寫(xiě)算法的時(shí)間復(fù)雜度。 6、設(shè)計(jì)一個(gè)在帶頭結(jié)點(diǎn)的單鏈表中刪除一個(gè)最小值結(jié)點(diǎn)的高效算法。 7、有一個(gè)不帶頭結(jié)點(diǎn)的單鏈表 L(至少有 1 人結(jié)點(diǎn)),其頭指針為 head,設(shè)計(jì)一個(gè)算法將 L 逆置,即最后一個(gè)結(jié)點(diǎn) 變成第一個(gè)結(jié)點(diǎn),原來(lái)倒數(shù)第二個(gè)結(jié)點(diǎn)變成第二個(gè)結(jié)點(diǎn),如此等等。 8、用單鏈表表示集合,設(shè)計(jì)一個(gè)算法求兩個(gè)集合的差。要求不破壞原有的結(jié)點(diǎn)。 9、

37、用單鏈表表示集合,設(shè)計(jì)一個(gè)算法求兩個(gè)集合的并。要求不破壞原有的結(jié)點(diǎn)。 10、設(shè)計(jì)一個(gè)算法,將一個(gè)頭結(jié)點(diǎn)指針為 a 的單鏈表 A 分解成兩個(gè)單鏈表 A 和 B,其頭結(jié)點(diǎn)指針?lè)謩e為 a 和 b, 使得 A 鏈表中含有原鏈表 A 中序號(hào)為奇數(shù)的元素,而 B 鏈表中含有原鏈表 A 中序號(hào)為倒數(shù)的元素,且保持原來(lái) 的相對(duì)順序。 11、 有一個(gè)單鏈表,其結(jié)點(diǎn)的元素值以遞增有序排列,設(shè)計(jì)一個(gè)算法刪除該單鏈表中多余的元素值相同的結(jié)點(diǎn)。 12、己知兩個(gè)存放整數(shù)的有序單鏈表(己按整數(shù)從小至大的順序排序),指針 L1 和 L2 分別指向這兩個(gè)單鏈表的 頭結(jié)點(diǎn)。設(shè)計(jì)一個(gè)算法,將 L1 和 L2 合并成一個(gè)單鏈表,且新

38、的鏈表仍按整數(shù)由小到大的順序排列,新的單鏈表 的結(jié)點(diǎn)由 L1 和 L2 的結(jié)點(diǎn)構(gòu)成。要求合并后的單鏈表利用原來(lái)單鏈表的存儲(chǔ)空間。 13、設(shè)計(jì)一個(gè)算法,將線性表 lb 連接到 la 之后,要求其時(shí)間復(fù)雜度為 O(1),占用的輔助空間盡量小。描述所用 的結(jié)構(gòu)。 14、設(shè)指針 p 指向雙鏈表中的結(jié)點(diǎn) X,指針 f 指向?qū)⒁迦氲男陆Y(jié)點(diǎn) Y,Y 要插入在結(jié)點(diǎn) X 之后,寫(xiě)出指針需要修 改的有關(guān)步驟。 15、有一個(gè)循環(huán)雙鏈表,每個(gè)結(jié)點(diǎn)由兩個(gè)指針(prior 和 next)以及關(guān)鍵字(data)構(gòu)成,p 指向其中某一結(jié)點(diǎn),設(shè)計(jì)一 個(gè)算法從該循環(huán)雙鏈表中刪除 p 所指的結(jié)點(diǎn)。 16、設(shè)有一個(gè)循環(huán)雙鏈表,其中

39、有一結(jié)點(diǎn)的指針為 p,設(shè)計(jì)一個(gè)算法將 p 與其后續(xù)結(jié)點(diǎn)進(jìn)行交換。 19、設(shè) A 和 B 是兩個(gè)單鏈表(帶頭結(jié)點(diǎn))，其表中元素遞增有序。設(shè)計(jì)一個(gè)算法將 A 和 B 歸并成一個(gè)按元素值 遞增有序的單鏈表 C，要求輔助空晨為 O(1)，并分析算法的時(shí)間復(fù)雜度。 - 13 - 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：線性表 填空題 1、在線性結(jié)構(gòu)中第一結(jié)點(diǎn)_前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有_個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)_ 后繼結(jié)點(diǎn)。 2、對(duì)于順序存儲(chǔ)的線性表，當(dāng)隨機(jī)插入或刪除一個(gè)元素時(shí)，約需平均移動(dòng)表長(zhǎng)_的元素。 3、對(duì)于長(zhǎng)度為 n 的順序表，插入或刪除元素的時(shí)間復(fù)雜性為_(kāi)；對(duì)于順序?；蜿?duì)列，插入或刪除元 素的時(shí)間復(fù)雜性為_(kāi)。 4

40、、在線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)_相鄰位置_決定的；在線性表的鏈接存儲(chǔ) 中，元素之間的邏輯關(guān)系是通過(guò)_連接指針_決定的。 5、一個(gè)單鏈表中刪除*p 結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行如下操作: (1)q=p->next; (2)p->data=p->next->data; (3)p->next=_; (4)free(q); 6、對(duì)于線性表的順序存儲(chǔ)，需要預(yù)先分配好存儲(chǔ)空間，若分配太多則容易造成存儲(chǔ)空間的_，若 分配太少又容易在算法中造成_溢出_，因此適應(yīng)于數(shù)據(jù)量變化不大的情況；對(duì)于線性表的鏈接存儲(chǔ) (假定采用動(dòng)態(tài)結(jié)點(diǎn))，不需要_存儲(chǔ)空間，存儲(chǔ)器中的整個(gè)_動(dòng)態(tài)存儲(chǔ)區(qū)_都

41、可供使用，分 配和回收結(jié)點(diǎn)都非常方便，能夠有效地利用存儲(chǔ)空間，在算法中不必考慮_溢出_的發(fā)生，因此適應(yīng) 數(shù)據(jù)量變化較大的情況。 7、從順序表中刪除第 i 個(gè)元素時(shí)，首先把第 i 個(gè)元素賦給_變參或函數(shù)名_帶回，接著從_連接 指針_開(kāi)始向后的所有元素均_一個(gè)位置，最后使線性表的長(zhǎng)度_。 8、向一個(gè)長(zhǎng)度為 n 的順序表中的第 i 個(gè)元素(0<=i<=n-1)之前插入一個(gè)元素時(shí)，需向后移動(dòng)_個(gè)元素。 9、在一個(gè)長(zhǎng)度為 n 的順序表刪除第 i 個(gè)元素(0<=i<=n-1)時(shí)，需向前移動(dòng)_個(gè)元素。 10、在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是_簡(jiǎn)化插入、刪除算法_。 11、在單鏈表中，要?jiǎng)h

42、除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的_結(jié)點(diǎn)。 12、訪問(wèn)單鏈表中的結(jié)點(diǎn)，必須沿著_指針鏈_依次進(jìn)行。 13、在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向_，另一個(gè)指向_。 14、在_循環(huán)雙_鏈表上，刪除最后一個(gè)結(jié)點(diǎn)，其算法的時(shí)間復(fù)雜度為 O(1)。 15、在一個(gè)單鏈表中的 p 所指結(jié)點(diǎn)之前插入一個(gè) s 所指結(jié)點(diǎn)時(shí)，可執(zhí)行如下操作。 (1)s->next=_。 (2)p->next=s; (3)t=p->data; (4)p->data=_。 (5)s-.data=_。 16、在一個(gè)單鏈表中刪除 p 所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作： q=p->next; p_data=p-

43、>next->data; p->next=_; free(q); 17、在一個(gè)單鏈表中 p 所指結(jié)點(diǎn)之后插入一個(gè) s 所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行 s->next=_和 p->next=_ 的操作。 18、對(duì)于一個(gè)具有 n 個(gè)結(jié)點(diǎn)的單鏈表，在*p 結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是_O(1)_；在給定值 - 14 - 為 x 的結(jié)點(diǎn)后插入一后新結(jié)點(diǎn)的時(shí)間復(fù)雜度是_。 19、在線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)_物理存儲(chǔ)位置_決定的；在線性表的鏈?zhǔn)酱鎯?chǔ) 中，元素之間的邏輯關(guān)系是通過(guò)_鏈域的指針值_決定的。 20、在一個(gè)長(zhǎng)度為 n 的順序表中刪除第 i 個(gè)元素(1&l

44、t;=i<=n)時(shí)，需向前移動(dòng)_個(gè)元素。 21、為了設(shè)置一個(gè)空的順序表 L，采用的操作是_L->length=0_。 22、刪除順序表的_元素，不需要移動(dòng)任何元素。 23、刪除順序表的_最后一個(gè)_元素，不需要移動(dòng)的元素最多。 24、在順序表_元素后面插入一個(gè)元素，不需要移動(dòng)任何元素。 25、插入順序表的_元素，需要移動(dòng)的元素最多。 26、在長(zhǎng)度為 n 的順序表 L 中查找指定元素值的元素，其時(shí)間復(fù)雜度為_(kāi)。 27、求單鏈表長(zhǎng)度的時(shí)間復(fù)雜度為_(kāi)。 28、刪除單鏈表 L 中某結(jié)點(diǎn)*p 之后的一個(gè)結(jié)點(diǎn)，其時(shí)間復(fù)雜度為_(kāi)。 29、刪除單鏈表 L 中某結(jié)點(diǎn)*p 之前的一個(gè)結(jié)點(diǎn)，其時(shí)間復(fù)雜度為

45、_O(n)_。 30、在一個(gè)單鏈表(己知每個(gè)結(jié)點(diǎn)含有數(shù)據(jù)域 data 和指針域 next)中刪除 p 所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作： (1)q=p->next; (2)p->data=q->data; (3)p->next = _; (4)free(q); 31、在一個(gè)單鏈表中的 p 所指結(jié)點(diǎn)之后插入*s 結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行 s->next=_和 p->next=_的操作。 32、對(duì)于一個(gè)具有 n 個(gè)結(jié)點(diǎn)的單鏈表，在*p 結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是_;在給定值為 x 的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是_。 33、刪除雙鏈表 L 中某結(jié)點(diǎn)*p 之后的一個(gè)結(jié)

46、點(diǎn)，其時(shí)間復(fù)雜度為_(kāi)。 34、刪除雙鏈表 L 中某結(jié)點(diǎn)*p 之前的一個(gè)結(jié)點(diǎn)，其時(shí)間復(fù)雜度為_(kāi)。 35、在非循環(huán)的_鏈表中，可以用表尾指針代替表頭指針。 36、對(duì)于雙鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需要修改的指針共_。 37、在一個(gè)雙鏈表中，若要在*p 結(jié)點(diǎn)之前插入結(jié)點(diǎn)*q，則執(zhí)行的操作是_。 38、循環(huán)單鏈表 L 為空的條件是_。 39、 在單鏈表中,結(jié)點(diǎn)與結(jié)點(diǎn)之間的邏輯關(guān)系不是通過(guò)存儲(chǔ)單元的順序來(lái)表示的,而是通過(guò)_指向下一個(gè)結(jié)點(diǎn) 的指針_來(lái)實(shí)現(xiàn)的. 40、對(duì)于一個(gè)長(zhǎng)度為 n 的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_(kāi)，在表尾插入元 素的時(shí)間復(fù)雜度為_(kāi)。 41、對(duì)于一個(gè)單鏈接存儲(chǔ)的線

47、性表，在表頭插入結(jié)點(diǎn)的時(shí)間復(fù)雜度為_(kāi)，在表尾插入元素的時(shí)間 復(fù)雜度為_(kāi)。 42、在線性表的順序存儲(chǔ)中，若一個(gè)元素的下標(biāo)為 i，則它的前驅(qū)元素的下標(biāo)為_(kāi)，后繼元素的 下標(biāo)為_(kāi)。 43、在線性表的單鏈接存儲(chǔ)中，若一個(gè)元素所在結(jié)點(diǎn)的地址為 p，則其后繼結(jié)點(diǎn)的地址為 _p->next_，若 p 為一個(gè)數(shù)組 a 中的下標(biāo)，則其后繼結(jié)點(diǎn)的下標(biāo)的_ap->next_。 44、在循環(huán)單鏈表中，最后一個(gè)結(jié)點(diǎn)的指針域指向_結(jié)點(diǎn)。 45、在雙向鏈表中每個(gè)結(jié)點(diǎn)包含有兩個(gè)指針域，一個(gè)指向其_結(jié)點(diǎn)，另一個(gè)指向其_ 結(jié)點(diǎn)。 46、在循環(huán)雙向鏈表中表頭結(jié)點(diǎn)的左指針域指向_結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的右指針域指向 _結(jié)點(diǎn)。

48、 47、在以為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為_(kāi) 和_。 - 15 - 50、在由數(shù)組 a 中元素結(jié)點(diǎn)構(gòu)成的單鏈表中，在下標(biāo)為 i 的結(jié)點(diǎn)的后面插入一個(gè)下標(biāo)為 j 的結(jié)點(diǎn)時(shí)，需要進(jìn) 行的操作為_(kāi)和_語(yǔ)句。 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題：線性表 問(wèn)答題 1、線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。試問(wèn)： (1)兩種存儲(chǔ)表示各有哪些主要優(yōu)缺點(diǎn)? (2)如果有 n 個(gè)線性表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化，線性表的總數(shù)也會(huì)自 動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)?為什么? (3)若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表

49、中的元素，那 么，應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)?為什么? 解答：(1)順序存儲(chǔ)是按索引（隱含的）直接存取數(shù)據(jù)元素，方便靈活，效率高，但插入、刪除操作時(shí)將引起 元素移動(dòng)，因而降低效率；鏈接存儲(chǔ)內(nèi)存采用動(dòng)態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間有序關(guān)系的指針 域，存取數(shù)據(jù)元素不如順序存儲(chǔ)方便，但結(jié)點(diǎn)的插入、刪除操作十分簡(jiǎn)單。 (2)應(yīng)選用鏈接表存儲(chǔ)結(jié)構(gòu)。 其理由是， 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用一組任意的存儲(chǔ)單元依次存儲(chǔ)線性表里各元素， 這里存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。這種存儲(chǔ)結(jié)構(gòu)，在對(duì)元素作插入或刪除運(yùn)算時(shí)，不需要移 動(dòng)元素，僅修改指針即可。所以很容易實(shí)現(xiàn)表的容量擴(kuò)充。 (3)應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。其理由是，每

50、個(gè)數(shù)據(jù)元素的存儲(chǔ)位置和線性表的起始位置相差一個(gè)和數(shù)據(jù)元 素在線性表中的序號(hào)成正比的常數(shù)。由此，只要確定了起始位置，線性表中任一數(shù)據(jù)元素都可隨機(jī)存取，所 以線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。而鏈表則是一種順序存取的存儲(chǔ)結(jié)構(gòu)。 2、用線性表的順序結(jié)構(gòu)來(lái)描述一個(gè)城市的設(shè)計(jì)和規(guī)劃合適嗎?為什么? 不合適。因?yàn)橐粋€(gè)城市的設(shè)計(jì)和規(guī)劃涉及非常多的項(xiàng)目，很復(fù)雜，經(jīng)常需要修改、 擴(kuò)充和刪除各種信息， 才能適應(yīng)不斷發(fā)展的需要。有鑒于此，順序線性表不能很好適應(yīng)其需要，故是不合適的。 3、在單鏈表和雙向表中，能否從當(dāng)前結(jié)點(diǎn)出發(fā)訪問(wèn)到任一結(jié)點(diǎn)? 在單鏈表中只能由當(dāng)前結(jié)點(diǎn)訪問(wèn)其后的任一結(jié)點(diǎn)，因?yàn)闆](méi)有指向其前驅(qū)

51、結(jié)點(diǎn)的指針。而在雙向鏈表中， 既有指向后繼結(jié)點(diǎn)的指針又有指向前驅(qū)結(jié)點(diǎn)的指針，故可由當(dāng)前結(jié)點(diǎn)出發(fā)訪問(wèn)鏈表中任一結(jié)點(diǎn)。 4、編寫(xiě)下列算法 (1)向類(lèi)型有 list 的線性表 L 的第 i 個(gè)元素（0iL.len）之后插入一個(gè)新元素 x。 (2)從類(lèi)型為 list 的線性表 L 中刪除其值等于 x 的所有元素。 (3)將兩個(gè)有序表 A 和 B 合并成一個(gè)有序表 C，其中 A，B，C 均為 list 類(lèi)型的變參。 (1) 解答: status insert(SqList L,int i,ElemType x) / 向線性表 L 中第 i 個(gè)元素之后插入值為 x 的新元素 (1) if (L.len =

52、 =m0) error('overflow'); (2) if (i<0) | (i>L.len) error ('out of range'); (3) for (j=L.len ;j>= i1;-j ) L.vecj1L.vecj; (4) L.veci1x; (5) L.lenlen1; (2) 解答: status delete(L,x) / 從線性表 L 中刪除其值等于 x 的所有元素 i1; while (i<L.len ) if (L.veci= =x ) - 16 - () for( ji1 ;j<= L.len ;

53、+j) L.vec 5、編寫(xiě)下列算法，假定單鏈表的表頭指針用 HL 表示，類(lèi)型為 linklist。 (1)將一個(gè)單鏈表中的所有結(jié)點(diǎn)按相反次序鏈接。 (2)刪除單鏈表中第 i 個(gè)（i1）結(jié)點(diǎn)。 (3)刪除單鏈表中由指針 p 所指向的結(jié)點(diǎn)。 (4)從帶有附加表頭結(jié)點(diǎn)的循環(huán)單鏈表中刪除其值等于 x 的第一個(gè)結(jié)點(diǎn)。 (5)在單鏈表中指針 p 所指結(jié)點(diǎn)之前插入一個(gè)值為 x 的新結(jié)點(diǎn)。 (6)從循環(huán)單鏈表中查找出最小值。 (7)根據(jù)一維數(shù)組 A(1:n)中順序存儲(chǔ)的具有 n 個(gè)元素的線性表建立一個(gè)帶有附加表頭結(jié) 點(diǎn)的單鏈表。 解答：(1)將一個(gè)單鏈表中的所有結(jié)點(diǎn)按相反次序鏈接。 (1) 解答: stat

54、us contrary(HL) / 使 HL 單鏈表中的所有結(jié)點(diǎn)按相反次序鏈接 pHL ; /p 指向未被逆序的第一個(gè)結(jié)點(diǎn)，初始指向原表頭結(jié)點(diǎn) HLnil; /HL 指向逆序后的表頭結(jié)點(diǎn)，初始值為空 while (p!=nil ) (1) qp; /q 指向?qū)⒈荒嫘蜴溄拥慕Y(jié)點(diǎn) (2) pp.next; (3) q.nextHL; (4) HLq; (2)刪除單鏈表中第 i 個(gè)（i1）結(jié)點(diǎn)。 (2) 解答:status delete(HL,i) (1) if (i<0) or (HLnil) error('not h&&le'); (2) if (i1 )

55、HLHL->next; return ; (3) j1; pHL; /p 指針?biāo)赶虻慕Y(jié)點(diǎn)，是單鏈表中第 j 6、對(duì)鏈表設(shè)置頭結(jié)點(diǎn)的作用是什么?(至少說(shuō)出兩條好處) 解答：(1) 對(duì)帶頭結(jié)點(diǎn)的鏈表，在表的任何結(jié)點(diǎn)之前插入結(jié)點(diǎn)或刪除表中任何結(jié)點(diǎn)，所要做的都是修改前一 結(jié)點(diǎn)的指針域，因?yàn)槿魏卧亟Y(jié)點(diǎn)都有前驅(qū)結(jié)點(diǎn)。若鏈表沒(méi)有頭結(jié)點(diǎn)，則首元素結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，在其前 插入結(jié)點(diǎn)或刪除該結(jié)點(diǎn)時(shí)操作會(huì)復(fù)雜些。 (2) 對(duì)帶頭結(jié)點(diǎn)的鏈表，表頭指針是指向頭結(jié)點(diǎn)的非空指針，因此空表與非空表的處理是一樣的。 7、在單鏈表、雙鏈表和單循環(huán)表中，若僅知道指針 p 指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)*p 從相應(yīng)的 鏈表中刪去？若可以，其時(shí)間復(fù)雜度各為多少？ 解答：1. 單鏈表。當(dāng)我們知道指針 p 指向某結(jié)點(diǎn)時(shí)，能夠根據(jù)該指針找到其直接后繼，但是由于不知道其 頭指針，所以無(wú)法訪問(wèn)到 p 指針指向的結(jié)點(diǎn)的直接前趨。因此無(wú)法刪去該結(jié)點(diǎn)。 2. 雙鏈表。由于這樣的鏈表提供雙向鏈接，因此根據(jù)已知