數(shù)據(jù)結(jié)構(gòu)作業(yè)一滿分

1、1.       在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費(fèi)的時(shí)間最少的是A.      單鏈表  B. 雙向鏈表  C.循環(huán)鏈表  D.順序表說明：順序表總從鏈表訪問快，因?yàn)轫樞虮碓囟际前错樞蚺帕性谝黄鸬?。而鏈表的元素是分散的，要訪問它的某一個(gè)元素，必須先訪問它前面的元素。 2.       順序表是線性表的 

2、;A.鏈?zhǔn)酱鎯Y(jié)構(gòu)      B.    順序存儲結(jié)構(gòu)      C. 索引存儲結(jié)構(gòu)  D.散列存儲結(jié)構(gòu)說明：順序存儲指在內(nèi)存中是一個(gè)連續(xù)的整塊，這是定義，沒啥說的。 3. 以下關(guān)于線性表的說法不正確的是( )。  A、線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。B、線性表中包含的數(shù)據(jù)元素個(gè)數(shù)不是任意的。  C、線性表根據(jù)存儲結(jié)構(gòu)分可以有順

3、序表、鏈表、動(dòng)態(tài)表D、存在這樣的線性表：表中各結(jié)點(diǎn)都沒有直接前趨和直接后繼說明：A，我認(rèn)為可以是任何類型（暫時(shí)沒想出反例）B，這句話不太好理解，估計(jì)原題的意思是為了說明：線性表是能得到確切的元素個(gè)數(shù)。C，線性表只包括順序表和鏈表。而動(dòng)態(tài)表，沒聽說過這種說法。D，線性表為空，好像就符合題意。4在順序表中，只要知道( )，就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲地址。A) 基地址      B) 結(jié)點(diǎn)大小     C) 向量大小   &

4、#160; D)基地址和結(jié)點(diǎn)大小說明：這里任意結(jié)點(diǎn)是指給出這個(gè)結(jié)點(diǎn)的索引(index)，則其地址為：base + index * sizeof(node)，這里base為基地址，sizeof(node)為結(jié)點(diǎn)大小，假設(shè)index從0開始計(jì)數(shù)（C/C+都是從0開始，如果其它語言從1開始，只要將index-1代替index就可以了）5在等概率情況下，順序表的插入操作要移動(dòng)( )結(jié)點(diǎn)。A) 全部               B)&#

5、160;一半         C) 三分之一               D) 四分之一說明：插入和刪除操作，平均約要移動(dòng)全部元素的1/2，在P25，有推導(dǎo)公式，記住結(jié)果就行了。6在( )運(yùn)算中，使用順序表比鏈表好。  A) 插入      

6、0;  B) 刪除               C) 根據(jù)序號查找               D)  根據(jù)元素值查找說明：插入、刪除操作都是鏈表快。根據(jù)元素值查找，都是要遍歷每個(gè)元素，進(jìn)行比對，直到找到為止，兩者效率應(yīng)該相等。根據(jù)序號查找

7、，也就是根據(jù)索引index，順序表的訪問時(shí)間為常量，比鏈表要快，這與第4題是同一個(gè)知識點(diǎn)。7在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是( )。  A)  O(1)              B)  O(n)              

8、;C)  O(n2)          D)  O(log2n)說明：插入前要遍歷之前的每一個(gè)元素，直到找到位置為止，這個(gè)定位過程，都是O(n)8( )適合作為經(jīng)常在首尾兩端操作線性表的存儲結(jié)構(gòu)。  A)  順序表    B) 單鏈表         C) 循環(huán)鏈表&#

9、160;        D) 雙向鏈表說明：常用操作無非包括插入、刪除、讀取三種方式。順序表的插入效率太低，不予考慮。對于BCD三種鏈表（循環(huán)鏈表沒說是雙向的，我們這里只認(rèn)為是普通方式，即單向循環(huán)）。對首端的操作差不多。但對尾端就不一樣了。比如要?jiǎng)h除尾結(jié)點(diǎn)t ，則必須先找到它的前一個(gè)結(jié)點(diǎn)s。前兩者，只有遍歷整個(gè)鏈表，才能找到s。而在雙向鏈表中，只要用s = t->prior就可以表示它的前一個(gè)結(jié)點(diǎn)了。9 非空的循環(huán)單鏈表head的尾節(jié)點(diǎn)（由r所指向）滿足A)  

10、;   r->next=NULL       B)    r=NULL         C)    r->next=head         D)   r=head說明：這是定義，最后一個(gè)結(jié)點(diǎn)的下一

11、結(jié)點(diǎn)為頭結(jié)點(diǎn)。 10設(shè)線性表（a1,a2,a3···an）按順序存儲,且每個(gè)元素占有m個(gè)存儲單元，則元素ai的地址為A      LOC(a1) + i×m ，其中LOC(a1)表示元素a1的地址B      LOC(a1) + (i-1)×m，C      LOC(a1) + (i2)×mD    

12、;  元素ai的地址無法計(jì)算說明：見第4題，這里從1開始，所以要減去111線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲單元的地址  A)    必須是連續(xù)的             B)  部分地址必須是連續(xù)的C)    一定是不連續(xù)的       

13、0;   D)  連續(xù)或不連續(xù)都可以說明：其每個(gè)結(jié)點(diǎn)的地址，都是malloc()出來的，這是系統(tǒng)調(diào)用，可能連續(xù)也可能不連續(xù)，不過一般情況下，都是不連續(xù)的。12. 下列圖1單鏈表執(zhí)行R->data=P->next->data語句后，P->next->data值為：A. 2          B. 5        

14、60;   C.7             D. 3 圖1說明：只是將P->next->data賦值給別人了，自己沒變化。13在一個(gè)單鏈表中，若P所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在P之后插入S所指結(jié)點(diǎn)，    則執(zhí)行：    A.Snext=P;Pnext=S       B.

15、Snext=Pnext;Pnext=S  C.Snext=Pnext; P=S      D.Pnext=S;Snext=P說明：鏈表插入的標(biāo)準(zhǔn)操作。要注意的是，這兩步別寫反了，否則鏈就斷開了。14.單鏈表表示的整數(shù)數(shù)列如下: 值Pànextànext->data為: A. 19      B. 47        C. 64

16、60;       D. 93說明：Pànext就是指向64那個(gè)結(jié)點(diǎn)，Pànextànext就是指向93那個(gè)結(jié)點(diǎn)，其data自然就是93了15. 在( )鏈表中，不能從任一結(jié)點(diǎn)出發(fā)訪問到表中的所有結(jié)點(diǎn)的是：A) 單鏈表       B) 單向循環(huán)鏈表     C) 雙向循環(huán)鏈表        D) 循環(huán)鏈表說明：循環(huán)鏈表和雙鏈表都行，只有單鏈表不行。 16、在雙向循環(huán)鏈表的*p結(jié)點(diǎn)之后插入*s結(jié)點(diǎn)的操作是：（）A)     p->next=s; s->prior=p; p->next->prior=s; s->next=p->nextB)      p->next=s; p->next->prior=s; s->prior=p; s->