數(shù)據(jù)結(jié)構(gòu)(線性表)習(xí)題與答案

一、單選題1、在長(zhǎng)度為n的順序表中的第i(1<=i<=n+1)個(gè)位置上插入一個(gè)元素，其算法時(shí)間復(fù)雜度為（）。A.O(n*n)B.O(log2n)C.O(1)D.O(n)正確答案：D2、在長(zhǎng)度為n的順序表中的第i(1=<i<=n+1)個(gè)位置上插入一個(gè)元素，需要移動(dòng)的元素個(gè)數(shù)為（）。A.iB.n-i+1C.n-i-1D.n-i正確答案：B3、鏈表不具有的特點(diǎn)是（）。A.插入、刪除不需要移動(dòng)元素B.不必事先估計(jì)存儲(chǔ)空間C.可隨機(jī)訪問(wèn)任一元素D.所需存儲(chǔ)空間與線性表程度成正比正確答案：C4、在一單鏈表中，刪除指針p所指的后繼結(jié)點(diǎn)，以下語(yǔ)句正確的是（）。A.p->next=p->next->next;free(p->next);B.p=p->next;C.free(p->next);p->next=p->next->next;D.s=p->next;p->next=s->next;free(s);正確答案：D5、假設(shè)刪除長(zhǎng)度為n的順序表中的每個(gè)元素的概率相同，則刪除一個(gè)元素平均要移動(dòng)的元素個(gè)數(shù)是（）。A.nB.n/2C.(n-1)/2D.(n+1)/2正確答案：C6、設(shè)某順序表中第一個(gè)元素的地址是Base，每個(gè)結(jié)點(diǎn)占m個(gè)單元，則第i個(gè)結(jié)點(diǎn)的地址為（）。A.Base+(i-1)×mB.Base+(i+1)×mC.Base-i×mD.Base+i×m正確答案：A7、長(zhǎng)度為n的非空線性表采用順序存儲(chǔ)結(jié)構(gòu)，在表的第i個(gè)位置插入一個(gè)數(shù)據(jù)元素，i的合法值應(yīng)該是（）。A.1≤i≤n-1B.0≤i≤n+1C.i>0D.1≤i≤n+1正確答案：D解析：一般插入位置從1開始。8、非空單鏈表結(jié)點(diǎn)結(jié)構(gòu)為【data,next】，若指針p所指結(jié)點(diǎn)是尾結(jié)點(diǎn)，則（）表達(dá)式為真。A.p->next==PB.p->next!=NULLC.p->next==NULLD.p==NULL正確答案：C9、某順序表的第一個(gè)元素的存儲(chǔ)地址是500，每個(gè)元素占4個(gè)單元，則第8個(gè)元素的起始地址是()。A.516B.508C.528D.504正確答案：C10、在長(zhǎng)度為n的順序表中刪除第i(1<=i<=n)個(gè)位置上的元素，需要移動(dòng)的元素個(gè)數(shù)為（）。A.n-i-1B.iC.n-iD.n-i+1正確答案：C解析：假設(shè)順序表為L(zhǎng)={a1,a2,a3,...,ai,ai+1,...,an}要?jiǎng)h除ai，則ai+1.....an的元素需要順次前移，共n-i個(gè)11、非空循環(huán)單鏈表L中，p指針指向尾結(jié)點(diǎn)，則以下表達(dá)式成立的是（）。A.p->next==NULLB.p==NULLC.p==LD.p->next==L正確答案：D解析：循環(huán)單鏈表中，尾結(jié)點(diǎn)的指針域指向單鏈表的頭結(jié)點(diǎn)或第一個(gè)結(jié)點(diǎn)。在本題中，只有這個(gè)選項(xiàng)最符合要求。12、若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（）存儲(chǔ)方式最節(jié)省時(shí)間。A.雙向鏈表B.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表C.單循環(huán)鏈表D.順序表正確答案：D解析：該題有兩個(gè)要求：第一個(gè)要求是存取任一指定序號(hào)的元素，當(dāng)然用順序表存儲(chǔ)最合適。第二個(gè)要求是插入和刪除，雖然順序表在插入刪除時(shí)需要移動(dòng)元素，浪費(fèi)時(shí)間，但該題中是在最后進(jìn)行插入刪除，因此順序表很適合。13、某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.帶尾指針的單循環(huán)鏈表B.僅有頭指針的單循環(huán)鏈表C.單鏈表D.雙鏈表正確答案：A14、對(duì)于雙向循環(huán)鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共（）個(gè)。A.2B.3C.5D.4正確答案：D15、將帶頭指針的長(zhǎng)度為m的單鏈表，鏈接到同樣帶頭指針的長(zhǎng)度為n的單鏈表末尾。該算法的時(shí)間復(fù)雜度為()。A.O(m+n)B.O(n)C.O(m)D.O(m*n)正確答案：B解析：需要找到長(zhǎng)度為n的單鏈表的末尾，所以時(shí)間復(fù)雜度為O（n）16、在某雙向鏈表中刪除一個(gè)結(jié)點(diǎn)，需要改動(dòng)（）個(gè)指針域。A.3B.4C.1D.2正確答案：D二、判斷題1、單鏈表中增加頭結(jié)點(diǎn)的目的是存儲(chǔ)鏈表的長(zhǎng)度。(×)解析：添加頭結(jié)點(diǎn)的目的是，簡(jiǎn)化操作。不一定是為了存儲(chǔ)鏈表的長(zhǎng)度。2、線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)。(×)3、線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比。(×)4、在順序表中，邏輯上相鄰的兩個(gè)元素物理存儲(chǔ)上也一定也相鄰。(√)5、順序表結(jié)構(gòu)適宜進(jìn)行隨機(jī)訪問(wèn)，而鏈表適宜進(jìn)行插入、刪除。(√)6、靜態(tài)鏈表既有順序存儲(chǔ)的優(yōu)點(diǎn)，又有動(dòng)態(tài)鏈表的優(yōu)點(diǎn)。所以，它存取表中第i個(gè)元素的時(shí)間與i無(wú)關(guān)。(×)解析：靜態(tài)鏈表本質(zhì)仍然是鏈表，所以它不具有順序表的優(yōu)點(diǎn)。7、循環(huán)單鏈表中，每個(gè)結(jié)點(diǎn)都有一個(gè)前驅(qū)和后繼，因此循環(huán)單鏈表不是線性結(jié)構(gòu)。(×)解析：前驅(qū)和后繼是元素間的邏輯關(guān)系。循環(huán)單鏈表是元素的存儲(chǔ)關(guān)系，只是為了操作方便而采用循環(huán)鏈表，并不會(huì)改變?cè)氐倪壿嬯P(guān)系。8、靜態(tài)鏈表中