數(shù)據(jù)結(jié)構(gòu)填空總題目

1、 1. 一個(gè)算法應(yīng)該具有以下幾個(gè)五個(gè)特征：（有窮性）（確定性）（輸入）（輸出）（可行性）2. 算法的復(fù)雜度有（時(shí)間）和（空間）之分3. 數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關(guān)系，既數(shù)據(jù)的組織形式，一般包括三個(gè)方面的內(nèi)容（邏輯結(jié)構(gòu)）（存儲(chǔ)結(jié)構(gòu)）（數(shù)據(jù)的運(yùn)算）4. （數(shù)據(jù)元素）是數(shù)據(jù)的基本單位5. （算法的復(fù)雜度）是算法效率的度量，是評價(jià)算法優(yōu)勢的重要依據(jù)6. （結(jié)構(gòu)）是元素之間的關(guān)系的集合7. 通常來說，一個(gè)數(shù)據(jù)結(jié)構(gòu)的DS可以表示為一個(gè)（二元組）8. 最常用的數(shù)據(jù)結(jié)構(gòu)是（數(shù)組結(jié)構(gòu)）和（記錄結(jié)構(gòu)）9. 算法設(shè)計(jì)策略有（遞歸技術(shù)）（分治法）（模擬法）（貪心算法）（隨機(jī)算法）（動(dòng)態(tài)規(guī)劃）（狀態(tài)空間）（搜索法）

2、10. 現(xiàn)實(shí)世界中的事物及聯(lián)系在數(shù)據(jù)世界中用（數(shù)據(jù)模型）描述11. 數(shù)據(jù)元素之間的邏輯關(guān)系，也稱（數(shù)據(jù)的邏輯結(jié)構(gòu)）12. 數(shù)據(jù)的邏輯結(jié)構(gòu)可以形式的用一個(gè)二元組B=（K，R）來表示，其中K是（結(jié)點(diǎn)的有窮集合）R是*（K上關(guān)系的有窮集合）13. 一個(gè)數(shù)據(jù)元素可以有若干個(gè)（數(shù)據(jù)項(xiàng)）組成考慮：如何做；14. （數(shù)據(jù)項(xiàng)）是具有獨(dú)立含義的最小表示單位15. （數(shù)據(jù)的運(yùn)算）既對數(shù)據(jù)施加的操作16. (數(shù)據(jù)的邏輯結(jié)構(gòu))可以看做是從具體問題抽象出來的數(shù)學(xué)模型17. 數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)；內(nèi)的表示稱為（數(shù)據(jù)的存取結(jié)構(gòu)）18. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用（計(jì)算機(jī)語言）的實(shí)現(xiàn)19. 對機(jī)器語言而言，存儲(chǔ)結(jié)構(gòu)是

