面試：數(shù)據(jù)結(jié)構(gòu)

1、數(shù)據(jù)結(jié)構(gòu)2.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種 C 的存儲(chǔ)結(jié)構(gòu)，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種_A_的存儲(chǔ)結(jié)構(gòu)。A隨機(jī)存取 B索引存取 C順序存取 D散列存取3.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址_D_。A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的 C. 一定是不連續(xù)的 D. 連續(xù)或不連續(xù)都可以第一章 數(shù)據(jù)結(jié)構(gòu)與算法一.算法的基本概念計(jì)算機(jī)解題的過程實(shí)際上是在實(shí)施某種算法，這種算法稱為計(jì)算機(jī)算法。1.算法的基本特征：可行性，確定性，有窮性，擁有足夠的情報(bào)。2.算法的基本要素：算法中對(duì)數(shù)據(jù)的運(yùn)算和操作、算法的控制結(jié)構(gòu)。3.算法設(shè)計(jì)的基本方法：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法

2、。4.算法設(shè)計(jì)的要求：正確性、可讀性、健壯性、效率與低存儲(chǔ)量需求二.算法的復(fù)雜度1.算法的時(shí)間復(fù)雜度：指執(zhí)行算法所需要的計(jì)算工作量2.算法的空間復(fù)雜度：執(zhí)行這個(gè)算法所需要的內(nèi)存空間三.數(shù)據(jù)結(jié)構(gòu)的定義1.數(shù)據(jù)的邏輯結(jié)構(gòu)：反映數(shù)據(jù)元素之間的關(guān)系的數(shù)據(jù)元素集合的表示。數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、線形結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)四種。2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間種的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。常用的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。四.數(shù)據(jù)結(jié)構(gòu)的圖形表示：在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；沒有后件的結(jié)點(diǎn)成為終端結(jié)點(diǎn)。插入和刪除是對(duì)數(shù)據(jù)結(jié)構(gòu)的兩種基本運(yùn)算。還有查找、分類、合并、分

3、解、復(fù)制和修改等。第二章 線性表五.線性結(jié)構(gòu)和非線性結(jié)構(gòu) 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)：非空數(shù)據(jù)結(jié)構(gòu)滿足：有且只有一個(gè)根結(jié)點(diǎn)；每個(gè)結(jié)點(diǎn)最多有一個(gè)前件，最多只有一個(gè)后件。非線性結(jié)構(gòu)：如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，稱之為非線性結(jié)構(gòu)。常見的線性結(jié)構(gòu)：線性表、棧、隊(duì)列六.線性表的定義線性表是n 個(gè)元素構(gòu)成的有限序列（A1，A2，A3）。表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)以外，有且只有一個(gè)前件。除了最后一個(gè)以外有且只有一個(gè)后件。即線性表是一個(gè)空表，或可以表示為（a1,a2,an）, 其中ai(I=1,2,n)是屬于數(shù)據(jù)對(duì)象的元

4、素，通常也稱其為線性表中的一個(gè)結(jié)點(diǎn)。非空線性表有如下一些特征：（1）有且只有一個(gè)根結(jié)點(diǎn)a1,它無前件；（2）有且只有一個(gè)終端結(jié)點(diǎn)an，它無后件；（3）除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。線性表中結(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長(zhǎng)度。當(dāng)n=0時(shí)稱為空表。七.線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序表指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。線性表的順序存儲(chǔ)結(jié)構(gòu)具備如下兩個(gè)基本特征：1.線性表中的所有元素所占的存儲(chǔ)空間是連續(xù)的；2.線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。即線性表邏輯上相鄰、物理也相鄰，則已知第一個(gè)元素首地址和每個(gè)元素所占字節(jié)數(shù)，則可

5、求出任一個(gè)元素首地址。假設(shè)線性表的每個(gè)元素需占用K個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。則線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai)之間滿足下列關(guān)系:LOC(ai+1)=LOC(ai)+KLOC(ai)=LOC(a1)+(i-1)*K 其中，LOC(a1)是線性表的第一個(gè)數(shù)據(jù)元素a1的存儲(chǔ)位置，通常稱做線性表的起始位置或基地址。因?yàn)樵陧樞虼鎯?chǔ)結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素地址可以通過公式計(jì)算得到，所以線性表的順序存儲(chǔ)結(jié)構(gòu)是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。在線性表的順序存儲(chǔ)結(jié)構(gòu)下，可以對(duì)線性表做以下運(yùn)算：插入、刪除、查找、排序、分解、合并

