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

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

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

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

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

科目代碼： 805

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

適用專(zhuān)業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)

考試時(shí)間：3小時(shí)

考試方式：筆試

總　　分：150分

考試范圍：

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

理解數(shù)據(jù)結(jié)構(gòu)基本術(shù)語(yǔ);掌握數(shù)據(jù)結(jié)構(gòu)的定義及研究?jī)?nèi)容;掌握邏輯結(jié)構(gòu)分類(lèi)及表示、常用存儲(chǔ)結(jié)構(gòu);掌握算法的定義、算法的特性和定量評(píng)價(jià)標(biāo)準(zhǔn)。

二、線性表

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

三、棧和隊(duì)列

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

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

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

五、樹(shù)

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

六、圖

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

七、排序

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

八、查找

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

樣 題：

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

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

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

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

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

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

2、完成在雙循環(huán)鏈表結(jié)點(diǎn)*p之后插入新結(jié)點(diǎn)*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è)一個(gè)棧的輸入序列依次是 1，2，3，4，5，元素入棧的過(guò)程中允許出棧，則下列序列中，是棧的合法輸出序列的是()

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、若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)入隊(duì)一個(gè)元素，再出隊(duì)兩個(gè)元素后，rear和front的值分別為()

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

5、樹(shù)最適合用來(lái)表示()

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

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

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

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

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

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

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

A.順序存儲(chǔ)結(jié)構(gòu) B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) C.索引存儲(chǔ)結(jié)構(gòu) D.散列存儲(chǔ)結(jié)構(gòu)

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

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

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

sum=1;

for (i=0;sum1)

sum+=1;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)寫(xiě)出依此哈夫曼樹(shù)對(duì)各個(gè)字母的哈夫曼編碼。

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

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

(1)畫(huà)出該有向圖，求出每個(gè)頂點(diǎn)的入度和出度。

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

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

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

4、(10分)給出下列圖的拓?fù)渑判蛐蛄?，并說(shuō)明此圖是否為有環(huán)圖，依據(jù)是什么。

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

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

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

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

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

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

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

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

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

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

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

參考書(shū)目

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

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