3、具體的。一般至在（高級語言）層次上討論存儲(chǔ)機(jī)構(gòu)20. 所謂（抽象的操作），是至只知道這些操作是“做什么”，而無需21. 較早的軟件開發(fā)用結(jié)構(gòu)法層序設(shè)計(jì)方法。層序的定律是;程序=（算法）+（數(shù)據(jù)結(jié)構(gòu)）22. 算法是一個(gè)獨(dú)立的整體，數(shù)據(jù)結(jié)構(gòu)也是一個(gè)獨(dú)立的整體倆者分開設(shè)計(jì)以（算法）為主；23. 數(shù)據(jù)結(jié)構(gòu)是介于（數(shù)學(xué)）（計(jì)算機(jī)硬件）（計(jì)算機(jī)軟件）三者之間的一門核心課程24. 數(shù)據(jù)的范疇包括（整數(shù)）（實(shí)數(shù)）（字符串）（圖像）和（聲音）25. 下面程序的時(shí)間復(fù)雜度為）（0（sqrt（n） Void prime(int n) for(i=2;(n%i)!=)0&(isqart(n)Printf(“%d is

4、 a prime number”,n); Else print(“%d is a prime number”,n); 26. 下面程序的時(shí)間復(fù)雜度為（0（n） Float suml (int n) p=1;suml=0;For(i=1;i=n;+i) p=p*i;suml=suml+p; 27. 下面的時(shí)間復(fù)雜度為（0（n2） Float sum2(int n) sum2=0; Fori=1;i=n;i+) p=1;For(j=1;jnext= p-next ; (2) p-next=s;(3)t=p-data;(4)p-data= s-data ;(5)s-data= t ; 4.根據(jù)線性表

5、的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表可分為（單鏈表）和（雙鏈表）；而根據(jù)指針的聯(lián)系方式，鏈表又可分為（非循環(huán)鏈表）和（循環(huán)鏈表）。5.對于線性表的順序存儲(chǔ)，需要預(yù)先分配好存儲(chǔ)空間。若分配太多容易造成存儲(chǔ)空間的（浪費(fèi)），若分配太少又容易在算法中造成（上溢），因而只適用于數(shù)據(jù)量變化不大的情況；對于線性表的鏈接存儲(chǔ)，不需要（預(yù)先分配）存儲(chǔ)空間，存儲(chǔ)器中的整個(gè)（空間）都可供使用，分配和回收結(jié)點(diǎn)都非常方便，能有效的利用存儲(chǔ)空間，在算法中不必考慮（上溢）的發(fā)生，因而適用于數(shù)據(jù)量變化較大的情況。7.（雙向）鏈表適合從指點(diǎn)結(jié)點(diǎn)開始，尋找直接前趨的運(yùn)算。8.當(dāng)一個(gè)線性表經(jīng)常進(jìn)行存取操作而很少進(jìn)行插入和刪

6、除操作時(shí)，則采用（順序）存儲(chǔ)結(jié)構(gòu)為宜，相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時(shí)，則采用（鏈接）存儲(chǔ)結(jié)構(gòu)為宜。9.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（使空表和非空表統(tǒng)一，算法處理一致）。10.順序表中邏輯上相鄰的元素物理位置（一定）緊鄰，單鏈表中邏輯上相鄰的元素物理位置（不一定）緊鄰。11.如果線性表的存儲(chǔ)空間變化較大，則適用（鏈）表。12.在鏈表中，每個(gè)結(jié)點(diǎn)中含8個(gè)字符，1個(gè)指針域。其中每個(gè)字符占1個(gè)字節(jié)，每個(gè)指針占4個(gè)字節(jié)。則該結(jié)點(diǎn)的存儲(chǔ)密度是（2/3）。13.當(dāng)向一個(gè)順序表插入一個(gè)元素時(shí)，從插入位置開始向后的所有元素均（后移）一個(gè)位置，移動(dòng)過程是從（后）向（前）依次移動(dòng)沒一個(gè)元素。14.要從一個(gè)順序

7、表刪除一個(gè)元素時(shí)，被刪除元素之后的所有元素均需（前移）一個(gè)位置，移動(dòng)過程是從（前）向（后）依次移動(dòng)一個(gè)元素。15在單鏈表中，若要在指針P所指結(jié)點(diǎn)后插入指針S所指結(jié)點(diǎn)，則需要執(zhí)行下列兩條語句（s-next=p-next）和（p-next=s）。16. 在帶有頭結(jié)點(diǎn)的雙鏈表1中，指針P所指結(jié)點(diǎn)是第一個(gè)元素結(jié)點(diǎn)的條件是（p=L-next）。17. 在線性表的單鏈存儲(chǔ)中，若一個(gè)元素所在結(jié)點(diǎn)的地址為P，則其后繼結(jié)點(diǎn)的地址為（p-next），若假定P為一個(gè)數(shù)組A中的下標(biāo)，則其后繼結(jié)點(diǎn)的下標(biāo)為（a【p】-next）。18. 在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，P指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針head可用

8、P表示為head=（p-next-next）。19. 既無前驅(qū)也沒有后繼的結(jié)點(diǎn)在所在線性表長度為（1），結(jié)點(diǎn)指針域的值為（空）。20. 在單鏈表中，除了元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由（其直接前驅(qū)結(jié)點(diǎn)的鏈域的值）指示。21. 靜態(tài)鏈表是用（數(shù)組）描述的鏈表。22、 循環(huán)鏈表的特點(diǎn)是表中（最后 ）一個(gè)結(jié)點(diǎn)的指針域指向（ 頭結(jié)點(diǎn) ），整個(gè)鏈表形成一個(gè)環(huán)。23、 雙向鏈表的結(jié)點(diǎn)中有（ 質(zhì) ）個(gè)指針域，其一指向（ 直接后繼 ），另一指向（ 直接前驅(qū) ）24、 設(shè)P點(diǎn)為結(jié)點(diǎn)a的指針，如果要?jiǎng)h除a的后一個(gè)結(jié)點(diǎn)，修改指針的語句為（ p-next=p-next-next ）25、 在單鏈表中，任何兩個(gè)元素的存儲(chǔ)

