計(jì)算機(jī)軟件技術(shù)基礎(chǔ)復(fù)習(xí)題含答案

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

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

3、圖所示的s所指結(jié)點(diǎn)加到p所指的結(jié)點(diǎn)之后，其語(yǔ)句應(yīng)為：D。A.snext=p1pnext=sB.(p).next=s(s).next=(p).nextC.snext=pnextpnext=snextD.snext=pnextpnext=s7.將兩個(gè)各有n個(gè)元素的有序表歸并為一個(gè)有序表時(shí)，其最少的比較次數(shù)是A。A.nB.2n1C.n1D.2n8.下面的程序段是合并兩個(gè)無(wú)頭結(jié)點(diǎn)鏈表(ha和hb)為一個(gè)無(wú)頭結(jié)點(diǎn)鏈表ha的過程，作為參數(shù)的兩個(gè)鏈表

4、都是按結(jié)點(diǎn)的data域由大到小鏈接的。合并后新鏈表的結(jié)點(diǎn)仍按此方式鏈接。請(qǐng)?zhí)顚懴率隹湛?，使程序能正確運(yùn)行。spnextnextnext3pa=hanextpb=hbnext(1)while((2))if(padata=pbdata)(3)else(4)(5)參考答案：(1)if(pa==NULL)return(true)(2)pb!=NULL(5)return(false)10.在本題的程序中，函數(shù)create_link_list(n)

5、建立一個(gè)具有n個(gè)結(jié)點(diǎn)的循環(huán)鏈表；函數(shù)josephus(nIm)對(duì)由create_link_list(n)所建立的具有n個(gè)結(jié)點(diǎn)的循環(huán)鏈表按一定的次序逐個(gè)輸出，并刪除鏈表中的所有結(jié)點(diǎn)。參數(shù)n(n0)指明循環(huán)鏈表的結(jié)點(diǎn)個(gè)數(shù)，參數(shù)I(1≤I≤n)指明起始結(jié)點(diǎn)，參數(shù)m（m0是步長(zhǎng)），指明從起始結(jié)點(diǎn)或前次被刪除并輸出的結(jié)點(diǎn)之后的第m個(gè)結(jié)點(diǎn)作為本次被輸出并刪除的結(jié)點(diǎn)。例如，對(duì)于下圖所示的具有6個(gè)結(jié)點(diǎn)的循環(huán)鏈表，在調(diào)用josephus(632)后，將輸

6、出513642。請(qǐng)?jiān)诳湛蛱幪钌线m當(dāng)內(nèi)容，每框只填一個(gè)語(yǔ)句。#defineNULL0typedefstructnodeintdatastructnodenextnodelinklisttypelinklisttypecreate_link_list(intn)linklisttypeheadpqintIhead=NULLif(n0)head=(linklisttype)malloc(sizeof(linklisttype))p=headf