1、要求：所有的題目的解答均寫在答題紙上，需寫清楚題目的序號。每張答題紙都要寫上姓名和序號。一、單項選擇題（每小題2分，共計30分）1. 算法的時間復雜度取決于 。A. 問題的規模B. 待處理數據的初始狀態C. A和BD. 計算機的配置2. 由n個無序的元素創建一個有序單鏈表的算法的時間復雜度是 。AO(nlog2n) BO(n) CO(n2) DA或C3. 在 _中將會用到棧結構。A. 遞歸調用 B. 函數調用 C. 表達式求值 D.以上場景都有4. 設循環隊列的最大容量是N，front是頭指針，rear是尾指針，則隊空的判定條件為 。A. (rear+1)%N=frontB. rea

2、r+1=front C. rear=frontD. rear=0，且front=05. 設二維數組A35，每個數組元素占用2個存儲單元，若按列優先順序進行存儲，A00的存儲地址為100，則A23的存儲地址是 。A. 122B. 126C. 114D. 1166. 在KMP算法中，串“ababaabab”的next數組值為_。A. -1,0,0,1,2,3,1,2,3B. -1,0,0,1,2,1,1,2,3C. -1,0,0,1,2,3,4,1,2D. -1,0,0,1,2,3,1,2,27. 在下列存儲形式中，_ 不是m叉樹（m>2）的存儲形式？A雙親表示法 B孩子鏈表表示法 C孩子兄

3、弟表示法 D順序存儲表示法8.下面 算法適合用于構造一個稠密圖的最小生成樹。A. Dijkstra算法B. Prim算法C. Floyd算法D. Kruskal算法9. 方法可以判斷一個有向圖是否存在回路。A. 求最小生成樹B. 拓撲排序C. 求關鍵路徑D. 求最短路徑10. 已知圖G的鄰接表如圖1所示，則從頂點V0出發進行深度優先遍歷的結果是_。圖1 圖G的鄰接表A. 0,1,2,3,4B. 0,1,2,4,3C. 0,1,3,4,2D. 0,1,4,2,311. 二分查找和二叉排序樹查找的時間性能 。A. 相同B. 有時不同C. 完全不同D. 數量級都是O(log2n)12.關于m階B-樹

4、說法錯誤的是 。A. m階B-樹是一棵平衡的m叉樹B. B-樹中的查找無論是否成功都必須找到最下層結點C. 根結點最多含有m棵子樹D. 根結點至少含有2棵子樹13. 時間復雜度恒為O(nlog2n)且不受數據初始狀態影響的排序算法是（ ）。A歸并排序 B希爾排序 C快速排序 D簡單選擇排序14. 有一種排序方法，它每一趟都將未排序序列中的一個元素，插入到已排序序列的合適位置，該排序方法是（ ）。A. 堆排序B. 冒泡排序C. 直接插入排序D. 簡單選擇排序15. 堆的形狀是一棵_。A. 滿二叉樹 B. 二叉判定樹 C. 平衡二叉樹 D. 完全二叉樹二、問答題（共計45分）1. 有以下算法，分析

