通信軟件基礎(chǔ)期末考試試卷A卷定稿(含答案)

通信軟件基礎(chǔ)期末考試試卷A卷

定稿（含答案）

通信軟件基礎(chǔ)2013年期末考試題目

（含參考答案）

一、選擇題（總分10分）

1、（1分）快速排序算法是基于（A）的一個(gè)排序算法。

A、分治法B、貪心法C、遞歸法D、動(dòng)態(tài)規(guī)劃法

2、（1分）當(dāng)進(jìn)程因時(shí)間片用完而讓出處理機(jī)時(shí)，該進(jìn)程應(yīng)轉(zhuǎn)變?yōu)椋˙）狀態(tài)。

A、等待B、就緒C、運(yùn)行D、完成

3.（1分）在多道程序環(huán)境下，操作系統(tǒng)分配資源的基本單位是（A）

A.進(jìn)程B.線程C.程序D.作業(yè)

4.（1分）文件系統(tǒng)中用（D）管理文件。

A、堆棧結(jié)構(gòu)B、指針C、頁表D、目錄

5.（1分）在操作系統(tǒng)中，JCB是指（A）。

A.作業(yè)控制塊B.進(jìn)程控制塊C.文件控制塊D.程序控制塊

6.（1分）關(guān)系模型中3NF是指（A）

A.滿足2NF且不存在傳遞依賴現(xiàn)象

B.滿足2NF且不存在部分依賴現(xiàn)象

C.滿足2NF且不存在非主屬性

D.滿足2NF且不存在組合屬性

7.（1分）將E-R模型轉(zhuǎn)換成關(guān)系模型，屬于數(shù)

據(jù)庫的（C）

A.需求分析B.概念設(shè)計(jì)

C.邏輯設(shè)計(jì)D.物理設(shè)計(jì)

8.（1分）以下屬于鏈表的優(yōu)點(diǎn)的是（B）（單

選）

A、用數(shù)組可方便實(shí)現(xiàn)B、

插入操作效率高

C、不用為節(jié)點(diǎn)間的邏輯關(guān)系而增加額

外的存儲(chǔ)開銷D、可以按元素號(hào)隨機(jī)訪問

9.（1分）借助于棧輸入A、B、C、D四個(gè)元素

（進(jìn)棧和出棧可以穿插進(jìn)行），則不可能出現(xiàn)的

輸出是（D）o

A、DCBAB、ABCDC、CBADD、CABD

10.（1分）在視圖上不能完成的操作是（C）

A.更新視圖B.查詢

C.在視圖上定義新的基本表D.在視圖

上定義新視圖

二、填空題（21分）

1、（2分）一個(gè)優(yōu)秀算法應(yīng)達(dá)到的指標(biāo)有正確強(qiáng)、可讀性、健壯性和高效性。

2、（2分）遞歸算法的執(zhí)行構(gòu)成分為遞推和回歸兩個(gè)階段。

3、（2分）貪心法的基本思想是：略。

4.（1分）若信號(hào)量S的初值定義為10,則在S上調(diào)用了16次P操作和15次V操作后S的

值應(yīng)該為9。

5.（2分）產(chǎn)生死鎖的四個(gè)必要條件是互斥條件、占有和等待條件、不剝奪條件和循環(huán)

等待條件（或答“環(huán)路”）一.

6.（1分）在操作系統(tǒng)的存儲(chǔ)管理中，由于進(jìn)行動(dòng)態(tài)不等長存儲(chǔ)分配，在內(nèi)存中形成一些很小的空

閑區(qū)域，稱之為碎片.

7.（1分）實(shí)時(shí)系統(tǒng)應(yīng)具有兩個(gè)基本特征：響應(yīng)速度快和可靠性高.

8.（1分）在存儲(chǔ)管理中，為進(jìn)程分配內(nèi)存時(shí)，取滿足申請(qǐng)要求且長度最大的空閑區(qū)域，這一算法稱

為最差適應(yīng)分配算法.

9.（2分）數(shù)據(jù)庫管理系統(tǒng)能實(shí)現(xiàn)的三大功能是

