數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)

*)設(shè)一組初始記錄關(guān)鍵字序列(8，3，6，5，9)，以第一個(gè)記錄關(guān)鍵字8為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為5,3,6,8,9*)用快速排序法對(duì)序列（22，5，8，20，18，10）進(jìn)行升序排序，寫出每一趟的排序過程。第一趟：{10582018}22第二趟：{85}10{2018}22第三趟：58101820*)從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）的一端的方法，稱為___選擇排序_______*)內(nèi)部排序是指排序過程在內(nèi)存中進(jìn)行的排序。按照排序過程涉及的存儲(chǔ)設(shè)備的不同，排序通?？煞譃閮?nèi)部排序和外部排序。*)用簡單選擇排序法對(duì)關(guān)鍵字序列(46，90，48，30，22，78)進(jìn)行升序排序，寫出每一趟的排序過程。P247答：第一趟：(22)9048304678第二趟：(2230)48904678 第三趟：(223046)904878第四趟：(22304648)9078第五趟：(2230464878)90堆是完全二叉樹，完全二叉樹不一定是堆正確直接選擇排序是一種穩(wěn)定的排序方法錯(cuò)誤（它是一種不穩(wěn)定的排序方法）堆的形狀是一棵__完全二叉樹___________*)假設(shè)關(guān)鍵字的輸入順序?yàn)?12,2,16,30,28,10,16,20,6,18),畫出堆排序每趟排序結(jié)束后關(guān)鍵字狀態(tài)。P2702(1)題圖片*)簡述快速排序算法思想。設(shè)要排序的\t"/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/_blank"數(shù)組是A[0]……A[N-1]，首先任意選取一個(gè)數(shù)據(jù)（通常選用數(shù)組的第一個(gè)數(shù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它左邊，所有比它大的數(shù)都放到它右邊，這個(gè)過程稱為一趟快速排序*)在快速排序、堆排序、歸并排序中，____歸并排序_____排序是穩(wěn)定的?？焖倥判蛟赺__被排序的數(shù)據(jù)完全無序___情況下最易發(fā)揮其長處。P246*)希爾排序?qū)嵸|(zhì)上是采用_分組插入___的方法來實(shí)現(xiàn)的。設(shè)待排序的關(guān)鍵字序列為{12，26，40，28，30，20，6，18}，試寫出使用直接插入排序，每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。答初始化關(guān)鍵字（12）2640283020618i=1 （1226）40283020618i=2 （122640）283020610i=3 （12262840）3020610i=4 （1226283040）20610i=5 （122026283040）610i=6 （6122026283040）10i=7 （610122026283040）*)簡述插入排序的基本思想每一趟講一個(gè)待排序的記錄，安其關(guān)鍵字的大小插入到已經(jīng)排好序的一組記錄的適當(dāng)位置上，直到所有待排序記錄全部插入為止。折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素52，則它將依次與表中（20703050）比較大小，查找結(jié)果是失敗。P231第7題折半查找只適用于有序表，包括有序的順序表和鏈表*）適用于折半查找的表的存儲(chǔ)方式及元素排列要求為順序方式存儲(chǔ)，元素有序*）對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較（）次關(guān)鍵字。P230第5題解法：第一次（1+22）/2=11假設(shè)在左邊第二次（1+10）/2=5第三次（1+4）/2=2第四次與第1個(gè)位置上的數(shù)進(jìn)行比較*)散列表的沖突處理方法，按組織形式的不同，分為___開放定址法________和____拉鏈(Chaining)法_________.*)散列表的平均查找長度取決于裝填因子。

