精選大學(xué)計算機軟件技術(shù)基礎(chǔ)考試技術(shù)復(fù)習題

1、大學(xué)計算機軟件技術(shù)根底考試技術(shù)復(fù)習題線性表采用鏈式存儲時，結(jié)點的存儲地址 A必須是不連續(xù)的 B連續(xù)與否均可 C必須是連續(xù)的 D和頭結(jié)點的存儲地址相連續(xù)由兩個棧共享一個向量空間的好處是： A減少存取時間，降低下溢發(fā)生的機率 B節(jié)省存儲空間，降低上溢發(fā)生的機率 C減少存取時間，降低上溢發(fā)生的機率 D節(jié)省存儲空間，降低下溢發(fā)生的機率假設(shè)以帶行表的三元組表表示稀疏矩陣，那么和以下行表02335 對應(yīng)的稀疏矩陣是 在一棵度為3的樹中,度為3的結(jié)點個數(shù)為2,度為2 的結(jié)點個數(shù)為1,那么度為0的結(jié)點個數(shù)為( )A4 B5 C6 D7一棵含18個結(jié)點的二叉樹的高度至少為( C ) A.3 B.4 C.5 D.

2、6 二叉樹的先序序列為ABDECF，中序序列為DBEAFC，那么后序序列為( D ) A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA 無向圖中一個頂點的度是指圖中( B ) A.通過該頂點的簡單路徑數(shù) B.與該頂點相鄰接的頂點數(shù) C.通過該頂點的回路數(shù) D.與該頂點連通的頂點數(shù) 設(shè)順序存儲的線性表共有123個元素，按分塊查找的要求等分成3塊。假設(shè)對索引表采用順序查找來確定塊，并在確定的塊中進行順序查找，那么在查找概率相等的情況下，分塊查找成功時的平均查找長度為( B ) A.21 B.23 C.41 D.62 在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為(

3、) Ae B2e Cn2e Dn22e用某種排序方法對關(guān)鍵字序列25，84，21，47，15，27，68，35，20進行排序時，序列的變化情況如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 那么所采用的排序方法是 A選擇排序 B希爾排序 C歸并排序 D快速排序數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的 存儲或存儲結(jié)構(gòu) 無關(guān)，是獨立于計算機的。在一個帶頭結(jié)點的單循環(huán)鏈表中，p指向尾結(jié)點的直接前驅(qū)，那么指向頭結(jié)點的指針head可用p表示為head= pnextnext 。

4、棧頂?shù)奈恢檬请S著 進棧和退棧 操作而變化的。假設(shè)一個9階的上三角矩陣A按列優(yōu)先順序壓縮存儲在一維數(shù)組B中，其中B0存儲矩陣中第1個元素a1,1,那么B31中存放的元素是 a4,8 。一棵完全二叉樹中共有768結(jié)點，那么該樹中共有 384 個葉子結(jié)點。 一個圖的廣度優(yōu)先生成樹如右圖所示，那么與此相 應(yīng)的廣度優(yōu)先遍歷序列為 abefcdg 。 從順序表中刪除一個元素時，表中所有在被刪元素之后的元素均需_前移_一個位置。 在隊列中，允許進行插入操作的一端稱為_隊尾_，允許進行刪除操作的一端稱為_隊頭_。 在有序表12，24，36，48，60，72，84中二分查找關(guān)鍵字72時所需進行的關(guān)鍵字比擬次數(shù)為

5、 。一個無向圖的頂點集為a, b, c, d, e ,其鄰接矩陣如下所示ab cde (1)畫出該圖的圖形； 2根據(jù)鄰接矩陣從頂點a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。該圖的圖形為： 深度優(yōu)先遍歷序列為：abdce廣度優(yōu)先遍歷序列為：abedcLList note(LList T) /T是不帶頭結(jié)點的單鏈表的頭指針 If (T&T-next) p=T；T=Tnext；q=T； Ro： while(qnext) q=qnext； Rt： qnext=p； return T； 請答復(fù)以下問題： 1Ro和Rt行的功能是什么？ 2說明算法的功能。1Ro查詢鏈表的尾結(jié)點，Rt將第一個