9、位置之間都有固定的聯(lián)系，因?yàn)榭梢詮模?頭結(jié)點(diǎn) ）進(jìn)行查找任何一個(gè)元素26、 鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，該鏈表稱為（ 線性鏈表 ）或（ 單鏈表 ）27、 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組（ 任意 ）的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素28、 在單鏈表中，若要在指針P所指結(jié)點(diǎn)后插入指針s所指結(jié)點(diǎn)，則需要執(zhí)行下列兩條語句，s-next=p-next，（ p-next=s ）29、 一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長度是2，則第5個(gè)元素的地址是（ 108 ）30、 向順序表中第i個(gè)元素之前插入一個(gè)新元素時(shí)，首先從（ 位置i ）開始向后的所有元素均需（ 后移 ）一個(gè)位置，接著把新元素寫入（位

10、置i）上，最后使線性表的長度（加1）。從順序表中刪除第i個(gè)元素時(shí)，首先把第i個(gè)元素賦給（工作單位），接著從（位置i+1）開始向后，所有元素均（前移），最后使線性表的長度（減1）31、 在一個(gè)長度為n的順序表中刪除第i個(gè)元素，要移動(dòng)（n-i）個(gè)元素，如果要在第i個(gè)元素前插入一個(gè)元素，要后移（n+i-1）個(gè)元素32、 在雙向循環(huán)鏈表中，在p所指的結(jié)點(diǎn)之后插入s指針?biāo)傅慕Y(jié)點(diǎn)，其操作是S-next=p-next;(p-next-prior )=s;s-prior=( p );p-next=s;33. 對于一個(gè)長度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為（O(n)），在表尾插入元素的時(shí)間復(fù)

11、雜度為（ O(1) ）34. 在雙向循環(huán)表中，在p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn)，其操作為 F-next=p-next;( p-next-prior=f )( f-prior=p )。35. 在順序表中，插入或刪除一個(gè)元素，需要平均移動(dòng)（約表長的一半）個(gè)元素，具體移動(dòng)的元素個(gè)數(shù)與（該元素在線性表中的位置）有關(guān)36. 在線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過（物理存儲(chǔ)位置）決定的，在線性表的鏈接存儲(chǔ)中，元素之間的邏輯關(guān)系是通過（鏈域的指針）決定的37. 對于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中，在已知的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為（O(1) ）在給定值為X的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度

12、為（O（n）38. 在線性表中，若結(jié)構(gòu)是一個(gè)非空集，則第一個(gè)結(jié)點(diǎn)稱為（開始結(jié)點(diǎn)），且此結(jié)點(diǎn)（沒有）前驅(qū)結(jié)點(diǎn)，其余各個(gè)結(jié)點(diǎn)有且僅有（一個(gè)前驅(qū)結(jié)點(diǎn)），最后一個(gè)結(jié)點(diǎn)稱為（終端結(jié)點(diǎn)），它（沒有）后繼結(jié)點(diǎn)，其余各個(gè)結(jié)點(diǎn)有且僅有1個(gè)后繼結(jié)點(diǎn)39. 只要確定了存儲(chǔ)線性表的起始位置，線性表中任何一個(gè)數(shù)據(jù)元素都可以（隨機(jī)存?。?，這個(gè)特點(diǎn)也鑄成了這種存儲(chǔ)結(jié)構(gòu)的弱點(diǎn)，在執(zhí)行（插入）和（刪除）操作時(shí)，需要移動(dòng)大量元素40. 從一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，應(yīng)該（先移動(dòng)隊(duì)首指針，反取出元素）41. 若L是splist類型的順序表，則表中的第i個(gè)數(shù)據(jù)元素是（Lelemi-1）42. 已知一個(gè)順序存儲(chǔ)的線性表，設(shè)