5、執行fun(a,n,0)的時間復雜度。需要推導過程。（7分）void fun (int a, int n, int k ) / 數組a共有n個元素1 if (k=n-1)2 for(int i = 0; i < n; i+) 3 printf(“%dn”, ai; 4 5 else 6 for (int i = k; i < n; i+)7 ai = ai + i*i;8 fun(a,n,k+1);9 2. 已知某二叉樹的中序和后序遍歷序列分別為BFDJGACHKEI和FJGDBKHIECA，請畫出該二叉樹，并給出該二叉樹的先序遍歷序列。（8分）3. 對于圖2所示的帶權有向圖，若采

6、用Dijkstra算法求從頂點a到其他頂點的最短路徑和長度，第一條最短路徑為：a->c，路徑長度2，則求得的剩余最短路徑依次是什么？（請按Dijkstra算法執行時產生最短路徑的順序，給出各最短路徑及其長度）。（10分）圖2 一個有向圖 4. 設有一組關鍵字32,13,49,24,38,21,4,12，其哈希函數為：H(key)=key % 7，采用開放地址法的線性探查法解決沖突，試在09的哈希地址空間中對該關鍵字序列構造哈希表，并求等概率下查找成功和查找失敗的平均查找長度。（10分） 5. 有一組關鍵字序列66,89,8,123,9,44,55,37,200,127,98：（1）請將其

7、調整成初始大根堆，并畫出初始大根堆的樹型表示。（5分）（2）采用堆排序實現按關鍵字遞增排序，請畫出當有1個最大的關鍵字已放置到最終位置時，剩余關鍵字構成的大根堆。（5分）三、算法設計題（共計25分）1. 若一元稀疏多項式采用有序單鏈表進行存儲，請給出一元稀疏多項式的存儲結構，并基于此存儲結構設計一個算法用于判斷兩個一元稀疏多項式是否相等。（10分） 2. 假設二叉排序樹采用中序線索鏈表作為存儲結構進行存儲，請寫出該線索鏈表的存儲結構，并編寫算法輸出該二叉排序樹中所有值在a，b之間的關鍵字，其中a < b，二叉排序樹左子樹結點的值小于根結點的值，右子樹結點的值大于根結點的值，樹中沒有關鍵字

8、相重的結點。（15分）“數據結構”考試試題（A）參考答案一、單項選擇題（每小題2分，共30分）15. CDDCA610.ADBBA1115.BBACD二、問答題（共45分）1. 設fun(a,n,k)的執行時間為T1（n,k），則fun(a,n,0)的執行時間為T(n)=T1(n,0)。由fun()算法可知： 則 T(n)=T1(n,0)=n+T1(n,1)=n+(n-1)+T1(n,2) = = n+(n-1)+2+T1(n,n-1) =+n=O(n2)評分說明：過程5分，答案2分。只有正確結果，給2分。2. 二叉樹如下圖所示： 6分 先序遍歷序列為：ABDFGJCEHKI 2分3. 第二條

9、：a->c->f，長度為6 2分第三條：a->c->e，長度為10 2分第四條：a->c->f->d，長度為11 2分第五條：a->c->f->d->g，長度為14 2分第六條：a->b，長度為15 2分4.key321349243821412H(key)46033045最終地址46035178計算次數11113244哈希表如下： 6分0123456789492124323813412 ASL成功=(1+1+1+1+3+2+4+4)/8=17/8 2分ASL失敗=(3+2+1+7+6+5+4)/7=4 2分4. （1）初始

10、大根堆: 5分（2）1個元素放入其最終位置后，剩余元素構成的大根堆： 5分三、算法設計題（25分）1. 一元稀疏多項式采用帶頭結點的有序單鏈表進行存儲，結點的存儲結構如下：3分 typedef struct node int coef; / 系數 int expn； / 指數 struct node *next; PNode;算法如下： 7分void compare(PNode *P1, PNode *P2)/ 多項式按指數遞增的順序進行存儲PNode *P, *Q;P = P1->next; Q = P2->next;while (P!=NULL && Q!=NU

11、LL)if(P->expnQ->expn && P->coef = Q->coef) P=P->next; Q=Q->next; else printf(“多項式不匹配！n”); return; if(P | Q) printf(“多項式不匹配！n”); printf(“多項式匹配！n”); return;2. 解： 二叉排序樹的結點定義如下： 3分 typedef struct Node int data; struct Node *lchild, *rchild; /左右孩子指針 int LTag, RTag; /左右標志，0表示孩子，1表示線索 BSTNode；算法如下： 12分 void report(BSTNode *T, int a, int b) p = T->lchild; / p指向根結點 while (p != T) / 空樹或遍歷結束時，p=T while (p->LTag=0) p = p->lchild; / 尋找第一個結點 if(p->data > a && p->data < b) printf(“%dn”, p->data); while (p->RTag=1 &&am