*)創(chuàng)建二叉排序樹的時(shí)間復(fù)雜度為______________*)平衡二叉樹的左子樹和右子樹的深度之差的絕對(duì)值不超過1*)已知關(guān)鍵字的輸入序列為（352348824135725），畫出建立平衡排序二叉樹的過程。答：如圖所以（因?yàn)椴恢牢易龅膶?duì)錯(cuò)，如果錯(cuò)了和我說下）*）對(duì)有序表（3，4，5，7，24，30，42，54，63，72，87，95）進(jìn)行折半查找元素42和80，則需要分別依次與哪些元素比較？答：3063428772*）若有18個(gè)元素的有序表存放在一維數(shù)組A[18]中，第一個(gè)元素放A[1]中，現(xiàn)進(jìn)行折半查找，則查找A［3］的比較序列的下標(biāo)依次為答：這個(gè)題有一點(diǎn)點(diǎn)問題，應(yīng)該是A[19]才對(duì)答案為：9423在一棵空的二叉排序樹中依次插入關(guān)鍵字序列為12，7，17，11，16，2，13，9，21，4，請(qǐng)畫出所得到的二叉排序樹。答：如圖所示：*）長度20的有序表進(jìn)行折半查找，則對(duì)應(yīng)的判定樹高度為答：5次*）對(duì)一個(gè)有序表：(13，18，24，35，47，50，62)進(jìn)行折半查找，畫出折半查找過程的判定樹，并給出查找元素24時(shí)，需要依次與哪些元素比較？答：如圖所示*)從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）的一端的方法，稱為插入排序*)由3個(gè)結(jié)點(diǎn)可以構(gòu)造出（5）種不同的二叉樹*)一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為11至1025之間注：折半折半的計(jì)算算出最小的來*)設(shè)F是一個(gè)森林，B是由F變換得的二叉樹。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（n+1）個(gè)。*）利用二叉鏈表存儲(chǔ)樹，則根結(jié)點(diǎn)的右指針是（A）。A．空 B．非空C．指向最左孩子 D．指向最右孩子注意：二叉鏈表：

左孩子右兄弟根節(jié)點(diǎn)沒有兄弟，所以為空 *)用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常借助（B）來實(shí)現(xiàn)算法。A．棧 B.隊(duì)列 C.樹 D．圖廣搜都是隊(duì)列

鄰接表是鏈表*)在下列存儲(chǔ)形式中，（D）不是樹的存儲(chǔ)形式？A．雙親表示法 B．孩子鏈表表示法C．孩子兄弟表示法 D．順序存儲(chǔ)表示法*)二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)的個(gè)數(shù)11二叉樹有如下性質(zhì)

N0=N2+1，葉子節(jié)點(diǎn)個(gè)數(shù)等于度為2的節(jié)點(diǎn)個(gè)數(shù)+1

*)深度為h的滿m叉樹的第k層有（B）個(gè)結(jié)點(diǎn)。(1=<k=<h)mk-1 B．mk-1 C．mh-1 D．mh-1*)n（n≥2）個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹，以下關(guān)于該樹的敘述中，錯(cuò)誤的是（A）。A．該樹一定是一棵完全二叉樹B．樹中一定沒有度為1的結(jié)點(diǎn)C．樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)D．樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值*）拓?fù)渑判蛩惴芘袛嘤邢驁D中存在環(huán)*)一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，則該二叉樹中度為1的結(jié)點(diǎn)個(gè)數(shù)是1，葉子結(jié)點(diǎn)的個(gè)數(shù)是500，二叉樹的高度是10。答：該樹有：2^9+489=1001同所以該樹高度為10其中10層的489個(gè)節(jié)點(diǎn)度為0同時(shí)這489個(gè)節(jié)點(diǎn)使得第9層有244度為21個(gè)度為1第9層共有2^（9-1）個(gè)節(jié)點(diǎn)256個(gè)節(jié)點(diǎn)所以第9層度為葉子節(jié)點(diǎn)有11個(gè)加上第10層的489個(gè)一共有500個(gè)葉子節(jié)點(diǎn)*)某二叉樹結(jié)點(diǎn)的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結(jié)點(diǎn)數(shù)目為4個(gè)提示：根據(jù)中序后序畫出二叉樹*)設(shè)哈夫曼樹中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有（100）個(gè)葉子結(jié)點(diǎn)提示：在哈夫曼樹中，葉子節(jié)點(diǎn)總比內(nèi)節(jié)點(diǎn)多一個(gè)，沒有度為1的節(jié)點(diǎn)所以設(shè)度為0的為a度為2的為ba=b+1n=a+b所以n=2*a-1b=100*)在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的（2）倍*)具有n個(gè)頂點(diǎn)的有向圖最多有（n(n-1)）條邊。完全有向圖*)若從無向圖的任意一個(gè)頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索可以訪問圖中所有的頂點(diǎn)，則該圖一定是（連通圖）圖*)已知圖的鄰接表如右圖所示，則從頂點(diǎn)v0出發(fā)的按照深度優(yōu)先遍歷的結(jié)果是（）*）Kruskal算法適合構(gòu)造一個(gè)稀疏圖G的最小生成樹，Prim算法適合構(gòu)造一個(gè)稠密圖G的最小生成樹*)有很少條邊或弧的圖稱為稀疏圖,反之稱為稠密圖對(duì)*)p1882（1）鄰接矩陣和鄰接表*)簡述迪杰斯特拉算法思想。*)簡述圖的廣度優(yōu)先搜索算法思想。廣度優(yōu)先搜索是一種圖的搜索算法。在搜索開始，會(huì)確定一個(gè)搜索的起點(diǎn)，然后選擇一個(gè)與其相鄰的且在值上與節(jié)點(diǎn)最接近的點(diǎn)，然后迭代進(jìn)行，如果在最后發(fā)現(xiàn)所有鄰居都已經(jīng)被訪問過，則開始回溯*)簡述克魯斯卡爾算法思想。答：考慮問題的出發(fā)點(diǎn):為使生成樹上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。

