首頁 - 網校 - 萬題庫 - 美好明天 - 直播 - 導航
熱點搜索
學員登錄 | 用戶名
密碼
新學員
老學員
您現(xiàn)在的位置: 考試吧 > 考研 > 考研模擬試題 > 考研專業(yè)課模擬試題 > 正文

2019年考研《計算機數(shù)據結構》測試題(5)

2019年考研《計算機數(shù)據結構》測試題(5),更多2019考研信息,請關注考試吧考研網或搜索公眾微信號“萬題庫考研”!

  點擊查看:2019年考研《計算機數(shù)據結構》測試題匯總

  一、選擇題(30分)

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

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

  (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.設二叉樹的先序遍歷序列和后序遍歷序列正好相反,則該二叉樹滿足的條件是( )。

  (A) 空或只有一個結點 (B) 高度等于其結點數(shù)

  (C) 任一結點無左孩子 (D) 任一結點無右孩子

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

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

  7.設某棵三叉樹中有40個結點,則該三叉樹的最小高度為( )。

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

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

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

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

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

  10. 深度為k的完全二叉樹中最少有( )個結點。

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

  11.設指針變量front表示鏈式隊列的隊頭指針,指針變量rear表示鏈式隊列的隊尾指針,指針變量s指向將要入隊列的結點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.設某無向圖中有n個頂點e條邊,則建立該圖鄰接表的時間復雜度為( )。

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

  13.設某哈夫曼樹中有199個結點,則該哈夫曼樹中有( )個葉子結點。

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

  14.設二叉排序樹上有n個結點,則在二叉排序樹上查找結點的平均時間復雜度為( )。

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

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

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

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

  二、判斷題(20分)

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

  2.分塊查找的平均查找長度不僅與索引表的長度有關,而且與塊的長度有關。( )

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

  4.滿二叉樹一定是完全二叉樹,完全二叉樹不一定是滿二叉樹。( )

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

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

  7.設一棵樹T可以轉化成二叉樹BT,則二叉樹BT中一定沒有右子樹。( )

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

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

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

  三、填空題(30分)

  1.for(i=1,t=1,s=0;i<=n;i++) {t=t*i;s=s+t;}的時間復雜度為_________。

  2.設指針變量p指向單鏈表中結點A,指針變量s指向被插入的新結點X,則進行插入操作的語句序列為__________________________(設結點的指針域為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.設無向圖G中有n個頂點,則該無向圖中每個頂點的度數(shù)最多是_________。

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

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

  7.設二叉樹中結點的兩個指針域分別為lchild和rchild,則判斷指針變量p所指向的結點為葉子結點的條件是_____________________________________________。

  8.簡單選擇排序和直接插入排序算法的平均時間復雜度為___________。

  9.快速排序算法的空間復雜度平均情況下為__________,最壞的情況下為__________。

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

  四、算法設計題(20分)

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

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

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

  相關推薦:

  考研歷年真題及答案專題關注微信

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

  考研萬題庫 科學通過,懶人必備!

文章搜索
萬題庫小程序
萬題庫小程序
·章節(jié)視頻 ·章節(jié)練習
·免費真題 ·?荚囶}
微信掃碼,立即獲。
掃碼免費使用
考研英語一
共計364課時
講義已上傳
53214人在學
考研英語二
共計30課時
講義已上傳
5495人在學
考研數(shù)學一
共計71課時
講義已上傳
5100人在學
考研數(shù)學二
共計46課時
講義已上傳
3684人在學
考研數(shù)學三
共計41課時
講義已上傳
4483人在學
推薦使用萬題庫APP學習
掃一掃,下載萬題庫
手機學習,復習效率提升50%!
版權聲明:如果考研網所轉載內容不慎侵犯了您的權益,請與我們聯(lián)系800@exam8.com,我們將會及時處理。如轉載本考研網內容,請注明出處。
官方
微信
掃描關注考研微信
領《大數(shù)據寶典》
下載
APP
下載萬題庫
領精選6套卷
萬題庫
微信小程序
幫助
中心
文章責編:wumeique