數(shù)據(jù)結(jié)構(gòu)歷年試題及答案

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)歷年試題及答案試卷：1252

中央廣播電視大學(xué)2023-2023學(xué)年度其次學(xué)期“開(kāi)放本科〞期末考試

一、單項(xiàng)選擇題（每題2分，共30分）1．在C語(yǔ)言中，順序存儲(chǔ)長(zhǎng)度為3的字符串，需要占用()個(gè)字節(jié)。A．4B．3C．6D．122。串函數(shù)StrCat(a，b)的功能是進(jìn)行串()。A．比較B．復(fù)制C．賦值D．連接3．-棵有n個(gè)結(jié)點(diǎn)采用鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)中，共有()個(gè)指針域?yàn)榭铡．n+lB．nC．n-lD．n-24．設(shè)一棵哈夫曼樹(shù)共有n個(gè)非葉結(jié)點(diǎn)，則該樹(shù)有()個(gè)葉結(jié)點(diǎn)。A．nB．n+lC．n-lD．2n5．從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用變量x保存被刪結(jié)點(diǎn)的值，則執(zhí)行()。A.x=top->data;top=top->nextB.x=top->data

C.top=top->next;x=top->dataD.top=top->next;x=data

6．一棵完全二叉樹(shù)共有5層，且第5層上有六個(gè)結(jié)點(diǎn)，該樹(shù)共有()個(gè)結(jié)點(diǎn)。A．30B．20C．21D．23

7．在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的()倍。^A．O上；．B．3C．1.5D．28．已知如圖1所示的一個(gè)圖，若從頂點(diǎn)V，出發(fā)，按深度優(yōu)先探尋法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為()。

9．已知如圖2所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先探尋法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為()。A.abcedfB.abcefdC.aebcfdD.acfdeb10.對(duì)二叉排序樹(shù)進(jìn)行()遍歷，可以使遍歷所得到的序列是有序序列。

A．按層次B．后序C．中序D．前序

11．在有序表(2，4，7，14，34，43，47，64，75，80，90，97，120)中，用折半查找法查找值80時(shí)，經(jīng)()次比較后查找成功。A．4B．2C．3D．5

12．有一個(gè)長(zhǎng)度為9的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率狀況下查找成功的平均比較次數(shù)為()。A．25/10B．25/9C．20/9D．17/9

13.排序算法中，從未排序序列中依次取出元素與已排序序殂（初始為空）中的元素進(jìn)行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是()。A．冒泡B。直接插入C．折半插入D．選擇排序

14．一組記錄的關(guān)鍵字序列為(46，79，56，38，40，84)，利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后結(jié)果為()。A．40,38946,79956,84B．40,38946,56,79,84C．40，38,46,84,56,79D．38，40,46956,79,84

15.排序方法中，從尚未排序序列中挑揀元素，并將其依次放人已排序序列（初始為空）的一端的方法，稱為()排序。A．歸并B．插入C．快速D．選擇

1．A2．D3．A4．B5.A6．C7．D8．A9．B10.C11．B2．B13．C14．B15.D二、填空題（每題2分。共20分）

16.在二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，尋常每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，它們是(值域)(左指針)(右指針)。17.一棵二叉樹(shù)中順序編號(hào)為i的結(jié)點(diǎn)，若它存在左、右孩子，則左、右孩子編號(hào)分別為(2i、2i+l)。

18.串的兩種最基本的存儲(chǔ)方式是(順序存儲(chǔ))和(鏈?zhǔn)酱鎯?chǔ))。

19.-棵有2n-l個(gè)結(jié)點(diǎn)的二叉樹(shù)，其每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2，則該樹(shù)共有(n)個(gè)葉結(jié)點(diǎn)。20.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其相應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中共有（n+1）個(gè)指針域?yàn)榭铡?1（中序）遍歷二叉排序樹(shù)可得到一個(gè)有序序列。

22.圖的深度優(yōu)先探尋和廣度優(yōu)先探尋序列不一定是唯一的。此斷言是（正確）的。

23.二叉樹(shù)為二叉排序的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說(shuō)法是（不正確）的。（回復(fù)正確或不正確）

24.對(duì)記錄序列排序是指按記錄的某個(gè)關(guān)鍵字排序，記錄序列按（主關(guān)鍵字）排序結(jié)果是唯一的。25.按某關(guān)鍵字對(duì)記錄序列排序，若（關(guān)鍵字相等的記錄）在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。三、綜合題（每題10分。共30分）

