第一部分 選擇題
一單項選擇題（本大題共小題每小題分共分）在每小題列出的四個選項中只有一個選項是符合題目要求的請將正確選項前的字母填在題後的括號內
算法分析的目的是( ? C? )
A找出數據結構的合理性 B研究算法中的輸入/輸出關系
C分析算法的效率以求改進 D分析算法的易讀性
在需要經常查找結點的前驅與後繼的場合中使用(? B )比較合適
A單鏈表 B雙鏈表
C順序表 D循環鏈表
下面關於線性表的敘述中錯誤的為(? D ? )
A順序表使用一維數組實現的線性表
B順序表必須占用一片連續的存儲單元
C順序表的空間利用率高於鏈表
D在鏈表中每個結點只有一個鏈域
帶頭結點的單鏈表head為空的判斷條件是( B )
A head=NIL ? B head>next=NIL
C head>next=head ? D head< >NIL
隊列通常采用兩種存儲結構是( A )
A順序存儲結構和鏈表存儲結構 B散列方式和索引方式
C鏈表存儲結構和數組 D線性存儲結構和非線性存儲結構
按照二叉樹的定義具有個結點的二叉樹有(? C? )種
A ? B ? C ? D
二叉樹的結構如下圖所示其中序遍歷的序列為( ? )
Aabdgcefh
Bdgbaechf
Cgdbehfca
Dabcdefgh
深度為的二叉樹至多有(? C? )個結點 (^M)
A ? B ? C ? D
對於一個具有n個頂點的無向圖若采用鄰接表表示則存放表頭結點的數組的大小為 (? A? )
An ? Bn+ ? Cn ? Dn+邊數
在一個具有n個頂點的無向圖中要連通全部頂點至少需要(? C? )條邊
An ? Bn+ ? Cn ? Dn/
靜態查找表與動態查找表二者的根本差別在於(? B? )
A它們的邏輯結構不一樣
B施加在其上的操作不同
C所包含的數據元素的類型不一樣
D存儲實現不一樣
散列文件使用散列函數將記錄的關鍵字值計算轉化為記錄的存放地址因為散列函數不是一對一的關系所以選擇好的( ?D? )方法是散列文件的關鍵
A散列函數 ? B除余法中的質數
C沖突處理 ? D散列函數和沖突處理
對於大文件的排序要研究在外設上的排序技術即( C? )
A快速排序法 ? B內排序法
C外排序法 ? D交叉排序法
設有個無序的元素希望用最快的速度挑選出其中前個最大的元素最好選用(? C? )法
A冒泡排序 B快速排序
C堆排序 D基數排序
二判斷題(判斷下列各題正確的在題干後面括號內打√錯誤的打×每小題分共分)
所謂數據的邏輯結構指的是數據元素之間的邏輯關系( ? )
在線性結構中每個結點都有一個直接前驅和一個直接後繼( ? )
插入和刪除是數組的兩種基本操作( ? )
在鏈棧的頭部必須要設置頭結點( ? )
在二叉樹中插入結點則該二叉樹便不再是二叉樹( ? )
查找表的邏輯結構是集合( ? )
靜態查找表的檢索與修改被分成兩個不交叉的階段分別進行( ? )
在索引順序文件中插入新的記錄時必須復制整個文件( ? )
如果某種排序算法是不穩定的則該方法沒有實際的應用價值( ? )
對於n個記錄的集合進行冒泡排序在最壞情況下所需要的時間是(n)( ? )
三填空題(每小題分共分)
程序設計的實質是________和________
設由字符串a=′data′b=′structure′c=′′則a與c連接然後與b連接的結果為________
通常單鏈表的頭結點指的是________單鏈表的首結點指的是________
一個隊列的入隊序列是abcd則隊列的輸出序列為________
棧結構通常采用的兩種存儲結構是________和________
具有N個結點的完全二叉樹的深度為________
樹的三種主要的遍歷方法是________________和層次遍歷
在無向圖的鄰接矩陣A中若A〔ij〕等於則A〔ji〕等於________
采用散列技術實現散列表時需要考慮的兩個主要問題是構造________和解決________
索引順序表上的查找分兩個階段()________()________
散列文件中的記錄通常是成組存放的若干的記錄組成一個存儲單位稱作________
就文件而言按用戶的觀點所確定的基本存儲單元稱為________按外設的觀點所確定的基本存儲單元稱為________
文件的檢索有三種方式________存取________存取和按關鍵字存取
最簡單的交換排序方法是________排序
外排序的基本方法是________
四應用題(每小題分共分)
假定在學生的檔案中含有姓名學號年齡性別如采用線性表作為數據結構來實現檔案管理問題分別給出線性表的在順序實現下的類型定義和在鏈接實現下的類型定義
有一份電文中共使用五個字符abcde它們的出現頻率依次為請構造相應的哈夫曼樹(左子樹根結點的權小於等於右子樹根結點的權)求出每個字符的哈夫曼編碼
有初始的無序序列為{}給出對其進行歸並排序(升序)的每一趟的結果
五設計題(每小題分共分)
假設用一個循環單鏈表來表示隊列(稱為循環鏈隊)該隊列中只設一個隊尾指 針rear不設隊首指針請編寫向循環鏈隊中插入一個元素X的過程
以鄰接表為存儲結構寫出連通圖的深度優先搜索算法
設有一組關鍵字{}采用散列函數H(key)=key MOD 采用線性探測法解決沖突試在～的散列地址空間中對該關鍵字序列構造散列表
數據結構導論試題參考答案
一單項選擇題(每小題分共分) ? C ? B ? D ? B ? A
C ? B? C ? A ? C
B D C C
二判斷題(每小題分共分)
× ? × ? × × ? ×
√ ? √ ? × × √ 三填空題(每小題分共分) ? ()數據表示? ()數據處理 ?′datastructure′ ? ()在單鏈表第一個結點之前增設的一個類型相同的結點
()表結點中的第一個結點 ? abcd ? ()順序存儲結構? ()鏈表存儲結構
〔logN〕+
()先根遍歷? ()後根遍歷
()散列函數? ()沖突
()確定待查元素所在的塊 ()在塊內查找待查的元素
桶
()邏輯結構 ? ()物理結構
()順序? ()直接
冒泡排序 ? 歸並 四應用題(每小題分共分) ? 順序實現
const maxsize∶=; ｛順序表的容量｝ ? type datatype=record ｛檔案數據類型｝
name∶string〔〕;｛姓名｝
number∶integer;｛學號｝
sex∶boolean;｛性別｝
age∶integer;｛年齡｝
end;
type slist =record
data∶array 〔maxsize〕 of datatype;
last∶integer;
end;
鏈接實現
type pointer=↑node;
node=record
name∶string 〔〕;｛姓名｝
number∶interger ｛學號｝
sex∶ boolean;｛性別｝
age∶integer;｛年齡｝
next∶pointer;｛結點的後繼指針｝
end;
list=pointer;
哈夫曼樹為
相應的哈夫曼編碼為
a: ? b: ? c: ? d: ? e:
畫出正確的哈夫曼樹給分寫出相應哈夫曼編碼給分
初始無序序列? ? ? ?
｛｝ ｛｝ ｛｝ ｛｝ ｛｝ ｛｝ ｛｝｛｝ ｛｝｛｝
第一次歸並 ｛ ｝ ｛ ｝ ｛ ｝? ｛ ｝? ｛ ｝
第二次歸並 ? ｛ ? ? ｝ ｛ ? ｝? ｛ ｝
第三次歸並 ｛ ? ｝? ｛ ｝
第四次歸並 ｛ ? ? ｝
五設計題(每小題分共分)
PROCEDURE insert (VAR rear∶pointer; x∶integer);
VAR head tmp∶pointer;
BEGIN
new(tmp);
tmp↑data∶=x;
if (rear=NIL) then ｛循環隊列為空新結點是隊列的首結點｝
BEGIN
rear∶=tmp;
rear↑next∶=tmp;
END
else ｛隊列不空將新結點插入在隊列尾｝
BEGIN
head∶=rear↑next;
rear↑next∶=tmp;
rear∶=tmp;
rear↑next∶=head;
END
END;
procedure dfs(g:adjlist;v∶integer);
｛從v出發深度優先遍歷圖g｝
begin
write(v);
visited(v)∶=true; ? ｛標志v已訪問｝
p=g〔v〕link; ? ｛找v的第一個鄰接點｝
while p< >nil do
〔 if not (visited〔p↑vertex〕)
then dfs(gp↑vertex);
p∶=p↑next〕 ｛找v的下一個鄰接點｝
end;
以鄰接表為存儲結構連通圖的深度優先搜索就是順序查找鏈表
構造過程如下
H()= MOD =
H()= MOD =
H()= MOD =
H()= MOD =(沖突)
H()=(+) MOD =
H()= MOD =
H()= MOD =
H()= MOD = (沖突)
H()=(+) MOD = (仍沖突)
H()=(+) MOD =
H()= MOD = (沖突)
H()=(+) MOD = (沖突)
H()=(+) MOD = (仍沖突)
H()=(+) MOD =
H()= MOD = (沖突)
H()=(+) MOD = (仍沖突)
H()=(+) MOD =
H()= MOD =
H()= MOD = (沖突)
H()=(+) MOD = (仍沖突)
H()=(+) MOD =
H()= MOD = (沖突)
H()=(+) MOD =
因此各關鍵字相應的地址分配如下
address()=
address()=
address()=
address()=
address()=
address()=
address()=
address()=
address()=
address()=
address()=
address()=
其余的地址中為空
From:http://tw.wingwit.com/Article/program/sjjg/201404/30585.html
