2023-2024-數(shù)據(jù)結(jié)構(gòu)A期末試卷(A卷)【含答案】

試卷編號擬題教研室（或老師）簽名東一波教研室主任簽名

長沙理工高?？荚囋嚲恚ˋ卷）

課程名稱（含檔次）數(shù)據(jù)結(jié)構(gòu)A課程代號0812023615課程編號002131

專業(yè)計算機相關(guān)專業(yè)層次（本、專）本科考試方式（開、閉卷）閉卷

一、應(yīng)用題（2小題，共8分）

設(shè)有一個棧，元素進棧的次序為：A,B,C,D,E,用I表示進棧操作，O表示出棧

操作，寫出下列出棧的操作序列。

（1）C,B,A,D,E（2）A,C,B,E,D

二、推斷正誤（5小題，共10分）

1.依次表結(jié)構(gòu)相宜于進行依次存取，而鏈表相宜于進行隨機存取。（）

2.一個棧的輸入序列為：A,B,C,D,可以得到輸出序列：C,A,B,D。（）

3.子串“ABC”在主串“AABCABCD”中的位置為2。（）

4.設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT,則二叉樹BT中肯定沒有右子樹。（）

5.調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的全部頂點。（）

三、單項選擇題（11小題，共22分）

1.兩個指針P和Q,分別指向單鏈表的兩個元素，P所指元素是Q所指元素前驅(qū)的條件是

（）。

A.P->next==Q->nextB.P->next==QC.Q->next==PD.P==Q

2.從一個具有n個結(jié)點的單鏈表中查找其值等于x結(jié)點時，在查找勝利的狀況下，需平均

比較（）個結(jié)點。

A.nB.n/2C.（n-l）/2D.（n+l）/2

3.假如以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時（）

A.必需判別棧是否滿B.必需判別棧是否空

C.必需判別棧元素類型D.對?？刹蛔鋈魏闻袆e

4.設(shè)輸入序列是1、2、3、……、n,經(jīng)過棧的作用后輸出序列的第一個元素是n,則輸出

序列中第i個輸出元素是（）o

An-iBn-l-iCn+l-iD不能確定

5.下列說法不正確的是（）

A.串中元素只能是字符B.串中元素只能是字母

C.串是一種特別的線性表D.串中可以含有空白字符

6.線索二叉樹中某結(jié)點R沒有左孩子的充要條件是（）。

A.R.lchild=NULL.BR.ltag=OC.R.ltag=lD.R.rchild=NULL

7.樹最適合用來表示（）o

A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素

C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)

8.設(shè)有向無環(huán)圖G中的有向邊集合E={<1,2>,<2,3>,<3,4>,<1,4>},則下列屬于

該有向圖G的一種拓撲排序序列的是（）。

A.1,2,3,4B.2,3,4,1C.1,4,2,3D.1,2,4,3

9.設(shè)數(shù)據(jù)結(jié)構(gòu)A=（D,R）,其中D={1,2,3,4},R={r},r={<l,2>,<2,3>,<3,4>,

<4,1>},則數(shù)據(jù)結(jié)構(gòu)A是（）。

A線性結(jié)構(gòu)B樹型結(jié)構(gòu)C圖型結(jié)構(gòu)D集合

10.每個結(jié)點只含有一個數(shù)據(jù)元素，全部存儲結(jié)點相繼存放在一個連續(xù)的存儲區(qū)里，這種存

儲結(jié)構(gòu)稱為（）結(jié)構(gòu)。

A.依次存儲B.鏈?zhǔn)酱鎯.索引存儲D.散列存儲

11.下列敘述中，錯誤的是（）

A.數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率親密相關(guān)

B.數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān)

C.數(shù)據(jù)的存儲結(jié)構(gòu)在計算機中所占的空間不肯定是連續(xù)的

D.一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)

四、算法設(shè)計題（3小題，共32分）

I.已知一個單鏈表，編寫一個函數(shù)從單鏈表中刪除自第i個結(jié)點起的k個結(jié)點。（11分）

2.設(shè)計一個在鏈?zhǔn)酱鎯Y(jié)構(gòu)上統(tǒng)計二叉樹中結(jié)點個數(shù)的算法。（II分）

3.先閱讀下列函數(shù)arrange。，再做下面（1）和（2）兩小題：

intarrange（inta[],intl,inth,intx）