13、每個(gè)結(jié)點(diǎn)需占用m個(gè)存儲(chǔ)單元，若第一個(gè)結(jié)點(diǎn)的地址為d1，則第1個(gè)結(jié)點(diǎn)的地址為（dl+(I-1)*m）第四份：CH031. 一個(gè)棧的輸入序列號12345，則棧的輸出序列是12345是（可能的）。2. 隊(duì)列的插入操作在（隊(duì)尾）進(jìn)行，刪除操作在（對頭）進(jìn)行。3. 棧又稱為（后進(jìn)先出）的表，隊(duì)列稱為（先進(jìn)先出）的表。4. 設(shè)長度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊(duì)和出隊(duì)操作的時(shí)間復(fù)雜度分別為（ O(n） ）和（ O(1) ）；若只設(shè)尾指針，則入隊(duì)和出對操作的時(shí)間復(fù)雜度分別為（ O(1) ）和（ O(1) ）。5. 向一個(gè)棧頂指針為HS的鏈中插入一個(gè)S所指結(jié)點(diǎn)時(shí)，則執(zhí)行（ S-next=HS

14、,HS=S; ）。6. 設(shè)S（1：maxsize）為一個(gè)順序存儲(chǔ)的棧，變量top只是棧頂位置，棧為空的條件是（ top=0 ），棧為滿的條件是（ top=maxsize ).7. 向一個(gè)順序棧插入一個(gè)元素時(shí)，受限使（ 棧頂指針 ）后移一個(gè)位置，然后把待插入元素（ 寫入 ）到這個(gè)位置上。8. 從一個(gè)棧刪除元素時(shí)，需要前移一位（ 棧頂指針 ）。9. 僅允許在表的同一端插入和刪除運(yùn)算的線性表被稱為（ 棧 )。10. 設(shè)sp（toplink=top ）和（ top=p ）操作。21. 鏈隊(duì)列實(shí)際上是一個(gè)同時(shí)帶有頭指針和尾指針的單鏈表，尾指針指向該單鏈表的（ 最后一個(gè)結(jié)點(diǎn) )。22. 設(shè)輸入元素的順序?yàn)?/p>

15、1,2,3,4,5，要在棧S的輸出端得到序列4.3.5.2.1，則進(jìn)行的操作用棧的基本運(yùn)算表示應(yīng)為push(S,1)，push(S,2),push(S,3),push(S,4),pop（S），( pop(s),push(s,5) ），pop(S)，pop（S），pop(S)。23. 在棧中存取數(shù)據(jù)遵從的原則是（ 后退先出 ）。24、 從一個(gè)棧頂指針為top的非空鏈?zhǔn)綏Ｖ袆h除節(jié)點(diǎn)并不需要返回棧頂結(jié)點(diǎn)的值和回收結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行（ top=toplink）操作。25、 假定front和rear分別為一個(gè)鏈?zhǔn)疥?duì)列的對頭和隊(duì)尾指針，則鏈?zhǔn)疥?duì)列中只有一個(gè)結(jié)點(diǎn)的條件為（front=rear&front！=NU

16、LL）。26、 在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的（前一個(gè)位置）；從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先取出隊(duì)首元素，后（移動(dòng)隊(duì)首指針）；在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有（n-1）個(gè)元素。27、 設(shè)有一個(gè)順序棧S，元素s1，s2，s3，s4，s5，s6依次進(jìn)棧，如果6個(gè)元素的出棧順序?yàn)閟2,s3,s6,s5,s1則順序棧的容量至少應(yīng)為（3）。28、 假設(shè)以數(shù)組Qm存放循環(huán)隊(duì)列中的元素，同時(shí)以rear和length分別只是循環(huán)隊(duì)列中的隊(duì)尾位置和隊(duì)列中的所含元素的個(gè)數(shù)，則該循環(huán)的隊(duì)列的對空條件為（length=0）。29、 中綴表達(dá)式3*（X+2）-5所對應(yīng)的后綴表達(dá)式為（3*2+*5

17、）。30、 后綴表達(dá)式45*32+-的值為（15）。31、 假設(shè)以數(shù)組Qm存放循環(huán)隊(duì)列中的元素，同時(shí)以rear和length分別只是循環(huán)隊(duì)列中的隊(duì)尾位置和隊(duì)列中的所含元素的個(gè)數(shù)，則該循環(huán)的隊(duì)列的對滿條件為（length=Maxsize）。32、 棧的存儲(chǔ)結(jié)構(gòu)有（順序棧）和（鏈棧）。33、 棧的特點(diǎn)（后進(jìn)先出），隊(duì)列的特點(diǎn)是（先進(jìn)先出），棧和隊(duì)列的特點(diǎn)是（操作受限的線性表）。34、 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素a.b.c.d.e.f依次通過棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q。若這6個(gè)元素出隊(duì)列的順序是bdcfea.則棧S的容量至少應(yīng)是（3）。35、 一個(gè)隊(duì)伍的入隊(duì)列是1234，則隊(duì)列的輸出順

