2023年大連交通大學計算機科學與技術考研初試805考試大綱

考試大綱的內容一般包括當年全國研究生入學考試相應科目的考試范圍、考試要求、考試形式、試卷結構等信息，對考生備考至關重要。希賽網整理了2023年大連交通大學計算機科學與技術（081200）考研805數據結構考試大綱信息，希望對考生備考有所幫助。

相關閱讀推薦>>>2021-2022年全國考研復試線丨2023年全國考試科目匯總丨2023年全國研究方向匯總

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

805 數據結構一初試考試大綱

科目代碼： 805

科目名稱：數據結構

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

考試時間：3小時

考試方式：筆試

總　　分：150分

考試范圍：

一、數據結構緒論

理解數據結構基本術語;掌握數據結構的定義及研究內容;掌握邏輯結構分類及表示、常用存儲結構;掌握算法的定義、算法的特性和定量評價標準。

二、線性表

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

三、棧和隊列

理解棧和隊列的概念及運算特點;掌握棧和隊列的存儲以及運算的實現;能夠根據實際問題的需求來決定采用棧和隊列哪種存儲結構并給出算法。

四、多維數組和廣義表

理解數組和廣義表的定義、特點及存儲結構;掌握各種壓縮存儲方法;掌握廣義表的運算。

五、樹

理解樹和二叉樹的概念;掌握二叉樹的性質、二叉鏈表存儲結構、二叉樹的遍歷運算;掌握哈夫曼樹的構建、編碼、譯碼原理;掌握樹和森林與二叉樹的轉換方法;能夠針對實際問題利用樹存儲結構設計算法并給出具體實現。

六、圖

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

七、排序

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

八、查找

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

樣 題：

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

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

A.數據的邏輯結構是指數據的各數據項之間的邏輯關系。

B.數據的物理結構是指數據在計算機內的實際存儲形式。

C.在順序存儲結構中，數據元素之間的關系是顯示體現的。

D.鏈接存儲結構是通過結點的存儲位置相鄰來體現數據元素之間的關系。

2、完成在雙循環(huán)鏈表結點*p之后插入新結點*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、設一個棧的輸入序列依次是 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的數組來實現循環(huán)隊列，且當前rear和front的值分別為0和3，當入隊一個元素，再出隊兩個元素后，rear和front的值分別為()

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

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

A.有序數據元素 B.無序數據元素

C.元素之間具有分支層次關系的數據 D.元素之間無聯系的數據

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

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

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

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

8、若結點的存儲地址與其關鍵字之間存在某種函數關系，則稱這種存儲結構為()

A.順序存儲結構 B.鏈式存儲結構 C.索引存儲結構 D.散列存儲結構

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

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

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

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

2、二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數是 。

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

4、 設無向圖采用鄰接矩陣存儲，則存儲空間的大小只與圖中 的個數有關。

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

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

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

三、簡答題(本大題共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)畫出二叉樹邏輯結構的圖示。

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

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

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

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

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

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

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

(2)畫出該圖的鄰接表存儲結構圖示。

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

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

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

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

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

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

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

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

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

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

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

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

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

2、以二叉鏈表為存儲結構，設計一個求二叉樹高度的算法。

參考書目

1. 霍利、董靚瑜等. 數據結構與算法(C語言版). 清華大學出版社. 2022年出版. 第1版

數據來源：大連交通大學2023碩士研究生招生初試大綱