數(shù)據(jù)定義功能、數(shù)據(jù)操縱功能、數(shù)據(jù)控制

功能（只答對(duì)1?2個(gè)得1分）。

10.（2分）從數(shù)據(jù)庫管理系統(tǒng)的角度劃分?jǐn)?shù)據(jù)

庫系統(tǒng)的體系結(jié)構(gòu)，可分為外模式、模式和內(nèi)模

或3層（只答對(duì)1?2個(gè)得1分）。

11.（1分）數(shù)據(jù)對(duì)象：具有相同性質(zhì)的數(shù)據(jù)元

素的集合。

12.（1分）數(shù)據(jù)結(jié)構(gòu)：同一數(shù)據(jù)對(duì)象中各個(gè)數(shù)

據(jù)元素之間的一種或多種關(guān)系。

13.（1分）抽象數(shù)據(jù)類型：由一種數(shù)據(jù)結(jié)構(gòu)和

定義在其上的一組操作組成。

14.（2分）窮舉法中常用的列舉方法有順序列舉、排序例舉、組合例舉。

三、綜合題（69分）

1、（3分）何謂時(shí)間復(fù)雜度和空間復(fù)雜度。P13

2、（3分）什么是算法？算法和數(shù)據(jù)結(jié)構(gòu)的關(guān)系是什么？P13-14

3、（2分）簡述文件的結(jié)構(gòu)和組織。P192

4.（3分）簡述進(jìn)程可經(jīng)歷的三種基本調(diào)度狀態(tài)，并圖示說明這些狀態(tài)及其轉(zhuǎn)換（標(biāo)出轉(zhuǎn)換條件）。

P155

5.（4分）請(qǐng)簡述事務(wù)的ACID特性。

答:ACID就是：原子性（Atomicity）、一致性

（Consistency）、隔離性（Isolation）和持久性

（Durabilily）o

A、原子性：事務(wù)內(nèi)的所有操作是不可再分

的一個(gè)整體；要么都成功，要么都失敗。

C、一致性：如果事務(wù)成功地完成，那么系

統(tǒng)中所有變化將正確地應(yīng)用，系統(tǒng)處于有效狀

態(tài)。通過保證系統(tǒng)的任何事務(wù)最后都處于有效狀

態(tài)來保持一致性。

I、隔離型：在隔離狀態(tài)執(zhí)行事務(wù)，使它們

好像是系統(tǒng)在給定時(shí)間內(nèi)執(zhí)行的唯一操作。如果

有兩個(gè)事務(wù)，運(yùn)行在相同的時(shí)間內(nèi)，執(zhí)行相同的

功能，事務(wù)的隔離性將確保每一事務(wù)在系統(tǒng)中認(rèn)

為只有該事務(wù)在使用系統(tǒng)。

D、持久性：持久性意味著一旦事務(wù)執(zhí)行成

功，在系統(tǒng)中產(chǎn)生的所有變化將是永久的。

（備注：基本上答對(duì)一個(gè)要點(diǎn)即給1分，4個(gè)

要點(diǎn)都答對(duì)即給4分）

6.（9分）教師為了方便記錄和處理學(xué)生考勤建

立了一個(gè)“考勤數(shù)據(jù)庫”，里面有2張表，學(xué)生

信息表（學(xué)號(hào)、姓名、專業(yè)、班級(jí)，缺勤扣分小

計(jì)）、學(xué)生考勤表（學(xué)號(hào)，姓名，缺勤次數(shù)，每

次缺勤扣分，備注），其中“缺勤次數(shù)”、“缺

勤扣分小計(jì)”、“每次缺勤扣分”這3個(gè)屬性為

整數(shù)型，缺勤次數(shù)初始值為0、每次缺勤扣分預(yù)

設(shè)為2,每次點(diǎn)名時(shí)缺勤的同學(xué)對(duì)應(yīng)的“缺勤次

數(shù)”字段由老師手動(dòng)修改。

2.1該“考勤數(shù)據(jù)庫”是否符合第3范式，為什

么？（2分）

