1、最新國家開放大學電大本科 數據結構 期末題庫及答案考試說明： 本人針對該科精心匯總了歷年題庫及答案，形成一個完整的題庫，并且每年都在更新。該題庫對考生的復習、作業和考試起著非常重要的作用，會給您節省大量的時間。做考題時，利用本文檔中的查 TOC o 1-5 h z 找工具，把考題中的關鍵字輸到查找工具的查找內容框內，就可迅速查找到該題答案。本文庫還有其他網核 及 教學考一體化答案 ，敬請查看。數據結構題庫及答案一( 每小題 2 分。共 l8 分)下面程序段的時間復雜度為 ( )。for(int i=0； im ； i+)for(int j=0； jlink=S ；s link=top link

2、 ; top link=S ;C S-link=top； top S；D . s link=top ; top top - link ;一棵具有35 個結點的完全二叉樹的高度為 ( ) 。假定空樹的高度為一l 。A 5 B 6C7 D8向具有 n 個結點的堆中插入一個新元素的時間復雜度為 ( )。A O(1) B 0(n)C O(log 2n)D O(nlog 2n).在一棵AVL樹中，每個結點的平衡因子的取值范圍是()。A. l 1 B . 22C . 12 D. O1一個有 n 個頂點和 n 條邊的無向圖一定是( ) 的。A.連通 B .不連通C 無回路D 有回路( 每小題 2 分，共 l

3、4 分)1 數據結構包括() 、存儲結構和對數據的運算這三個方面。一維數組所占用的空間是連續的。但數組元素不一定順序存取，通常是按元素的() 存取的。將一個n 階對稱矩陣的上三角部分或下三角部分壓縮存放于一個一維數組中，則該一維數組需要至少具有() 個元素。對于一棵具有n 個結點的樹，該樹中所有結點的度數之和為 () 。在一棵高度為 3 的理想平衡二叉樹中，最少含有() 個結點，假定樹根結點的高度為 0 。假定對長度n=50 的有序表進行折半搜索，則對應的判定樹中最底層的結點數為 () 個。用鄰接矩陣存儲圖，占用的存儲空間與圖中的 () 數有關。三、判斷題。在每小題前面打對號表示正確或打叉號表

4、示錯誤(每小題 2 分。共 14 分)()1算法和程序都應具有下面一些特征：有輸入，有輸出，確定性，有窮性，有效性。( )2 用字符數組存儲長度為 n 的字符串，數組長度至少為 n+1。()3在用循環單鏈表表示的鏈式隊列中，可以不設隊頭指針，僅在鏈尾設置隊尾指針。( )4 鄰接矩陣適用于稀疏圖的表示，鄰接表適用于稠密圖的表示。( )5 對一個無向連通圖進行一次深度優先搜索遍歷時可以訪問到圖中的所有頂點。 ( )6 在索引順序結構的搜索中，對索引表只可以采取順序搜索，不可以采用折半搜索。 ( )7 圖中各個頂點的編 號是人為的，不是它本身固有的，因此可以根據需要進行改變。四、運算題 ( 每小題

5、6 分，共 30 分)1 假定一棵二叉樹廣義表表示為 a(b(c) ， d(e ， f) ，分別寫出對它進行中序、后序、按層遍歷的結果。中序：后序：按層:如有你有幫助，請購買下載，謝謝！ 2 . 一個一維數組 all2中存儲著有序表(15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 80, 86),根據折半搜索所對應的判定樹，寫出該判定樹中度為1的結點個數，并求出在等概率情況下進行成功搜索時的平均搜索長度。度為l的結點個數：平均搜索長度：.假定一個線性序列為(38, 42, 55, 15, 23, 44, 30, 74, 48, 26),根據此線性序列中元素的排

6、列次序生成一棵二叉搜索樹，求出該二叉搜索樹中左子樹為空的所有單支結點、右子樹為空的所有單支結 點和所有葉子結點，請按照結點值從小到大的次序寫出。左子樹為空的所有單支結點： 右子樹為空的所有單支結點： 所有葉子結點：.已知一個圖的頂點集V和邊集G分別為：V=1 , 2, 3, 4, 5, 6;E=, , , , , , , , ;假定該圖采用鄰接表表示，每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次 序鏈接的，試寫出：(1)從頂點l出發進行深度優先搜索所得到的頂點序列；(2)9,N點1出發進行廣度優先搜索所得到的頂點序列。(1):(2)5.已知一個數據序列為16, 45, 27, 23,

7、41 , 15, 56, 64,請把它調整為一個最大堆。最大堆： 五、算法分析題(每小題6分。共12分)下面算法的功能為：將兩個有序單鏈表合并成一個有序單鏈表并返回其表頭指針。閱 讀算法，在劃有橫線的上面填寫合適的內容。ListNode*Mergel(ListNode* . & pl , ListNode*&p2) ListNode*p=new ListNode , *f=p ;while(p1!=NULL & p2!=NULL) if(pl-datadata) p-link=pl ； ;elsep-link=p2 ; p2=p2 一link ; )if(pl!=NULL)p-link=pl

8、; else p 1ink=p2 ;pl=p2=NULL;return f 一 link :2 已知二叉樹中的結點類型BinTreeNode 定義為：struct BinTreeNodeElemType data ； BinTreeNode*left ， *right ； ；其中 data 為結點值域， left 和 right 分別為指向左、右子女結點的指針域。根據下面算法的定義指出其功能。算法中參數BT 指向一棵二叉樹。BinTreeNode*BTreeSwopX(BinTreeNode*BT)if(BT= =NULL)return NULL ；elseBinTreeNode*pt=new

9、 BinTreeNode ；pt -dataBT-data ;pt right BTreeSwopX(BTleft);pt 一 left=BTreeSwopX(BT-right)；return pt ；算法功能：六、算法設計題 ( 每小題 6 分，共 12 分)已知 f 為單鏈表的表頭指針，單鏈表中的結點結構為 (data ， link) ，并假定每個結點的值均為大于 0 的整數。根據下面函數聲明寫出遞歸算法，返回單鏈表中所有結點的最大值，若單鏈表為空則返回數值 0。int Max(LinkNode*f) ；設Q 是一個由其隊尾指針和隊列長度標識的循環隊列，按照下面隊列定義和函數聲明寫出從此隊

10、列中刪除一個元素的算法。循環隊列定義struct CyclicQueueElemType elemEM ;/ M為已定義過的整型常量int rear ； rear 指向隊尾元素的后一個位置int length ： length 指示隊列中元素個數5若隊列非空則刪除隊頭元素并由引用參數 x 帶回， 同時返回 true ； 否則若隊列為空則返回 false5頁ElemType&x)；bool DelCQueue(CyclicQueue Q試題答案及評分標準一、單項選擇題，翟括號內填寫所選擇的標號（ 每小題 2 分，共 18 分）1 C 2 C 3 B 4 B 5 C6 A 7 C 8 A 9 b二

11、、填空題。在橫線處填寫合適內容（ 每小題 2 分，共 14 分）1 邏輯結構 2 下標 （或順序號 ） 3 n（n+1） 2 4 n 一 1 5 8 6 19 7 頂點三、判斷題，在每小題前面打對號表示正確或打叉號表示錯誤（ 毒小題 2 分。共 14 分 ）1 錯2 對 3 對 4 錯5 對6錯 7 對 7 對四、運算題 （ 每小題 6 分，共 30 分 ）中序：C， b， a， e ， d， f后序：C，b，e，f ，d ，a按層：a ，b，d，C，e ，f度為1 的結點個數： 5平均搜索長度： 37/12左子樹為空的所有單支結點：l5 ， 23， 42， 44右子樹為空的所有單支結點： 3

12、0所有葉子結點： 26， 48 ， 74 （I）1 ，2，4，5， 3，6 3分（2）1 ， 2 ，3 ，4，5， 63 分最大堆： 64 ， 45， 56， 23， 41， 15， 27， 16五、算法分析題 （ 每小題 6 分。共 12 分）. pl2p1 link、p=p link /每空 3 分生成一棵新二叉樹并返回樹根指針，該二叉樹是已知二叉樹BT 中所有結點的左、右子樹 （ 或左、右孩子的值） 交換的結果。六、算法設計題 （ 每小題 6 分。共 12 分）評分標準：按注釋酌情給分。int Max（LinkNode*f）if（f= =NULL）return 0：if（f 一 link

13、= =NULL）return f 一 data ；int temp=Max(f-link)；if(f 一 datatemp)return f 一 data ；else return temp ；2評分標準：按注釋酌情給分：bool DelCQueue(CyelieQueue Q ， ElemType&x)if(Q 1ength= =O)return false ；x Q elem(Q rear Q 1ength-t-M) M；Q 1ength 一 一；return true ；數據結構題庫及答案二一、單項選擇題 ( 每小題 2 分。共 30 分)鏈表所具備的特點是( ) 。A 可以隨機訪問任一

14、結點B 占用連續的存儲空間C 插入刪除元素的操作不需要移動元素結點D 可以通過下標對鏈表進行直接訪問線性結構中數據元素的位置之間存在( ) 的關系。A 一對一B 一對多C 多對多D 。每一個元素都有一個直接前驅和一個直接后繼算法的時間復雜度與( ) 有關。 7A 所使用的計算機B 與計算機的操作系統C 與算法本身 D 與數據結構在一個單鏈表中，p、 q 分別指向表中兩個相鄰的結點，且q 所指結點是P 所指結點的直接后繼，現要刪除 q 所指結點，可用的語句是( ) 。A p=q-next B p-next=qC p-next=q-next D q-next=NULL TOC o 1-5 h z

15、在一個鏈隊中，假設f 和 r 分別為隊頭和隊尾指針，則刪除一個結點的運算為 ( )。A r=f-next ：Br=r-next ：Cf=f 一 next；Df=r 一 next：元素 3 ， 6 ， 9 按順序依次進棧，則該棧的不可能輸出序列是( )( 進棧出棧可以交替進行) 。A9，6 ，3B9，3 ，6C6，3 ，9D3，9 ，6.設有一個10階的對稱矩陣A,采用壓縮存儲的方式，將其下三角部分以行序為主存儲到一維數組中(數組下標從1 開始 ) ，則矩陣中元素氏， 。在一維數組B 中的下標是( ) 。A33B32C85D41在 C 語言中，順序存儲長度為 3 的字符串，需要占用 ( ) 個字

16、節。A4 B3C6 D12一棵有 n 個結點采用鏈式存儲的二叉樹中，共有( ) 個指針域為空。A n+1 B nC n 一 1 D n-2設一棵哈夫曼樹共有n 個葉結點，則該樹有( ) 個非葉結點。A n 1 B nC n+1 D 2n在一個無向圖中，所有頂點的度數之和等于邊數的 ( ) 倍。A 3 B 2 5C 1 5 D 2.已知如圖1所示的一個圖，若從頂點V。出發，按廣度優先進行遍歷，則可能得到的一種頂點序列為 ( ) 。在有序表2 ， 4， 7， 14， 34， 43， 47， 64， 75， 80， 90， 97， 120) 中，用折半查找法查找值80時，經 ( ) 次比較后查找成功

