2023年電大本科《數(shù)據(jù)結(jié)構(gòu)（本）》期末復(fù)習(xí)試題及答案

本文格式為Word版，下載可任意編輯——2023年電大本科《數(shù)據(jù)結(jié)構(gòu)（本）》期末復(fù)習(xí)試題及答案2023年電大本科《數(shù)據(jù)結(jié)構(gòu)（本）》期末復(fù)習(xí)試題及答案

一、單項選擇題

1．棧和隊列的共同特點是（）。

A.元素都可以隨機進出B.都是先進先出C.都是先進后出D.都是操作受限的線性結(jié)構(gòu)2.數(shù)據(jù)的存儲結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（）。A.數(shù)據(jù)處理的方法B.數(shù)據(jù)元素間的關(guān)系的表示C.相關(guān)算法D.數(shù)據(jù)元素的類型

3．對一個棧頂指針為top的鏈棧進行入棧操作，通過指針變量p生成入棧結(jié)點，則執(zhí)行：p=(structnode*)malloc(sizeof(structnode);p->data=a;和（）。A.top->next=p;p=top;B.p->nex=top;top=p;C.top=top->next;p=top;D.p->next=top;p=top;

4．樹狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。

A．每一個元素都有一個直接前驅(qū)和一個直接后繼B．一對一C．多對多D．一對多

5．設(shè)頭指針為head的非空的單向鏈表,指針p指向尾結(jié)點,則通過以下操作()可使其成為單向循環(huán)鏈表。A．p->next=NULL;B．head=p;C．p->next=head;D．p=head;

6．設(shè)有一個長度為26的順序表，要插入一個元素,并使它成為新表的第6個元素,需移動元素的個數(shù)為（）。A．21B．22C．20D．197．一種規(guī)律結(jié)構(gòu)（）。

A．只能有唯一的存儲結(jié)構(gòu)B．可以有不同的存儲結(jié)構(gòu)

C．與存儲該規(guī)律結(jié)構(gòu)的計算機相關(guān)D．是指某一種數(shù)據(jù)元素的性質(zhì)

8．頭指針為head的帶頭結(jié)點的單向循環(huán)鏈表，p所指向尾結(jié)點，要使該鏈表成為不帶頭結(jié)點的單向循環(huán)鏈表,可執(zhí)行head=head->nex;和（）。A．p=head->nextB．head->next=p

C．head->next=p->nextD．p->next=head;

9．把數(shù)據(jù)存儲到計算機中，并具體表達數(shù)據(jù)元素間的規(guī)律結(jié)構(gòu)稱為（）。A．存儲結(jié)構(gòu)B．規(guī)律結(jié)構(gòu)

C．?dāng)?shù)據(jù)元素的存儲D.給數(shù)據(jù)元素分派存儲空間

10．元素111，113，115，117按順序依次進棧，則該棧的不可能輸出序列是（）（進棧出?？梢越惶孢M行）。

A．117，115，113，111B．111，113，115，117C．117，115，111，113D．113，111，117，115

11．圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。A．一對一B．一對多

C．多對多D．每一個元素都有一個且只有一個直接前驅(qū)和一個直接后繼12．以下說法正確的是（）。A．棧的特點是先進先出B．棧的特點是先進后出

C．隊列的特點是先進后出

D.棧和隊列的特點都是后進后出

13．一個單鏈表中,在p所指結(jié)點之后插入一個s所指的結(jié)點時，可執(zhí)行:s->next=p->next;和（）。

A．s=p->next;B．p->next=s->next;C．p=s->next;D．p->next=s;

14.設(shè)有一個20階的對稱矩陣A(第一個元素為a1,1)，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣元素a6,2在一維數(shù)組B中的下標(biāo)是（）。A．21B．28C．17D．23

15．元素12，14，16，18順序依次進棧，則該棧的不可能輸出序列是（）。（進棧出?？梢越惶孢M行）。

A．18，16，14，12B．12，14，16，18D．14，12，18，16D．18，16，12，1416．設(shè)有串p1=〞ABADF〞,P2=〞ABAFD〞，P3=〞ABADFA〞,P4=〞ABAF〞,以下四個串中最大的是()。

A．p3B．p2C．p1D．p4

17．設(shè)有一個30階的對稱矩陣A(第一個元素為a1,1)，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a9,2在一維數(shù)組B中的下標(biāo)是（）。A．41B．32C．18D．38

