計算機軟件技術基礎復習題含答案

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

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

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

4、都是按結點的data域由大到小鏈接的。合并后新鏈表的結點仍按此方式鏈接。請?zhí)顚懴率隹湛?，使程序能正確運行。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.在本題的程序中，函數create_link_list(n)

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

6、出513642。請在空框處填上適當內容，每框只填一個語句。#defineNULL0typedefstructnodeintdatastructnodenextnodelinklisttypelinklisttypecreate_link_list(intn)linklisttypeheadpqintIhead=NULLif(n0)head=(linklisttype)malloc(sizeof(linklisttype))p=headf