具體做法:先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止。*)度為2的有序樹是二叉樹錯(cuò)*)存在這樣的二叉樹，其任何次序的遍歷結(jié)果都相同對(duì)*)圖的廣度優(yōu)先搜索樹是惟一的。錯(cuò)*)圖的深度優(yōu)先遍歷類似于二叉樹的__前序遍歷_______*)G是一個(gè)非連通無向圖，共有28條邊，則該圖至少有（9）個(gè)頂點(diǎn)注：將28條邊全部連接起來的最小頂點(diǎn)數(shù)為8，因?yàn)榉沁B通，再加一個(gè)頂點(diǎn)得答案9*)存儲(chǔ)圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點(diǎn)個(gè)數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。 錯(cuò)*)完全二叉樹某結(jié)點(diǎn)有右子樹，則必然有左子樹。 對(duì) *)圖的深度優(yōu)先序列和廣度優(yōu)先序列不是惟一的。 對(duì) *)鄰接表只能用于存儲(chǔ)有向圖。 錯(cuò) *)從源點(diǎn)到終點(diǎn)的最短路徑是唯一的。對(duì) *)強(qiáng)連通圖的各頂點(diǎn)間均可達(dá)。對(duì)*)完全二叉樹某結(jié)點(diǎn)有右子樹，則必然有左子樹。 對(duì) *)稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。 對(duì) *)圖的廣度優(yōu)先搜索樹是惟一的。錯(cuò) *)圖的生成樹是惟一的。 錯(cuò) *)無向圖的連通分量是其極小連通子圖。 錯(cuò)*)二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于1。 錯(cuò) *)具有12個(gè)結(jié)點(diǎn)的完全二叉樹有5個(gè)度為2的結(jié)點(diǎn)。 對(duì) *)哈夫曼樹中沒有度數(shù)為1的結(jié)點(diǎn)。 對(duì) *)中序遍歷一棵二叉排序樹可以得到一個(gè)有序的序列。 對(duì)*)二叉樹的先序、中序、后序遍歷*)在用二叉鏈表存儲(chǔ)一棵二叉樹時(shí)，n個(gè)結(jié)點(diǎn)的二叉樹共有___2n_____個(gè)指針域，其中有____n-1____個(gè)指針域是存放了地址，有_____n+1__個(gè)指針是空指針。*)圖有鄰接矩陣、鄰接表等存儲(chǔ)結(jié)構(gòu)，遍歷圖有深度優(yōu)先遍歷、廣度優(yōu)先遍歷等方法。*)在無向圖G的鄰接矩陣A中，A[i][j]=1，則A[j][i]=1*)一棵完全二叉樹有128個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為8，葉子結(jié)點(diǎn)的個(gè)數(shù)為___64_____。*)一棵完全二叉樹上有500個(gè)結(jié)點(diǎn)，則該二叉樹中度為1的結(jié)點(diǎn)個(gè)數(shù)是1，葉子結(jié)點(diǎn)的個(gè)數(shù)是250，二叉樹的高度是9。*)遍歷圖的基本方法有廣度優(yōu)先遍歷和深度優(yōu)先遍歷兩種，其中可以借助棧實(shí)現(xiàn)的是深度優(yōu)先遍歷，可以借助隊(duì)列實(shí)現(xiàn)的是廣度優(yōu)先遍歷。*)具有10個(gè)頂點(diǎn)的無向圖，邊的總數(shù)最多為____45____。注：n(n-1)/2*)二叉樹的后序遍歷是CBEDA，中序序列是BCADE，則該二叉樹的樹根是A，根結(jié)點(diǎn)的左孩子是B，右孩子是D，二叉樹的先序序列為ABCDE。*)一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)元素為ABCDEF，則該二叉樹的先序遍歷序列為__ABDECF_________，中序遍歷序列為__DBEAFC________，后序遍歷序列為___DEBFCA________。*)樹結(jié)構(gòu)中根節(jié)點(diǎn)___沒有_____雙親結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)都有1個(gè)雙親結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有孩子結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)都有至少1個(gè)孩子結(jié)點(diǎn)。*)在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的__2____倍。*)度為2的樹與二叉樹有何區(qū)別？答：度為2的樹是不區(qū)分左右子樹的，而二叉樹左子樹與右子樹是不一樣的度為2的樹是不包含空樹，而二叉樹是可以有空樹的總結(jié)：二叉樹定義要比度為2的樹嚴(yán)格*)簡述連通圖的生成樹的定義答：連通圖G(V,E),當(dāng)從圖的任意一頂點(diǎn)出發(fā)，將邊集E(G)分成T（G）和B（G），其中T（G）是遍歷圖時(shí)所經(jīng)歷過的邊的集合，B（G）是遍歷圖未經(jīng)過邊的集合，即，G1（V,T）就是G的極小聯(lián)通子圖，所以G1就是連通圖G的生成樹。*)一份電文中有6種字符：A,B,C,D,E,F，它們的出現(xiàn)頻率依次為6，5，9，13，30，1，畫出對(duì)應(yīng)的哈夫曼樹（要求每個(gè)結(jié)點(diǎn)左孩子的頻率不高于右孩子的頻率）；計(jì)算其帶權(quán)路徑長度WPL解：WPL=1*5+5*5+6*4+9*3+13*2+30*1=137*)已知如圖所示的無向網(wǎng)，請(qǐng)畫出它的最小生成樹(兩個(gè)算法都要掌握)。答：普里姆算法克魯斯卡爾算法*)假設(shè)一棵二叉樹的先序序列：ABDFCEGH，中序序列：BFDAGEHC，畫出這棵二叉樹，求這棵二叉樹的后序序列。答：后序遍歷為：FDBGHECA*)已知如圖所示的有向圖，請(qǐng)給出：每個(gè)頂點(diǎn)的入度和出度、鄰接矩陣和鄰接表。ID：入度OD：出度ID(1)=3OD（1）=0（1）ID(2)=2OD（2）=1（1）ID(3)=1OD（3）=2（1）ID(4)=1OD（4）=3（1）ID(5)=2OD（5）=1ID(6)=2OD（6）=3*)P17(1)(2),(3)(4)(5)(6)*)邏輯結(jié)構(gòu)的四種基本關(guān)系。*)數(shù)據(jù)結(jié)構(gòu)主要包括哪三方面內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算.*)邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系。邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，而存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，它包括數(shù)據(jù)元素的表示及其關(guān)系的表示。一種邏輯結(jié)構(gòu)可以采用一種或幾種存儲(chǔ)方式來表達(dá)數(shù)據(jù)元素之間的邏輯關(guān)系，相應(yīng)的存儲(chǔ)結(jié)構(gòu)稱為給定邏輯結(jié)構(gòu)的存儲(chǔ)實(shí)現(xiàn)或存儲(chǔ)映像。*)線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn)。線性結(jié)構(gòu)是最簡單最常用的一種數(shù)據(jù)結(jié)構(gòu),線性結(jié)構(gòu)的特點(diǎn)是結(jié)構(gòu)中的元素之間滿足線性關(guān)系,按這個(gè)關(guān)系可以把所有元素排成一個(gè)線性序列.線性表,串,棧和隊(duì)列都屬于線性結(jié)構(gòu).