6、結(jié)點鏈接到鏈表的尾部，作為新的尾結(jié)點2使原單鏈表變?yōu)檠h(huán)單鏈表，返回循環(huán)單鏈表的頭指針假設(shè)兩個隊列共享一個循環(huán)向量空間參見右以下圖， 其類型Queue2定義如下： typedef struct DateType dataMaxSize； int front2,rear2； Queue2；對于i=0或1，fronti和reari分別為第i個隊列的頭指針和尾指針。請對以下算法填空，實現(xiàn)第i個隊列的入隊操作。 int EnQueue (Queue2*Q,int i,DateType x) /假設(shè)第 i個隊列不滿，那么元素x入隊列，并返回1；否那么返回0 if(i1)return 0； if(Qrea

7、ri=Qfront return 0； Qdata =x； Qreari= ; return1； (i1)%2(或1i)Qreari(Qreari1)%Maxsize一個圖如下所示，其頂點按a、b、c、d、e、f順序存放在鄰接表的頂點表中，請畫出該圖的鄰接表，使得按此鄰接表進行深度優(yōu)先遍歷時得到的頂點序列為acbefd，進行廣度優(yōu)先遍歷時得到的頂點序列為acbdfe。兩個45的稀疏矩陣的三元組表分別如下： 0 1 4 16 0 1 1 32 1 2 2 18 1 2 2 22 2 3 4 25 2 2 5 69 3 4 2 28 3 3 4 25 4 4 2 51 請畫出這兩個稀疏矩陣之和的三

8、元組表。 解: 從空樹起，依次插入關(guān)鍵字40，8，90，15，62，95，12，23，56，32，構(gòu)造一棵二叉排序樹。 (1)畫出該二叉排序樹 (2)畫出刪去該樹中元素值為90的結(jié)點之后的二叉排序樹。 閱讀以下函數(shù)algo,并答復(fù)以下問題。 (1)假設(shè)整型數(shù)組A1.8中的元素依次為(3，8，9，1，7，4，2，6)。執(zhí)行函數(shù)調(diào)用algo(A,8)時，外層while的循環(huán)體執(zhí)行多少次?函數(shù)的返回值是多少? (2)簡述函數(shù)algo(L,n)的功能。 int algo(int L,intn) int i=0,j,s=1,t=n; while (i!=(n+1)/2) int x=Ls； i=s;j=

9、t; while(ij) while(i=x)j-; Li=Lj; while(ij & Li=x)i+; Lj=Li; Li=x; if(inext=p-next;p-next=s;t=p-data;p-data=s-data;s-data=t;A結(jié)點*p與結(jié)點*s的數(shù)據(jù)域互換B在p所指結(jié)點的元素之前插入元素C在p所指結(jié)點的元素之后插入元素D在結(jié)點*p之前插入結(jié)點*s棧和隊列都是A限制存取位置的線性結(jié)構(gòu)B順序存儲的線性結(jié)構(gòu)C鏈式存儲的線性結(jié)構(gòu)D限制存取位置的非線性結(jié)構(gòu)當在二叉排序樹中插入一個新結(jié)點時，假設(shè)樹中不存在與待插入結(jié)點的關(guān)鍵字相同的結(jié)點，且新結(jié)點的關(guān)鍵字小于根結(jié)點的關(guān)鍵字，那么新結(jié)點

10、將成為A左子樹的葉子結(jié)點B左子樹的分支結(jié)點C右子樹的葉子結(jié)點D右子樹的分支結(jié)點希爾排序的增量序列必須是A遞增的B隨機的C遞減的D非遞減的如果在排序過程中，每次均將一個待排序的記錄按關(guān)鍵字大小參加到前面已經(jīng)有序的子表中的適當位置，那么該排序方法稱為A插入排序B歸并排序C冒泡排序D堆排序指針p指向單鏈表中某個結(jié)點，那么語句p-next=p-next-next的作用是_。刪除*P的直接后繼結(jié)點刪除雙向循環(huán)鏈表中*p的前驅(qū)結(jié)點(存在)應(yīng)執(zhí)行的語句是_。q=p-pre;q-pre-next=p;p-pre=q-pre;free(q);棧下溢是指在_?？誣時進行出棧操作。完全二叉樹T的第5層只有7個結(jié)點，

11、那么該樹共有_23+7/2=11_個葉子結(jié)點。在有向圖中，以頂點v為終點的邊的數(shù)目稱為v的_入度_。假設(shè)元素只能按a,b,c,d的順序依次進棧，且得到的出棧序列中的第一個元素為c，那么可能得到的出棧序列為_，不可能得到的出棧序列為_1)cbad,cbda,cdba2)cabd,cadb,cdab假設(shè)以鄰接矩陣表示有向圖，那么鄰接矩陣上第i行中非零元素的個數(shù)即為頂點vi的_。出度以下函數(shù)的功能是，對以帶頭結(jié)點的單鏈表作為存儲結(jié)構(gòu)的兩個遞增有序表表中不存在值相同的數(shù)據(jù)元素進行如下操作：將所有在Lb表中存在而La表中不存在的結(jié)點插入到La中，其中La和Lb分別為兩個鏈表的頭指針。請在空缺處填入適宜內(nèi)

