一單項選擇題(在每小題列出的四個備選答案中選出一個正確的答案並將其號碼填在題干的括號內每小題分共分)
下列有關線性表的敘述中正確的是( )
A線性表中的元素之間隔是線性關系
B線性表中至少有一個元素
C線性表中任何一個元素有且僅有一個直接前趨
D線性表中任何一個元素有且僅有一個直接後繼
下列關於串的敘述中正確的是( )
A一個串的字符個數即該串的長度
B一個串的長度至少是
C空串是由一個空格字符組成的串
D兩個串S和S若長度相同則這兩個串相等
以數組Q[m ]存放循環隊列中的元素變量rear和qulen分別指示循環隊列中隊尾元素的實際位置和
當前隊列中元素的個數隊列第一個元素的實際位置是( )
Arear qulen
Brear qulen + m
Cm qulen
D +(rear + m qulen)mod m
高二叉樹根結點的層次為所有含有個結點的二叉樹中最小高度是( )
A
B
C
D
設結點x和結點y是二叉樹T中的任意兩個結點若在先根序列中x在y之前而在後根序列中x在y之後則x和y的關系是( )
Ax是y的左兄弟
Bx是y的右兄弟
Cx是y的祖先
Dx是y的後代
下列四種排序方法中不穩定的方法是( )
A直接插入排序
B冒泡排序
C歸並排序
D直接選擇排序
設有一個長度為的已排好序的表用二分查找進行查找若查找不成功至少比較( )次
A
B
C
D
一棵二叉排序樹T用( )方法進行遍歷可以得到各結點鍵值的遞增序列
A先根遍歷
B中根遍歷
C層次遍歷
D後根遍歷
二判斷題(判斷下列各題是否正確正確的在括號內打√錯誤的打×每小題分共分)
數據的機內表示稱為數據的存儲結構( )
線性表的鏈接存儲表中元素的邏輯順序與物理順序一定相同( )
二叉樹中任何一個結點的度都是( )
由二叉樹結點的先根序列的後根序列可以唯一地確定一棵二叉樹( )
一個無向圖的鄰接矩陣中各元素之和與圖中邊的條數相等( )
用直接選擇排序方法分別對序列S=()和序列S=()
進行排序兩者的比較次數不相同( )
一棵哈夫曼樹中不存在度為的結點( )
用二分查找法對一個順序表進行查找這個順序表可以是按各鍵值排好序的也可以是沒有按鍵值排好序的( )
順序文件適宜順序存取不適宜隨機存取( )
平衡二叉排序樹上任何一個結點的左右子樹的高度之差的絕對值不大於( )
三填空題(每空分共分)
一個n×n的下三角矩陣A中的元素aij(i≥j≤ij≤n)按行存於一個一維數組B[n(n
+)/]中對其中的任一元素aij若在B中的位置為k則k=____________
含有個結點的樹有____________條邊
一棵二叉樹有個結點這些結點的度要麼是要麼是這棵二叉樹中度為的結點有_________個
在一個無環有向圖G中若存在一條從頂點i到頂點j的弧則在頂點的拓撲序列中頂點i與頂點j的先後次序是____________
在一個無向圖的鄰接表中若表結點的個數是m則圖中邊的條數是____________條
設一個閉散列表的容量為m用線性控測法解決沖突要插入一個鍵值若插入成功至多要進行____________次比較
設一棵二叉樹結點的先根序列為ABDECFGH中根序列為DEBAFCHG則二叉樹中葉子結點是____________
一棵哈夫曼樹有個結點則其葉子結點的個數是____________
將兩個長度分別m和n(m>n)的排好序的表歸並成一個排好序的表至少要進行____________次鍵值比較
設二維數組M:array[]of integer每個元素(整數)占個存儲單元元素按行的順序存儲數組的起始地址為元素M[]的地址是____________
線性表L=(aaan)采用順序存儲假定在不同的n
+ 個位置上插入的概率相同則插入一個新元素平均需要移動的元素個數是____________
設棧S和隊列Q的初始狀態皆為空元素aaaaa和a依次通過一個棧一個元素出棧後即進入隊列Q若個元素出隊列的順序是aaaaaa則棧S至少應該容納____________個元素
兩個序列如下
L={}
L={}
用冒泡排序方法分別對序列L和L進行排序交換次序較少的是序列____________
將一棵有個結點的完全二叉樹從根結點開始由根向下每一層從左至右順序地存儲在一個一維
數組bt[]中這棵二叉樹最下面一層上最左邊一個結點存儲在數組元素____________中
一個索引文件由____________兩部分組成
四應用題(共分)
初始輸入序列的鍵值如下
()
試采用二路歸並排序法進行從小到大的排序寫出該序列在每遍掃描時的合並過程(分)
五設計題(共分)
修改冒泡排序法以實現雙向冒泡排序即第一次把最大記錄放到表尾第二次將最小記錄放到表頭如此反復進行直至排序結束試編寫此算法(分)
From:http://tw.wingwit.com/Article/program/sjjg/201311/23399.html
