《數(shù)據(jù)結構》模擬試題綜合測試題帶答案 (16)

1、數(shù)據(jù)結構模擬試題16一、填空題（每小題2分，共20分）1、 數(shù)據(jù)及其聯(lián)系在計算機內(nèi)存中的存儲稱為數(shù)據(jù)的物理（存儲）結構，基本的物理結構有 和 。2、 數(shù)據(jù)結構中評價算法的兩個重要指標是 和 。3、 堆棧是操作受限的線性結構，只能在 插入和刪除元素；不能進行插入和刪除元素的一端稱為 。4、 有一個10階對稱矩陣A，采用壓縮存儲方式（以行為主存儲），A00的地址是100，若每個元素占3個基本存儲單元，則A58的地址是 。5、 設有一棵深度為n的二叉樹，它至少有 個結點，至多 有 個結點。6、 動態(tài)存儲管理主要是解決系統(tǒng)如何 _、_ 的兩大問題。7、對線性表進行二分查找時，要求線性表必須是 ，且要求

2、 。8、 對于內(nèi)部排序，有多種排序方法。按排序基本思想（策略），可分為 、 、 、歸并排序和基數(shù)排序。9、 索引表是存儲記錄的 和記錄的 之間的對照表，每個元素稱為一個索引項。10、 對于文件，按物理結構劃分，可分為順序文件、 文件、 文件和多關鍵字文件。二、單項選擇題（請將答案寫在題目后的括號中。每題2分，共18分）1、有如下遞歸函數(shù)fact(n)，其時間復雜度是（ ）。Fact(int n) if (n<=1) return 1; else return(n*fact(n-1) ;（A） O(n) （B） O(n2) （C） O(2n) （D） O(n2n)2、線性表若采用鏈式存儲結

3、構時，要求內(nèi)存中可用存儲單元的地址是（ ）。（A） 必須是連續(xù)的 （B） 部分地址必須是連續(xù)的（C） 一定是不連續(xù)的 （D） 是否連續(xù)沒有要求3、 判斷一個循環(huán)隊列Q（最多元素個數(shù)為m）為滿隊列的條件是（ ）。（A） Q.front=Q.rear ； （B） Q.front!=Q.rear ；（C） Q.front=(Q.rear+1)%m； （D） Q.front!=(Q.rear+1)%m；4、一棵二叉樹，其先序遍歷序列是abdehicfg，中序遍歷序列是dbheiafcg，則其后序遍歷序列是( )。（A） dhiebafgc （B） dhiebfgca（C） dhiebfgac （D）

4、dbhiefgca5、 在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的 倍，所有頂點的度之和等于所有頂點的入度之和的 倍。（ ）（A） 1/2，1 （B） 2，1 （C） 1，2 （D） 1，46、對于有n個頂點e(e>n)條邊的帶權無向圖，以下關于該圖的最小生成樹的描述正確的是（ ）。（A） 最小生成樹是唯一的。（B） 最小生成樹中所有邊上的權值之和是唯一的。（C） 最小生成樹有n條邊。（D） 最小生成樹有n個頂點e-1條邊。7、 設哈希表長m=14，H（key）=key MOD 13，address(19)=6，address(41)=2，address(57)=5，ad

5、dress(85)=7，其余地址為空。對于關鍵字31，若用線性探測法解決沖突，其地址是 ；若用二次探測法解決沖突，其地址是 。（ ）（A） 8，4 （B） 11，4 （C） 4，8 （D） 4，118、從未排序序列中挑選元素，并將其依次放入到已排序序列中(初始時為空)的一端的方法是（ ）。（A） 直接插入排序 （B） 選擇排序 （C） 快速排序 （D） 堆排序9、 若以3, 5, 6, 8, 14作為葉子的權值構造Huffman樹(按左子樹根結點的權小于等于右子樹根結點的權的次序構造)，則其帶權路徑長度WPL為（ ）。（A） 78 （B） 80 （C） 82 （D） 84三、分析題（每題6分，

6、共30分）1、 設QU0，5是一個靜態(tài)循環(huán)隊列，初始狀態(tài)是front=rear=0，畫出進行下列操作后隊列的頭、尾指針的狀態(tài)變化情況，若不能入隊，請指出不能入隊的元素，并說明理由。（1） a，e，b入隊； （2） a，e出隊； （3） s，t，k，m入隊； （4） b，s，t出隊； （5） r，p，u，v入隊；2、 設有一棵樹如下圖， 給出該樹的孩子表示法的復合鏈表存儲結構； 將此樹轉換為二叉樹； 給出轉換后二叉樹的后序遍歷序列。ABDGECHJIF3、 設有如下帶權有向無環(huán)圖， 給出該圖的正鄰接鏈表存儲結構； 給出對該圖進行拓撲排序過程。 9V45107863543V0V1V2V3V54、

7、線性表的關鍵字集合31，25，18，29，42，69，95，53，17，16，47，116，87，共有13個元素，已知散列函數(shù)為：H（k） = k MOD 11，采用鏈地址法處理沖突，請給出對應的散列表結構。5、 已知關鍵字序列15，29，12，40，47，39，58，27，73，44，86，55，請給出采用希爾排序法對該序列做非遞減排序的過程（設增量序列是5，3，1）。四、算法填空（每空2分，共20分）請在下面各算法的空白處填上相應語句以實現(xiàn)算法功能。每個空白只能填一個語句。1、設有一個以L為頭結點的雙向循環(huán)鏈表，刪除數(shù)據(jù)為key的所有結點，數(shù)據(jù)結構定義如下：typedef struct L

8、node ElemType key ; /* 關鍵字碼 */struct Lnode *prior; /* 指向直接前趨結點的指針域 */struct Lnode *next; /* 指向直接后繼結點的指針域 */LNode; /* 結點的類型 */void *Delete_Node(LNode L，ElemType key) ElemType data; LNode *p;if ( L->next=L) printf(“%s”,” 鏈表為空！n”); else p=L->next ;while ( ) if (EQ(p->data=key) ) ； ; free(p); /

9、* 刪除數(shù)據(jù)為key的結點 */ 2、非遞歸中序遍歷二叉樹。#define MAXNODE 50void InorderTraverse( BTNode *T) BTNode *stackMAXNODE ,*p=T ; int top=0 , bool=1 ; if (T=NULL) printf(“ Binary Tree is Empty!n”) ; else do while (p!=NULL) ; p=p->Lchild ; if (top=0) bool=0 ; else p=stacktop ; top- ; visit( p->data ) ; ; while(boo

10、l!=0) ; 以下2題是查找和排序，所使用的記錄類型的定義如下：#define MAX_SIZE 100typedef int KeyType ;typedef struct RecType KeyType key ; /* 關鍵字碼 */infoType otherinfo ; /* 其他域 */RecType ;typedef struct Sqlist RecType RMAX_SIZE ; /* 順序表 */int length ; /* 實際元素個數(shù) */Sqlist ;3、二叉排序樹的查找BSTNode *BST_Serach(BSTNode *T , KeyType key)