而非線性結(jié)構(gòu)是指在該類結(jié)構(gòu)中至少存在一個(gè)數(shù)據(jù)元素,它具有兩個(gè)或者兩個(gè)以上的前驅(qū)或后繼.如樹和二叉樹等.*)評(píng)估算法的優(yōu)劣，通常從時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面考察。*)數(shù)據(jù)的邏輯結(jié)構(gòu)分兩大類：邏輯結(jié)構(gòu)和__儲(chǔ)存____結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)方法主要有兩種：順序存儲(chǔ)方法和鏈?zhǔn)酱鎯?chǔ)方法。*)程序段“i=1;while(i<=n)i=i*3;”的時(shí)間復(fù)雜度為。解析：假設(shè)循環(huán)次數(shù)是x。

i=1,3,9,27,i=3^x

條件是i<=n

3^x<=n

所以x<=log3n一共執(zhí)行循環(huán)體log3n次，所以時(shí)間復(fù)雜度是O(log3n)*)線性結(jié)構(gòu)中元素之間是一對(duì)一關(guān)系，樹結(jié)構(gòu)中元素之間是一對(duì)多關(guān)系，圖結(jié)構(gòu)中元素之間是多對(duì)多關(guān)系。*)線性表的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，其元素的個(gè)數(shù)稱為線性表的長度。*)p51(1)(2)(3)(5)(6)(7)(9)(11)(13)*)存儲(chǔ)密度*)非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)p滿足（A）。A．p->next==head B.p->next==NULL C.p==NULL D.p==headP83(1)(2)(3)(10)(12)(14)(15)P108(1)(5)(6)(7)(8)(11)(12)(14)(15)判斷題：*)數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴于計(jì)算機(jī)的。錯(cuò)*)順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。錯(cuò)*)單鏈表不是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)對(duì)*)循環(huán)鏈表不是線性表。錯(cuò)*)數(shù)組元素的下標(biāo)值越大，存取時(shí)間越長。 錯(cuò) *)線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。錯(cuò)*)一個(gè)遞歸算法必須包括終止條件和迭代部分。 錯(cuò)是遞歸部分 *)稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。 對(duì)*)空串就是空格串。 錯(cuò) 空串是"";空白串是null

