1、3個結點可構成棵不同形態的樹。
2、利用直接選擇排序演算法對n個記錄進行排序,最壞的情況下,記錄交換的次數為
3、乙個圖的_______表示法是唯一的,而______表示法是不唯一的。
4、一棵深度為h的滿二叉樹上的結點總數為 ,一棵深度為h的完全二叉樹上的結點總數的最小值為 ,最大值為 。
5、在一棵完全二叉樹中有n個結點,對這些結點按層序編號,若乙個結點編號為69,則其雙親編號為 ,有左孩子的條件是 ,其左孩子編號為 。
6、二維陣列m的成員是6個字元組成的串,行下標i的範圍從0到8,列下標j的範圍從1到10,則存放m至少需要________個位元組;m的第8列和第5行共占個位元組;若m按行優先方式儲存,元素m[8][5]的起始位址與當m按列優先方式儲存時的________元素的起始位址一致。
7、設有一順序棧s,元素s1,s2,s3,s4,s5,s6依次進棧,如果6個元素出棧的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應該是________。
8、**性表的順序儲存中,元素之間的邏輯關係是通過決定的;**性表的鏈式儲存中,元素之間的邏輯關係是通過_________決定的。
9、n個頂點的連通圖的生成樹有 n-1 條邊。
10、通常陣列只有______給定一組有定義的下標,訪問相應的資料__和___給定一組有定義的下標,修改相應資料元素的值_____兩種運算,因此常採用__順序_______來儲存陣列。
11、3個節點可以構成 5 棵不同形態的二叉樹。
12、對於一棵具有n個結點的二叉樹,當它為一棵完全二叉樹時具有最小高度,即為 ∟log2n」+1 ,當它為一棵單支樹時具有最大高度,即為 n
13、在一棵有n個結點的完全二叉樹中,對這些結點按層序編號,若乙個結點編號為59,則其雙親編號為若乙個結點編號為23,則其有右孩子的條件是
14、陣列m中每個元素的長度是3個位元組,行下標i從1到8,列下標j從1到10,從首位址ea開始連續存放在儲存器中。若按行優先方式存放,元素m[8][5]的起始位址為________;若按列優先方式存放,元素m[8][5]的起始位址為________。
15、對於乙個具有n個結點的單鏈表,在p所指結點後插入乙個新結點的時間複雜度為_______;在給定值為x的結點後插入乙個新結點的時間複雜度為
16、資料結構的實質就是研究資料的以及定義在邏輯結構上所進行的一組 。
17、任何連通圖的連通分量有_____1_____個,即__它本身
18 假定查詢有序表a[1..10]中每個元素的概率相等,則進行順序查詢時的平均查詢長度為 5.5 ,進行二分查詢時的平均查詢長度為 20 。
1、在乙個單鏈表中,已知q所指結點是p所指結點的前驅,若在p、q之間插入s結點,則執行( )操作。
a、s->next=p-next;p->next=s; b、q->next=s;s->next=p;
c、p->next=s->next;s->next=p; d、p->next=s;s->next=q;
2、下面程式段的時間複雜度為( )。
i=1;
while (i<=n)
i=i*2;
a、o(log2n) b、o(n) c、o( n) d、o(nlog2n)
3、設森林t中有三棵樹,第
一、二、三棵樹的結點個數分別是n1,n2,n3,那麼當把森林轉換成二叉樹後,其根結點的左子樹上有( )個結點,右子樹上有( )個結點。
a、n1-1 b、n1 c、n1+n2 d、n2+n3
4、若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素,則採用( )儲存方式最節省時間。
a、單鏈表 b、雙鏈表 c、單向迴圈鍊錶 d、順序表
5、使用雙向鍊錶儲存資料,其優點是可以( )。
a、提高檢索速度 b、很方便地插入和刪除資料
c、節約儲存空間 d、很快**儲存空間
6、單鏈表中,增加頭結點的目的是為了( )。
a、方便運算的實現b、標識單鏈表
c、使單鏈表中至少有乙個結點 d、用於標識起始結點的位置
7、在具有n個結點的二叉排序樹上插入乙個新結點時,其時間複雜度大致為( )。
a、o(n2) b、o(n) c、o(log2n) d、o(nlog2n)
8、下面程式段的時間複雜度為( )。
for (i=1;i<=m;++i)
for (j=1;j<=n;++j)
a[i,j]=i*j;
a、o(m2) b、o(n2) c、o(m*n) d、o(m+n)
9、帶頭結點的單鏈表h為空的判斷條件是( )。
a、h==null b、h->next==null c、h->next==h d、h!=null
10、設有乙個無向圖g=(v,e)和g`=(v`,e`),如果g`為g的生成樹,則下面不正確的說法是( )。
a、g`為g的子圖b、g`為g的連通分量
c、g`為g的極小連通子圖且v`=v
d、g`是g的乙個無環子圖
11、設計乙個判別表示式中左右括號是否配對出現的演算法,採用( )資料結構最佳。
a、線性表的順序儲存結構 b、棧
c、佇列d、線性表的鏈式儲存結構
12、在具有n個葉子的哈夫曼樹中,其結點總數為( c )。
a、不確定 b、2n c、2n+1 d、2n-1
13、有一雜湊表,表長m為100,採用除餘法構造雜湊函式,即h(k)=k mod p,為使雜湊函式具有較好的效能,p的選擇應是( )。
a、99 b、97 c、91 d、93
14、在乙個具有n個單元的順序棧中,假定以位址低端(即下標為0的單元)作為棧底,以top作為棧頂指標,則當作退棧處理時,top的變化為( )。
a、top不變 b、top=0 c、top=top+1 d、top=top-1
15、鏈棧與順序棧相比,有乙個較明顯的優點是( )。
a、通常不會出現棧滿的情況 b、通常不會出現棧空的情況
c、插入操作更加方便d、刪除操作更加方便
16、已知10個資料元素為(54,28,16,34,73,62,95,60,26,43),按依次插入結點的方法生成一棵二叉排序樹後,查詢值為62的結點所需用比較的次數為( b ),查詢61的比較次數為( )。
a、2 b、3 c、4 d、5
1、已知某系統在通訊聯絡中只可能出現8種字元,其頻率分別為9,6,18,19,10,21,5,12。試設計哈夫曼編碼。(必須畫出哈夫曼樹)
2、對下列有向圖,
寫出以頂點1為出發點對圖進行深度優先搜尋所得到的所有可能的訪問序列。
解:深度優先搜尋
1——>3——>6——>4——>2——>5
1——>3——>2——>5——>4——>6
1——>3——>1——>2——>5——>4——>6
1——>3——>6——>3——>2——>5——>4
1——>2——>5——>4——>3——>6
3、假定乙個待雜湊儲存的線性表為(32,75,63,48,94,25,36,18,70),雜湊位址空間為[0..10],若採用除餘法構造雜湊函式和線性探測再雜湊法處理衝突,試給出它們對應的雜湊表。
解1:解2:
4、如圖所示的有向圖,求出從源點1到其他頂點的最短路徑(要求寫出過程)。
1090
1003050 10
8040
20 6010
資料結構練習題
習題3 棧和佇列 一 基本內容 棧和佇列的結構特點 在兩種儲存結構上如何實現棧和佇列的基本操作以及棧和佇列在程式設計中的應用。二 學習要點 1.掌握棧和佇列的特點。2 熟練掌握棧型別的兩種實現方法,即兩種儲存結構表示時的基本操作實現演算法,特別應注意棧滿和棧空的條件以及它們的描述方法。3 熟練掌握迴...
資料結構練習題
習題5 陣列和廣義表 一 基本內容 陣列定義及表示方式 特殊矩陣和稀疏矩陣的壓縮儲存方法及運算的實現 廣義表的邏輯結構和儲存結構。二 學習要點 1.了解陣列的兩種儲存表示方法,並掌握陣列在以行為主的儲存結構中的位址計算方法。2 掌握對特殊矩陣進行壓縮儲存時的下標變換公式。3 了解稀疏矩陣的兩種壓縮儲...
資料結構練習題
a.n b.n 1 2 c.n 1 9 對於乙個具有n個頂點和e條邊的無向圖,若採用鄰接表表示,則表頭向量的大小為 所有鄰接表中的接點總數是 b.n 1 c.n 1 d.n e a.e 2 b.e d.n e 10 已知乙個圖如圖7.1所示,若從頂點a出發按深度搜尋法進行遍歷,則可能得到的一種頂點序...