18、序是（1、2、3、4）。36、 對于一個(gè)棧做進(jìn)棧運(yùn)算時(shí)，應(yīng)先判斷棧是否為（棧滿），做出棧運(yùn)算時(shí)，應(yīng)先判斷別棧是否（?？眨?dāng)棧中元素為m時(shí)，做棧運(yùn)算時(shí)發(fā)生上溢，則說明棧的可用最大容量為（m）。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的（棧底）分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當(dāng)（兩棧和棧頂空間的某一個(gè)位置）時(shí)才發(fā)生上溢。37、 設(shè)有一個(gè)空棧，棧頂指針為1000H，現(xiàn)有輸入序列為12345，push，push，pop，push，pop，push，push后，輸出序列為（2，3），棧頂指針是（1003H）。38、 設(shè)有一空棧，現(xiàn)有輸入隊(duì)列1234

19、5，經(jīng)push，push，pop，push，pop，push，push，后，輸出隊(duì)列是（2,3）。39、 用數(shù)組Q表示一個(gè)環(huán)形隊(duì)列，f為當(dāng)前對頭元素的錢一位置，r為隊(duì)尾元素的位置。假定隊(duì)列中元素個(gè)數(shù)總小于n，求隊(duì)列中元素個(gè)數(shù)公式是（r-f+n）%n）。40、 用循環(huán)鏈表表示的隊(duì)列長度為n，若只設(shè)頭指針，則出對和入對的時(shí)間復(fù)雜度分別是（0（1）和（0（n）；若只設(shè)尾指針，則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是（0（n）和（0（1）。41、 向棧中壓入元素的操作是（先移動(dòng)棧頂指針，后存入元素）。42、 向棧進(jìn)行出棧時(shí)的操作是（先取出元素，后移動(dòng)棧頂指針）。43、 在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向?qū)χ茉氐模?/p>

20、前一個(gè)位置）。44、 從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是（先移動(dòng)隊(duì)首指針，后取出位置）。45、 假設(shè)Q1,10是一個(gè)循環(huán)隊(duì)列，初始狀態(tài)為front=rear=1，若做完debgh入隊(duì)和de出隊(duì)的操作后，rear=（6），front=(3).46、 在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有（n-1）個(gè)元素。47、 將f=1+1/2+1/3+.+1/n轉(zhuǎn)化成速遞歸函數(shù)，其遞歸出口是（f（1）=1）遞歸體是（f（n）=f（n-1）+1/n）。1、 空串是 零個(gè)字符的串 ，其長度等于 零 。2、 空格串是 有一個(gè)或多個(gè)空格組成的串 ，其長度等于 串空格字符的個(gè)數(shù) 。3、 數(shù)組的長度是 數(shù)組的元素個(gè)數(shù)

21、。4、 空串與空格串的區(qū)別在于 空串的長度為零，而空格串的長度不為零 。5、 兩個(gè)字符相等的充分必要條件是 長度相等 。6、 串的兩種最基本的存儲(chǔ)方式是 順序存儲(chǔ)方式和鏈接存儲(chǔ)方式 。7、 兩個(gè)串相等的充分必要條件是 兩個(gè)串的長度相等且對應(yīng)位置的字符相同 。8、 串中任意個(gè)連續(xù)相等的字符組成的子序列稱為 子串 。9、 包含子串的串相應(yīng)地稱為 主串 。10、 當(dāng)且僅當(dāng)兩個(gè)串的值相等，稱兩個(gè)串 相等 。11、 常對數(shù)組進(jìn)行的操作是 查找和修改 。12、 二維數(shù)組A1020采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元，并且A00的存儲(chǔ)地址是200，則A612的地址是 200+（6x20+12）x1

22、。13、 有一個(gè)10階對稱矩陣A，采用壓縮存儲(chǔ)方式（以行序列為主存儲(chǔ)，且A00=1），則A85的地址是 42 。14、 串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別在于 串的數(shù)據(jù)對象約束 。15、 串的基本操作中，通常以 串的整體 為操作對象。16、 廣義表（a），（b），c），（d）的表頭是 (a) ，表尾是 (b)，c），（d）) 。17、 廣義表（a），（b），c），（d）的長度是 3 ，深度是 4 。18、 子串的定操作通常稱為串的 模式匹配 。19、 由零個(gè)或多個(gè)字符組成的有限序列，稱為 串 。20、 通常稱字符在序列中的序號為該字符在串中的 位置 。21、 兩個(gè)字符串S1和S2的長度分別為m