*)廣義表的元素可以是單原子也可以是子表。對(duì)*)棧和隊(duì)列都是受限的線性結(jié)構(gòu)。 對(duì) *)以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，出棧必須判別棧空的情況。對(duì)*）循環(huán)鏈表不是線性表。錯(cuò)1.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算這三個(gè)方面的內(nèi)容。2.在具有n個(gè)元素的循環(huán)隊(duì)列中，隊(duì)滿時(shí)具有n-1個(gè)元素。3.在棧結(jié)構(gòu)中，允許插入、刪除的一端稱為棧頂，另一端稱為棧底。*)當(dāng)有多個(gè)函數(shù)構(gòu)成嵌套調(diào)用時(shí)，按照____后調(diào)用先返回________的原則，上述函數(shù)之間的信息傳遞和控制轉(zhuǎn)移必須通過_____棧_____來實(shí)現(xiàn)。4.廣義表(a，(b)，((c，(d))))的長度是2，深度是3，表頭是a，表尾是(b)，((c，(d)))。5.設(shè)二維數(shù)組A的內(nèi)存首地址為M，其行下標(biāo)i=0,1,…,8,列下標(biāo)j=1,2,…,10。若A按行先存儲(chǔ)，則元素A[8,5]的地址為M+84；當(dāng)A按列先存儲(chǔ)時(shí)，該地址存放的的元素是A[8][5]。設(shè)每個(gè)字符占一個(gè)字節(jié)。若其首地址是S，每個(gè)元素占k個(gè)字節(jié)，則數(shù)組元素A[i][j]的地址P是p=S+(i*n+j)*kP=M+(8*10+4)*11.評(píng)估算法的優(yōu)劣，通常從時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面考察。2.數(shù)據(jù)的邏輯結(jié)構(gòu)分兩大類：___線性__結(jié)構(gòu)和_非線性_結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)方法主要有兩種：順序存儲(chǔ)方法和鏈?zhǔn)酱鎯?chǔ)方法。3.用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列時(shí)，如果當(dāng)前front和rear的值分別為3和0，則從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，front和rear的值分別為4和2。解析：當(dāng)出隊(duì)列中刪除一個(gè)元素，也就是出隊(duì)，即front+1:=4再插入兩個(gè)元素，即rear+2=22.線性結(jié)構(gòu)中元素之間是一對(duì)一關(guān)系，樹結(jié)構(gòu)中元素之間是一對(duì)多關(guān)系，圖結(jié)構(gòu)中元素之間是多對(duì)多關(guān)系。3.具有n個(gè)元素的循環(huán)隊(duì)列中，隊(duì)滿時(shí)有n-1個(gè)元素。4.假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，G），H（I，J）），則樹中所含的結(jié)點(diǎn)數(shù)為__9_____個(gè)，樹的深度為3，樹的度為___8____。1.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算這三個(gè)方面的內(nèi)容。2.線性結(jié)構(gòu)中元素之間是一對(duì)一關(guān)系，樹結(jié)構(gòu)中元素之間是一對(duì)多關(guān)系，圖結(jié)構(gòu)中元素之間是多對(duì)多關(guān)系。3.用容量為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列時(shí)，如果當(dāng)前front和rear的值分別為4和1，則從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，front和rear的值分別為和5,6。*)在具有n個(gè)元素的循環(huán)隊(duì)列中，隊(duì)滿時(shí)具有n-1個(gè)元素。*)在棧結(jié)構(gòu)中，允許插入、刪除的一端稱為棧頂，另一端稱為棧底。*)已知循環(huán)隊(duì)列的存儲(chǔ)空間大小為20，且當(dāng)前隊(duì)列的頭指針和尾指針的值分別為8和3，則該隊(duì)列的當(dāng)前的長度為__15_____；插入2個(gè)元素又刪除5個(gè)元素后頭指針變?yōu)?0，尾指針變?yōu)?，隊(duì)列長度變?yōu)?8。長度計(jì)算：（20-8）+（3-0）=15*)簡述隊(duì)列和棧的相同點(diǎn)和不同點(diǎn)。棧和隊(duì)列都是線性表，都是限制了插入刪除點(diǎn)的線性表（或者說是控制了訪問點(diǎn)的線性表）共同點(diǎn)：都是只能在線性表的端點(diǎn)插入和刪除 不同點(diǎn)棧的插入和刪除都在線性表的同一個(gè)端點(diǎn)，該點(diǎn)通稱棧頂，相應(yīng)地，不能插入刪除的另一個(gè)端點(diǎn)通稱棧底，其特性是后進(jìn)先出隊(duì)列在線性表的表頭插入，表尾刪除，表頭一般稱隊(duì)頭，表尾一般稱隊(duì)尾，其特性是先進(jìn)先出

