計(jì)算機(jī)考研計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)測(cè)試題(二)

1、2018計(jì)算機(jī)考研：計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)測(cè)試題(二) 2018考研，計(jì)算機(jī)專業(yè)課考試科目為：計(jì)算機(jī)組成原理、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)以及計(jì)算機(jī)網(wǎng)絡(luò)等，需要大家記憶的知識(shí)點(diǎn)有很多，但是不能死機(jī)硬背，還是要理解為主的，融會(huì)貫通才能把題做好，拿到高分，小編就為大家分享計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)測(cè)試題及參考答案，希望計(jì)算機(jī)考研的考生在復(fù)習(xí)之余能夠認(rèn)真做題，鞏固知識(shí)。計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)測(cè)試題(二)一、選擇題(30分)1.下列程序段的時(shí)間復(fù)雜度為( )。for(i=0; i<m; i="0;" p="" style="margin: 0px; padding: 0px;&quo

2、t;>(A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n)2.設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)元素需要移動(dòng)( )個(gè)元素。(A) n-i (B) n+l -i (C) n-1-i (D) i3.設(shè)F是由T1、T2和T3三棵樹組成的森林，與F對(duì)應(yīng)的二叉樹為B，T1、T2和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3，則二叉樹B的根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)數(shù)為( )。(A) N1-1 (B) N2-1 (C) N2+N3 (D) N1+N34.利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為( )。(A) O(n) (B) O(nlog2

3、n) (C) O(n2) (D) O(1og2n)5.設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(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

4、->right=p->right;(D) s->left=p;s->right=p->right;p->right->left=s; p->right=s;6.下列各種排序算法中平均時(shí)間復(fù)雜度為O(n2)是( )。(A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 冒泡排序7.設(shè)輸入序列1、2、3、n經(jīng)過棧作用后，輸出序列中的第一個(gè)元素是n，則輸出序列中的第i個(gè)輸出元素是( )。(A) n-i (B) n-1-i (C) n+l -i (D) 不能確定8.設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)= key % p，則p最好選擇( )

5、。(A) 小于等于m的最大奇數(shù) (B) 小于等于m的最大素?cái)?shù)(C) 小于等于m的最大偶數(shù) (D) 小于等于m的最大合數(shù)9.設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個(gè)，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個(gè)，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個(gè)，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有( )個(gè)。(A) 4 (B) 5 (C) 6 (D) 710.設(shè)完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有( )條邊。(A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/211.設(shè)順序表的長(zhǎng)度為n，則順序查找的平均比較次數(shù)為( )。(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/212.設(shè)有序

6、表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過( )次比較。(A) 1 (B) 2 (C) 3 (D) 413.設(shè)順序線性表的長(zhǎng)度為30，分成5塊，每塊6個(gè)元素，如果采用分塊查找，則其平均查找長(zhǎng)度為( )。(A) 6 (B) 11 (C) 5 (D) 6.514.設(shè)有向無環(huán)圖G中的有向邊集合E=<1，2>，<2，3>，<3，4>，<1，4>，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖? )。(A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，315.設(shè)

7、有一組初始記錄關(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é)點(diǎn)A，指針s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的前面插入結(jié)點(diǎn)X時(shí)的操作序列為：1) s->next=_;2) p->next=s;3) t=p->data;4) p->data=_;5) s->data=t;2. 2. 設(shè)某棵完全二叉樹中有100個(gè)結(jié)點(diǎn)，則該二叉樹中有_個(gè)葉子結(jié)點(diǎn)。3. 3. 設(shè)某順序循環(huán)隊(duì)列中有m個(gè)元素，且規(guī)定隊(duì)頭指針F指向隊(duì)頭元素

8、的前一個(gè)位置，隊(duì)尾指針R指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中最多存儲(chǔ)_隊(duì)列元素。4. 4. 對(duì)一組初始關(guān)鍵字序列(40，50，95，20，15，70，60，45，10)進(jìn)行冒泡排序，則第一趟需要進(jìn)行相鄰記錄的比較的次數(shù)為_，在整個(gè)排序過程中最多需要進(jìn)行_趟排序才可以完成。5. 5. 在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應(yīng)最好選擇_排序，如果從節(jié)省存儲(chǔ)空間的角度來考慮則最好選擇_排序。6. 6. 設(shè)一組初始記錄關(guān)鍵字序列為(20，12，42，31，18，14，28)，則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長(zhǎng)度是_。7. 7. 設(shè)一棵二叉樹的中序遍歷序列為BD

9、CA，后序遍歷序列為DBAC，則這棵二叉樹的前序序列為_。8. 8. 設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(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é)點(diǎn)的個(gè)數(shù)不一定相等。( )2. 2. 對(duì)鏈表進(jìn)行插入和刪除操作時(shí)不必移動(dòng)鏈表中結(jié)點(diǎn)。( )3. 3. 子串“ABC”在

10、主串“AABCABCD”中的位置為2。( )4. 4. 若一個(gè)葉子結(jié)點(diǎn)是某二叉樹的中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的先序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。( )5. 5. 希爾排序算法的時(shí)間復(fù)雜度為O(n2)。( )6. 6. 用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，則其所占用的存儲(chǔ)空間與圖中頂點(diǎn)數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。( )7. 7. 中序遍歷一棵二叉排序樹可以得到一個(gè)有序的序列。( )8. 8. 入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)時(shí)不需要考慮棧溢出的情況。( )9. 9. 順序表查找指的是在順序存儲(chǔ)結(jié)構(gòu)上進(jìn)行查找。( )10.10.堆是完全二叉樹，完全二叉樹不一定是堆。( )四、算法設(shè)計(jì)題

11、(20分)1. 1. 設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。2. 2. 設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。3. 3. 設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)測(cè)試題(二)答案一、選擇題1.A 2.A 3.A 4.C 5.D6.D 7.C 8.B 9.C 10.A11.C 12.C 13.D 14.A 15.A二、填空題1. 1. p->next，s->data2. 2. 503. 3. m-14. 4. 6，85. 5. 快速，堆6. 6. 19/77. 7. CBDA8. 8. 69. 9. (24，65，33，80，70，56，48)10. 10. 8三、判斷題1.錯(cuò) 2.對(duì) 3.對(duì) 4.對(duì) 5.錯(cuò)6.錯(cuò) 7.對(duì) 8.對(duì) 9.錯(cuò) 10.對(duì)四、算法設(shè)計(jì)題1. 1. 設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。void sum(bitree *bt,int &s)if(bt!=0) s=s+bt->data; sum(bt->lchild,s); sum(bt->rchild,s);2. 2. 設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。void quickpass(int r, int s, int t)int i=s,j=t,x=rs;while(iwhile (iwhile (iri=x;3. 3. 設(shè)計(jì)判斷單鏈表中元素是