計算機復習材料補充-面向信息技術(shù)類專業(yè)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識

1、數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識整*1、數(shù)據(jù)：是信息的載體，能夠被計算機識別* 2數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識整*1、數(shù)據(jù)：是信息的載體，能夠被計算機識別* 2。* 3* 4* 5* 6*7* 8*9、算法的時間復雜度T(n)：是該算法的時間耗費，它是該算法所求解問題規(guī)模n趨向*10和平均時間復雜度：由于算法中語句的頻度不僅與問題規(guī)模n有關(guān)，還與輸* 11、數(shù)據(jù)的運算：指對數(shù)據(jù)施加的操作。數(shù)據(jù)的運算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的* 12、線性表：由n(n0)個結(jié)點組成的有限序列。其邏輯特征反映了結(jié)點間一對一的*13、順序表：順* 14、單鏈表：每個結(jié)點有兩個域：一個值域data；另一個指針域next，用來指向該* 15、雙鏈

2、表：每個結(jié)點中增加了一個prior，用來指向該點的直接前趨結(jié)點。它是雙*16、循環(huán)鏈表：是一種首尾相接的鏈表。單循環(huán)鏈表形成一個* 15、雙鏈表：每個結(jié)點中增加了一個prior，用來指向該點的直接前趨結(jié)點。它是雙*16、循環(huán)鏈表：是一種首尾相接的鏈表。單循環(huán)鏈表形成一個next鏈環(huán)，而雙循環(huán)鏈*17密度為1，而鏈表密度小于1*18（stack* 19、LIFO表：即后進先出表，修改操作按后進先出的原則進行。譬如棧就是一種*20、順序棧：采用順結(jié)構(gòu)的棧，稱為順序棧*21* 22隊列只允許在一端進（queue*23、FIFO表：即先進先出表。譬如隊列就是一種FIFO*24* 25、循環(huán)隊列：為克服

3、順序隊列中假上溢現(xiàn)象，將向量空間想象為一個首尾相接的圓環(huán)這種向量稱為循環(huán)向量在其中的隊列稱為循環(huán)隊列*26、鏈隊列：采用鏈*an28、空白串：由一個或多個空格組成的串稱為空白串*29、空串：長度為零的串稱為空串，它不包括任何字符*30、順序串：串的順*31、鏈式串：串的鏈32、模式匹配：子串的定位運算又稱為串的模式匹配*33、對稱矩陣：元素滿足aij=aji（0i,jn）的矩陣*34、三角矩陣：主對角線以上或以下的元素（不包括對角線）均為常數(shù)的*34、三角矩陣：主對角線以上或以下的元素（不包括對角線）均為常數(shù)的矩陣*35、帶狀矩陣：所有非零元素均集中在以主對角線為中心的帶狀區(qū)域的矩陣*36、稀

4、疏矩陣：非零元素遠遠少于矩陣元素的矩陣* 37、廣義表：有n個元素a1,a2an組成的有限序列，其中n可以是原子或一個廣義表* 38、三元組表：若線性表順*39*40排序：假設(shè)給定含有n（R1,R2,Rn）的文件，其相應的關(guān)鍵字（K1，K2，,Kn）,則排序是確定一個排列（P(1),P(2),P(n)Kp(2)Kp(n)p(n)* 41、穩(wěn)定排序：假設(shè)在待排序的文件中，存在兩個或兩個以上* 42排序若排序算法所需的輔助空間并不依賴于問題的規(guī)模n，即輔助空間為* 43、堆：n個關(guān)鍵字序列K1，K2，,Kn，稱為堆，當且僅當序列滿足如下性質(zhì)K2i，且KiK2i1或KiK2i，且KiK2i1*44、

5、查找：即給定一個值K，在含有n個結(jié)點的表中找出關(guān)鍵字等于給定值K* 45、動態(tài)查找表：若在查找的同時對表做修改操作（和刪除，則相應的表稱* 46、靜態(tài)查找表：若在查找的同時不對表做修改操作（和刪除*47*48*50、散列函數(shù)：在關(guān)鍵字和表地址之間建立的對應關(guān)系h*51。*52* 53、裝填因子：設(shè)m和n分別表示表長和表中填入的結(jié)點數(shù)，則將=n/m* 1*50、散列函數(shù)：在關(guān)鍵字和表地址之間建立的對應關(guān)系h*51。*52* 53、裝填因子：設(shè)m和n分別表示表長和表中填入的結(jié)點數(shù)，則將=n/m* 1、索引、散列。 2*3、一個算法的效率可分為時間和空間效率。 4*5。 6*7、按順8、線性表中結(jié)點

