1252數(shù)據(jù)結(jié)構(gòu)（本）-國家開放大學(xué)2018年1月至2021年7月期末考試真題及答案（201801-202107不少于6套）

1、試卷代號：1252數(shù)據(jù)結(jié)構(gòu)（本）試題2018年1月一、單項選擇題（每小題3分，共30分）1設(shè)有頭指針為head的帶有頭結(jié)點的非空單向循環(huán)鏈表，指針p指向其尾結(jié)點，要刪除頭結(jié)點，并使其仍為單向循環(huán)鏈表，則可利用下述語句head=head-next；()。Ap=head；Bp=NULL;Cp-next=head;D.head=p;2以下說法不正確的是()。A.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)不必占用連續(xù)的存儲空間B-種邏輯結(jié)構(gòu)只能有唯一的存儲結(jié)構(gòu)C-種邏輯結(jié)構(gòu)可以有不同的存儲結(jié)構(gòu)D線性表的順序存儲結(jié)構(gòu)必須占用連續(xù)的存儲空間3把數(shù)據(jù)存儲到計算機中，并具體體現(xiàn)()稱為物理結(jié)構(gòu)。A.數(shù)據(jù)元素間的邏輯關(guān)系B數(shù)據(jù)的處理

2、方法C數(shù)據(jù)的性質(zhì)D數(shù)據(jù)的運算4鏈表所具備的特點之一是()。A.可以隨機訪問任一結(jié)點B需要占用連續(xù)的存儲空間C插入元素的操作不需要移動元素D刪除元素的操作需要移動元素5圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在()的關(guān)系。A.-對一B多對多C-對多D每一個元素都有一個直接前驅(qū)和一個直接后繼6元素15，9，11，13按順序依次進棧，則該棧的不可能輸出序列是()（進棱出?？梢越惶孢M行）。A.13,11,9,15B.15,9,11,13C.13,11,15,9D.9,15,13,117設(shè)有一個14階的對稱矩陣A(第一個元素為al，1)，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從

3、1開始），則矩陣中元素a4.3在一維數(shù)組B中的下標(biāo)是()。A9B10C11D88在一棵二叉樹中，若編號為8的結(jié)點存在右孩子，則右孩子的順序編號為()。A18B16C15D179設(shè)一棵哈夫曼樹共有14個非葉結(jié)點，則該樹總共有()個結(jié)點。A29B27C30D2810.如圖1所示的一個圖，若從頂點a出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為()。A.abecdfB.acfebdC.aebcfdD.aedbfc二、填空題（每小題2分，共24分）11.隊列的特點之一是：元素進、出隊的次序是：先進 。12. 結(jié)構(gòu)中，數(shù)據(jù)元素間存在一對多的關(guān)系。13.對稀疏矩陣進行壓縮存儲，矩陣中每個非零元

4、素對應(yīng)的三元組包括該元素的三項信息是 。14.在對11個記錄的序列(12，35，9，7，2，11，56，95，37，58，60)進行直接插入排序時，當(dāng)把第6個記錄11插入到有序表時，為尋找插入位置，元素間需比較 次。（由小到大排列）15.哈希函數(shù)是記錄關(guān)鍵字的值與該記錄 之間所構(gòu)造的對應(yīng)關(guān)系。16.20個元素進行冒泡法排序，通常需要進行19趟冒泡，其中第10趟冒泡共需要進行 次元素間的比較。17.-棵有19個結(jié)點的二叉樹，采用鏈?zhǔn)浇Y(jié)構(gòu)存儲，該樹結(jié)構(gòu)中有 個指針域為空。18.中序遍歷一棵 樹可得到一個有序序列。19.二叉排序樹插入操作中，新插入的結(jié)點總是以樹的 結(jié)點被插入的。20.廣義表的(a，

5、(d，a，b)，h，(e，(i，j)，k)深度是 。21序列4，2，5，3，8，6，7，9，采用歸并排序算法（升序），經(jīng)一趟歸并后，序列的結(jié)果： 。22.字符串a(chǎn)l一“teijing”，a2一“tef”，a3一“teifang“，a4一“tefi”最小的是_。三、綜合題（每小題中每問6分，共30分）23.設(shè)查找表為序號1234567891011序列1121819375565778586117(1)畫出對上述查找表進行折半查找所對應(yīng)的判定樹（樹中結(jié)點用下標(biāo)表示）。(2)說明成功查找到元素86需要經(jīng)過多少次比較？(3)求在等概率條件下，成功查找的平均比較次數(shù)？24.(1)-組記錄的關(guān)鍵字序列為(2

6、6，59，36，18，20，25)，給出利用堆排序（堆頂元素是最小元素）的方法建立的初始堆（要求以完全二叉樹描述）。(2)對關(guān)鍵字序列(26，59，36，18，20，64)采用快速排序，給出以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后的結(jié)果。試卷代號：1252數(shù)據(jù)結(jié)構(gòu)（本）試題答案及評分標(biāo)準(zhǔn)（供參考）2018年1月一、單項選擇題（每小題3分，共30分）1C2B3A4C5B6C7A8D9A10.D二、填空題（每小題2分，共24分）11.先出12.樹形13.行下標(biāo)列下標(biāo)數(shù)組元素14.315.存儲位置16.io17.2018.二叉排序樹19.葉20.421.2,4,3,5,6,8,7,922a2三、綜合

7、題（每小題中每問6允，共30分）23(1) (2)3次(3)平均查找長度=(1+2*2_-3*4+4*4)/11=324.(1)18,20,25,59,26,36(2)20,18,26,36,59,64四、程序填空題（每空2分，共16分）25.(1)low=high(2)(low+high)/2(3)mid;(4)amid.keydata)(2)lnorder(BT-left)(3)abdfec試卷代號：1252國家開放大學(xué)（中央廣播電視大學(xué)）2018年春季學(xué)期“開放本科”期末考試數(shù)據(jù)結(jié)構(gòu)（本） 試題2018年7月一、單項選擇題（每小題3分，共30分）1數(shù)據(jù)的存儲結(jié)構(gòu)包括數(shù)據(jù)元素的表示和( )

