809-數(shù)據(jù)結(jié)構(gòu)-廣東財(cái)經(jīng)大學(xué)2020年研究生招生初試自命題試題真題

1、歡迎報(bào)考廣東財(cái)經(jīng)大學(xué)碩士研究生，祝你考試成功?。ǖ?PAGE 3 頁 共 NUMPAGES 3 頁）PAGE PAGE 3廣東財(cái)經(jīng)大學(xué)碩士研究生入學(xué)考試試卷考試年度：2020年 考試科目代碼及名稱：809-數(shù)據(jù)結(jié)構(gòu)（自命題） 適用專業(yè)：085400電子信息友情提醒：請(qǐng)?jiān)诳键c(diǎn)提供的專用答題紙上答題，答在本卷或草稿紙上無效！單項(xiàng)選擇題（10題，每題2分，共20分）設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)。下面的算法1是將一維數(shù)組a中的n個(gè)數(shù)逆序存放到原數(shù)組中，該算法的空間復(fù)雜度是_（要求用大O符號(hào)表示）。AO(1) BO(n) CO(2n) DO(n2)算法1：for(i=0; in; i+) bi=an-(

2、i+1);for(i=0; in; i+) ai=bi;圖1圖2在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O(1)的操作是_。A訪問第i個(gè)結(jié)點(diǎn)（1=i=n）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)B在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1=i=n）C刪除第i個(gè)結(jié)點(diǎn)（1=iprior-next=p-next; p-next-prior=p-prior; Bp-next=p-next-next; p-next-prior=p; Cp-priort=p-next-next; p-next=p-prior-prior;Dp-prior-next=p; p-prior=p-prior-prior; 最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指

3、針是rear，隊(duì)頭是front，則隊(duì)空的條件是_。A. (rear+1)%n=front B. rear=front Crear+1=front D. (rear-l)%n=front若讓元素1，2，3，4，5依次進(jìn)棧，則出棧次序不可能出現(xiàn)在_種情況。A5，4，3，2，1 B4，3，1，2，5 C2，1，5，4，3 D2，3，5，4，1串“ababaabab”的nextval為_。A010104101 B010102101 C010100011 D010101011 二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以_。A它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ) B它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ) C順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ) D

4、順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用 圖1是一個(gè)有向無環(huán)圖，其拓?fù)渑判蚪Y(jié)果為_。Av0、v1、v2、v4、v5、v3、v6 Bv1、v0、v3、v4、v5、v2、v6Cv1、v0、v3、v4、v5、v6、v2 Dv1、v0、v3、v4、v6、v2、v5在圖2所示AOE網(wǎng)中，其關(guān)鍵路徑長度為_。A16 B17 C18 D19對(duì)一組數(shù)據(jù)(2，12,16,88,5,10)進(jìn)行排序，若前三趟排序結(jié)果如下： 第一趟排序結(jié)果：2，12,16,88,5,10第二趟排序結(jié)果：2,5,16,88,12,10第三趟排序結(jié)果：2,5,10,88,12,16 則采用的排序方法可能_。A希爾排序 B. 快速排序 C.

5、簡單選擇排序 D. 直接插入排序名詞解釋（10題，每題3分，共30分）數(shù)據(jù)結(jié)構(gòu)算法算法的5個(gè)特性算法的時(shí)間復(fù)雜度O(1)棧及其特點(diǎn)遞歸函數(shù)隊(duì)列及其特點(diǎn)串的模式匹配二叉樹的線索化AOE網(wǎng)簡答題（6題，每題10分，共60分）設(shè)一棵二叉樹的先序序列： A B D F C E G H ，中序序列： B F D A G E H C畫出這棵二叉樹； （2）將這棵二叉樹轉(zhuǎn)換成對(duì)應(yīng)的樹（或森林）。字符及其在報(bào)文中出現(xiàn)的頻率如下表：字符CASTE頻率38456利用Huffman樹，為這些字符設(shè)計(jì)一組最優(yōu)二進(jìn)制編碼，要求：（1）請(qǐng)?jiān)诖痤}紙上繪出Huffman樹，并且按Huffman編碼規(guī)則在該樹的每個(gè)分支上標(biāo)上“

