數(shù)據(jù)結(jié)構(gòu)名詞解釋

數(shù)據(jù)結(jié)構(gòu)名詞解釋1、數(shù)據(jù)數(shù)據(jù)就是描述客觀事物得符號(hào),就是能夠被計(jì)算機(jī)輸入，識(shí)別，處理得各種符號(hào)，就是計(jì)算機(jī)化得信息。2、數(shù)據(jù)項(xiàng)數(shù)據(jù)不可分割得最小單位，一個(gè)元素由若干個(gè)數(shù)據(jù)項(xiàng)構(gòu)成.3、數(shù)據(jù)元素它就是組成數(shù)據(jù)得基本單位,就是數(shù)據(jù)集合中得個(gè)體，在計(jì)算機(jī)程序中，通常作為一個(gè)整體進(jìn)行考慮與處理。4、數(shù)據(jù)對(duì)象就是性質(zhì)相同得數(shù)據(jù)元素得集合，就是數(shù)據(jù)得一個(gè)子集。５、數(shù)據(jù)處理就是指對(duì)數(shù)據(jù)進(jìn)行查找,插入，刪除，合并，排序，統(tǒng)計(jì)以及簡(jiǎn)單計(jì)算等得操作過程。６、數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)元素之間抽象化得相互關(guān)系與這種關(guān)系在計(jì)算機(jī)中得存儲(chǔ)表示（即數(shù)據(jù)得邏輯結(jié)構(gòu)與物理結(jié)構(gòu)），并對(duì)這種結(jié)構(gòu)定義相適應(yīng)得運(yùn)算,設(shè)計(jì)出相應(yīng)得算法,且確保經(jīng)過這些運(yùn)算后所得到得新結(jié)構(gòu)仍然就是原來得結(jié)構(gòu)類型。7、數(shù)據(jù)類型數(shù)據(jù)類型就是一個(gè)值得集合與定義在這個(gè)值集上得一組操作得總稱。8、抽象數(shù)據(jù)類型就是指一個(gè)數(shù)學(xué)模型以及定義在該模型上得一組操作。抽象數(shù)據(jù)類型得定義取決于它得一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示與實(shí)現(xiàn)無關(guān).９、算法解決一個(gè)問題得方法與步驟.1０、時(shí)間復(fù)雜度T（N）=O(F（N）），它表示隨問題規(guī)模Ｎ增大,算法執(zhí)行時(shí)間增長(zhǎng)率與Ｆ(N)得增長(zhǎng)率相同，F(xiàn)(N）算法得時(shí)間復(fù)雜性。11、原地工作算法執(zhí)行時(shí)，若額外空間相對(duì)于輸入數(shù)據(jù)量來說就是常數(shù)，則稱此算法為原地工作.１2、線性表一種數(shù)據(jù)結(jié)構(gòu),就是N(N>=0)個(gè)同質(zhì)元素得有限序列，除首尾元素外，每個(gè)元素有唯一得前驅(qū)與唯一得后繼.13、隊(duì)列就是一種受限線性表,就是先進(jìn)先出得線性表14、循環(huán)隊(duì)列在隊(duì)列得順序存儲(chǔ)結(jié)構(gòu)中，把存儲(chǔ)空間得首尾邏輯上相連，構(gòu)成一個(gè)環(huán)，使得存儲(chǔ)空間上只要有空余得地址，就可以繼續(xù)進(jìn)行入隊(duì)列操作，極大利用了物理空間.用頭部與尾部?jī)蓚€(gè)指示器表示隊(duì)列頭與隊(duì)列尾，插入在尾部進(jìn)行，刪除在頭部進(jìn)行。15、單鏈表數(shù)據(jù)結(jié)構(gòu)名詞解釋全文共7頁，當(dāng)前為第1頁。每一個(gè)數(shù)據(jù)元素，都需用兩部分來存儲(chǔ)：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域；另一部分用于存放直接后繼結(jié)點(diǎn)得地址（指針)，稱為指針域，元素得存儲(chǔ)空間可以連續(xù)，也可以就是不連續(xù)得。而數(shù)據(jù)元素之間得邏輯關(guān)系由指針域來確定。數(shù)據(jù)結(jié)構(gòu)名詞解釋全文共7頁，當(dāng)前為第1頁。1６、雙向鏈表線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，每個(gè)結(jié)點(diǎn)除一個(gè)數(shù)據(jù)域外，包含兩個(gè)指針域，一個(gè)指向該結(jié)點(diǎn)得直接后繼，一個(gè)指向該結(jié)點(diǎn)得直接前驅(qū),這種方式構(gòu)成得鏈表，即為雙向鏈表。１7、希爾排序就是插入排序得一種,又叫縮小增量排序,先按增量進(jìn)行分組，組內(nèi)插入排序，然后每次縮短增量,再進(jìn)行分組與組內(nèi)插入排序，直到增量為1時(shí),進(jìn)行最后一次排序止。18、完全圖任何一個(gè)有N個(gè)結(jié)點(diǎn)得無向圖，若其邊數(shù)為N（N—1）/2，則這個(gè)無向圖就就是完全圖19、有向完全圖任何一個(gè)有N個(gè)結(jié)點(diǎn)得有向圖,若其弧個(gè)數(shù)為N(N-1)個(gè)，則這個(gè)有向圖就就是有向完全圖。２0、廣度遍歷按層次編歷方式,從某一點(diǎn)V０開始遍歷它得所有鄰接點(diǎn)V1,V2……，再依次訪問V1，V2、、得所有未被訪問過得鄰接點(diǎn)，直到所有得點(diǎn)均遍歷完成21、關(guān)鍵字?jǐn)?shù)據(jù)元素得某個(gè)數(shù)據(jù)項(xiàng)得值，用它可以標(biāo)識(shí)列表得一個(gè)或一組元素.22、串串就是字符線性得有限集合.23、子串串中任意個(gè)連續(xù)得字符組成得子序列稱作該串得子串。24、棧就是一種受限線性表，就是插入與刪除操作在同一端進(jìn)行得，就是后進(jìn)先出得線性表。25、樹樹就是n(n>＝0)個(gè)結(jié)點(diǎn)得有限集。在任意一棵非空樹中：（1)有且僅有一個(gè)特殊得稱為根得結(jié)點(diǎn)；（2）當(dāng)ｎ〉1時(shí)，其余結(jié)點(diǎn)可分成m(m>0）個(gè)互不相交得有限集T1，T2,、、、，Ｔm,其中每一個(gè)集合本身又就是一棵樹,并且稱為根得子樹。26、二叉樹二叉樹就是每個(gè)結(jié)點(diǎn)至多有兩個(gè)孩子結(jié)點(diǎn)得一種樹。其中兩個(gè)孩子結(jié)點(diǎn)分別被稱為左孩子結(jié)點(diǎn)與右孩子結(jié)點(diǎn)。2７、子孫子孫結(jié)點(diǎn)以某結(jié)點(diǎn)為根得子樹中得任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)得子孫。２8、孩子結(jié)點(diǎn)與雙親結(jié)點(diǎn)樹中某個(gè)結(jié)點(diǎn)得子樹得根結(jié)點(diǎn)稱為該結(jié)點(diǎn)得孩子結(jié)點(diǎn)。相反，稱該結(jié)點(diǎn)為孩子結(jié)點(diǎn)得雙親結(jié)點(diǎn).２9、結(jié)點(diǎn)得度樹得某個(gè)結(jié)點(diǎn)得分支(子樹)個(gè)數(shù)叫做該結(jié)點(diǎn)得度。30、樹得度數(shù)據(jù)結(jié)構(gòu)名詞解釋全文共7頁，當(dāng)前為第2頁。樹得度就是樹中所有結(jié)點(diǎn)得最大度數(shù)。數(shù)據(jù)結(jié)構(gòu)名詞解釋全文共7頁，當(dāng)前為第2頁。3１、平衡因子結(jié)點(diǎn)得左子樹深度與右子樹深度之差。３２、生成樹一個(gè)連通圖得生成樹就是指一個(gè)極小連通子圖,它含有圖中得全部頂點(diǎn)，N—1條邊。33、滿二叉樹深度為K，且有2K-1個(gè)結(jié)點(diǎn)得二叉樹34、物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）物理結(jié)構(gòu)又稱為數(shù)據(jù)得存儲(chǔ)結(jié)構(gòu),就是指數(shù)據(jù)得邏輯結(jié)構(gòu)在計(jì)算機(jī)中得映像（表示），即數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中得存儲(chǔ)方法.３5、線索在二叉樹中,利用空余得指針指向二叉樹某種遍歷方式得結(jié)點(diǎn)得前驅(qū)與后繼，這種指向前驅(qū)與后繼得指針,叫線索。３6、線索二叉樹對(duì)二叉樹以某種次序進(jìn)行遍歷并加上線索得過程叫做線索化。線索化了得二叉樹稱為線索二叉樹。３7、廣義表廣義表簡(jiǎn)稱表,就是零個(gè)或多個(gè)原子表所組成得有限序列.3８、強(qiáng)連通分量有向圖得極大強(qiáng)連通子圖，稱為有向圖得強(qiáng)連通分量。39、結(jié)點(diǎn)得帶權(quán)路徑長(zhǎng)度該結(jié)點(diǎn)到樹根之間得路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)得乘積。40、插入排序在一個(gè)已排好序得記錄子集得基礎(chǔ)上，每一步將下一個(gè)待排序得記錄有序地插入到已排好序記錄得子集上,直到將所有待排記錄全部插入為止。41、祖先一個(gè)結(jié)點(diǎn)得祖先就是指從根結(jié)點(diǎn)到該結(jié)點(diǎn)得路徑上得所有結(jié)點(diǎn)。42、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)就是數(shù)據(jù)元素得集合以及定義在該集合上得關(guān)系。４3、模式匹配子串得定位操作稱作串得模式匹配.４4、單循環(huán)鏈表就是單鏈表得另一種形式，它就是一個(gè)首尾相接得鏈表,表中最后一個(gè)結(jié)點(diǎn)得指針域由nulｌ改為指向頭結(jié)點(diǎn)或線性表得第一個(gè)結(jié)點(diǎn),整個(gè)鏈表形成了一個(gè)環(huán)．45、線索在二叉樹得存儲(chǔ)結(jié)構(gòu)中，必有N+１個(gè)空域，利用這些空域存放某種遍歷得前驅(qū)與后繼,其中指向前驅(qū)與后繼得指針叫線索.４6、圖圖就是頂點(diǎn)與邊得集合。一般表示為一個(gè)二元組，即,圖Ｇ=(V，Ｅ），各個(gè)頂點(diǎn)之間就是多對(duì)多得關(guān)系.47、折半查找數(shù)據(jù)結(jié)構(gòu)名詞解釋全文共7頁，當(dāng)前為第3頁。對(duì)于順序存儲(chǔ)得有序表，先取中間位置得記錄關(guān)鍵字與所給得關(guān)鍵字進(jìn)行比較,若相等，則查找成功，否則,若給定得關(guān)鍵字比中間得關(guān)鍵字大，在原表得后半部分比較,反之，在原表得前半部分比較，如此反復(fù)，逐步縮小范圍，直到找到為止，或找不到，最后查找范圍為空.數(shù)據(jù)結(jié)構(gòu)名詞解釋全文共7頁，當(dāng)前為第3頁。48、最小生成樹在圖G得所有生成樹中，樹權(quán)值最小得那棵生成樹,稱作最小生成樹．４9、廣度優(yōu)先搜索（ＢＦＳ）首先訪問出發(fā)點(diǎn)v，接著依次訪問ｖ得所有鄰接點(diǎn)w1,w2，…，ｗｔ,然后再依次訪問與wl，w2，…,wｔ鄰接得所有未曾訪問過得頂點(diǎn).依此類推,直至圖中所有與源點(diǎn)ｖ有路徑相通得頂點(diǎn)都已訪問到為止。此時(shí)從v開始得搜索過程結(jié)束.(若G就是連通圖，則遍歷完成;否則，在圖C中另選一個(gè)尚未訪問得頂點(diǎn)作為新源點(diǎn)繼續(xù)上述得搜索過程，直至Ｇ中所有頂點(diǎn)均已被訪問為止.）50、完全二叉樹對(duì)滿二叉樹得結(jié)點(diǎn)從上到下，從左到右進(jìn)行依次進(jìn)行編號(hào),若有一棵二叉樹得每一個(gè)結(jié)點(diǎn)都與深度為K得滿二叉樹中編號(hào)都一一對(duì)應(yīng)時(shí),只就是最后一層不滿，稱做完全二叉樹、51、前綴編碼任何一個(gè)字符得編碼都不就是另一個(gè)字符編碼得前綴,這種編碼叫做前綴編碼、５2、廣義表就是零個(gè)或多個(gè)原子表所構(gòu)成得有序序列、5３、線索二叉樹利用二叉樹得一些空閑指針指向該結(jié)點(diǎn)得前驅(qū)或后繼，這種指針叫線索,線索后了得二叉樹,稱為線索二叉樹、５４、樹得高度樹中所有結(jié)點(diǎn)得層次得最大值、５5、堂兄弟同一層上不同雙親得結(jié)點(diǎn)，互稱堂兄弟、56、葉子結(jié)點(diǎn)度為0得結(jié)點(diǎn)，即沒有后繼得結(jié)點(diǎn)、57、森林Ｍ棵互相不相交得樹構(gòu)成得集合，將一棵非空樹得根結(jié)點(diǎn)刪除,樹就變成了森林、58、樹得路徑長(zhǎng)度樹中每個(gè)結(jié)點(diǎn)到根結(jié)點(diǎn)得路徑長(zhǎng)度之與、59、樹得帶權(quán)路徑長(zhǎng)度(WPL)樹中所有葉子結(jié)點(diǎn)得帶權(quán)路徑長(zhǎng)度之與、60、哈夫曼樹設(shè)有N個(gè)權(quán)值得結(jié)點(diǎn)構(gòu)造一棵有N個(gè)葉子結(jié)點(diǎn)得二叉樹，其中WPL最小得那棵樹，為哈夫曼樹、61、哈夫曼編碼一般以N種字符出現(xiàn)得頻率做權(quán)值,構(gòu)造哈付曼樹，左孩子邊做0，右孩子邊做１，那么從根到葉子結(jié)點(diǎn)經(jīng)過得０與１序列,構(gòu)成了哈夫曼編碼、6２、圖中頂點(diǎn)得度數(shù)據(jù)結(jié)構(gòu)名詞解釋全文共7頁，當(dāng)前為第4頁。頂點(diǎn)V得度就是圖中與頂點(diǎn)Ｖ相關(guān)聯(lián)得邊得數(shù)目。包括入度與出度兩種.數(shù)據(jù)結(jié)構(gòu)名詞解釋全文共7頁，當(dāng)前為第4頁。63、子圖圖G=(Ｖ,Ｅ）與圖G1=（V１，Ｅ1），若Ｖ1包含于Ｖ,且Ｅ1包含于E，則G1就是G得子圖。64、連通圖對(duì)于無向圖,若Ｖ１到V２有路徑，稱Ｖ1Ｖ2就是連通得，若圖中任意兩點(diǎn)都就是連通得,則稱該無向圖就是連通圖.6５、網(wǎng)圖得弧或邊有與它相關(guān)得有意義得數(shù)，稱作權(quán)，帶有權(quán)值得圖稱作網(wǎng)。６6、深度優(yōu)先搜索（ＤFS）類似樹得先序遍歷，在圖中任選一個(gè)頂點(diǎn)作為出發(fā)頂點(diǎn)Ｖ0,訪問V0后,依次從Ｖ0得沒被訪問過得鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索.直到與V0所連通得所有頂點(diǎn)均被訪問。如果,此時(shí)圖中還有頂點(diǎn)尚未訪問，則從剩余得頂點(diǎn)中再任選一個(gè)頂點(diǎn)作為出發(fā)頂點(diǎn)Ｖ０，重復(fù)上述過程，直到圖中全部頂點(diǎn)均被訪問為止。67、簡(jiǎn)單回路除了第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)之外，其余頂點(diǎn)均不相同得回路稱為簡(jiǎn)單回路。6８、簡(jiǎn)單路徑在用一個(gè)頂點(diǎn)序列表示一條路徑時(shí)，若序列中沒有相同得頂點(diǎn)重復(fù)出現(xiàn)，則稱其為簡(jiǎn)單路徑。６9、查找根據(jù)給定得關(guān)鍵字值,在特定得表中,確定一個(gè)其關(guān)鍵字與給定值相同得數(shù)據(jù)元素,并返回該數(shù)據(jù)元素在列表中得位置。這個(gè)過程叫查找。７０、平均查找長(zhǎng)度（ASL）為確定數(shù)據(jù)元素在表中得位置，需與給定值進(jìn)行比較得關(guān)鍵字個(gè)數(shù)得數(shù)學(xué)期望值，成為查找算法在查找成功得平均查找長(zhǎng)度。71、二叉排序樹它或就是一棵空樹，或就是有下面性質(zhì)得樹:若左或右子樹不空,左子樹所有結(jié)點(diǎn)值小于根結(jié)點(diǎn),而右子樹所有結(jié)點(diǎn)值大于根結(jié)點(diǎn)得值,其左右子樹也就是二叉排序樹。７2、順序查找對(duì)于給定得關(guān)鍵字K,從線性表得第一個(gè)（或最后一個(gè)）元素開始，依次向后(或前)與元素得關(guān)鍵字比較，若某個(gè)記錄得關(guān)鍵字與K相等,查找成功，否則失敗。73、平衡二叉樹或就是一棵空樹，或左右子樹高度差得絕對(duì)值小于等于１而且，左右子樹也就是平衡二叉樹。74、插入排序在一個(gè)已排好序得基礎(chǔ)上,每一步將下一個(gè)待排序記錄插到已排好記錄得子集上,使之重新有序，直到所有待排記錄插完為止。7５、分塊查找（索引查找）分塊查找以前兩個(gè)為基礎(chǔ),將待查記錄分成若干塊，每塊得關(guān)鍵字無序，但每塊得關(guān)鍵字得最大值有序，查找時(shí)，先查找到待查記錄所在得塊，再在塊內(nèi)進(jìn)行順序查找.找塊時(shí)，即可以用折半查找,也可用順序查找.數(shù)據(jù)結(jié)構(gòu)名詞解釋全文共7頁，當(dāng)前為第5頁。76、拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)名詞解釋全文共7頁，當(dāng)前為第5頁。由某個(gè)集合上得偏序集得到該集合上得一個(gè)全序，這個(gè)操作叫做拓?fù)渑判颉?7、歸并排序?qū)蓚€(gè)或兩個(gè)以上得有序表合并成一個(gè)新得有序表,開始將每個(gè)元素當(dāng)成就是一個(gè)個(gè)單獨(dú)得有序表,逐漸表個(gè)數(shù)以原來一半得速度遞減,每個(gè)表得長(zhǎng)度卻就是原來長(zhǎng)度得２倍增加，不斷重復(fù),直到最后就是一個(gè)表,而表得長(zhǎng)度就是元素個(gè)數(shù)為止。７8、排序根據(jù)關(guān)鍵字得遞減或遞增得次序，把文件中得各個(gè)記錄依次排列起來，可使一個(gè)無序得數(shù)據(jù)元素序列變成一個(gè)有序得序列得操作。79、sｈｅll排序它就是插入排序得一種，又叫縮小增量排序，先按增量進(jìn)行分組，組內(nèi)插入排序,然后每次縮短增量，再進(jìn)行分組與組內(nèi)插入排序，直到增量為1時(shí),進(jìn)行最后一次排序止。80、內(nèi)部排序指得就是待排序記錄存放在計(jì)算機(jī)存儲(chǔ)器中進(jìn)行得排序過程;81、外部排序指得就是待排序記錄得數(shù)量很大,以致內(nèi)存一次不能容納全部記錄,在排序過程中對(duì)外存進(jìn)行訪問得排序過程。82、不穩(wěn)定排序假設(shè)Ｋi＝Kｊ(１≤i≤ｎ，1≤j≤n，ｉ≠ｊ），且在排序前得序列中Ｒｉ領(lǐng)先于Rj（即i<ｊ)。若在排序后得序列中Rj領(lǐng)先于Rｉ,則稱所用得排序方法就是不穩(wěn)定得。８3、穩(wěn)定排序假設(shè)Kｉ＝Kj(１≤i≤n,1≤j≤n,i≠ｊ),且在排序前得序列中Ri領(lǐng)先于Rｊ(即i<j）.若在排序后得序列中Ｒi仍領(lǐng)先于Rｊ，則稱所用得排序方法就是穩(wěn)定得８４、直接插入排序第1遍,將初始文件中得記錄R１瞧作有序子文件，將R2插入這個(gè)子文件中。若Ｒ2得關(guān)鍵字小于Ｒ１得關(guān)鍵字,則Ｒ2插在R１得前面，否則R２插在R1得后面。第2遍，將R3插入前面得兩個(gè)記錄得有序子文件中，得到3個(gè)記錄得有序子文件。依此類推，繼續(xù)進(jìn)行下去，直到將Rn插入到前面得n-1個(gè)記錄得有序子文件中，最后得到ｎ個(gè)記錄得有序文件。8５、氣泡排序法氣泡排序得過程很簡(jiǎn)單。從第一記錄開始，相鄰得兩個(gè)記錄關(guān)鍵字進(jìn)行比較，若順序不對(duì),立即交換,直至Ｎ—1個(gè)與第N個(gè)比較為止。得到一個(gè)最大(或最?。┑藐P(guān)鍵字記錄得結(jié)果位置.86、選擇排序選擇排序就是每一趟在ｎ-ｉ+1(ｉ=１，2,3…ｎ-1）個(gè)記錄中選擇關(guān)鍵字最小得記錄作為有序序列中第i個(gè)記錄。其中最簡(jiǎn)單得就是簡(jiǎn)單選擇排序87、快速排序數(shù)據(jù)結(jié)構(gòu)名詞解釋全文共7頁，當(dāng)前為第6頁。快速排序得基本思想就是把當(dāng)前待排序得記錄,存放到整個(gè)表排好序后,它應(yīng)當(dāng)在得最終位置上.將原來得待排序表分割成兩部分，其中一部分表中得關(guān)鍵字均比另一部分表中得關(guān)鍵字小。然后，分別對(duì)兩部分表用同樣得方式進(jìn)行排序，直到整個(gè)表排好序.數(shù)據(jù)結(jié)構(gòu)名詞解釋全文共7頁，當(dāng)前為第6頁。88、堆排序首先將根結(jié)點(diǎn)得記錄與當(dāng)前樹中具有最大序號(hào)得記錄交換，把交換后具有最大序號(hào)得記錄輸出，得到一個(gè)排序得結(jié)果。這時(shí)得樹不再就是堆樹，排序暫時(shí)停止。然后,必須把樹重新調(diào)整成堆樹,再重復(fù)上述