計算機(jī)考研數(shù)據(jù)結(jié)構(gòu)試卷十一(練習(xí)題含答案)

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

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

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

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

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出發(fā)得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。2. 一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來。試求出空格處的內(nèi)容，并畫出該二叉樹。先序序列： 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;對于結(jié)點類型為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;對于結(jié)點類型為LNode的單鏈表，以上算法的功能為：五、 算法設(shè)計題：1. 編寫復(fù)制一棵二叉樹的非遞歸算法。2. 假設(shè)二叉樹中每個結(jié)點所

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

8、序序列空格中依次填A(yù)DKJ，中序中依次填BHG，后序中依次填DIEC。四、閱讀下列算法，分析它的作用1. 統(tǒng)計單鏈表中結(jié)點的值等于給定值x的結(jié)點數(shù)。2. 對數(shù)組A中的n個元素進(jìn)行排序，稱為起泡算法。五、算法設(shè)計題： 1. 將算法實現(xiàn)函數(shù)聲明為二叉樹類的友元函數(shù)，可采用層次遍歷的方式進(jìn)行復(fù)制，將已復(fù)制的結(jié)點進(jìn)入一個隊列中即可。具體算法實現(xiàn)如下：/ 文件路徑名:exam5alg.h template void CopyBitree(BinaryTree *fromBtPtr, BinaryTree *&toBtPtr)/ 操作結(jié)果: 復(fù)制二叉樹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);/ 復(fù)制根結(jié)點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);/ 復(fù)制fromPtr左孩子fromQ.InQueue(fromPtr-leftChild); toQ.InQueue(toPtr-leftChild);/ 入隊if (fromPtr-rig

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