華中科技大學(xué)命令式計(jì)算原理-《命令式計(jì)算原理》樣卷二及參考答案

計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2020-2021學(xué)年第2學(xué)期考試試卷

命令式計(jì)算原理A卷參考答案

姓名班級(jí)學(xué)號(hào)考試日期2021-7-1

、一

—?

題號(hào)二三四五八七總分核對(duì)

題分106209251515100

得分

得分評(píng)卷人

'一、整數(shù)類型與大O符號(hào)(10分)

1.(6分)C0語言中，對(duì)于以下每個(gè)陳述，請(qǐng)判定其是真還是假。如果是真,

請(qǐng)簡(jiǎn)單說明理由；如果是假，請(qǐng)?zhí)峁┮粋€(gè)反例。

(1)如果x和y是int類型，且y>=x,那么，x+(y?x)/2=(x+y)/2。

假。x=INTMAXy-INTMAX

(2)如果x是int類型，那么，(x?2)?2=xo

假°x=INTMIN

(3)如果x、y和z是int類型，那么，(x+y)+z=x+(y+z)°

真。用模運(yùn)算來處理溢Hi時(shí)，加法結(jié)合律始終成立。

2.(4分)填空，大0符號(hào)的定義：

g(n)GO(f(n))當(dāng)且僅當(dāng)___________________________

存在n0和c>0,對(duì)于所有n>=nO使得h(n)<=c*f(n)

得分評(píng)卷人

■二、線性查找(6分)

本題我們探究數(shù)組搜索問題。我們將使用尖數(shù)組，而不是有序數(shù)組。如果一

個(gè)整型數(shù)組從第一個(gè)元素開始到峰值元素，元素值嚴(yán)格遞增，且從峰值元素到數(shù)

組最后一個(gè)元素，元素值嚴(yán)格遞減，我們稱該整型數(shù)組為尖數(shù)組。尖數(shù)組的嚴(yán)格

遞增段或嚴(yán)格遞減段可以為空，這意味著峰值元素既可以是第一個(gè)元素，也可以

是最后一個(gè)元素。

我們將在尖數(shù)組的相關(guān)約定中使用函數(shù)is_peaked和gt.seg,在約定中不允

許使用這兩個(gè)函數(shù)外的其他函數(shù)，但可以使用一般算術(shù)運(yùn)算、關(guān)系運(yùn)算，及數(shù)組

訪問運(yùn)算([])。

boolis_peaked(int[]A,intlower,intupper)

//?requires0<=lower&&lower<=upper&&upper<=Mength(A);

boolgt_seg(intx,int[]A,intlower,intupper)

//?requires0<=lower&&lower<=upper&&upper<=\length(A);

這兩個(gè)函數(shù)說明如下：

is_peaked(A,lower,upper)表示數(shù)組段A[lower::upper)是尖的。

gt_seg(x,A,lower,upper)表示x>A[lower::upper),即x嚴(yán)格大于下標(biāo)從

lower(包括在內(nèi))到upper(不包括在內(nèi))的所有元素汗

把函數(shù)find_peak」in填寫完整，使其實(shí)現(xiàn)對(duì)非空尖數(shù)組進(jìn)行線性搜索，返回

峰值元素的下標(biāo)。你的代碼必須滿足所有給定的約定，而你不能改變這些約定和

代碼。你不得調(diào)用函數(shù)gt_seg和is_peaked,這兩個(gè)函數(shù)僅用于約定。

你填寫的循環(huán)體應(yīng)該有一個(gè)或兩個(gè)語句。如果只有一個(gè)語句，那么將另一個(gè)

空留著不填。

intfind_peak_lin(int[]A,intn)

//?requires0<n&&n<=Menglh(A);

//@requiresis_peaked(A,0,n);

//@ensures0<=\result&&\result<n;

//@ensuresgt_seg(A[\result],A,0,\result);

//?ensuresgt_seg(A[\result],A,\resull+l,n);

