數據結構面試題及答案

① 數據結構筆試題

本文出自數據結構十套筆試題之第一套，本站為原創作品，轉載請註明出處，謝謝！

• 一、選擇題

• 1、棧和隊列的共同特點是( )。
  A.只允許在端點處插入和刪除元素
  B.都是先進後出
  C.都是先進先出
  D.沒有共同點

參考答案是：

歸並

② 面試常問的資料庫問題及答案

目前在職場中很難找到非常合格的資料庫開發人員。有人說:「SQL開發是一門語言，它很容易學，但是很難掌握。」
在面試應聘的SQL Server資料庫開發人員時，我運用了一套標準的基準技術問題。下面這些問題是我覺得能夠真正有助於淘汰不合格應聘者的問題。它們按照從易到難的順序排列。當你問到關於主鍵和外鍵的問題時，後面的問題都十分有難度，因為答案可能會更難解釋和說明，尤其是在面試的情形下。
你能向我簡要敘述一下SQL Server 2000中使用的一些資料庫對象嗎?
你希望聽到的答案包括這樣一些對象:表格、視圖、用戶定義的函數，以及存儲過程;如果他們還能夠提到像觸發器這樣的對象就更好了。如果應聘者不能回答這個基本的問題，那麼這不是一個好兆頭。
NULL是什麼意思?
NULL(空)這個值是資料庫世界裡一個非常難纏的東西，所以有不少應聘者會在這個問題上跌跟頭您也不要覺得意外。
NULL這個值表示UNKNOWN(未知):它不表示「」(空字元串)。假設您的SQL Server資料庫里有ANSI_NULLS，當然在默認情況下會有，對NULL這個值的任何比較都會生產一個NULL值。您不能把任何值與一個 UNKNOWN值進行比較，並在邏輯上希望獲得一個答案。您必須使用IS NULL操作符。

什麼是索引?SQL Server 2000里有什麼類型的索引?
任何有經驗的資料庫開發人員都應該能夠很輕易地回答這個問題。一些經驗不太多的開發人員能夠回答這個問題，但是有些地方會說不清楚。
簡單地說，索引是一個數據結構，用來快速訪問資料庫表格或者視圖里的數據。在SQL Server里，它們有兩種形式:聚集索引和非聚集索引。聚集索引在索引的葉級保存數據。這意味著不論聚集索引里有表格的哪個(或哪些)欄位，這些欄位都會按順序被保存在表格。由於存在這種排序，所以每個表格只會有一個聚集索引。非聚集索引在索引的葉級有一個行標識符。這個行標識符是一個指向磁碟上數據的指針。它允許每個表格有多個非聚集索引。
什麼是主鍵?什麼是外鍵?
主鍵是表格里的(一個或多個)欄位，只用來定義表格里的行;主鍵里的值總是唯一的。外鍵是一個用來建立兩個表格之間關系的約束。這種關系一般都涉及一個表格里的主鍵欄位與另外一個表格(盡管可能是同一個表格)里的一系列相連的欄位。那麼這些相連的欄位就是外鍵。
什麼是觸發器?SQL Server 2000有什麼不同類型的觸發器?
讓未來的資料庫開發人員知道可用的觸發器類型以及如何實現它們是非常有益的