相同之處：n個(gè)（同類）數(shù)據(jù)元素的有限序列稱為線性表。線性表的特點(diǎn)是數(shù)據(jù)元素之間存在“一對(duì)一”的關(guān)系，棧和隊(duì)列都是操作受限制的線性表，他們和線性表一樣，數(shù)據(jù)元素之間都存在“一對(duì)一”的關(guān)系不同之處：棧只允許在一段進(jìn)行插入或刪除操作的線性表，其最大的特點(diǎn)是“后進(jìn)后出”；對(duì)列是只允許在一端進(jìn)行插入，另一端進(jìn)行刪除操作的線性表，其最大的特點(diǎn)是“先進(jìn)后出”。*)簡述數(shù)據(jù)結(jié)構(gòu)主要研究的對(duì)象和研究的問題數(shù)據(jù)的邏輯結(jié)構(gòu)，即數(shù)據(jù)關(guān)系之間的邏輯關(guān)系；數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，即數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示；操作算法，即插入、刪除、修改、查詢、排序等。*)假定有三個(gè)元素A、B、C、D依次進(jìn)棧，進(jìn)棧過程中允許出棧，試寫出所有元素C先出棧的出棧序列。ABDC，BADC*)簡述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)。頭結(jié)點(diǎn)：是為了方便操作鏈表而附設(shè)的,頭結(jié)點(diǎn)數(shù)據(jù)域通常用來保存跟鏈表有關(guān)的信息,比如鏈表的長度；

