計(jì)算機(jī)軟件技術(shù)基礎(chǔ)復(fù)習(xí)題及答案完美打印版

1、《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)》試題1.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)相比優(yōu)點(diǎn)是CD。A.所有的操作算法實(shí)現(xiàn)簡單B.便于隨機(jī)存取C.C.便于插入和刪除便于插入和刪除D.D.便于利用零散的存儲器空間便于利用零散的存儲器空間2.線性表是具有n個C的有限序列。A.表元素B.字符C.C.數(shù)據(jù)元素?cái)?shù)據(jù)元素D.數(shù)據(jù)項(xiàng)E.信息項(xiàng)3.若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第I個位置插入一個新元素的算法的時(shí)間復(fù)雜度為C。（1≤I≤n1）A.O(0)B.O(1

2、)C.C.O(n)O(n)D.O(n2)4.設(shè)A是一個線性表(a1a2…an)，采用順序存儲結(jié)構(gòu)，則在等概率的前提下，平均每插入一個元素需要移動的元素個數(shù)為B，平均每刪除一個元素需要移動的元素個數(shù)為A；若元素插在ai與ai1之間(0≤I≤n1)的概率為，則平均每插入一)1()(2??nnin個元素所要移動的元素個數(shù)為C；A.B.21?n2nC.D.312?n413?n5.下列函數(shù)中，按它們在時(shí)的無窮大階數(shù)，最大的是D。??nA.logn

3、B.nlognC.2n2D.D.n!n!6.將下圖所示的s所指結(jié)點(diǎn)加到p所指的結(jié)點(diǎn)之后，其語句應(yīng)為：D。A.snext=p1pnext=sB.(p).next=s(s).next=(p).nextC.snext=pnextpnext=snextD.D.snext=pnextsnext=pnextpnext=spnext=s7.將兩個各有n個元素的有序表歸并為一個有序表時(shí)，其最少的比較次數(shù)是A。A.A.nB.2n1C.n1D.2n8.下面

4、的程序段是合并兩個無頭結(jié)點(diǎn)鏈表(ha和hb)為一個無頭結(jié)點(diǎn)鏈表ha的過程，作為參數(shù)的兩個鏈表都是按結(jié)點(diǎn)的data域由大到小鏈接的。合并后新鏈表的結(jié)點(diǎn)仍按此方式鏈接。請?zhí)顚懴率隹湛?，使程序能正確運(yùn)行。spnextnextnextpa=hanextpb=hbnext(1)while((2))if(padata=pbdata)(3)else(4)(5)參考答案：(1)if(pa==NULL)return(true)(2)pb!=NULL(5)

5、return(false)10.在本題的程序中，函數(shù)create_link_list(n)建立一個具有n個結(jié)點(diǎn)的循環(huán)鏈表；函數(shù)josephus(nIm)對由create_link_list(n)所建立的具有n個結(jié)點(diǎn)的循環(huán)鏈表按一定的次序逐個輸出，并刪除鏈表中的所有結(jié)點(diǎn)。參數(shù)n(n0)指明循環(huán)鏈表的結(jié)點(diǎn)個數(shù)，參數(shù)I(1≤I≤n)指明起始結(jié)點(diǎn)，參數(shù)m（m0是步長），指明從起始結(jié)點(diǎn)或前次被刪除并輸出的結(jié)點(diǎn)之后的第m個結(jié)點(diǎn)作為本次被輸出并刪除的

6、結(jié)點(diǎn)。例如，對于下圖所示的具有6個結(jié)點(diǎn)的循環(huán)鏈表，在調(diào)用josephus(632)后，將輸出513642。請?jiān)诳湛蛱幪钌线m當(dāng)內(nèi)容，每框只填一個語句。#defineNULL0typedefstructnodeintdatastructnodenextnodelinklisttypelinklisttypecreate_link_list(intn)linklisttypeheadpqintIhead=NULLif(n0)head=(lin