{//l和h分別為數(shù)據(jù)區(qū)的下界和上界

inti,j,t；

i=l：j=h；

while（i<j）{

while（i<j&&a[j]>=x）j—；

while（i<j&&a[i]<=x）i++；

if（i<j）

{t=a[j]；a[j]=a[i];a[i]=t；}

）

if（a[i]<x）returni；

elsereturni—1；

（1）寫出該函數(shù)的功能；（5分）

（2）寫一個調(diào)用上述函數(shù)實現(xiàn)下列功能的算法：對一整型數(shù)組b[n]中的元素進行重新排

列，將全部負數(shù)均調(diào)整到數(shù)組的低下標(biāo)端，將全部正數(shù)均調(diào)整到數(shù)組的高下標(biāo)端，若有零值,

則置于兩者之間，并返回數(shù)組中零元素的個數(shù)。（5分）

五、填空題（5小題，共10分）

1.由兩個棧共享一個存儲空間的好處是（）

2.設(shè)長度為n的鏈隊列用單循環(huán)鏈表表示，若只設(shè)尾指針，則出隊操作的時間困

難度為（）o

3.設(shè)無向圖G中頂點數(shù)為n,則圖G至少有（）條邊，至多有（）條邊。

4.在無向圖的鄰接矩陣中，第i行（列）中“1”的個數(shù)是第i個頂點的,矩陣中“1”

的個數(shù)的一半是圖中的o

5.依次存儲結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由（）表示的，鏈接存儲結(jié)構(gòu)中的數(shù)據(jù)

元素之間的邏輯關(guān)系是由（）表示的。

六、簡答題（2小題，共10分）

1.請說明依次表和單鏈表各有何優(yōu)缺點。

2.設(shè)指針變量p指向雙向鏈表中結(jié)點A,指針變量q指向被插入結(jié)點B,要求給出在結(jié)

點A的后面插入結(jié)點B的操作序列（設(shè)雙向鏈表中結(jié)點的兩個指針域分別為llink和rlink）0

七、名詞說明Q小題，共8分）

1.什么是AOE網(wǎng)？

2.簡述下列概念：線性結(jié)構(gòu)、非線性結(jié)構(gòu)。

長沙理工高校計算機與通信工程學(xué)院

2023-2024學(xué)年一學(xué)期數(shù)據(jù)結(jié)構(gòu)A期末考試試卷(A卷)

(答案部分)

一、應(yīng)用題(1小題，共8分)

1.解：(1)IIIOOOIOIO(2)IOIIOOIIOO

二、推斷正誤(5小題，共10分)

1.(X)2.(X)3.(V)4.(V)5.(X)

三、單項選擇題(U小題，共22分)

1.B2.D3.B4.C5.B6.C7.C8.A9.C10.A11.B

四、算法設(shè)計題(3小題，共32分)

1.解：

voidDel(ListNode*head,inti,intk)

(

node*p,*q;

intj;

if(i==l)For(j=l;j<=k;j++)〃刪除前k個元素

{

p=head;〃p指向要刪除的結(jié)點

head=head->next;Free(p);

)

else

(

p=head;

for(j=l;j<=i-2;j++)

p=p->next;//p指向要刪除的結(jié)點的前一個結(jié)點

for(j=l;j<=k;j++)

{

q=p->next;//q指向要刪除的結(jié)點

p->next=q->next;

free(q);

}

)

)

2.解：

voidcountnode(bitree*bt,int&count){

if(bt!=O)

{count++;

countnode(bt->lchild,count);

countnode(bt->rchild,count);)

3.解答:

(1)該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組叫中的元素并返回分界值i,使全部<x的元素均

落在a[l..i]±,使全部》x的元素均落在a[i+l..h]上。

(2)intf(intb[],intn)或intf(intb[],intn)

((

intp,q；intp,q；

p=arrange(b,O,n—1,0)；p=arrange(b,O,n—1,1)；

q=anange(b,p+1,n—1,1)；q=arrange(b,0,p,0)；

returnq—p；returnp—q；

)}

五、填空題(5小題，共10分)

1.節(jié)約存儲空間，降低上溢發(fā)生的機率

2.0(1)

3.0,n(n-l)/2

4.度邊數(shù)

5.存儲位置指針

六、簡答題(2小題，共10分)

1.答：

(1)依次表的優(yōu)點：①無需為表示表中元素