首元結(jié)點(diǎn)：就是鏈表里“正式”的第一個(gè)結(jié)點(diǎn),即鏈表的開始結(jié)點(diǎn)。

頭指針：頭指針是指向鏈表的基地址。如果鏈表存在頭結(jié)點(diǎn)則頭指針就是指向頭結(jié)點(diǎn)的地址,反之指向首元結(jié)點(diǎn)的地址。*)順序表與鏈表各自的優(yōu)缺點(diǎn)是什么？順序表存儲(chǔ)：

優(yōu)點(diǎn)：（1）空間利用率高。（局部性原理，連續(xù)存放，命中率高）

（2）存取速度高效，通過下標(biāo)來直接存儲(chǔ)。缺點(diǎn)：（1）插入和刪除比較慢，比如：插入或者刪除一個(gè)元素時(shí)，整個(gè)表需要遍歷移動(dòng)元素來重新排一次順序。

（2）不可以增長長度，有空間限制,當(dāng)需要存取的元素個(gè)數(shù)可能多于順序表的元素個(gè)數(shù)時(shí),會(huì)出現(xiàn)"溢出"問題.當(dāng)元素個(gè)數(shù)遠(yuǎn)少于預(yù)先分配的空間時(shí),空間浪費(fèi)巨大。鏈表存儲(chǔ)：優(yōu)點(diǎn)：（1）存取某個(gè)元素速度慢。

（2）插入和刪除速度快，保留原有的物理順序，比如：插入或者刪除一個(gè)元素時(shí)，只需要改變指針指向即可。

（3）沒有空間限制,存儲(chǔ)元素的個(gè)數(shù)無上限,基本只與內(nèi)存空間大小有關(guān).

缺點(diǎn)：（1）占用額外的空間以存儲(chǔ)指針(浪費(fèi)空間，不連續(xù)存放，malloc開辟，空間碎片多)

（2）查找速度慢，因?yàn)椴檎視r(shí)，需要循環(huán)鏈表訪問，需要從開始節(jié)點(diǎn)一個(gè)一個(gè)節(jié)點(diǎn)去查找元素訪問。

*)棧、隊(duì)列和線性表的區(qū)別是什么？棧和隊(duì)列都是線性表，并且都是特殊的線性表：特殊在于限制了插入和刪除點(diǎn)棧是在線性表的某固定一端插入和刪除，因此特性為后進(jìn)先出隊(duì)列是在線性表的一端插入，另外一端刪除，因此特性為先進(jìn)先出*)請(qǐng)將banana用工具H()—Head()，T()—Tail()從L中取出。其中，L=(apple,(orange,(strawberry,(banana)),peach),pear)。H（H（T（H（T（H（T（L）））））））根據(jù)廣義表的定義來取值程序設(shè)計(jì)題主要考鏈表，包括鏈表的查詢，插入，刪除，循環(huán)鏈表的合并#include"stdafx.h"#include<stdio.h>#include<iostream.h>typedefintElemType;typedefstructLNode{ ElemTypedata; structLNode*next;}LNode,*LinkList;//鏈表的初始化intInitList(LinkList&L){L=newLNode;L->next=NULL;return1;}//創(chuàng)建一個(gè)單鏈表voidCreateList_H(LinkList&L,intn){ inti; LinkListp;L=newLNode; L->next=NULL; for(i=0;i<n;i++){ p=newLNode;// scanf("%d",&p->data); cin>>p->data; p->next=L->next; L->next=p; }}//根據(jù)下標(biāo)查找數(shù)據(jù)intGetElem(LinkList&L,inti,ElemType&e){LinkListp;p=L->next;intj=1;while(p&&j<i){p=p->next;