26．設(shè)查找表為(16，15，20，53，64，7)，(1)用冒泡法對(duì)該表進(jìn)行排序（要求升序排列），寫(xiě)出每一趟的排序過(guò)程，尋常對(duì)n個(gè)元素進(jìn)行冒泡排序要進(jìn)行多少趟冒泡？第j趟要進(jìn)行多少次元素間的比較？(2)在排序后的有序表的基礎(chǔ)上，畫(huà)出對(duì)其進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)。（要求以數(shù)據(jù)元素作為樹(shù)結(jié)點(diǎn)）。27．(1)設(shè)有查找表{5，14，2，6，18，7，4，16，3），依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹(shù)。(2)說(shuō)明如何由序列的二叉排序樹(shù)得到相應(yīng)序列的排序結(jié)果。

38．(1)對(duì)給定權(quán)值2，1，3，3，4，5，構(gòu)造哈夫曼樹(shù)（要求每個(gè)結(jié)點(diǎn)的左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán)）。(2)給出各權(quán)值的哈夫曼編碼。

四、程序填空題【每空2分。共16分）

30.以下程序是后序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分（樹(shù)結(jié)構(gòu)中，左、右指針域分別為1eft和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。voidPostorder(structBTreeNode*BT)

{if(BT!=NULL){(1)[](2)[](3)[]}}

試卷：1252

中央廣播電視大學(xué)2023-2023學(xué)年度第一學(xué)期“開(kāi)放本科〞期末考試

一、單項(xiàng)選擇題（每題2分，共30分）

1．同一種規(guī)律結(jié)構(gòu)()。A.只能有唯一的存儲(chǔ)結(jié)構(gòu)B．可以有不同的存儲(chǔ)結(jié)構(gòu)C．只能表示某一種數(shù)據(jù)元素之間的關(guān)系n以上三種說(shuō)法均不正確

2．鏈表所具備的特點(diǎn)是()。A可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B占用連續(xù)的存儲(chǔ)空間C插入刪除元素的操作不需要移動(dòng)元素結(jié)點(diǎn)D可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)3．?dāng)?shù)據(jù)的物理結(jié)構(gòu)()。A與數(shù)據(jù)的規(guī)律結(jié)構(gòu)無(wú)關(guān)B僅僅包括數(shù)據(jù)元素的表示C只包括數(shù)據(jù)元素間關(guān)系的表示n包括數(shù)據(jù)元素的表示和關(guān)系的表示4.線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在()的關(guān)系。

A-對(duì)一B一對(duì)多C多對(duì)多D.每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼

14.設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹鞔鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素氏。在一維數(shù)組B中的下標(biāo)是．()。A．33B．32C．85D．41

15．在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的()倍。A3＆2.5C1.5D．21．B2．C3．D4．A5．D6．C7．B8．C9．A10．C11．A12．B13．C14．A15．D

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

16.棧和隊(duì)列的操作特點(diǎn)分別是（后進(jìn)先出）和（先進(jìn)先出）。17.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為（網(wǎng)狀）結(jié)構(gòu)。18.根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，尋?？煞譃榧?、線性、（樹(shù)形）、（圖形）、四類基本結(jié)構(gòu)。

19.要求在n個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時(shí)間繁雜度分別為（n-1）和(O(n))。

20.在一個(gè)單向鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指向的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行(s->next=s)和(p->next=s)的操作。21．在二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，尋常每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，它們是值域、(左指針)、（右指針）。22．一棵二叉樹(shù)中順序編號(hào)為i的結(jié)點(diǎn)，若它存在左、右孩子，則左右孩子的編號(hào)分別為（2i）、（2i+1）23．向一個(gè)棧頂指針為h的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，可執(zhí)行(s->next=h)；和(n=s)。24.在一個(gè)鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為（r->next=s）和r=s；(結(jié)點(diǎn)的指針域?yàn)閚ext)。

25.設(shè)有一棵深度為4的完全二叉樹(shù)，第四層上有5個(gè)結(jié)點(diǎn)，該樹(shù)共有(12)個(gè)結(jié)點(diǎn)。（根所在結(jié)點(diǎn)為第1層）26.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的（行下標(biāo)）、（列下標(biāo)）和非零元素值三項(xiàng)信息。

27.在對(duì)一組記錄(55，39，97，22，16，73，65，47，88)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄65插入到有序表時(shí)，為尋覓插入位置，需比較（3）次。三、綜合題（每題10分，共30分）

28．(1)以2，3，4，7，8，9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(shù)（要求每個(gè)結(jié)點(diǎn)的左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán)），給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。(2)-棵哈夫曼樹(shù)有n個(gè)葉結(jié)點(diǎn)，它一共有多少個(gè)結(jié)點(diǎn)？簡(jiǎn)述理由。29．一組記錄的關(guān)鍵字序列為(46，79，56，38，40，84)

(1)利用快速排序的方法，給出以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果（給出逐次交換元素的過(guò)程，要求以升序排列）。(2)對(duì)上述序列用堆排序的方法建立大根堆，要求以二叉樹(shù)逐次描述建堆過(guò)程。30．設(shè)查找表為(50，60，75，85，96，98，105，110，120，130)

