1、.共25套適用于計算機考研數據結構系統練習（PS：其他正在整理，敬請期待）數據結構試卷11一、填空:1. 設需要對5個不同的記錄關鍵字進行排序，則至少需要比較_次，至多需要比較_次。2. 設二叉排序樹的高度為h，則在該樹中查找關鍵字key最多需要比較_次。3. 設在長度為20的有序表中進行二分查找，則比較一次查找成功的結點數有_個，比較兩次查找成功有結點數有_個。4. 數據結構從邏輯上劃分為三種基本類型：_、_和_。5. 在一個具有n個頂點的無向完全圖中，包含有_條邊，在一個具有n個頂點的有向完全圖中，包含有_條邊。6. 向一棵B_樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹比原樹的高

2、度_。7. 在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為_，整個堆排序過程的時間復雜度為_。8. 在快速排序、堆排序、歸并排序中，_排序是穩定的。9. 在有n個葉子結點的哈夫曼樹中，總結點數是_。10. 一棵樹T采用二叉鏈表存儲，如果樹T中某結點為葉子結點，則在二叉鏈表BT中所對應的結點一定_。二、選擇題：1. 隊列的特點是【 】。A 先進后出B 先進先出C 任意位置進出D 前面都不正確2. 有n個記錄的文件，如關鍵字位數為d，基數為r，則基數排序共要進行【 】遍分配與收集。A nB dC rD n - d 3. 在二叉樹結點的先序序列、中序序列和后序序列中，所有葉子結點的先后順序

3、【 】。A 都不相同B 完全相同C 先序和中序相同，而與后序不同D 中序和后序相同，而與先序不同4. 設有198個初始歸并段，如采用K-路平衡歸并三遍完成排序，則K值最大為【 】。A 12B 13C 14D 155. 下面關于廣義表的敘述中，不正確的是【 】。A 廣義表可以是一個多層次的結構B 廣義表至少有一個元素C 廣義表可以被其他廣義表所共享D 廣義表可以是一個遞歸表6. 設二叉樹根結點的層次為0，一棵深度（高度）為k的滿二叉樹和同樣深度完全二叉樹各有f個結點和c個結點，下列關系式不正確的是【 】。A f=cB cfC f=2k+1-aD csk-17. 從L=(apple,pear),(

4、orange,banana)中，取出banana元素的表達式為【 】。A head(tail(L)B head(head(tail(L)C tail(head(tail(L)D head(tail(head(tail(L)8. 下列文件的物理結構中，不利于文件長度動態增長的文件物理結構是【 】。A 順序結構B 鏈接結構 C 索引結構D Hash結構9. 在數據結構中，數據元素可由【 】。A 實體B 域C 數據項D 字段10. 對于有n個頂點的有向圖，由弗洛伊德（FloyD 算法求每一對頂之間的最短路徑的時間復雜度是【 】。A O(1)B O(n)C O(n)D O(n3)三、 計算與算法應用題

5、：1. 已知一個圖的頂點集V和邊集E分別為：V=1,2,3,4,5,6,7;E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;按照普里姆算法從頂點1出發得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。2. 一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來。試求出空格處的內容，并畫出該二叉樹。先序序列： B F ICEH G中序序列：D KFIA EJC 后序序列： K FBHJ G A四、閱讀下列算法，分析它的作用：1. int AA(LN

6、ode *HL , ElemType x) int n=0; LNode *p=HL;while (p!=NULL) if (p-data= =x) n+; p=p-next;return n;對于結點類型為LNode的單鏈表，以上算法的功能為：2. int AA(LNode *HL , ElemType x) int n=0; LNode *p=HL;while (p!=NULL) if (p-data= =x) n+; p=p-next;return n;對于結點類型為LNode的單鏈表，以上算法的功能為：五、 算法設計題：1. 編寫復制一棵二叉樹的非遞歸算法。2. 假設二叉樹中每個結點所

7、含數據元素均為單字母，以二叉鏈表為存儲結構，試編寫算法按如下圖所示的樹狀顯示二叉樹。11. 評卷人12. 得分13.14.答案（PS:后15套較難，有不會的可以我）一、填空題1. 4，102. n3. 1，24. 線性結構，樹型結構，圖型結構5. n(n-1)/2 n(n-1)6. 增加17. O(log2n) O(nlog2n)8. 歸并9. n-110. 左右子樹空二、單項選擇題 1-5 BBBCB 6-10 BDACD三、 計算與算法應用題1.普里姆算法從頂點1出發得到最小生成樹為：(1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)202. 在先

8、序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。四、閱讀下列算法，分析它的作用1. 統計單鏈表中結點的值等于給定值x的結點數。2. 對數組A中的n個元素進行排序，稱為起泡算法。五、算法設計題： 1. 將算法實現函數聲明為二叉樹類的友元函數，可采用層次遍歷的方式進行復制，將已復制的結點進入一個隊列中即可。具體算法實現如下：/ 文件路徑名:exam5alg.h template void CopyBitree(BinaryTree *fromBtPtr, BinaryTree *&toBtPtr)/ 操作結果: 復制二叉樹fromBt到toBt的非遞歸算法if (toBtPt

9、r != NULL) delete toBtPtr;/ 釋放toBtPtrif (fromBtPtr-Empty()/ 空二叉樹toBtPtr = NULL;/ 空二叉樹else/ 非空二叉樹LinkQueueBinTreeNode * fromQ, toQ;/ 隊列BinTreeNode *fromPtr, *toPtr, *fromRoot, *toRoot;fromRoot = fromBtPtr-GetRoot();/ 取出fromBtPtr的根toRoot = new BinTreeNode(fromRoot-data);/ 復制根結點fromQ.InQueue(fromRoot);

10、 toQ.InQueue(toRoot);/ 入隊while (!fromQ.Empty()/ fromQ非空fromQ.OutQueue(fromPtr);/ 出隊 toQ.OutQueue(toPtr);/ 出隊 if (fromPtr-leftChild != NULL)/ 左子樹非空toPtr-leftChild = new BinTreeNode(fromPtr-leftChild-data);/ 復制fromPtr左孩子fromQ.InQueue(fromPtr-leftChild); toQ.InQueue(toPtr-leftChild);/ 入隊if (fromPtr-rig

11、htChild != NULL)/ 右子樹非空 toPtr-rightChild = new BinTreeNode(fromPtr-rightChild-data);/ 復制fromPtr左孩子fromQ.InQueue(fromPtr-rightChild); toQ.InQueue(toPtr-rightChild);/ 入隊toBtPtr = new BinaryTree(toRoot);/ 生成toBtPtr2. 從上圖來看，二叉樹的第一層顯示在第一列，第二層顯示在第二列，第三層顯示在第三列；每行顯示一個結點，從上至下是先顯示右子樹，再顯示根，最后最左子樹，也就是以先遍歷右子樹，最后遍歷左子樹的中序遍歷次序顯示各結點。具體算法實現如下：/ 文件路徑名:exam1alg.h ss ElemTypevoid DisplayHelp(BinTreeNode *r, int level)/ 操作結果：按樹狀形式顯示以r為根的二叉樹，level為層次數，可設根結點的層次數為1if(r != NULL)/ 空樹不顯式，只顯式非空樹DisplayHelp(r-rightChild, level + 1);/ 顯示右子樹cout endl;/ 顯示新行for(int i = 0; i level - 1; i+)cout ;/ 確保在第level列顯示結點