23、和n，求這兩個(gè)字符串最大共同子串的時(shí)間復(fù)雜度為T（m，n），這最優(yōu)的時(shí)間復(fù)雜度為 O(m*n) 。22、 廣義表（a，（a，b），d，e，（i，j），k）的長度是5 ，深度是 3 。23、 稀疏矩陣一般的壓縮存儲(chǔ)方式是 三元組和十字鏈表 。24、 二位數(shù)組A10.205.10采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，并且A105的存儲(chǔ)地址是1000，則A189的地址是 1208 。25、 二維數(shù)組Amn采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單位，并且第一個(gè)元素的存儲(chǔ)地址是LOC（A00），則Aij的地址是 Loc(A00)+(n*i+j)*k 。26、 寫出模式串P=“abaabcac”

24、的next函數(shù)值序列為01122312 。27、 數(shù)組A-2.5,2.8,1.8以行序存儲(chǔ)，設(shè)第一個(gè)元素的首地址是54，每個(gè)元素的長度為5，則元素A0，6，5的存儲(chǔ)首址為 319 。28、 設(shè)n行n列的下三角矩陣A已壓縮到一維數(shù)組S1.n*（n+1）/2中，若按行序?yàn)橹鞔鎯?chǔ)，則Aij對應(yīng)的S中的存儲(chǔ)位置是 i*(i+1)/2+j+1 。29、 數(shù)組A中，每個(gè)元素A的長度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素A85的起始地址為SA+222 。30、 其非零元素較零元素少，且分布沒有一定規(guī)律的矩陣，稱為SA+180 。31、 數(shù)

25、組A中，每個(gè)元素A的長度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的單元數(shù)是 稀疏矩陣 。32、 廣義表的表尾總是一個(gè) 240 。33、 設(shè)按低下標(biāo)優(yōu)先存儲(chǔ)整數(shù)數(shù)組A9358時(shí)，第一個(gè)元素的字節(jié)地址是100，每個(gè)整數(shù)占4個(gè)字節(jié)，a3125的存儲(chǔ)地址是 1784 。34、 假如值相同的元素或零元素在矩陣中的分布有一定規(guī)律，稱為 特殊矩陣 。35、 為多個(gè)值相同的元素分配一個(gè)存儲(chǔ)空間；對零元素不分配空間，稱為 壓縮存儲(chǔ) 。36、 廣義表的深度定義為 廣義表中括弧的重?cái)?shù) ，是廣義表的一種量度。37、 二維數(shù)組可有兩種存儲(chǔ)方式即 以行序?yàn)橹?/p>

26、序的存儲(chǔ)方式和一列序?yàn)橹餍虻拇鎯?chǔ)方式 。38、 三元組順序標(biāo)又稱有序的雙下標(biāo)法，它的特點(diǎn)是 非零元素在表中按行序有序存儲(chǔ) 。39、 設(shè)廣義表L=（），（），則Head（L）是 Head(L)=0 ；Tail（L）是 Tail(L)=(0) ；L的長度是 2 ，深度是 2 。1. 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為2h-12. 已知某二叉樹的后序遍歷為dabcc，中序遍歷為debac，則它的前序遍歷為cedba3. 如果t2是出有序樹t轉(zhuǎn)換而來的二叉樹，那么t中的結(jié)點(diǎn)的前序就是t2結(jié)點(diǎn)中的前序。4. 如果t2是由序樹t轉(zhuǎn)換而來的二叉樹，那么t中的結(jié)點(diǎn)

27、的后序就是t2結(jié)點(diǎn)中的中序。5. 某二叉樹的前序遍歷結(jié)點(diǎn)順序?yàn)閍bdgcefg，中序遍歷結(jié)點(diǎn)順序?yàn)閐gbacchf，則后序遍歷的結(jié)點(diǎn)順序?yàn)間dbehfca6. 按照二叉樹的定義，具有個(gè)結(jié)點(diǎn)的二叉樹有5種7. 深度為的二叉樹至多以有31個(gè)結(jié)點(diǎn)8. 樹最適合用來表示元素之間具有分支層次關(guān)系的數(shù)據(jù)9. 任何一顆二叉樹的葉結(jié)點(diǎn)在前序，中序，后序遍歷中的相對次序不發(fā)生改變10. 在一非空二叉樹的中，根結(jié)點(diǎn)的右邊只有右子樹上的所有結(jié)點(diǎn)11. 實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不適用棧結(jié)構(gòu)，最佳的二叉樹方法是采用三叉列表的存儲(chǔ)結(jié)構(gòu)12. 如果某二叉樹的前序?yàn)?，中序?yàn)閡wtvs，那么二叉樹的后序?yàn)閣uvt