6、、復(fù)制、逆轉(zhuǎn)八.順序表的插入運(yùn)算線性表的插入運(yùn)算是指在表的第I個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)x，使長(zhǎng)度為n的線性表（a1,a2 aian）變成長(zhǎng)度為n+1的線性表(a1,a2x,aian).該算法的時(shí)間主要花費(fèi)在循環(huán)的結(jié)點(diǎn)后移語句上，執(zhí)行次數(shù)是n-I+1。當(dāng)I=n+1,最好情況，時(shí)間復(fù)雜度o(1) 當(dāng)I=1, 最壞情況，時(shí)間復(fù)雜度o(n)算法的平均時(shí)間復(fù)雜度為o(n)九.順序表的刪除運(yùn)算線性表的刪除運(yùn)算是指在表的第I個(gè)位置上，刪除一個(gè)新結(jié)點(diǎn)x，使長(zhǎng)度為n的線性表（a1,a2 aian）變成長(zhǎng)度為n-1的線性表(a1,a2ai-1,ai+1an).當(dāng)I=n,時(shí)間復(fù)雜度o(1),當(dāng)I=1,時(shí)間復(fù)雜度o(

7、n) ,平均時(shí)間復(fù)雜度為o(n)第三章 棧和隊(duì)列十.棧及其基本運(yùn)算1.什么是棧？ 棧實(shí)際上也是一個(gè)線性表，只不過是一種特殊的線性表。棧是只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除這一端為棧頂（TOP），另一端為棧底（BOTTOM）。當(dāng)表中沒有元素時(shí)稱為空棧。棧頂元素總是后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。假設(shè)棧S=（a1,a2,a3,an），則a1 稱為棧底元素，an稱為棧頂元素。棧中元素按a1,a2,a3an的次序進(jìn)棧，退棧的第一個(gè)元素應(yīng)該是棧頂元素。即后進(jìn)先出。2.棧的順序存儲(chǔ)及其運(yùn)算用S（1：M）作為棧的順

8、序存儲(chǔ)空間。M為棧的最大容量。棧的基本運(yùn)算有三種：入棧、退棧與讀棧頂元素。入棧運(yùn)算：在棧頂位置插入一個(gè)新元素。首先將棧頂指針進(jìn)一（TOP+1），然后將新元素插入到棧頂指針指向的位置。退棧運(yùn)算：指取出棧頂元素并賦給一個(gè)指定的變量。首先將棧頂元素賦給一個(gè)指定的變量，然后將棧頂指針退一（TOP-1）讀棧頂元素：將棧頂元素賦給一個(gè)指定的變量。棧頂指針不會(huì)改變。十一.隊(duì)列及其基本運(yùn)算1.什么是隊(duì)列 隊(duì)列是只允許在一端刪除，在另一端插入的順序表，允許刪除的一端叫做對(duì)頭，允許插入的一端叫做對(duì)尾。隊(duì)列的修改是先進(jìn)先出。往隊(duì)尾插入一個(gè)元素成為入隊(duì)運(yùn)算。從對(duì)頭刪除一個(gè)元素稱為退隊(duì)運(yùn)算。2.循環(huán)隊(duì)列及其運(yùn)算 在實(shí)際

9、應(yīng)用中，隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置，因此，從排頭指針front指向的后一個(gè)位置直到隊(duì)尾指針 rear指向的位置之間所有的元素均為隊(duì)列中的元素。在實(shí)際使用循環(huán)隊(duì)列時(shí)，為了能區(qū)分隊(duì)滿還是隊(duì)列空，通常需要增加一個(gè)標(biāo)志S：隊(duì)列空，則S=0，rear=front=m 隊(duì)列滿，則S=1，rear=front=m循環(huán)隊(duì)列主要有兩種基本運(yùn)算：入隊(duì)運(yùn)算和退隊(duì)運(yùn)算n 入隊(duì)運(yùn)算指在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)新元素，首先rea