(1)說(shuō)出進(jìn)行折半查找成功查找到元素120需要進(jìn)行多少次元素間的比較？(2)為了折半查找元素95，經(jīng)過(guò)多少次元素間的比較才能確定不能查到？

(3)畫(huà)出對(duì)上述有序表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)（要求以數(shù)據(jù)元素作為樹(shù)結(jié)點(diǎn)）。

四、程序填空題（每空2分，共16分）

試卷：1252

中央廣播電視大學(xué)2023--2023學(xué)年度第一學(xué)期“開(kāi)放本科〞期末考試

一、單項(xiàng)選擇題(每題2分。共30分)

1．鏈表所具備的特點(diǎn)是()。A．可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B．占用連續(xù)的存儲(chǔ)空間C．插入刪除元素的操作不需要移動(dòng)元素結(jié)點(diǎn)D．可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)2．線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在()的關(guān)系。A．一對(duì)一B．一對(duì)多C．多對(duì)多

D。每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼3．算法的時(shí)間繁雜度與()有關(guān)。7A．所使用的計(jì)算機(jī)B．與計(jì)算機(jī)的操作系統(tǒng)C．與算法本身D．與數(shù)據(jù)結(jié)構(gòu)

4．在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是P所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q所指結(jié)點(diǎn)，可用的語(yǔ)句是()。A．p=q->nextB．p->next=qC．p->next=q->nextD．q->next=NULL

5．在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為()。A．r=f->next：B．r=r->next：C．f=f一>next；D．f=r一>next：

6．元素3，6，9按順序依次進(jìn)棧，則該棧的不可能輸出序列是()(進(jìn)棧出?？梢越惶孢M(jìn)行)。A．9，6，3B．9，3，6C．6，3，9D．3，9，6

7．設(shè)有一個(gè)l0階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹鞔鎯?chǔ)到一維數(shù)組8中(數(shù)組下標(biāo)從1開(kāi)始)，則矩陣中元素氏，。在一維數(shù)組B中的下標(biāo)是(．)。A．33B．32C．85D．41

8．在C語(yǔ)言中，順序存儲(chǔ)長(zhǎng)度為3的字符串，需要占用()個(gè)字節(jié)。A．4B．3C．6D．12

9．一棵有n個(gè)結(jié)點(diǎn)采用鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)中，共有()個(gè)指針域?yàn)榭?。A．n+1B．nC．n一1D．n--2

10．設(shè)一棵哈夫曼樹(shù)共有n個(gè)葉結(jié)點(diǎn)，則該樹(shù)有()個(gè)非葉結(jié)點(diǎn)。A．n—lB．nC．n+1D．2n

11．在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的()倍。A．3B．2．5C．1．5D．2

12．已知如圖1所示的一個(gè)圖，若從頂點(diǎn)V。出發(fā)，按廣度優(yōu)先進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為()。

13．在有序表{2，4，7，14，34，43，47，64，75，80，90，97，120)中，用折半查找法查找值80時(shí)，經(jīng)()次比較后查找成功。A．4B．2C．3D．5

14．排序算法中，從未排序序列中依次取出元素與已排序序列(初始為空)中的元素進(jìn)行比較(要求比

較次數(shù)盡量少)，然后將其放入已排序序列的正確位置的方法是()。A．冒泡B．直接插入C．折半插人D．選擇排序

15．排序方法中，從尚未排序序列中挑揀元素，并將其依次放入已排序序列(初始為空)的一端的方法，稱為()排序。A．歸并B．插入C．快速D．選擇

二、填空題(每題2分。共24分)

1·結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為——結(jié)構(gòu)。

2.要求在n個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時(shí)間繁雜度分別為和

3·設(shè)有一個(gè)頭指針為head的單向循環(huán)鏈表，p指向鏈表中的結(jié)點(diǎn)，若p一>next==——，則P所指結(jié)點(diǎn)為尾結(jié)點(diǎn)。

4·向一個(gè)棧頂指針為h的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，可執(zhí)行s一>next=h；和5·在一個(gè)鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為和r=s；(結(jié)點(diǎn)的指針域?yàn)閚ext)

6.設(shè)有n階對(duì)稱矩陣A，用數(shù)組s進(jìn)行壓縮存儲(chǔ)，當(dāng)inext=NULL；head=(1)——；(2)——；

for(i=1；idata=i；if(i==1)p->next=NULL；else

p->next2(4)——；q一>next2(5)——；}

return(head)；}

