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

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