一單項選擇題 ( 在每小題的四個備選答案中選出一個正確答案並將正確答案的序號填在題干的括號內每小題 分共 分 )
某二叉樹的先序序列和後序序列正好相同則該二叉樹一定是 ( ) 的二叉樹
A 空或只有一個結點 B 高度等於其結點數
C 任一結點無左孩子 D 任一結點無右孩子
下列排序算法中時間復雜度不受數據初始狀態影響恆為 O(log n) 的是 ( )
A 堆排序 B 冒泡排序
C 直接選擇排序 D 快速排序
下列排序算法中 ( ) 算法可能會出現下面情況初始數據有序時花費的時間反而最多
A 堆排序 B 冒泡排序
C 快速排序 DSHELL 排序
一個棧的輸入序列為 則下列序列中不可能是棧的輸出序列的是 ( )
A B
C D
設循環隊列中數組的下標范圍是 ～ n 其頭尾指針分別為 f 和 r 則其元素個數為 ( )
A rf B rf+
C (rf) mod n+ D (rf+n) mod n
若某鏈表最常用的操作是在最後一個結點之後插入一個結點和刪除最後一個結點則采用 ( ) 存儲方式最節省時間
A 單鏈表 B 雙鏈表
C 帶頭結點的雙循環鏈表 D 單循環鏈表
在有 n 個結點的二叉鏈表中值為非空的鏈域的個數為 ( )
A n B n
C n+ D n+
一棵左右子樹均不空的二叉樹在先序線索化後其空指針域數為 ( )
A B
C D 不確定
數組 A [][]的每個元素占 個單元將其按行優先次序存儲在起始地址為 的連續的內存單元中則元素 A []的地址為 ( )
A B
C D
求最短路徑的 DIJKSTRA 算法的時間復雜度為 ( )
A O(n) B O(n+e)
C O(n ) D O(n × e)
對有 個元素的有序表作二分查找則查找 A [ ]的比較序列的下標依次為 ( )
A B
C D
快速排序算法在最好情況下的時間復雜度為 ( )
A O(n) B O(nlog n)
C O(n ) D O(log n)
下列排序算法中某一趟結束後未必能選出一個元素放在其最終位置上的是 ( )
A 堆排序 B 冒泡排序
C 快速排序 D 直接插入排序
二叉樹在線索化後仍不能有效求解的問題是 ( )
A 先序線索二叉樹中求先序後繼
B 中序線索二叉樹中求中序後繼
C 中序線索二叉樹中求中序前趨
D 後序線索二叉樹中求後序後繼
DFS 算法的時間復雜度為 ( )
A O(n) B O(n )
C O(n ) D O(n+e)
隊列操作的原則是 ( )
A 先進先出 B 後進先出
C 只能進行插入 D 只能進行刪除
有 個結點的完全二叉樹的深度為 ( )( 根的層次為 )
A B
C D
在平衡二叉樹中插入一個結點後造成了不平衡設最低的不平衡結點為 A 並已知 A 的左孩子的平衡因子為 右孩子的平衡因子為 則應作 ( ) 型調整以使其平衡
A LL B LR
C RL D RR
數據表 A 中有 個元素如果僅要求求出其中最大的 個元素則采用 ( ) 排序算法最節省時間
A 堆排序 B 希爾排序
C 快速排序 D 直接選擇排序
二判斷題 ( 判斷下列各題正確的在題後括號內打 √ 錯的打 × 每小題 分共 分 )
給出不同的輸入序列建造二叉排序樹一定得到不同的二叉排序樹 ( )
由於希爾排序的最後一趟與直接插入排序過程相同因此前者一定比後者花費的時間多 ( )
在對鏈隊列作出隊操作時不會改變 front 指針的值 ( )
若一個棧的輸入序列為 … n 其輸出序列的第一個元素為 n 則其輸出序列的每個元素 a i 一定滿足 a i =ni+(i=n)( )
二叉樹中的葉子結點就是二叉樹中沒有左右子樹的結點 ( )
一棵樹中的葉子結點數一定等於與其對應的二叉樹中的葉子結點數 ( )
有向圖用鄰接矩陣表示後頂點 i 的人度等於鄰接矩陣中第 i 列的元素個數 ( )
有向圖的鄰接表和逆鄰接表中的結點數一定相同 ( )
刪除二叉排序樹中一個結點再重新插入上去一定能得到原來的二叉排序樹 ( )
圖 G 的拓撲序列唯一則其弧數必為 n( 其中 n 為 G 的頂點數 ) ( )
三填空題 ( 每空 分共 分 )
在有 n 個葉子結點的哈夫曼樹中總結點數是 _______
一棵樹 T 采用二叉鏈表存儲如果樹 T 中某結點為葉子結點則在二叉鏈表 BT 中所對應的結點一定 _______
已知數組 A [][]為對稱矩陣其中每個元素占 個單元現將其下三角部分按行優先次序存儲在起始地址為 的連續的內存單元中則元素 A []對應的地址是 _______
在有 n 個結點的無向圖中其邊數最多為 _______
取出廣義表 A=(x(abcd)) 中原子 x 的函數是 _______
對矩陣采用壓縮存儲是為了 _______
帶頭結點的雙循環鏈表 L 為空表的條件是 _______
在雙鏈表中在指針 P 所指結點前面插入一個結點 S ∧時的語句序列是
S>next=P;S>prior=P>prior;P>prior=S;
_______ ;
對廣義表 A=(x((ab)cd)) 的運算 head (head (tail (A))) 的結果是 ______
判斷線索二叉樹中某結點指針 P 所指結點有左孩子的條件是 _______
四簡答題 ( 每小題 分共 分 )
&#;
求出下圖的一棵最小生成樹
將下面順序表建成一個小頭堆
( )
已知一棵二叉樹的先序序列是 ABCDEFGHIJK 中序序列是 CDBGFEAHJIK 請構造出該二叉樹
五綜合應用題 ( 共 分 )
已知一樹的雙親表示法如下其中各兄弟結點是依次出現的畫出該樹及對應的二叉樹 ( 滿分 分 )
data A B C D E F G H I J K L M N O
parent
計算二叉樹的深度的算法 ( 分 )
浙江省 年 月高等教育自學考試
數據結構試題參考答案
課程代碼
一單項選擇題 ( 每小題 分共 分 )
A B C B D
C A B A C
D B D D C
A B A C
二判斷題 ( 每小題 分共 分 )
√ × √ √ ×
× √ × × ×
三填空題 ( 每空 分共 分 )
n
左右子樹空
n(n)/
head(A)
節省空間
L>next=L>prior 或 L>next=L
S>prior>next=S
(a)
P>ltag=
四簡答題 ( 每小題 分共 分 )
&#; 最小生成樹
小頭堆
二叉樹
五綜合應用題 ( 共 分 )
&#;
從森林轉換為二叉樹 ( 分 )
計算二叉樹的深度的算法 ( 分 )
int depth(tree *T)
{
if(!T)
return ;
else
return +max(depth(T>Lchild)depth(>Rchild));
}
From:http://tw.wingwit.com/Article/program/sjjg/201311/23398.html