答：該數(shù)據(jù)庫不符合第3范式，因?yàn)榇嬖诜侵?/p>

屬性對(duì)鍵的傳遞函數(shù)依賴。比如：“學(xué)生考勤表”

里的非主屬性“姓名”,是“學(xué)生信息表”里的

鍵“學(xué)號(hào)”的傳遞函數(shù)依賴。學(xué)生信息表,學(xué)號(hào)

分學(xué)生信息表.姓名等生考勤表.姓名，這實(shí)際上

造成了姓名字段的冗余；同時(shí)，學(xué)生信息表里的

非主屬性“缺勤扣分小計(jì)”存在對(duì)學(xué)生考勤表里

的鍵“學(xué)號(hào)”的傳遞函數(shù)依賴，即學(xué)生考勤表.

學(xué)號(hào)令（缺勤次數(shù)，每次缺勤扣分）令學(xué)生信息

表.缺勤扣分小計(jì)，這實(shí)際上也造成了數(shù)據(jù)冗余。

（答對(duì)要點(diǎn)即給分）

【此題考點(diǎn)是讓學(xué)生理解范式的作用，讓學(xué)生

理解在數(shù)據(jù)庫設(shè)計(jì)中需要兼顧時(shí)間效率和空間

效率，并找到一個(gè)平衡點(diǎn)。范式越高則空間效率

越高，但是時(shí)間效率越低，因?yàn)楸聿鸱值倪^細(xì)之

后，表間連接查詢要費(fèi)時(shí)間的；范式越低，則時(shí)

間效率越高，但是空間效率越低，至于第一范式

就是一般不能用的，因?yàn)闀?huì)出現(xiàn)刪除異常、插入

異常和更新異常。為什么第3范式對(duì)數(shù)據(jù)庫來說

是最重要的，因?yàn)榈?范式在滿足一般數(shù)據(jù)庫應(yīng)

用的時(shí)間和空間效率的平衡點(diǎn)方面比較合適】

2.2寫出SQL語句，根據(jù)學(xué)生考勤表里的“缺勤

次數(shù)”和“每次缺勤扣分”來修改學(xué)生信息表里

的“缺勤扣分小計(jì)”。（3分）【該題的考點(diǎn)是

讓同學(xué)們理解數(shù)據(jù)庫引擎的掃描工作方式，對(duì)于

數(shù)據(jù)庫來說，多表之間的聯(lián)合查詢是不可避免

的】

答：

寫法1（用元組變量）：

update學(xué)生信息表set缺勤扣分小計(jì)二b.缺

勤次數(shù)*b.每次缺勤扣分from

學(xué)生信息表a,學(xué)生考勤表bwherea.學(xué)號(hào)

=b.學(xué)號(hào)

寫法2（用自然連接）：

update學(xué)生信息表set學(xué)生信息表.缺勤

扣分小計(jì)二學(xué)生考勤表.缺勤次數(shù)*學(xué)生考勤表.

每次缺勤扣分from學(xué)生信息表innerjoin學(xué)

生考勤表on學(xué)生信息表.學(xué)號(hào)=考勤表.學(xué)號(hào)

寫法3（用嵌套查詢）:

update學(xué)生信息表set學(xué)生信息表.缺勤扣分

小計(jì)二

（select學(xué)生考勤表.缺勤次數(shù)*學(xué)生考勤表.

每次缺勤扣分from學(xué)生考勤表where學(xué)生信

息表.學(xué)號(hào)二學(xué)生考勤表.學(xué)號(hào)）

（等等，寫出一個(gè)即給分）。

備注：

Update學(xué)生信息表.缺勤扣分小計(jì)二學(xué)生考勤表.

缺勤次數(shù)*學(xué)生考勤表.每次缺勤扣分where學(xué)

生信息表.學(xué)號(hào)二學(xué)生考勤表.學(xué)號(hào)（這是錯(cuò)誤

的，數(shù)據(jù)庫系統(tǒng)無法進(jìn)行檢索執(zhí)行，不給分或者

象征性的給1分）。

2.3寫出SQL語句，查詢?nèi)鼻诖螖?shù)最多的那些學(xué)

