山東建筑大學(xué)數(shù)據(jù)結(jié)構(gòu)知識要點(diǎn)

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

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

//假定表空間大小為100

structSqList{

intelem[ListSize];

//數(shù)組elem用于存放表中的數(shù)據(jù)

intlength;

//當(dāng)前的表長度

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

if(L.length>=ListSize)

cout<<”O(jiān)VERFLOW”;

//判斷是否溢出

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.某二叉樹結(jié)點(diǎn)的中序序列為H，B，C，D，E，F(xiàn)，G，后序序