6、0”或“1”。為了使答案唯一，請(qǐng)將Huffman樹上每一層結(jié)點(diǎn)的權(quán)值按左小右大排列；（2）并在答題紙上自行繪制和填寫下表；字符CASTEHuffman編碼（3）若接收到1001100，這樣一串Huffman編碼，請(qǐng)寫出其譯碼結(jié)果。（4）計(jì)算其WPL值。已知無向圖G的邏輯結(jié)構(gòu)圖如圖3所示，試回答下述問題。（1）畫出圖G的鄰接矩陣。（2）若從編號(hào)為的頂點(diǎn)出發(fā)遍歷該圖，請(qǐng)畫出其深度優(yōu)先生成樹和廣度優(yōu)先生成樹。針對(duì)圖4所示的無向網(wǎng)：（1）按Kruscal算法生成最小生成樹的過程，畫出各步驟生成的中間圖，并最終得出最小生成樹；（2）求出最小生成樹的代價(jià)。圖3圖4已知哈希函數(shù)為H(key)=key % 1

7、1，哈希表長度為13，用平方探測再散列處理沖突。表中已存放6個(gè)記錄，它們的存儲(chǔ)地址為：addr(22)=0、addr(12)=1、addr(24)=2、addr(32)=10、addr(54)=10沖突，調(diào)整至11、addr(59)=4；其余地址為空。寫出存儲(chǔ)地址計(jì)算式（H0？, Hi？）現(xiàn)有第七個(gè)關(guān)鍵字65，寫出其存儲(chǔ)地址計(jì)算過程（要求寫出每一步的計(jì)算式和沖突處理）。若查找關(guān)鍵字65的記錄，需依次與哪些關(guān)鍵字進(jìn)行比較？若刪除54應(yīng)如何處理？已知一組關(guān)鍵值序列503，87，512，61，908，170，897，275，653，462，試采用堆排序法對(duì)該組序列進(jìn)行降序排序，要求：用二叉樹的形式畫

8、出所建立的初始堆，畫出第一次輸出堆元素后，經(jīng)過篩選調(diào)整之后的堆。算法設(shè)計(jì)與編程(4題，每題10分，共40分)已知順序表的類型定義如下：#define MaxSize typedef struct int *elem; / 存儲(chǔ)空間基址 int length; / 當(dāng)前表長 SqList;設(shè)順序表L中數(shù)據(jù)元素為整型，各個(gè)數(shù)據(jù)元素的值均不相同，試編寫函數(shù)實(shí)現(xiàn)刪除L中值最小的數(shù)據(jù)元素。函數(shù)原型為：DeleteMin_Sq(LinkList &L)請(qǐng)用類C 語言寫出函數(shù)代碼，并且加上適當(dāng)注釋，以增加可讀性。已知二叉鏈表的類型定義如下：typedef struct BitNode TElemType d

9、ata;Struct BiTNode *lchild,*rchild;BiTNode, *BiTree;已知二叉樹 T用二叉鏈表，試用遞歸方法編寫函數(shù)計(jì)算T中葉子結(jié)點(diǎn)的數(shù)目。請(qǐng)用類C 語言寫出函數(shù)代碼，并且加上適當(dāng)注釋，以增加可讀性。已知單鏈表的類型定義如下：typedef struct LNode ElemType data; /數(shù)據(jù)域struct LNode *next;/指針域LNode, *LinkList;設(shè)帶頭結(jié)點(diǎn)的單鏈表L，其數(shù)據(jù)元素非遞減有序，試編寫函數(shù)實(shí)現(xiàn)將數(shù)據(jù)元素e插入L的適當(dāng)位置，以保持該鏈表的依然非遞減有序。函數(shù)原型為：bool InsertOrderList(LinkList &L, ElemType e)請(qǐng)用類C 語言寫出函數(shù)代碼，并且加上適當(dāng)注釋，以增加可讀性。記錄結(jié)構(gòu)定義如下：typedef struct int key ; /關(guān)鍵字域 Infotype otherinfo; /其它域RecordType;記錄依順序存儲(chǔ)結(jié)構(gòu)存放，其類型定義如下：#define MAXSIZE 100 /最大記錄