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

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

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

3、) Ae B2e Cn2e Dn22e用某種排序方法對關(guān)鍵字序列25，84，21，47，15，27，68，35，20進(jìn)行排序時(shí)，序列的變化情況如下： 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)，是獨(dú)立于計(jì)算機(jī)的。在一個帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，那么指向頭結(jié)點(diǎn)的指針head可用p表示為head= pnextnext 。

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

5、 。一個無向圖的頂點(diǎn)集為a, b, c, d, e ,其鄰接矩陣如下所示ab cde (1)畫出該圖的圖形； 2根據(jù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。該圖的圖形為： 深度優(yōu)先遍歷序列為：abdce廣度優(yōu)先遍歷序列為：abedcLList note(LList T) /T是不帶頭結(jié)點(diǎn)的單鏈表的頭指針 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é)點(diǎn)，Rt將第一個

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

7、ri=Qfront return 0； Qdata =x； Qreari= ; return1； (i1)%2(或1i)Qreari(Qreari1)%Maxsize一個圖如下所示，其頂點(diǎn)按a、b、c、d、e、f順序存放在鄰接表的頂點(diǎn)表中，請畫出該圖的鄰接表，使得按此鄰接表進(jìn)行深度優(yōu)先遍歷時(shí)得到的頂點(diǎn)序列為acbefd，進(jìn)行廣度優(yōu)先遍歷時(shí)得到的頂點(diǎn)序列為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é)點(diǎn)之后的二叉排序樹。 閱讀以下函數(shù)algo,并答復(fù)以下問題。 (1)假設(shè)整型數(shù)組A1.8中的元素依次為(3，8，9，1，7，4，2，6)。執(zhí)行函數(shù)調(diào)用algo(A,8)時(shí)，外層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é)點(diǎn)*p與結(jié)點(diǎn)*s的數(shù)據(jù)域互換B在p所指結(jié)點(diǎn)的元素之前插入元素C在p所指結(jié)點(diǎn)的元素之后插入元素D在結(jié)點(diǎn)*p之前插入結(jié)點(diǎn)*s棧和隊(duì)列都是A限制存取位置的線性結(jié)構(gòu)B順序存儲的線性結(jié)構(gòu)C鏈?zhǔn)酱鎯Φ木€性結(jié)構(gòu)D限制存取位置的非線性結(jié)構(gòu)當(dāng)在二叉排序樹中插入一個新結(jié)點(diǎn)時(shí)，假設(shè)樹中不存在與待插入結(jié)點(diǎn)的關(guān)鍵字相同的結(jié)點(diǎn)，且新結(jié)點(diǎn)的關(guān)鍵字小于根結(jié)點(diǎn)的關(guān)鍵字，那么新結(jié)點(diǎn)

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

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

12、容，使其成為一個完整的算法。voidunion(LinkListLa,LinkListLb)/本算法的功能是將所有Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到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)時(shí)，對L進(jìn)行的頭兩趟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)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是()A.出隊(duì)

14、B.入隊(duì)C.取隊(duì)頭元素D.取隊(duì)尾元素假設(shè)進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，那么不可能出現(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)進(jìn)行增量為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)在計(jì)算機(jī)存儲器內(nèi)的表示，稱為數(shù)據(jù)的_存儲結(jié)構(gòu)_。假設(shè)以數(shù)組seqnm存放循環(huán)隊(duì)列的元素，設(shè)變量rear和quelen分別指示循環(huán)隊(duì)列中隊(duì)尾元素的位置和元素的個數(shù)。(1)寫出隊(duì)滿的條件表達(dá)式；(2)寫出隊(duì)空的條件表達(dá)式；(3)設(shè)m=40,rear=13,quelen=19,求隊(duì)頭元素的位置；(4)寫出一般情況下隊(duì)頭元素位置的表達(dá)式。(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，沒找到，那么在適當(dāng)?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)用過程中進(jìn)行元素交換操作的總次數(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次能進(jìn)行二分查找的線性表,必須以AA順序方式存儲,且元素按關(guān)鍵字有序B鏈?zhǔn)椒绞酱鎯?且元素按關(guān)鍵字有序C順序方式存儲,且元素按關(guān)鍵字分塊有序D鏈?zhǔn)椒绞酱鎯?且元素按關(guān)鍵字分塊有序數(shù)組采用順序存儲方式表示是因?yàn)橥ǔ２粚?shù)組進(jìn)行_插入和刪除_操作。結(jié)點(diǎn)數(shù)為20的二叉樹可能達(dá)期的最大高度為_19_。在現(xiàn)代操作系統(tǒng)中引入了 ，從而使并發(fā)和共享成為可能。A.單道程序 B. 磁盤 C. 對象 D.多道程序 ( )操作系統(tǒng)允許在一臺主機(jī)上同時(shí)連接多臺終端，多個用戶可以通過各自的終端同時(shí)交互地使用計(jì)算機(jī)。 A.網(wǎng)絡(luò) B.分布式 C.分

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