觸發器是一種專用類型的存儲過程，它被捆綁到SQL Server 2000的表格或者視圖上。在SQL Server 2000里，有INSTEAD-OF和AFTER兩種觸發器。INSTEAD-OF觸發器是替代數據操控語言(Data Manipulation Language，DML)語句對表格執行語句的存儲過程。例如，如果我有一個用於TableA的INSTEAD-OF-UPDATE觸發器，同時對這個表格執行一個更新語句，那麼INSTEAD-OF-UPDATE觸發器里的代碼會執行，而不是我執行的更新語句則不會執行操作。
AFTER觸發器要在DML語句在資料庫里使用之後才執行。這些類型的觸發器對於監視發生在資料庫表格里的數據變化十分好用。
您如何確一個帶有名為Fld1欄位的TableB表格里只具有Fld1欄位里的那些值，而這些值同時在名為TableA的表格的Fld1欄位里?
這個與關系相關的問題有兩個可能的答案。第一個答案(而且是您希望聽到的答案)是使用外鍵限制。外鍵限制用來維護引用的完整性。它被用來確保表格里的欄位只保存有已經在不同的(或者相同的)表格里的另一個欄位里定義了的值。這個欄位就是候選鍵(通常是另外一個表格的主鍵)。
另外一種答案是觸發器。觸發器可以被用來保證以另外一種方式實現與限制相同的作用，但是它非常難設置與維護，而且性能一般都很糟糕。由於這個原因，微軟建議開發人員使用外鍵限制而不是觸發器來維護引用的完整性。
對一個投入使用的在線事務處理表格有過多索引需要有什麼樣的性能考慮?
你正在尋找進行與數據操控有關的應聘人員。對一個表格的索引越多，資料庫引擎用來更新、插入或者刪除數據所需要的時間就越多，因為在數據操控發生的時候索引也必須要維護。
你可以用什麼來確保表格里的欄位只接受特定范圍里的值?
這個問題可以用多種方式來回答，但是只有一個答案是「好」答案。您希望聽到的回答是Check限制，它在資料庫表格里被定義，用來限制輸入該列的值。
觸發器也可以被用來限制資料庫表格里的欄位能夠接受的值，但是這種辦法要求觸發器在表格里被定義，這可能會在某些情況下影響到性能。因此，微軟建議使用Check限制而不是其他的方式來限制域的完整性。
<b?返回參數和output參數之間的區別是什麼?>如果應聘者能夠正確地回答這個問題，那麼他的機會就非常大了，因為這表明他們具有使用存儲過程的經驗。
返回參數總是由存儲過程返回，它用來表示存儲過程是成功還是失敗。返回參數總是INT數據類型。
OUTPUT參數明確要求由開發人員來指定，它可以返回其他類型的數據，例如字元型和數值型的值。(可以用作輸出參數的數據類型是有一些限制的。)您可以在一個存儲過程里使用多個OUTPUT參數，而您只能夠使用一個返回參數。
什麼是相關子查詢?如何使用這些查詢?
經驗更加豐富的開發人員將能夠准確地描述這種類型的查詢。
相關子查詢是一種包含子查詢的特殊類型的查詢。查詢里包含的子查詢會真正請求外部查詢的值，從而形成一個類似於循環的狀況。</b?返回參數和output參數之間的區別是什麼?>

③ 數據結構（C#語言版）筆試試題與答案

《數據結構》期末考試試卷（ A ）

