數(shù)據(jù)結(jié)構(gòu)試卷樣卷

1、安 徽 建 筑 工 業(yè) 學(xué) 院 試 卷（試卷 A） 共 3 頁 第 1 頁總 分二三一二三四五六七（樣卷）八閱卷教師考試課程：算法與數(shù)據(jù)結(jié)構(gòu) 班級： 05計算機 學(xué)號： 姓名： 復(fù)核教師一 單項選擇題（共20題，每題1.5分，共30分）1. 下面程序段的時間復(fù)雜度為( C )。 for(int i=0;i<m;i+) for(int j=0;j<n;j+) aij=i*j; A、O(m2) B、O(n2) C、O(m*n) D、O(m+n) 2. 一個棧的輸入序列為1，2，3，4，下面哪一個序列不可能是這個棧的輸出序列( C )。A、 1，3，2，4 B、2，3，4，1C、 4，3

2、，1，2 D、3，4，2，1 3. 采用順序搜索方法查找長度為n的順序表時，搜索成功的平均搜索長度為（ D ）。A、 nB、 n/ C、(n-1)/2 D、(n+1)/2 4. 若一棵二叉樹具有10個度為2的結(jié)點，則該二叉樹的度為0的結(jié)點個數(shù)是（ B ）A、 9B、 11C、 12D、不確定 5. 對矩陣壓縮存儲是為了（ B ）。A、方便壓縮 B、節(jié)省空間 C、方便存儲 D、提高運算速度 6. 在已知待排序文件已基本有序的前提下，效率最高的排序方法是（ A ） A、 直接插入排序 B、 直接選擇排序 C、 快速排序 D、 歸并排序 7. 在有n個葉子結(jié)點的哈夫曼樹中，其結(jié)點總數(shù)為（ D ）。、

3、 不確定 、2n 、2n+1 、2n-1 8. 廣義表( (A , B, E, F , G)的表尾是( B )。 A、(B, E , F, G) B、( )C、（A，B， E，F(xiàn)，G） D、不存在 9. 折半查找要求查找表中各元素的關(guān)鍵字值必須是（ A ）排列。、 遞增或遞減 、遞增 、遞減 、無序 10. 在一個單鏈表中，若p所指結(jié)點不是最后一個結(jié)點，在p之后插入t所指結(jié)點，則執(zhí)行（ B ） A、 t->next=p；p->next=t； B、 t->next=p->next；p->next=t；C、 t->nexr=p->next；p=t

4、； D、 p->next=t；t->next=p； 11在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復(fù)雜度為（ A ）。A、 O(n)B、 O(n/2)C、 O(1)D、 O(n2)12帶頭結(jié)點的單鏈表first為空的判定條件是（ B ）。A、 first = NULL; B、 first->link = NULL;C、 first->link = first; D、 first != NULL;13當利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大長度為（ B ）。A、 n-2 B、 n-1C、 n D、 n+114m階B樹中的m是指（ C ）。A、 每

5、個結(jié)點至少有m棵子樹 B、 非終端結(jié)點中關(guān)鍵字的個數(shù)C、 每個結(jié)點至多有m棵子樹 D、 m階B樹的深度（或高度）15在一棵樹中，（ C ）沒有前驅(qū)結(jié)點。 A、 分支結(jié)點 B、 葉結(jié)點 C、 樹根結(jié)點 D、 空結(jié)點16在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設(shè)最低的不平衡結(jié)點為A，并已知A的左孩子的平衡因子為-1，右孩子的平衡因子為0，則應(yīng)作（ B ）型調(diào)整以使其平衡。A、LL B、 LR C、 RL D、 RR17對于長度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長度為（ C ）的值除以9。 A、 20 B、 18 C、 25 D、 2218在有向圖中每個頂點的度等于

6、該頂點的（ C ）。A、 入度 B、 出度C、 入度與出度之和D、 入度與出度之差19在基于排序碼比較的排序算法中，（ C ）算法的最壞情況下的時間復(fù)雜度不高于O(nlog2n)。A、 起泡排序B、 希爾排序C、 歸并排序D、 快速排序20當?shù)闹递^小時，散列存儲通常比其他存儲方式具有（ B ）的查找速度。A、 較慢B、較快C、 相同注：1.請命題老師用黑色的墨水工整的書寫，作圖準確，以保證試卷字跡清晰。2.請命題老師在試題后面留出答題空間。 3.學(xué)生不得在草稿紙上答題安 徽 建 筑 工 業(yè) 學(xué) 院 考 試 命 題 紙（A）卷 共 3 頁 第 2 頁考試課程： 算法與數(shù)據(jù)結(jié)構(gòu) 班級： 05計算機

