2023年大連交通大學(xué)計算機科學(xué)與技術(shù)考研初試805考試大綱

考試大綱的內(nèi)容一般包括當(dāng)年全國研究生入學(xué)考試相應(yīng)科目的考試范圍、考試要求、考試形式、試卷結(jié)構(gòu)等信息，對考生備考至關(guān)重要。希賽網(wǎng)整理了2023年大連交通大學(xué)計算機科學(xué)與技術(shù)（081200）考研805數(shù)據(jù)結(jié)構(gòu)考試大綱信息，希望對考生備考有所幫助。

相關(guān)閱讀推薦>>>2021-2022年全國考研復(fù)試線丨2023年全國考試科目匯總丨2023年全國研究方向匯總

（注：以下信息來自學(xué)院官網(wǎng)，僅供參考，具體內(nèi)容以院校發(fā)布為準）

805 數(shù)據(jù)結(jié)構(gòu)一初試考試大綱

科目代碼： 805

科目名稱：數(shù)據(jù)結(jié)構(gòu)

適用專業(yè)：計算機科學(xué)與技術(shù)

考試時間：3小時

考試方式：筆試

總　　分：150分

考試范圍：

一、數(shù)據(jù)結(jié)構(gòu)緒論

理解數(shù)據(jù)結(jié)構(gòu)基本術(shù)語;掌握數(shù)據(jù)結(jié)構(gòu)的定義及研究內(nèi)容;掌握邏輯結(jié)構(gòu)分類及表示、常用存儲結(jié)構(gòu);掌握算法的定義、算法的特性和定量評價標準。

二、線性表

理解線性表的概念及運算的定義;掌握線性表的順序存儲和鏈接存儲方法及常用運算在兩種存儲結(jié)構(gòu)上的實現(xiàn)算法;能夠根據(jù)實際問題的需求來決定采用何種存儲結(jié)構(gòu)并給出具體的算法。

三、棧和隊列

理解棧和隊列的概念及運算特點;掌握棧和隊列的存儲以及運算的實現(xiàn);能夠根據(jù)實際問題的需求來決定采用棧和隊列哪種存儲結(jié)構(gòu)并給出算法。

四、多維數(shù)組和廣義表

理解數(shù)組和廣義表的定義、特點及存儲結(jié)構(gòu);掌握各種壓縮存儲方法;掌握廣義表的運算。

五、樹

理解樹和二叉樹的概念;掌握二叉樹的性質(zhì)、二叉鏈表存儲結(jié)構(gòu)、二叉樹的遍歷運算;掌握哈夫曼樹的構(gòu)建、編碼、譯碼原理;掌握樹和森林與二叉樹的轉(zhuǎn)換方法;能夠針對實際問題利用樹存儲結(jié)構(gòu)設(shè)計算法并給出具體實現(xiàn)。

六、圖

理解圖的基本概念;掌握圖的鄰接矩陣存儲和鄰接表存儲的原理及特點;掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷原理及對應(yīng)生成樹;理解求最小生成樹、拓撲排序、關(guān)鍵路徑和最短路徑的算法原理;能夠根據(jù)圖的基本原理解決一些應(yīng)用問題，如：判定圖的連通性、判定是否有環(huán)等。

七、排序

理解排序的基本概念及常用的排序算法;掌握插入排序、快速排序、選擇排序、歸并排序、基數(shù)排序的基本思想及性能評價;可以利用各種排序算法解決實際問題。

八、查找

理解查找的概念;掌握順序查找、索引查找方法的思想，對數(shù)據(jù)元素和存儲結(jié)構(gòu)的要求;掌握二叉排序樹的定義及構(gòu)造方法、常用運算在其上的實現(xiàn);掌握散列表的定義、解決散列表沖突的方法及散列表創(chuàng)建的方法、查找散列表的方法;掌握各種查找算法平均查找長度的計算;可以利用各種查找算法解決實際問題。

樣 題：

一、單項選擇題(本大題共10小題，每小題2分，共20分)

1、在下列的敘述中，正確的是()

A.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系。

B.數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。

C.在順序存儲結(jié)構(gòu)中，數(shù)據(jù)元素之間的關(guān)系是顯示體現(xiàn)的。

D.鏈接存儲結(jié)構(gòu)是通過結(jié)點的存儲位置相鄰來體現(xiàn)數(shù)據(jù)元素之間的關(guān)系。

2、完成在雙循環(huán)鏈表結(jié)點*p之后插入新結(jié)點*s的操作是()

A. p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;

B. p->next->prior=s; p->next=s; s->prior=p; s->next=p->next;

C. s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;

D. s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;

3、設(shè)一個棧的輸入序列依次是 1，2，3，4，5，元素入棧的過程中允許出棧，則下列序列中，是棧的合法輸出序列的是()

A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 2 1 5 D. 3 5 2 4 1

4、若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3，當(dāng)入隊一個元素，再出隊兩個元素后，rear和front的值分別為()

A. 1和 5 B. 2和4 C. 4和2 D. 5和1

5、樹最適合用來表示()

A.有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素

C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無聯(lián)系的數(shù)據(jù)

6、n個頂點的有向全圖中有向邊的數(shù)目最多為()

