數(shù)據(jù)結(jié)構(gòu)試卷一及答案.doc

習題一一、 選擇題 ( 每小題 2 分，共 20 分 ) 1下列程序段的時間復雜度為（ ）。i=0，s=0； while (snext=p-next；p-next=-s； (B) q-next=s； s-next=p；(C) p-next=s-next；s-next=p； (D) p-next=s；s-next=q；4設(shè)輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為（ ）。(A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1 (C) 3，1，2，5，4，6 (D) 1，5，4，6，2，35設(shè)有一個10階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順序存儲到連續(xù)的55個存儲單元中，每個數(shù)組元素占1個字節(jié)的存儲空間，則A54地址與A00的地址之差為（ ）。(A) 10 (B) 19 (C) 28 (D) 556設(shè)一棵m叉樹中有N1個度數(shù)為1的結(jié)點，N2個度數(shù)為2的結(jié)點，Nm個度數(shù)為m的結(jié)點，則該樹中共有（ ）個葉子結(jié)點。7. 二叉排序樹中左子樹上所有結(jié)點的值均（ ）根結(jié)點的值。(A) (C) = (D) !=8. 設(shè)一組權(quán)值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長度為（ ）。(A) 129 (B) 219 (C) 189 (D) 2299. 設(shè)有n個關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個關(guān)鍵字映射到HASH表中需要做（ ）次線性探測。(A) n2 (B) n(n+1) (C) n(n+1)/2 (D) n(n-1)/210.設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點且度數(shù)為0的結(jié)點數(shù)為n，則這棵二叉中共有（ ）個結(jié)點。(A) 2n (B) n+l (C) 2n-1 (D) 2n+l二、 填空題 ( 每空2 分，共 50 分 ) 1. 數(shù)據(jù)元素及其關(guān)系在計算機存儲器內(nèi)的表示稱為。 2. 假設(shè)某個帶頭結(jié)點的單鏈表的頭指針為head，則判定該表為空表的條件是。 3. 棧是一種操作受限的線性結(jié)構(gòu)，其操作的主要特征是 。若進棧序列為123，則不可能的出棧序列為 。 4. 已知廣義表C=(a，(b，c)，d)，則：tail(head(tail(C)= 。 5. 要在單鏈表中指針p所指向結(jié)點后插入s所指的結(jié)點，應(yīng)順序執(zhí)行 和 語句。 6.具有3個結(jié)點的二叉樹有 種形態(tài)。 7.一棵二叉樹采用二叉鏈表存儲，則必有 個指針域不空。 8.對關(guān)鍵字序列采用快速排序以位于最左位置的對象為基準而得到的第一次劃分結(jié)果為 。 9. 在哈希查找中，處理沖突的方法有 、再哈希法、 和建立公共溢出區(qū)。 10.在堆排序過程中，由n個待排序記錄建成初始堆需要進行 次篩選。 11.已知二叉樹中葉子結(jié)點數(shù)為50，則該二叉樹的總結(jié)點數(shù)至少應(yīng)有 個。 12.一個具有n個頂點無向連通圖最少有 條邊，最多有 條邊。 13.圖的深度優(yōu)先搜索遍歷算法類似于二叉樹的 遍歷，圖的廣度優(yōu)先遍歷算法類似于二叉樹的 遍歷。 14.在二叉排序樹上進行 遍歷，可以得到一個關(guān)鍵字的遞增序列。 15.在圖G的鄰接表表示中，每個頂點鄰接表中所含的結(jié)點數(shù)，對于無向圖來說等于該頂點的 ；對于有向圖來說等于該頂點的 。 16.若待排序序列中存在多個具有相同關(guān)鍵字的記錄，若排序完成后這些記錄的相對位置發(fā)生改變，則稱該排序法是 。寫出3種不穩(wěn)定的排序法 、 、 。三、 判斷題 (每小題1分， 共 10 分 ) 1.單鏈表的頭結(jié)點是必不可少的。 （ ） 2.如果一個二叉樹中沒有度為1的結(jié)點，則必為滿二叉樹。 （ ） 3順序存儲結(jié)構(gòu)只能用來存放線性結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)只能用來存放非線性結(jié)構(gòu)。 （ ） 4.隊列只能在隊首進行刪除，在隊尾進行插入。 （ ） 5.一棵樹轉(zhuǎn)換成二叉樹后根結(jié)點一定沒有右孩子。 （ ） 6.有向圖中，所有結(jié)點的出度之和等于入度之和。 （ ） 7.內(nèi)部排序是指排序過程在內(nèi)存中進行的排序。 （ ） 8.在一個大根堆中，最小元素不一定在最后。 （ ） 9.一棵赫夫曼樹中不存在度為1的結(jié)點。 （ ） 10.平衡二叉樹左子樹和右子樹的深度之差的絕對值不超過1。（ ） 四、算法設(shè)計題(每題10分，共20分) 1從順序表中刪除具有最小值的元素并返回被刪元素的值。空出的位置由最后一個元素填補，若順序表為空則顯示出錯信息。 順序表的類型描述如下： #define maxsize 100typedef struct ElemType elemmaxsize； /* 線性表占用的數(shù)組空間。*/int last； /*記錄線性表中最后一個元素在數(shù)組elem 中 的位置（下標值），空表置為-1*/ SeqList；2已知一個二叉樹采用二叉鏈表存放，寫一算法，計算二叉樹的度為2的結(jié)點的個數(shù)。 二叉鏈表的類型描述如下： typedef struct NodeDataType data;struct Node * lchild;struct Node * rchild;BiTNode, *BiTree;答案：一、選擇題 1A 2D 3B 4B 5B 6D 7A 8D 9D 10C 二、填空題 1.物理結(jié)構(gòu)或存儲結(jié)構(gòu) 2.head-next=NULL 3.先進后出或后進先出、312 4. （c） 5. s-next= p-next 、p-next=s 6. 5種 7.n-1個 8.（40,38,46,56,79,84） 9.開放定址法、鏈地址法 10. n/2 11. 99 12.n-1、n(n-1)/2 13.先序，層次 14.中序 15.度、出度 16.不穩(wěn)定、（簡單選擇排序、堆排序、快速排序、希爾排序）任選3個 三、判斷題 1-10： 四、算法設(shè)計題 1.解：#define OK 1#define ERROR 0int DelList(SeqList *L,ElemType *e)/*在順序表L中刪除最小值的數(shù)據(jù)元素，并用指針參數(shù)e返回其值?？粘龅奈恢糜勺詈笠粋€元素填補*/ int m=0,i; /假定0號元素的值最小 if (L-last = -1 ) /表空, 中止操作返回 printf( “ List is Empty!n ”); return error; for (i = 1; i last; i+ ) /循環(huán), 尋找具有最小值的元素 if (L-elem i elem m ) m = i; /讓m指向當前具最小值的元素 *e= L-elem m; L-elem m = L-elem L-last; L-last-; /空出位置由最后元素填補, 表最后元素位置減1 return ok; 2.解：/* NodeCount保存滿足條件的結(jié)點的數(shù)目的全局變量