數(shù)據(jù)結(jié)構(gòu)高起專

1、離線考核數(shù)據(jù)結(jié)構(gòu)（高起專）滿分100分一、簡答題（每小題8分，共40分。）1什么是有根的有向圖？答：在一個(gè)有向圖中，若存在一個(gè)頂點(diǎn)V0，從該頂點(diǎn)有路經(jīng)可以到達(dá)圖中其他所有頂點(diǎn)，則稱此有向圖為有根的有向圖，V0稱作圖的根。2 什么是負(fù)載因子？答：負(fù)載因子(load factor)，也稱為裝填因子，定義為：3 試分析順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn)。答：優(yōu)點(diǎn)： 內(nèi)存的存儲密度高(d=1)； 可以隨機(jī)地存取表中的結(jié)點(diǎn),與i的大小無關(guān)。 缺點(diǎn)： 進(jìn)行插入和刪除結(jié)點(diǎn)的運(yùn)算時(shí)，往往會造成大量結(jié)點(diǎn)的移動，效率較低； 順序表的存儲空間常采用靜態(tài)分配，在程序運(yùn)行前存儲規(guī)模很難預(yù)先確定。估計(jì)過大將導(dǎo)致空間的浪費(fèi)，估計(jì)小了，隨

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

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

4、編寫計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)的算法(要求寫出存儲結(jié)構(gòu)的描述)，并分析算法的時(shí)間復(fù)雜度。答：存儲結(jié)構(gòu)描述如下：const int MaxSize =100;typedef char datatype;typedef struct node datatype data; struct node *lchild, *rchild; BTnode, *BinTree;BinTree root;BTnode* p;int num; / 統(tǒng)計(jì)二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)的變量進(jìn)入算法時(shí)，指針root指向根結(jié)點(diǎn) 算法結(jié)束時(shí)，二叉樹中分支結(jié)點(diǎn)個(gè)數(shù)保存在變量num中。（說明：下面的算法和C/C+ 程序只要給出其中一種形式即

5、可。）/ 調(diào)用為InOrderCount (root, num)，mun的初值為0。算法 計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù) 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 = NULL p->rchil

6、d = = NULL)則 num num+1 num+; InOrderCount (p->rchild) InOrderCount (p->rchild); 2. 算法結(jié)束 設(shè)二叉樹中有n個(gè)結(jié)點(diǎn)，因?yàn)槭潜闅v運(yùn)算，故此算法的時(shí)間復(fù)雜度為：O(n)。3 編寫一個(gè)求單循環(huán)鏈表中結(jié)點(diǎn)個(gè)數(shù)的算法，并分析算法的時(shí)間復(fù)雜度(要求寫出存儲結(jié)構(gòu)的描述)。答：型與變量說明及算法如下：typedef int datatype; / 結(jié)點(diǎn)的數(shù)據(jù)域的類型為整型typedef struct node / 結(jié)點(diǎn)類型定義 datatype data; / 結(jié)點(diǎn)的數(shù)據(jù)域 struct node *next; /

7、結(jié)點(diǎn)的指針域 ListNode, *LinkList;ListNode *p; LinkList rear;int n;（說明：下面的算法和C/C+ 程序只要給出其中一種形式即可。）算法 求單循環(huán)鏈表中結(jié)點(diǎn)個(gè)數(shù) 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; 循環(huán) 當(dāng) p->next rear 時(shí)，執(zhí)行 while (