《數(shù)據(jù)結(jié)構(gòu)》模擬試題綜合測(cè)試題帶答案 (16)

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

2、 。8、 對(duì)于內(nèi)部排序，有多種排序方法。按排序基本思想（策略），可分為 、 、 、歸并排序和基數(shù)排序。9、 索引表是存儲(chǔ)記錄的 和記錄的 之間的對(duì)照表，每個(gè)元素稱為一個(gè)索引項(xiàng)。10、 對(duì)于文件，按物理結(jié)構(gòu)劃分，可分為順序文件、 文件、 文件和多關(guān)鍵字文件。二、單項(xiàng)選擇題（請(qǐng)將答案寫在題目后的括號(hào)中。每題2分，共18分）1、有如下遞歸函數(shù)fact(n)，其時(shí)間復(fù)雜度是（ ）。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、線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)

3、構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址是（ ）。（A） 必須是連續(xù)的 （B） 部分地址必須是連續(xù)的（C） 一定是不連續(xù)的 （D） 是否連續(xù)沒(méi)有要求3、 判斷一個(gè)循環(huán)隊(duì)列Q（最多元素個(gè)數(shù)為m）為滿隊(duì)列的條件是（ ）。（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、 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 倍，所有頂點(diǎn)的度之和等于所有頂點(diǎn)的入度之和的 倍。（ ）（A） 1/2，1 （B） 2，1 （C） 1，2 （D） 1，46、對(duì)于有n個(gè)頂點(diǎn)e(e>n)條邊的帶權(quán)無(wú)向圖，以下關(guān)于該圖的最小生成樹的描述正確的是（ ）。（A） 最小生成樹是唯一的。（B） 最小生成樹中所有邊上的權(quán)值之和是唯一的。（C） 最小生成樹有n條邊。（D） 最小生成樹有n個(gè)頂點(diǎn)e-1條邊。7、 設(shè)哈希表長(zhǎng)m=14，H（key）=key MOD 13，address(19)=6，address(41)=2，address(57)=5，ad

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

6、共30分）1、 設(shè)QU0，5是一個(gè)靜態(tài)循環(huán)隊(duì)列，初始狀態(tài)是front=rear=0，畫出進(jìn)行下列操作后隊(duì)列的頭、尾指針的狀態(tài)變化情況，若不能入隊(duì)，請(qǐng)指出不能入隊(duì)的元素，并說(shuō)明理由。（1） a，e，b入隊(duì)； （2） a，e出隊(duì)； （3） s，t，k，m入隊(duì)； （4） b，s，t出隊(duì)； （5） r，p，u，v入隊(duì)；2、 設(shè)有一棵樹如下圖， 給出該樹的孩子表示法的復(fù)合鏈表存儲(chǔ)結(jié)構(gòu)； 將此樹轉(zhuǎn)換為二叉樹； 給出轉(zhuǎn)換后二叉樹的后序遍歷序列。ABDGECHJIF3、 設(shè)有如下帶權(quán)有向無(wú)環(huán)圖， 給出該圖的正鄰接鏈表存儲(chǔ)結(jié)構(gòu)； 給出對(duì)該圖進(jìn)行拓?fù)渑判蜻^(guò)程。 9V45107863543V0V1V2V3V54、

7、線性表的關(guān)鍵字集合31，25，18，29，42，69，95，53，17，16，47，116，87，共有13個(gè)元素，已知散列函數(shù)為：H（k） = k MOD 11，采用鏈地址法處理沖突，請(qǐng)給出對(duì)應(yīng)的散列表結(jié)構(gòu)。5、 已知關(guān)鍵字序列15，29，12，40，47，39，58，27，73，44，86，55，請(qǐng)給出采用希爾排序法對(duì)該序列做非遞減排序的過(guò)程（設(shè)增量序列是5，3，1）。四、算法填空（每空2分，共20分）請(qǐng)?jiān)谙旅娓魉惴ǖ目瞻滋幪钌舷鄳?yīng)語(yǔ)句以實(shí)現(xiàn)算法功能。每個(gè)空白只能填一個(gè)語(yǔ)句。1、設(shè)有一個(gè)以L為頭結(jié)點(diǎn)的雙向循環(huán)鏈表，刪除數(shù)據(jù)為key的所有結(jié)點(diǎn)，數(shù)據(jù)結(jié)構(gòu)定義如下：typedef struct L

8、node ElemType key ; /* 關(guān)鍵字碼 */struct Lnode *prior; /* 指向直接前趨結(jié)點(diǎn)的指針域 */struct Lnode *next; /* 指向直接后繼結(jié)點(diǎn)的指針域 */LNode; /* 結(jié)點(diǎn)的類型 */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的結(jié)點(diǎn) */ 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 ; /* 關(guān)鍵字碼 */infoType otherinfo ; /* 其他域 */RecType ;typedef struct Sqlist RecType RMAX_SIZE ; /* 順序表 */int length ; /* 實(shí)際元素個(gè)數(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分）設(shè)T是指向二叉樹根結(jié)點(diǎn)的指針變量，每個(gè)結(jié)點(diǎn)的數(shù)據(jù)都是字符。 寫出輸出樹中度為1及度為0的結(jié)點(diǎn)數(shù)的算法。（6分） 寫出從根結(jié)點(diǎn)開始按層次次序“自上而下，從左至右”輸出樹中的各結(jié)點(diǎn)的算法。（6分）提示：為保證是按層次遍歷，必須設(shè)置一個(gè)隊(duì)列，初始化時(shí)為空。共9頁(yè) 第13頁(yè)數(shù)據(jù)結(jié)構(gòu)模擬試題16參考答案一、填空題（每小題2分，共20分）1、 順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 2、 時(shí)間復(fù)雜度 空間復(fù)雜度3、 棧頂 棧底4、 2745、 n 2n-1 6

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

14、k，m入隊(duì)10243frontm5kreart10243rear5bfront10243frontmtb5skreart每圖1分2、解： 該樹的孩子表示法的復(fù)合鏈表存儲(chǔ)結(jié)構(gòu)如下圖；(3分) A BC DE F G H I J 0100 123456789MAX_NODE-1rootnum3 2 1 6 5 4 9 8 7 將此樹轉(zhuǎn)換為二叉樹如下圖。(2分) ABFCEDIJHG 轉(zhuǎn)換后二叉樹的后序遍歷序列是：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 給出對(duì)該圖進(jìn)行拓?fù)渑判蜻^(guò)程如下(3分)，其拓?fù)湫蛄惺牵篤0V1V2V4V3V5 (1分)9V451078634V1V2V3V59V4510784V2V3V5 輸出V0后 輸出V1后9V457V3V5 輸出V2后5V3V5 輸出V4后V5 輸出V3后4、 解：根據(jù)所給定的散列函數(shù)和處理沖突方法，得到的散列表結(jié)構(gòu)如下：01234567891025186917 16 116 87 3129 47 95 4253 5、解：采用希爾排序法對(duì)該序列做非遞減排序的每一趟結(jié)果如下。(一趟3分，二趟2分，三趟1分)444715 29 12 40 47 39 58 27 73 4

16、4 86 55初始關(guān)鍵字：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分）請(qǐng)?jiān)谙旅娓魉惴ǖ目瞻滋幪钌舷鄳?yīng)語(yǔ)句實(shí)現(xiàn)算法功能。每個(gè)空白處只能填一個(gè)語(yǔ)句。1、設(shè)有一個(gè)以L為頭結(jié)點(diǎn)的雙向循環(huán)鏈表，刪除數(shù)據(jù)為key的所有結(jié)點(diǎn)。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的結(jié)點(diǎn)數(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