一單項選擇題(在下列每小題四個備選答案中選出一個正確答案並將其字母標號填入題干的括號內每小題分共分)
下列數據組織形式中( )的結點按邏輯關系依次排列形成一個鎖鏈
A集合 B樹形結構 C線性結構 D圖狀結構
數據結構可以形式化地定義為(S△)其中S指某種邏輯結構△是指( )
A S上的算法 B S的存儲結構
C 在S上的一個基本運算集 D 在S上的所有數據元素
下列說法正確的是( )
A線性表的邏輯順序與存儲順序總是一致的
B線性表的鏈式存儲結構中要求內存中可用的存儲單元可以是連續的也可以不連續
C線性表的線性存儲結構優於鏈式存儲結構
D每種數據結構都具有插入刪除和查找三種基本運算
設非空單鏈表的數據域為data指針域為next指針p指向單鏈表中第i個結點s指向已生成的新結點現將s結點插入到單鏈表中使其成為第i個結點下列算法段能正確完成上述要求的是( )
A s > next=p > next; p > next=s;
B p>next=s; s>next=p>next;
C s>next=p>next; p>next=s; 交換p>data和s>data;
D p=s; s>next=p;
稀疏矩陣一般采用( )方法壓縮存儲
A三維數組 B單鏈表 C三元組表 D散列表
樹若用雙親鏈表表示則( )
A可容易地實現求雙親及子孫的運算
B求雙親及子孫的運算均較困難
C可容易地實現求雙親運算但求子孫運算較困難
D可容易地實現求子孫運算但求雙親運算較困難
將一棵有個結點的完全二叉樹按層編號則對編號為的結點x該結點( )
A無左右孩子 B有左孩子無右孩子
C有右孩子無左孩子 D有左右孩子
用鄰接表作為有向圖G的存儲結構設有n個頂點e條弧則拓撲排序的時間復雜度為( )
A O(n) B O(n+e) C O(e) D O(n*e)
如果從無向圖的任一頂點出發進行一次深度優先搜索即可訪問所有頂點則該圖一定是( )
A完全圖 B連通圖 C有回路 D一棵樹
采用線性探測法解決沖突問題所產生的一系列後繼散列地址( )
A必須大於等於原散列地址
B必須小於等於原散列地址
C可以大於或小於但不能等於原散列地址
D地址大小沒有具體限制
在對查找表的查找過程中若被查找的數據元素不存在則把該數據元素插入到集合中這種方式主要適合於( )
A靜態查找表 B動態查找表
C靜態查找表與動態查找表 D兩種表都不適合
由索引集順序集和數據集三部分組成的文件稱為( )
A VSAM文件 B散列文件 C順序文件 D索引文件
下列有關散列文件的說法中不正確的是( )
A散列文件具有隨機存放的優點
B散列文件只能按關鍵字存取
C散列文件需要索引區
D散列文件的記錄不需要進行排序
一組記錄的鍵值為()按路歸並排序方法對該序列進行一趟歸並後的結果為( )
A B
C D
用快速排序方法對包含有n個關鍵的序列進行排序最壞情況下執行的時間雜度為( )
A O(n) B O(log n) C O(nlog n) D O(n )
二填空題(每空分共分)
定義在線性表上的初始化查找插入和刪除運算中 是引用型運算
線性表(a a a …a n ) (n≥)中每個元素占c個存儲單元m為a 的首地址則按順序存儲方式存儲線性表a n 的存儲地址是
在棧的順序實現中設棧頂指針為top棧空的條件為
隊列中允許進行插入的一端稱為
深度為的滿二叉樹上第層有 個結點
給定n個值構造哈夫曼樹根據哈夫曼算法初始森林中共有n棵二叉樹經過 次合並後才能使森林中的二叉樹的數目由n棵減少到只剩下一棵最終的哈夫曼樹
設無向圖G的頂點數為n則G最少有 條邊
通常采用拉鏈法線性探測法多重散列法二次探測法公共溢出區法等解決散列地址沖突問題若要避免堆積現象發生應采用 法
對有序表()用二分查找法查找則所需的比較次數為
樹型結構結點間通過父子關系相互關聯這種相互關聯構成了數據間的 關系
文件的檢索有順序存取直接存取和 三種方式
第i趟在ni+l (i=…nl)個記錄中選取鍵值最小的記錄作為有序序列的第i個記錄這樣的排序方法稱為
在堆排序和快速排序中若原始記錄已基本有序則較適合選用
三應用題(共分)
設有字符串為 * y a / y ∧ 試利用棧寫出將其轉換為 y * a y ∧ / 的操作步驟假定用 X 代表掃描該字符串過程中順序取一個字符進棧的操作用 S 代表從棧中取出一個字符加入到新字符串尾的出棧操作例如ABC 變為 BCA 的操作步驟為 XXSXSS (分)
現有某二叉樹按先根遍歷的序列為ABDEFCGH按中根遍歷的序列為DEFBGHCA試畫出此二叉樹(分)
給定表()按數據元素在表中的次序構造一棵二叉排序樹(分)
已知序列()請給出采用直接插入排序法對該序列作升序排序時的每一趟的結果(分)
已知無向圖G的鄰接表如下請畫出其所有的連通分量(分)
四設計題(共分)
設字符串僅由圓括號 ( 和 ) 方括號 [ 和 ] 花括號 { 和 } 組成利用鏈棧的操作編寫一個檢查括號是否正確配對的算法 int Matcher(LStackTP *ls) 例如 [{{()}[]}(){[]}] 是正確的而 {({()[]})}])} 則不正確設鏈棧定義如下(分)
typedef struct node
{ char data;
struct node *next;
} LStackTp;
利用一維數組 a 可以對 n 個整數進行排序其中一種排序算法的處理思想是將 n 個整數分別作為數組 a 的 n 個元素值每次(即第 i 次)從元素 a[i] 到 a[n] 中挑出最小的一個元素 a[k](i≤k≤n) 然後將 a[k] 與 a[i] 換位這樣反復 n 次完成排序編寫實現上述算法的函數 void sort(int a[]int n) (分)
From:http://tw.wingwit.com/Article/program/sjjg/201311/23391.html
