吉林大學《數據結構》2020-2021學年期末試卷

吉林大學2020-2021學年第一學期期末試卷《數據結構》課程試題注意：所有答題一律寫在答題紙上，否則無效。一、填空題(每空3分，共30分)1.數據結構的研究的內容包括：數據的,數據的及數據的。2.當線性表很少做插入刪除操作時，應采用存儲結構為好。3.若哈夫曼樹的葉結點個數為m,則該哈夫曼樹共有個結點。5.對n個元素的表做順序查找時，若查找每個元素的概率相同，則查找成功的平均查找長度為。_6.已知一個圖的鄰接矩陣表示，計算第i個結點的入度的方法是。7.一個圖的生成樹包含圖的全部頂點和圖的條邊。1.算法分析的兩個主要方面是。A.可讀性和文檔性B.空間復雜性和時間復雜性C.正確性和簡明性D.數據復雜性和程序復雜性2.數據的邏輯結構主要類型中不包括。A.集合B.線性結構C.存儲結構D.圖形結構3.數組Q[n]用來表示一個循環(huán)隊列，f為當前隊列頭元素的前一位置，r為隊尾元素的位置，假定隊列中元素的個數小于n,計算隊列中元素的公式為。4.在長度為n的線性順序表中刪除一個元素(元素刪除概率相等)所需移動元素的平均次數為。5.隊列結構的元素個數是。A.不變的B.可變的C.任意的D.06.設有100個元素，用折半查找法進行查找時，最大比較次數是。7.一個隊列的入列序列是1,2,3,4,則隊列的輸出序列是A、4,3,2,1B、1,2,3,4C、 8.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是 9.穩(wěn)定排序是指在排序中，關鍵字相等的不同記錄間的前后相對位置。A.保持不變B.一定相反C.不定10.假設一個有n個頂點和e條弧的有向圖用鄰接表表示，則刪除與某個頂點vi相關的所有弧的時間復雜度是。A.O(n)B.O(e)C.O(n+e)D.O(n*e) 三、問答題(每小題10分，共20分)1.什么是算法?算法分析的目的是什么?算法分析主要涉及哪兩個主要方面的內容?2.一棵有n個結點的滿二叉樹，請計算它的度為0的結點數、它的分枝結點和葉子結點各為多少?。四、圖表計算題(每小題15分，共30分)1.以{13,24,37,90,53,12}構造二叉平衡樹，并進行中序遍歷。2.假定一個待散列存儲的線性表為(32,75,63,48,94,25,36,18,70),散列地址空間為[0,1....,10]1、設數組a是一個有n個結點的完全二叉樹的靜態(tài)存儲結構，算法bintree將a轉換為相應的二叉鏈表存儲結構。試在下劃線處填入適當語句，以完善該算法功能。(20分)New(bt);bt.data=a[1];Q[rear]=bt;/*}2、(共20分，每小題4分)某工程的AOE網如下圖所示，圖中孤上的權值表示所需天數，請求解：(1)事件V?的最早發(fā)生時間Ve(5);(2)事件V?的最遲發(fā)生時間V1(4