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

線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（ ） A必須是不連續(xù)的 B連續(xù)與否均可 C必須是連續(xù)的 D和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)由兩個(gè)棧共享一個(gè)向量空間的好處是：（ ） A減少存取時(shí)間，降低下溢發(fā)生的機(jī)率 B節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率 C減少存取時(shí)間，降低上溢發(fā)生的機(jī)率 D節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的機(jī)率假設(shè)以帶行表的三元組表表示稀疏矩陣，則和下列行表02335 對(duì)應(yīng)的稀疏矩陣是（ ） 在一棵度為3的樹中,度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2 的結(jié)點(diǎn)個(gè)數(shù)為1,則度為0的結(jié)點(diǎn)個(gè)數(shù)為( )A4 B5 C6 D7一棵含18個(gè)結(jié)點(diǎn)的二叉樹的高度至少為( C ) A.3 B.4 C.5 D.6 已知二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為( D ) A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA 無向圖中一個(gè)頂點(diǎn)的度是指圖中( B ) A.通過該頂點(diǎn)的簡(jiǎn)單路徑數(shù) B.與該頂點(diǎn)相鄰接的頂點(diǎn)數(shù) C.通過該頂點(diǎn)的回路數(shù) D.與該頂點(diǎn)連通的頂點(diǎn)數(shù) 設(shè)順序存儲(chǔ)的線性表共有123個(gè)元素，按分塊查找的要求等分成3塊。若對(duì)索引表采用順序查找來確定塊，并在確定的塊中進(jìn)行順序查找，則在查找概率相等的情況下，分塊查找成功時(shí)的平均查找長(zhǎng)度為( B ) A.21 B.23 C.41 D.62 在含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中,零元素的個(gè)數(shù)為( ) Ae B2e Cn2e Dn22e用某種排序方法對(duì)關(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ù)的 存儲(chǔ)（或存儲(chǔ)結(jié)構(gòu)） 無關(guān)，是獨(dú)立于計(jì)算機(jī)的。在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針head可用p表示為head= pnextnext 。棧頂?shù)奈恢檬请S著 進(jìn)棧和退棧 操作而變化的。假設(shè)一個(gè)9階的上三角矩陣A按列優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組B中，其中B0存儲(chǔ)矩陣中第1個(gè)元素a1,1,則B31中存放的元素是 a4,8 。已知一棵完全二叉樹中共有768結(jié)點(diǎn)，則該樹中共有 384 個(gè)葉子結(jié)點(diǎn)。 已知一個(gè)圖的廣度優(yōu)先生成樹如右圖所示，則與此相 應(yīng)的廣度優(yōu)先遍歷序列為 abefcdg 。 從順序表中刪除一個(gè)元素時(shí)，表中所有在被刪元素之后的元素均需_前移_一個(gè)位置。 在隊(duì)列中，允許進(jìn)行插入操作的一端稱為_隊(duì)尾_，允許進(jìn)行刪除操作的一端稱為_隊(duì)頭_。 在有序表（12，24，36，48，60，72，84）中二分查找關(guān)鍵字72時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)為 。已知一個(gè)無向圖的頂點(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； 請(qǐng)回答下列問題： （1）Ro和Rt行的功能是什么？ （2）說明算法的功能。（1）Ro查詢鏈表的尾結(jié)點(diǎn)，Rt將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)（2）使原單鏈表變?yōu)檠h(huán)單鏈表，返回循環(huán)單鏈表的頭指針假設(shè)兩個(gè)隊(duì)列共享一個(gè)循環(huán)向量空間（參見右下圖）， 其類型Queue2定義如下： typedef struct DateType dataMaxSize； int front2,rear2； Queue2；對(duì)于i=0或1，fronti和reari分別為第i個(gè)隊(duì)列的頭指針和尾指針。請(qǐng)對(duì)以下算法填空，實(shí)現(xiàn)第i個(gè)隊(duì)列的入隊(duì)操作。 int EnQueue (Queue2*Q,int i,DateType x) /若第 i個(gè)隊(duì)列不滿，則元素x入隊(duì)列，并返回1；否則返回0 if(i1)return 0； if(Qreari=Qfront return 0； Qdata =x； Qreari= ; return1； (i1)%2(或1i)Qreari(Qreari1)%Maxsize已知一個(gè)圖如下所示，其頂點(diǎn)按a、b、c、d、e、f順序存放在鄰接表的頂點(diǎn)表中，請(qǐng)畫出該圖的鄰接表，使得按此鄰接表進(jìn)行深度優(yōu)先遍歷時(shí)得到的頂點(diǎn)序列為acbefd，進(jìn)行廣度優(yōu)先遍歷時(shí)得到的頂點(diǎn)序列為acbdfe。已知兩個(gè)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 請(qǐng)畫出這兩個(gè)稀疏矩陣之和的三元組表。 解: 從空樹起，依次插入關(guān)鍵字40，8，90，15，62，95，12，23，56，32，構(gòu)造一棵二叉排序樹。 (1)畫出該二叉排序樹 (2)畫出刪去該樹中元素值為90的結(jié)點(diǎn)之后的二叉排序樹。 閱讀下列函數(shù)algo,并回答問題。 (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)簡(jiǎn)述函數(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=t; while(i<j) while(i<j & Lj>=x)j-; Li=Lj; while(i<j & Li<=x)i+; Lj=Li; Li=x; if(i<(n+1)/2)s=i+1; else t=i-1; if(i=0)return 0; else return Li; (1) (2) (3) 33題答案： （1）外循環(huán)執(zhí)行4次，函數(shù)返回值為3。 （2）將A1至A8中不小于A1的元素進(jìn)行遞增排序，如調(diào)用algo(A,8)時(shí)最終排序結(jié)果為2 1 3 4 6 7 8 9 隊(duì)和棧的主要區(qū)別是(d)A.邏輯結(jié)構(gòu)不同B.存儲(chǔ)結(jié)構(gòu)不同C.所包含的運(yùn)算個(gè)數(shù)不同D.限定插入和刪除的位置不同鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是(d)A.插入操作更加方便B.刪除操作更加方便C.不會(huì)出現(xiàn)下溢的情況D.不會(huì)出現(xiàn)上溢的情況二叉樹中第5層上的結(jié)點(diǎn)個(gè)數(shù)最多為(d)A.8B.15C.16D.32假設(shè)隊(duì)列q中的元素為(2,4,5,7,8),其中“2”為隊(duì)頭元素。寫出執(zhí)行函數(shù)調(diào)用algo(&q)后的隊(duì)列q；(2)簡(jiǎn)述算法algo的功能。voidalgo(Queue*Q)StackS;InitStack(&S);while(!QueueEmpty(Q)Push(&S,DeQueue(Q);while(!StackEmpty(&S)nQueue(Q,Pop(&S);(1)87542(2)隊(duì)列倒置在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)可以分成（）A內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)B線性結(jié)構(gòu)和非線性結(jié)構(gòu)C緊湊結(jié)構(gòu)和非緊揍結(jié)構(gòu)D動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)在以單鏈表為存儲(chǔ)結(jié)構(gòu)的線性表中，數(shù)據(jù)元素之間的邏輯關(guān)系用（）A數(shù)據(jù)元素的相鄰地址表示B數(shù)據(jù)元素在表中的序號(hào)表示C指向后繼元素的指針表示D數(shù)據(jù)元素的值表示設(shè)p指向單鏈表中的一個(gè)結(jié)點(diǎn)，s指向待插入的結(jié)點(diǎn)，則下述程序段的功能是（）s-next=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順序存儲(chǔ)的線性結(jié)構(gòu)C鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)D限制存取位置的非線性結(jié)構(gòu)當(dāng)在二叉排序樹中插入一個(gè)新結(jié)點(diǎn)時(shí)，若樹中不存在與待插入結(jié)點(diǎn)的關(guān)鍵字相同的結(jié)點(diǎn)，且新結(jié)點(diǎn)的關(guān)鍵字小于根結(jié)點(diǎn)的關(guān)鍵字，則新結(jié)點(diǎn)將成為（）A左子樹的葉子結(jié)點(diǎn)B左子樹的分支結(jié)點(diǎn)C右子樹的葉子結(jié)點(diǎn)D右子樹的分支結(jié)點(diǎn)希爾排序的增量序列必須是（）A遞增的B隨機(jī)的C遞減的D非遞減的如果在排序過程中，每次均將一個(gè)待排序的記錄按關(guān)鍵字大小加入到前面已經(jīng)有序的子表中的適當(dāng)位置，則該排序方法稱為（）A插入排序B歸并排序C冒泡排序D堆排序已知指針p指向單鏈表中某個(gè)結(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個(gè)結(jié)點(diǎn)，則該樹共有_23+7/2=11_個(gè)葉子結(jié)點(diǎn)。在有向圖中，以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目稱為v的_入度_。假設(shè)元素只能按a,b,c,d的順序依次進(jìn)棧，且得到的出棧序列中的第一個(gè)元素為c，則可能得到的出棧序列為_，不可能得到的出棧序列為_1)cbad,cbda,cdba2)cabd,cadb,cdab若以鄰接矩陣表示有向圖，則鄰接矩陣上第i行中非零元素的個(gè)數(shù)即為頂點(diǎn)vi的_。出度下列函數(shù)的功能是，對(duì)以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)的兩個(gè)遞增有序表（表中不存在值相同的數(shù)據(jù)元素）進(jìn)行如下操作：將所有在Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到La中，其中La和Lb分別為兩個(gè)鏈表的頭指針。請(qǐng)?jiān)诳杖碧幪钊牒线m內(nèi)容，使其成為一個(gè)完整的算法。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-next=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í)，對(duì)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ì)B.入隊(duì)C.取隊(duì)頭元素D.取隊(duì)尾元素若進(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對(duì)關(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)不一定相同，但平均查找長(zhǎng)度相同B.其形態(tài)不一定相同，平均查找長(zhǎng)度也不一定相同C.其形態(tài)均相同，但平均查找長(zhǎng)度不一定相同D.其形態(tài)均相同，平均查找長(zhǎng)度也都相同數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的_存儲(chǔ)結(jié)構(gòu)_。假設(shè)以數(shù)組seqnm存放循環(huán)隊(duì)列的元素，設(shè)變量rear和quelen分別指示循環(huán)隊(duì)列中隊(duì)尾元素的位置和元素的個(gè)數(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-quelen+m)%m閱讀下列算法，并回答問題：(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)簡(jiǎn)述算法的功能。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ù)后移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()里是把Ri和RRi交換;(1)L=0,1,2,3,4,5,6,7;(2)5次能進(jìn)行二分查找的線性表,必須以（A）A順序方式存儲(chǔ),且元素按關(guān)鍵字有序B鏈?zhǔn)椒绞酱鎯?chǔ),且元素按關(guān)鍵字有序C順序方式存儲(chǔ),且元素按關(guān)鍵字分塊有序D鏈?zhǔn)椒绞酱鎯?chǔ),且元素按關(guān)鍵字分塊有序數(shù)組采用順序存儲(chǔ)方式表示是因?yàn)橥ǔ２粚?duì)數(shù)組進(jìn)行_插入和刪除_操作。結(jié)點(diǎn)數(shù)為20的二叉樹可能達(dá)期的最大高度為_19_。在現(xiàn)代操作系統(tǒng)中引入了（ ），從而使并發(fā)和共享成為可能。A.單道程序 B. 磁盤 C. 對(duì)象 D.多道程序 ( )操作系統(tǒng)允許在一臺(tái)主機(jī)上同時(shí)連接多臺(tái)終端，多個(gè)用戶可以通過各自的終端同時(shí)交互地使用計(jì)算機(jī)。 A.網(wǎng)絡(luò) B.分布式 C.分時(shí) D.實(shí)時(shí)當(dāng)一個(gè)進(jìn)程處于（ ）狀態(tài)時(shí)，稱其為等待（或阻塞）狀態(tài)。A. 它正等待中央處理機(jī) B. 它正等待合作進(jìn)程的一個(gè)消息 C. 它正等待分給它一個(gè)時(shí)間片 D. 它正等待進(jìn)入內(nèi)存一個(gè)進(jìn)程釋放一種資源將有可能導(dǎo)致一個(gè)或幾個(gè)進(jìn)程（ ）。A.由就緒變運(yùn)行 B.由運(yùn)行變就緒 C.由阻塞變運(yùn)行 D.由阻塞變就緒有m個(gè)進(jìn)程共享同一臨界資源，若使用信號(hào)量機(jī)制實(shí)現(xiàn)對(duì)一臨界資源的互斥訪問，則信號(hào)量的變化范圍是（ ）。A.1至 (m-1) B.1至m-1 C.1至m D.1至m在下面關(guān)于虛擬存儲(chǔ)器的敘述中，正確的是（ ）。A.要求程序運(yùn)行前必須全部裝入內(nèi)存且在運(yùn)行過程中一直駐留在內(nèi)存B.要求程序運(yùn)行前不必全部裝入內(nèi)存且在運(yùn)行過程中不必一直駐留在內(nèi)存C.要求程序運(yùn)行前不必全部裝入內(nèi)存但