10、r=rear+1,當(dāng)rear=m+1時(shí)，置rear=1,然后將新元素插入到隊(duì)尾指針指向的位置。當(dāng)S=1，rear=front,說明隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算，稱為“上溢”。n 退隊(duì)運(yùn)算指在循環(huán)隊(duì)列的排頭位置退出一個(gè)元素并賦給指定的變量。首先front=front+1,并當(dāng)front=m+1時(shí)，置front=1,然后將排頭指針指向的元素賦給指定的變量。當(dāng)循環(huán)隊(duì)列為空S=0，不能進(jìn)行退隊(duì)運(yùn)算，這種情況成為“下溢”。十二.線性單鏈表的結(jié)構(gòu)及其基本運(yùn)算1.線性單鏈表的基本概念 一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，因此，為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼數(shù)據(jù)元素ai+1之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素a

11、i來說，除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息（即直接后繼的存儲(chǔ)位置）。這兩部分信息組成數(shù)據(jù)元素ai的存儲(chǔ)映象，成為結(jié)點(diǎn)。它包括兩個(gè)域：其中存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，存儲(chǔ)直接后繼存儲(chǔ)位置的域稱為指針域。指針域中存儲(chǔ)的信息稱做指針或鏈。N個(gè)結(jié)點(diǎn)鏈結(jié)成一個(gè)鏈表，即為線性表(a1, a2,an)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。又由于此鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，故又稱線性鏈表或單鏈表。有時(shí)，我們?cè)趩捂湵淼牡谝粋€(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱之為頭結(jié)點(diǎn)，它指向表中第一個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可存儲(chǔ)如線性表的長(zhǎng)度等類的附加信息，頭結(jié)點(diǎn)的指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針（即第一

12、個(gè)元素結(jié)點(diǎn)的存儲(chǔ)位置）。在單鏈表中，取得第I個(gè)數(shù)據(jù)元素必須從頭指針出發(fā)尋找，因此，單鏈表是非隨機(jī)存取的存儲(chǔ)結(jié)構(gòu) 鏈表的形式：?jiǎn)蜗?，雙向2.線性單鏈表的存儲(chǔ)結(jié)構(gòu)3帶鏈3.帶列的棧與隊(duì)列棧也是線性表，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。隊(duì)列也是線性表，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。十三.線性鏈表的基本運(yùn)算 1.線性鏈表的插入 2.線性鏈表的刪除十四.雙向鏈表的結(jié)構(gòu)及其基本運(yùn)算在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域，其一指向直接后繼，另一指向直接前驅(qū)。十五.循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。因此，從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)。第六

13、章 樹十六.樹的定義樹是一種簡(jiǎn)單的非線性結(jié)構(gòu)。樹型結(jié)構(gòu)的特點(diǎn)：1.每個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)。2.每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件結(jié)點(diǎn)，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)3.一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為樹的結(jié)點(diǎn)度4.樹的最大層次稱為樹的深度。十七.二叉樹的定義及其基本性質(zhì)1.二叉樹是另一種樹型結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹（即二叉樹中不存在度大于2的結(jié)點(diǎn)），并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。2.二叉樹的基本性質(zhì)在二叉樹的第I層上至多有2i-1個(gè)結(jié)點(diǎn)。深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)(k=1)在任意一個(gè)二叉樹中，度為

14、0的結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)；具有n 個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為log2n+1。一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。這種樹的特點(diǎn)是每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。3.滿二叉樹與完全二叉樹滿二叉樹：除最后一層以外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。在滿二叉樹的第K層上有2K-1個(gè)結(jié)點(diǎn)，且深度為M的滿二叉樹右2M-1個(gè)結(jié)點(diǎn)完全二叉樹：除最后一層以外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。具有N個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1完全二叉樹總結(jié)點(diǎn)數(shù)為N，若N為奇數(shù)，則葉子結(jié)點(diǎn)數(shù)為（N+1）/2 若N為偶數(shù)，則葉子結(jié)點(diǎn)數(shù)為N/24.二叉樹的存儲(chǔ)結(jié)構(gòu)二

