數(shù)據(jù)結(jié)構(gòu)考試重點(diǎn)

數(shù)據(jù)結(jié)構(gòu)考試重點(diǎn)數(shù)據(jù)結(jié)構(gòu)考試重點(diǎn)數(shù)據(jù)結(jié)構(gòu)考試重點(diǎn)xxx公司數(shù)據(jù)結(jié)構(gòu)考試重點(diǎn)文件編號(hào)：文件日期：修訂次數(shù)：第1.0次更改批準(zhǔn)審核制定方案設(shè)計(jì)，管理制度數(shù)據(jù)結(jié)構(gòu)第一章緒論1、數(shù)據(jù)結(jié)構(gòu)的定義：按照某種邏輯關(guān)系組織起來(lái)的數(shù)據(jù)集、數(shù)據(jù)與數(shù)據(jù)間的邏輯關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)形式以及定義在數(shù)據(jù)集上的一組操作與操作的實(shí)現(xiàn)這三個(gè)方面統(tǒng)稱為數(shù)據(jù)結(jié)構(gòu)。2、數(shù)據(jù)主要分為兩大類：數(shù)值型數(shù)據(jù)和非數(shù)值類型數(shù)據(jù)。數(shù)值型數(shù)據(jù)主要包括整數(shù)、實(shí)數(shù)和復(fù)數(shù)等；非數(shù)值類型數(shù)據(jù)包括字符、字符串、文字、聲音、圖形、圖像等。3、數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素的集合以及定義在該集合上的數(shù)據(jù)元素之間的一種或多種特定關(guān)系。4、數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)是根據(jù)解決問(wèn)題的功能目標(biāo)而建立的；數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)是根據(jù)解決問(wèn)題的性能要求而建立的。5、數(shù)據(jù)類型是一個(gè)具體相同性質(zhì)的值的集合以及定義在該集合上的一組操作的總稱。數(shù)據(jù)類型定義了數(shù)據(jù)的性質(zhì)、取值范圍以及對(duì)數(shù)據(jù)所能進(jìn)行的一組操作。6、根據(jù)數(shù)據(jù)元素之間邏輯關(guān)系的不同特性，可將數(shù)據(jù)結(jié)構(gòu)分為：集合、線性機(jī)構(gòu)、樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)。7、一個(gè)非空的線性結(jié)構(gòu)的邏輯特點(diǎn)：1.只有一個(gè)數(shù)據(jù)元素沒(méi)有前驅(qū)，稱其為“第一個(gè)”元素；2.只有一個(gè)數(shù)據(jù)元素沒(méi)有后繼，稱其為“最后一個(gè)”元素；3.除第一個(gè)元素外，其余數(shù)據(jù)元素有且只有一個(gè)前驅(qū)；4.除最后一個(gè)元素外，其余數(shù)據(jù)元素有且只有一個(gè)后繼。8、算法是指為解決一個(gè)問(wèn)題而采用的方法和步驟；9、算法的五個(gè)特性：1.有窮性：算法必須在有限步驟及有限時(shí)間內(nèi)終止，并計(jì)算出結(jié)果；2.確定性：算法的每一個(gè)操作步驟都有確切的含義，即無(wú)二義性；3.算法的每一個(gè)操作步驟，都是有效的、可行的；4.輸入：一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定對(duì)象的集合；5.輸出：一個(gè)算法必須有一個(gè)或多個(gè)輸出。算法的目的是為了求解，通過(guò)算法所求得的“解”即是算法的輸出。注意，計(jì)算機(jī)算法的輸出不一定就是計(jì)算機(jī)顯示或打印輸出，一個(gè)算法得到的結(jié)果實(shí)際就是算法的輸出。第二章線性表10、線性表是一種最基本而且應(yīng)用最廣泛的數(shù)據(jù)結(jié)構(gòu)，其特點(diǎn)是結(jié)構(gòu)中的各數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系，是一種最典型的線性結(jié)構(gòu)。11、線性表是具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列。12、線性表中的數(shù)據(jù)元素在位置上是有序的，相鄰的元素之間存在著序偶關(guān)系。13、順序表的順序存儲(chǔ)結(jié)構(gòu)是指把線性表中所有數(shù)據(jù)元素，按照其邏輯順序依次存儲(chǔ)到計(jì)算機(jī)存儲(chǔ)器中從指定位置開(kāi)始的一塊連續(xù)的存儲(chǔ)空間中，數(shù)據(jù)元素間的存儲(chǔ)（物理）位置即表示了它的邏輯位置。14、順序表基本操作的實(shí)現(xiàn)：1.初始化操作；2.求長(zhǎng)度操作；3.判空操作；4.清空操作；5.取元素操作；6.按值查找操作；7.插入操作；8.刪除操作。15、算法的空間效率是指算法在計(jì)算機(jī)上運(yùn)行時(shí)所需存儲(chǔ)空間的大小。算法的空間復(fù)雜度用大O記法表示為：S（n）=O（f（n））隨著問(wèn)題規(guī)模n的增大，算法運(yùn)行時(shí)所需輔助存儲(chǔ)空間的增長(zhǎng)率的數(shù)量級(jí)為f（n）。若算法運(yùn)行時(shí)所占的存儲(chǔ)空間與問(wèn)題規(guī)模無(wú)關(guān)，是個(gè)常量，則稱這種算法為原地工作，其空間復(fù)雜度用O（1）表示。16、順序表的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：a.實(shí)現(xiàn)方法簡(jiǎn)單，各種高級(jí)語(yǔ)言中都有數(shù)組，容易實(shí)現(xiàn)；b.訪問(wèn)元素的速度快，因?yàn)樵陧樞虮碇羞壿嬌舷噜彽膬蓚€(gè)元素在存儲(chǔ)位置上也必定相鄰，所以只要知道了第一個(gè)元素的地址，其他任何一個(gè)元素的地址都可通過(guò)簡(jiǎn)單的計(jì)算求得，故可實(shí)現(xiàn)隨機(jī)存取，即順序表L的第i個(gè)元素即為L(zhǎng).base[i-1]。缺點(diǎn)：a.需占用連續(xù)的存儲(chǔ)區(qū)，存儲(chǔ)要求高，不能利用小塊存儲(chǔ)區(qū)；b.由于在順序表中邏輯上相鄰的兩個(gè)元素在存儲(chǔ)位置上也必定相鄰，所以在進(jìn)行插入和刪除操作時(shí)，需要進(jìn)行大量的元素移動(dòng)操作，影響了算法效率。17、通常把使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的線性表稱為鏈表。18、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元來(lái)存放線性表中的數(shù)據(jù)元素，這組存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的，甚至可以零散分布在內(nèi)存中的任意位置上。19、鏈表的相關(guān)概念：1.首元結(jié)點(diǎn)，指鏈表中用于存儲(chǔ)線性表的第一各數(shù)據(jù)元素的結(jié)點(diǎn)；2.頭結(jié)點(diǎn)，在鏈表中為了便于進(jìn)行插入和刪除等操作，為鏈表增設(shè)一個(gè)輔助結(jié)點(diǎn)，稱該輔助結(jié)點(diǎn)為鏈表的頭結(jié)點(diǎn)。頭結(jié)點(diǎn)在鏈表中可有可無(wú)；3.頭指針，是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針，可以唯一地表示一個(gè)鏈表；4.空指針，當(dāng)鏈表中某個(gè)結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)，稱該結(jié)點(diǎn)的指針域?yàn)榭罩羔槨?0、鏈表的表長(zhǎng)是指鏈表中存放數(shù)據(jù)元素的結(jié)點(diǎn)數(shù)目。21、鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表。22、單鏈表的建立操作：1.頭插法建立單鏈表：在單鏈表的建立過(guò)程中，總是將由讀入元素所生成的結(jié)點(diǎn)插入到鏈表的表首端，即插入時(shí)始終將新生成結(jié)點(diǎn)作為第1個(gè)結(jié)點(diǎn)插入。2.尾插法建立單鏈表：與頭插法正好相反，在單鏈表的建立過(guò)程中，其每次都是將所生成的新結(jié)點(diǎn)插入到單鏈表尾端，即在插入時(shí)始終是新生成結(jié)點(diǎn)作為最后一個(gè)結(jié)點(diǎn)插入。23、鏈表的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：a.能充分利用內(nèi)存中的小塊存儲(chǔ)區(qū)；b.便于進(jìn)行插入和刪除操作，在進(jìn)行插入和刪除操作時(shí)不需要進(jìn)行元素的移動(dòng)，只需修改相應(yīng)結(jié)點(diǎn)的指針域即可。缺點(diǎn)：a.與順序表相比，其實(shí)現(xiàn)方法較復(fù)雜，特別在對(duì)雙鏈表進(jìn)行操作時(shí)不僅要考慮向后指向的“鏈”，還需考慮向前指向的“鏈”；b.無(wú)法像順序表那樣實(shí)現(xiàn)隨機(jī)存取，在鏈表中要找某個(gè)結(jié)點(diǎn)只能從表頭開(kāi)始向后尋找；c.在鏈表的每個(gè)結(jié)點(diǎn)需要附加存儲(chǔ)關(guān)系信息（指針域），因此當(dāng)問(wèn)題規(guī)模較小且基本一定時(shí)，鏈表所需存儲(chǔ)空間比順序表多。第三章棧與隊(duì)列24、棧的定義：棧是一種將插入操作與刪除操作限制在同一段進(jìn)行的特殊線性表。在這個(gè)特殊的線性表中，進(jìn)行插入與刪除操作的一端稱為棧頂（Top），另一端則稱為棧底（Bottom）。也就是說(shuō)棧的插入操作與刪除操作均在棧頂端進(jìn)行，其中，插入操作稱為入棧操作（Push），刪除操作稱為出棧操作（Pop）。不含任何元素的棧稱為空棧。25、棧具有后進(jìn)先出或者說(shuō)為先進(jìn)后出的特性，故棧又稱為后進(jìn)先出表或先進(jìn)后出表。26、棧的基本操作：初始化、銷毀、判空、清空、入棧、出棧、取棧頂、求棧長(zhǎng)及遍歷。27、經(jīng)試探可行則行進(jìn)，不可行則返回重新試探的方法稱為回溯法。28、一個(gè)概念、函數(shù)等對(duì)象用自己來(lái)定義自己，則稱該對(duì)象為遞歸定義的。在程序設(shè)計(jì)語(yǔ)言中，一個(gè)算法直接或間接調(diào)用自己，則稱該算法為遞歸算法。29、遞歸法則：1.基準(zhǔn)情形法則。遞歸定義中的基準(zhǔn)情形即遞歸出口，它本身不再使用遞歸定義，是遞歸的結(jié)束條件；2.不斷推進(jìn)法則。不斷推進(jìn)法則是指在遞歸求解過(guò)程中，每一次遞歸調(diào)用都必須使求解狀況朝接近基準(zhǔn)情形的方向推進(jìn)。30、隊(duì)列是一種插入操作限制在一端進(jìn)行而刪除操作限制在另一端進(jìn)行的特殊線性表。在這個(gè)特殊的線性表中進(jìn)行插入操作的一端成為隊(duì)尾，進(jìn)行刪除操作的一端稱為隊(duì)頭。在隊(duì)列尾端進(jìn)行的插入操作稱為入隊(duì)操作，而在隊(duì)列頭端進(jìn)行的刪除操作稱為出隊(duì)操作。不含任何元素的隊(duì)列稱為空隊(duì)。31、隊(duì)列具有先進(jìn)先出或者說(shuō)后進(jìn)后出的重要特性，故隊(duì)列又稱為先進(jìn)先出表或后進(jìn)后出表。第四章串32、串的定義：串是由零個(gè)或多個(gè)任意字符組成的有限序列，一般記作：S=“s1s2…si…sn”（n≥0）。其中S是串名，用雙引號(hào)括起來(lái)的字符序列為串值，但引號(hào)本身并不屬于串的內(nèi)容，它的作用是為了避免與變量名或數(shù)的常量相混淆。Si（1≤i≤n）稱為串的元素，它可以是任意字母、數(shù)字或者是其他字符，是構(gòu)成串的基本單位，i是它在整個(gè)串中的序號(hào)。n為串的長(zhǎng)度，表示串中所包含的字符個(gè)數(shù)。例如，串S1=“abcd”，串的元素為一個(gè)字母，其長(zhǎng)度為5。而在串S2=“123456”33、串的靜態(tài)順序存儲(chǔ)結(jié)構(gòu)利用的是數(shù)組的靜態(tài)分配方式，它是為每個(gè)定義的字符串分配一個(gè)固定長(zhǎng)度的連續(xù)存儲(chǔ)區(qū)域，將字符串中的字符順序地存放在存儲(chǔ)區(qū)域的各個(gè)單元里。實(shí)質(zhì)上就是將串定義成字符數(shù)組，利用串名可以直接訪問(wèn)串值。用這種表示方式，串的存儲(chǔ)空間在編譯時(shí)確定，其大小不能改變。34、串的動(dòng)態(tài)順序存儲(chǔ)結(jié)構(gòu)仍是為每個(gè)定義的字符串分配一個(gè)連續(xù)存儲(chǔ)區(qū)域，將字符串中的字符順序地存放在這組存儲(chǔ)區(qū)域中的各個(gè)單元里，只是這個(gè)存儲(chǔ)區(qū)域不是在操作前分配的固定長(zhǎng)度的區(qū)域，而是在操作過(guò)程中根據(jù)需要?jiǎng)討B(tài)分配得到的，即在程序運(yùn)行時(shí)為每個(gè)產(chǎn)生的串分配一塊實(shí)際串長(zhǎng)所需的存儲(chǔ)空間，若分配成功，則返回指向該存儲(chǔ)空間起始地址的指針，作為串的基址。第五章數(shù)組和廣義表35、數(shù)組是n個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素a0，a1，…，an-1構(gòu)成的占用一塊地址連續(xù)的內(nèi)存單元的有限序列。數(shù)組中任意一個(gè)元素可以用該元素在數(shù)組中的位置來(lái)表示，數(shù)組元素的位置通常稱作數(shù)組的下標(biāo)。36、在大多數(shù)語(yǔ)言中采用以行序?yàn)橹餍虻拇鎯?chǔ)方式，如C語(yǔ)言、C++語(yǔ)言和Pascal語(yǔ)言；在Fortran等少數(shù)語(yǔ)言中采用以列序?yàn)橹餍虻拇鎯?chǔ)方式。37、常見(jiàn)的特殊矩陣：對(duì)稱矩陣、三角矩陣和帶狀矩陣。對(duì)稱矩陣：在一個(gè)n階方陣A中，若元素滿足下述興致：aij=aji（1≤i，j≤n），則稱A為n階對(duì)稱矩陣。三角矩陣：以主對(duì)角線劃分，n階三角矩陣有n階上三角矩陣和n階下三角矩陣兩種。n階上三角矩陣的下三角（不包括主對(duì)角線）中的元素均為常數(shù)c（或0）。n階下三角矩陣正好相反，它的主對(duì)角線上方均為常數(shù)c（或0）。帶狀矩陣：帶狀矩陣是指所有非零元素均集中在以對(duì)角線為中心的帶狀區(qū)域中的n階方陣。38、常見(jiàn)的稀疏矩陣存儲(chǔ)方法：三元組順序表和十字鏈表。39、三元組順序表：將表示稀疏矩陣非零元素的三元組按行優(yōu)先或列優(yōu)先（一般情況下為行優(yōu)先）的順序排列，并以此存儲(chǔ)在向量中，這種稀疏矩陣的順序存儲(chǔ)結(jié)構(gòu)稱為三元組順序表。40、在廣義表中，每個(gè)結(jié)點(diǎn)既可以屬于基本數(shù)據(jù)類型，也可以屬于廣義表類型。41、廣義表的定義是一個(gè)遞歸定義，它和線性表之間的不同之處在于：數(shù)據(jù)元素之間不僅有先后關(guān)系，更有元素內(nèi)部的層次關(guān)系。42、廣義表的長(zhǎng)度是指表中數(shù)據(jù)元素的個(gè)數(shù)，需要注意的是數(shù)據(jù)元素可能是原子，也可能是子表；廣義表的深度是指表中層次關(guān)系的最大深度，即所含括弧的重?cái)?shù)，需要注意：“原子”深度為0，“空表”的深度為1。43、廣義表的特性：1.廣義表是一個(gè)多層次的結(jié)構(gòu)。表中元素可以是子表，子表的元素還可以是子表；2.廣義表可為其他廣義表所共享。在實(shí)際應(yīng)用中，利用共享特性可以節(jié)約存儲(chǔ)空間來(lái)；3.廣義表可以是一個(gè)遞歸的表。遞歸表的深度是無(wú)窮值，長(zhǎng)度則是有限值。44、廣義表的存儲(chǔ)形式：頭尾鏈表和擴(kuò)展線性鏈表。第六章樹(shù)45、樹(shù)形結(jié)構(gòu)是一種典型的非線性結(jié)構(gòu)，在形狀上類似于自然界中倒立的樹(shù)，所有元素之間具有明顯的層次關(guān)系和分支關(guān)系?，F(xiàn)實(shí)生活中，操作系統(tǒng)的文件管理、家族的族譜關(guān)系和社會(huì)機(jī)構(gòu)的組成等都可以用樹(shù)形象地表示。46、樹(shù)是n（n≥0）個(gè)結(jié)點(diǎn)的有限集。若n=0，稱為空樹(shù)；否則，在任何一棵非空樹(shù)中滿足以下條件：1.有且僅有一個(gè)特定的沒(méi)有前驅(qū)的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；2.當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m（m>0）個(gè)互不相交的有限集合T1，T2，…，Tm。其中每個(gè)集合本身又是一棵樹(shù)，稱為根結(jié)點(diǎn)的子樹(shù)。47、樹(shù)的定義具有遞歸性，即樹(shù)的定義中還有樹(shù)。它刻畫了樹(shù)的固有特性：一棵非空子樹(shù)由一個(gè)根結(jié)點(diǎn)及若干子樹(shù)構(gòu)成，而子樹(shù)又可以由其根結(jié)點(diǎn)和若干棵更小的子樹(shù)構(gòu)成。48、樹(shù)的基本術(shù)語(yǔ)：1.結(jié)點(diǎn)的度和樹(shù)的度；2.孩子、雙親和兄弟；3.結(jié)點(diǎn)的層次和樹(shù)的高度；4.路徑和路徑長(zhǎng)度；5.有序樹(shù)和無(wú)序樹(shù)；6.森林。49、樹(shù)的高度：空樹(shù)的高度為0；在非空樹(shù)中，所有結(jié)點(diǎn)的最大層次稱為樹(shù)的高度（或深度）。50、二叉樹(shù)的概念：二叉樹(shù)是一種重要的樹(shù)形結(jié)構(gòu)，在計(jì)算機(jī)領(lǐng)域有著十分廣泛的應(yīng)用。任何一棵樹(shù)都可以轉(zhuǎn)換成一個(gè)與之對(duì)應(yīng)的二叉樹(shù)，從而對(duì)樹(shù)的表示與處理便可用二叉樹(shù)的表示和相關(guān)運(yùn)算來(lái)實(shí)現(xiàn)。二叉樹(shù)或?yàn)榭諛?shù)，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹(shù)和右子樹(shù)的、互不相交的二叉樹(shù)組成。其特點(diǎn)是它是一棵有序樹(shù)，每個(gè)結(jié)點(diǎn)的度最大為2。51、滿二叉樹(shù)：在一棵二叉樹(shù)中，如果所有分支結(jié)點(diǎn)的度均為2，且所有葉子結(jié)點(diǎn)在同一層上，則這棵二叉樹(shù)稱為滿二叉樹(shù)。52、完全二叉樹(shù)：對(duì)滿二叉樹(shù)從樹(shù)根為1開(kāi)始，按照從上到下、每層從左到右的原則對(duì)其順序編號(hào)。滿二叉樹(shù)是完全二叉樹(shù)的特例。53、二叉樹(shù)的性質(zhì)：1.在二叉樹(shù)的第i層上至少有2i-1個(gè)結(jié)點(diǎn)（i>0）；2.深度為k的二叉樹(shù)上至多含2k-1個(gè)結(jié)點(diǎn)（k≥1）；3.對(duì)任何一棵非空二叉樹(shù)，如果它含有n0個(gè)葉子結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，那么：n0=n2+1；4.具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2n]+1;5.對(duì)有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)編號(hào)后，則對(duì)任意一個(gè)編號(hào)為i的結(jié)點(diǎn)：a.若i=1，則該結(jié)點(diǎn)是二叉樹(shù)的根，無(wú)雙親；否則，其雙親結(jié)點(diǎn)編號(hào)為[i/2]結(jié)點(diǎn);b.若2i>n，則該結(jié)點(diǎn)無(wú)左孩子，否則，編號(hào)為2i的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；c.若2i+1>n，則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)，否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。54、二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)是用一組地址連續(xù)的存儲(chǔ)單元來(lái)存放二叉樹(shù)的數(shù)據(jù)元素。55、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，結(jié)點(diǎn)之間的邏輯關(guān)系是通過(guò)指針實(shí)現(xiàn)的。由于二叉樹(shù)中每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子結(jié)點(diǎn)，所以每個(gè)結(jié)點(diǎn)結(jié)構(gòu)中，除了數(shù)據(jù)域data外，還需要設(shè)置兩個(gè)指針域LChild和RChild，分別指向左孩子和右孩子，這種存儲(chǔ)結(jié)構(gòu)稱為二叉鏈表。56、二叉樹(shù)的二叉鏈表和三叉鏈表的特點(diǎn)：1.它們均由root唯一確定，如二叉樹(shù)為空，則root=NULL；2.具有n個(gè)結(jié)點(diǎn)的二叉鏈表，共有2n個(gè)指針域，其中具有n+1個(gè)空鏈域；3.在三叉鏈表中易于查找某個(gè)結(jié)點(diǎn)的雙親，而在二叉鏈表中則需要遍歷整棵樹(shù)才能查找某結(jié)點(diǎn)的雙親。57、二叉樹(shù)遍歷是按照一定的路徑訪問(wèn)二叉樹(shù)中的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。58、DLR:先序遍歷；LDR:中序遍歷；LRD:后序遍歷。第七章圖59、圖是一種比線性表和樹(shù)