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

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

命令式計算原理A卷參考答案

姓名班級學號考試日期2021-7-1

、一

—?

題號二三四五八七總分核對

題分106209251515100

得分

得分評卷人

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

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

請簡單說明理由；如果是假，請?zhí)峁┮粋€反例。

(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)°

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

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

g(n)GO(f(n))當且僅當___________________________

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

得分評卷人

■二、線性查找(6分)

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

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

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

遞增段或嚴格遞減段可以為空，這意味著峰值元素既可以是第一個元素，也可以

是最后一個元素。

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

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

訪問運算([])。

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);

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

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

gt_seg(x,A,lower,upper)表示x>A[lower::upper),即x嚴格大于下標從

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

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

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

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

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

空留著不填。

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_________________________________________

得分評卷人

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

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

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

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

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

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

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

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

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

則在右邊空白處補充。我們己留@@$5?11注解選項，你可用來填寫簡明宣稱來幫助

你進行代碼推理，也有助于我們分步計分。

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分)寫一個不包含常量的表達式，其值隨每次循環(huán)嚴格遞減且存在下

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

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

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

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

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

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

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

你的答案。

O(long(n))

得分評卷人

四、棧和隊列(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ù)的stack類型的參數(shù)都不是NULLO

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

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

voidrev(stackS,stackD)

//@requiress_empty(D);

//?ensuress_empty(S);

while(!semDty(S))

push(pop(S),D)：

)

現(xiàn)在我們設計一種新的隊列實現(xiàn)。一個隊列由兩個棧：in和。ut組成。入隊

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

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

structqueue{

stackin;

stackout;

}；

typedefstructqueue*queue;

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

voidenq(queueQ,intx)

{

Dush(x,

)

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

終止計算。

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)的復雜性。我們計算底層棧的push操作和pop操

作總次數(shù)。

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

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

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

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

得分評卷人

----------------五、分攤分析（25分）

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

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

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

存的時間忽略不計。

1.（10分）以下證明插入操作的分攤時間開銷是一個常數(shù)。空白部分是請你

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

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

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

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

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

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

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

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

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

操作需要常數(shù)分攤時間開銷。

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

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

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

形式）4n。

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

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

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

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

元素復制到大數(shù)組。這樣就將limit增加時突然增加的時間消耗分攤到將來的每一

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

烈變化的弊病。

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

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

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

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

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

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

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

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

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

short

limit/2

long"c〃"d"____________________

0jumpnextlimit

以下是實現(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ù)，實現(xiàn)從上述的無界數(shù)組中讀取下標為i的元素。

elemuba_get(ubaL,inti)

//@rcquiresis_uba(L);

//@requires0vi&&ivL->next;

(

if(i>Lojump)

returnL->long[i];

else

returnL->short[i];

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

(提示：遵守數(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ù)，實現(xiàn)給上述的無界數(shù)組在末尾增加一個元素。

(提示：遵守數(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]：

得分評卷人

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

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

改成不用遞歸而用循環(huán)實現(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分)以下是二分查找樹中插入一個元素所用到的庫函數(shù)，是用遞歸實現(xiàn)

的，試改成不用遞歸而用循環(huán)實現(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);

得分評卷人

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

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

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

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

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

ASSERT(x<0);

x=x+1;

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

因為還有其它x值也能使得x