下面請(qǐng)看2015年考研：計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)測(cè)試題(五)
一、選擇題(30分)
1. 設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長(zhǎng)度之和為( )。
(A) 20 (B) 30 (C) 40 (D) 45
2.執(zhí)行一趟快速排序能夠得到的序列是( )。
(A) [41，12，34，45，27] 55 [72，63]
(B) [45，34，12，41] 55 [72，63，27]
(C) [63，12，34，45，27] 55 [41，72]
(D) [12，27，45，41] 55 [34，63，72]
3.設(shè)一條單鏈表的頭指針變量為head且該鏈表沒(méi)有頭結(jié)點(diǎn)，則其判空條件是( )。
(A) head==0 (B) head->next==0
(C) head->next==head (D) head!=0
4.時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是( )。
(A) 堆排序 (B) 冒泡排序 (C) 希爾排序 (D) 快速排序
5.設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是( )。
(A) 空或只有一個(gè)結(jié)點(diǎn) (B) 高度等于其結(jié)點(diǎn)數(shù)
(C) 任一結(jié)點(diǎn)無(wú)左孩子 (D) 任一結(jié)點(diǎn)無(wú)右孩子
6.一趟排序結(jié)束后不一定能夠選出一個(gè)元素放在其最終位置上的是( )。
(A) 堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希爾排序
7.設(shè)某棵三叉樹中有40個(gè)結(jié)點(diǎn)，則該三叉樹的最小高度為( )。
(A) 3 (B) 4 (C) 5 (D) 6
8.順序查找不論在順序線性表中還是在鏈?zhǔn)骄�性表中的時(shí)間復(fù)雜度為( )。
(A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)
9.二路歸并排序的時(shí)間復(fù)雜度為( )。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
10. 深度為k的完全二叉樹中最少有( )個(gè)結(jié)點(diǎn)。
(A) 2k-1-1 (B) 2k-1 (C) 2k-1+1 (D) 2k-1
11.設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X，則入隊(duì)列的操作序列為( )。
(A) front->next=s;front=s; (B) s->next=rear;rear=s;
(C) rear->next=s;rear=s; (D) s->next=front;front=s;
12.設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊，則建立該圖鄰接表的時(shí)間復(fù)雜度為( )。
(A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3)
13.設(shè)某哈夫曼樹中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有( )個(gè)葉子結(jié)點(diǎn)。
(A) 99 (B) 100 (C) 101 (D) 102
14.設(shè)二叉排序樹上有n個(gè)結(jié)點(diǎn)，則在二叉排序樹上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為( )。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
15.設(shè)用鄰接矩陣A表示有向圖G的存儲(chǔ)結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為( )。
(A) 第i行非0元素的個(gè)數(shù)之和 (B) 第i列非0元素的個(gè)數(shù)之和
(C) 第i行0元素的個(gè)數(shù)之和 (D) 第i列0元素的個(gè)數(shù)之和
二、判斷題(20分)
1.調(diào)用一次深度優(yōu)先遍歷可以訪問(wèn)到圖中的所有頂點(diǎn)。( )
2.分塊查找的平均查找長(zhǎng)度不僅與索引表的長(zhǎng)度有關(guān)，而且與塊的長(zhǎng)度有關(guān)。( )
3.冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。( )
4.滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。( )
5.設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。( )
6.層次遍歷初始堆可以得到一個(gè)有序的序列。( )
7.設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT，則二叉樹BT中一定沒(méi)有右子樹。( )
8.線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更好。( )
9.中序遍歷二叉排序樹可以得到一個(gè)有序的序列。( )
10.快速排序是排序算法中平均性能最好的一種排序。( )
三、填空題(30分)
1.for(i=1，t=1，s=0;i<=n;i++) {t=t*i;s=s+t;}的時(shí)間復(fù)雜度為_________。
2.設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的新結(jié)點(diǎn)X，則進(jìn)行插入操作的語(yǔ)句序列為__________________________(設(shè)結(jié)點(diǎn)的指針域?yàn)閚ext)。
3.設(shè)有向圖G的二元組形式表示為G =(D，R)，D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，則給出該圖的一種拓?fù)渑判蛐蛄衉_________。
4.設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)，則該無(wú)向圖中每個(gè)頂點(diǎn)的度數(shù)最多是_________。
5.設(shè)二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為50，度數(shù)為1的結(jié)點(diǎn)數(shù)為30，則該二叉樹中總共有_______個(gè)結(jié)點(diǎn)數(shù)。
6.設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，則判斷該循環(huán)隊(duì)列為空的條件為_____________________。
7.設(shè)二叉樹中結(jié)點(diǎn)的兩個(gè)指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_____________________________________________。
8.簡(jiǎn)單選擇排序和直接插入排序算法的平均時(shí)間復(fù)雜度為___________。
9.快速排序算法的空間復(fù)雜度平均情況下為__________，最壞的情況下為__________。
10.散列表中解決沖突的兩種方法是_____________和_____________。
四、算法設(shè)計(jì)題(20分)
1.1. 設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。
2.2. 設(shè)計(jì)判斷二叉樹是否為二叉排序樹的算法。
3.3. 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法
2015年考研：計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)測(cè)試題(五)答案
考研視頻題庫(kù)【手機(jī)題庫(kù)】 | 搜索公眾微信號(hào)"566考研"
相關(guān)推薦：
2015考研招生簡(jiǎn)章專題
2015考研報(bào)考指南:考研深造首選城市TOP10
2015考研：考試吧考研政治智能題庫(kù) ※ 考試吧題庫(kù)