12、容，使其成為一個完整的算法。voidunion(LinkListLa,LinkListLb)/本算法的功能是將所有Lb表中存在而La表中不存在的結(jié)點插入到La表中LinkListpre=La,q;LinkListpa=La-next;LinkListpb=Lb-next;free(Lb);while(pa&pd)if(pa-datadata)pre=pa;pa=pa-next;elseif(pa-datapb-data)(1);pre=pb;pb=pb-next;(2);elseq=pb;pb=pb-next;free(q);if(pb)(3);(1)pre-next=pb(2)pre-nex

13、t=pa(3)pre-next=pb整形數(shù)組L1.8中的元素依次為9，8，5，7，6，3，2，1，閱讀以下函數(shù)，并寫出執(zhí)行函數(shù)調(diào)用sort(L,8)時，對L進行的頭兩趟pass分別為0和1處理結(jié)果。Voidsort(intR,intn)intpass=0,k,exchange,x;dok=pass%2+1;exchange=0;while(kRk+1)x=Rk;Rk=Rk+1;Rk+1=x;exchange=1;K+=2pass+;while(exchange=1|passnext=NULLC.head!=NULLD.head-next=head引起循環(huán)隊列隊頭位置發(fā)生變化的操作是()A.出隊

14、B.入隊C.取隊頭元素D.取隊尾元素假設(shè)進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行，那么不可能出現(xiàn)的出棧序列是()A.2，4，3，1，5，6B.3，2，4，1，6，5C.4，3，2，1，5，6D.2，3，5，1，6，4對關(guān)鍵字序列(56，23，78，92，88，67，19，34)進行增量為3的一趟希爾排序的結(jié)果為()A.(19，23，56，34，78，67，88，92)B.(23，56，78，66，88，92，19，34)C.(19，23，34，56，67，78，88，92)D.(19，23，67，56，34，78，92，88)由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹()A.其形態(tài)

15、不一定相同，但平均查找長度相同B.其形態(tài)不一定相同，平均查找長度也不一定相同C.其形態(tài)均相同，但平均查找長度不一定相同D.其形態(tài)均相同，平均查找長度也都相同數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器內(nèi)的表示，稱為數(shù)據(jù)的_存儲結(jié)構(gòu)_。假設(shè)以數(shù)組seqnm存放循環(huán)隊列的元素，設(shè)變量rear和quelen分別指示循環(huán)隊列中隊尾元素的位置和元素的個數(shù)。(1)寫出隊滿的條件表達式；(2)寫出隊空的條件表達式；(3)設(shè)m=40,rear=13,quelen=19,求隊頭元素的位置；(4)寫出一般情況下隊頭元素位置的表達式。(1)quelen=m(2)quelen=0(3)(13-19+40)%40=34(4)(rear

16、-quelen+m)%m閱讀以下算法，并答復(fù)以下問題：(1)設(shè)順序表L=(3,7,11,14,20,51)，寫出執(zhí)行f30(&L,15)之后的L；(2)設(shè)順序表L=(4,7,10,14,20,51)，寫出執(zhí)行f30(&L,10)之后的L；(3)簡述算法的功能。voidf30(SeqList*L,DataTypex)inti=0,j;while(ilength&xL-datai)i+;if(ilength&x=L-datai)/找到x，那么刪除x，大于x的數(shù)前移for(j=i+1;jlength;j+)L-dataj-1=L-dataj;L-length-;else/沒找到，插入x,大于x的數(shù)后

17、移for(j=L-length;ji;j-)L-dataj=L-dataj-1;L-datai=x;L-length+;(1)L=(3,7,11,14,15,20,51)(2)L=(4,7,14,20,51)(3)在順序表L中查找數(shù)x,找到，那么刪除x，沒找到，那么在適當?shù)奈恢貌迦離，插入后，L依然有序.假設(shè)數(shù)組L8=3,0,5,1,6,4,2,7，寫出執(zhí)行函數(shù)調(diào)用f32(L，8)后的L；(2)寫出上述函數(shù)調(diào)用過程中進行元素交換操作的總次數(shù)。voidf32(intR,intn)inti,t;for(i=0;in-1;i+)while(Ri!=i)t=RRi;RRi=Ri;Ri=t;while(

18、)里是把Ri和RRi交換;(1)L=0,1,2,3,4,5,6,7;(2)5次能進行二分查找的線性表,必須以AA順序方式存儲,且元素按關(guān)鍵字有序B鏈式方式存儲,且元素按關(guān)鍵字有序C順序方式存儲,且元素按關(guān)鍵字分塊有序D鏈式方式存儲,且元素按關(guān)鍵字分塊有序數(shù)組采用順序存儲方式表示是因為通常不對數(shù)組進行_插入和刪除_操作。結(jié)點數(shù)為20的二叉樹可能達期的最大高度為_19_。在現(xiàn)代操作系統(tǒng)中引入了 ，從而使并發(fā)和共享成為可能。A.單道程序 B. 磁盤 C. 對象 D.多道程序 ( )操作系統(tǒng)允許在一臺主機上同時連接多臺終端，多個用戶可以通過各自的終端同時交互地使用計算機。 A.網(wǎng)絡(luò) B.分布式 C.分

19、時 D.實時當一個進程處于 狀態(tài)時，稱其為等待或阻塞狀態(tài)。A. 它正等待中央處理機 B. 它正等待合作進程的一個消息 C. 它正等待分給它一個時間片 D. 它正等待進入內(nèi)存一個進程釋放一種資源將有可能導(dǎo)致一個或幾個進程 。A.由就緒變運行 B.由運行變就緒 C.由阻塞變運行 D.由阻塞變就緒有m個進程共享同一臨界資源，假設(shè)使用信號量機制實現(xiàn)對一臨界資源的互斥訪問，那么信號量的變化范圍是 。A.1至 (m-1) B.1至m-1 C.1至m D.1至m在下面關(guān)于虛擬存儲器的表達中，正確的選項是 。A.要求程序運行前必須全部裝入內(nèi)存且在運行過程中一直駐留在內(nèi)存B.要求程序運行前不必全部裝入內(nèi)存且在運行過程中不必一直駐留在內(nèi)存C.要求程序運行前不必全部裝入內(nèi)存但是在運行過程中必須一直駐留在內(nèi)存D.要求程序運行前必須全部