1線性表的邏輯順序與存儲(chǔ)順序總是一致的

1、第二章 習(xí)題一判斷題1 .線性表的邏輯順序與存儲(chǔ)順序總是一致的。順序存儲(chǔ)的線性表可以按序號(hào)隨機(jī)存取。順序表的插入和刪除操作不需要付出很大的時(shí)間代價(jià)，因?yàn)槊看尾僮髌骄挥薪话氲?元素需要移動(dòng)。線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此 是屬于同一數(shù)據(jù)對(duì)象。在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定緊鄰。在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。在線性表的順序存儲(chǔ)結(jié)構(gòu)中，插入和刪除時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中數(shù)據(jù)

2、元素的。在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取 的存儲(chǔ)結(jié)構(gòu)。二單選題(請(qǐng)從下列A, B, C, D選項(xiàng)中選擇一項(xiàng))1 .線性表是()。個(gè)有限序列，可以為空；(B)個(gè)有限序列，不能為空；(C) 一個(gè)無(wú)限序列，可以為空；(D) 一個(gè)無(wú)序序列，不能為空。對(duì)順序存儲(chǔ)的線性表，設(shè)其長(zhǎng)度為n，在任何位置上插入或刪除操作都是等概率的。插 入一個(gè)元素時(shí)平均要移動(dòng)表中的()個(gè)元素。(A) n/2(B) n+1/2(C) n -1/2(D) n線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址()。必須是連續(xù)的；(B)部分地址必須是連續(xù)的；(C) 一定是不連續(xù)的；(D)連續(xù)與否均可以。用鏈表表示線

3、性表的優(yōu)點(diǎn)是()。便于隨機(jī)存取花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少便于插入和刪除數(shù)據(jù)元素的物理順序與邏輯順序相同某鏈表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除最后一個(gè)元素，則采 用()存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。單鏈表雙鏈表單循環(huán)鏈表帶頭結(jié)點(diǎn)的雙循環(huán)鏈表循環(huán)鏈表的主要優(yōu)點(diǎn)是()。不在需要頭指針了已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到他的直接前趨在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好的保證鏈表不斷開(kāi)從表中的任意結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表下面關(guān)于線性表的敘述錯(cuò)誤的是()。線性表采用順序存儲(chǔ)，必須占用一片地址連續(xù)的單元；線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作；線性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片地址連續(xù)的單元；線

4、性表采用鏈?zhǔn)酱鎯?chǔ)，不便于進(jìn)行插入和刪除操作；單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是為了()。(A)使單鏈表至少有一個(gè)結(jié)點(diǎn)(B)標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置(C)方便運(yùn)算的實(shí)現(xiàn)(D)說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則 采用()存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。(A)單鏈表(B)僅有頭指針的單循環(huán)鏈表(C)雙鏈表(D)僅有尾指針的單循環(huán)鏈表若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用() 存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間()。(A)單鏈表(B)順序表(C)雙鏈表(D)單循環(huán)鏈表三填空題帶頭結(jié)點(diǎn)的單鏈表H為空的條件是。1.非空單循環(huán)鏈

5、表L中*?是尾結(jié)點(diǎn)的條件是。在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)由指針f所指結(jié)點(diǎn)，應(yīng)執(zhí)行s-next=;和p-next=的操作。在一個(gè)單鏈表中p所指結(jié)點(diǎn)之前插入一個(gè)由指針f所指結(jié)點(diǎn)，可執(zhí)行以下操作：s-next=;p-next=s;t=p-data;p-data=;s-data=; 在順序表中做插入操作時(shí)首先檢查。四算法設(shè)計(jì)題1.設(shè)線性表存放在向量Aarrsize的前elenum個(gè)分量中，且遞增有序。試寫(xiě)一算法，將x插入到線性表的適當(dāng)位置上，以保持線性表的有序性。并且分析算法的時(shí)間復(fù)雜度。已知一順序表A,其元素值非遞減有序排列，編寫(xiě)一個(gè)函數(shù)刪除順序表中多余的值相同 的元素。編寫(xiě)一個(gè)函數(shù)，從一給

6、定的順序表A中刪除值在xy(x=y)之間的所有元素，要求以較 高的效率來(lái)實(shí)現(xiàn)。提示：可以先將順序表中所有值在xy之間的元素置成一個(gè)特殊的值，并不立即刪 除它們，然后從最后向前依次掃描，發(fā)現(xiàn)具有特殊值的元素后，移動(dòng)其后面的元素將其 刪除掉。線性表中有n個(gè)元素，每個(gè)元素是一個(gè)字符，現(xiàn)存于向量Rn中，試寫(xiě)一算法，使R中 的字符按字母字符、數(shù)字字符和其它字符的順序排列。要求利用原來(lái)的存儲(chǔ)空間，元素 移動(dòng)次數(shù)最小。線性表用順序存儲(chǔ)，設(shè)計(jì)一個(gè)算法，用盡可能少的輔助存儲(chǔ)空間將順序表中前m個(gè)元素 和后n個(gè)元素進(jìn)行整體互換。即將線性表(a1, a2,，am, b1, b2, . , bn)改變?yōu)椋?場(chǎng),b2,

7、. , bn , a1, a2,，am)。已知帶頭結(jié)點(diǎn)的單鏈表L中的結(jié)點(diǎn)是按整數(shù)值遞增排列的，試寫(xiě)一算法，將值為x的結(jié) 點(diǎn)插入到表L中，使得L仍然有序。并且分析算法的時(shí)間復(fù)雜度。假設(shè)有兩個(gè)已排序的單鏈表A和B，編寫(xiě)一個(gè)函數(shù)將他們合并成一個(gè)鏈表C而不改變其 排序性。假設(shè)長(zhǎng)度大于1的循環(huán)單鏈表中，既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針，p為指向該鏈表中某一結(jié)點(diǎn) 的指針，編寫(xiě)一個(gè)函數(shù)刪除該結(jié)點(diǎn)的前趨結(jié)點(diǎn)。已知兩個(gè)單鏈表A和B分別表示兩個(gè)集合，其元素遞增排列，編寫(xiě)一個(gè)函數(shù)求出A和 B的交集C，要求C同樣以元素遞增的單鏈表形式存儲(chǔ)。設(shè)有一個(gè)雙向鏈表，每個(gè)結(jié)點(diǎn)中除有prior、data和next域外，還有一個(gè)訪問(wèn)頻度 freq域，在鏈表被起用之前，該域其值初始化為零。每當(dāng)在