28、s13. 具有五層結(jié)點(diǎn)的二叉樹平衡樹至少有15個(gè)結(jié)點(diǎn)14. 線索二叉樹是一種物理結(jié)構(gòu)15. 設(shè)n m 為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷中，n在m的前面的條件是n在m的上方16. 二叉樹按照某種線索化后，任意結(jié)點(diǎn)均有指向其前驅(qū)和后繼的線索，這種說法是錯(cuò)誤的二叉樹的前序遍歷中，任意一個(gè)結(jié)點(diǎn)均處于其子女結(jié)點(diǎn)的前面，這種說法是正確的17. 由于二叉樹中每個(gè)結(jié)點(diǎn)的度最大為2，所以二叉樹是一種特殊的樹，這種說法是錯(cuò)誤的18. 設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個(gè)非終端結(jié)點(diǎn)，則B中有指針域?yàn)榭盏慕Y(jié)點(diǎn)有n+1個(gè) 21.對于二個(gè)具有a個(gè)結(jié)點(diǎn)的二又樹.當(dāng)它為一裸完成二叉樹時(shí)具有最小高度，即為【

29、log2n】+1.當(dāng)它為一裸單支樹具有最大.高度.即為_n 22.在二叉搜素排序樹上進(jìn)行搜索查找時(shí).其時(shí)間復(fù)雜度為o（logN）進(jìn)行側(cè)除時(shí)，其時(shí)間復(fù)雜度為o（logn） 23.山帶權(quán)為3,，、6,2,5的5個(gè)葉子結(jié)點(diǎn)構(gòu)成一裸哈夫愛樹.則帶權(quán)路徑長度為5524.在一裸二叉排序樹上按中序遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。25 對于一裸具有n個(gè)結(jié)點(diǎn)的二又樹.當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí).其二又鏈表中的指針城的總數(shù)為2n個(gè).其中（n-1）個(gè)用于鏈接孩子結(jié)點(diǎn)n+1個(gè)空閑著。26.在一操二叉樹中.度為0的結(jié)點(diǎn)個(gè)數(shù)為no.度為2的結(jié)點(diǎn)個(gè)數(shù)為n2則n0=n2+127在具有”個(gè)結(jié)點(diǎn)的二叉排序樹上播人一個(gè)新結(jié)點(diǎn)時(shí).其時(shí)間復(fù)雜

30、度大致o（log2n）為，n個(gè)數(shù)據(jù)元眾生成一裸二又排序樹時(shí)，其時(shí)間復(fù)雜度大致為（O（log2n）28.已知8個(gè)數(shù)據(jù)元素由( 35,75,40,15,20,55,95,65 )按照依次搔入結(jié)點(diǎn)的方法生成一裸二叉排序樹后.最后兩層上的結(jié)點(diǎn)總數(shù)為 2_ 29.由a, b, c三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹.共有_ 5 種不同結(jié)構(gòu)。30假定一裸三叉樹的結(jié)點(diǎn)放為50,則它的最小高度為 5 31，在一裸二叉樹上的第5層的結(jié)點(diǎn)數(shù)最多為_ 16 32.由帶權(quán)為，9、2. 5,7，的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一裸哈夫曼樹.該樹的帶權(quán)路徑長度為 44 33假定在一操二又樹中.雙分支結(jié)點(diǎn)數(shù)為15.單分支結(jié)點(diǎn)致為30個(gè).則葉子結(jié)點(diǎn)數(shù)為