一、 選擇題（每小題2分，共24分）
1．計算機識別、存儲和加工處理的對象被統稱為( A )
A.數據 B.數據元素
C.數據結構 D.數據類型
2．棧和隊列都是（ A ）
A．限制存取位置的線性結構 B．順序存儲的線性結構
C．鏈式存儲的線性結構 D．限制存取位置的非線性結構
3．鏈棧與順序棧相比，比較明顯的優點是( D )
A.插入操作更加方便 B.刪除操作更加方便
C.不會出現下溢的情況 D.不會出現上溢的情況
4．採用兩類不同存儲結構的字元串可分別簡稱為( B )
A.主串和子串 B.順序串和鏈串
C.目標串和模式串 D.變數串和常量串
5． 一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是：B
A. 110 B .108
C. 100 D. 120
6．串是一種特殊的線性表，其特殊性體現在：B
A.可以順序存儲 B .數據元素是一個字元
C. 可以鏈接存儲 D. 數據元素可以是多個字元
7．設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數至少為： C
A. 2h B .2h-1
C. 2h+1 D. h+1
軟體開發網 www.mscto.com
8．樹的基本遍歷策略可分為先根遍歷和後根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和後序遍歷。這里，我們把 由樹轉化得到的二叉樹叫做這棵樹對應的二叉樹。下列結論哪個正確？ A
A. 樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列相同
B .樹的後根遍歷序列與其對應的二叉樹的後序遍歷序列相同
C. 樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列相同
D. 以上都不對
9．一個有n個頂點的無向圖最多有多少邊？C
A. n B .n(n-1)
C. n(n-1)/2 D. 2n
10．在一個圖中，所有頂點的度數之和等於所有邊數的多少倍?C
A. 1/2 B .1
C. 2 D. 4
11．當在二叉排序樹中插入一個新結點時，若樹中不存在與待插入結點的關鍵字相同的結點，且新結點的關鍵字小於根結點的關鍵字，則新結點將成為（ A ）
A．左子樹的葉子結點 B．左子樹的分支結點
C．右子樹的葉子結點 D．右子樹的分支結點
軟體開發網 www.mscto.com
12．對於哈希函數H(key)=key%13,被稱為同義詞的關鍵字是( D )
A.35和41 B.23和39
C.15和44 D.25和51
二、已知某棵二叉樹的前序遍歷結果為A,B,D,E,G,C,F,H,I,J，其中中序遍歷的結果為D,B,G,E,A,H,F,I,J,C。請畫出二叉的具體結構。（注意要寫出具體步驟）（10分）
原理見課本128頁

三、有圖如下，請寫出從頂點c0出發的深度優先及寬度優先遍歷的結果。(10分)
深度優先；C0-C1-C3-C4-C5-C2
寬度優先：C0-C1-C2-C3-C4-C5
四、有圖如下，按Kruskal演算法求出其最小生成樹。要求寫出完整的步驟。（10分）
原理見課本250頁

五、給定線性表（12，23，45，66，76，88，93，103，166），試寫出在其上進行二分查找關鍵字值12，93，166的過程。並寫出二分查找的演算法。（20分）
0 1 2 3 4 5 6 7 8
12 23 45 66 76 88 93 103 166
過程：
mid=(0+8)/2=4
high=3,low=0 mid=1
high=0,low=0 mid=0（找到12）
high=8,low=5,mid=6（找到93）
high=8,low=7,mid=7
high=8 low=8 mid=8
演算法：見課本84頁上

六、知單鏈表的結點結構為
Data next
下列演算法對帶頭結點的單鏈表L進行簡單選擇排序，使得L中的元素按值從小到大排列。
請在空缺處填入合適的內容，使其成為完整的演算法。 (可用文字說明該演算法的基本思想及執行的過程，10分)
void SelectSort(LinkedList L)
{
LinkedList p,q,min;
DataType rcd;
p= (1) ;
while(p!=NULL) {
min=p;
q=p->next;
while(q!=NULL){
if( (2) )min=q;
q=q->next;
}
if( (3) ){
rcd=p->data;
p->data=min->data;
min->data=rcd;
}
(4) ;
}
}
本題不會。嘿嘿。。。。
七、一個完整的演算法應該具有哪幾個基本性質？分別簡要說明每一性質的含意。(5分)
輸入：
四個基本性質：1.輸入：有零個或多個有外部提供的量作為演算法的輸入
2：輸出：演算法產生至少一個量作為輸出
3.：確定性：組成演算法的每條指令是清晰的，無歧異的。
4.：有限性：演算法中每條指令的執行次數是有限的，執行每條指令的時間也是有限的

八、何謂隊列的"假溢"現象？如何解決？（5分）
隊列的假溢現象是指數組實現的順序隊列中，隊尾指針已到達數組的下表上界產生上溢而隊頭指針之前還有若干 空間閑置的現象。解決的辦法之一是利用循環隊列技術使數組空間的首尾相連。

九、說明並比較文件的各種物理結構。（6分）