數(shù)據(jù)結構試題(24253)

1、數(shù)據(jù)結構試題一、選擇題(30分)1.下列程序段的時間復雜度為( )。(A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n)2.設順序線性表中有n個數(shù)據(jù)元素，則刪除表中第i個元素需要移動( )個元素。(A) n-i (B) n+l -i (C) n-1-i (D) i3.設F是由T1、T2和T3三棵樹組成的森林，與F對應的二叉樹為B，T1、T2和T3的結點數(shù)分別為N1、N2和N3，則二叉樹B的根結點的左子樹的結點數(shù)為( )。(A) N1-1 (B) N2-1 (C) N2+N3 (D) N1+N34.利用直接插入排序法的思想建立一個有序線性表的時間

2、復雜度為( )。(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n)5.設指針變量p指向雙向鏈表中結點A，指針變量s指向插入的結點X，則在結點A的后面插入結點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-

3、>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.下列各種排序算法中平均時間復雜度為O(n2)是( )。(A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 冒泡排序7.設輸入序列1、2、3、n經(jīng)過棧作用后，輸出序列中的第一個元素是n，則輸出序列中的第i個輸出元素是( )。(A) n-i (B) n-1-i (C) n+l -i (D) 不能確定8.設散列表中有m個存儲單元，散列

4、函數(shù)H(key)= key % p，則p最好選擇( )。(A) 小于等于m的最大奇數(shù) (B) 小于等于m的最大素數(shù)(C) 小于等于m的最大偶數(shù) (D) 小于等于m的最大合數(shù)9.設在一棵度數(shù)為3的樹中，度數(shù)為3的結點數(shù)有2個，度數(shù)為2的結點數(shù)有1個，度數(shù)為1的結點數(shù)有2個，那么度數(shù)為0的結點數(shù)有( )個。(A) 4 (B) 5 (C) 6 (D) 710.設完全無向圖中有n個頂點，則該完全無向圖中有( )條邊。(A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/211.設順序表的長度為n，則順序查找的平均比較次數(shù)為( )。(A) n (B) n/2 (C

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

6、(C) 1，4，2，3 (D) 1，2，4，315.設有一組初始記錄關鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關鍵字生成的二叉排序樹的深度為( )。(A) 4 (B) 5 (C) 6 (D) 7二、填空題(30分)1.設指針p指向單鏈表中結點A，指針s指向插入的結點X，則在結點A的前面插入結點X時的操作序列為：1) s->next=_;2) p->next=s;3) t=p->data;4) p->data=_;5) s->data=t;2.設某棵完全二叉樹中有100個結點，則該二叉樹中有_個葉子結點。3.設某順序循環(huán)隊列中有m個元素，

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

8、A，后序遍歷序列為DBAC，則這棵二叉樹的前序序列為_。8.設用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、6、32、3、21、10，根據(jù)這些頻率作為權值構造哈夫曼樹，則這棵哈夫曼樹的高度為_。9.設一組記錄關鍵字序列為(80，70，33，65，24，56，48)，則用篩選法建成的初始堆為_。10. 10. 設無向圖G(如右圖所示)，則其最小生成樹上所有邊的權值之和為_。三、判斷題(20分)1.有向圖的鄰接表和逆鄰接表中表結點的個數(shù)不一定相等。( )2.對鏈表進行插入和刪除操作時不必移動鏈表中結點。( )3.子串“ABC”在主串“AABCABCD”中的位置為2。( )4.若一個葉子結點是某二叉樹的中序遍歷序列的最后一個結點，則它必是該二叉樹的先序遍歷序列中的最后一個結點。( )5.希爾排序算法的時間復雜度為O(n2)。( )6.用鄰接矩陣作為圖的存儲結構時，則其所占用的存儲空間與圖中頂點數(shù)無關而與圖中邊數(shù)有關。( )7.中序遍歷一棵二叉排序樹可以得到一個有序的序列。( )8.入棧操作和入隊列操作在鏈式存儲結構上實現(xiàn)時不需要考慮棧溢出的情況。(