15、叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹具有下列重要特性：性質(zhì)1 在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i1)。 利用歸納法容易證得此性質(zhì)。 i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)。 顯然，2i-1=20=1是對(duì)的。 現(xiàn)在假定對(duì)所有的j，1jnext=head）29.與單向鏈表相比，雙向鏈表的優(yōu)點(diǎn)之一是（更容易訪問相鄰結(jié)點(diǎn)） 30. 在（D）中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)依次訪問到表中其他所有結(jié)點(diǎn)。A線性單鏈表B雙向鏈表 C線性鏈表 D循環(huán)鏈表31. 以下數(shù)據(jù)結(jié)構(gòu)屬于非線性數(shù)據(jù)結(jié)構(gòu)的是（C）A隊(duì)列 B線性表C二叉樹 D棧32.樹是結(jié)點(diǎn)的集合，它的根結(jié)點(diǎn)數(shù)目是（有且只有1）33.具有3個(gè)結(jié)點(diǎn)的二叉

16、樹有（5種形態(tài)） 34. 在一棵二叉樹上第8層的結(jié)點(diǎn)數(shù)最多是（128） 注：2K-135. 在深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為（16） 注：2n-136. 在深度為5的滿二叉樹中，共有（31）個(gè)結(jié)點(diǎn)。 注：2n137.設(shè)一棵完全二叉樹共有699個(gè)結(jié)點(diǎn)，則在該二叉樹中的葉子結(jié)點(diǎn)數(shù)為（350）說明：完全二叉樹總結(jié)點(diǎn)數(shù)為N，若N為奇數(shù)，則葉子結(jié)點(diǎn)數(shù)為（N+1）/2；若N為偶數(shù)，則葉子結(jié)點(diǎn)數(shù)為N/2。42. 串的長(zhǎng)度是（串中所含字符的個(gè)數(shù)） 43.設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)位置的運(yùn)算稱做（模式匹配）44. N個(gè)頂點(diǎn)的連通圖中邊的條數(shù)至少為（N-1）45.N個(gè)頂點(diǎn)的強(qiáng)連通圖的邊數(shù)至少有（

17、N）46.對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為（N）47. 最簡(jiǎn)單的交換排序方法是（冒泡排序） 48.假設(shè)線性表的長(zhǎng)度為n，則在最壞情況下，冒泡排序需要的比較次數(shù)為（n(n-1)/2） 49. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是（冒泡排序）50. 在最壞情況下，下列順序方法中時(shí)間復(fù)雜度最小的是（堆排序） 51. 希爾排序法屬于（插入類排序）52. 堆排序法屬于（選擇類排序）53. 在下列幾種排序方法中，要求內(nèi)存量最大的是（歸并排序） 54. 已知數(shù)據(jù)表A中每個(gè)元素距其最終位置不遠(yuǎn)，為節(jié)省時(shí)間，應(yīng)采用（直接插入排序）55. 算法的基本特征是可行性、

18、確定性、 有窮性 和擁有足夠的情報(bào)。1.一個(gè)算法通常由兩種基本要素組成：一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作，二是算法的控制結(jié)構(gòu)。1. 算法的復(fù)雜度主要包括時(shí)間復(fù)雜度和 空間 復(fù)雜度。2. 實(shí)現(xiàn)算法所需的存儲(chǔ)單元多少和算法的工作量大小分別稱為算法的空間復(fù)雜度和時(shí)間復(fù)雜度 。3.所謂數(shù)據(jù)處理是指對(duì)數(shù)據(jù)集合中的各元素以各種方式進(jìn)行運(yùn)算，包括插入、刪除、查找、更改等運(yùn)算，也包括對(duì)數(shù)據(jù)元素進(jìn)行分析。4.數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的 數(shù)據(jù)元素 的集合。5.數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)，線性鏈表屬于 存儲(chǔ)結(jié)構(gòu) 。6.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯 結(jié)構(gòu)和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。7. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的 存儲(chǔ)結(jié)構(gòu) 以