(

inti=0;

while(ivn-1&&A[i]<A[i+A)

//@loop_invariant0<=i&&i<=n-1;

//@loop_invariantgt_seg(A[i],A,0,i);

//@loop_invariantis_peaked(A,i,n);

return_i_________________________________________

得分評(píng)卷人

---------------三、二分查找與約定（20分）

我們接著使用上題中定義的尖數(shù)組進(jìn)行編程。

1.（14分）將函數(shù)find_peak_bin填寫完整，使其實(shí)現(xiàn)對(duì)非空尖數(shù)組進(jìn)行二

分查找，返回峰值元素下標(biāo)。函數(shù)flnd_peak_bin的前置條件和后置條件與上題中

線性搜索函數(shù)find_peak_lin的相同。

這一次，我們已經(jīng)給出所有執(zhí)行代碼，要求你填寫循環(huán)不變量。你填寫的循

環(huán)不變量應(yīng)足夠強(qiáng)壯，以確保代碼中對(duì)數(shù)組的所有存取是安全的，并能夠結(jié)合循

環(huán)條件來證明函數(shù)后置條件成立。你不得修改代碼、函數(shù)前置條件和后置條件。

你填寫的循環(huán)不變量如果不需要四個(gè)，則將剩下的空留下不填；如果多于四個(gè)，

則在右邊空白處補(bǔ)充。我們己留@@$5?11注解選項(xiàng)，你可用來填寫簡(jiǎn)明宣稱來幫助

你進(jìn)行代碼推理，也有助于我們分步計(jì)分。

intfind_peak_bin(int[1A,intn)

//@requires0<n&&n<=Mength(A);

//?requiresis_peaked(A,0,n);

//@ensures0<=\result&&\result<n;

//@ensuresgt_seg(A[\result],A,0,\result);

//@ensuresgt_seg(A[\result],A,\result+l,n);

(

intlower=0;

intupper=n-1;

while(lower<upper)

//@loop_invariant0〈二lower&&lower〈二upper&&uppervn;

//@loop_invariantis-eaked(A,lower,叩網(wǎng)+1):

//@loop_invariantgtseg(A「lower],A,OJower);

//@loop_invariantglseg(A[upper],A,upper+1,n);

(

intmid=lower+(upper-lower)/2;

//@assertmid<upper;/*optional*/

if(Afmidl<A[mid+1])

lower=mid+1;

else//@assertAlmidl>A[mid+1];/*optional*1

upper=mid;

I

//@assertlower二二upper;/*optional*/

returnlower;

)

2.(2分)寫一個(gè)不包含常量的表達(dá)式，其值隨每次循環(huán)嚴(yán)格遞減且存在下

限，從而保證循環(huán)終止。該表達(dá)式的下限值是多少？

表達(dá)式：uiDer-lower的值隨每次循環(huán)遞減，且下限值為0。

3.(2分)對(duì)于有4,000,000個(gè)元素的尖數(shù)組，最壞情況下while循環(huán)體將執(zhí)

行多少次，直到找到峰值元素？

4,000,000略小于2-*2。*2?=22?

所以，最壞情況下while循環(huán)體將執(zhí)行22次，直到找到峰值元素。

4.(2分)find_peak_bin(A,n)的漸近復(fù)雜性如何？用大O表示，不必解釋

你的答案。

O(long(n))

得分評(píng)卷人

四、棧和隊(duì)列(9分)

以下是棧的接口定義。

typedefstructstack*stack:

stacks_new();/*0(1);createnew,emptystack*/

bools_empty(stackS);/*0(1);checkifstackisempty*/

voidpush(intx,stackS);/*0(1);pushelementontostack*/

intpop(stackS);/*0(1);popelementfromstack*/

本題不必寫注釋。假設(shè)所有函數(shù)的stack類型的參數(shù)都不是NULLO

1.(2分)編寫函數(shù)rev(stackS,stackD)。D最初是空的，當(dāng)函數(shù)rev返回時(shí),

D應(yīng)該以相反的次序包含S中的所有元素，而S應(yīng)為空。

voidrev(stackS,stackD)

//@requiress_empty(D);

//?ensuress_empty(S);

while(!semDty(S))

push(pop(S),D)：

)

現(xiàn)在我們?cè)O(shè)計(jì)一種新的隊(duì)列實(shí)現(xiàn)。一個(gè)隊(duì)列由兩個(gè)棧：in和。ut組成。入隊(duì)

時(shí)，我們總是將元素加入in,而出隊(duì)時(shí)則從。ut移除元素。必要時(shí)，我們可以調(diào)

用上面的函數(shù)rev將棧in中元素反轉(zhuǎn)到棧out中去。

structqueue{

stackin;

stackout;

}；

typedefstructqueue*queue;

2.(2分)編寫入隊(duì)函數(shù)enq。

voidenq(queueQ,intx)

{

Dush(x,

)

3.(3分)編寫出隊(duì)函數(shù)deq。如果deq被不正確調(diào)用，用適當(dāng)?shù)腶ssert語句

終止計(jì)算。

intdeq(queueQ)

(

assert(!semmy(Q->in)||!semDtyQ>out)

"cannotdequeuefromemptyaueue");

if(semDty(O->out))f

rev(Q>in,O?《out);

leturnpopQ>oul);

現(xiàn)在我們分析這種數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性。我們計(jì)算底層棧的push操作和pop操

作總次數(shù)。

4.（2分）在最壞情況下，函數(shù)enq的復(fù)雜性如何？在最壞情況下，函數(shù)deq

的復(fù)雜性又如何？用大O符號(hào)來表示你的答案，m表示隊(duì)列中已存元素的總數(shù)。

最壞情況下，函數(shù)enq的復(fù)雜性為：0（1）：

而函數(shù)deq的復(fù)雜性為：O（m）。

得分評(píng)卷人

----------------五、分?jǐn)偡治觯?5分）

