數據結構知識點概括第一章概論數據就是指能夠被計算機識別、存儲和加工處理的信息的載體。數據元素是數據的基本單位，可以由若干個數據項組成。數據項是具有獨立含義的最小標識單位。數據結構的定義：·邏輯結構：從邏輯結構上描述數據，獨立于計算機。·線性結構：一對一關系。·線性結構：多對多關系。·存儲結構：是邏輯結構用計算機語言的實現。·順序存儲結構：如數組。·鏈式存儲結構：如鏈表。·索引存儲結構：·稠密索引：每個結點都有索引項。·稀疏索引：每組結點都有索引項。·散列存儲結構：如散列表。·數據運算。·對數據的操作。定義在邏輯結構上，每種邏輯結構都有一個運算集合。·常用的有：檢索、插入、刪除、更新、排序。數據類型：是一個值的集合以及在這些值上定義的一組操作的總稱。·結構類型：由用戶借助于描述機制定義，是導出類型。抽象數據類型ADT：·是抽象數據的組織和與之的操作。相當于在概念層上描述問題。·優點是將數據和操作封裝在一起實現了信息隱藏。程序設計的實質是對實際問題選擇一種好的數據結構，設計一個好的算法。算法取決于數據結構。算法是一個良定義的計算過程，以一個或多個值輸入，并以一個或多個值輸出。評價算法的好壞的因素：·算法是正確的；·執行算法的時間；·執行算法的存儲空間（主要是輔助存儲空間）；·算法易于理解、編碼、調試。時間復雜度：是某個算法的時間耗費，它是該算法所求解問題規模n的函數。漸近時間復雜度：是指當問題規模趨向無窮大時，該算法時間復雜度的數量級。評價一個算法的時間性能時，主要標準就是算法的漸近時間復雜度。算法中語句的頻度不僅與問題規模有關，還與輸入實例中各元素的取值相關。時間復雜度按數量級遞增排列依次為：常數階O（1）、對數階O（log2n）、線性階O（n）、線性對數階O（nlog2n）、平方階O（n^2）、立方階O（n^3）、……k次方階O（n^k）、指數階O（2^n）。空間復雜度：是某個算法的空間耗費，它是該算法所求解問題規模n的函數。算法的時間復雜度和空間復雜度合稱算法復雜度。第二章線性表線性表是由n≥0個數據元素組成的有限序列。n=0是空表；非空表，只能有一個開始結點，有且只能有一個終端結點。線性表上定義的基本運算：·構造空表：Initlist（L）·求表長：Listlength（L）·取結點：GetNode（L，i）·查找：LocateNode（L，x）·插入：InsertList（L，x，i）·刪除：Delete（L，i）順序表是按線性表的邏輯結構次序依次存放在一組地址連續的存儲單元中。在存儲單元中的各元素的物理位置和邏輯結構中各結點相鄰關系是一致的。地址計算：LOCa（i）=LOCa（1）+（i-1）*d；（首地址為1）在順序表中實現的基本運算：·插入：平均移動結點次數為n/2；平均時間復雜度均為O（n）。·刪除：平均移動結點次數為（n-1）/2；平均時間復雜度均為O（n）。線性表的鏈式存儲結構中結點的邏輯次序和物理次序不一定相同，為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還存儲了其后繼結點的地址信息（即指針或鏈）。這兩部分信息組成鏈表中的結點結構。一個單鏈表由頭指針的名字來命名。單鏈表運算：·建立單鏈表·頭插法：s->next=head；head=s；生成的順序與輸入順序相反。平均時間復雜度均為O（n）。·尾插法：head=rear=null；if（head=null）head=s；elser->next=s；r=s；平均時間復雜度均為O（n）·加頭結點的算法：對開始結點的操作無需特殊處理，統一了空表和非空表。·查找·按序號：與查找位置有關，平均時間復雜度均為O（n）。·按值：與輸入實例有關，平均時間復雜度均為O（n）。·插入運算：p=GetNode（L，i-1）；s->next=p->next；p->next=s；平均時間復雜度均為O（n）·刪除運算：p=GetNode（L，i-1）；r=p->next；p->next=r->next；free（r）；平均時間復雜度均為O（n）單循環鏈表是一種首尾相接的單鏈表，終端結點的指針域指向開始結點或頭結點。鏈表終止條件是以指針等于頭指針或尾指針。采用單循環鏈表在實用中多采用尾指針表示單循環鏈表。優點是查找頭指針和尾指針的時間都是O（1），不用遍歷整個鏈表。雙鏈表就是雙向鏈表，就是在單鏈表的每個結點里再增加一個指向其直接前趨的指針域prior，形成兩條不同方向的鏈。由頭指針head惟一確定。雙鏈表也可以頭尾相鏈接構成雙（向）循環鏈表。雙鏈表上的插入和刪除時間復雜度均為O（1）。順序表和鏈表的比較：·基于空間：·順序表的存儲空間是靜態分配，存儲密度為1；適于線性表事先確定其大小時采用。·鏈表的存儲空間是動態分配，存儲密度＜1；適于線性表長度變化大時采用。·基于時間：·順序表是隨機存儲結構，當線性表的操作主要是查找時，宜采用。·以插入和刪除操作為主的線性表宜采用鏈表做存儲結構。·若插入和刪除主要發生在表的首尾兩端，則宜采用尾指針表示的單循環鏈表。第三章棧和隊列棧（Stack）是僅限制在表的一端進行插入和刪除運算的線性表，稱插入、刪除這一端為棧頂，另一端稱為棧底。表中無元素時為空棧。棧的修改是按后進先出的原則進行的，我們又稱棧為LIFO表（LastInFirstOut）。通常棧有順序棧和鏈棧兩種存儲結構。棧的基本運算有六種：·構造空棧：InitStack（S）·判棧空：StackEmpty（S）·判棧滿：StackFull（S）·進棧：Push（S，x）·退棧：Pop（S）·取棧頂元素：StackTop（S）在順序棧中有“上溢”和“下溢”的現象。·“上溢”是棧頂指針指出棧的外面是出錯狀態。·“下溢”可以表示棧為空棧，因此用來作為控制轉移的條件。順序棧中的基本操作有六種：·構造空棧·判棧空·判棧滿·進棧·退棧·取棧頂元素鏈棧則沒有上溢的限制，因此進棧不要判棧滿。鏈棧不需要在頭部附加頭結點，只要有鏈表的頭指針就可以了。鏈棧中的基本操作有五種：·構造空棧·判棧空·進棧·退棧·取棧頂元素隊列（Queue）是一種運算受限的線性表，插入在表的一端進行，而刪除在表的另一端進行，允許刪除的一端稱為隊頭（front），允許插入的一端稱為隊尾（rear），隊列的操作原則是先進先出的，又稱作FIFO表（FirstInFirstOut）.隊列也有順序存儲和鏈式存儲兩種存儲結構。隊列的基本運算有六種：·置空隊：InitQueue（Q）·判隊空：QueueEmpty（Q）·判隊滿：QueueFull（Q）·入隊：EnQueue（Q，x）·出隊：DeQueue（Q）·取隊頭元素：QueueFront（Q）順序隊列的“假上溢”現象：由于頭尾指針不斷前移，超出向量空間。這時整個向量空間及隊列是空的卻產生了“上溢”現象。為了克服“假上溢”現象引入循環向量的概念，是把向量空間形成一個頭尾相接的環形，這時隊列稱循環隊列。判定循環隊列是空還是滿，方法有三種：·一種是另設一個布爾變量來判斷；·第二種是少用一個元素空間，入隊時先測試（（rear+1）%m=front）？滿：空；·第三種就是用一個計數器記錄隊列中的元素的總數。隊列的鏈式存儲結構稱為鏈隊列，一個鏈隊列就是一個操作受限的單鏈表。為了便于在表尾進行插入（入隊）的操作，在表尾增加一個尾指針，一個鏈隊列就由一個頭指針和一個尾指針唯一地確定。鏈隊列不存在隊滿和上溢的問題。在鏈隊列的出隊算法中，要注意當原隊中只有一個結點時，出隊后要同進修改頭尾指針并使隊列變空。第四章串串是零個或多個字符組成的有限序列。·空串：是指長度為零的串，也就是串中不包含任何字符（結點）。·空白串：指串中包含一個或多個空格字符的串。·在一個串中任意個連續字符組成的子序列稱為該串的子串，包含子串的串就稱為主串。·子串在主串中的序號就是指子串在主串中首次出現的位置。·空串是任意串的子串，任意串是自身的子串。串分為兩種：·串常量在程序中只能引用不能改變；·串變量的值可以改變。串的基本運算有：·求串長strlen（char*s）·串復制strcpy（char*to，char*from）·串聯接strcat（char*to，char*from）·串比較charcmp（char*s1，char*s2）·字符定位strchr（char*s，charc）串是特殊的線性表（結點是字符），所以串的存儲結構與線性表的存儲結構類似。串的順序存儲結構簡稱為順序串。順序串又可按存儲分配的不同分為：·靜態存儲分配：直接用定長的字符數組來定義。優點是涉及串長的操作速度快，但不適合插入、鏈接操作。·動態存儲分配：是在定義串時不分配存儲空間，需要使用時按所需串的長度分配存儲單元。串的鏈式存儲就是用單鏈表的方式存儲串值，串的這種鏈式存儲結構簡稱為鏈串。鏈串與單鏈表的差異只是它的結點數據域為單個字符。為了解決“存儲密度”低的狀況，可以讓一個結點存儲多個字符，即結點的大小。順序串上子串定位的運算：又稱串的“模式匹配”或“串匹配”，是在主串中查找出子串出現的位置。在串匹配中，將主串稱為目標（串），子串稱為模式（串）。這是比較容易理解的，串匹配問題就是找出給定模式串P在給定目標串T中首次出現的有效位移或者是全部有效位移。最壞的情況下時間復雜度是O（（n-m+1）m），假如m與n同階的話則它是O（n^2）。鏈串上的子串定位運算位移是結點地址而不是整數第五章多維數組數組一般用順序存儲的方式表示。存儲的方式有：·行優先順序，也就是把數組逐行依次排列。PASCAL、C·列優先順序，就是把數組逐列依次排列。FORTRAN地址的計算方法：·按行優先順序排列的數組：LOCa（ij）=LOCa（11）+（（i-1）*n+（j-1））*d.·按列優先順序排列的數組：LOCa（ij）=LOCa（11）+（（j-1）*n+（i-1））*d.矩陣的壓縮存儲：為多個相同的非零元素分配一個存儲空間；對零元素不分配空間。特殊矩陣的概念：所謂特殊矩陣是指非零元素或零元素分布有一定規律的矩陣。稀疏矩陣的概念：一個矩陣中若其非零元素的個數遠遠小于零元素的個數，則該矩陣稱為稀疏矩陣。特殊矩陣的類型：·對稱矩陣：滿足a（ij）=a（ji）。元素總數n（n+1）/2.I=max（i，j），J=min（i，j），LOCa（ij）=LOC（sa[0]）+（I*（I+1）/2+J）*d.·三角矩陣：·上三角陣：k=i*（2n-i+1）/2+j-i，LOCa（ij）=LOC（sa[0]）+k*d.·下三角陣：k=i*（i+1）/2+j，LOCa（ij）=LOC（sa[0]）+k*d.·對角矩陣：k=2i+j，LOCa（ij）=LOC（sa[0]）+k*d.稀疏矩陣的壓縮存儲方式用三元組表把非零元素的值和它所在的行號列號做為一個結點存放在一起，用這些結點組成的一個線性表來表示。但這種壓縮存儲方式將失去隨機存儲功能。加入行表記錄每行的非零元素在三元組表中的起始位置，即帶行表的三元組表。第六章樹樹是n個結點的有限集合，非空時必須滿足：只有一個稱為根的結點；其余結點形成m個不相交的子集，并稱根的子樹。根是開始結點；結點的子樹數稱度；度為0的結點稱葉子（終端結點）；度不為0的結點稱分支結點（非終端結點）；除根外的分支結點稱內部結點；有序樹是子樹有左，右之分的樹；無序樹是子樹沒有左，右之分的樹；森林是m個互不相交的樹的集合；樹的四種不同表示方法：·樹形表示法；·嵌套集合表示法；·凹入表示法·廣義表表示法。二叉樹的定義：是n≥0個結點的有限集，它是空集（n=0）或由一個根結點及兩棵互不相交的分別稱作這個根的左子樹和右子樹的二叉樹組成。二叉樹不是樹的特殊情形，與度數為2的有序樹不同。二叉樹的4個重要性質：·二叉樹上第i層上的結點數目最多為2^（i-1）（i≥1）。；·深度為k的二叉樹至多有（2^k）-1個結點（k≥1）；·在任意一棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則n0=n2+1；·具有n個結點的完全二叉樹的深度為int（log2n）+1.滿二叉樹是一棵深度為k，結點數為（2^k）-1的二叉樹；完全二叉樹是滿二叉樹在最下層自右向左去處部分結點；二叉樹的順序存儲結構就是把二叉樹的所有結點按照層次順序存儲到連續的存儲單元中。（存儲前先將其畫成完全二叉樹）樹的存儲結構多用的是鏈式存儲。BinTNode的結構為lchild|data|rchild，把所有BinTNode類型的結點，加上一個指向根結點的BinTree型頭指針就構成了二叉樹的鏈式存儲結構，稱為二叉鏈表。它就是由根指針root唯一確定的。共有2n個指針域，n+1個空指針。根據訪問結點的次序不同可得三種遍歷：先序遍歷（前序遍歷或先根遍歷），中序遍歷（或中根遍歷）、后序遍歷（或后根遍歷）。時間復雜度為O（n）。利用二叉鏈表中的n+1個空指針域來存放指向某種遍歷次序下的前趨結點和后繼結點的指針，這些附加的指針就稱為“線索”，加上線索的二叉鏈表就稱為線索鏈表。線索使得查找中序前趨和中序后繼變得簡單有效，但對于查找指定結點的前序前趨和后序后繼并沒有什么作用。樹和森林及二叉樹的轉換是唯一對應的。轉換方法：·樹變二叉樹：兄弟相連，保留長子的連線。·二叉樹變樹：結點的右孩子與其雙親連。·森林變二叉樹：樹變二叉樹，各個樹的根相連。樹的存儲結構：·有雙親鏈表表示法：結點data|parent，對于求指定結點的雙親或祖先十分方便，但不適于求指定結點的孩子及后代。·孩子鏈表表示法：為樹中每個結點data|next設置一個孩子鏈表firstchild，并將data|firstchild存放在一個向量中。·雙親孩子鏈表表示法：將雙親鏈表和孩子鏈表結合。·孩子兄弟鏈表表示法：結點結構leftmostchild|data|rightsibing，附加兩個分別指向該結點的最左孩子和右鄰兄弟的指針域。樹的前序遍歷與相對應的二叉樹的前序遍歷一致；樹的后序遍歷與相對應的二叉樹的中序遍歷一致。樹的帶權路徑長度是樹中所有葉結點的帶權路徑長度之和。樹的帶權路徑長度最小的二叉樹就稱為最優二叉樹（即哈夫曼樹）。在葉子的權值相同的二叉樹中，完全二叉樹的路徑長度最短。哈夫曼樹有n個葉結點，共有2n-1個結點，沒有度為1的結點，這類樹又稱為嚴格二叉樹。變長編碼技術可以使頻度高的字符編碼短，而頻度低的字符編碼長，但是變長編碼可能使解碼產生二義性。如00、01、0001這三個碼無法在解碼時確定是哪一個，所以要求在字符編碼時任一字符的編碼都不是其他字符編碼的前綴，這種碼稱為前綴碼（其實是非前綴碼）。哈夫曼樹的應用最廣泛地是在編碼技術上，它能夠容易地求出給定字符集及其概率分布的最優前綴碼。哈夫曼編碼的構造很容易，只要畫好了哈夫曼樹，按分支情況在左路徑上寫代碼0，右路徑上寫代碼1，然后從上到下到葉結點的相應路徑上的代碼的序列就是該結點的最優前綴碼。第七章圖圖的邏輯結構特征就是其結點（頂點）的前趨和后繼的個數都是沒有限制的，即任意兩個結點之間之間都可能相關。圖GraphG=（V，E），V是頂點的有窮非空集合，E是頂點偶對的有窮集。有向圖Digraph：每條邊有方向；無向圖Undigraph：每條邊沒有方向。有向完全圖：具有n*（n-1）條邊的有向圖；無向完全圖：具有n*（n-1）/2條邊的無向圖；有根圖：有一個頂點有路徑到達其它頂點的有向圖；簡單路徑：是經過頂點不同的路徑；簡單回路是開始和終端重的簡單路徑；網絡：是帶權的圖。圖的存儲結構：·鄰接矩陣表示法：用一個n階方陣來表示圖的結構是唯一的，適合稠密圖。·無向圖：鄰接矩陣是對稱的。·有向圖：行是出度，列是入度。建立鄰接矩陣算法的時間是O（n+n^2+e），其時間復雜度為O（n^2）·鄰接表表示法：用頂點表和鄰接表構成不是唯一的，適合稀疏圖。·頂點表結構vertex|firstedge，指針域存放鄰接表頭指針。·鄰接表：用頭指針確定。·無向圖稱邊表；·有向圖又分出邊表和逆鄰接表；·鄰接表結點結構為adjvex|next，時間復雜度為O（n+e）。，空間復雜度為O（n+e）。。圖的遍歷：·深度優先遍歷：借助于鄰接矩陣的列。使用棧保存已訪問結點。·廣度優先遍歷：借助于鄰接矩陣的行。使用隊列保存已訪問結點。生成樹的定義：若從圖的某個頂點出發，可以系統地訪問到圖中所有頂點，則遍歷時經過的邊和圖的所有頂點構成的子圖稱作該圖的生成樹。最小生成樹：圖的生成樹不唯一，從不同的頂點出發可得到不同的生成樹，把權值最小的生成樹稱為最小生成樹（MST）。構造最小生成樹的算法：·Prim算法的時間復雜度為O（n^2）與邊數無關適于稠密圖。·Kruskal算法的時間復雜度為O（lge），主要取決于邊數，較適合于稀疏圖。最短路徑的算法：·Dijkstra算法，時間復雜度為O（n^2）。·類似于prim算法。拓撲排序：是將有向無環圖G中所有頂點排成一個線性序列，若<u，v>∈E（G），則在線性序列u在v之前，這種線性序列稱為拓撲序列。拓撲排序也有兩種方法：·無前趨的頂點優先，每次輸出一個無前趨的結點并刪去此結點及其出邊，最后得到的序列即拓撲序列。·無后繼的結點優先：每次輸出一個無后繼的結點并刪去此結點及其入邊，最后得到的序列是逆拓撲序列。第八章排序記錄中可用某一項來標識一個記錄，則稱為關鍵字項，該數據項的值稱為關鍵字。排序是使文件中的記錄按關鍵字遞增（或遞減）次序排列起來。·基本操作：比較關鍵字大小；改變指向記錄的指針或移動記錄。·存儲結構：順序結構、鏈表結構、索引結構。經過排序后這些具有相同關鍵字的記錄之間的相對次序保持不變，則稱這種排序方法是穩定的，否則排序算法是不穩定的。排序過程中不涉及數據的內、外存交換則稱之為“內部排序”（內排序），反之，若存在數據的內外存交換，則稱之為外排序。內部排序方法可分五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。評價排序算法好壞的標準主要有兩條：執行時間和所需的輔助空間，另外算法的復雜程序也是要考慮的一個因素。插入排序：·直接插入排序：·逐個向前插入到合適位置。·哨兵（監視哨）有兩個作用：·作為臨變量存放R[i]·是在查找循環中用來監視下標變量j是否越界。·直接插入排序是就地的穩定排序。時間復雜度為O（n^2），比較次數為（n+2）（n-1）/2；移動次數為（n+4）（n-1）/2；·希爾排序：·等間隔的數據比較并按要求順序排列，最后間隔為1.·希爾排序是就地的不穩定排序。時間復雜度為O（n^1.25），比較次數為（n^1.25）；移動次數為（1.6n^1.25）；交換排序：·冒泡排序：·自下向上確定最輕的一個。·自上向下確定最重的一個。·自下向上確定最輕的一個，后自上向下確定最重的一個。·冒泡排序是就地的穩定排序。時間復雜度為O（n^2），比較次數為n（n-1）/2；移動次數為3n（n-1）/2；·快速排序：·以第一個元素為參考基準，設定、動兩個指針，發生交換后指針交換位置，直到指針重合。重復直到排序完成。·快速排序是非就地的不穩定排序。時間復雜度為O（nlog2n），比較次數為n（n-1）/2；選擇排序：·直接選擇排序：·選擇最小的放在比較區前。·直接選擇排序就地的不穩定排序。時間復雜度為O（n^2）。比較次數為n（n-1）/2；·堆排序

