?數(shù)據(jù)結構自考2017年4月真題
摘要:本試卷為單選題型,填空題,算法閱讀,算法設計等題型。
數(shù)據(jù)結構自考2017年4月真題及答案解析
本試卷為單選題型,填空題,算法閱讀,算法設計等題型。
一、單項選擇題(本大題共15小題,每小題2分,共30分) 在每小題列出的四個備選項中只有一個是符合題目要求的,請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。
1.下列敘述中,不正確的是( )
A.算法解決的只能是數(shù)值計算問題
B.同一問題可以有多種不同算法
C.算法的每一步操作都必須明確無歧義
D.算法必須在執(zhí)行有限步后結束
2.下列關于棧中邏輯上相鄰的兩個數(shù)據(jù)元素的敘述中,正確的是( )
A.順序存儲時不一定相鄰,鏈式存儲時一定相鄰
B.順序存儲時不一定相鄰,鏈式存儲時也不一定相鄰
C.順序存儲時一定相鄰,鏈式存儲時也一定相鄰
D.順序存儲時一定相鄰,鏈式存儲時不一定相鄰
3.對帶頭結點的單循環(huán)鏈表從頭結點開始遍歷(head為頭指針,p=head->next)。若指 針p指向當前被遍歷結點,則判定遍歷過程結束的條件是( )
A.p==NULL
B.head==NULL
C.p==head
D.head !=p
4.設棧的入棧序列為1,2,3,4,5,經(jīng)過入、出棧操作后,可能得到的出棧序列是( )
A.2,3,5,1,4
B.4,2,1,3,5
C.3,4,1,2,5
D.3,4,2,1,5
5.數(shù)組A[2][3]按行優(yōu)先順序存放,A的首地址為10。若A中每個元素占用一個存儲單元,則元素A[1][2]的存儲地址是( )
A.10
B.12
C.14
D.15
6.廣義表((a,b),(c,d))的表尾是( )
A.b
B.d
C.( c, d)
D.((c,d))
7.若完全二叉樹T包含20個終端結點,則T的結點數(shù)最多是( )
A.38
B.39
C.40
D.41
8.對下面的二叉樹進行中序線索化后,結點f的右指針指向的結點是( )
A.a
B.b
C.c
D.e
9.若圖G是一個含有n個頂點的強連通有向圖,則G的邊數(shù)至少是( )
A.n-1
B.n
C.n*(n+1)/2
D.n*(n+1)
10.若從頂點a開始對下圖進行廣度優(yōu)先遍歷,則不可能得到的遍歷序列是( )
A.a,b,c,e,f,d
B.a,c,b,e,f,d
C.a,c,e,b,d,f
D.a,e,b,c,f,d
11.下列排序算法中,穩(wěn)定的是( )
A.堆排序
B.直接選擇排序
C.冒泡排序
D.希爾排序
12.下列排序算法中,比較操作的次數(shù)與待排序序列初始排列狀態(tài)無關的是( )
A.快速排序
B.直接選擇排序
C.冒泡排序
D.直接插入排序
13.若對二叉排序樹進行遍歷,則下列遍歷方式中,其遍歷結果為遞增有序的是( )
A.前序遍歷
B.中序遍歷
C.后序遍歷
D.按層遍歷
14.設一組記錄的關鍵字為{12,22,10,20,88,27,54,11},散列函數(shù)為H(key)=key%11,用拉鏈法解決沖突,則散列地址為0的鏈中結點數(shù)是( )
A.1
B.2
C.3
D.4
15.在下面3階B樹中插入關鍵字65后,其根結點內的關鍵字是( )
A.53 90
B.53
C.90
D.65
二、填空題(本大題共10小題,每小題2分,共20分) 請在每小題的空格中填上正確答案。錯填、不填均無分。
11.散列方法的基本思想是根據(jù)元素的關鍵字直接計算出該元素的________。
12.一個需要頻繁增刪的線性表宜選擇________存儲結構。
13.若中綴表達式為9+(6-2)*8,則相應的后綴表達式是________。
14.對任何一棵二叉樹T,若其葉子結點數(shù)為n0, 度數(shù)為2的結點數(shù)為, 則等于________。
15.若某二叉樹T的前序遍歷序列是A,B,C,D,中序遍歷序列是B,A,D,C,則T的后序遍歷序列是________。
16.在給定n個葉子結點權值且不含度數(shù)為1的結點的所有二叉樹中,其________最小的二叉樹稱為哈夫曼樹。
17.用鄰接表存儲含n個頂點e條邊的有向無環(huán)圖G,對G進行拓撲排序,算法的時間復雜度為________。
18.連通圖G的一個子圖如果是一棵包含G的所有頂點的樹,則該子圖稱為G的________樹。
19.二分查找的速度快效率高,但是它要求表按關鍵字有序并且________。
110.除了問題的規(guī)模和分量個數(shù)之外,還有________是影響基數(shù)排序時間復雜度的主要因素。
三、解答題(本大題共4小題,每小題5分,共20分)
21.對題26圖所示的帶權無向圖G,試回答以下問題。(1)畫出G的最小生成樹;(2)若用克魯斯卡爾( Kruskal)算法求最小生成樹,請按被選中的次序寫出最小生成樹上各條邊的頂點和權值。
22.已知散列表的長度為11,散列函數(shù)為H(key)=key%11,散列表的當前狀態(tài)如下:現(xiàn)要插入關鍵字38,回答下列問題(1)若用線性探查法解決沖突,則38所在位置的下標是什么?(2)若用二次探查法解決沖突,則38所在位置的下標是什么?(3)以上兩種方法中,各需要多少次擦查次數(shù)?
23.試回答下列關于拓撲排序算法的問題。(1)算法中利用一個棧保存入度為0的頂點,其目的是什么?(2)若在算法中將隊列改為棧,相應地將入、出棧及判??詹僮鞲臑槿?、出隊列和判隊列空操作,其他部分不變,是否依然能夠得到拓撲排序的正確結果?
24.考慮用快速排序、堆排序和歸并排序3種排序方法對數(shù)據(jù)序列進行排序,針對下列不同情況,宜分別選擇哪種排序方法?(1)使用盡量少的存儲空間;(2)要求排序結果是穩(wěn)定的;(3)快速找出數(shù)據(jù)序列中關鍵字值較大的若干項。
四、算法閱讀題(本大題共4小題,每小題5分,共20分)
31.設鏈表中結點類型定義如下,閱讀程序,回答下列問題。typedef int DataType;typedef struct node{ DataType data; struct node *next;} RecType, LinkList; int f30( LinkList *head) { if( head ==NULL ) return 0; else return max(head-> data,f30(head->next); //max(ab)返回ab中的較大者}(1)若鏈表L={2,12,16,88,5,10},寫出調用f30(L)的輸出結果;(2)函數(shù)f30的功能是什么?
32.函數(shù)f31的功能是逆序輸出鏈表中所有結點的數(shù)據(jù)域值。請在空白處填充適當?shù)膬热?使其完成指定功能。void f31 LinkList *head){ if( head==NULL ) ___(1)___; else { f31(head->next); printf("%d",___(2)___); }}
33.函數(shù)f32的功能是統(tǒng)計N個頂點的有向圖中邊的數(shù)量,有向圖用鄰接矩陣A表示。閱讀程序,并在空白處填入適當內容,使其完成指定功能。int f32(intAIN) { int i, j; int sum=0; for(i=0; i<N; (3) ) for( ___(2)___ ; j <N;j++) if( ___(3)___ ) sum++; return sun;}
34.已知二叉樹的二叉鏈表類型定義如下:typedef struct node{ char data; struct node * lchild, *rchild; } BiTNode; typedef BiNode BiTree;以下程序為求二叉樹深度的遞歸算法,請?zhí)羁胀昶罩nt depth( Bitree *bt) /*bt為指向根結點的指針*/ { int h1=0, hr =0; if(___(1)___) return (0); h1=depth( bt-> lchild); hr= depth (bt->rchild); if(___(2)___) return (h1+1); else ___(3)___;}
五、算法設計題(本大題共1小題,共10分)
41.已知二叉樹的結點類型定義如下:typedef struct node{ int data; struct node *lchild, *rchild;}BinTNode;typedef BinTNode BinTree;請編寫函數(shù) SearchXNum,計算任意二叉樹T中其數(shù)據(jù)域的值大于或等于x的結點的個數(shù)并返回該值。函數(shù)原型如下: int SearchXNum( Bintree *T, int x);//返回二叉樹T中數(shù)據(jù)域的值大于或等于x的結點的個數(shù)
延伸閱讀
- 2023年10月自考00257票據(jù)法真題
- 2023年10月自考00249國際私法真題
- 2023年10月自考00246國際經(jīng)濟法概論真題
- 2023年10月自考00245刑法學真題
- 2023年10月自考00186國際商務談判真題
- 2023年10月自考00185商品流通概論真題
自考微信公眾號
掃碼添加
自考備考資料免費領取
去領取