2．以下程序是后序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分(樹(shù)結(jié)構(gòu)中，左、右指針域分別為left和right，數(shù)據(jù)域data為字符型；BT指向根結(jié)點(diǎn))。voidPostorder(structBTreeNode*BT){if(BT!=NULL){·

(1)；(2)；(3)；

()

A．iront==rearB．front!=NULLC．rear!=NULL

D．front==NULL

5．若讓元素l，2，3依次進(jìn)棧，則出棧次序不可能出現(xiàn)()種狀況。A．3，2，1

B．2，1，3

C．3，1，2D．1，3，2

6．在一棵高度為5(假定樹(shù)根結(jié)點(diǎn)的高度為0)的完全二叉樹(shù)中，所含結(jié)點(diǎn)個(gè)數(shù)至少等于()A．16

B．64

C．31D．32

7．向具有n個(gè)結(jié)點(diǎn)的二叉探尋樹(shù)中插入一個(gè)結(jié)點(diǎn)的時(shí)間繁雜度大致為()。

A．O(1)B．O(1og2n)C．O(n)

D．O(nlog2n)

8．具有n個(gè)頂點(diǎn)的有向圖最多可包含有()條有向邊。

A．n—1

B．n

C．n(n一1)／2D．n(n一1)

9．圖的廣度優(yōu)先探尋類似于樹(shù)的()遍歷。A．先根

C．后根

B．中根D．層次

二、填空題。在橫線處填寫(xiě)適合的內(nèi)容(每題2分，共14分)1．鏈表只適用于()查找。

2．設(shè)雙向循環(huán)鏈表中每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為(data，llink，rlink)，則結(jié)點(diǎn)*P的前驅(qū)結(jié)點(diǎn)的地址為()。

3．在一個(gè)鏈?zhǔn)疥?duì)列中，若隊(duì)頭指針與隊(duì)尾指針的值一致，則表示該隊(duì)列至多有()個(gè)結(jié)點(diǎn)。4．假定一棵樹(shù)的廣義表表示為a(b，c，d(e，f)，g(h))，則結(jié)點(diǎn)f的層數(shù)為()。假定樹(shù)根結(jié)點(diǎn)的層數(shù)為0。

5．從一棵二叉探尋樹(shù)中探尋一個(gè)元素時(shí)，若給定值大于根結(jié)點(diǎn)的值，則需要向根的()繼續(xù)探尋。

6．每次從第i至第n個(gè)元素中順序挑揀出一個(gè)最小元素，把它交換到第i個(gè)位置，此種排序方法叫做()排序。

7．快速排序在最壞狀況下的時(shí)間繁雜度為()。

三、判斷題，在每題前面打?qū)μ?hào)表示正確或打叉號(hào)表示錯(cuò)誤(每題2分。共14分)

()1．?dāng)?shù)據(jù)的規(guī)律結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。()2．使用三元組表示稀疏矩陣中的非零元素能節(jié)省存儲(chǔ)空間。

()3．在一棵二叉樹(shù)中，假定每個(gè)結(jié)點(diǎn)只有左子女，沒(méi)有右子女，則對(duì)它分別進(jìn)行前序遍歷和按層遍歷時(shí)具有一致的結(jié)果。

()4．能夠在鏈接存儲(chǔ)的有序表上進(jìn)行折半探尋，其時(shí)間繁雜度與在順序存儲(chǔ)的有序表上一致。

()5．鄰接表表示只能用于有向圖的存儲(chǔ)，鄰接矩陣對(duì)于有向圖和無(wú)向圖的存儲(chǔ)都適用。()6．在索引順序結(jié)構(gòu)上實(shí)施分塊探尋，在等概率狀況下，其平均探尋長(zhǎng)度不僅與子表個(gè)數(shù)有關(guān)，而且與每一個(gè)子表中的對(duì)象個(gè)數(shù)有關(guān)。

()7．向一棵8樹(shù)插入關(guān)鍵碼的過(guò)程中，若最終引起樹(shù)根結(jié)點(diǎn)的分裂，則新樹(shù)比原樹(shù)的高度減少1。

四、運(yùn)算題(每題6分。共30分)

1．假定一棵二叉樹(shù)廣義表表示為a(b(c(，g))，d(e，f))，分別寫(xiě)出對(duì)它進(jìn)行先序、中序和后序遍歷的結(jié)果。

先序：中序：后序：

2．有7個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3，7，8，2，6，10，14，試以它們?yōu)槿~子結(jié)點(diǎn)生成一棵霍夫曼樹(shù)，求出該樹(shù)的帶權(quán)路徑長(zhǎng)度。帶權(quán)路徑長(zhǎng)度：

3．已知圖G=(V，E)，其中

V={a，b，c，d，e}，

E={，，，，，，}在該圖的鄰接表表示中，每個(gè)頂點(diǎn)單鏈表各有多少個(gè)邊結(jié)點(diǎn)。頂點(diǎn)：abcde邊結(jié)點(diǎn)數(shù)：

4．已知一個(gè)AOV網(wǎng)的頂點(diǎn)集V和邊集G分別為：

V={0，1，2，3，4，5，6，7}；

E={，，，，，，，，，}