2021年中央電大計算機科學(xué)與技術(shù)專業(yè)數(shù)據(jù)結(jié)構(gòu)本科試卷

中央電大計算機科學(xué)與技術(shù)專業(yè)

數(shù)據(jù)構(gòu)造（本科）試卷7

7月已考

一、選取題（每小題1分，共10分）

1.在一種長度為n順序表任一位置插入一種新元素漸進時間復(fù)雜度為（）。

A.O（n）B.O（n/2）C.0（1）D.O（n2）

2.帶頭結(jié)點單鏈表first為空鑒定條件是：

A.first==NULL;B.first->link==NULL;

C.first->link==first;D.first!=NULL;

3.當運用大小為n數(shù)組順序存儲一種隊列時，該隊列最大長度為（）o

A.n-2B.n-lC.nD.n+l

4.在系統(tǒng)實現(xiàn)遞歸調(diào)用時需運用遞歸工作記錄保存實際參數(shù)值。在傳值參數(shù)情形，需為相

應(yīng)形式參數(shù)分派空間，以存儲實際參數(shù)副本;在引用參數(shù)情形,需保存實際參數(shù)（）,

在被調(diào)用程序中可直接操縱實際參數(shù)。

A.空間B.副本C.返回地址D.地址

5.在一棵樹中，（）沒有前驅(qū)結(jié)點。

A.分支結(jié)點B.葉結(jié)點C.樹根結(jié)點D.空結(jié)點

6.在一棵二叉樹二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加（）o

A.2B.1C.OD.-1

7.對于長度為9有序順序表，若采用折半搜索，在等概率狀況下搜索成功平均搜索長度為

（）值除以%

A.20B.18C.25D.22

8.在有向圖中每個頂點度等于該頂點()。

A.入度B.出度

C.入度與出度之和D.入度與出度之差

9.在基于排序碼比較排序算法中，()算法最壞狀況下時間復(fù)雜度不高于O(nlog2n)。

A.起泡排序B.希爾排序C.歸并排序D.迅速排序

10.當a值較小時，散列存儲普通比其她存儲方式具備()查找速度。

A.較慢B.較快C.相似

二、填空題(每小題1分，共10分)

1.二維數(shù)組是一種非線性構(gòu)造，其中每一種數(shù)組元素最多有個直接前驅(qū)(或直

接后繼)。

2.將一種n階三對角矩陣A三條對角線上元素按行壓縮存儲于一種一維數(shù)組B中,A[0][0]

存儲于B⑼中。對于任意給定數(shù)組元素B[K],它應(yīng)是A中第行元素。

3.鏈表對于數(shù)據(jù)元素插入和刪除不需移動結(jié)點，只需變化有關(guān)結(jié)點______域值。

4.在一種鏈式枝中，若棧頂指針等于NULL則為。

5.主程序第一次調(diào)用遞歸函數(shù)被稱為外部調(diào)用，遞歸函數(shù)自己調(diào)用自己被稱為內(nèi)部調(diào)用，

它們都需要運用棧保存調(diào)用后____地址。

6.在一棵樹中，結(jié)點沒有后繼結(jié)點。

7.一棵樹廣義表表達為a(b(c,d(e,f),g(h)),i(j,k(x,y))),結(jié)點f層數(shù)為。

假定根結(jié)點層數(shù)為0。

8.在一棵AVL樹(高度平衡二叉搜索樹)中，每個結(jié)點左子樹高度與右子樹高度之差絕

對值不超過o

9.n（n>0）個頂點無向圖最多有條邊，至少有條邊。

10.在索引存儲中，若一種索引項相應(yīng)數(shù)據(jù)對象表中一種表項（記錄），則稱此索引為

索弓I,若相應(yīng)數(shù)據(jù)對象表中若干個表項，則稱此索引為索引。

三、判斷題（每小題1分，共10分）

1.數(shù)組是一種復(fù)雜數(shù)據(jù)構(gòu)造，數(shù)組元素之間關(guān)系既不是線性也不是樹形。

