下面請看2015年考研：計算機數據結構測試題(三)

　　一、選擇題(30分)

　　1. 1. 字符串的長度是指( )。

　　(A) 串中不同字符的個數 (B) 串中不同字母的個數

　　(C) 串中所含字符的個數 (D) 串中不同數字的個數

　　2. 2. 建立一個長度為n的有序單鏈表的時間復雜度為( )

　　(A) O(n) (B) O(1) (C) O(n2) (D) O(log2n)

　　3. 3. 兩個字符串相等的充要條件是( )。

　　(A) 兩個字符串的長度相等 (B) 兩個字符串中對應位置上的字符相等

　　(C) 同時具備(A)和(B)兩個條件 (D) 以上答案都不對

　　4. 4. 設某散列表的長度為100，散列函數H(k)=k % P，則P通常情況下最好選擇( )。

　　(A) 99 (B) 97 (C) 91 (D) 93

　　5. 5. 在二叉排序樹中插入一個關鍵字值的平均時間復雜度為( )。

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

　　6. 6. 設一個順序有序表A[1:14]中有14個元素，則采用二分法查找元素A[4]的過程中比較元素的順序為( )。

　　(A) A[1]，A[2]，A[3]，A[4] (B) A[1]，A[14]，A[7]，A[4]

　　(C) A[7]，A[3]，A[5]，A[4] (D) A[7]，A[5] ，A[3]，A[4]

　　7. 7. 設一棵完全二叉樹中有65個結點，則該完全二叉樹的深度為( )。

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

　　8. 8. 設一棵三叉樹中有2個度數為1的結點，2個度數為2的結點，2個度數為3的結點，則該三叉鏈權中有( )個度數為0的結點。

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

　　9. 9. 設無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為( )。

　　(A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc

　　10. 10. 隊列是一種( )的線性表。

　　(A) 先進先出 (B) 先進后出 (C) 只能插入 (D) 只能刪除

　　二、判斷題(20分)

　　1. 1. 如果兩個關鍵字的值不等但哈希函數值相等，則稱這兩個關鍵字為同義詞。( )

　　2. 2. 設初始記錄關鍵字基本有序，則快速排序算法的時間復雜度為O(nlog2n)。( )

　　3. 3. 分塊查找的基本思想是首先在索引表中進行查找，以便確定給定的關鍵字可能存在的塊號，然后再在相應的塊內進行順序查找。( )

　　4. 4. 二維數組和多維數組均不是特殊的線性結構。( )

　　5. 5. 向二叉排序樹中插入一個結點需要比較的次數可能大于該二叉樹的高度。( )

　　6. 6. 如果某個有向圖的鄰接表中第i條單鏈表為空，則第i個頂點的出度為零。( )

　　7. 7. 非空的雙向循環(huán)鏈表中任何結點的前驅指針均不為空。( )

　　8. 8. 不論線性表采用順序存儲結構還是鏈式存儲結構，刪除值為X的結點的時間復雜度均為O(n)。( )

　　9. 9. 圖的深度優(yōu)先遍歷算法中需要設置一個標志數組，以便區(qū)分圖中的每個頂點是否被訪問過。( )

　　10. 10. 稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。( )

　　三、填空題(30分)

　　1. 1. 設一組初始記錄關鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結束后的結果為_____________________________。

　　2. 2. 下面程序段的功能是實現在二叉排序樹中插入一個新結點，請在下劃線處填上正確的內容。

　　typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree;

　　void bstinsert(bitree *&t,int k)

　　{

　　if (t==0 ) {____________________________;t->data=k;t->lchild=t->rchild=0;}

　　else if (t->data>k) bstinsert(t->lchild,k);else__________________________;

　　}

　　3. 3. 設指針變量p指向單鏈表中結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X需要執(zhí)行的語句序列：s->next=p->next; _________________;。

　　4. 4. 設指針變量head指向雙向鏈表中的頭結點，指針變量p指向雙向鏈表中的第一個結點，則指針變量p和指針變量head之間的關系是p=_________和head=__________(設結點中的兩個指針域分別為llink和rlink)。

　　5. 5. 設某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為__________。

　　6. 6. 完全二叉樹中第5層上最少有__________個結點，最多有_________個結點。

　　7. 7. 設有向圖中不存在有向邊，則其對應的鄰接矩陣A中的數組元素A[i][j]的值等于____________。

　　8. 8. 設一組初始記錄關鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結束后的結果為_____________________________。

　　9. 9. 設連通圖G中有n個頂點e條邊，則對應的最小生成樹上有___________條邊。

　　10. 10. 設有一組初始記錄關鍵字序列為(50，16，23，68，94，70，73)，則將它們調整成初始堆只需把16與___________相互交換即可。

　　四、算法設計題(20分)

　　1. 1. 設計一個在鏈式存儲結構上統(tǒng)計二叉樹中結點個數的算法。

　　2. 2. 設計一個算法將無向圖的鄰接矩陣轉為對應鄰接表的算法。

　　2015年考研：計算機數據結構測試題(三)答案

考研政治題庫【手機題庫】　|　搜索公眾微信號"566考研"

　　相關推薦：

　　2015考研招生簡章專題

　　2015考研專業(yè)課考試科目及題型結構

　　2015考研報考指南:考研深造首選城市TOP10

　　2015考研：考試吧考研政治智能題庫　※　考試吧題庫