8、。 A.數(shù)據(jù)處理的方法 B相關(guān)算法 C數(shù)據(jù)元素的類型 D數(shù)據(jù)元素間的關(guān)系的表示2在一個頭指針為head的單向鏈表中，p指向尾結(jié)點，要使該鏈表成為單向循環(huán)鏈表可執(zhí)行( )。 A. p- head-next; B.head-next=p; C.head-next= p- next; D.p-next=head;3元素111，113，115，117按順序依次進棧，則該棧的不可能輸出序列是( )（進棧出?？梢越惶孢M行）。 A. 117 ,115 ,113 ,111 B.111, 113, 115, 117 C. 117 ,115 ,111,113 D.113 ,111,117 ,1154以下說法正確的

9、是( )。 A棧的特點是先進后出 B棧的特點是先進先出 C隊列的特點是先進后出 D棧和隊列的特點都是先進后出5設(shè)有一個20階的對稱矩陣A(第一個元素為a1，1)，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a6，：在一維數(shù)組B中的下標(biāo)是( )。 A. 24 B17 C16 D236設(shè)一棵有2n+l個結(jié)點的二叉樹，除葉結(jié)點外每個結(jié)點度數(shù)都為2，則該樹共有( )個葉結(jié)點。 An Bn+l Cn+2 Dn-l7已知如圖1所示的一個圖，若從頂點a出發(fā)，按廣度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為( )。A. abecdf B. aecbdf

10、C. aebcfd D: aedfcb8線性表以( )方式存儲，能進行折半查找。 A.關(guān)鍵字有序的順序 B順序 C鏈接 D二叉樹9一棵具有38個結(jié)點的完全二叉樹，最后一層有( )個結(jié)點。 A.7 B5 C6 D810.對一個棧頂指針為top的鏈棧進行出棧操作，用變量e保存棧頂元素的值，則執(zhí)行( )。 A.e- topnext; topdata=e; B.top=topnext; e=topdata;C. e=topdata; top=topnext; D.top=topnext; e=data;二、填空題（每小題2分，共24分）11數(shù)組a經(jīng)初始化char a 一“English”；a7中存放的

11、是_。12設(shè)有串pl=”ABADF”，P2=”ABAFD”，P3=”ABADFA”P4=”ABAF”，四個串中最大的是_。13.在一棵二叉樹中，若編號為i的結(jié)點存在右孩子，則右孩子的順序編號為_。14.設(shè)有一個長度為20的順序表，要插入一個元素，并作為第8個元素，需移動元素的個數(shù)為_。15.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為_ 結(jié)構(gòu)。16.設(shè)有一棵深度為4的完全二叉樹，第四層上有5個結(jié)點，該樹共有_個結(jié)點。（根所在結(jié)點為第1層）17. -棵二叉樹中有n個非葉結(jié)點，每一個非葉結(jié)點的度數(shù)都為2，則該樹共有_個葉結(jié)點。18.在對一組記錄(55，39，97，22，16，73，65，47，88)進行直

12、接插入排序時，當(dāng)把第7個記錄65插入到有序表時，為尋找插入位置需比較_次。（由小到大排序）19.n個元素進行冒泡法排序，第j趟冒泡要進行_次元素間的比較。20. 一棵有n個葉結(jié)點的哈夫曼樹，則該樹共有_個結(jié)點。21.中序遍歷_可得到一個有序序列。22.廣義表(a，b)，d，e，(i，j)k)的長度是_。三、綜合題（每小題中每問6分，共30分）23(1)設(shè)有數(shù)據(jù)集合40，29，7，73，101，4，55，2，81，92，39），依次取集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹。 (2)-組記錄的關(guān)鍵字序列為(5，8，6，3，4，7)，利用堆排序（堆頂元素是最小元素）的方法建立初始堆。（要求用完全二叉樹表示）

13、24(1)以2，3，4，7，8，9作為葉結(jié)點的權(quán)，構(gòu)造一棵哈夫曼樹。(2)給出上述哈夫曼樹葉結(jié)點的哈夫曼編碼。 (3)-組記錄的關(guān)鍵字序列為(37，70，47，29，31，85)，利用快速排序，以第一個關(guān)鍵字為分割元素，給出經(jīng)過一次劃分后結(jié)果。（從小到大排序）四、程序填空題（每空2分，共16分） 25.設(shè)線性表為(6，10，16，4)，以下程序用說明結(jié)構(gòu)變量的方法建立單向鏈表，并輸出鏈表中各結(jié)點中的數(shù)據(jù)。 # define NULL 0 void main( ) NODE a,b,c,d,*head,*p; adata=6; bdata=10, cdata=16； ddata=4；/*d是尾結(jié)

