期中考試試卷答案

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦期中考試試卷答案一、單項挑選題（共15小題，每小題2分，共30分）

1.一個棧的輸入序列為12345，則下列序列中不行能是棧的輸出序列的是（b）。

A、23415

B、54132

C、23145

D、15432

2.設(shè)循環(huán)隊列中數(shù)組的下標范圍是1-n，其頭尾指針分離為f和r，則其元素個數(shù)為（d）。

A、r-f

B、r-f+1

C、(r-f)modn+1

D、(r-f+n)modn

3.對于C語言的二維數(shù)組DataTypeA[m][n],每個數(shù)據(jù)元素占K個存儲單元，二維數(shù)組中隨意元素a[i,j]的存儲位置可由(c)式確定.

A、Loc[i,j]=A[m,n]+[(n+1)*i+j]*k

B、Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k

C、Loc[i,j]=loc[0,0]+[n*i+j]*k

D、Loc[i,j]=[(n+1)*i+j]*k

4．假如以鏈表作為棧的存儲結(jié)構(gòu)，則退棧操作是(B)

A、必需判別棧是否滿

B、必需判別棧是否空

C、判別棧元素的類型

D、對棧不做任何操作

5．基于三元組的稀疏矩陣，對每個非零元素aij,可以用一個（b）唯一確定。

A、非零元素

B、三元組(i,j,aij)

C、aij

D、④i,j

6.設(shè)有一挨次棧S，元素s1,s2,s3,s4,s5,s6依次進棧，假如6個元素出線的挨次是s2,s3,s4,s6,s5,s1,則棧的容量至少應當是（B）

A、2

B、3

C、5

D、6

7．算法指的是（D）

A．計算機程序B．解決問題的計算辦法C．排序算法D．解決問題的有限運算序列8．線性表采納鏈式存儲時，結(jié)點的存儲地址（B）

A．必需是不延續(xù)的B．延續(xù)與否均可C．必需是延續(xù)的D．和頭結(jié)點的存儲地址相延續(xù)9．將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時光復雜度為（c）

A．O（1）B．O（n）C．O（m）D．O（m+n）

10．由兩個棧分享一個向量空間的益處是：（b）

A．削減存取時光，降低下溢發(fā)生的機率B．節(jié)約存儲空間，降低上溢發(fā)生的機率

C．削減存取時光，降低上溢發(fā)生的機率D．節(jié)約存儲空間，降低下溢發(fā)生的機率11．設(shè)數(shù)組data[m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針front值為（d）

A．front=front+1B．front=(front+1)%(m-1)C．front=(front-1)%mD．front=(front+1)%m12．如下陳述中正確的是（a）

A．串是一種特別的線性表B．串的長度必需大于零

C．串中元素只能是字母D．空串就是空白串

13．一個非空廣義表的表頭（d）

A．不行能是子表B．只能是子表C．只能是原子D．可以是子表或原子

14、數(shù)據(jù)結(jié)構(gòu)是討論數(shù)據(jù)的（c）以及它們之間的關(guān)系。

A)抱負結(jié)構(gòu)和物理結(jié)構(gòu)B)抱負結(jié)構(gòu)和抽象結(jié)構(gòu)

C)物理結(jié)構(gòu)和規(guī)律結(jié)構(gòu)D)抽象結(jié)構(gòu)和規(guī)律結(jié)構(gòu)

15．設(shè)單鏈表中指針p指向接點A，若要刪除A后的結(jié)點（若存在），則應執(zhí)行的語句是(a)

A．p->next=p->next->next;B．p=p->next;

C．p=p->next->next;D．p->next=p;

二、填空題（共10小題，每小題2分）

1．數(shù)據(jù)的規(guī)律結(jié)構(gòu)是從規(guī)律關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的__存儲結(jié)構(gòu)___無關(guān)，是自立于計算機的。

2.設(shè)S1=“good”，S2=“”，S3=“book”，則S1，S2和S3依次聯(lián)接后的結(jié)果是goodbook。

3.假設(shè)三維數(shù)組A[10][9][8]按行優(yōu)先挨次存儲，若每個元素占3個存儲單元，且首地址為100，則元素A[9][8][7]的存儲地址是667。

4．在一個帶頭結(jié)點的單循環(huán)鏈表中，p指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針head可用p表示為head=_p－>next－>next____。

5．棧頂?shù)奈恢檬请S著_進棧和退棧____操作而變化的。

6．在串S=“structure”中，以t為首字符的子串有__12___個。

7．現(xiàn)有一“遺傳”關(guān)系：設(shè)x是y的父親，則x可以把它的屬性遺傳給y。表示該遺傳關(guān)系最適合的數(shù)據(jù)結(jié)構(gòu)為樹。

8．在線性結(jié)構(gòu)中，第一個結(jié)點前驅(qū)結(jié)點，其余每個結(jié)點有且惟獨個前驅(qū)結(jié)點；最后一個結(jié)點_____后續(xù)結(jié)點，其余每個結(jié)點有且惟獨_______個后續(xù)結(jié)點。1、沒有、1、沒有、1

9.在一個長度為n的循環(huán)鏈表中，刪除其元素值為x的結(jié)點的時光復雜度為____。

10.假如入棧序列是1，3，5，…，97，99，且出棧序列的第一個元素為99，則出棧序列中第30個元素為______。

三、推斷題（每題1分，共5分）

1.線性表的規(guī)律挨次與物理挨次總是全都的。(F)

2.線性表的挨次存儲表示優(yōu)于鏈式存儲表示。(F)

3．假如一個串中的全部字符均在另一串中浮現(xiàn)，則說前者是后者的子串。(F)

4.空串與空格串是相同的(F)

5．進棧操作時，必需推斷棧是否滿。(F)

四、程序填空題（每空1分，共5分）

下面是在單鏈表的第i個位置之前插入一個元素的算法，請將算法補齊。

statusListInsert_L(LinkListj=0;

while(p++j;}

if(!p||j>i-1)returnERROR;

s=(LinkList)(sizeof(LNODE));

s->data=;

___________=p->next;

p->next=;returnOK;}

p->next

malloc