11、BSTNode *p=T ;while (p!=NULL&& !EQ(p->key, key) ) if ( LT(key, p->key) ) ;else p=p->Rchild ;if (EQ(p->key, key) ) return(p) ;else ;4、選擇排序算法void simple_selection_sort(Sqlist *L) int m, n , k;for (m=1; ; m+) k=m ; for (n=m+1; n<=L->length; n+) if ( LT(L->Rn.key, L->Rk.k

12、ey) ) k=n ;if ( ) /* 記錄交換 */ L->R0=L->Rm; L->Rm=L->Rk; ; 五、編寫算法（12分）設T是指向二叉樹根結點的指針變量，每個結點的數(shù)據(jù)都是字符。 寫出輸出樹中度為1及度為0的結點數(shù)的算法。（6分） 寫出從根結點開始按層次次序“自上而下，從左至右”輸出樹中的各結點的算法。（6分）提示：為保證是按層次遍歷，必須設置一個隊列，初始化時為空。共9頁 第13頁數(shù)據(jù)結構模擬試題16參考答案一、填空題（每小題2分，共20分）1、 順序存儲結構 鏈式存儲結構 2、 時間復雜度 空間復雜度3、 棧頂 棧底4、 2745、 n 2n-1 6

13、、 存儲空間的分配 釋放的存儲空間的回收7、 以順序方式存儲 結點按關鍵字有序8、 插入排序 交換排序 選擇排序9、 關鍵字 存儲地址 或 存儲地址 關鍵字10、索引文件 散列(哈希)文件二、單項選擇題（請將答案寫在題目后的括號中。每題2分，共18分）題號123456789答案ADCBCDABB三、分析題（每題6分，共30分）102435frontrear(a) 隊列初始化 a, e, b入隊10243frontrearaeb51、解：做完下列操作后隊列的頭尾指針的狀態(tài)變化情況如下面圖形所示。 b，s，t出隊 r，p，u，v入隊10243rearfrontmvp5ukr a, e出隊 s，t，