當(dāng)實(shí)現(xiàn)一個(gè)無界數(shù)組時(shí)，當(dāng)要插入新元素，而數(shù)組的size己達(dá)到limit時(shí)，就

將limil增加到原來limit的4/3倍，如果結(jié)果不是整數(shù)，就向上取整?？紤]在數(shù)

組尾部增加一個(gè)新元素的uba_add操作，只計(jì)算寫操作的次數(shù)，讀操作和分配內(nèi)

存的時(shí)間忽略不計(jì)。

1.（10分）以下證明插入操作的分?jǐn)倳r(shí)間開銷是一個(gè)常數(shù)?？瞻撞糠质钦?qǐng)你

幫助完成的內(nèi)容，請(qǐng)按一般情況填入以L、k為變量的表達(dá)式。為了不用考慮取

整問題，假設(shè)其中的L是3的倍數(shù)。

假定此時(shí)我們剛得到一個(gè)新的limit=L,Wk>0個(gè)籌碼。接下來都是插入操

作。每次操作都是在尾部插入元素，增加size。在size沒有達(dá)到limit時(shí)，每次插

入要寫入1次，花掉1個(gè)籌碼，另外還需要攢4個(gè)籌碼。

在L/4次插入之后，size會(huì)到達(dá)limit,又需要增加數(shù)組的

limit,這時(shí)需要分配一個(gè)limit為4/3*L的新數(shù)組，并

且將L個(gè)元素從舊數(shù)組復(fù)制到新數(shù)組。此刻還剩

下k個(gè)籌碼。此數(shù)非負(fù)，因此每次插入

操作需要常數(shù)分?jǐn)倳r(shí)間開銷。

2.（4分）從limil=l的空無界數(shù)組開始，連續(xù)插入n個(gè)元素，需要的寫操作

次數(shù)逼近上界（不寫大0形式）一5n一：如果改為每次將limit增加到原

來的3/2倍的策略，連續(xù)插入n個(gè)元素，需要的寫操作次數(shù)逼近上界（不寫大O

形式）4n。

接下來我們討論一種新技術(shù)，用來消除原有方法在limit加倍時(shí)突然增加的時(shí)

間消耗。為簡(jiǎn)化問題，我們只考慮將limit增加到原來limit的2倍的策略。策略

是當(dāng)我們創(chuàng)建好一個(gè)2倍limit的大數(shù)組后，我們不是馬上將原小數(shù)組中所有元素

都復(fù)制到大數(shù)組，而是每次大數(shù)組末尾增加一個(gè)新元素時(shí).，才將一個(gè)小數(shù)組中的

元素復(fù)制到大數(shù)組。這樣就將limit增加時(shí)突然增加的時(shí)間消耗分?jǐn)偟綄淼拿恳?/p>

次在數(shù)組末尾增加新元素時(shí)，消除了原方案插入新元素的處理時(shí)間出現(xiàn)不平穩(wěn)劇

烈變化的弊病。

為此，我們需要同時(shí)維護(hù)原小數(shù)組中未復(fù)制的元素和新大數(shù)組中已復(fù)制的和

新增加的元素。用下標(biāo)變量jump表示小數(shù)組的最后一個(gè)未復(fù)制元素的下標(biāo)，next

表示大數(shù)組最后一個(gè)元素的下標(biāo)+1,如下圖所示，小數(shù)組命名為short,大數(shù)組命

名為longo此前小數(shù)組short里放有元素“a”“b"％”。當(dāng)插入元素“d”時(shí)，

小數(shù)組short已滿，創(chuàng)建limit增加到原來的2倍的大數(shù)組long。這時(shí)將“d”插入

到大數(shù)組的下標(biāo)為limit/2的地方，next指向“d”后面一格。這時(shí)只將小數(shù)組的

最后一個(gè)元素“c”復(fù)制到大數(shù)組，jump指向“c”前面一格。如果再增加一個(gè)元

素“e"，next加1,則再復(fù)制元素“b"，jump減1。如此類推。下標(biāo)為0的單元

格空著不用，從下標(biāo)為1的單元格開始存放元素。

short

limit/2

long"c〃"d"____________________

0jumpnextlimit

以下是實(shí)現(xiàn)此修改方案的代碼。假定代碼注釋中的條件都在is_uba函數(shù)中做

了檢查。