2.鏈式存儲在插入和刪除時需要保持物理存儲空間順序分派，不需要保持數(shù)據(jù)元素之間邏

輯順序。

3.在用循環(huán)單鏈表表達鏈式隊列中，可以不設(shè)隊頭指針，僅在鏈尾設(shè)立隊尾指針、

4.普通遞歸算法簡樸、易懂、容易編寫，并且執(zhí)行效率也高。

5.一種廣義表表尾總是一種廣義表。

6.當從一種小根堆（最小堆）中刪除一種元素時，需要把堆尾元素彌補到堆頂位置，然后

再按條件把它逐級向下調(diào)節(jié)，直到調(diào)節(jié)到適當位置為止。

7.對于一棵具備n個結(jié)點，其高度為h二叉樹，進行任一種版序遍歷時間復(fù)雜度為0（h）。

8.存儲圖鄰接矩陣中，鄰接矩陣大小不但與圖頂點個數(shù)關(guān)于，并且與圖邊數(shù)也關(guān)于。

9.直接選取排序是一種穩(wěn)定排序辦法。

10.閉散列法普通比開散列法時間效率更高。

四、運算題(每小題8分，共40分)

1.設(shè)有一種10x10對稱矩陣A,將其下三角某些按行存儲在一種一維數(shù)組B中，A[0][0]

存儲于B⑼中，那么A兇⑸存儲于B中什么位置。

2.這是一種記錄單鏈表中結(jié)點值等于給定值x結(jié)點數(shù)算法，其中while循環(huán)有錯，請重新

編寫出對的while循環(huán)。

intcount(ListNode*Ha,ElemTypex)