18.數(shù)組a經(jīng)初始化chara[]=“English〞;a[7]中存放的是（）。A.字符串的終止符B.字符hC.〝h〞D.變量h

19．設(shè)有一個長度為32的順序表，要刪除第8個元素需移動元素的個數(shù)為（）。A．15B．22C．14D．24

20.設(shè)主串為“ABcCDABcdEFaBc〞，以下模式串能與主串成功匹配的是（）。A.BcdB.BCdC.ABCD.Abc

21.在一棵二叉樹中，若編號為i的結(jié)點存在右孩子，則右孩子的順序編號為（）。A．2iB．2i-1C．2i+1D．2i+2

22．在一棵二叉樹中，若編號為i的結(jié)點存在左孩子，則左孩子的順序編號為（）。A．2i+1B．2i-1C．2iD．2i+2

23．一棵具有16個結(jié)點的完全二叉樹，共有（）層。(設(shè)根結(jié)點在第一層)A．7B．6C．4D．5

24．如圖1所示，若從頂點a出發(fā)，按圖的廣度優(yōu)先探尋法進行遍歷，則可能得到的一種頂點序列為（）。

A．a(chǎn)becdfB．a(chǎn)ebcfdC．a(chǎn)ecbdfD．a(chǎn)edfcb

25．如圖2所示，若從頂點a出發(fā)，按圖的深度優(yōu)先探尋法進行遍歷，則可能得到的一種頂點序列為（）。

A．a(chǎn)becdfgB．a(chǎn)cfebgdC．a(chǎn)ebcfgdD．a(chǎn)edfcgb

26．線性表以（）方式存儲，能進行折半查找。A．鏈接B．順序C．關(guān)鍵字有序的順序D．二叉樹

27.字符串“DABcdabcd321ABC〞的子串是()。A.“cd32〞B.“ABcD〞C.“aBcd〞D.“321a〞

28．一棵具有38個結(jié)點的完全二叉樹，最終一層有（）個結(jié)點。A．7B．5C．6D．8

29．如圖3所示，若從頂點a出發(fā)，按廣度優(yōu)先探尋法進行遍歷，則可能得到的一種頂點序列為（）。

A．a(chǎn)bcdfgeB．a(chǎn)bcdfegC．a(chǎn)cbfedgD．a(chǎn)bcfgde

30.下圖4的拓?fù)湫蛄惺?)。A．52346B．23645C．56234D.23564

二、填空題

1.對稀疏矩陣進行壓縮存儲,可采用三元組表，一個有10行的稀疏矩陣A共有97個零元素，其相應(yīng)的三元組表共有3個元素。該矩陣A有列。2．結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為________結(jié)構(gòu)。

3．在單向鏈表中，q指向p所指結(jié)點的直接后繼結(jié)點，要刪除q所指結(jié)點，可以用操作______=q->next;。

4.n個元素進行冒泡法排序，第j趟冒泡要進行______次元素間的比較。

5.對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應(yīng)的三元組包括該元素的行下標(biāo)、列下標(biāo)和_______三項信息。

6．中序遍歷________樹可得到一個有序序列。7.隊列的操作特點是后進________。

8.待排序的序列為8,3,4,1,2,5,9,采用直接選擇排序算法,當(dāng)進行了兩趟選擇后,結(jié)果序列為()。9．n個元素進行冒泡法排序，尋常需要進行________趟冒泡。10廣義表((a,b),d,e,((i,j),k))的長度是________。

11．中序遍歷二叉排序樹可得到一個________的序列。12.廣義表的(c，a,(a,b),d,e,((i,j),k))深度是________。13.廣義表(c,a,(a,b),d,e,((i,j),k))的長度是________。

14.對稀疏矩陣進行壓縮存儲,可采用三元組表，一個有10行10列的稀疏矩陣A共有95個零元素，其相應(yīng)的三元組表共有個元素。

15.廣義表的(c,a,(a,b),d,e,((i,j),k))深度是________。

16．在對一組記錄(50,49,97,22,16,73,65,47,88)進行直接插入排序時，當(dāng)把第7個記錄65插入到有序表時，為尋覓插入位置需比較_________次。

17.循環(huán)隊列在規(guī)定少用一個存儲空間的狀況下，隊空的判定條件為________。18.一棵有5個葉結(jié)點的哈夫曼樹,該樹中總共有_____個結(jié)點。19.c語言中,字符串“E〞存儲時占個字節(jié)。