17、。 TOC o 1-5 h z A4B2C3D5排序算法中，從未排序序列中依次取出元素與已排序序列 （ 初始為空 ） 中的元素進行比較（ 要求比較次數盡量少） ，然后將其放入已排序序列的正確位置的方法是（ ）。A 冒泡B 直接插入C 折半插人D 選擇排序 排序方法中， 從尚未排序序列中挑選元素， 并將其依次放入已排序序列 （ 初始為空 ） 的一端的方法，稱為 （ ） 排序。A 歸并 B 插入C 快速 D 選擇二、填空題 （ 每小題 2 分。共 24 分 ）-結構中的數據元素存在多對多的關系稱為一一結構。. 要求在 n 個數據元素中找其中值最大的元素，設基本操作為元素間的比較。則比較的次數和算法

18、的時間復雜度分別為 和設有一個頭指針為head的單向循環鏈表，p指向鏈表中的結點，若pnext=,則P所指結點為尾結點。向一個棧頂指針為h的鏈棧中插入一個 s所指結點時，可執行snext=h;和在一個鏈隊中，設 f和r分別為隊頭和隊尾指針，則插入s所指結點的操作為-和 r=s ； （結點的指針域為next）.設有n階對稱矩陣A,用數組s進行壓縮存儲，當inext=NULL；head=(1) ；2) ；for(i=1 ； idata=i ；p-next=NULL ；elsep-next2(4)；q 一 next2(5) ；return(head) ；2 以下程序是后序遍歷二叉樹的遞歸算法的程序，

19、完成程序中空格部分( 樹結構中，左、右指針域分別為 left 和 right ，數據域 data 為字符型； BT 指向根結點 ) 。void Postorder(struct BTreeNode*BT)if(BT!=NULL) TOC o 1-5 h z ； ； ；試題答案及評分標準 一、單項選擇題 ( 每小題 2 分，共 30 分)1C 2A 3 C 4C 5 C6 B 7 A 8 A 9 A l0 A11 D l2 C l3 A l4 C l5 D TOC o 1-5 h z 二、填空題 ( 每小題 2 分。共 24 分)- 圖狀 ( 網狀 ). n 1, 0(n)headH=s； r

20、一 next=S ；.i(i 1)/2+j2i 和2i+1n中序 abdefeg不正確關鍵字相等的記錄三、綜合題 ( 每小題 10 分。共 30 分)1 (1) 初始序列 46， 79， 56， 38， 40， 84 TOC o 1-5 h z 40，79，56，38，回，8440 ，回， 56,38 ， 79， 8440，38，56，圍，79，8440，38，回，56，79，8440，38，46，56，79，84，(2)2 (1) 原序列 16 15 20 53 64 715 16 20 53 7 64 n一 1 耥15 16 20 7 53 64 n j 次15 16 7 20 53 64

21、7 15 16 20 53 64平均查找長度一(1*1+2*2+3*3) 6 1463 (1) 不正確，二叉排序樹要求其子樹也是二又排序樹。(2)后續遍歷 5， 6， 4， 9， 8， 18， 20， 16， 7四、程序填空題 ( 每空 2 分。共 16 分) (1)P(2)q=P(3)(NODE*)malloc(sizeof(NODE)(4)q-next(5)p (1)Postorder(BT 一 left)(2)Postorder(BT 一 right)(3)printf(c”，BTdata)數據結構題庫及答案三一、單項選擇題。在括號內填寫所選擇的標號( 每小題 2 分。共 18 分)若需

22、要利用形參直接訪問實參，則應把形參變量說明為 ( ) 參數。A.指針B.引用C 傳值D 常值在二維數組中，每個數組元素同時處于( ) 個向量中。A O B 1C 2 D n.已知單鏈表A長度為m,單鏈表8長度為n,它們分別由表頭指針所指向，若將B整體連接到A的 TOC o 1-5 h z 末尾，其時間復雜度應為 ( )。AO(1)BO(m)C.O(n)D.O(m十n)假定一個鏈式隊列的隊頭和隊尾指針分別為 front 和 rear ，則判斷隊空的條件為 ( ) A iront= =rear B front!=NULLC rear! = NULLD front= =NULL若讓元素l ， 2 ，

23、 3 依次進棧，則出棧次序不可能出現( ) 種情況。 TOC o 1-5 h z A3，2，1B2，1，3C3，1 ，2D1，3，2在一棵高度為 5( 假定樹根結點的高度為 0) 的完全二叉樹中，所含結點個數至少等于A 16B 64C 31D 32向具有 n 個結點的二叉搜索樹中插入一個結點的時間復雜度大致為 ( )A O(1) B O(1og2n)C O(n)D O(nlog 2n)8 具有 n 個頂點的有向圖最多可包含有( ) 條有向邊。A n 1B nC n(n 一 1) 2 D n(n 一 1)9 圖的廣度優先搜索類似于樹的( ) 遍歷。A.先根B.中根C.后根D.層次二、填空題。在橫

24、線處填寫合適的內容( 每小題 2 分，共 14 分)鏈表只適用于() 查找。設雙向循環鏈表中每個結點的結構為 (data ， llink ， rlink) ，則結點 *P 的前驅結點的地址為()。在一個鏈式隊列中，若隊頭指針與隊尾指針的值相同，則表示該隊列至多有() 個結點。假定一棵樹的廣義表表示為a(b ， c ， d(e ， f) ， g(h) ，則結點 f 的層數為 () 。假定樹根結點的層數為 0。從一棵二叉搜索樹中搜索一個元素時，若給定值大于根結點的值，則需要向根的( ) 繼續搜索。每次從第i 至第 n 個元素中順序挑選出一個最小元素，把它交換到第 i 個位置，此種排序方法叫做 ()

25、 排序。快速排序在最壞情況下的時間復雜度為()。三、判斷題，在每小題前面打對號表示正確或打叉號表示錯誤(每小題 2 分。共 14 分)()1數據的邏輯結構與數據元素本身的內容和形式無關。()2使用三元組表示稀疏矩陣中的非零元素能節省存儲空間。( )3 在一棵二叉樹中，假定每個結點只有左子女，沒有右子女，則對它分別進行前序遍歷和按層遍歷時具有相同的結果。( )4能夠在鏈接存儲的有序表上進行折半搜索，其時間復雜度與在順序存儲的有序表上相同。( )5鄰接表表示只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用。( )6 在索引順序結構上實施分塊搜索，在等概率情況下，其平均搜索長度不僅與子表

26、個數有關，而且與每一個子表中的對象個數有關。( )7 向一棵 8樹插入關鍵碼的過程中，若最終引起樹根結點的分裂，則新樹比原樹的高度減少 1。四、運算題 ( 每小題 6 分。共 30 分 )假定一棵二叉樹廣義表表示為 a(b(c( ， g) ， d(e ， f) ，分別寫出對它進行先序、中序和后序遍歷的結果。先序：中序：后序：有 7 個帶權結點，其權值分別為3， 7， 8， 2， 6， 10， 14，試以它們為葉子結點生成一棵霍夫曼樹，求出該樹的帶權路徑長度。帶權路徑長度：已知圖 G=(V， E) ，其中V=a ， b， c， d， e ，E=， ， ， ， ， ， 在該圖的鄰接表表示中，每個頂

27、點單鏈表各有多少個邊結點。頂點： a b c d e邊結點數：.已知一個AOV網的頂點集V和邊集G分別為：V=0， 1 ， 2， 3， 4， 5， 6， 7 ；E=， ， ， ， ， ， ， ， ；若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序鏈接的，則按主教材中介紹的進行拓撲排序的算法，寫出得到的拓撲序列。拓撲序列：5 已知有一個數據表為 30 ， 16， 20， 15， 38， 12， 44， 53， 46， 18， 26， 86 ，給出進行歸并排序16頁的過程中每一趟排序后的數據表變化。(o)30 16 20 15 38 12 44 53 46 18 26

28、 86(2)五、算法分析題(每小題6分。共12分).該算法功能為：從表頭指針為la的、按值從小到大排列的有序鏈表中刪除所有值相同的多余元素,并釋放被刪結點的動態存儲空間。閱讀算法，在劃有橫線的上面填寫合適的內容。void purge_linkst(ListNode * &la)ListNode * P , *q ;if(1a= =NULL)return ;q=1a; p=la -link;while(p)if(p -dataq -data)q=p ; p=p -link ; elseq -link ;delete(p);p= ；.已知二叉樹中的結點類型BinTreeNode定義為：struct

29、 BinTreeNodeElemType data ; BinTreeNode*left , *right ; ;其中data為結點值域，left和right分別為指向左、布子女結點的指針域。下面函數的功能是從二 叉樹BT中查找值為X的結點，若查找成功則返回結點地址，否則返回空。閱讀算法，在劃有橫線的上面 填寫合適的內容。BinTreeNode*BTF(BinTreeNode*BT , ElemType x)if(BT=NULL)NULL ;elseif(BT - data= =x) ; elseBinTreeNode*t ;if(t BTF(BT left , x)return tif(t=

30、 )return t;return NULL ; 六、算法設計題(每小題6分，共12分) 1. Q是一個由其隊尾指針和隊列長度標識的循環隊列，請寫出插入一個元素的算法。 struct CyelieQueue/循環隊列定義ElemType elemM ; / M為已定義過的整型常量int rear ;/rear指向隊尾元素的后一個位置int length ;/length指示隊列中元素個數；bool EnCQueue(CyclicQueue& Q , ElemType x);/Q是一個循環隊列，若隊列不滿，則將x插入并返回true ；否則返回false。/在下面寫出該函數的函數體2.已知二叉搜索

31、樹中的結點類型BinTreeNode定義為：struct BinTreeNodeElemType data; BinTreeNode*left, *right;)其中data為結點值域，left和right分別為指向左、右子女結點的指針域。參數BST指向一棵二叉搜索樹的根結點。試根據下面的函數聲明編寫一個遞歸算法，向BST樹中插入值為item的結點，要求若樹中不存在item結點則進行插入并返回l表示插入成功，若樹中已存在item結點則不插入并返回。表示插入失敗。int Insert(BinTreeNode*&BST , const ElemType&item);試題答案及評分標準一、單項選擇題

32、。在括號內填寫所選擇的標號(每小題2分。共18分). B 2.C 3.B 4.D 5.C6. D 7.B 8.D 9.D18頁二、填空題。在橫線處填寫合適內容( 每小題 2 分。共 14 分)1 順序 2 p-llink 3 1 4 2 5 右子樹6 直接選擇7 0(n 2)三、判斷題，在每小題前面打對號表示正確或打叉號表示錯誤( 每小題 2 分共 14 分 )1 對2對3對4錯5 錯 6 對 7 錯四、運算題 ( 每小題 6 分共 30 分 ) TOC o 1-5 h z 1 先序：a， b， c ， g，d，e， f2 分中序：c ，g ，b，a，e，d，f2 分后序：g，c，b，e，f，

33、d，a2 分2帶權路徑長度：l31評分標準：每個數據對給l 分，全對給6 分。頂點： a b cd e邊結點數： 11 21 2評分標準：若與答案完全相同得6 分，若仍為一種拓撲序列則得3 分，其他則酌情處理。其他則酌情處理。拓撲序列： 1 ， 3 ， 6， 0， 2 ， 5 ， 4， 75分步給分(0)30 16 20 15 38 12 44 53 46 18 26 86(1)16 3015 2012 3844 5318 4626 86 /l分(2)15 16 20 3012 38 44 5318 26 46 86 l 分(3)-r-1112 分(4)12 15 16 18 20 26 30

34、 38 44 46 53 86 /2分五、算法分析題【每小題 6 分。共 12 分 ) p -link 、 q -link. return BT、BTF(BT right , x)六、算法設計題 ( 每小題 6 分。共 12 分)評分標準：根據編程完整程度酌情給分。 bool EnCQueue(CyclicQueue&Q ， ElemType x) ；if(Q.1ength= =M)return false ； 1 分Q elemQ rear=x ； 2 分Q rear=(Q rear+1)%M ；/14 分Q 1ength+ ； 5 分return true ； 6 分 int Insert

35、(BinTreeNode*&BST ， const ElemType&item)if(BST= =NULL)BinTreeNode*p=new BinTreeNode ；p 一 data=item ；p 一 left=p 一 right=NULL ；BST=P：return l ；else if(item= =BST 一 data)return 0；else if(itemdata)return Insert(BST 一 left ， itern) ；elsereturn Insert(BST-right， item) ；說明：函數體中的三個else 保留字均可以被省略。數據結構題庫及答案四

36、TOC o 1-5 h z 一、單項選擇題(每小題 2 分，共30 分)同一種邏輯結構( ) 。A. 只能有唯一的存儲結構B 可以有不同的存儲結構C 只能表示某一種數據元素之間的關系 n 以上三種說法均不正確鏈表所具備的特點是( ) 。A 可以隨機訪問任一結點B 占用連續的存儲空間C 插入刪除元素的操作不需要移動元素結點D 可以通過下標對鏈表進行直接訪問數據的物理結構( ) 。A與數據的邏輯結構無關B僅僅包括數據元素的表示C只包括數據元素間關系的表示n 包括數據元素的表示和關系的表示.線性結構中數據元素的位置之間存在（）的關系。A-對一B 一對多C多對多D.每一個元素都有一個直接前驅和一個直接

37、后繼.設有一個10階的對稱矩陣A,采用壓縮存儲的方式，將其下三角部分以行序為主存儲到一維數組B中（數組下標從1開始），則矩陣中元素氏，。在一維數組B中的下標是.（）。A . 33 B . 32C . 85 D . 41 TOC o 1-5 h z .在一個無向圖中，所有頂點的度數之和等于邊數的（）倍。A3 & 2.5C 1.5 D . 2二、填空題（每小題 2分，共24分）. 棧和隊列的操作特點分別是 和 一。.結構中的數據元素存在多對多的關系稱為- 結構。.根據數據元素間關系的不同特性，通常可分為集合、線性、四類基本結構。.要求在n個數據元素中找其中值最大的元素，設基本操作為元素間的比較。則

38、比較的 次數和算法的時間復雜度分別為 和 一。.在一個單向鏈表中p所指結點之后插入一個s所指向的結點時，應執行 和= 的操作。.在二叉樹的鏈式存儲結構中，通常每個結點中設置三個域，它們是值域、-。.-棵二叉樹中順序編號為 i的結點，若它存在左、右孩子，則左右孩子的編號分別為.向一個棧頂指針為h的鏈棧中插入一個s所指結點時，可執行-;和。.在一個鏈隊中，設f和r分別為隊頭和隊尾指針，則插入 s所指結點白操作為-和r=s；（結點的指針域為next）。.設有一棵深度為4的完全二叉樹，第四層上有5個結點，該樹共有 個結點。（根所在結點為第. 對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應的三元組包括該

39、元素的 、 和非零元素值三項信息。. 在對一組記錄 （55 ， 39， 97， 22， 16， 73， 65， 47， 88） 進行直接插入排序時，當把第7 個記錄 65插入到有序表時，為尋找插入位置需比較一次。三、綜合題（每小題 10 分，共 30 分） （1） 以 2 ， 3， 4， 7， 8 ， 9 作為葉結點的權，構造一棵哈夫曼樹（要求每個結點的左子樹根結點的權小于等于右子樹根結點的權） ，給出相應權重值葉結點的哈夫曼編碼。（2）- 棵哈夫曼樹有n 個葉結點，它一共有多少個結點？簡述理由。一組記錄的關鍵字序列為 （46 ， 79， 56 ， 38， 40， 84）利用快速排序的方法，給

40、出以第一個記錄為基準得到的一次劃分結果（給出逐次交換元素的過程，要求以升序排列） 。對上述序列用堆排序的方法建立大根堆，要求以二叉樹逐次描述建堆過程。30 設查找表為 （50 ， 60， 75， 85， 96， 98， 105， 110， 120， 130）說出進行折半查找成功查找到元素120 需要進行多少次元素間的比較？為了折半查找元素95，經過多少次元素間的比較才能確定不能查到？畫出對上述有序表進行折半查找所對應的判定樹（要求以數據元素作為樹結點） 。四、程序填空題（每空2 分，共 16 分）試題答案及評分標準一、單項選擇題（每小題 2 分，共 30 分） TOC o 1-5 h z 1B

41、2 C 3D4 A5 D6C7 B 8C9 A10 C11 A 12B13C14A15 D二、填空題（每題 2 分其 24 分】數據結構題庫及答案五一、單項選擇題（每小題 2 分，共 30 分）在 C 語言中，順序存儲長度為 3 的字符串，需要占用 （ ） 個字節。 TOC o 1-5 h z A4B3C 6D12。串函數 StrCat（a ， b） 的功能是進行串 （ ）。A比較B復制C 。賦值 D 連接 - 棵有 n 個結點采用鏈式存儲的二叉樹中，共有( ) 個指針域為空。 TOC o 1-5 h z An+lBnCn-lDn-2設一棵哈夫曼樹共有n 個非葉結點，則該樹有( ) 個葉結點。

42、A n B n+lC n-l D 2n從一個棧頂指針為 top 的鏈棧中刪除一個結點時，用變量x 保存被刪結點的值，則執行( )A. x=top-data;top=top-next B.x=top-dataC. top= top-next; x=top-data D.top=top-next;x=data一棵完全二叉樹共有5 層，且第 5 層上有六個結點，該樹共有( ) 個結點。A30B20C21D23在一個無向圖中，所有頂點的度數之和等于邊數的 ( ) 倍。A.。上；B . 3C 1.5 D 2.已知如圖1所示的一個圖，若從頂點V,出發，按深度優先搜索法進行遍歷，則可能得到的一種頂點序列為(

43、 )。已知如圖2 所示的一個圖，若從頂點 a 出發，按廣度優先搜索法進行遍歷，則可能得到的一種頂點序列為( )。abcedfabcefdaebcfdacfdeb對二叉排序樹進行( ) 遍歷，可以使遍歷所得到的序列是有序序列。A 按層次B 后序C 中序 D 前序80在有序表(2 ， 4， 7， 14， 34， 43， 47 ， 64， 75， 80， 90， 97， 120) 中，用折半查找法查找值時，經 ( ) 次比較后查找成功。A 4 B 2aC3 D5有一個長度為 9 的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數為 ( ) 。A 25/10 B 25/9C 20

44、/9 D 17/9排序算法中，從未排序序列中依次取出元素與已排序序殂（初始為空）中的元素進行比較（要求比較次數盡量少） ，然后將其放入已排序序列的正確位置的方法是（ ）。A 冒泡B 。直接插入C 折半插入D 選擇排序一組記錄的關鍵字序列為 （46 ， 79， 56 ， 38， 40， 84） ，利用快速排序，以第一個關鍵字為分割元素，經過一次劃分后結果為 （ ）。A40,38946,79956,84B40,38946,56,79,84C40， 38,46,84,56,79D38， 40,46956,79,84排序方法中，從尚未排序序列中挑選元素，并將其依次放人已排序序列（初始為空）的一端的方法

45、，稱為 （ ） 排序。A 歸并B 插入C 快速D 選擇二、填空題（每小題 2 分。共 24 分）在二叉樹的鏈式存儲結構中，通常每個結點中設置三個域，它們是 、 、右指針。- 棵二叉樹中順序編號為 i 的結點，若它存在左、右孩子，則左、右孩子編號分別為串的兩種最基本的存儲方式是一 和 一。- 棵有 2n-l 個結點的二叉樹，其每一個非葉結點的度數都為2 ，則該樹共有個葉結點。對于一棵具有n 個結點的二叉樹，其相應的鏈式存儲結構中共有個指針域為空。 遍歷二叉排序樹可得到一個有序序列。22如圖3所示的二叉樹，其后序遍歷序列為%圖323 如圖 4所示的二叉樹，其先序遍歷序列為妒圖4圖的深度優先搜索和廣

46、度優先搜索序列不一定是唯一的。 此斷言是一的。 (回答正確或不正確)二叉樹為二叉排序的充分必要條件是其任一結點的值均大于其左孩子的值、小于其右孩子的值。這種說法是的。 (回答正確或不正確)對記錄序列排序是指按記錄的某個關鍵字排序，記錄序列按 排序結果是唯一的。按某關鍵字對記錄序列排序，若在排序前和排序后仍保持它們的前后關系，則排序算法是穩定的，否則是不穩定的。三、綜合題(每小題 10 分。共 30 分)設查找表為 (16 ， 15， 20， 53， 64， 7) ，用冒泡法對該表進行排序(要求升序排列) ，寫出每一趟的排序過程，通常對n 個元素進行冒泡排序要進行多少趟冒泡？第 j 趟要進行多少

47、次元素間的比較？在排序后的有序表的基礎上，畫出對其進行折半查找所對應的判定樹。 (要求以數據元素作為樹結點) 。29 (1) 設有查找表5 ， 14， 2， 6， 18， 7， 4， 16 ， 3) ，依次取表中數據，構造一棵二叉排序樹。說明如何由序列的二叉排序樹得到相應序列的排序結果。30 (1) 對給定權值2 ， 1， 3， 3 ， 4， 5，構造哈夫曼樹(要求每個結點的左子樹根結點的權小于等于右子樹根結點的權) 。給出各權值的哈夫曼編碼。四、程序填空題【每空2 分。共 16 分)以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分(樹結構中，左、右指針域分別為 1eft 和 ri

48、ght ，數據域 data 為字符型， BT 指向根結點) 。voidPostorder( structBTreeNode* BT)if(BT! =NULL)試題答案及評分標準一、單項選擇題(每小題 2 分，共 30 分)1 A 2 D 3 A 4 B5.A6 C 7 D 8 A 9 B10.C11 B 12 B 13 C 14 B15.D二、填空題(每題 2 分，共 24 分)值域 左指針 右指針2i 2i+l順序存儲 鏈式存儲/ , 一。 nr磷 n+1-中序 gdbeihfca。掣 3 abdefcg正確不正確主關鍵字關鍵字相等的記錄數據結構題庫及答案六一、單項選擇題(每小題 2 分，共

49、 30 分)在數據結構和算法中，與所使用的計算機有關的是( )。A 數據元數間的抽象關系 B 數據的存儲結構C 算法的時間復雜度D 數據的邏輯結構對順序表，以下敘述中正確的是( ) 。A 用一組地址連續的存儲單元依次存放線性表的數據元素B 各個數據元素的首地址是連續的C 數據元素不能隨機訪問D 插入操作不需要移動元素設有一個長度為 25 的順序表，要刪除第10 個元素(下標從1 開始) ，需移動元素的個數為 ( ) 。A 9 B 10C 15 D 16.設單向鏈表中，指針 p指向結點A,若要刪除A的直接后繼，則所需修改指針的操作為 TOC o 1-5 h z ( )。13. 已知如圖 1 所示

50、的一個圖，若從頂點 a 出發，按深度優先搜索法進行遍歷，則可能得到的一種頂點序列為() 。abedfc BacfebdC aebcfdDaedfbc14 一組記錄的關鍵字序列為 (46,20,30,79,56,38,40,84,90il10) ，利用快速排序，以第一個關鍵字為分割元素，經過一次劃分后結果為 ( )。A. 20,30,40,38,46,79,56,84,90 ,10040,20,30,38,46,56,79,84,90 ,11030,20 ,40,38,46,84,56,79,90 ,10020,30 38,40 i46,56 ,79 ,84 ,90 ,10015. 一組記錄的關鍵字序列為(75,63,95