{〃Ha為不帶頭結(jié)點單鏈表頭指針

intn=0;

while(Ha->link!=NULL){

Ha=Ha->link；

if(Ha->data==x)n++;

)

returnn;

3.已知一棵二叉樹前序和中序序列，求該二叉權(quán)il后序序列。

前序序列：A,B,C,D,E,F,G,H,I,J

中序序列：C,B,A,E,F,D,I,H,J,G

后序序列：

4.已知一種有序表(15,26,34,39,45,56,58,63,74,76,83,94)順序存儲于

一維數(shù)組a[12]中，依照折半搜索過程填寫成功搜索下表中所給元素34,56,58,63,

94時比較次數(shù)。

24565R6a94

5.設(shè)散列表為HT[17],待插入核心碼序列為{Jan,Feb,Mar,Apr,May,June,July,

Aug,Sep,Oct,Nov,Dec),散列函數(shù)為H(key)=Li/2」，其中,i是核心碼第一種字

母在字母表中序號?，F(xiàn)采用線性探查法解決沖突。

字母ABCDEFGHIJKLM

序號12345678910111213

字母NOPQRSTUVWXYZ

序號14151617181920212223242526

(1)試畫出相應(yīng)散列表;

(2)計算等概率下搜索成功平均搜索長度；

五、算法分析題(每小題8分，共24分)

1.閱讀下列算法，并補充所缺語句

voidpurge_linkst(ListNode*&la){

〃從頭指針為la帶表頭結(jié)點有序鏈表中刪除所有值相似多余元素,

〃并釋放被刪結(jié)點空間。

ListNodep,q,t；ElemTypetemp;

p=la->link;

while(p!=NULL){

q=p;

temp=p->data;

p=p->link;

if(p!=NULL&&)p=p->link;

else{

while(p!=NULL&&){

t=p；p=p->link;

deletet;

)

q->link=p;

2.下面給出一種排序算法，它屬于數(shù)據(jù)表類成員函數(shù)，其中currentSize是數(shù)據(jù)表實例當前

長度，Vector[]是存儲數(shù)據(jù)表元素一維數(shù)組。

template<classT>

voiddataList<T>:：unknown(){

Ttemp；inti,j,n=currentSize;

for(i=1；i<n；i++)

if(Vector[i].key<Vector[i-l].key){

temp=Vector[iJ；Vectorli]=Vector[i-l];

for(j=i-2；j>=0；j-)

if(temp.key<Vector[j].key)Vector[j+1]=Vector[j];

elsebreak;

Vector[j4-1]=temp;

(1)寫出該算法功能。

(2)針對有n個數(shù)據(jù)對象待排序數(shù)據(jù)表，在最佳狀況下，算法排序碼比較次數(shù)和對象移

動次數(shù)分別是多少？

比較次數(shù)：移動次數(shù)：

3.已知二叉樹中結(jié)點類型用BinTreeNode表達，被定義為：

structBinTreeNode{ElemTypedata;BinTreeNode*leftChild,*rightChild;};

其中data為結(jié)點值域，leftChild和rightChild分別為指向左、右子女結(jié)點指針域。依照

下面函數(shù)定義指出函數(shù)功能。算法中參數(shù)BT指向一棵二叉樹樹根結(jié)點。

BinTreeNode*BinTreeSwopX(BinTreeNode*BT){

if(BT==NULL)returnNULL;

else(

BinTreeNode*pt=newBinTreeNode;

pt->data=BT->data;

pt->rightChild=BinTreeSwopX(BT->leftChild);

pt->lefthild=BinTreeSwopX(BT->righlChild);

returnpt;

六、算法設(shè)計題(6分)

已知二叉樹中結(jié)點類型用BinTreeNode表達，被定義為：

structBTreeNode{chardata;BinTreeNode*leftChild,*rightChild;};

其中data為結(jié)點值域，leftChild和rightChild分別為指向左、右子女結(jié)點指針域，依照

下面函數(shù)聲明編寫出求一棵二叉樹中結(jié)點總數(shù)算法，該總數(shù)值由函數(shù)返回。假定參數(shù)

BT初始指向這棵二叉樹根結(jié)點。

intBTreeCount(BinTreeNode*BT);

中央電大計算機科學(xué)與技術(shù)專業(yè)

數(shù)據(jù)構(gòu)造（本科）試題參照答案及評分原則7

一、選取題（每小題1分，共10分）

1.A2.B3.B4.D5.C6.A7.C8.C

9.C10.B

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

1.22.L（K+l）/3j3.指針4.空棧

5.返回6.葉子7.38.1

9.n（n-l）/2,010.稠密，稀疏

第9和10小題中有一空錯則1分全扣。

三、判斷題（每小題1分，共10分）

1.對2.錯3.對4.錯5.對6.對7.錯8.錯

9.錯10.錯

四、運算題（每小題8分，共40分）

1.依照題意，矩陣A中當元素下標I與J滿足I>J時，任意元素在一維數(shù)組B中

存儲位置為1*（1+1）/2+J,因而，A[8][5]在數(shù)組B中位置為

8*（8+1）/2+5=41。

2.

while(Ha!=NULL){

if(Ha->data==x)n++;

Ha=Ha->link;

3.后序序列：C,B,F,E,I,J,H,G,D,A

4.判斷成果

3456586394

元素值

17AA

比較次數(shù)//對1個給1分，全對給8分

5.

H(Jan)=L10/2j=5,成功.H(Feb)=|_6/2」=3,成功.

H(Mar)=L13/2」=6,成功.H(Apr)=Ll/2j=0,成功.

H(May)=L13/2j=6,=7,成功,H(June)=110/2」=5,=6,=7,=8,成功

H(July)=L10/2J=5,=6,=7,=8,=9,成功.

H(Aug)=|_1/2」=0,=1,成功.H(Sep)=L19/2」=9,=10,成功.

H(Oct)=|j5/2」=7,=8,=9,=10,=11,成功.

H(Nov)=114/2」=7,=8,=9,=10,=11,=12.成功.

H(Dec)=14/2」=2,成功.

⑴相應(yīng)散列表（6分），錯一種存儲位置扣1分，最多扣6分