19、及對(duì)數(shù)據(jù)的操作運(yùn)算。8.數(shù)據(jù)元素之間的任何關(guān)系都可以用 前趨和后繼 關(guān)系來描述。9.數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。10.常用的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、 索引 等存儲(chǔ)結(jié)構(gòu)。11. 順序存儲(chǔ)方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置 相鄰 的存儲(chǔ)單元中。12. 棧的基本運(yùn)算有三種：入棧、退棧與讀棧頂元素 。13. 隊(duì)列主要有兩種基本運(yùn)算：入隊(duì)運(yùn)算與 退隊(duì)運(yùn)算 。14. 在實(shí)際應(yīng)用中，帶鏈的?？梢杂脕硎占?jì)算機(jī)存儲(chǔ)空間中所有空閑的存儲(chǔ)結(jié)點(diǎn)，這種帶鏈的棧稱為 可利用棧 。15.棧和隊(duì)列通常采用的存儲(chǔ)結(jié)構(gòu)是 鏈?zhǔn)酱鎯?chǔ)和順序存儲(chǔ) 。16.當(dāng)線性表采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)存儲(chǔ)時(shí)，其主要特點(diǎn)是 邏輯結(jié)構(gòu)中

20、相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰 。17. 循環(huán)隊(duì)列主要有兩種基本運(yùn)算：入隊(duì)運(yùn)算與退隊(duì)運(yùn)算。每進(jìn)行一次入隊(duì)運(yùn)算，隊(duì)尾指針就 進(jìn)1 。18.當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于對(duì)頭指針時(shí)，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為 上溢 。19.當(dāng)循環(huán)隊(duì)列為空時(shí)，不能進(jìn)行退隊(duì)運(yùn)算，這種情況稱為 下溢 。20. 在一個(gè)容量為25的循環(huán)隊(duì)列中，若頭指針front=16，尾指針rear=9，則該循環(huán)隊(duì)列中共有 18 個(gè)元素。注：當(dāng)rearfront時(shí)，元素個(gè)數(shù)rearfront。21. 在一個(gè)容量為15的循環(huán)隊(duì)列中，若頭指針front=6，尾指針rear=9，則該循環(huán)隊(duì)列中共有3 個(gè)元素。22.順序查找一般

21、是指在 線性表 中查找指定的元素。23.在計(jì)算機(jī)中存放線性表，一種最簡(jiǎn)單的方法是 順序存儲(chǔ) 。24.在程序設(shè)計(jì)語言中，通常定義一個(gè) 一維數(shù)組 來表示線性表的順序存儲(chǔ)空間。25.在鏈?zhǔn)酱鎯?chǔ)方式中，要求每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域，另一部分用于存放指針，稱為 指針域 。其中指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)（即前件或后件）。26.在 線性單鏈表中 ，每一個(gè)結(jié)點(diǎn)只有一個(gè)指針域，由這個(gè)指針只能找到后繼結(jié)點(diǎn)，但不能找到前驅(qū)結(jié)點(diǎn)。27. 為了要在線性鏈表中插入一個(gè)新元素，首先要給該元素分配一個(gè) 新結(jié)點(diǎn) ，以便用于存儲(chǔ)該元素的值。28. 在線性鏈表中刪除一個(gè)元素后，只需要改變被刪除元素所在結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的 指針域 即可。29. 用鏈表表示線性表的突出優(yōu)點(diǎn)是 便于插入和刪除操作 。30. 在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 前件 。31. 在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度。葉子結(jié)點(diǎn)的度為 0 。32. 設(shè)一棵二叉樹中有3個(gè)葉子結(jié)點(diǎn)，8個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中總的結(jié)點(diǎn)數(shù)為 13。33. 設(shè)一棵完全二叉樹共有739個(gè)結(jié)點(diǎn)，則在該二叉樹中有 370 個(gè)葉子結(jié)點(diǎn)。34. 設(shè)一棵完全二叉樹共有700個(gè)結(jié)點(diǎn)，則在該二叉樹中有 350 個(gè)葉子結(jié)點(diǎn)。35. 在先左后右