數(shù)據(jù)結(jié)構(gòu)期末考試試題及復(fù)習(xí)資料

數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案

一、選擇題

1.評價一個算法時間性能的主要標(biāo)準(zhǔn)是()。

A、算法易于調(diào)試

B、算法易于理解

C、算法的穩(wěn)定性和正確性

D、算法的時間復(fù)雜度

2.計算機算法具備有輸入、輸出、（）等五個特性。

A、可行性、可移植性和可擴充性

B、可行性、確定性和有窮性

C、確定性、有窮性和穩(wěn)定性

D、易讀性、穩(wěn)定性和安全性

3.帶頭結(jié)點的單鏈表head為空的判定條件是（）。

A、head==NULL

B、head->next==NULL

C、head->next==head

D、head！=NULL

4.以下關(guān)于線性表的說法不正確的是()。

A、線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。

B、線性表中包含的數(shù)據(jù)元素個數(shù)不是任意的。

C、線性表中的每個結(jié)點都有且只有一個直接前趨和直接后繼。

D、存在這樣的線性表：表中各結(jié)點都沒有直接前趨和直接后繼。

5.在順序表中，只要知道()，就可在相同時間內(nèi)求出任一結(jié)點的存儲地址。

A、基地址

B、結(jié)點大小

C、向量大小

D、基地址和結(jié)點大小

6.()運算中，使用順序表比鏈表好。

A、插入

B、刪除

C、根據(jù)序號查找

D、根據(jù)元素值查找

7.一個長度為n的順序表中，向第i個元素之前插入一個新元素時，需要向后移動（）個元

A、n-i

B、n-i+1

C、n-i-1

D、i

8.()適合作為經(jīng)常在首尾兩端操作線性表的存儲結(jié)構(gòu)。

A、順序表

B、單鏈表

C、循環(huán)鏈表

D、雙向鏈表

9.棧和隊列的共同點是()

A、都是先進后出

B、都是先進先出

C、只允許在端點處插入和刪除元素

D、沒有共同點

10.一個隊列的入列序列是1234，則隊列的輸出序列是()。

A、4321

B、1234

C、1432

D、3241

11.隊列與一般的線性表的區(qū)別在于()。

A、數(shù)據(jù)元素的類型不同

B、運算是否受限制

C、數(shù)據(jù)元素的個數(shù)不同

D、邏輯結(jié)構(gòu)不同

12.“假上溢”現(xiàn)象會出現(xiàn)在()中。

A、循環(huán)隊列

B、隊列

C、鏈隊列

D、順序隊列

⑦P=L;

二、填空題

1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)被分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖結(jié)構(gòu)。

2．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)被分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)。

3．下面程序段的時間復(fù)雜度是O（n）。

i=s=0;

while(s<n)

{i++;

s++;;

}

4．樹型結(jié)構(gòu)和圖形結(jié)構(gòu)合稱是非線性結(jié)構(gòu)。

5．在長度為n的順序存儲線性表的第i個元素（1≤i≤n）之前插入一個元素時，

需要向后移動n-i+1個元素。

6．在一個長度為n的順序存儲的線性表中，刪除第i個元素（1≤i≤n）時，

需要向前移動n-i個元素。

7．指針p指向非空循環(huán)單鏈表head的尾結(jié)點，則p滿足p->next=head。

8．已知L是帶頭結(jié)點的非空單鏈表，且P結(jié)點既不是第一個數(shù)據(jù)結(jié)點，也不是最后一個結(jié)點，試的答案中選擇合適的語句序列，實現(xiàn)刪除P結(jié)點的直接后繼結(jié)點的語句序列是⑥①⑨。

①P->next=P->next->next;

②P=P->next->next;

③while(P->next!=Q)P=P->next;

④while(P->next->next=Q)P=P->next;

⑤Q=P;

⑥Q=P->next;

⑧L=L->next;

⑨free(Q);

9．在線性結(jié)構(gòu)中，第一個結(jié)點無前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點。

10．單鏈表是線性表的鏈?zhǔn)酱鎯Ρ硎尽?/p>

11．棧是限定僅在表尾進行插入或刪除操作的線性表。

12．在棧頂指針為HS的鏈棧中，判定?？盏臈l件是HS=NULL。

13．假設(shè)以S和X分別表示進棧和退棧操作，則對輸入序列a、b、c、d、e進行一系列棧操作SS后，得到的輸出序列為bceda。

14．設(shè)棧S和隊列Q的初始狀態(tài)為空，元素a、b、c、d、e、f依次通過棧S，一個元素出棧后即若這6個元素出隊列的順序是b、d、c、f、e、a，則棧S的容量至少應(yīng)該是3。

三、算法填空

1．已知一個順序表中的元素按關(guān)鍵字值非遞減有序，下列算法刪除順序表中關(guān)鍵字相同的多余元關(guān)鍵字不同的元素在表中只保留一個。

voidpurge_sq(SqList&la)

{

//刪除順序表la中關(guān)鍵字相同的多余元素，即使操作之后的順序表中只保留操作之前表中所有按不相同的元素

k=-1;//k指示新表的表尾

for(i=0;i<La.length;++i)//順序考察表中每個元素

{j=0;

while(j<=k&&la.elem[j]!=la.elem[i])

++j;//在新表中查詢是否存在和la.elem[i]相同的元素

if(k==-1||j>k)//k=-1表明當(dāng)前考察的是第一個元素

la.elem[++k]=la.elem[i];

}//for

la.length=k+1;//修改表長

}//purge_sq

2．一個頭指針為head的單鏈表，其中每個結(jié)點存放一個整數(shù)，以下算法將其拆分為兩個單鏈表hea使head1中僅含有正整數(shù)，head2中僅含有負整數(shù)。