6、的集合是有限的，結(jié)點間的關(guān)系是一對一的* 9、在n個結(jié)點的順序表中(刪除)一個結(jié)點需平均移動n/2（(n-1)/2）個（刪除）位置i* 10任意一結(jié)點的時間復雜度均為O(1)，因此，順序表也稱為隨機* 11、在民個結(jié)點的單鏈表中要刪除已知結(jié)點*p，需找到它的直接前趨結(jié)點的地址，其*12、在雙鏈有中要刪除已知結(jié)點*p，其時間復雜度為O(1)* 13、在單鏈表中要在已知結(jié)點*p一新結(jié)點，仍需找到*p的直接前趨結(jié)點的址，其時間復雜度為O(n)；而在雙鏈表中，完成同樣操作其時間復雜庶O(1)能遍歷鏈表。 15、在棧中存取數(shù)據(jù)遵從后進先出的原則，隊列中則是先進先出。* 16、棧結(jié)構(gòu)中，允*17、在有n個

7、元素的棧中，進棧和退棧操作的復雜度為O(1)和O(1)*18、設(shè)長度為n的鏈隊列用單循環(huán)鏈表示，若只設(shè)頭指針，則入隊和出隊操作的時間復雜度分別為O(n)和 O(1)；若只設(shè)尾指針，則O(1) 和O(1)。* 19、通常在程序中使用串可*17、在有n個元素的棧中，進棧和退棧操作的復雜度為O(1)和O(1)*18、設(shè)長度為n的鏈隊列用單循環(huán)鏈表示，若只設(shè)頭指針，則入隊和出隊操作的時間復雜度分別為O(n)和 O(1)；若只設(shè)尾指針，則O(1) 和O(1)。* 19、通常在程序中使用串可分為串變量和串常量；而串式串。 20* 21、成功匹配的起始位置稱為有效位移， 所有匹配不成功稱為無效位移；Naiv

8、estrMatch返回的是第1個有效位移*22、串的樸素匹配算法 的情況下需要比較字符的總次數(shù)為(n-m+1)m,n為主串長* 23、 對于數(shù)組 Anm， 其元素aij按行優(yōu)先與列優(yōu)先的地址之差為(i-1)(n-1)-(j-1)(m-1).(兩的LOC(a11)相同*24、特殊矩陣是指非零或零元素分布有一定規(guī)律的矩陣。 25數(shù)組方式順序和鏈式。 26* 27、任何一個非空廣義表的表頭是表中第一個元素，它可以是原子*28、表的長度是指廣義表元素的個數(shù)，表的深度是指廣義表展開后擴號的層數(shù)。 29樹中結(jié)點的最大層次稱為樹的深度（高度*30、若有一棵二叉排序樹，則按照中序遍歷順序?qū)a(chǎn)生一個有序序列。