14、k，m入隊10243frontm5kreart10243rear5bfront10243frontmtb5skreart每圖1分2、解： 該樹的孩子表示法的復合鏈表存儲結構如下圖；(3分) A BC DE F G H I J 0100 123456789MAX_NODE-1rootnum3 2 1 6 5 4 9 8 7 將此樹轉換為二叉樹如下圖。(2分) ABFCEDIJHG 轉換后二叉樹的后序遍歷序列是：GFEJIHDCBA (1分)3、 解： 該圖的正鄰接鏈表如下圖所示：(2分)V0 2V1 2V2 3V3 1V4 2V5 2 0123451 5 2 3 2 6 4 3 5 5 3 4

15、5 10 4 8 3 9 5 7 給出對該圖進行拓撲排序過程如下(3分)，其拓撲序列是：V0V1V2V4V3V5 (1分)9V451078634V1V2V3V59V4510784V2V3V5 輸出V0后 輸出V1后9V457V3V5 輸出V2后5V3V5 輸出V4后V5 輸出V3后4、 解：根據(jù)所給定的散列函數(shù)和處理沖突方法，得到的散列表結構如下：01234567891025186917 16 116 87 3129 47 95 4253 5、解：采用希爾排序法對該序列做非遞減排序的每一趟結果如下。(一趟3分，二趟2分，三趟1分)444715 29 12 40 47 39 58 27 73 4

16、4 86 55初始關鍵字：555873558442927554715 29 12 40 44 39 55 27 73 47 86 58一趟排序后：15 27 12 40 29 39 47 44 58 55 86 73二趟排序后：12 15 27 29 39 40 44 47 55 58 73 86三趟排序后：四、算法填空（每空2分，共20分）請在下面各算法的空白處填上相應語句實現(xiàn)算法功能。每個空白處只能填一個語句。1、設有一個以L為頭結點的雙向循環(huán)鏈表，刪除數(shù)據(jù)為key的所有結點。p>next !=Lp>prior->next=p>nextp->next->

17、prior=p->prior2、非遞歸中序遍歷二叉樹。stack+top=pp=p->Rchild3、二叉排序樹的查找。p=p>Lchild return(NULL)4、選擇排序算法。m<L->length k!=m L->Rk=L->R0五、編寫算法（12分）解： 輸出樹中度為1及度為0的結點數(shù)的算法。（6分）#define MAXNODE 50void count_nodes( BTNode *T) BTNode *StackMAXNODE ,*p=T;int top=0, num1=0, num0=0 ;if (T=NULL) printf(“B

18、inary Tree is Empty!n”) ;else stack+top=p ; while (top>0) （循環(huán)及控制1分） p=stacktop- ; if ( !(p->Lchild!=NULL&&p->Rchild!=NULL) ) （判斷部分3分） if (p->Lchild=NULL&&p->Rchild=NULL) num0+ ; else if (p->Lchild!=NULL|p->Rchild!=NULL) num1+ ; if (p->Rchild!=NULL ) stack+top=p->Rc