軟件與編程 第2章測試 （選擇題）附答案

1、軟件與編程 第2章測試 （選擇題）復(fù)制學(xué)號： 填空題 *_姓名： 填空題 *_線性表是n個(gè)( )的有限序列。 單選題 *A. 整數(shù)B. 字符C. 數(shù)據(jù)元素(正確答案)D. 數(shù)據(jù)項(xiàng)線性表L=(a1,a2,an)，下列說法正確的是( )。 單選題 *A. 每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B. 線性表中至少要有一個(gè)元素C. 表中諸元素的排列順序必須是由小到大或由大到小D. 除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都由一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼(正確答案)一個(gè)順序表的第一個(gè)元素的存儲地址是90，每個(gè)元素的長度為2，則第6個(gè)元素的存儲地址是( )。 單選題 *A. 98B. 100(正確答案)

2、C. 102D. 106線性表的順序存儲結(jié)構(gòu)是一種( )存儲結(jié)構(gòu)。 單選題 *A. 隨機(jī)存取(正確答案)B. 順序存取C. 索引存取D. 散列存取在一個(gè)長度為n的順序表中，在第i個(gè)元素之前插入一個(gè)新元素時(shí)，需向后移動( )個(gè)元素。 單選題 *A. n-iB. n-i+1(正確答案)C. n-i-1D. i在一個(gè)長度為n的順序表中刪除第i個(gè)元素，需要向前移動( )個(gè)元素。 單選題 *A. n-i(正確答案)B. n-i+1C. n-i-1D. i+1在表長為n的順序表中，插入一個(gè)元素所需移動的元素平均數(shù)是( )。 單選題 *A. (n-1)/2B. nC. n+1D. n/2(正確答案)在表長為

3、n的順序表中，當(dāng)在任何位置刪除一個(gè)元素的概率相同時(shí)，刪除一個(gè)元素所需移動的平均個(gè)數(shù)為( )。 單選題 *A. (n-1)/2(正確答案)B. n/2C. (n+1)/2D. n在下列對順序表進(jìn)行的操作中，算法時(shí)間復(fù)雜度為O(1)的是( )。 單選題 *A. 訪問第i個(gè)元素的前驅(qū)(1i=n )(正確答案)B. 在第i個(gè)元素之后插入一個(gè)新元素(1=i=n )C. 刪除第i個(gè)元素(1=inext=head(正確答案)B. p-next=NULLC. p=NULLD. p=head鏈表不具有的特點(diǎn)是( )。 單選題 *A. 可隨機(jī)訪問任一元素(正確答案)B. 插入刪除不需要移動元素C. 不必事先估計(jì)存

4、儲空間D. 所需空間與線性表長度成正比在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入一個(gè)指針q所指向的新結(jié)點(diǎn)，修改指針的操作是( )。 單選題 *A. p-next=q;q-prior=p;p-next-prior=q;q-next=q;B. p-next=q;p-next-prior=q;q-prior=p;q-next=p-next;C. q-prior=p;q-next=p-next;p-next-prior=q;p-next=q;(正確答案)D. q-next=p-next;q-prior=p;p-next=q;p-next=q;線性表采用鏈?zhǔn)酱鎯r(shí)，結(jié)點(diǎn)的存儲地址( )。 單選題 *A.

5、 必須是連續(xù)的B. 必須是不連續(xù)的C. 連續(xù)與否均可(正確答案)D. 和頭結(jié)點(diǎn)的存儲地址相連續(xù)從表中任一結(jié)點(diǎn)出發(fā)，都能掃描整個(gè)表的是( )。 單選題 *A. 單鏈表B. 順序表C. 循環(huán)鏈表(正確答案)D. 靜態(tài)鏈表在具有n個(gè)結(jié)點(diǎn)的單鏈表上查找值為x的元素時(shí)，其時(shí)間復(fù)雜度為( )。 單選題 *A. O(n)(正確答案)B. O(1)C. O(n2)D. O(n-1)將長度為n的單鏈表連接在長度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為( )。 單選題 *A. O(1)B. O(n)C. O(m)(正確答案)D. O(m+n)循環(huán)鏈表的主要優(yōu)點(diǎn)是( )。 單選題 *A. 不再需要頭指針B. 已知某結(jié)點(diǎn)

6、位置后能容易找到其直接前驅(qū)C. 在進(jìn)行插入、刪除運(yùn)算時(shí)能保證鏈表不斷開D. 在表中任一結(jié)點(diǎn)出發(fā)都能掃描整個(gè)鏈表(正確答案)帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是( )。 單選題 *A. head=NULLB. head-next=NULL(正確答案)C. head-next=headD. head!=NULL已知指針p和q分別指向某單鏈表中第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)。假設(shè)指針s指向另一個(gè)單鏈表中某個(gè)結(jié)點(diǎn)，則在s所指結(jié)點(diǎn)之后插入上述鏈表應(yīng)執(zhí)行的語句為( )。 單選題 *A. q-next=s-next；s-next=p；(正確答案)B. s-next=p；q-next=s-next；C. p-n

7、ext=s-next；s-next=q；D. s-next=q；p-next=s-next；在以下的敘述中，正確的是( )。 單選題 *A. 線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B. 線性表的順序存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況C. 線性表的鏈表存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況(正確答案)D. 線性表的鏈表存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入一個(gè)結(jié)點(diǎn)s，則執(zhí)行( )。 單選題 *A. s-next=p-next; p-next=s;B. p-next=s-next;s-next=p;C. q-next=s;s-next=p;(正確答案)D. p-next=s;s-next=q;在單鏈表中，指針p指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn)刪除x的后繼結(jié)點(diǎn)的修改指針語句是( )。 單選題 *A. p=p-next;B. p-next=p-next-next;(正確答案)C. p-next=p;D. p=p-next-n