structuba{

intlimit;/*limit>0*/

intnext;/*1<=next&&next<=limit*/

intjump;/*jump+next==limit-1*/

elem[]short;/*\length(short)=limit/2*/

elem[]long;怦\length(long)=limit*/

typedefstructuba*uba;

boolis_uba(ubaL);

3.(4分)完成以下函數(shù)，實(shí)現(xiàn)從上述的無界數(shù)組中讀取下標(biāo)為i的元素。

elemuba_get(ubaL,inti)

//@rcquiresis_uba(L);

//@requires0vi&&ivL->next;

(

if(i>Lojump)

returnL->long[i];

else

returnL->short[i];

4.(2分)完成以下函數(shù)，實(shí)現(xiàn)給上述無界數(shù)組limit加倍。

(提示：遵守?cái)?shù)據(jù)結(jié)構(gòu)不變性)

voiduba_double(ubaL)

//@requiresis_uba(L);

//@ensuresis_uba(L);

(

L->Iimit=2*L->limit;

L->short=L->long;

L->long=alloc_array(elem,L->limit);

L->jump=L->next-l(或者1或者L->limit-L->next-l)

return;

}

5.(5分)完成以下函數(shù)，實(shí)現(xiàn)給上述的無界數(shù)組在末尾增加一個(gè)元素。

(提示：遵守?cái)?shù)據(jù)結(jié)構(gòu)不變性)

voidaddend(ubaL,eleme)

//?requiresis_uba(L);

//?ensuresis_uba(L);

(

if(L->next==L->limit)

uba_double(L);

L->Long(L->next)=e：

L-next++：

L->Long「L->iump]=L->short[L->jump]：

得分評(píng)卷人

■六、二分查找樹（15分）

1.（7分）以下是二分查找樹中查找一個(gè)元素的庫函數(shù)，是用遞歸實(shí)現(xiàn)的，試

改成不用遞歸而用循環(huán)實(shí)現(xiàn)。

elemtree_lookup(tree*T,keyk)

//@requiresis_ordtree(T);

//@ensures\result==NULL||key_compare(elem_key(\result),k)==0;

(

if(T==NULL)returnNULL;

intr=key_compare(k,elem_key(T->data));

if(r==0)

returnT->data;

elseif(r<0)

returntree_lookup(T->left,k);

else//@assertr>0;

returntree_lookup(T->righl,k);

)

elemtree_lookup(tree*T,keyk)

//?requiresis_ordtree(T);

//@ensures\result==NULL||key_compare(elem_key(\result),k)==0;

(

while(T!=NULL){

intr=key_compare(k,elem_key(T->data));

if(r==0)returnT->data;

elseif(r<0)T=T->left;

else//@assertr>0;

T=T->right;

//@assertT==NULL;

returnNULL;

2.(8分)以下是二分查找樹中插入一個(gè)元素所用到的庫函數(shù)，是用遞歸實(shí)現(xiàn)

的，試改成不用遞歸而用循環(huán)實(shí)現(xiàn)。

tree*tree_insert(tree*T,eleme)

//?requiresis_ordtree(T);

//?requirese!=NULL;

//?ensuresis_ordtree(\result);

(

if(T==NULL){

/*createnewnodeandreturnit*/

T=alloc(structtree_node);

T->data=e;

T->left=NULL;

T->right=NULL;

returnT;

)

intr=key_compare(elem_key(e),elem_key(T->data));

if(r==0)

T->data=e;/*modifyinplace*/

elseif(r<0)

T->left=tree_insert(T->left,e);

else//@assertr>0;

T->right=tree_insert(T->right,e);

returnT;

)

tree*tree_insert(tree*T,eleme)

//?requiresis_ordtree(T);

//?requirese!=NULL;

//?ensuresis_ordtree(\result);

(

R=T;

intr=0;

while(T!=NULL){

r=key_compare(elem_key(e),elem_key(T->data));

P=T;

if(r==0){

T->data=e;/*modifyinplace*/

return(R);

}elseif(r<0)

T=T->left;

else//@assertr>0;

T=T->right;

}

//@assertT==NULL;

/*createnewnodeandreturnit*/

T=alloc(structtree_node);

T->data=e;

T->left=NULL;

T->right=NULL;

if(r==O)R=T;

elseif(r<0)

P->left=T;

else//@assertr>0;

P->right=T;

return(R);

得分評(píng)卷人

■七、C語言的安全性(15分)

C語言中，如果一條語句的行為是有定義的，則認(rèn)為它的執(zhí)行是安全的。安

全前置條件(簡(jiǎn)稱前置條件)是一個(gè)斷言，如果該斷言為真，則保證接下來的語

句的執(zhí)行是安全的。例如，假定申明了變量x,并且用某個(gè)未知數(shù)值進(jìn)行了初始

化，則斷言x<0是x加1語句的安全前置條件?？杀磉_(dá)為：

ASSERT(x<0);

x=x+1;

前置條件x<0可以保證后面語句的安全性。但是它對(duì)x所加的限制太強(qiáng)了，

因?yàn)檫€有其它x值也能使得x