9、31結(jié)構(gòu)，遍歷圖有深度優(yōu)先（DFT）和廣度優(yōu)先（BFT）等方法*34、有向圖G，其第i行的所有和等于頂點i的出度。 35果n個頂點的圖是一個環(huán)，則它有n個生成樹O(n2（O(n+e)* 38、圖的逆鄰接39、已知一個圖的鄰接矩陣表示，刪所有從第i個頂點出發(fā)的邊的方法是將鄰接矩陣的第i行全置0* 40n個頂點e條邊的圖用鄰接矩（鄰接（O(n+e)*41、圖的BFS生成樹的樹高比DFSO(n2)（O(elog2e)*43、稀疏（稠密）圖G的最小生成樹，最好用Kruskal（Prim*41、圖的BFS生成樹的樹高比DFSO(n2)（O(elog2e)*43、稀疏（稠密）圖G的最小生成樹，最好用Kru

10、skal（Prim）* 45、用Dijkstra算法求某一頂點到其余各頂點間最短路徑是按路徑長度遞增的次序* 46、拓撲排序算法是通過重復選擇具有0個前趨頂點的過程來完成的。 47*48、對n個頂點e條邊的圖進行拓撲排序，算法的時間復雜度為O(n+e)*49*50* 51、在堆、快速和歸并排序中，只考* 52、大多數(shù)排序算法都有兩個基本操作：比較兩上關(guān)鍵字的大小和改變指*53、散列地址。 54* 57、m階B-樹具有k個子樹的非葉子結(jié)點含有k1個關(guān)鍵字。 58、m階B-*59、中序遍歷二叉樹排序樹的結(jié)點就可以得到排好序的結(jié)點序列。 60。在B樹地*62、在各種查找方法中，平均查找長度與結(jié)點個數(shù)

11、n*64中，裝填因子*65、假設(shè)在有序線生表a20上進行二分查找，則比較一次查找的結(jié)點數(shù)為1*62、在各種查找方法中，平均查找長度與結(jié)點個數(shù)n*64中，裝填因子*65、假設(shè)在有序線生表a20上進行二分查找，則比較一次查找的結(jié)點數(shù)為1；比較兩*66的數(shù)據(jù)項，稱為主關(guān)鍵字，否則稱為次關(guān)鍵字。 67*68、文件有四種常用的組織：順序、索引、散列和多關(guān)鍵字文件。 *70、衡量文件操作質(zhì)量的重要標志是檢索功能的多少和速度的快慢。 71* 72、在索引非順序文件中采用動態(tài)索引時，為減* 73、在索引文件中，評價外存索引表的查找性能*74、常用的索引順序文件有ISAM（索引順序存取法）和VSAM（存取方法*

12、 75、ISAM*76、VSAM是一種索引順序文件的組織方式，采用B+*77* 78、在雙鏈表中*79、對于一棵滿二叉樹，若有m個葉子，則結(jié)點數(shù)為2m-1；若滿二叉樹的結(jié)點數(shù)為n，* 80、森林的后序遍歷序列正是相應二叉樹的中序遍歷序列，森林的先序遍歷序列正是*點若81、在一棵具有n個結(jié)點的完全二叉樹中，從樹根起，自上而下、自左至右地給所有為1*點若81、在一棵具有n個結(jié)點的完全二叉樹中，從樹根起，自上而下、自左至右地給所有為1。為i的結(jié)點，有左孩子，那么其右孩子為為i的結(jié)點，有父結(jié)點，那么其父結(jié)為i/2* 82、采用折半查找法進行查找的數(shù)據(jù)文件應為有序表和順結(jié)構(gòu)。 83* 84、在有n個結(jié)點

13、的二叉鏈表中，空指針域有n+1*85*86、在含胡n個結(jié)點的二叉排序樹上查找某結(jié)點時，其平均查找長度ASL的范圍估計是*87密度為1，而鏈表密度小于*88、在上三角矩陣中，它的下三角（不包括對角線）中的元素均為常數(shù)C中的重復元素C可個空間，其余的元素正好有n(n+1)/2個*1 *2*答：順*3*4、簡述算法復雜度（效率分析）* * 空間，也是總是規(guī)模*3*4、簡述算法復雜度（效率分析）* * 空間，也是總是規(guī)模n的函數(shù)，同樣用漸近空間復*5* *6 （ *7 其另一端的頭指針是rearnextnext(表結(jié)點)。這將給操作帶來很多方便*8*9、在順序棧中簡述進棧、退棧操作的過程*指針先加*9

14、、在順序棧中簡述進棧、退棧操作的過程*指針先加1，再送值到棧頂指針指向處。退棧時，先從棧頂指針指向處取值，棧頂指針再*10、在隊列中簡述入隊、出隊操作的過程（用“少和一個元素空間”的方法 * 在隊列不空時，可執(zhí)行出隊操作，此時先從隊頭指針指向處取值，隊頭指針再加1（取模*11*隊列結(jié)構(gòu)主要應用在需要“排除”的事件中，例如OS*12*13 *的相對次序（特別是相同排序碼的元素）*14*第i*89.排序前每一個位置上的排序碼43現(xiàn)在位于第5個位置上* 15、在快速排序算法中，能否用隊列代替棧來保存子文件首* 的地址（下標的地址（下標* 這才能地該子文件進行快速排序（排序過程又可能出現(xiàn)新的子文件*1

15、6、設(shè)有5000個無序的元素，希望用最快速度挑選出其中前10排序、堆排序、歸并排序、基數(shù)排序和 素，然后對堆進行調(diào)整，保證堆頂?shù)脑乜偸怯嘞略刂凶畲蟮模ɑ蜃钚?根據(jù)題意，只要選取前10* 17、將十進制的關(guān)鍵字用二進制表示，對基數(shù)排序所需的計算時間和附設(shè)空間分別有* 答：因為基數(shù)排序所需的計算時間不僅與文件的大小n*把n分放到各個人列中并重新收集起來所需的時間為O(n)，因此一遍排序所需時間復雜度為O(n+r)*若每個關(guān)鍵字有d位，則總共要d遍排序，所以基數(shù)排序的時間復雜度為O(d(n+r)。由于關(guān)鍵字的位數(shù)d直接與基數(shù)r以及最大關(guān)鍵字的值有關(guān)因此不同的r和關(guān)鍵字將需要* 18、有n個不同的

16、英文單詞，它們的長度相等，均為m，若n50，m5，試問什么排 * 19、試述順序查找法 * 19、試述順序查找法、折半查找法和分塊查找法對被查找的表中元素的要求，并求其*答：順序查找法：表中元素可以任意存放。查找成功的平均查找長度為 * 20的地址空間的長度為1000，如果散列函數(shù)只是簡單地抽取鍵字中間的3位作為散列函數(shù)* 21、假定有n個關(guān)鍵字，它們具有相同的散列函數(shù)值，用線性探測方法把這n* 答：由于線性探測的查找次數(shù)主要取決于裝填因子* 則在此情況下連續(xù)裝入n個具有相同的散列函數(shù)值的關(guān)鍵字所需的總探測次數(shù)為n=n(n+1)/2* 22、已知一個含有100表設(shè)計方案，要求它在等概率情況下查找成功的平均查找長度不超過*小，表中數(shù)越小或表越長* 的可能性就越小，查找效率也越高；反之，的可能性就越大，查找時間也越長* 若采用二次探測再散列，這樣在等概率情況下查找成功的平均查找長度為Sn-1/(1-)，根據(jù)題目要求有-1/(1-)3，即-的可能性就越大，查找時間也越長* 若采用二次探測再散列，這樣在等概率情況下查找成功的平均查找長度為Sn-1/(1-)，根據(jù)題目要求有-1/(1-)3，即-(1-* 可求得0.8.因為0.8，表中含有1