考研真題:廣東財經大學2020年[數據結構]考試真題

2024年1月12日發(作者：教科網)

考研真題：廣東財經大學2020年[數據結構]考試真題一、單項選擇題（10題，每題2分，共20分）1、設n是描述問題規模的非負整數。下面的算法1是將一維數組a中的n個數逆序存放到原數組中，該算法的空間復雜度是________（要求用大O符號表示）。A．O(1)

B．O(n)

C．O(2n)

D．O(n2)算法1：for(i=0; i

b[i]=a[n-(i+1)];for(i=0; i

a[i]=b[i];圖1圖22、在n個結點的順序表中，算法的時間復雜度是O(1)的操作是________。A．訪問第i個結點（1<=i<=n）和求第i個結點的直接前驅B．在第i個結點后插入一個新結點（1<=i<=n）C．刪除第i個結點（1<=i<=n）D．將n個結點從小到大排序3、在雙向鏈表中，刪除結點p的操作是________。A．p->prior->next=p->next; p->next->prior=p->prior;

B．p->next=p->next->next; p->next->prior=p;

C．p->priort=p->next->next; p->next=p->prior->prior;D．p->prior-next=p; p->prior=p->prior->prior;

4、最大容量為n的循環隊列，隊尾指針是rear，隊頭是front，則隊空的條件是________。

A. (rear+1)%n==front

B. rear==front

C．rear+1==front

D. (rear-l)%n==front5、若讓元素1，2，3，4，5依次進棧，則出棧次序不可能出現在________種情況。A．5，4，3，2，1

B．4，3，1，2，5

C．2，1，5，4，3

D．2，3，5，4，16、串“ababaabab”的nextval為_________。A．010104101

B．010102101

C．010100011

D．010101011

7、二叉樹是非線性數據結構，所以_________。A．它不能用順序存儲結構存儲

B．它不能用鏈式存儲結構存儲

C．順序存儲結構和鏈式存儲結構都能存儲

D．順序存儲結構和鏈式存儲結構都不能使用

8、圖1是一個有向無環圖，其拓撲排序結果為________。A．v0、v1、v2、v4、v5、v3、v6

B．v1、v0、v3、v4、v5、v2、v6C．v1、v0、v3、v4、v5、v6、v2

D．v1、v0、v3、v4、v6、v2、v59、在圖2所示AOE網中，其關鍵路徑長度為________。A．16

B．17

C．18

D．1910、對一組數據(2，12,16,88,5,10)進行排序，若前三趟排序結果如下：

第一趟排序結果：2，12,16,88,5,10第二趟排序結果：2,5,16,88,12,10第三趟排序結果：2,5,10,88,12,16則采用的排序方法可能________。A．希爾排序

B. 快速排序

C. 簡單選擇排序

D. 直接插入排序二、名詞解釋（10題，每題3分，共30分）1、數據結構4、算法的時間復雜度O(1)7、隊列及其特點10、AOE網2、算法5、棧及其特點8、串的模式匹配3、算法的5個特性6、遞歸函數9、二叉樹的線索化三、簡答題（6題，每題10分，共60分）1、設一棵二叉樹的先序序列： A B D F C E G H ，中序序列： B F D A G E H C（1）畫出這棵二叉樹； （2）將這棵二叉樹轉換成對應的樹（或森林）。2、字符及其在報文中出現的頻率如下表：

字符頻率C3A8S4T5E6利用Huffman樹，為這些字符設計一組最優二進制編碼，要求：（1）請在答題紙上繪出Huffman樹，并且按Huffman編碼規則在該樹的每個分支上標上“0”或“1”。為了使答案唯一，請將Huffman樹上每一層結點的權值按左小右大排列；（2）并在答題紙上自行繪制和填寫下表；字符Huffman碼（3）若接收到1001100，這樣一串Huffman編碼，請寫出其譯碼結果。（4）計算其WPL值。編CASTE3、已知無向圖G的邏輯結構圖如圖3所示，試回答下述問題。（1）畫出圖G的鄰接矩陣。（2）若從編號為１的頂點出發遍歷該圖，請畫出其深度優先生成樹和廣度優先生成樹。4、針對圖4所示的無向網：（1）按Kruscal算法生成最小生成樹的過程，畫出各步驟生成的中間圖，并最終得出最小生成樹；（2）求出最小生成樹的代價。圖4圖35、已知哈希函數為H(key)=key % 11，哈希表長度為13，用平方探測再散列處理沖突。表中

已存放6個記錄，它們的存儲地址為：addr(22)=0、addr(12)=1、addr(24)=2、addr(32)=10、addr(54)=10沖突，調整至11、addr(59)=4；其余地址為空。（1）寫出存儲地址計算式（H0＝？, Hi＝？）（2）現有第七個關鍵字65，寫出其存儲地址計算過程（要求寫出每一步的計算式和沖突處理）。（3）若查找關鍵字65的記錄，需依次與哪些關鍵字進行比較？（4）若刪除54應如何處理？6、已知一組關鍵值序列{503，87，512，61，908，170，897，275，653，462}，試采用堆排序法對該組序列進行降序排序，要求：（1）用二叉樹的形式畫出所建立的初始堆，（2）畫出第一次輸出堆元素后，經過篩選調整之后的堆。四、算法設計與編程(4題，每題10分，共40分)1、已知順序表的類型定義如下：#define MaxSize <順序表的容量>typedef struct {

int *elem; // 存儲空間基址int length; // 當前表長2、已知二叉鏈表的類型定義如下：typedef struct BitNode {TElemType data;Struct BiTNode *lchild,*rchild;}BiTNode, *BiTree;已知二叉樹 T用二叉鏈表，試用遞歸方法} SqList;設順序表L中數據元素為整型，各個數據元素的編寫函數計算T中葉子結點的數目。請用值均不相同，試編寫函數實現刪除L中值最小的類C 語言寫出函數代碼，并且加上適當數據元素。函數原型為：DeleteMin_Sq(LinkList 注釋，以增加可讀性。&L)請用類C 語言寫出函數代碼，并且加上適當注釋，以增加可讀性。3、已知單鏈表的類型定義如下：typedef struct LNode {

ElemType data; //數據域struct LNode *next;//指針域}LNode, *LinkList;設帶頭結點的單鏈表L，其數據元素非遞減有序，試編寫函數實現將數據元素e插入L的適當位置，以保持該鏈表的依然非遞減有序。函數原型為：bool InrtOrderList(LinkList &L,

ElemType e)請用類C 語言寫出函數代碼，并且加上適當注釋，以增加可讀性。4、記錄結構定義如下：typedef struct{ int key ; //關鍵字域 Infotype otherinfo; //其它域}RecordType;記錄依順序存儲結構存放，其類型定義如下：#define MAXSIZE 100 //最大記錄數

typedef struct{

RecordType [MAXSIZE +1]; //0號單元不存記錄int length;

} SqList;依據冒泡排序思路，編寫實現升序排序的函數，函數原型為：void BubbleSort (Sqlist &L)請用類C 語言寫出函數代碼，適當加上注釋，以增加可讀性。