點(diǎn)擊查看：2019年考研《計算機數據結構》測試題匯總

　　一、選擇題(30分)

　　1. 設一組權值集合W={2，3，4，5，6}，則由該權值集合構造的哈夫曼樹(shù)中帶權路徑長(cháng)度之和為( )。

　　(A) 20 (B) 30 (C) 40 (D) 45

　　2.執行一趟快速排序能夠得到的序列是( )。

　　(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.設一條單鏈表的頭指針變量為head且該鏈表沒(méi)有頭結點(diǎn)，則其判空條件是( )。

　　(A) head==0 (B) head->next==0

　　(C) head->next==head (D) head!=0

　　4.時(shí)間復雜度不受數據初始狀態(tài)影響而恒為O(nlog2n)的是( )。

　　(A) 堆排序 (B) 冒泡排序 (C) 希爾排序 (D) 快速排序

　　5.設二叉樹(shù)的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹(shù)滿(mǎn)足的條件是( )。

　　(A) 空或只有一個(gè)結點(diǎn) (B) 高度等于其結點(diǎn)數

　　(C) 任一結點(diǎn)無(wú)左孩子 (D) 任一結點(diǎn)無(wú)右孩子

　　6.一趟排序結束后不一定能夠選出一個(gè)元素放在其最終位置上的是( )。

　　(A) 堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希爾排序

　　7.設某棵三叉樹(shù)中有40個(gè)結點(diǎn)，則該三叉樹(shù)的最小高度為( )。

　　(A) 3 (B) 4 (C) 5 (D) 6

　　8.順序查找不論在順序線(xiàn)性表中還是在鏈式線(xiàn)性表中的時(shí)間復雜度為( )。

　　(A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)

　　9.二路歸并排序的時(shí)間復雜度為( )。

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

　　10. 深度為k的完全二叉樹(shù)中最少有( )個(gè)結點(diǎn)。

　　(A) 2k-1-1 (B) 2k-1 (C) 2k-1+1 (D) 2k-1

　　11.設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向將要入隊列的結點(diǎn)X，則入隊列的操作序列為( )。

　　(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.設某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊，則建立該圖鄰接表的時(shí)間復雜度為( )。

　　(A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3)

　　13.設某哈夫曼樹(shù)中有199個(gè)結點(diǎn)，則該哈夫曼樹(shù)中有( )個(gè)葉子結點(diǎn)。

　　(A) 99 (B) 100 (C) 101 (D) 102

　　14.設二叉排序樹(shù)上有n個(gè)結點(diǎn)，則在二叉排序樹(shù)上查找結點(diǎn)的平均時(shí)間復雜度為( )。

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

　　15.設用鄰接矩陣A表示有向圖G的存儲結構，則有向圖G中頂點(diǎn)i的入度為( )。

　　(A) 第i行非0元素的個(gè)數之和 (B) 第i列非0元素的個(gè)數之和

　　(C) 第i行0元素的個(gè)數之和 (D) 第i列0元素的個(gè)數之和

　　二、判斷題(20分)

　　1.調用一次深度優(yōu)先遍歷可以訪(fǎng)問(wèn)到圖中的所有頂點(diǎn)。( )

　　2.分塊查找的平均查找長(cháng)度不僅與索引表的長(cháng)度有關(guān)，而且與塊的長(cháng)度有關(guān)。( )

　　3.冒泡排序在初始關(guān)鍵字序列為逆序的情況下執行的交換次數最多。( )

　　4.滿(mǎn)二叉樹(shù)一定是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿(mǎn)二叉樹(shù)。( )

　　5.設一棵二叉樹(shù)的先序序列和后序序列，則能夠唯一確定出該二叉樹(shù)的形狀。( )

　　6.層次遍歷初始堆可以得到一個(gè)有序的序列。( )

　　7.設一棵樹(shù)T可以轉化成二叉樹(shù)BT，則二叉樹(shù)BT中一定沒(méi)有右子樹(shù)。( )

　　8.線(xiàn)性表的順序存儲結構比鏈式存儲結構更好。( )

　　9.中序遍歷二叉排序樹(shù)可以得到一個(gè)有序的序列。( )

　　10.快速排序是排序算法中平均性能最好的一種排序。( )

　　三、填空題(30分)

　　1.for(i=1，t=1，s=0;i<=n;i++) {t=t*i;s=s+t;}的時(shí)間復雜度為_(kāi)________。

　　2.設指針變量p指向單鏈表中結點(diǎn)A，指針變量s指向被插入的新結點(diǎn)X，則進(jìn)行插入操作的語(yǔ)句序列為_(kāi)_________________________(設結點(diǎn)的指針域為next)。

　　3.設有向圖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>}，則給出該圖的一種拓撲排序序列__________。

　　4.設無(wú)向圖G中有n個(gè)頂點(diǎn)，則該無(wú)向圖中每個(gè)頂點(diǎn)的度數最多是_________。

　　5.設二叉樹(shù)中度數為0的結點(diǎn)數為50，度數為1的結點(diǎn)數為30，則該二叉樹(shù)中總共有_______個(gè)結點(diǎn)數。

　　6.設F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為_(kāi)____________________。

　　7.設二叉樹(shù)中結點(diǎn)的兩個(gè)指針域分別為lchild和rchild，則判斷指針變量p所指向的結點(diǎn)為葉子結點(diǎn)的條件是_____________________________________________。

　　8.簡(jiǎn)單選擇排序和直接插入排序算法的平均時(shí)間復雜度為_(kāi)__________。

　　9.快速排序算法的空間復雜度平均情況下為_(kāi)_________，最壞的情況下為_(kāi)_________。

　　10.散列表中解決沖突的兩種方法是_____________和_____________。

　　四、算法設計題(20分)

　　1. 設計在順序有序表中實(shí)現二分查找的算法。

　　2. 設計判斷二叉樹(shù)是否為二叉排序樹(shù)的算法。

　　3. 在鏈式存儲結構上設計直接插入排序算法

　　相關(guān)推薦：

　　考研歷年真題及答案專(zhuān)題※關(guān)注微信

　　2019考研報考指南※2019考研報名

　　考研萬(wàn)題庫 科學(xué)通過(guò)，懶人必備!