A. n-1 B. n C. n(n-1)/2 D. n(n-1)

7、在下面的排序方法中，平均時間復(fù)雜度為O(n2)且是不穩(wěn)定的排序方法為()

A. 快速排序 B. 直接插入排序 C. 直接選擇排序 D. 起泡排序

8、若結(jié)點的存儲地址與其關(guān)鍵字之間存在某種函數(shù)關(guān)系，則稱這種存儲結(jié)構(gòu)為()

A.順序存儲結(jié)構(gòu) B.鏈式存儲結(jié)構(gòu) C.索引存儲結(jié)構(gòu) D.散列存儲結(jié)構(gòu)

9、將長度為m的單循環(huán)鏈表鏈接到長度為n的單循環(huán)鏈表之后，算法的時間復(fù)雜度最好可為()

A. O(n) B. O(1) C.O(m) D.O(m+n)

10、下面程序段的時間復(fù)雜度為()

sum=1;

for (i=0;sum1)

sum+=1;

A. O(n) B. O(1) C.O(01/2) D.O(n2)

二、填空題(本大題共10個空，每空2分，共20分)

1、設(shè)有一個10階的對稱矩陣A，以行優(yōu)先順序存儲下三角元素，其中a00為第一元素，其存儲地址為1，每個元素占一個字節(jié)，則a76的地址為 ;若a11為第一元素，那么a76的地址為 。

2、二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是 。

3、廣義表((a,b),(c,d), e)的表尾是 。

4、 設(shè)無向圖采用鄰接矩陣存儲，則存儲空間的大小只與圖中 的個數(shù)有關(guān)。

5、快速排序、堆排序和歸并排序的平均時間復(fù)雜度都是 ，但其中穩(wěn)定的排序方法只有 。

6、 在動態(tài)查找表中， 既擁有類似折半查找的特性，又采用了鏈表作存儲結(jié)構(gòu)。

7、 順序表和鏈表中能實現(xiàn)隨機存取的是 ，插入、刪除操作效率高的是 。

三、簡答題(本大題共6小題，共80分)

1、(15分)一棵二叉樹的中序、后序遍歷序列分別為： G L D H B E I A C J F K和L G H D I E B J K F C A，請回答：

(1)畫出二叉樹邏輯結(jié)構(gòu)的圖示。

(2)畫出此二叉樹的二叉鏈表存儲結(jié)構(gòu)的圖示并給出C語言描述。

2、(10分)假設(shè)用于通信的電文由字符集{a，b，c，d，e，f，g，h}中的字母構(gòu)成，這8個字母在電文中出現(xiàn)的概率分別為{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}，試為這8個字母進行哈夫曼編碼。請回答：

(1)畫出哈夫曼樹(按根點權(quán)值左小右大的原則)。

(2)寫出依此哈夫曼樹對各個字母的哈夫曼編碼。

(3)求出此哈夫曼樹的帶權(quán)路徑長度WPL。

3、(15分)設(shè)一個有向圖為G=(V,E)，其中V={ v1,v2,v3,v4}，E={< v2,v1>,< v2,v3>,< v4,v1>,< v1,v4>,< v4,v2>}，請回答下列各問：

(1)畫出該有向圖，求出每個頂點的入度和出度。

(2)畫出該圖的鄰接表存儲結(jié)構(gòu)圖示。

(3)對(2)中的鄰接表，給出從頂點v2出發(fā)的DFS序列和DFS生成樹。

(4)對(2)中的鄰接表，給出從頂點v2出發(fā)的BFS序列和BFS生成樹。

4、(10分)給出下列圖的拓撲排序序列，并說明此圖是否為有環(huán)圖，依據(jù)是什么。

5、(15分)設(shè)待排序文件各個記錄的排序碼序列為：19、23、2、67、39、91、43、25，進行堆排序，請回答：

(1)畫出初始建成的大根堆對應(yīng)的完全二叉樹。

(2)寫出初始大根堆序列。

(3)畫出第一趟堆排序后對應(yīng)的完全二叉樹。

6、(15分)設(shè)關(guān)鍵字序列為(71，12，88，53，11，25，65，27，16)，散列函數(shù)為H(key)= key % 7，采用鏈地址法解決沖突。請回答：

(1)畫出散列表示意圖(用頭插法向單鏈表中插入結(jié)點)。

(2)查找關(guān)鍵字32(失敗)時，需要依次與哪些關(guān)鍵字比較。

(3)求等概率下查找成功的平均查找長度ASL。

四、算法設(shè)計(本大題共2小題，每小題15分，共30分)

1、通常稱正讀和反讀都相同的字符序列為“回文”，例如，“abcdeedcba”、 “abcdcba”是回文。若字符序列存儲在一個單鏈表中，編寫算法判斷此字符序列是否為回文。(提示：將一半字符先依次進棧)

2、以二叉鏈表為存儲結(jié)構(gòu)，設(shè)計一個求二叉樹高度的算法。

參考書目

1. 霍利、董靚瑜等. 數(shù)據(jù)結(jié)構(gòu)與算法(C語言版). 清華大學(xué)出版社. 2022年出版. 第1版

數(shù)據(jù)來源：大連交通大學(xué)2023碩士研究生招生初試大綱