1、精選優質文檔-傾情為你奉上離線考核數據結構（高起專）滿分100分一、簡答題（每小題8分，共40分。）1什么是有根的有向圖？答：在一個有向圖中，若存在一個頂點V0，從該頂點有路經可以到達圖中其他所有頂點，則稱此有向圖為有根的有向圖，V0稱作圖的根。2 什么是負載因子？答：負載因子(load factor)，也稱為裝填因子，定義為：3 試分析順序存儲結構的優缺點。答：優點： 內存的存儲密度高(d=1)； 可以隨機地存取表中的結點,與i的大小無關。 缺點： 進行插入和刪除結點的運算時，往往會造成大量結點的移動，效率較低； 順序表的存儲空間常采用靜態分配，在程序運行前存儲規模很難預先確定。估計過大將導

2、致空間的浪費，估計小了，隨著結點的不斷插入，所需的存儲空間超出了預先分配的存儲空間，就會發生空間溢出。 4 算法的時間復雜度僅與問題的規模相關嗎？答：算法的時間復雜度不僅與問題的規模相關而且還與數據結構中的數據分布有關。5 舉例說明散列表的平均查找長度不隨表中結點數目的增加而增加，而是隨著負載因子的增大而增大。答：與其他基于比較的查找方法(如順序查找、折半查找等)相比，這是散列法的基本特征，它是一種與負載因子有關的查找方法。例如，當m = 100, n = 50時與當m = 10000, n = 5000時， = n/m = 0.5,即兩者的平均查找長度相同。由于平均查找長度ASL()是關于負

3、載因子的遞增函數，顯然平均查找長度隨負載因子的增大而增大。二、圖示題（每小題15分，共30分。）1設待排序文件的初始排序碼序列為 32, 38, 10, 53, 80, 69, 32, 05 ，寫出采用冒泡排序算法排序時，每趟結束時的狀態。答：冒泡排序算法排序時，每趟結束時的狀態如下：2 設有關鍵字集合為 16,05,28,10,09,17 ，散列表的長度為8，用除留余數法構造散列函數，用線性探查法解決沖突，并按關鍵字在集合中的順序插入，請畫出此散列(哈希)表，并求出在等概率情況下查找成功的平均查找長度。答：三、算法題（每小題15分，共30分。）1. 二叉樹以二叉鏈表(lchild-rchil

4、d表示法)作為存儲結構，試編寫計算二叉樹中葉結點個數的算法(要求寫出存儲結構的描述)，并分析算法的時間復雜度。答：存儲結構描述如下：const int MaxSize =100;typedef char datatype;typedef struct node datatype data; struct node *lchild, *rchild; BTnode, *BinTree;BinTree root;BTnode* p;int num; / 統計二叉樹中葉結點個數的變量進入算法時，指針root指向根結點 算法結束時，二叉樹中分支結點個數保存在變量num中。（說明：下面的算法和C/C+

5、程序只要給出其中一種形式即可。）/ 調用為InOrderCount (root, num)，mun的初值為0。算法 計算二叉樹中葉結點個數 C/C+ 程序： InOrderCount (p, num) InOrderCount (BinTree p, int &num) 1. 若pNULL if ( p!=NULL) 則 InOrderCount (p->lchild) InOrderCount (p->lchild); 若p->lchild = NULL 且 if (p->lchild = = NULL &&p->rchild = NUL

6、L p->rchild = = NULL)則 num num+1 num+; InOrderCount (p->rchild) InOrderCount (p->rchild); 2. 算法結束 設二叉樹中有n個結點，因為是遍歷運算，故此算法的時間復雜度為：O(n)。3 編寫一個求單循環鏈表中結點個數的算法，并分析算法的時間復雜度(要求寫出存儲結構的描述)。答：型與變量說明及算法如下：typedef int datatype; / 結點的數據域的類型為整型typedef struct node / 結點類型定義 datatype data; / 結點的數據域 struct n

7、ode *next; / 結點的指針域 ListNode, *LinkList;ListNode *p; LinkList rear;int n;（說明：下面的算法和C/C+ 程序只要給出其中一種形式即可。）算法 求單循環鏈表中結點個數 int LinkedListCount (LinkList rear)LinkedListCount (rear ) ListNode *p; 若 rear = NULL int n = 0;則 n 0; return n if (rear = = NULL) return n; p rear; n 1 p = rear; n = 1; 循環 當 p->next rear 時，執行 while (p->