數據結構知識要點1.在數據結構中,從邏輯上可以把數據結構分為線性結構和非線性結構2.在數據結構中,與所使用的計算機無關的是數據的邏輯結構。3.任何一棵二叉樹的葉子結點在前序、中序和后序遍歷序列中的相對次序不發生改變4.在下述論述中,只有一個結點的二叉樹的度為0;深度為K的順序二叉樹的結點個數小于或等于深度相同的滿二叉樹。5.某二叉樹結點的中序序列為ABCDEFG,后序序列為BDCAFGE,則其左子樹中結點數目為:46.順序查找法適合于存儲結構為順序存儲或鏈式存儲的線性表。7.采用折半查找法查找長度為n的線性表時,每個元素的平均查找長度為O(log2n)8.線性表是具有n個數據元素的有限序列。9.若長度為n的線性表采用順序存儲結構,在其第i個位置插入一個新元素的算法的時間復雜度為O(n)10.線性表(a1,a2,…,an)以鏈式方式存儲,訪問第i位置元素的時間復雜度為O(n)11.允許對隊列進行的操作有刪除隊頭元素12.若串S=…software?,其子串的數目是3713.一個棧的進棧序列是a,b,c,d,e,則棧的不可能的輸出序列是dceab14.從隊列中刪除第i個元素不是隊列的基本運算?15.在一個具有n個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是O(n)16.與單鏈表相比,雙鏈表的優點之一是順序訪問相鄰結點更靈活17.在長度為n的順序表的第i個位置上插入一個元素(1≤i≤n+1),元素的移動次數為:n–i+118.一個隊列的入隊序列是1,2,3,4,則隊列的輸出序列是1,2,3,419.設有兩個串p和q,求q在p中首次出現的位置的運算稱為模式匹配20假設該數組的內存起始位置為200,average[15]的內存地址是26021.設二維數組A[1…m,1…n]按行存儲在數組B中,則二維數組元素A[i,j]在一維數組B中的下標為n*(i-1)+j22.有一個100×90的稀疏矩陣,非0元素有10,設每個整型數占2個字節,則用三元組表示該矩陣時,所需的字節數是6623.數組A[0…4,-1…-3,5…7]中含有的元素個數是5524.對矩陣進行壓縮存儲是為了減少存儲空間25.設有一個10階的對稱矩陣A,采用壓縮存儲方式,以行序為主存儲,a1,1為第一個元素,其存儲地址為1,每個元素占1個地址空間,則a8,5的地址為3326.稀疏矩陣一般的壓縮存儲方式有兩種,即三元組和十字鏈表27.樹最適合用來表示元素之間具有分支層次關系的數據28.在以下的敘述中,二維數組是其數據元素為線性表的線性表29.鏈表不具備的特點是可隨機訪問任一結點30.需要分配較大空間,插入和刪除不需要移動元素的線性表,其存儲結構是靜態鏈表31算法的5個重要特性是有窮性、確定性、可行性、輸入和輸出。32.在順序表中插入或刪除一個數據元素,需要平均移動n個數據元素,移動數據元素的個數與位置有關。33.在雙鏈表中,每個結點有兩個指針域,一個指向前驅節點,另一個指向后繼結點。34.帶頭結點的循環鏈表L中只有一個元素結點的條件是L->next->next=L。35.一個字符串中任意個連續字符構成的部分稱為該串的子串。36.在有n個結點的二叉鏈表中,空鏈域的個數為__n+1__。37.順序存儲結構是通過下標表示元素之間的關系的;鏈式存儲結構是通過指針表示元素之間的關系的。38.子串”str”在主串”datastructure”中的位置是5。39.稀疏矩陣一般的壓縮存儲方法有兩種,即三元組表和十字鏈表。40.線索二叉樹的左線索指向其遍歷序列中的前驅,右線索指向其遍歷序列中的后繼。41.在各種查找方法中,平均查找長度與結點個數n無關的查找方法是散列查找法。42.索引是為了加快檢索速度而引進的一種數據結構。一個索引隸屬于某個數據記錄集,它由若干索引項組成,索引項的結構為關鍵字和關鍵字對應記錄的地址。43.在一棵m階B樹中,除根結點外,每個結點最多有m棵子樹,最少有m/2棵子樹。44.深度為5的二叉樹至多有31個結點。45.在各種查找方法中,平均查找長度與結點個數n無關的查找方法是散列查找法。46.抽象數據類型(ADT)包括定義和實現兩方面,其中定義是獨立于實現的,定義僅給出一個ADT的邏輯特性,不必考慮如何在計算機中實現。47.抽象數據類型與計算機內部表示和實現無關。48.二叉樹的后序遍歷序列中,任意一個結點均處在其孩子結點的后面。49.廣義表(((a),b),c)的表頭是((a),b),表尾是(c)。50.在平衡二叉樹中,任意結點左右子樹的高度差(絕對值)不超過1。51、單鏈表中結點的結構如下所示：typedefstructnode{

intdata;structnode*next;}node設順序表L是一個遞增有序表，試寫一算法，將x插入L中，并使L仍是一個有序表。順序表的結構定義如下：#defineListSize100

//假定表空間大小為100

structSqList{

intelem[ListSize];

//數組elem用于存放表中的數據

intlength;

//當前的表長度

};//以上為順序表的結構//函數頭定義如下voidInsertIncreaseList(SqList&L,intx){inti;

if(L.length>=ListSize)

cout<<”OVERFLOW”;

//判斷是否溢出

for(i=L.length;i>0&&L.elem[i-1]>x;i--)

L.elem[i]=L.elem[i-1];//比較并移動元素

L.elem[i]=x;

//插入x

L.length++;

//表長增1

}52.某二叉樹結點的中序序列為H，B，C，D，E，F，G，后序序