·建堆：按層次將數據填入完全二叉樹，從int（n/2）處向前逐個調整位置。·然后將樹根與最后一個葉子交換值并斷開與樹的連接并重建堆，直到全斷開。·堆排序是就地不穩定的排序，時間復雜度為O（nlog2n），不適宜于記錄數較少的文件。歸并排序：·先兩個一組排序，形成（n+1）/2組，再將兩組并一組，直到剩下一組為止。·歸并排序是非就地穩定排序，時間復雜度是O（nlog2n），分配排序：·箱排序：·按關鍵字的取值范圍確定箱子數，按關鍵字投入箱子，鏈接所有非空箱。·箱排序的平均時間復雜度是線性的O（n）。·基數排序：·從低位到高位依次對關鍵字進行箱排序。·基數排序是非就穩定的排序，時間復雜度是O（d*n+d*rd）。各種排序方法的比較和選擇：·待排序的記錄數目n；n較大的要用時間復雜度為O（nlog2n）的排序方法；·記錄的大小（規模）；記錄大最好用鏈表作為存儲結構，而快速排序和堆排序在鏈表上難于實現；·關鍵字的結構及其初始狀態；·對穩定性的要求；·語言工具的條件；·存儲結構；·時間和輔助空間復雜度。第九章查找查找的同時對表做修改操作（如插入或刪除）則相應的表稱之為動態查找表，否則稱之為靜態查找表。衡量查找算法效率優劣的標準是在查找過程中對關鍵字需要執行的平均比較次數（即平均查找長度ASL）。線性表查找的方法：·順序查找：逐個查找，ASL=（n+1）/2；·二分查找：取中點int（n/2）比較，若小就比左區間，大就比右區間。用二叉判定樹表示。ASL=（∑（每層結點數*層數））/N.·分塊查找。要求“分塊有序”，將表分成若干塊內部不一定有序，并抽取各塊中的最大關鍵字及其位置建立有序索引表。二叉排序樹（BST）定義是：二叉排序樹是空樹或者滿足如下性質的二叉樹：·若它的左子樹非空，則左子樹上所有結點的值均小于根結點的值；·若它的右子樹非空，則右子樹上所有結點的值均大于根結點的值；·左、右子樹本身又是一棵二叉排序樹。二叉排序樹的插入、建立、刪除的算法平均時間性能是O（nlog2n）。二叉排序樹的刪除操作可分三種情況進行處理：·*P是葉子，則直接刪除*P，即將*P的雙親*parent中指向*P的指針域置空即可。·*P只有一個孩子*child，此時只需將*child和*p的雙親直接連接就可刪去*p.·*p有兩個孩子，則先將*p結點的中序后繼結點的數據到*p，刪除中序后繼結點。關于B-樹（多路平衡查找樹）。它適合在磁盤等直接存取設備上組織動態的查找表，是一種外查找算法。建立的方式是從下向上拱起。散列技術：將結點按其關鍵字的散列地址存儲到散列表的過程稱為散列。散列函數的選擇有兩條標準：簡單和均勻。常見的散列函數構的造方法：·平方取中法：hash=int（（x^2）%100）·除余法：表長為m，hash=x%m·相乘取整法：hash=int（m*（x*A-int（x*A））；A=0.618·隨機數法：hash=random（x）。處理沖突的方法：·開放定址法：·一般形式為hi=（h（key）+di）%m1≤i≤m-1，開放定址法要求散列表的裝填因子α≤1.·開放定址法類型：·線性探查法：address=（hash（x）+i）%m；·二次探查法：address=（hash（x）+i^2）%m；·雙重散列法：address=（hash（x）+i*hash（y））%m；·拉鏈法：·是將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中。·拉鏈法的優點：·拉鏈法處理沖突簡單，且無堆積現象；·鏈表上的結點空間是動態申請的適于無法確定表長的情況；·拉鏈法中α可以大于1，結點較大時其指針域可忽略，因此節省空間；·拉鏈法構造的散列表刪除結點易實現。·拉鏈法也有缺點：當結點規模較小時，用拉鏈法中的指針域也要占用額外空間，還是開放定址法省空間。第十章排序10.1排序的基本概念10.2插入排序10.3選擇排序10.4交換排序本章主要知識點：排序的基本概念和衡量排序算法優劣的標準，其中衡量標準有算法的時間復雜度、空間復雜度和穩定性直接插入排序，希爾排序直接選擇排序，堆排序冒泡排序，快速排序10.1排序的基本概念1.排序是對數據元素序列建立某種有序排列的過程。2.排序的目的：便于查找。3.關鍵字是要排序的數據元素集合中的一個域，排序是以關鍵字為基準進行的。關鍵字分主關鍵字和次關鍵字兩種。對要排序的數據元素集合來說，如果關鍵字滿足數據元素值不同時該關鍵字的值也一定不同，這樣的關鍵字稱為主關鍵字。不滿足主關鍵字定義的關鍵字稱為次關鍵字。4.排序的種類：分為內部排序和外部排序兩大類。若待排序記錄都在內存中，稱為內部排序；若待排序記錄一部分在內存，一部分在外存，則稱為外部排序。注：外部排序時，要將數據分批調入內存來排序，中間結果還要及時放入外存，顯然外部排序要復雜得多。5.排序算法好壞的衡量標準：(1)時間復雜度——它主要是分析記錄關鍵字的比較次數和記錄的移動次數。(2)空間復雜度——算法中使用的內存輔助空間的多少。(3)穩定性——若兩個記錄A和B的關鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩定的。10.2插入排序插入排序的基本思想是：每步將一個待排序的對象，按其關鍵字大小，插入到前面已經排好序的一組對象的適當位置上，直到對象全部插入為止。簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。常用的插入排序有：直接插入排序和希爾排序兩種。10.2.11、其基本思想是：順序地把待排序的數據元素按其關鍵字值的大小插入到已排序數據元素子集合的適當位置。例1：關鍵字序列T=（13，6，3，31，9，27，5，11），請寫出直接插入排序的中間過程序列。初始關鍵字序列：【13】,6,3,31,9,27,5,11第一次排序：【6,13】,3,31,9,27,5,11第二次排序：【3,6,13】,31,9,27,5,11第三次排序：【3,6,13，31】,9,27,5,11第四次排序：【3,6,9,13，31】,27,5,11第五次排序：【3,6,9,13，27,31】,5,11第六次排序：【3,5,6,9,13，27,31】,11第七次排序：【3,5,6,9,11，13，27,31】注：方括號[]中為已排序記錄的關鍵字，下劃橫線的關鍵字表示它對應的記錄后移一個位置。2.直接插入排序算法publicstaticvoidinsertSort(int[]a){ inti,j,temp; intn=a.Length; for(i=0;i<n-1;i++){ temp=a[i+1]; j=i; while(j>-1&&temp<a[j]){ a[j+1]=a[j]; j--; } a[j+1]=temp; }}初始關鍵字序列：【13】,6,3,31,9,27,5,11第一次排序：【6,13】,3,31,9,27,5,11第二次排序：【3,6,13】,31,9,27,5,113、直接插入排序算法分析(1)時間效率：當數據有序時，執行效率最好，此時的時間復雜度為O(n)；當數據基本反序時，執行效率最差，此時的時間復雜度為O(n2)。所以當數據越接近有序，直接插入排序算法的性能越好。(2)空間效率：僅占用1個緩沖單元——O（1）(3)算法的穩定性：穩定8.2.2希爾（shell）排序（又稱縮小增量排序）1、基本思想：把整個待排序的數據元素分成若干個小組，對同一小組內的數據元素用直接插入法排序；小組的個數逐次縮小，當完成了所有數據元素都在一個組內的排序后排序過程結束。2、技巧：小組的構成不是簡單地“逐段分割”，而是將相隔某個增量d的記錄組成一個小組,讓增量d逐趟縮短（例如依次取5,3,1），直到d＝1為止。3、優點：讓關鍵字值小的元素能很快前移，且序列若基本有序時，再用直接插入排序處理，時間效率會高很多。例2：設待排序的序列中有12個記錄，它們的關鍵字序列T=(65，34，25，87，12，38，56，46，14，77，92，23），請寫出希爾排序的具體實現過程。publicstaticvoidshellSort(int[]a,int[]d,intnumOfD){ inti,j,k,m,span; inttemp; intn=a.Length; for(m=0;m<numOfD;m++){ //共numOfD次循環 span=d[m]; //取本次的增量值 for(k=0;k<span;k++){ //共span個小組 for(i=k;i<n-span;i=i+span){ temp=a[i+span]; j=i; while(j>-1&&temp<a[j]){ a[j+span]=a[j]; j=j-span; } a[j+span]=temp; } } }}算法分析：開始時d的值較大，子序列中的對象較少，排序速度較快；隨著排序進展，d值逐漸變小，子序列中對象個數逐漸變多，由于前面工作的基礎，大多數記錄已基本有序，所以排序速度仍然很快。時間效率：O(n(log2n)2)空間效率：O（1）——因為僅占用1個緩沖單元算法的穩定性：不穩定練習：1.欲將序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的關鍵碼按字母升序重排，則初始d為4的希爾排序一趟的結果是？答：原始序列：Q,H,C,Y,P,A,M,S,R,D,F,Xshell一趟后：P,A,C,S,Q,D,F,X,R,H,M,Y2.以關鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫出執行希爾排序（取d=5,3,1）算法的各趟排序結束時，關鍵字序列的狀態。解：原始序列:256，301，751，129，937，863，742，694，076，438希爾排序第一趟d=5256301694076438863742751129937第二趟d=3076301129256438694742751863937第三趟d=107612925630143869474275186393710.3選擇排序選擇排序的基本思想是：每次從待排序的數據元素集合中選取關鍵字最小（或最大）的數據元素放到數據元素集合的最前（或最后），數據元素集合不斷縮小，當數據元素集合為空時選擇排序結束。常用的選擇排序算法：（1）直接選擇排序（2）堆排序10.3.1直接選擇排序1、其基本思想每經過一趟比較就找出一個最小值，與待排序列最前面的位置互換即可。（即從待排序的數據元素集合中選取關鍵字最小的數據元素并將它與原始數據元素集合中的第一個數據元素交換位置；然后從不包括第一個位置的數據元素集合中選取關鍵字最小的數據元素并將它與原始數據集合中的第二個數據元素交換位置；如此重復，直到數據元素集合中只剩一個數據元素為止。）2、優缺點優點：實現簡單缺點：每趟只能確定一個元素，表長為n時需要n-1趟例3：關鍵字序列T=（21，25，49，25*，16，08），請給出直接選擇排序的具體實現過程。原始序列：21，25，49，25*，16，08第1趟08，25，49，25*，16，21第2趟08，16,49，25*，25，21第3趟08，16,21，25*，25，49第4趟08，16,21，25*，25，49第5趟08，16,21，25*，25，49publicstaticvoidselectSort(int[]a){ inti,j,small; inttemp; intn=a.Length; for(i=0;i<n-1;i++){ small=i; //設第i個數據元素最小 for(j=i+1;j<n;j++) //尋找最小的數據元素 if(a[j]<a[small])small=j; //記住最小元素的下標 if(small!=i){ //當最小元素的下標不為i時交換位置 temp=a[i]; a[i]=a[small]; a[small]=temp; } }}3、算法分析時間效率：O(n2)——雖移動次數較少，但比較次數仍多。空間效率：O（1）——沒有附加單元（僅用到1個temp)算法的穩定性：不穩定4、穩定的直接選擇排序算法例：關鍵字序列T=（21，25，49，25*，16，08），請給出穩定的直接選擇排序的具體實現過程。原始序列：21，25，49，25*，16，08第1趟08,21,25,49,25*,16第2趟08，16,21，25，49，25*第3趟08，16,21，25，49，25*第4趟08，16,21，25，49，25*第5趟08，16,21，25，25*，49publicstaticvoidselectSort2(int[]a){ inti,j,small; inttemp; intn=a.Length; for(i=0;i<n-1;i++){ small=i; for(j=i+1;j<n;j++){ //尋找最小的數據元素if(a[j]<a[small])small=j; //記住最小元素的下標 } if(small!=i){ temp=a[small]; for(j=small;j>i;j--)//把該區段尚未排序元素依次后移 a[j]=a[j-1]; a[i]=temp; //插入找出的最小元素 } }}8.3.2堆排序1.什么是堆？2.怎樣建堆？3.怎樣堆排序？堆的定義：設有n個數據元素的序列k0，k1，…，kn-1，當且僅當滿足下述關系之一時，稱之為堆。解釋：如果讓滿足以上條件的元素序列（k０，k１，…，kn－１）順次排成一棵完全二叉樹，則此樹的特點是：樹中所有結點的值均大于（或小于）其左右孩子，此樹的根結點（即堆頂）必最大（或最小）。例4：有序列T1=（08,25,49,46,58,67）和序列T2=（91,85,76,66,58,67,55）,判斷它們是否“堆”？2.怎樣建堆？步驟：從第一個非終端結點開始往前逐步調整，讓每個雙親大于（或小于）子女，直到根結點為止。終端結點（即葉子）沒有任何子女，無需單獨調整例：關鍵字序列T=(21，25，49，25*，16，08），請建最大堆。解：為便于理解，先將原始序列畫成完全二叉樹的形式：這樣可以很清晰地從(n-1-1)/2開始調整。publicstaticvoidcreateHeap(int[]a,intn,inth){ inti,j,flag; inttemp; i=h; j=2*i+1; //j為i結點的左孩子結點的下標 temp=a[i]; flag=0; while(j<n&&flag!=1){ //尋找左右孩子結點中的較大者,j為其下標 if(j<n-1&&a[j]<a[j+1])j++; if(temp>=a[j]) //a[i]>=a[j] flag=1; //標記結束篩選條件 else{ //否則把a[j]上移 a[i]=a[j]; i=j; j=2*i+1; } } a[i]=temp; }利用上述createHeap（a,n,h）函數，初始化創建最大堆的過程就是從第一個非葉子結點a[i]開始，到根結點a[0]為止，循環調用createHeap（a,n,h）的過程。初始化創建最大堆算法如下：publicstaticvoidinitCreateHeap(int[]a){ intn=a.Length; for(inti=(n-1-1)/2;i>=0;i--) createHeap(a,n,i);}3.怎樣進行整個序列的堆排序？*基于初始堆進行堆排序的算法步驟：堆的第一個對象a[0]具有最大的關鍵碼，將a[0]與a[n-1]對調，把具有最大關鍵碼的對象交換到最后; 再對前面的n-1個對象，使用堆的調整算法，重新建立堆（調整根結點使之滿足最大堆的定義）。結果具有次最大關鍵碼的對象又上浮到堆頂，即a[0]位置; 再對調a[0]和a[n-2]，然后對前n-2個對象重新調整，…如此反復，最后得到全部排序好的對象序列。例5：對剛才建好的最大堆進行排序：publicstaticvoidheapSort(int[]a){ inttemp; intn=a.Length; initCreateHeap(a); //初始化創建最大堆 for(inti=n-1;i>0;i--){ //當前最大堆個數每次遞減1 //把堆頂a[0]元素和當前最大堆的最后一個元素交換 temp=a[0]; a[0]=a[i]; a[i]=temp; createHeap(a,i,0); //調整根結點滿足最大堆 }}4、堆排序算法分析：時間效率：O(nlog2n)。空間效率：O(1)。穩定性：不穩定。練習1：以下序列是堆的是（）{75,65,30,15,25,45,20,10}B.{75,65,45,10,30,25,20,15}C.{75,45,65,30,15,25,20,10}D.{75,45,65,10,25,30,20,15}練習2：有一組數據{15,9,7,8,20,1,7*,4}，建成的最小堆為（）。A.{1,4,8,9,20,7,15,7*}B.{1,7,15,7*,4,8,20,9}C.{1,4,7,8,20,15,7*,9}D.以上都不對練習3：已知序列{503，87，512，61，908，170，897，275，653，462}，寫出采用堆排序對該序列作非遞減排列時的排序過程。排序好的序列為：61，87，170，275，462，503，512，653，897，90810.4交換排序交換排序的基本思想是：利用交換數據元素的位置進行排序的方法。交換排序的主要算法有：1)冒泡排序2)快速排序10.4.1冒泡排序1、基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規則交換。2、優點：每趟結束時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；一旦下趟沒有交換發生，還可以提前結束排序。例：關鍵字序列T=(21，25，49，25*，16，08），請按從小到大的順序，寫出冒泡排序的具體實現過程。初態：21，25，49，25*，16，08第1趟21，25，25*，16，08，49第2趟21，25，16，08，25*，49第3趟21，16，08，25，25*，49第4趟16，08，21，25，25*，49第5趟08，16，21，25，25*，493、冒泡排序算法publicstaticvoidbubbleSort(int[]a){ inti,j,flag=1; inttemp; intn=a.Length; for(i=1;i<n&&flag==1;i++){ flag=0; for(j=0;j<n-i;j++){ if(a[j]>a[j+1]){ flag=1; temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } }}4、冒泡排序的算法分析時間效率：O（n2)—因為要考慮最壞情況（數據元素全部逆序），當然最好情況是數據元素已全部排好序，此時循環n-1次，時間復雜度為O（n)空間效率：O（1）—只在交換時用到一個緩沖單元穩定性：穩定—25和25*在排序前后的次序未改變練習：關鍵字序列T=(31，15，9，25，16，28），請按從小到大的順序，寫出冒泡排序的具體實現過程。初態：31，15，9，25，16，28第1趟15，9，25，16，28，31第2趟9，15，16，25，28，31第3趟9，15，16，25，28，311、基本思想：設數組a中存放了n個數據元素，low為數組的低端下標，high為數組的高端下標，從數組a中任取一個元素（通常取a[low]）做為標準元素，以該標準元素調整數組a中其他各個元素的位置，使排在標準元素前面的元素均小于標準元素，排在標準元素后面的均大于或等于標準元素。這樣一次排序過程結束后，一方面將標準元素放在了未來排好序的數組中該標準元素應位于的位置上，另一方面將數組中的元素以標準元素為中心分成了兩個子數組，位于標準元素左邊子數組中的元素均小于標準元素，位于標準元素右邊子數組中的元素均大于等于或標準元素。對這兩個子數組中的元素分別再進行方法類同的遞歸快速排序。算法的遞歸出口條件是low≥high。例、關鍵字序列T=(60，55，48，37，10，90，84，36），請按從小到大的順序，寫出快速排序的具體實現過程。快速排序算法各次快速排序過程3、快速排序算法publicstaticvoidquickSort(int[]a,intlow,inthigh){ inti,j; inttemp; i=low; j=high; temp=a[low]; //取第一個元素為標準數據元素 while(i<j){//在數組的右端掃描 while(i<j&&temp<=a[j])j--; if(i<j){ a[i]=a[j]; i++; }//在數組的左端掃描while(i<j&&a[i]<temp)i++; if(i<j){ a[j]=a[i]; j--; }}a[i]=temp;if(low<i)quickSort(a,low,i-1); //對左端子集合遞歸if(i<high)quickSort(a,j+1,high);//對右端子集合遞歸}4、快速排序算法分析：時間效率：一般情況下時間復雜度為O(nlog2n)，最壞情況是數據元素已全部正序或反序有序，此時每次標準元素都把當前數組分成一個大小比當前數組小1的子數組，此時時間復雜度為O(n2)空間效率：O（log2n）—因為遞歸要用棧穩定性：不穩定—因為有跳躍式交換。練習：已知序列{503,87,512,61,908,170,897,275,653,462}，給出采用快速排序對該序列作非遞減排序時每趟的結果。第一趟：【4628727561170】503【897908653512】第二趟：【1708727561】462503【512653】897【908】第三趟：【6187】170【275】462503512【653】897908第四趟：61【87】170275462503512653897908最后排序結果：61871702754625035126538979081.插入排序是穩定的，選擇排序是不穩定的。2.堆排序所需要附加空間數與待排序的記錄個數無關。3.對有n個記錄的集合進行快速排序，所需時間確定于初始記錄的排列情況，在初始記錄無序的情況下最好。4.直接插入排序在最好情況下的時間復雜度為（A）A.O(n)B.O(nlog2n)C.O(log2n)D.O(n2)5.數據序列{8,9,10,4,5,6,20,1,2}只能是（C）算法的兩趟排序后的結果。A.直接選擇排序B.冒泡排序C.直接插入排序D.堆排序6.用直接插入排序對下面4個序列進行遞增排序，元素比較次數最少的是（C）A.94,32,40,90,80,46,21,69B.32,40,21,46,69,94,90,80C.21,32,46,40,80,69,90,94D.90,69,80,46,21,32,94,407..以下排序算法中，（B）不能保證每趟排序至少能將一個元素放到其最終位置上。A.快速排序B.希爾排序C.堆排序D.冒泡排序8.對關鍵字{28,16,32,12,60,2,5,72}序列進行快速排序，第一趟從小到大一次劃分結果為（B）A.(2,5,12,16)26(60,32,72)B.(5,16,2,12)28(60,32,72)C.(2,16,12,5)28(60,32,72)D.(5,16,2,12)28(32,60,72)9.若用冒泡排序對關鍵字序列{18，16，14，12，10，8}進行從小到大的排序，所需進行的關鍵字比較總次數是（B）。A.10B.15C.21D.3410.一組記錄的關鍵字為{45，80，55，40，42，85}，則利用堆排序的方法建立的初始堆為（B）。A.{85，80，45，40，42，55}B.{85，80，55，40，42，45}C.{85，80，55，45，42，40}D.{85，55，80，42，45，40}第十章文件文件是性質相同的記錄的集合。記錄是文件中存取的基本單位，數據項是文件可使用的最小單位，數據項有時稱字段或者屬性。文件·邏輯結構是一種線性結構。·操作有：檢索和維護。并有實時和批量處理兩種處理方式。文件·存儲結構是指文件在外存上的組織方式。·基本的組織方式有：順序組織、索引組織、散列組織和鏈組織。·常用的文件組織方式：順序文件、索引文件、散列文件和多關鍵字文件。評價一個文件組織的效率，是執行文件操作所花費的時間和文件組織所需的存儲空間。檢索功能的多寡和速度的快慢，是衡量文件操作質量的重要標志。順序文件是指按記錄進入文件的先后順序存放、其邏輯順序和物理順序一致的文件。主關鍵字有序稱順序有序文件，否則稱順序無序文件。一切存儲在順序存儲器（如磁帶）上的文件都只能順序文件，只能按順序查找法存取。順序文件的插入、刪除和修改只能通過復制整個文件實現。索引文件的組織方式：通常是在主文件之外建立一張索引表指明邏輯記錄和物理記錄之間一一對應的關系，它和主文件一起構成索引文件。索引非順序文件中的索引表為稠密索引。索引順序文件中的索引表為稀疏索引。若記錄很大使得索引表也很大時，可對索引表再建立索引，稱為查找表。是一種靜態索引。索引順序文件常用的有兩種：·ISAM索引順序存取方法：是專為磁盤存取文件設計的，采用靜態索引結構。·VSAM虛擬存儲存取方法：采用B+樹作為動態索引結構，由索引集、順序集、數據集組成。散列文件是利用散列存儲方式組織的文件，亦稱為直接存取文件。散列文件·優點是：文件隨機存放，記錄不需要排序；插入刪除方便；存取速度快；不需要索引區，節省存儲空間。·缺點是：不能進行順序存取，只能按關鍵字隨機存取，且詢問方式限地簡單詢問，需要重新組織文件。多重表文件：對需要查詢的次關鍵字建立相應的索引，對相同次關鍵字的記錄建一個鏈表并將鏈表頭指針、長度、次關鍵字作為索引表的索引項。倒排表：次關鍵字索引表稱倒排表，主文件和倒排表構成倒排文件。數據結構與算法試題1、線性表的邏輯順序與物理順序總是一致的。()2、線性表的順序存儲表示優于鏈式存儲表示。()3、線性表若采用鏈式存儲表示時所有結點之間的存儲單元地址可連續可不連續。()4、二維數組是其數組元素為線性表的線性表。()5、每種數據結構都應具備三種基本運算：插入、刪除和搜索。()6、數據結構概念包括數據之間的邏輯結構，數據在計算機中的存儲方式和數據的運算三個方面。()7、線性表中的每個結點最多只有一個前驅和一個后繼。（）8、線性的數據結構可以順序存儲，也可以鏈接存儲。非線性的數據結構只能鏈接存儲。（）9、棧和隊列邏輯上都是線性表。（）10、單鏈表從任何一個結點出發，都能訪問到所有結點（）11、刪除二叉排序樹中一個結點，再重新插入上去，一定能得到原來的二叉排序樹。（）12、快速排序是排序算法中最快的一種。（）13、多維數組是向量的推廣。（）14、一般樹和二叉樹的結點數目都可以為0。（）15、直接選擇排序是一種不穩定的排序方法。（）16、98、對一個堆按層次遍歷，不一定能得到一個有序序列。（）17、在只有度為0和度為k的結點的k叉樹中，設度為0的結點有n0個，度為k的結點有nk個，則有n0=nk+1。（）18、折半搜索只適用與有序表，包括有序的順序表和有序的鏈表。（）19、堆棧在數據中的存儲原則是先進先出。（）20、隊列在數據中的存儲原則是后進先出。（）21、用相鄰矩陣表示圖所用的存儲空間大小與圖的邊數成正比。（）22、哈夫曼樹一定是滿二叉樹。（）23、程序是用計算機語言表述的算法。（）24、線性表的順序存儲結構是通過數據元素的存儲地址直接反映數據元素的邏輯關系。（）25、用一組地址連續的存儲單元存放的元素一定構成線性表。（）26、堆棧、隊列和數組的邏輯結構都是線性表結構。（）27、給定一組權值，可以唯一構造出一棵哈夫曼樹。（）28、只有在初始數據為逆序時，冒泡排序所執行的比較次數最多。（）29、希爾排序在較率上較直接接入排序有較大的改進。但是不穩定的。（）30、在平均情況下，快速排序法最快，堆積排序法最節省空間。（）31、快速排序法是一種穩定性排序法。（）32、算法一定要有輸入和輸出。（）33、算法分析的目的旨在分析算法的效率以求改進算法。（）34、非空線性表中任意一個數據元素都有且僅有一個直接后繼元素。（）35、數據的存儲結構不僅有順序存儲結構和鏈式存儲結構，還有索引結構與散列結構。（）36、若頻繁地對線性表進行插入和刪除操作，該線性表采用順序存儲結構更合適。（）37、若線性表采用順序存儲結構，每個數據元素占用4個存儲單元，第12個數據元素的存儲地址為144，則第1個數據元素的存儲地址是101。（）38、若長度為n的線性表采用順序存儲結構，刪除表的第i個元素之前需要移動表中n-i+1個元素。（）39、符號p->next出現在表達式中表示p所指的那個結點的內容。（）40、要將指針p移到它所指的結點的下一個結點是執行語句p←p->next。（）41、若某堆棧的輸入序列為1,2,3,4，則4,3,1,2不可能是堆棧的輸出序列之一。（）42、線性鏈表中各個鏈結點之間的地址不一定要連續。（）43、程序就是算法，但算法不一定是程序。（）44、線性表只能采用順序存儲結構或者鏈式存儲結構。（）45、線性表的鏈式存儲結構是通過指針來間接反映數據元素之間邏輯關系的。（）46、除插入和刪除操作外，數組的主要操作還有存取、修改、檢索和排序等。（）47、稀疏矩陣中0元素的分布有規律，因此可以采用三元組方法進行壓縮存儲。（）48、不管堆棧采用何種存儲結構，只要堆棧不空，可以任意刪除一個元素。（）49、確定串Ｔ在串Ｓ中首次出現的位置的操作稱為串的模式匹配。（）50、深度為h的非空二叉樹的第i層最多有2i-1個結點。（）51、滿二叉樹也是完全二叉樹。（）52、已知一棵二叉樹的前序序列和后序序列可以唯一地構造出該二叉樹。（）53、非空二叉排序樹的任意一棵子樹也是二叉排序樹。（）54、對一棵二叉排序樹進行前序遍歷一定可以得到一個按值有序的序列。（）55、一個廣義表的深度是指該廣義表展開后所含括號的層數。（）56、散列表的查找效率主要取決于所選擇的散列函數與處理沖突的方法。（）57、序列初始為逆序時，冒泡排序法所進行的元素之間的比較次數最多。（）58、已知指針P指向鍵表L中的某結點，執行語句P=P-〉next不會刪除該鏈表中的結點。（）59、在鏈隊列中，即使不設置尾指針也能進行入隊操作。（）60、如果一個串中的所有字符均在另一串中出現，則說前者是后者的子串。（）61、設與一棵樹T所對應的二叉樹為BT，則與T中的葉子結點所對應的BT中的結點也一定是葉子結點。（）62、若圖G的最小生成樹不唯一，則G的邊數一定多于n-1，并且權值最小的邊有多條（其中n為G的頂點數）。（）63、給出不同的輸入序列建造二叉排序樹，一定得到不同的二叉排序樹。（）64、由于希爾排序的最后一趟與直接插入排序過程相同，因此前者一定比后者花費的時間多。（）65、程序越短，程序運行的時間就越少。（）66、采用循環鏈表作為存儲結構的隊列就是循環隊列。（）67、堆棧是一種插入和刪除操作在表的一端進行的線性表。（）68、一個任意串是其自身的子串。（）69、哈夫曼樹一定是完全二叉樹。（）70、帶權連通圖中某一頂點到圖中另一定點的最短路徑不一定唯一。（）71、折半查找方法可以用于按值有序的線性鏈表的查找。（）72、稀疏矩陣壓縮存儲后,必會失效掉隨機存取功能。（）73、由一棵二叉樹的前序序列和后序序列可以唯一確定它。（）74、在n個結點的元向圖中,若邊數在于n-1,則該圖必是連通圖。（）75、在完全二叉樹中,若某結點元左孩子,則它必是葉結點。（）76、若一個有向圖的鄰接矩陣中,對角線以下元素均為0,則該圖的拓撲有序序列必定存在。（）77、樹的帶權路徑長度最小的二叉樹中必定沒有度為1的結點。（）78、二叉樹可以用0≤度≤2的有序樹來表示。（）79、一組權值，可以唯一構造出一棵哈夫曼樹。()80、101，88，46，70，34，39，45，58，66，10）是堆；（）81、將一棵樹轉換成二叉樹后，根結點沒有左子樹；（）82、用樹的前序遍歷和中序遍歷可以導出樹的后序遍歷；（）83、在非空線性鏈表中由p所指的結點后面插入一個由q所指的結點的過程是依次執行語句：q->next=p->next;p->next=q。（）84、非空雙向循環鏈表中由q所指的結點后面插入一個由p指的結點的動作依次為：p->prior=q,p->next=q->next,q->next=p,q->prior->next←p。（）85、刪除非空鏈式存儲結構的堆棧(設棧頂指針為top)的一個元素的過程是依次執行:p=top,top=p->next,free(p)。()86、哈希的查找無需進行關鍵字的比較。（）87、一個好的哈希函數應使函數值均勻的分布在存儲空間的有效地址范圍內，以盡可能減少沖突。（）88、排序是計算機程序設計中的一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個按關鍵字有序的序列。（）89、隊列是一種可以在表頭和表尾都能進行插入和刪除操作的線性表。（）90、在索引順序表上實現分塊查找，在等概率查找情況下，其平均查找長度不與表的個數有關，而與每一塊中的元素個數有關。（）91、對于有向圖，頂點的度分為入度和出度，入度是以該頂點為終點的入邊數目；出度是以該頂點為起點的出邊數目，該頂點的度等于其入度和出度之和。（）92、無向圖的鄰接矩陣是對稱的有向圖的鄰接矩陣是不對稱的。（）93、具有n個頂點的連通圖的生成樹具有n-1條邊（）二、填空題：1、《數據結構》課程討論的主要內容是數據的邏輯結構、存儲結構和______________。2、數據結構算法中，通常用時間復雜度和__________________兩種方法衡量其效率。3、一個算法一該具有______,______,____,______和____這五種特性。4、若頻繁地對線性表進行插入與刪除操作，該線性表應采用____________存儲結構。5、在非空線性表中除第一個元素外，集合中每個數據元素只有一個_______；除最后一個元素之外，集合中每個數據元素均只有一個_________。6、線性表中的每個結點最多有________前驅和____________后繼。7、______鏈表從任何一個結點出發，都能訪問到所有結點。8、鏈式存儲結構中的結點包含____________域，_______________域。9、在雙向鏈表中，每個結點含有兩個指針域，一個指向______結點，另一個指向________結點。10、某帶頭結點的單鏈表的頭指針head，判定該單鏈表非空的條件______________。11、在雙向鏈表中，每個結點含有兩個指針域，一個指向_______結點，另一個指向_____結點。12、已知指針p指向單鏈表中某個結點，則語句p->next=p->next->next的作用__刪除p的后繼結點_。13、已知在結點個數大于1的單鏈表中，指針p指向某個結點，則下列程序段結束時，指針q指向*p的_____________結點。q=p;while(q->next!=p)q=q->next;14、若要在單鏈表結點*P后插入一結點*S，執行的語句_______________。15、線性表的鏈式存儲結構地址空間可以_________，而向量存儲必須是地址空間___________。16、棧結構允許進行刪除操作的一端為_____________。17、在棧的順序實現中，棧頂指針top，棧為空條件______________。18、對于單鏈表形式的隊列，其空隊列的F指針和R指針都等于__________________。19、若數組s[0..n-1]為兩個棧s1和s2的共用存儲空間，僅當s[0..n-1]全滿時，各棧才不能進行棧操作，則為這兩個棧分配空間的最佳方案是：s1和s2的棧頂指針的初值分別為_________。20、允許在線性表的一端插入,另一端進行刪除操作的線性表稱為_______。插入的一端為______,刪除的一端為______。21、設數組A[m]為循環隊列Q的存儲空間，font為頭指針，rear為尾指針，判定Q為空隊列的條件____________________。22、對于順序存儲的隊列，存儲空間大小為n，頭指針為F，尾指針為R。若在邏輯上看一個環，則隊列中元素的個數為___________。23、已知循環隊列的存儲空間為數組data[21]，且頭指針和尾指針分別為8和3，則該隊列的當前長度__________。24、一個串的任意個連續的字符組成的子序列稱為該串的________，包含該子串的串稱為________。25、求串T在主串S中首次出現的位置的操作是________________。26、在初始為空的隊列中插入元素A,B,C,D以后，緊接著作了兩次刪除操作，此時的隊尾元素是__________。27、在長度為n的循環隊列中，刪除其節點為x的時間復雜度為_______________。28、已知廣義表L為空，其深度為___________。29、已知一順序存儲的線性表，每個結點占用k個單元，若第一個結點的地址為DA1，則第i個結點的地址為______________。30、設一行優先順序存儲的數組A[5][6]，A[0][0]的地址為1100，且每個元素占2個存儲單元，則A[2][3]的地址為_____________。31、設有二維數組A[9][19]，其每個元素占兩個字節，第一個元素的存儲地址為100，若按行優先順序存儲，則元素A[6,6]的存儲地址為______________，按列優順序存儲，元素A[6,6]的存儲地址為______________。32、在進行直接插入排序時,其數據比較次數與數據的初始排列________關；而在進行直接選擇排序時，其數據比較次數與數據的初始排列__________關。33、假設以行為優先存儲的三維數組A[5][6][7]，A[0][0][0]的地址為1100，每個元素占兩個存儲單元，則A[4][3][2]的地址為_______。34、設二維數組A[m][n]按列優先存儲，每個元素占1個存儲單元，元素A00的存儲地址loc(A00)，則Aij的存儲地址loc(Aij)=____________________。35、稀疏矩陣一般采用__________方法進行壓縮存儲。36、稀疏矩陣可用_________進行壓縮存儲，存儲時需存儲非零元的________、________、________。37、若矩陣中所有非零元素都集中在以主對角線為中心的帶狀區域中，區域外的值全為0，則稱為__________。38、若一個n階矩陣A中的元素滿足：Aij=Aji(0<=I,j<=n-1)則稱A為____________矩陣；若主對角線上方(或下方)的所有元素均為零時，稱該矩陣為______________。39、對于上三角形和下三角形矩陣，分別以按行存儲和按列存儲原則進行壓縮存儲到數組M[k]中，若矩陣中