14、點* head= (1) ； anext=&b； bnext=&c； cnext= &d; (2) ；*以上結(jié)束建表過程* p=head; /*p為工作指針，準(zhǔn)備輸出鏈表* do printf(“%dn”，(3) )； (4)_ ； ) while（ （5） )；26.以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、 右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點）。 void Inorder (struct BTreeNode*BT) if(BT! =NULL) (1) ； (2) ； Inorder(BTright); 利用上述程序?qū)τ?/p>

15、圖進行遍歷，結(jié)果是；(3) ; 試卷代號：1252國家開放大學(xué)（中央廣播電視大學(xué)）2018年春季學(xué)期“開放本科”期末考試數(shù)據(jù)結(jié)構(gòu)（本） 試題答案及評分標(biāo)準(zhǔn)（供參考） 2018年7月一、單項選擇題（每小題3分，共30分） 1D 2D 3C 4A 5B 6B 7B 8A 9A 10.C二、填空題（每小題2分，共24分） 11字符串的結(jié)束符 12p2 13. 2i+1 14. 13 15圖狀 16. 12 17n+1 18. 3 19. Nj 20. 2n1 21.二叉排序樹 22. 4三、綜合題（每小題中每問6分，共30分） 23(1)（2）3，4，6，8，5，7 24.（1） (2)2:0000

16、 3 0001 4 001 7 10 8 11 9 01 (3) 31,29,37,47,70,85四、程序填空題（每空2分，共16分） 25(1)a (2)dnext=NULL (3)pdata (4)p=pnext (5)p! =NULL 26. (l)lnorder(BTleft) (2)printf( %c,BTdata) (3)bedafc試卷代號：1252數(shù)據(jù)結(jié)構(gòu)（本） 試題2019年7月一、單項選擇題（每小題3分，共30分）1.以下說法正確的是（ ）。A.在順序表中可以隨機訪問任一結(jié)點B.-種邏輯結(jié)構(gòu)在存儲時只能采用一種存儲結(jié)構(gòu)C.對鏈表進行插入、刪除元素的操作一定要移動結(jié)點D.

17、在鏈表中可以隨機訪問任一結(jié)點2.線性表在存儲后，如果要求：僅通過已知的指向第i個結(jié)點的指針，進行相關(guān)操作，訪問到該結(jié)點的前驅(qū)結(jié)點，則采用（ ）存儲方式是不可行的。A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.順序表3.棧和隊列的共同特點是（ ）。A.都是先進后出B.元素都可以隨機進出C.只容許在端點處插入和刪除元素D.都是先進先出4.元素4，6，8，10按順序依次進棧，按該棧的可能輸出序列依次入隊列，該隊列的可能輸出序列是（ ）（進棧出?？梢越惶孢M行）。A.10，8，4，6B.10，6，4，8C.8，4，6，10D.10，8，6，45.在一個不帶頭結(jié)點的鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，從該隊列

18、中進行出隊操作，并把結(jié)點的值保存在變量x中的操作為（ ）。A.x= r-data; r= r- next;B.r=r- next; x= r- data;C.x= f-data; f= f- next;D.f=f-next; x= f-data;6.設(shè)有一個18階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣元素a。，。對應(yīng)于數(shù)組B中第（ ）號元素。（矩陣中的第1個元素是ai，）A.42B.39C.38D.407.-棵采用鏈?zhǔn)酱鎯Φ亩鏄渲?，共有n-l個指針域被有效使用（即指針域為非空）。該二叉樹中有（ ）個指針域為空。A.n+lB.n

19、C.n-lD.n-28.設(shè)一棵哈夫曼樹共有n個非葉結(jié)點，則該樹共有（ ）個結(jié)點。A. 2nB.2n+lC.2n-lD.2n+29.如圖所示，若從頂點a出發(fā)，按圖的廣度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。A.ahbedfcB.ahcfebdC.ahebcdfD.ahebcfd10.線性表以（ ）方式存儲，能進行折半查找。A.關(guān)鍵字有序的鏈接B.順序C.關(guān)鍵字有序的順序D.數(shù)組二、填空題（每小題2分，共24分）11.n個元素進行冒泡法排序，通常需要進行_ _趟冒泡。12.在對一組序列(35，19，77，2，6，53，55，27，26，98)進行直接插入排序時，當(dāng)把第9個記錄26插

20、入到有序表時，為尋找插入位置需進行_ 次元素間的比較。13.在C語言中，分別存儲“S”和s，各需要占用_ _字節(jié)。14.數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示稱為_ _結(jié)構(gòu)。15.在一棵二叉樹中，若編號為i的結(jié)點是其雙親結(jié)點的左孩子，則i結(jié)點的雙親結(jié)點的順序編號為_ _。16.設(shè)有一個頭指針為head的單向鏈表，p指向表中某一個結(jié)點，且有p- next為NULL，現(xiàn)要把該單向鏈表構(gòu)造成單向循環(huán)鏈表，可通過操作 。17.從一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用d保存被刪結(jié)點的值，可執(zhí)行d=top-data;和 。(結(jié)點的指針域為next，數(shù)據(jù)域為data)。18.循環(huán)鏈隊列中，設(shè)front和re

21、ar分別為隊頭和隊尾指針，（最多元素為MaxSize，采用少用一個元素的模式），判斷循環(huán)鏈隊列為滿的條件為 。19. -棵有7個權(quán)重值構(gòu)造的哈夫曼樹，共有 個結(jié)點。20.二叉樹中有1個1度結(jié)點，8個2度結(jié)點，則該二叉樹樹共有_ _個結(jié)點。21.如圖所示的二叉樹，其先序遍歷序列為 。22.在查找表中，通過記錄的某關(guān)鍵字能唯一地確定一個記錄，該關(guān)鍵字稱為 。三、綜合題（每小題6分，共30分）23.(1)對給定權(quán)值4，2，6，6，7，8，構(gòu)造高度為4層的哈夫曼樹。（設(shè)根為第1層）提示：構(gòu)造中當(dāng)出現(xiàn)有兩個以上值相等的可選結(jié)點時，可適當(dāng)選擇結(jié)點組合，以控制樹的高度。(2)求樹的帶權(quán)路徑長度。24.如下的

22、一棵二叉棵樹，(1)請給出前序遍歷序列？請給出中序遍歷序列？(2)把1，2，3，4，5，6，7，8，9填人，使它成為一棵二叉排序樹。提示：設(shè)圖中的樹是二叉排序樹，則中序遍歷序列是有序的，從而找出中序遍歷序列與1，2，9的對應(yīng)關(guān)系。(3)在圖中給出在二叉排序樹中插入結(jié)點2.5的結(jié)果。四、程序填空題（每空2分，共16分）25.以下函數(shù)為直接選擇排序算法，對al,a2，an中的記錄進行直接選擇排序，完成程序中的空格typedef struct int key;NODE;void selsort(NODE a ,int n)int i,j,k;NODE temp;for(i=1；i=(1) ；i+)k

23、=i：for(j=i+1;j=(2) ；j+)if(aj.keydata；while (q-next!=NULL)q=q-next;(1) q=p；p= p-next；while(p-datal =x) q=p；(2) (3) 試卷代號：1252數(shù)據(jù)結(jié)構(gòu)（本） 試題答案及評分標(biāo)準(zhǔn) 2019年7月一、單項選擇題（每小題2分，共30分） 1A 2A 3C 4D 5C 6C 7.A 8B 9C 10.C二、填空題(每題2分，共24分) 1. n-1 12. 6 13.兩個和1個 14存儲結(jié)構(gòu) 15. i/2 16. p-next= head; 17top=top- next.; 18. front=

24、 =(rear+1)%MaxSize 19. 13 19. 18 20. 1 21. 215934786 22主關(guān)鍵字三、綜合應(yīng)用題（每小題6分，共30分） 23(1)(2) WPL=4+2+6+6-* 3+ (7+8) 2=8424. (1)前序 A1 A2 A4 A7 A8 A5 A9 A3 A6中片： A7 A4 A8 A2 Ao A9 A1 A3 A6(2)A7 A4 A8 A2 A5 A9 A1 A3 A6 1 2 3 4 5 6 7 8 9（3）四、程序填空題（每空2分，共16分） 25.(1)n-1 (2)n (3)k=j (4)ai一ak (5)akl=temp 26. (1)

25、 q-next= head; (2)p= p- next; (3) q- next= p- next,試卷代號：1252 座位號國家開放大學(xué)2 0 1 9年秋季學(xué)期期末統(tǒng)一考試數(shù)據(jù)結(jié)構(gòu)（本）試題 2020年1月一、單項選擇題(每小題3分，共30分)1以下說法不正確的是( )。 A線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)不必占用連續(xù)的存儲空間 B一種邏輯結(jié)構(gòu)只能有唯一的存儲結(jié)構(gòu) C. 一種邏輯結(jié)構(gòu)可以有不同的存儲結(jié)構(gòu) D線性表的順序存儲結(jié)構(gòu)必須占用連續(xù)的存儲空間2單向鏈表所具備的特點之一是( )。 A可以隨機訪問表中任一結(jié)點 B需要占用連續(xù)的存儲空間 C插入元素和刪除元素的操作不需要移動元素 D可以通過指向某元素的

26、指針操作，直接訪問到該結(jié)點的直接前驅(qū)結(jié)點3線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在( )的關(guān)系。 A多對多 B一對多 C一對一 D每一個元素都有一個直接前驅(qū)和一個直接后繼4在一個單向鏈表中，p和q分別是指向結(jié)點類型的指針，要刪除p所指結(jié)點的直接后繼結(jié)點，可執(zhí)行( )。 A.q=p-next;p-next= q- next Bq=p;p=q-next C.q-p- next;p-next=q Dq-p；p-next=q5設(shè)有帶頭結(jié)點的且頭指針為head的非空的單向鏈表，指針p指向其尾結(jié)點，要使該單向鏈表成為不蒂頭結(jié)點的單向循環(huán)鏈表，則可利用下述語句：head=head-next;和( )。 Ap- he

27、ad B. p=NULL C. p-next=head n head=p6元素20，14160，180按順序依次進棧，則該棧的不可能輸出序列是( )。（進棧出棧可以交替進行）。 A. 180,160,14,20 B.20,14,160,180 C. 180,160,20,14 D. 14,20,180,1607設(shè)有一個15階的對稱矩陣A(第一個元素為a1，1)，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a5，3在一維數(shù)組B中的下標(biāo)是( )。 A11 B13 C14 D128設(shè)一棵有n個葉結(jié)點的二叉樹，度數(shù)為1的結(jié)點有4個，則該樹共有( )

28、個結(jié)點。 A2n B2n+3 C2n+2 D2n+49設(shè)根結(jié)點所在層為第一層，一棵具有5層的完全二叉樹，最后一層有6個結(jié)點，則該樹總共有( )個結(jié)點。 A22 B20C.21 D.10 10已知如圖l所示的一個圖，若從頂點a出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為( )。圖1 Aabecdfg BacfebdgCaebcfdg Daedfcbg二、填空題（每小題2分，共24分） 11把數(shù)據(jù)存儲到計算機中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯關(guān)系稱為_結(jié)構(gòu)。 12設(shè)有一個長度為22的順序表，要刪除第8個元素需移動元素的個數(shù)為_。 13在一棵二叉樹中，若編號為i的結(jié)點存在右孩子，則右孩子的

29、順序編號為_。 14設(shè)一棵哈夫曼樹共有18個非葉結(jié)點，則該樹總共有_個結(jié)點。 15棧元素的進、出棧次序是：后進一 。 16在對10個記錄的序列(8，36，19，78，4，10，53，45，27，68)進行直接插入排序時，當(dāng)把第6個記錄10插入到有序表時，為尋找插入位置，元素間需比較_次。 17n個元素進行冒泡法排序，通常需要進行n-l趟冒泡，其中第j趟冒泡共需要進行 次元素間的比較。 18序列7，1，4，2，5，3，8，6用歸并法排序（升序），經(jīng)一次歸并后的結(jié)果序列是 。 19中序遍歷一棵_ 樹可得到一個有序序列。 20廣義表(h，(b，a)f，e，（i，j)，k）的深度是_。 21_結(jié)構(gòu)中，

30、數(shù)據(jù)元素間存在一對多的關(guān)系。22字符串a(chǎn)l= beijing”，a2一“bef”，a3一“beifang”，a4一“befi”最小的是_。三、綜合題（每小題中每問6分，共30分）23設(shè)查找表為序號1234567891011序列11162425436171839192123(1)畫出對上述查找表進行折半查找所對應(yīng)的判定樹（樹中結(jié)點用下標(biāo)表示）。(2)說明不成功查找元素45需要經(jīng)過多少次比較？(3)求在等概率條件下，成功查找的平均比較次數(shù)？ 24(1) 一組記錄的關(guān)鍵字序列為(37，67,43，25，27，32)，給出利用堆排序（堆頂元素是最小元素）的方法建立的初始堆（要求以完全二叉樹描述）。 (

31、2)對關(guān)鍵字序列(40，73，49，3133，77)采用快速排序，給出以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后的結(jié)果。四、程序填空題（每空2分，共16分） 25.以下函數(shù)在a0到an-l中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時返回-l，完成程序中的空格。 typedef struct int key, NODE; int Binary_Search(NODEa ,int n,int k) int low, mid, high; low=0： (l) while(_low= high) Mid= (2) if (amid. key=k) return(3) el

32、se if(amid. keyright);) 利用上述程序?qū)ο聢D進行遍歷，結(jié)果是(3) ；圖2試卷代號：1252國家開放大學(xué)2 0 1 9年秋季學(xué)期期末統(tǒng)一考試數(shù)據(jù)結(jié)構(gòu)（本） 試題答案及評分標(biāo)準(zhǔn)（供參考） 2020年1月一、單項選擇題（每小題3分，共30分） 1B 2C 3C 4A 5C 6C 7B 8B 9C 10D二、填空題（每小題2分，共24分） 11存儲（物理） 12. 14 13. 2i+1 14. 37 15先出 16.4 17n-j 18. 1,7,2.4,3,5.6,8 19二叉排序樹 20.3 21樹形 22a2三、綜合題（每小題中每問6分，共30分）23(1)(2)4次(

33、3)平均查找長度=(1+2*2+3* 4+4* 4)/11=324. (1)25,27,32,67.37.43 (2)33，31,40 ,49 ,73,77四、程序填空題（每空2分，共16分） 25. (1) high=n-1 (2)low+high)/2 (3)mid (4)high=mid-1 (5)return-1 26. (1)printf(“%c”.BT-data) (2)Preorder(BT-left) (3)a b df g e c試卷代號：1 252國家開放大學(xué)2 0 2 0年春季學(xué)期期末統(tǒng)一考試數(shù)據(jù)結(jié)構(gòu)（本） 試題2020年7月一.單項選擇題（每小題3分，共30分）1.設(shè)主

34、串為“DBcCDABcdEFdBc”，以下模式串能與主串成功匹配的是（ ）。A.dBcB.BCdC.DBCD.Abc2.順序表所具備的特點之一是（ ）。A.可以隨機訪問任一結(jié)點B.不用占用連續(xù)的存儲空間C.插入刪除操作不需要移動元素D.必須要有頭指針3.在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，p指向一個已生成的結(jié)點，現(xiàn)要為該結(jié)點的數(shù)據(jù)域賦值e，并使結(jié)點入隊的運算為p-data=e;p-next一NULL;和（ ）。A. f-next=p; f=pB.r-next=p;r=pC. p-next=r;r=pD.p-next=f; f=p4.在一個頭指針為head的帶頭結(jié)點的單向循環(huán)鏈表中，p

35、指向尾結(jié)點，要使該鏈表成為不帶頭結(jié)點的單向鏈表，可執(zhí)行（ ）。A. head= head-next;p=NULLB.headhead- next; P- next= headC.head- next= p- nextD. head- head-next;p-next=NULL5。元素212，214，216，218按順序依次進棧，則該棧的不可能輸出序列是（ ）（進棧出?？梢越惶孢M行）。A.212, 214, 216, 218B.216, 214, 212,218C.214 ,212, 218, 216D.218, 216, 212, 2146.設(shè)有一個25階的對稱矩陣A(第一個元素為ai，采用壓

36、縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中(數(shù)組下標(biāo)從1開始)，則矩陣中元素a4，s在一維數(shù)組B中的下標(biāo)是（ ）。A.10B.9C.7D.87.在一棵二叉樹中，編號為19的結(jié)點的雙親結(jié)點的順序編號為（ ）。A.9B.8C.34D.358.線性表以（ ）方式存儲，能進行折半查找。A.關(guān)鍵字有序的B.順序C.鏈接D.關(guān)鍵字有序的順序9.如圖1所示的一個圖，若從頂點a出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。A. abecdfg B. aecbdfgC. aebcfdg D. aedfcbg10.設(shè)一棵哈夫曼樹共有31個結(jié)點，則該樹共有（ ）個非葉子結(jié)點。 A

37、.14B.15 C.16D.17二、填空題（每小題2分，共24分）II._結(jié)構(gòu)中，數(shù)據(jù)元素的位置之間存在多對多的關(guān)系。12.設(shè)有一個長度為20的順序表，要插入一個元素，并作為第6個元素，需移動元素的個數(shù)為_ _。13.數(shù)組a經(jīng)初始化char a一“fhglisp”；a6中存放的是_。14.序列4，2，15，13，18，16，采用冒泡排序算法，經(jīng)一趟冒泡后，序列的結(jié)果是 。15.對19個元素的序列用冒泡排法進行排序，通常第7趟冒泡中，共需要進行 次元素間的比較。16.對一組記錄(41，25，93，20，12，78，46，51，89)進行直接插入排序（由小到大排序），當(dāng)把第7個記錄46插入有序表，

38、為尋找插入位置需比較_次。17.設(shè)有一棵深度為5的完全二叉樹，第5層上有4個結(jié)點，該樹共有一個結(jié)點。（根所在結(jié)點為第1層）18.設(shè)有串pl=”DEADFG”，P2=”DEAFDF”，P3=”DEADFAB”P4=”DEAFE”，四個串中最大的是_ _。19. 一棵有8個葉結(jié)點的哈夫曼樹，則該樹共有_ _個結(jié)點。20._ _遍歷二叉排序樹可得到一個有序序列。21.廣義表(g，(a，b，d，c)，d，e，(i，j)，k的長度是_ _。22.在一個單向鏈表中，已知q指向p所指結(jié)點的直接前驅(qū)結(jié)點，現(xiàn)要刪除p所指結(jié)點，則可以用操作q- next=_ _。三、綜合題（每小題中每問6分，共30分）23.(1

39、)設(shè)有數(shù)據(jù)集合50，39，17，83，111，14，65，13，91，102，49，依次取集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹。(2) -組記錄的關(guān)鍵字序列為(6，9，7，4，5，8)，利用堆排序（堆頂元素是最小元素）的方法建立初始堆。（要求用完全二叉樹表示）24.(1)如下為一個長度為10的有序表，給出按折半查找對該表進行查找的判定樹。(2)按折半查找對該表進行查找，求在等概率情況下查找成功的平均比較次數(shù)。(3)以1，2，3，6，7，8作為葉結(jié)點的權(quán)，構(gòu)造一棵哈夫曼樹。序號12345678910序列28356075798086909599四、程序填空題（每空2分，共16分）25.設(shè)線性表以不帶頭結(jié)

40、點的單向鏈表存儲，鏈表頭指針為head，以下程序的功能是：(1)輸出鏈表中各結(jié)點中的數(shù)據(jù)域data。(2)把該單向鏈表改為以p作為尾指針的單向循環(huán)鏈表。(鏈表中結(jié)點的指針域為next，數(shù)據(jù)域為data)。# define NULL 0void main（ ） NODE*head，*p；p= head； /*p為工作指針*doprintf(“%d n”，(1) )；(2) ；while(p -next!=(（3） );printf(“%dn”p-data);（4） ）26.以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data

41、為字符型，BT指向根結(jié)點）。完成程序中空格部分。void postorder (struct BTreeNode*BT)if(1) )postorder(BT-left)；(2) (3) 利用上述程序?qū)ο聢D所示二叉樹遍歷的結(jié)果為(4) 試卷代號：1252國家開放大學(xué)2 0 2 0年春季學(xué)期期宋統(tǒng)一考試數(shù)據(jù)結(jié)構(gòu)（本） 試題答案及評分標(biāo)準(zhǔn)（供參考） 2020年7月一、單項選擇題（每小題3分，共30分） 1A 2A 3B 4D 5D 6B 7A 8D 9D 10.B二、填空題（每小題2分，共24分） 11圖狀 12. 15 13.字符p 14. 2,4,13,15,16 ,18 15. 12 16.

42、 3 17. 19 18. P4 19. 15 20中序 21.5 22. P-next三、綜合題（每小題中每問6分，共30分） 23(1) (2)4，5，7，9，6，824.(1)(2) (1+2 * 2+3 * 4+4 * 3)/10=29/10 (3)四、程序填空題（每空2分，共16分） 25. (1) p-data (2) p=p-next (3) NULL (4)p-nex= head 26. (1) BT! =NULL (2) postorder(BT-right) (3) printf(%c,BT-data) (4)9，6，5，8，7，4 試卷代號：1252 國家開放大學(xué)2020

43、年秋季學(xué)期期末統(tǒng)一考試 數(shù)據(jù)結(jié)構(gòu)（本）試題 2021年1月一、單項選擇題（把合適的選項編號填寫在括號內(nèi)。每小題3分，共 45分）1.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為( )。 A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) D.線性結(jié)構(gòu)和非線性結(jié)構(gòu)2.下面程序段的時間復(fù)雜度是( )。for(i=l;i=n；i+) for（j=l；j=n；j+） cij=0； for(k=l；knext=q-next B.p=q-next C.p-next=q D.p-next=q4.設(shè)有一個長度為n的順序表，要在第i個元素之前（也就是插入元素作為新表的第i個元素），插入一個元素

44、，則移動元素個數(shù)為( )。 A.n-i B.n-i-l C.n-i+l D.i5.一個隊列的人隊序列是1，2，3，4。則隊列的輸出序列是( )。 A.4,3，2，1 B.1,2,3,4 C.1，4，3，2 D.3,2.4,16.在一個棧頂指針為top的鏈棧中，將一個p指針?biāo)傅慕Y(jié)點人棧，應(yīng)執(zhí)行( )。 A.top-next=p B.p-next=top-next;top-next=p C.p-next=top； top=p D.p- next= top-next, top= top-next7.判斷一個循環(huán)隊列Q(最多元素為m)為滿的條件是( )。 A.Q-front= =Q-rear B.Q

45、-front！ =Q-rear C.Q-front=(Q-rear+l)%m D.Q-front! =(Q-rear+l)%m8.設(shè)有兩個串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為( )。 A.求子串 B.連接 C.模式匹配 D.求串長9.一個非空廣義表的表頭( )。 A.不可能是原子 B.只能是子表 C.只能是原子 D.可以是子表或原子10.樹中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)加( )。 A.1 B.0 C.2 D.-111.在一棵二叉樹上，第5層的結(jié)點數(shù)最多為( )。 A.8 B.15C.16 D.3212.在一個圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的( )倍。 A.1

46、/2 B.1 C.2 D.413.對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則所有頂點鄰接表中的結(jié)點總數(shù)為( )。 A.n B.e C.2n D.2e14.有一個長度為12的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為( )。 A.37/12 B.39/12 C.41/12 D.35/1215.從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放人已排序序列的正確的位置上，此方法稱為( )。 A.插入排序 B.交換排序 C.選擇排序 D.歸并排序二、判斷題（根據(jù)敘述正確與否在奠后面的括號內(nèi)打?qū)μ枴啊被虼虿嫣枴啊?。每小題2分，共30分） 1

47、6.數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立的。( ) 17.數(shù)據(jù)結(jié)構(gòu)中，元素之間存在多對多的關(guān)系稱為圖狀結(jié)構(gòu)。( ) 18.設(shè)有一個單向鏈表，結(jié)點的指針域為next，頭指針為head，p指向尾結(jié)點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句p-next=head。( ) 19.設(shè)有一個單向循環(huán)鏈表，結(jié)點的指針域為next，頭指針為head，指針p指向表中某結(jié)點，若邏輯表達式p-next= =head;的結(jié)果為真，則p所指結(jié)點為尾結(jié)點。( ) 20.棧和隊列都是特殊的線性表，但它們對存取位置的限制不同。( ) 21.棧是限定在表的兩端進行插入和刪除操作的線性表，又稱為

48、先進先出表。( ) 22.遞歸定義的數(shù)據(jù)結(jié)構(gòu)通常用遞歸算法來實現(xiàn)對它的操作。( ) 23.一個空格的串的長度是0。( ) 24.對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應(yīng)的三元組包括該元素的行號、列號和元素值三項信息。( ) 25.深度為k的完全二叉樹至少有2k-l個結(jié)點。( ) 26.完全二叉樹中沒有度為1的結(jié)點。( ) 27.圖的生成樹是惟一的。( ) 28.對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。( ) 29.在順序查找、折半查找、哈希表查找3種方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是折半查找。( ) 30.n個元素進行冒泡法排序，通常需要進行n-l趟冒泡。( )

49、三、綜合應(yīng)用及程序設(shè)計題（每小題5分，共25分）31.在下面空格處填寫一條語句，以使下面的鏈?zhǔn)疥犃腥吭爻鲫牭乃惴ㄍ暾nt write(LinkQueue*q)(QueueNode*p；if(q-front= =q-rear) *隊空* printf（“隊空！無元素可取”）； exit(0)； while (q-fronr-next!=NULL) （p=q-front-next； q-front-next= p- next; *出隊* printf(“%4d”,p-data); free(p)； *釋放已出隊結(jié)點x *隊空時，頭尾指針指向頭結(jié)點* A.q-front=q-rear B.q

50、=q-next C.q-rear=q-front D.p=p-next 32.以下程序是先序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點）。 void Preorder (struct BTreeNode* BT) (if (BT! =NULL) _； Preorder(BT- left)； Preorder(BT- right)； A.printf(“%c”,BT-left) B.printf(“%c”.BT-right) C printf(“%c”,BT-data) D.printf(“%d”,BT-

51、data)33.一組記錄的關(guān)鍵字序列為(6，9，7，4，5，8)，利用堆排序（堆頂元素是最小元素）的方法建立初始堆是如下哪個圖？( ) 34.設(shè)關(guān)鍵字序列為：(36，69，46，28，30，74) (1)將此序列用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一趟劃分的結(jié)果為( )。（本小題3分） A.30,28.46,36,69,74 B.28,30,36,46,69,74 C.28,30,46,36,69,74 D.30,28.36,46,69,74 (2)用冒泡法對上述序列排序，經(jīng)過兩趟冒泡的結(jié)果序列為( )。（本小題2分） A.36,28,30,46,69,74 B.36,46,28,20,

52、69,74 C.38,36,30,46,69,74 D.28,36,30,46,69,74 35.設(shè)數(shù)據(jù)序列為：53，30，37，12，45，24，96) (l)從空二叉樹開始逐個插入該數(shù)據(jù)序列來形成二叉排序樹，若希望高度最小，應(yīng)該選擇的序列是( )。（本小題3分） A.45,24,53,12,37,96,30 B.37,24,12,30,53,40,96 C.12,24,30,37.45,53,96 D.30, 24 ,12,37,45,96,53 (2)用鏈接地址法將該數(shù)據(jù)序列構(gòu)造哈希表，哈希函數(shù)為H(key) =key mod 13，則散列地址為1的鏈中有( )個記錄。（本小題2分） A

53、.0 B.1 C.2 D.3試卷代號：1252國家開放大學(xué)2020年秋季學(xué)期期末統(tǒng)一考試數(shù)據(jù)結(jié)構(gòu)(本)試題答案及評分標(biāo)準(zhǔn)(供參考)2021年1月一、單項選擇題(每小題3分,共45分)1.D2.D3.A4.C5.B6.C7.C8.C9.D10.A11.C12.C13.D14.A15.A二、判斷題(每小題2分,共30分)16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.三、綜合應(yīng)用及程序設(shè)計題(每小題5分,共25分)31.C.或q-rear=q-front32.C.或printf(“%c”,BT-data)33.C.34.(1)D.或30,28,36,46,

54、69,74(本小題3分)(2)A.或36,28,30,46,69,74(本小題2分)35.(1)B或37,24,30,53，45,96(本小題3分)(2)B.或1(本小題2分)試卷代號：1252國家開放大學(xué)2021年春季學(xué)期期末統(tǒng)一考試數(shù)據(jù)結(jié)構(gòu)（本） 試題2021年7月一、單項選擇題（把合適的選項編號填寫在括號內(nèi)。每小題3分，共45分）1.下面程序段的時間復(fù)雜度是（ ）。for（i=1；i=n；i+）for（j=1；j=n；j+）cij=O；for(k=l；k=n；k+)cij=cij+aik*bkj；A.O(1)B.O(log2n)C.O(n)D.O(n3)2.數(shù)據(jù)的存儲結(jié)構(gòu)包括數(shù)據(jù)元素的表

55、示和（ ）。A.數(shù)據(jù)處理的方法B.相關(guān)算法C.數(shù)據(jù)元素的類型D.數(shù)據(jù)元素間的關(guān)系的表示3.在一個單鏈表中p所指結(jié)點之后插入一個s所指的結(jié)點時，可執(zhí)行（ ）。A.p-next=s；s-next=p-nextB.p-next=s-nextC.p=s-nextD.s-next=p-next；p-next=s4.在一個單鏈表中，p、q分別指向表中兩個相鄰的結(jié)點，且q所指結(jié)點是p所指結(jié)點的直接后繼，現(xiàn)要刪除q所指結(jié)點，可用語句（ ）。A.p=q-nextB.p-next=qC.p-next=q-nextD.q-next=NULL5.若讓元素1，2，3依次進棧，則出棧順序不可能為（ ）。A.3，2，1B.2,1,3C.3，1，2D.1，3,26.表達式a*(b+c)-d的后綴表達式是（ ）。A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd7.判斷順序棧s滿（元素個數(shù)最多n個）的條件是（ ）。A.s-top= =0B.s-top!=0C.s-top= =n-lD.s-top!=n-l8.串的長度是指（ ）。A.串中所含不同字母的個數(shù)B.串中所含字符的個數(shù)C.串中所含不同字符的個數(shù)D.串中所含非空格字符的個數(shù)9.廣義表的(a，(d，a，b)，h，(e，(i，j)，k)深度是（ ）。A.6B.10C.8D.410.在一棵二叉樹中，若編號為8的結(jié)點存在右孩子，則右孩子的順