7、 學(xué)號： 姓名： 二、 填空題（每空1分，共10分）1在一棵樹中， 葉子 結(jié)點沒有后繼結(jié)點。2在一棵AVL樹（高度平衡的二叉搜索樹）中，每個結(jié)點的左子樹高度與右子樹高度之差的絕對值不超過 1 。3 n (n0) 個頂點的無向圖最多有 n(n-1)/2 條邊，最少有 0 條邊。4按策略劃分內(nèi)部排序方法可分為五類： 插入排序 、 選擇排序 、交換排序、歸并排序和分配排序。5n個結(jié)點的二叉樹采用二叉鏈表存放，共有空鏈域個數(shù)為_ n+1 _ 。 6已知二維數(shù)組A2010采用行序為主方式存儲,每個元素占2個存儲單元,并且A105的存儲地址是1000,則A189的存儲地址是_ 1168 _ 。7在各種查找

8、方法中，平均查找長度與結(jié)點個數(shù)無關(guān)的是_ 哈希查找法 _ 。 8樹的存儲結(jié)構(gòu)中，常用的鏈表結(jié)構(gòu)有孩子表示法、雙親表示法和 孩子兄弟表示法 三種。三、判斷題（共10題，每題1分，共10分）1. （ T ）有回路的有向圖不能完成拓撲排序。 2. （ F ）一棵樹的度是指該樹中所有結(jié)點的度的和。 3. （ T ）在完全二叉樹中，一個結(jié)點若沒有左孩子，則它一定沒有右孩子。  4. （F ）在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。 5. （ F ）能夠在鏈接存儲的有序表上進行折半搜索，其時間復(fù)雜度與在順序表上相同。6. （ F ）通常遞歸的算法簡單、易懂、容易編

9、寫，而且執(zhí)行的效率也高。7. （ T ）直接選擇排序是一種不穩(wěn)定的排序方法 。 8. （ T ）一個廣義表的表尾總是一個廣義表。 9. （ F ）對任意一個圖，從它的某個頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索遍歷可訪問到該圖的每個頂點。 10.（ T ）由樹轉(zhuǎn)化成二叉樹，其根的右子孩指針總是空的。四、簡答題（共4題，每題5分，共20分）1.有一組關(guān)鍵字50，52，85，22，96，17，36，55，請用快速排序，寫出第一趟排序結(jié)果。解：36，17，22，50，96，85，52，55 2.   將關(guān)鍵碼53，78，65，17，87，09，81，45，23依次插入到一棵初始為空的二叉排序

10、樹中，畫出最終的二叉排序樹。 3.已知葉子結(jié)點值2，3，5，6，9，11，構(gòu)造哈夫曼樹，計算其帶權(quán)路徑長度。WPL=11×2+6×2+9×2 +5×3 +2×4+3×4=87注：哈夫曼樹的左右子樹可以互換注：1.請命題老師用黑色的墨水工整的書寫，作圖準確，以保證試卷字跡清晰。2.請命題老師在試題后面留出答題空間。 3.學(xué)生不得在草稿紙上答題安 徽 建 筑 工 業(yè) 學(xué) 院 考 試 命 題 紙（A）卷 共 3 頁 第 3 頁考試課程： 算法與數(shù)據(jù)結(jié)構(gòu) 班級： 05計算機 學(xué)號： 姓名： 4.已知某二叉樹的前序序列為CBADEGFH，中序序

11、列為ABCEFGHD，請畫出對應(yīng)的二叉樹并給出其后序序列。后序序列為ABFHGEDC。評分標準：畫出二叉樹4分 給出后序序列1分 五、算法設(shè)計題（30分） 1 編寫一個直接插入排序算法。（10分）解：typedef struct int rMAXSIZE +1； int length； SqList；void StraightInsertSort(SqList *S) int i，j；for(i=2；i<=S->length；i+) S->r0=S->ri； j= i-1; while (S->r0 < S->rj) S->rj+1=S->

12、rj；j- ; S->rj+1=S->r0； 2設(shè)二叉樹以二叉鏈表形式存儲，請編寫一個求葉子結(jié)點總數(shù)的算法。（10分）（要求寫出二叉樹的二叉鏈表存儲表示，并在此基礎(chǔ)上實現(xiàn)）。typedef struct BiTNodeTElemType data;struct BiTNode *Lchild, *Rchild; bitnode, *BinTree; 1分int leafNum=0; 2分void countLeaf(BinTree t) if (t=Null) return; 3分if (t->Lchild=Null && t->Rchild=Null) leafNum+; 5分else countLeaf(t->Lchild); 7分countLeaf(t->Rchild); 8分 3、設(shè)計一個算法，就地逆置帶頭結(jié)點的單鏈表head。（要求寫出單鏈表的鏈式存儲結(jié)構(gòu)）（10分） 解： typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList; void Inve