20.設(shè)有一棵深度為4的完全二叉樹，第四層上有5個結(jié)點，該樹共有_______個結(jié)點。（根所在結(jié)點為第1層）。

21．一棵二叉樹中有n個非葉結(jié)點，每一個非葉結(jié)點的度數(shù)都為2，則該樹共有_______個葉結(jié)點。

22．設(shè)有一個長度為40的順序表，要刪除第8個元素需移動元素的個數(shù)為_______。23．在

對一組記錄(55,39,97,22,16,73,65,47,88)進行直接插入排序時，當(dāng)把第7個記錄65插入到有序表時，為尋覓插入位置需比較_________次。24.有以下程序段chara*+=“English〞;char*p=a;intn=0;

while(*p!=‘\\0’){n++;p++;}結(jié)果中，n的值是_______。三、綜合題

1．設(shè)查找表為(1,10,11,14,23,27,29,55,68),元素的下標(biāo)依次為1,2,3,??，9。（1）畫出對上述查找表進行折半查找所對應(yīng)的判定樹（樹中結(jié)點用下標(biāo)表示）。（2）說明成功查找到元素14,需要依次經(jīng)過與哪些元素的比較？共幾次比較？（3）求在等概率條件下，成功查找的平均比較次數(shù)？.

2．有一個長度為11的有序表(1,2,11,15,24,28,30,56,69,70,80),元素的下標(biāo)依次為1,2,3,??,11，按折半查找對該表進行查找。

(1）畫出對上述查找表進行折半查找所對應(yīng)的判定樹。

（2）說出成功查找到元素56,,需要依次經(jīng)過與哪些元素的比較？（3）說出不成功查找元素72,需要進行元素比較的次數(shù)？3．

(1)以3，4，5，8，9，作為葉結(jié)點的權(quán)，構(gòu)造一棵哈夫曼樹。(2)給出相應(yīng)權(quán)重值葉結(jié)點的哈夫曼編碼。

(3)n個葉結(jié)點的哈夫曼樹，總共有多少個結(jié)點？

4.(1)一組記錄的關(guān)鍵字序列為（57，90，67，50，51，56），利用堆排序（堆頂元素是最小元素）的方法建立初始堆（要求以完全二叉樹描述）。

(2)對關(guān)鍵字序列(56,51,71,54,46,106)利用快速排序，以第一個關(guān)鍵字為分割元素，給出經(jīng)過一次劃分后結(jié)果。

(3)一組記錄的關(guān)鍵字序列為（60,47，80，57，39，41，46,30），利用歸并排序的方法,分別給出(1,1)歸并、(2,2)歸并、(4,4)歸并的結(jié)果序列。四、程序填空題

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

if(BT!=NULL){（1）;（2）;

Inorder(BT->right);}}

利用上述程序?qū)τ覉D進行遍歷，結(jié)果是（3）;

2.設(shè)線性表為（16，20，26，24），以不帶頭結(jié)點的單向鏈表存儲，鏈表頭指針為head,以下程序的功能是輸出鏈表中各結(jié)點中的數(shù)據(jù)域data。structnode{intdata;

structnode*next;

};

typedefstructnodeNODE;#defineNULL0voidmain()

{NODE*head,*p;

p=head;/*p為工作指針*/do

,printf(“%d\\n〞,___(1)_____);___(2)_____;

}while(___(3)_____);}

3．以下冒泡法程序?qū)Υ娣旁赼[1]，a[2]，??，a[n]中的序列進行排序，完成程序中的空格部分，其中n是元素個數(shù)，要求按升序排列。voidbsort(NODEa[],intn){NODEtemp;inti,j,flag;

for(j=1;（1）;j++);{flag=0;

for(i=1;（2）;i++)if(a[i].key>a[i+1].key){flag=1;temp=a[i];

（3）;（4）;}

if(flag==0)break;}}

設(shè)有序列6，4，5，8，2，1，給出由該程序經(jīng)過兩趟冒泡后的結(jié)果序列（5）

4.以下函數(shù)為直接選擇排序算法，對a[1],a[2],?a[n]中的記錄進行直接選擇排序，完成程序中的空格typedefstruct{intkey;??}NODE;

voidselsort(NODEa[],intn){

inti,j,k;

NODEtemp;

for(i=1;inext;4．n-j

5．?dāng)?shù)組元素6．二叉排序樹7．后出

8．1，2，4，8，3，5，99．n-110．411．有序12．313．614．515．316．3

17.front==rear