華中科技大學(xué)研究生考試軟件工程答案數(shù)據(jù)結(jié)構(gòu)“名詞解釋”部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法分析(已修改)
2024-12-03 00:06 本頁面
【正文】 1 數(shù)據(jù)結(jié)構(gòu) (C 語言版 ) 第一章：緒論 1. 數(shù)據(jù)結(jié)構(gòu) 是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作對象以及它們之間的關(guān)系和操作等的科學(xué)。 2. 數(shù)據(jù) (data)是對客觀事物的符號表示，在計算機(jī)科學(xué)中是指所有以輸入到計算機(jī)中并被計算機(jī)程序處理的符號的總稱。 3. 數(shù)據(jù)元素 (data element)是數(shù)據(jù)的基本單位，在計算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。 4. 數(shù)據(jù)對象 (data object)是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。 5. 數(shù)據(jù)結(jié)構(gòu) (data structure)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的 集合。 6. 根據(jù)數(shù)據(jù)結(jié)構(gòu)之間關(guān)系的不同特性，通常有下列 4 類基本結(jié)構(gòu) :集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。 7. 抽象數(shù)據(jù)類型 (ADT)：是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作，有“數(shù)據(jù)抽象”和“數(shù)據(jù)封裝”兩個重要特性。 8. 算法 (algorithm)是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作，具有“有窮性”，“確定性”，“可行性”，“輸入”，“輸出”五個特性。 9. 算法設(shè)計的要求 ：正確性、可讀性、健壯性、效率與低存儲需求。 10. 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問 題規(guī)模 n 的某個函數(shù) f(n)，算法的時間量度記作 T(n)=O(f(n))，它表示隨問題規(guī)模 n 的增大，算法執(zhí)行時間的增長率和 f(n)的增長率相同，稱做算法的 漸近時間復(fù)雜度 ，簡稱時間復(fù)雜度。 第二章：線性表 1. 線性表 ：是 n 個數(shù)據(jù)元素的有限序列，有順序存儲和鏈?zhǔn)酱鎯煞N表示形式。 2. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 的特點是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，包括兩個域，其中存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，存儲直接后繼存儲位置的域稱為指針域。 3. 循環(huán)鏈表 是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整 個鏈表形成一個環(huán)。 4. 雙向鏈表 是指有兩個指針域，其一指向直接后繼，另一指向直接前趨。 第三章：棧和隊列 1. 棧 是限定僅在表尾進(jìn)行插入或刪除操作的線性表。因此，對棧來說，表尾端有其特殊含義稱為棧頂，相應(yīng)地，表頭端稱為棧底。棧的修改是按后進(jìn)先出的原則進(jìn)行的，因此又稱后進(jìn)先出表。 2. 隊列 是一種先進(jìn)先出的線性表，它只允許在表的一端進(jìn)行插入，而在另一端刪除元素，在隊列中，允許插入的一端稱做隊尾，允許刪除的一端稱做隊頭。 第四章：串 1. 串 (string)是由零個或多個字符組成的有限序列。串中任意個連續(xù)的字符組成的子序列稱該串的子 串，通常稱字符在序列中的序號為該字符在序列中的序號為該字符的在串2 中的位置。 2. 稱兩個串是相等的，當(dāng)且僅當(dāng)這兩個串的值相等。也就是說，只有當(dāng)兩個串的長度相等，并且各個對應(yīng)位置的字符都相等時才相等。 第六章：樹與二叉樹 1. 樹 (tree)是指 n(n=0)個結(jié)點的有限集，在任意一棵非空樹中： 1）有且僅有一個特定的稱為根。 2）當(dāng) n1 時，其余結(jié)點可分為 m(m0)個互不相交的有限集，其中每一個集合本身又是一棵樹。 2. 樹的結(jié)點包含一個數(shù)據(jù)元素及若干指向其子樹的分支。結(jié)點擁有的子樹稱為結(jié)點的 度 。度為 0 的結(jié)點稱為 葉子或終端結(jié)點 。 樹的度 是樹內(nèi)各結(jié)點的度的最大值。結(jié)點的子樹的根稱為該結(jié)點的 孩子 ，相應(yīng)的該結(jié)點稱為孩子的 雙親 。同一個雙親的孩子之間互稱 兄弟 。 結(jié)點的祖先 是從根到該結(jié)點所經(jīng)分支上的所有結(jié)點。反之，以某結(jié)點為根的子樹中的任一結(jié)點都稱為該結(jié)點的 子孫 。 3. 結(jié)點的層次 從根開始定義起，根為
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1