一、選擇題(30分)
1.下列程序段的時間復(fù)雜度為( )。
for(i=0; i 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.設(shè)順序線性表中有n個數(shù)據(jù)元素,則刪除表中第i個元素需要移動( )個元素。 (A) n-i (B) n+l -i (C) n-1-i (D) i 3.設(shè)F是由T1、T2和T3三棵樹組成的森林,與F對應(yīng)的二叉樹為B,T1、T2和T3的結(jié)點數(shù)分別為N1、N2和N3,則二叉樹B的根結(jié)點的左子樹的結(jié)點數(shù)為( )。 (A) N1-1 (B) N2-1 (C) N2+N3 (D) N1+N3 4.利用直接插入排序法的思想建立一個有序線性表的時間復(fù)雜度為( )。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n) 5.設(shè)指針變量p指向雙向鏈表中結(jié)點A,指針變量s指向被插入的結(jié)點X,則在結(jié)點A的后面插入結(jié)點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.下列各種排序算法中平均時間復(fù)雜度為O(n2)是( )。 (A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 冒泡排序 7.設(shè)輸入序列1、2、3、…、n經(jīng)過棧作用后,輸出序列中的第一個元素是n,則輸出序列中的第i個輸出元素是( )。 (A) n-i (B) n-1-i (C) n+l -i (D) 不能確定 8.設(shè)散列表中有m個存儲單元,散列函數(shù)H(key)= key % p,則p最好選擇( )。 (A) 小于等于m的最大奇數(shù) (B) 小于等于m的最大素數(shù) (C) 小于等于m的最大偶數(shù) (D) 小于等于m的最大合數(shù) 9.設(shè)在一棵度數(shù)為3的樹中,度數(shù)為3的結(jié)點數(shù)有2個,度數(shù)為2的結(jié)點數(shù)有1個,度數(shù)為1的結(jié)點數(shù)有2個,那么度數(shù)為0的結(jié)點數(shù)有( )個。 (A) 4 (B) 5 (C) 6 (D) 7 10.設(shè)完全無向圖中有n個頂點,則該完全無向圖中有( )條邊。 (A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2 11.設(shè)順序表的長度為n,則順序查找的平均比較次數(shù)為( )。 (A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2 12.設(shè)有序表中的元素為(13,18,24,35,47,50,62),則在其中利用二分法查找值為24的元素需要經(jīng)過( )次比較。 (A) 1 (B) 2 (C) 3 (D) 4 13.設(shè)順序線性表的長度為30,分成5塊,每塊6個元素,如果采用分塊查找,則其平均查找長度為( )。 (A) 6 (B) 11 (C) 5 (D) 6.5 14.設(shè)有向無環(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.設(shè)有一組初始記錄關(guān)鍵字序列為(34,76,45,18,26,54,92),則由這組記錄關(guān)鍵字生成的二叉排序樹的深度為( )。 (A) 4 (B) 5 (C) 6 (D) 7 二、填空題(30分) 1. 1. 設(shè)指針p指向單鏈表中結(jié)點A,指針s指向被插入的結(jié)點X,則在結(jié)點A的前面插入結(jié)點X時的操作序列為: 1) s->next=___________;2) p->next=s;3) t=p->data; 4) p->data=___________;5) s->data=t; 2. 2. 設(shè)某棵完全二叉樹中有100個結(jié)點,則該二叉樹中有______________個葉子結(jié)點。 3. 3. 設(shè)某順序循環(huán)隊列中有m個元素,且規(guī)定隊頭指針F指向隊頭元素的前一個位置,隊尾指針R指向隊尾元素的當(dāng)前位置,則該循環(huán)隊列中最多存儲_______隊列元素。 4. 4. 對一組初始關(guān)鍵字序列(40,50,95,20,15,70,60,45,10)進行冒泡排序,則第一趟需要進行相鄰記錄的比較的次數(shù)為__________,在整個排序過程中最多需要進行__________趟排序才可以完成。 5. 5. 在堆排序和快速排序中,如果從平均情況下排序的速度最快的角度來考慮應(yīng)最好選擇_________排序,如果從節(jié)省存儲空間的角度來考慮則最好選擇________排序。 6. 6. 設(shè)一組初始記錄關(guān)鍵字序列為(20,12,42,31,18,14,28),則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長度是_______________________________。 7. 7. 設(shè)一棵二叉樹的中序遍歷序列為BDCA,后序遍歷序列為DBAC,則這棵二叉樹的前序序列為____________________。 8. 8. 設(shè)用于通信的電文僅由8個字母組成,字母在電文中出現(xiàn)的頻率分別為7、19、2、6、32、3、21、10,根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹,則這棵哈夫曼樹的高度為________________。 9. 9. 設(shè)一組記錄關(guān)鍵字序列為(80,70,33,65,24,56,48),則用篩選法建成的初始堆為_______________________。 10. 10. 設(shè)無向圖G(如右圖所示),則其最小生成樹上所有邊的權(quán)值之和為_________________。 三、判斷題(20分) 1. 1. 有向圖的鄰接表和逆鄰接表中表結(jié)點的個數(shù)不一定相等。( ) 2. 2. 對鏈表進行插入和刪除操作時不必移動鏈表中結(jié)點。( ) 3. 3. 子串“ABC”在主串“AABCABCD”中的位置為2。( ) 4. 4. 若一個葉子結(jié)點是某二叉樹的中序遍歷序列的最后一個結(jié)點,則它必是該二叉樹的先序遍歷序列中的最后一個結(jié)點。( ) 5. 5. 希爾排序算法的時間復(fù)雜度為O(n2)。( ) 6. 6. 用鄰接矩陣作為圖的存儲結(jié)構(gòu)時,則其所占用的存儲空間與圖中頂點數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。( ) 7. 7. 中序遍歷一棵二叉排序樹可以得到一個有序的序列。( ) 8. 8. 入棧操作和入隊列操作在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實現(xiàn)時不需要考慮棧溢出的情況。( ) 9. 9. 順序表查找指的是在順序存儲結(jié)構(gòu)上進行查找。( ) 10.10.堆是完全二叉樹,完全二叉樹不一定是堆。( ) 四、算法設(shè)計題(20分) 1. 1. 設(shè)計計算二叉樹中所有結(jié)點值之和的算法。 2. 2. 設(shè)計將所有奇數(shù)移到所有偶數(shù)之前的算法。 3. 3. 設(shè)計判斷單鏈表中元素是否是遞增的算法。 附件: 2015年考研:計算機數(shù)據(jù)結(jié)構(gòu)測試題(二)答案 相關(guān)推薦:
· | 2022考研復(fù)試聯(lián)系導(dǎo)師有哪些注意事 | 04-28 |
· | 2022考研復(fù)試面試常見問題 | 04-28 |
· | 2022年考研復(fù)試面試回答提問方法有 | 04-28 |
· | 2022考研復(fù)試怎么緩解緩解焦慮心態(tài) | 04-27 |
· | 2022年考研復(fù)試的訣竅介紹 | 04-27 |
· | 2022年考研復(fù)試英語如何準(zhǔn)備 | 04-26 |
· | 2022年考研復(fù)試英語口語常見句式 | 04-26 |
· | 2022年考研復(fù)試的四個細節(jié) | 04-26 |
· | 2022考研復(fù)試準(zhǔn)備:與導(dǎo)師及時交流 | 04-26 |
· | 2022考研復(fù)試面試的綜合技巧 | 04-26 |