voidseparate(LinkList&head,LinkList&head1,LinkList&head2)

{

//將頭指針為head的單鏈表（帶頭結(jié)點）拆分為兩個單鏈表head1和head2，

//使head1中僅含有正整數(shù)，head2中僅含有負整數(shù)

head1=(LinkList)malloc(sizeof(Lnode));head1->next=NULL;

head2=(LinkList)malloc(sizeof(Lnode));head2->next=NULL;

p=head->next;

while(p)

{q=p->next;

if（p->dat=0）

{p->next=head1->next;

head1->next=p;

}

else{p->next=head2->next;

head2->next=p;

}

p=q;

}//while

free(head);

}//seperate

3．設(shè)一個長度大于1的循環(huán)單鏈表中，既無頭結(jié)點也無頭指針，p為指向該鏈表中某個結(jié)點的指一個刪除該結(jié)點直接前驅(qū)結(jié)點的算法。

voiddelete(LinkListp)

{

//在一個既無頭結(jié)點也無頭指針的長度大于一的循環(huán)鏈表中，

//刪除指針p所指的某個結(jié)點的直接前驅(qū)結(jié)點

q=p;//查找p結(jié)點的前驅(qū)結(jié)點q

while(q->next!=p)

q=q->next;

r=q;//查找q結(jié)點的前驅(qū)結(jié)點r

while(r->next!=q)

r=r->next;

r->next=p;

free(q);

}

四、計算題

1．設(shè)有頭指針為head的單鏈表。寫算法要求在鏈表中查找元素值等于x的結(jié)點，若找到則刪除復(fù)，直至所有值為x的元素全部刪除為止；若一個也找不到則給出相應(yīng)提示信息。

1．voidelemdelete_x(LinkList&l,ElemTypex)

{

//刪除頭指針為head的單鏈表中（帶頭結(jié)點）所有的值為x的元素

n=0;pre=l;//記下結(jié)點*p的前驅(qū)

p=l->next;

while(p)//順序考察表中每個元素

{

while(p&&p->data!=x)

{pre=p;p=p->next;}//在表中查詢是否存在和x相同的元素

if(p)//將結(jié)點＊p插入到新的表中

｛pre->next=p->next;

q=p;p=p->next;free(q);

n++;

}//if

}//while

if(n==0)printf(“Notfoundx\n”);

}//elemdelete_x

2．有頭指針為head的單鏈表，寫算法在鏈表中查找出所有按先后順序出現(xiàn)的元素x和y，并將的所有結(jié)點全部刪除之。

2．voiddelete(LinkList&head,ElemTypex,ElemTypey)

{

//在頭指針為head的單鏈表中查找出所有按先后順序出現(xiàn)的元素x和y，

//并將x和y之間的所有結(jié)點全部刪除

p=head->next;

while(p){

while(p&&p->data!=x)

p=p->next;

if(!p)exit(1);//沒找到x

r=p->next;

while(r&&r->data!=y)

r=r->next;

if(!r)exit(1);//沒找到相應(yīng)的y

while(p->next!=r)

{q=p-next;

p->next=q->next;

free(q);

}//while

}//while

}

3．設(shè)某個單鏈表以la為頭指針，鏈表中每個元素均為整數(shù)且無序，寫算法按遞增順序打印鏈表方法是：反復(fù)找出鏈表中最小的元素，打印并刪除之，直至表空為止。

3．voidrearrange(LinkList&la){

//將頭指針是la的單鏈表按遞增順序打印出來

p=la->next;p1=la;

while(p->next!=NULL)

{a=p->data;q1=p;q=p->next;

while(q!=NULL)

{if(a>q->data)

{a=q->data;p1=q1;}//if

q1=q;q=q->next;

}//while

s=p1->next;

printf(s->data);

p1->next=p1->next->next;

free(s);

p1=la;p=la->next;

}//while

printf(p->data);

free(p);free(la);

}//rearrange

4．設(shè)有一個頭指針為head的單鏈表，每個結(jié)點存放一個整數(shù)。寫一算法將其按負整數(shù)在前部正整數(shù)在后部的次序存放（正整數(shù)與正整數(shù)之間、負整數(shù)與負整數(shù)之間不要求有序），存儲空

間仍占用原來的鏈表。

4．huafen(LinkList&L)

{//L為帶頭結(jié)點的單鏈表的頭指針

p=L->next;

while(p->next)p=p->next;

pt=p;pr=p;p0=L;

p=p0->next;3分

while(p!=pr)

if(p->data>=’0’&&p->data<=’9’)

{p0=p;p=p->next;}

else2分

{p0->next=p->next;

s=p;p=p->next;

pt->next=s;s->next=NULL;

pt=s;

}

}//huafen3分

5．設(shè)有一順序表a，寫算法在表中查找先后出現(xiàn)的元素x和y，將x和y之間的元素逆置，逆置部分不包含x和y。若找不到相應(yīng)的x和y則給出提示信息。

5．voidrevert(ElemType&R[],ints,intt)

{

//本算法將數(shù)組R中下標(biāo)自s到t的元素逆置

//即將（RRRR）改變?yōu)椋≧RRR）

S,s+1,…,t-1,tt,t-1,…,s+1,s

for(k=s;k<=(s+t)/2;k++)

{w=R[k];

R[k]=R[t-k+s];

R[t-k+s]=w;

}//for

}//revert

voidexchange(SqList&a,ElemTypex,ElemTypey)

{

//本算法實現(xiàn)在順序表a中查找先后出現(xiàn)的元素x和y之間的元素逆置，