全國(guó)計(jì)算機(jī)二級(jí)內(nèi)容學(xué)習(xí)(已修改)
2025-07-01 21:02 本頁(yè)面
【正文】 全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法一、基本概念：v 數(shù)據(jù)(Data)：信息的載體，能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的物理符號(hào)。包括文本類型的數(shù)據(jù)(如：字母、數(shù)字、漢字)和多媒體類型的數(shù)據(jù)(如：聲音、動(dòng)畫、圖像)。v 數(shù)據(jù)元素(Data Element)：是數(shù)據(jù)的基本單位，有時(shí)也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄，可以有若干個(gè)數(shù)據(jù)項(xiàng)（字段、域、屬性）組成。v 數(shù)據(jù)結(jié)構(gòu)（Data Structure）：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。其包括三個(gè)部分：邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示。數(shù)據(jù)的運(yùn)算（算法）：即對(duì)數(shù)據(jù)施加的操作v 數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類：線性結(jié)構(gòu)：特征是：若結(jié)構(gòu)是非空集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)最多只有一個(gè)直接前趨和一個(gè)直接后繼。例：一維數(shù)組、鏈表、棧、隊(duì)列、串非線性結(jié)構(gòu)：特征是：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。例：多維數(shù)組、廣義表、樹、圖v 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有以下基本存儲(chǔ)方法：順序存儲(chǔ)方法：該方法是將邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)，一般通過(guò)數(shù)組來(lái)實(shí)現(xiàn)的。鏈接存儲(chǔ)方法：該方法不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。通過(guò)指針類型來(lái)實(shí)現(xiàn)的。索引存儲(chǔ)方法：該方法通常是在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，還建立附加的索引表，索引表中的每一項(xiàng)稱為索引項(xiàng)，索引項(xiàng)的一般形式是：關(guān)鍵字，地址。散列存儲(chǔ)方法：該方法的基本思想是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址，通過(guò)散列函數(shù)實(shí)現(xiàn)。例：除余法散列函數(shù)、相乘取整法散列函數(shù)v 算法的基本特征：可行性(Effectiveness)：針對(duì)實(shí)際問(wèn)題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果。確定性(Definiteness)：算法中的每一個(gè)步驟都必須有明確的定義，不允許出現(xiàn)歧義性。有窮性(Finiteness)：算法必須在有限時(shí)間內(nèi)做完，即必須在執(zhí)行有限個(gè)步驟之后終止。v 時(shí)間復(fù)雜度：該算法執(zhí)行的時(shí)間耗費(fèi)，它是該算法所求解問(wèn)題規(guī)模n的函數(shù)。v 空間復(fù)雜度：該算法執(zhí)行時(shí)所耗費(fèi)的存儲(chǔ)空間，它也是問(wèn)題規(guī)模n的函數(shù)。二、線性表：v 線性表(Linear List)：是由n(n=0)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))a1,a2,a3,,an組成的有限序列。對(duì)于非空的線性表，有且僅有一個(gè)開始結(jié)點(diǎn)a1，它沒有直接前趨；有且僅有一個(gè)終端結(jié)點(diǎn)an，它沒有直接后繼；其余的結(jié)點(diǎn)有且僅有一個(gè)直接前趨結(jié)點(diǎn)和一個(gè)直接后繼結(jié)點(diǎn)。v 線性表的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)(Sequential List)：將線性表的結(jié)點(diǎn)按邏輯次序依次存放在一組地址連續(xù)的存儲(chǔ)單元里，用這種方法存儲(chǔ)的線性表稱為順序表。鏈?zhǔn)酱鎯?chǔ)(Linked List)：邏輯上相鄰的結(jié)點(diǎn)，物理上也相鄰，存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還存儲(chǔ)指向其后繼結(jié)點(diǎn)的地址，用這種方法存儲(chǔ)的線性表稱為鏈表。v 常見的運(yùn)算有：表的初始化、求表的長(zhǎng)度、取表中的第i個(gè)結(jié)點(diǎn)、查找結(jié)點(diǎn)、插入新的結(jié)點(diǎn)、刪除結(jié)點(diǎn)。v 順序表和鏈表的比較：基于空間的考慮：A、順序表的存儲(chǔ)空間是靜態(tài)分配的，而鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的。B、順序表占的存儲(chǔ)空間必須是連續(xù)的，而鏈表占的存儲(chǔ)空間可以是連續(xù)的，也可是不連續(xù)的C、順序表存儲(chǔ)密度為1，而鏈表中的每個(gè)結(jié)點(diǎn)，除了數(shù)據(jù)域外，還要額外的設(shè)置指針域，存儲(chǔ)密度小于1基于時(shí)間的考慮：A、在鏈表中的任何位置上進(jìn)行插入和刪除，只需要修改指針，而順序表中平均將要移動(dòng)近一半的結(jié)點(diǎn)。B、順序表是隨機(jī)存取結(jié)構(gòu)，它的存取時(shí)間為O(1)，而鏈表需從頭結(jié)點(diǎn)順著鏈掃描鏈表。 總之，當(dāng)線性表的長(zhǎng)度變化不大，易于事先確定其大小時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序表作為存儲(chǔ)結(jié)構(gòu)；當(dāng)線性表的長(zhǎng)度變化較大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，以采用鏈表作為存儲(chǔ)結(jié)構(gòu)為好。若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序表做存儲(chǔ)結(jié)構(gòu)為宜；對(duì)于頻繁進(jìn)行插入和刪除的線性表，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。例：關(guān)于線性表的描述中，錯(cuò)誤的是（ ） A、線性表是線性結(jié)構(gòu) B、線性表的順序存儲(chǔ)結(jié)構(gòu)，必須占用一片連續(xù)的存儲(chǔ)單元C、線性表是單鏈表 D、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，不必占用一片連續(xù)的存儲(chǔ)單元用數(shù)組表示線性表的優(yōu)點(diǎn)是（ ）A、便于插入和刪除操作 B、便于隨機(jī)存取C、可以動(dòng)態(tài)地分配存儲(chǔ)空間 D、不需要占用一片連續(xù)的存儲(chǔ)空間三、棧：v 棧(Stack)：是限制僅在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端稱為棧底(Bottom)。當(dāng)表中沒有元素時(shí)稱為空棧。是一種后進(jìn)先出的線性表，又稱為L(zhǎng)IFO表。v 棧的基本運(yùn)算有：棧的初始化、判?？铡⑴袟M、進(jìn)棧、出棧等v 棧的存儲(chǔ)：順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)例：若進(jìn)棧的輸入序列是A、B、C、D、E，并且在它們進(jìn)棧的過(guò)程中可以進(jìn)行出棧操作，則不可能出現(xiàn)的出棧序列是（ ）A、EDCBA B、DECBA C、DCEAB D、ABCDE四、隊(duì)列：v 隊(duì)列(Queue)：也是一種運(yùn)算受限的線性表，它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。允許刪除的一段稱為隊(duì)頭(Front)，允許插入的一段稱為隊(duì)尾(Re
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1