年國家開放大學電大數據結構期末綜合考題及答案一、單項選擇題1.數據的物理結構(D)。A.與數據的邏輯結構無關B.僅僅包括數據元素的表示C.只包括數據元素間關系的D.包括數據元素的表示和關系的表示2.數據元素是數據A.只能有一個數據項組成B.至少有二個數據項組成C.可以是一個數據項也可以由若干個數據項組成D.至少有一個數據項為指針類型3.從nA.基本操作是數據元素間的交換B.算法的時間復雜度是O(n2)C.算法的時間復雜度是D.需要進行(n+1)次數據元素間的比較4.線性表的順序結oA.邏輯上相鄰的元素在物理位置上不一定相鄰B.數據元素是不能隨機訪問的C.邏輯上相鄰的元素在物理位置上也相鄰D.進行數據元素的插入、刪除效率較高5.以下表中可以隨機A.單向鏈表B.雙向鏈表D.順序表6.帶頭結點的單向鏈表為空的判斷條件是(B)(設頭指針為head)。D.n-i8.線性結構中數據元素的位置之間存在(A)的關A.x=top-data;top=toD.top-next=top;x=top-data;10.設順序存儲的線性表長度為n,要刪除第i個元素，按課本的算法，當i=(C)時，D.411.以下說法正確的是(CC.棧的刪除和插入操作都只能在棧頂進行B.棧的特點是D.隊列的刪除和插入操作都只能在隊頭進行12以下說法在隊頭進行13.串函數StrCmp(“abA”,”aba”的值為(D)。C.“abAaba”D.dcba15.設有一個12階的對稱矩陣A,采用壓縮存儲A的第一個元素為a1,1,數組b的下標從1開始),則矩陣A中第4行的元素在數組b中的下標i一定有(A)。D.m/217.設有一個帶頭結點的鏈隊列，隊列中每個結點鏈隊列的頭指針和尾指針，要執行出隊操作，用x保存出隊元A.連通圖G一定存在生成樹B.連通圖G的生成樹中一定包含G的所有頂點C.連通圖G的生成樹中不一定包含G的所有邊D.連通圖G的生成樹可以是不連通的19.散列查找的原A.在待查記錄的關鍵字值與該記錄的存儲位置之間建立確定的對應關系B.按待查記錄的關鍵字有序的順序方C.按關鍵字值的比較進行查找D.基于二分查找的方法20.空串的長度為(A)。D.321.排序過程中，每一趟從無序子表中將一個待排序的記錄按其關鍵字的大小放置到已經排好序的子序列的適當位置，直到全部排好序為止，該排序算法是D)。A.選擇排序B.快速排序C.冒泡排序D.直接插入排序22.采用順序查找法對長度為n的線性表進行查找(不采用表尾設監視哨的方法),最壞的情況下要進行(B)次元素間D.n/223.設有一個10階的對稱矩陣A,采用壓縮存儲A的第一個元素為a1,1,數組b的下標從1開始),則矩陣元素a5,3對應一維數組b的數組元素是(C)。D.b24.如圖1若從頂點a出發按廣度優先搜索法進行遍歷，則可能得到的頂點序列為(D)。A.acebdfghB.aebcghdfC.aedfbcghD.abecdfgh圖125.已知如圖2所示的一個圖，若從頂點a出發，按A.abecdf圖226.一棵哈夫曼樹總共有23個結點，該樹共有(D)個葉結點(終端結點)。2.通常可以把某城市中各公交站點間的線路圖抽象成_圖狀 3.設有一個單向鏈表，結點的指針域為next,頭指針為用語句_p-next=head_。4.設有一個單向循環鏈表，頭指針為head,鏈表中結點的指針域為next,p指向尾結點的直接前驅結點，若要刪除尾結點，得到一個新的單向循環鏈表，可執行操作_p-next=head。5.循環隊列的隊頭指針為f,隊尾指針為r,當r=f_時表明隊列已空。6.在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結點的指針域為next,則插入一個s所指結點的操作為_r-next=s_;r=s;7.設有一個鏈棧，棧頂指針為hs,現有一個s所指向的結點要入棧，則可執行操作_s-next=hs;和hs=s;8.循環隊列的隊頭指針為f,隊尾指針為r,當 r==f時表明隊列為空。9.在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結點的指針域為next,則插入一個s所指結點的操作為r-next=s;11.串的兩種最基本的存儲方式分別是_順序存儲和鏈12.一棵二叉樹沒有單分支結點，有6個葉結點，則該樹13.一棵二叉樹中順序編號為i的結點，若它存在左、右孩子，則左、右孩子編號分別為_2i 14.按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有-15.兩個串相等的充分必要條件是--串長度相等且對應位置16.把數據存儲到計算機中，并具體體現數據之間的邏輯結構稱為物理存儲結構。17.一棵二叉樹葉結點(終端結點)數為5,單分支結點數為2,該樹共有_11_個結點。18.如圖3所示的二叉樹，其后序遍歷序列為19.根據搜索方法的不同，圖的遍歷有_深度優先搜索遍歷20.二叉樹為二叉排序的充分必要條件是其任一結點的值均21.一個有序表{3,4,10,14,34,43,46,64,75,78,90,96,130}用折半查找法查找值為90的結點，經4次比較后4(1)設有查找表{5,14,2,6,18,7,4,1依次取表中數據，構造一棵二叉排序樹.(2)說明如何通過序列的二叉排序樹得到相中序遍歷5.(1)利用篩選過程把序列{42,82,67,102,16,32,57,52}建成堆(小根堆),畫出相應的完全二叉樹(不(2)寫出對上述堆對應的完全二叉樹進行中序遍歷得到的序列四、程序填空題1.以下函數在a到a[n-1]中，用折半查找算法查找關鍵字等于k的記錄，查找成功返回該記錄的下失敗時返回-1,完成程序中的空格typedefkey;....}NODE;intBinary_Search(NODEa[],intn,intk) 」2x是要進棧的結點的數據 ; }3x為voidInQueue(ElemTy ; ; 三、綜合應用題(每小題010分，共030分)4282675257321610216423252576初始樹堆1.(1)low=high(2)mid(3)a[2.(1)low=high(2)mid(3)a[mid].keyk;(4)high=mi3.(1)sizeof(structnode)(2)p-next=top(3)top=p4.(1)malloc(sizeof(structnode))(2)rear-next=p(3)p期末綜合練習二二一、單項選擇題1.(CD.數據項2.同一種邏輯結構(A.只能有唯一的存儲結構B.可以有不同的存儲結構C.只能表示某一種數據元素之間的關系D.以上三種說法均不正確3.設鏈表中的結點是NODE類型的結構體變量，且有NODE*p;為了申請一個新結點，并由p指向該結點，可用以下語句(Ap=(Bp=(*NODE)malloc(sizeof(NODE));C.p=(NODE)malloc(sizeof(p));D.p=(NODE*4.鏈表所具備的特點是(A.可以隨機訪問任一結點B.占用連續的存儲空間C.插入刪除元D.可以通過下標對鏈表進行直接訪問5.設順序存儲的線性長度為n,要在第i個元素之前插入一個新元素，按課本的算點，可用的語句是(m,則m一定不可能是(A.x=top-data;top=toD.top=top-next;x=data;19.以下說法正確的是(A.連通圖G的生成樹中可以包含回路B.連通圖G的生成樹可以是不連通的C.連通圖G的生成樹一定是唯一的D.連通圖G的生成樹一定是連通而不包含回路的20.在一個的運算為(n-1趟冒泡，在第j趟冒泡中共要進行()次元素間的比較。D.n-j-122.一個棧的進棧序列是a,b,c,d不可能輸出序列是()(進棧出棧可以交替進行)。24.有一個長度為10的有序表，按折半查找對該表進行查D.31/1025.如圖1若從頂點a出發按深度優先搜索法進A.aebcfdB.abedcfC.acebdfD.acfbdeD.4129.數據的()結構與所使用的計算機無關。A.邏輯B.物理D.邏輯與存儲30.在一個無向圖中，所有頂點的度數之和等于邊數的(二、填空題1.通常可以把一本含有不同章節的書的目錄結 3.要在一個單向鏈表中p所指向的結點之后插入一個s這樣做正確嗎?若正確則回答正確，若不正確則說明應如何(1)以2,3,4,7,8,9作為葉結點的權，構造一棵哈夫曼樹(要求每個結點的左子樹根結點的權小于等于右子樹根結點的權),給出相應權重值葉結點的哈夫曼編碼。(2)一棵哈夫曼樹有n個葉結點，它一共有述理由?3.(1)畫出對長度為10的有序表進行折半查找的判定樹(以序號1,2,……10表示樹結點)(2)對上述序列進行折半查找，求等概率條件下，成功查4.一組記錄的關鍵字序列為(46,79,56,38,40,84)(1)利用快速排序的方法，給出以第一個記錄為基準得到的一次劃分結果(給出逐次交換元素的過程，要求以升序排列)(2)對上述序列用堆排序的方法建立大根堆，要求以二叉5.(1)利用篩選法，把序列{37,77,62,97,11,27,52,,畫出相應的完全二叉樹(2)寫出對上述堆所對應的二叉樹進行前序遍歷得到的序列6.設查找表為(50,60,75,85,96,98,105,110,120,130)(1)說出進行折半查找成功查找到元素120需要進行多少次元素間的比較?(2)為了折半查找元素95,經過多少次元素間的比較才能確定不能查到?(3)畫出對上述有序表進行折半NODEtemp;{; ;}2以下是用尾插法建立帶頭結點且有n個結點的單向鏈表的程序，結點中的數據域從前向后依次為1,2,3......,n完成程序NODE*create(n){NODE*head,*p,*q;p=(NODE*)malloc(sizeof(NODE));hea;pnext=NULL;/*建立頭結點pnext=NULL;2:11103:111141107:008:019:1046,79,56,38,40,8440,79,56,38,40,856,38,79,8440,38,56,38,7952849631071235679384084)個字節。數之和為(4.串函數StrCat(a,b)的功能是進行串(D.連接5.數據結構中，與所使用的計算機無關的是數據)結構。C.邏輯與物理)個指針域為空。D.n-27.鏈表所具備的特點是(D.可以通過下標對鏈表進行直接訪問8.設一棵哈夫曼樹共有n個非葉結點，則該樹有()個葉結點。D.2n9.線性表只要以(A.鏈接D.二叉樹10.從一個棧頂指針為top的鏈棧中刪除一個D.top=top-next;x=data;11.散列查找的原理是(定的對應關系B.按待查記錄的關鍵字有序的順序方式存儲C.按關鍵字值的比較進行查找D.基于二分查找的方法12.一棵完全二叉樹共有5層，且第5層上有六個結點，該樹共有()個結點。B40,38,46,56,79,84C.40,38,46,84,56,79D.38,40,46,56,79,8429.隊列的插入操作在()進行。C.隊頭或隊尾D.在任意指定位置題二、填空題(每小題2分，共24分)1.一棵二叉樹沒有單分支結點，有6個葉結點，則該樹總2.在二叉樹的鏈式存儲結構中，通常每個結點中設置三個、右指針。3.設一棵完全二叉樹，其最高層上最右邊的葉結點的編號為奇數，該葉節點的雙親結點的編號為10,該完全二叉樹一共4.一棵二叉樹中順序編號為i的結點，若它存在左、右孩__5.按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有6.串的兩種最基本的存儲方式是 o7.數據結構中的數據元素存在一對多的關系稱為結數都為2,則該樹共有個葉結點。10.對于一棵具有n個結點的二叉樹，其相應的鏈式存儲13.如圖4所示的二叉樹，其后序遍歷序列為14.n個元素進行冒泡法排序，通常需要進行趟冒15o_17.圖的深度優先搜索和廣度優先搜索序列不一定是唯一的。18,根據搜索方法的不同，圖的遍歷有 19.對記錄序列排序是指按記錄的某個關鍵字排序，記錄序20.按某關鍵字對記錄序列排序，若關鍵字三、綜合題1.(1)利用篩選過程把序列{42,82,67,102,16,32,57,52}建成堆(小根堆),畫出該堆(不要求中間過程)。(2)寫出對上述堆對應的完全二叉樹進行中序遍歷得到的2.設查找表為(16,15,20,53,64,7),(1),寫出每一趟的排序過程，通常對n個元素進行冒泡排序要進行多少趟冒泡?第j趟要進行多少次元素間的比較?(1)設有查找表{5,14,2,6,18,7,4,1依對取表中數據，構造(2)說明如何由序列的二叉排序樹得到相應序列的排序結4.(1)設有一個整數序列{50,38,16,82,110,13,64},(2)利用上述二叉排序樹，為了查找110,經多少次元素間的比較能成功查到，為了查找15,經多少次元素間的比較可5.(1)對給定權值2,1,3,3,4,5,構造哈夫曼樹。(2)同樣用上述權值構造另一棵哈夫曼樹，使兩棵哈夫曼四、程序填空題1.以下函數為鏈隊列的入隊操作，x為要 ; ; ;2.設線性表為(6,10,16,4),以下程序用說明結構變量的方法建立單向鏈表，并輸出鏈表中各結點中的數據。#defineNULL0{NODEa,b,c,d,*head,*p;a./*以上結束建表過程*/p=head;/*p為工作指針，準備輸出3.以下函數在head為頭指針的具有頭結點的單向鏈表中*next;};typedefNODEintj; 4.以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程期末綜合練習三答案一、單項選擇題1.C二、填空題1.112.值域左指針3.214.2i和2i+15.先序；中序；后序6.順序存儲9.物理(存儲)18.深度優先搜索遍歷廣度優先搜索遍歷19.主關鍵字20.相等三、綜合應用題1.(1)2.(1)原序列16777777圖4(3平均查找長度=(1*1+2*2+3*3)/6=14/6圖6(2中序遍歷中序2,3,4,5,6,7,14,16,1850388213110641671520641653(2)三次；四次1.(1)malloc(sizeof(structnode))(2)p18(1)amp;a(2)dnext=NULL(3)p-data(4)p=p-3.(1)ji-1p4.(1)Postorder(BT-left)(2)Postorder(BT-right)