點(diǎn)擊查看：2019年考研《計算機數據結構》測試題匯總

　　一、選擇題(30分)

　　1.下列程序段的時(shí)間復雜度為( )。

　　for(i=0; i

　　(A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n)

　　2.設順序線(xiàn)性表中有n個(gè)數據元素，則刪除表中第i個(gè)元素需要移動(dòng)( )個(gè)元素。

　　(A) n-i (B) n+l -i (C) n-1-i (D) i

　　3.設F是由T1、T2和T3三棵樹(shù)組成的森林，與F對應的二叉樹(shù)為B，T1、T2和T3的結點(diǎn)數分別為N1、N2和N3，則二叉樹(shù)B的根結點(diǎn)的左子樹(shù)的結點(diǎn)數為( )。

　　(A) N1-1 (B) N2-1 (C) N2+N3 (D) N1+N3

　　4.利用直接插入排序法的思想建立一個(gè)有序線(xiàn)性表的時(shí)間復雜度為( )。

　　(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n)

　　5.設指針變量p指向雙向鏈表中結點(diǎn)A，指針變量s指向被插入的結點(diǎn)X，則在結點(diǎn)A的后面插入結點(diǎn)X的操作序列為( )。

　　(A) p->right=s; s->left=p; p->right->left=s; s->right=p->right;

　　(B) s->left=p;s->right=p->right;p->right=s; p->right->left=s;

　　(C) p->right=s; p->right->left=s; s->left=p; s->right=p->right;

　　(D) s->left=p;s->right=p->right;p->right->left=s; p->right=s;

　　6.下列各種排序算法中平均時(shí)間復雜度為O(n2)是( )。

　　(A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 冒泡排序

　　7.設輸入序列1、2、3、…、n經(jīng)過(guò)棧作用后，輸出序列中的第一個(gè)元素是n，則輸出序列中的第i個(gè)輸出元素是( )。

　　(A) n-i (B) n-1-i (C) n+l -i (D) 不能確定

　　8.設散列表中有m個(gè)存儲單元，散列函數H(key)= key % p，則p最好選擇( )。

　　(A) 小于等于m的最大奇數 (B) 小于等于m的最大素數

　　(C) 小于等于m的最大偶數 (D) 小于等于m的最大合數

　　9.設在一棵度數為3的樹(shù)中，度數為3的結點(diǎn)數有2個(gè)，度數為2的結點(diǎn)數有1個(gè)，度數為1的結點(diǎn)數有2個(gè)，那么度數為0的結點(diǎn)數有( )個(gè)。

　　(A) 4 (B) 5 (C) 6 (D) 7

　　10.設完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中有( )條邊。

　　(A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2

　　11.設順序表的長(cháng)度為n，則順序查找的平均比較次數為( )。

　　(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2

　　12.設有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過(guò)( )次比較。

　　(A) 1 (B) 2 (C) 3 (D) 4

　　13.設順序線(xiàn)性表的長(cháng)度為30，分成5塊，每塊6個(gè)元素，如果采用分塊查找，則其平均查找長(cháng)度為( )。

　　(A) 6 (B) 11 (C) 5 (D) 6.5

　　14.設有向無(wú)環(huán)圖G中的有向邊集合E={<1，2>，<2，3>，<3，4>，<1，4>}，則下列屬于該有向圖G的一種拓撲排序序列的是( )。

　　(A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3

　　15.設有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹(shù)的深度為( )。

　　(A) 4 (B) 5 (C) 6 (D) 7

　　二、填空題(30分)

　　1. 設指針p指向單鏈表中結點(diǎn)A，指針s指向被插入的結點(diǎn)X，則在結點(diǎn)A的前面插入結點(diǎn)X時(shí)的操作序列為：

　　1) s->next=___________;2) p->next=s;3) t=p->data;

　　4) p->data=___________;5) s->data=t;

　　2. 設某棵完全二叉樹(shù)中有100個(gè)結點(diǎn)，則該二叉樹(shù)中有______________個(gè)葉子結點(diǎn)。

　　3. 設某順序循環(huán)隊列中有m個(gè)元素，且規定隊頭指針F指向隊頭元素的前一個(gè)位置，隊尾指針R指向隊尾元素的當前位置，則該循環(huán)隊列中最多存儲_______隊列元素。

　　4. 對一組初始關(guān)鍵字序列(40，50，95，20，15，70，60，45，10)進(jìn)行冒泡排序，則第一趟需要進(jìn)行相鄰記錄的比較的次數為_(kāi)_________，在整個(gè)排序過(guò)程中最多需要進(jìn)行__________趟排序才可以完成。

　　5. 在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來(lái)考慮應最好選擇_________排序，如果從節省存儲空間的角度來(lái)考慮則最好選擇________排序。

　　6. 設一組初始記錄關(guān)鍵字序列為(20，12，42，31，18，14，28)，則根據這些記錄關(guān)鍵字構造的二叉排序樹(shù)的平均查找長(cháng)度是_______________________________。

　　7. 設一棵二叉樹(shù)的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹(shù)的前序序列為_(kāi)___________________。

　　8. 設用于通信的電文僅由8個(gè)字母組成，字母在電文中出現的頻率分別為7、19、2、6、32、3、21、10，根據這些頻率作為權值構造哈夫曼樹(shù)，則這棵哈夫曼樹(shù)的高度為_(kāi)_______________。

　　9. 設一組記錄關(guān)鍵字序列為(80，70，33，65，24，56，48)，則用篩選法建成的初始堆為_(kāi)______________________。

　　10. 設無(wú)向圖G(如右圖所示)，則其最小生成樹(shù)上所有邊的權值之和為_(kāi)________________。

　　三、判斷題(20分)

　　1. 有向圖的鄰接表和逆鄰接表中表結點(diǎn)的個(gè)數不一定相等。( )

　　2. 對鏈表進(jìn)行插入和刪除操作時(shí)不必移動(dòng)鏈表中結點(diǎn)。( )

　　3. 子串“ABC”在主串“AABCABCD”中的位置為2。( )

　　4. 若一個(gè)葉子結點(diǎn)是某二叉樹(shù)的中序遍歷序列的最后一個(gè)結點(diǎn)，則它必是該二叉樹(shù)的先序遍歷序列中的最后一個(gè)結點(diǎn)。( )

　　5. 希爾排序算法的時(shí)間復雜度為O(n2)。( )

　　6. 用鄰接矩陣作為圖的存儲結構時(shí)，則其所占用的存儲空間與圖中頂點(diǎn)數無(wú)關(guān)而與圖中邊數有關(guān)。( )

　　7. 中序遍歷一棵二叉排序樹(shù)可以得到一個(gè)有序的序列。( )

　　8. 入棧操作和入隊列操作在鏈式存儲結構上實(shí)現時(shí)不需要考慮棧溢出的情況。( )

　　9. 順序表查找指的是在順序存儲結構上進(jìn)行查找。( )

　　10.堆是完全二叉樹(shù)，完全二叉樹(shù)不一定是堆。( )

　　四、算法設計題(20分)

　　1. 設計計算二叉樹(shù)中所有結點(diǎn)值之和的算法。

　　2. 設計將所有奇數移到所有偶數之前的算法。

　　3. 設計判斷單鏈表中元素是否是遞增的算法。

　　相關(guān)推薦：

　　考研歷年真題及答案專(zhuān)題※關(guān)注微信

　　2019考研報考指南※2019考研報名

　　考研萬(wàn)題庫 科學(xué)通過(guò)，懶人必備!