生清單（包含：學(xué)號(hào)、班級(jí)），并按班級(jí)分組或

排序。（2分）

答：

這個(gè)是絕對(duì)送分題，不考慮學(xué)生信息表的缺

勤扣分小計(jì)字段是否更新，在第1個(gè)表里進(jìn)行查

詢即可。

比如：select學(xué)號(hào)，班級(jí)from學(xué)生信息表

where缺勤扣分小計(jì)二（selectmax（缺勤扣分小

計(jì)）from學(xué)生信息表）orderby班級(jí)

等等，只要能夠查詢到結(jié)果的SQL表達(dá)都行。

2.4寫出SQL語句，對(duì)考勤數(shù)據(jù)庫里的這兩張表

進(jìn)行連接查詢，查詢結(jié)果包含這兩張表的所有字

段。（2分）

這個(gè)是送分題，普通的2個(gè)表的連接。答案

略

7.（4分）已知順序表中有卬至h共n個(gè)元素，在

第i（I"+1）個(gè)位置上插入一個(gè)元素x,試計(jì)

算插入操作的時(shí)間復(fù)雜度。（寫出計(jì)算過程）

解：i在1、2、3…n+1上服從均勻分布，概

率為移動(dòng)元素的次數(shù)為.?平

均移動(dòng)次數(shù)為耳=9）=砧年+刖T+D....

時(shí)間復(fù)雜度為。（〃）。

8.（3分）如下圖所示鏈表，在第i-1和第i節(jié)

點(diǎn)之間插入一個(gè)新節(jié)點(diǎn)x,已知指向第i-1個(gè)節(jié)

點(diǎn)的指針為P，指向新節(jié)點(diǎn)x的指針為s,填寫

完成該插入操作的代碼語句。

p

s->next=p->next;

p->next=s;

9.（3分）如下圖所示鏈表，指向第i-1個(gè)節(jié)點(diǎn)

的指針為P，現(xiàn)在要?jiǎng)h除第i個(gè)節(jié)點(diǎn)，試寫出該

刪除操作的代碼語句。

s=p->next;

p->next=p->next->next;或

p->next=s->next;

free（s）;

10.（4分）在程序退出時(shí)，需要銷毀鏈表以釋

放內(nèi)存空間，否則會(huì)產(chǎn)生內(nèi)存泄露。假設(shè)有如下

鏈表銷毀函數(shù)，參數(shù)Head為指向鏈表頭節(jié)點(diǎn)的

指針，試完成函數(shù)體中代碼。

voidDestroyList(LinkList*Head)

LinkList*p;

while(Head)

p=Head;

Head=Head->next;

free(p);

11.（4分）如下圖所示鏈棧結(jié)構(gòu)，將值X的元

素壓棧，試完成以下壓棧函數(shù)。

top-?next

next

next

NULL

voidPushLinkStack(structLinkStack*

top,DataTypeX)

structLinkStack*p;

p=(struct

LinkStack*)malloc(sizeof(struct

LinkStack));

p->data=X;

p->next=top;

top=p;

}

12.(5分)運(yùn)用棧編碼實(shí)現(xiàn)十進(jìn)制數(shù)(正整數(shù))

到十六進(jìn)制數(shù)的轉(zhuǎn)換。

intmain(intargc,char*argv[])

(

intstack[10];

inttop=0;

intN=0;

printf(”請(qǐng)輸入十進(jìn)制數(shù):\n");

scanf&N);

do

|

stack[top]=N%16;

N=N/16;

top++;

}while(N!=0);

printf("對(duì)應(yīng)的十六進(jìn)制數(shù):\n");

for(top=top-l;top>=0;top一)

printfstack[top]);

printf("\n");

return0;

)

13.(2分)有如圖所示的二叉樹采用順序存儲(chǔ)

結(jié)構(gòu)，畫出二叉樹示意圖。

2

1257

14.（5分）有如下圖所示二叉樹，試寫出先序

遍歷的代碼和先序遍歷的輸出（假設(shè)節(jié)點(diǎn)