31、16 34.在一裸度為3的樹中.度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為.個(gè)。度為.的結(jié)點(diǎn)數(shù)為2個(gè).則度為0的結(jié)點(diǎn)數(shù)為 6 個(gè)， 35.假定一裸樹的廣義表表示為A(B(E),C(F(H,I,J),G),D), (Il該樹的深度為 4 36. 有12個(gè)結(jié)點(diǎn)的平衡二叉樹的最大深度是 5 37.設(shè)森林F中有三裸樹，第一、第二和第只裸樹的結(jié)點(diǎn)個(gè)數(shù)分別為ml, m2, m3.則與森林F對應(yīng)的二又樹根結(jié)點(diǎn)的右子樹I.的結(jié)點(diǎn)個(gè)致是_ m2+m3 。 38.若二又樹采用的是二又鏈表存儲(chǔ)結(jié)構(gòu).要交換其所有分支結(jié)點(diǎn)左右子樹的位置利用_中序 遍歷方斌最合適。39.在計(jì)算遞歸曲數(shù)時(shí)，如不使用遞歸過程.則一般悄況下必須借

32、助于 棧 數(shù)據(jù)結(jié)構(gòu)。 40樹(及一切樹形結(jié)構(gòu))是一種“_ 分支層次 “結(jié)構(gòu)，在樹上根_結(jié)點(diǎn)沒有育接晌馭，對樹上任一結(jié)點(diǎn)x來說.x是它的任一子樹的根結(jié)點(diǎn)惟一的_直接前驅(qū) 。 41.一裸樹上的任何結(jié)點(diǎn)(不包括根本身)稱為根的_子孫 。若B是A的子孫.則稱A是B的 祖先 42.一般的.二又樹有 空 二又樹、 只含根 的二叉樹、只有 非空左子樹 的二又樹，只有 非空右子樹 _的二叉樹、同時(shí)有 非空左右子樹 的二又樹五種幕本形態(tài): 43.二又樹第i (i=1）層上至多有 2t-1 個(gè)結(jié)點(diǎn)。 44.深度為k(k=1)的二叉樹至多有 2k-1 個(gè)結(jié)點(diǎn). 45對任何二又樹.若度為2的結(jié)點(diǎn)數(shù)為n2:，則葉子數(shù)n

33、0= n2+1 46滿二叉樹卜各層的結(jié)點(diǎn)數(shù)以達(dá)到了二叉樹可以容納的 最大值 。滿二叉樹也是_完全 二又樹.但反之不然。 47.具有n個(gè)結(jié)點(diǎn)的完全二又樹的深度為_（log2n）+1 。48.如果將一裸有n個(gè)結(jié)點(diǎn)的完全二X樹按層編號.則對任一編號為i(1=i1,則x的雙親PARENT(X)的編號為 Floor（i/2） (2)若2in.則結(jié)點(diǎn)x無 左孩子 且無 右孩子 ;否則。x的左孩子LC)iILD(X)的編號為 2i (3)若2i+1n。.則結(jié)點(diǎn)x無_ 右孩子 否則.x的右孩子RCHILD(X)的編號為 2i+1 49.二叉樹通常有 順序 存儲(chǔ)結(jié)構(gòu)和 鏈?zhǔn)?存儲(chǔ)結(jié)構(gòu)兩類存儲(chǔ)結(jié)構(gòu)。50.每個(gè)二叉

34、鏈表的訪問只能從 根 結(jié)點(diǎn)的指針.該指針幾有標(biāo)識二叉鏈表的作用。51.對二叉鏈表的訪問只能從 根 指針開始.若二叉樹為空， 則 root =NULL,1. 有向圖G用鄰接矩陣A1。n，1。n存儲(chǔ)，其第一列的所有元素之和等于頂點(diǎn)1的（入度）。2. 在一個(gè)有向圖中，所有頂點(diǎn)入度之和等于所有頂點(diǎn)出度之和的（1）倍。3. 對于含有N個(gè)頂點(diǎn)E條邊的無向連通圖，利用Kruskal算法生成最小代價(jià)生成樹的時(shí)間復(fù)雜度為（o（elg0）。4. 設(shè)G為具有N個(gè)頂點(diǎn)的無向連通圖，則G至少有（N-1）條邊。5. 一棵有N個(gè)頂點(diǎn)的生成樹有且僅有（N-1）條邊。6. 若連通網(wǎng)絡(luò)上各邊的權(quán)值均不相同，則該圖的最小生成樹有（1）棵。7. 不存在拓?fù)湫蛄械模ㄓ邢驁D）是圖中存在回路。8. 已知一個(gè)圖的鄰接矩陣表示，刪除所有從第一個(gè)節(jié)點(diǎn)出發(fā)的邊的方法是（將矩陣第一行全部置為0）.9. 對于一個(gè)圖G，若邊集E（G）為有向邊的集合，則該圖為（有向圖）。10. 對于一個(gè)圖G，若邊集E（G）為無向邊的集合，則該圖為（無向圖）。11. 在一個(gè)無向圖中，若存在一條邊,則稱Vi和Vj為該邊的兩個(gè)端點(diǎn)，并稱他們互為（鄰接點(diǎn)）。12. 對于有向圖，頂點(diǎn)V的度分為（入度和出度）。13. 有向圖頂點(diǎn)V的度