數據結構試卷B卷(含答案)

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦數據結構試卷B卷(含答案)《數據結構》試卷B

一、填空題（每空1分，共15分）

1.向量、棧和隊列都是結構，可以在向量的

位置插入和刪除元素；對于棧只能在插入和刪除元素；對于隊列只能在插入和刪除元素。

2.棧是一種特別的線性表，允許插入和刪除運算的一端稱

為。不允許插入和刪除運算的一端稱為。

3.數據結構是一門討論非數值計算的程序設計問題中計算

機的以及它們之間的和運算等的學科。

4.在挨次表中插入或刪除一個元素，需要平均移動

元素，詳細移動的元素個數與

有關。

5.在具有n個單元的循環(huán)隊列中，隊滿時共有

個元素。

6.假設在有序線性表a[20]上舉行折半查找，則比較一次查找勝利的結點數為1；比較兩次查找勝利的結點數為；比較四次查找勝利的結點數為；平均查找長度為。

二、推斷正誤（推斷下列概念的正確性，并作出簡要的說明。）（每小題1分，共10分）

（）1.線性表的每個結點只能是一個容易類型，而鏈表的每個結點可以是一個復雜類型。

（）2.在表結構中最常用的是線性表，棧和隊列不太常用。

（）3.棧是一種對全部插入、刪除操作限于在表的一端舉行的線性表，是一種后進先出型結構。

（）4.對于不同的使用者，一個表結構既可以是棧，也可以是隊列，也可以是線性表。

（）5.線性表的規(guī)律挨次與存儲挨次總是全都的

（）6.棧和隊列是一種非線性數據結構。

（）7.棧和隊列的存儲方式既可是挨次方式，也可是鏈接方式。

（）8.兩個棧分享一片延續(xù)內存空間時，為提高內存

利用率，削減溢出機會，應把兩個棧的棧底分

別設在這片內存空間的兩端。

（）9.隊是一種插入與刪除操作分離在表的兩端舉行的線性表，是一種先進后出型結構。

（）10.一個棧的輸入序列是12345，則棧的輸出序列不行能是12345。

三、單項挑選題（每小題1分，共20分）

（）1．數據在計算機存儲器內表示時，物理地址與邏

輯地址相同并且是延續(xù)的，稱之為：（A）存儲結構（B）規(guī)律結構（C）挨次存儲結構（D）鏈式存儲結構

（）2.若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為

Ａ．iＢ．n=iＣ．n-i+1

Ｄ．不確定

（）3.判定一個棧ST（最多元素為m0）為空的條件

是

Ａ．ST->top0Ｂ．ST->top=0Ｃ．ST->topm0Ｄ．ST->top=m0

（）4設矩陣A是一個對稱矩陣，為了節(jié)約存儲，將其

下三角部分（如下圖所示）按行序存放在一維數組B[1,

n(n-1)/2]中，對下三角部分中任一元素ai,j(i≤j),在一維數

組B中下標k的值是：Ａ．i(i-1)/2+j-1Ｂ．i(i-1)/2+j

Ｃ．i(i+1)/2+j-1Ｄ．i(i+1)/2+j

（）5．具有n(n>0)個結點的徹低二叉樹的深度

為。

(Ａ)?log2(n)?(Ｂ)?log2(n)?(Ｃ)?log2(n)

?+1(Ｄ)?log2(n)+1?

（）6.有8個結點的無向連通圖最少有條邊。

A．5B.6C.7

D.8

7.數據結構反映了數據元素之間的結構關系。鏈表是一種??????

????????=nnnnaaaaaaA,2,1,2,21,21,1ΛΛ

A，它對于數據元素的插入和刪除

B。通常查找線性表數據元素的辦法有

C和

D兩種辦法，其中C是一種只適合于挨次存儲結構但

E的辦法；而D是一種對挨次和鏈式存儲結構均適用的辦法。

供挑選的答案：

A：①挨次存儲線性表②非挨次存儲非線性表③挨次存儲非線性表④非挨次存儲線性表

B：①不需要移動結點，不需轉變結點指針②不需要移動結點，只需轉變結點指針

③只需移動結點，不需轉變結點指針④既需移動結點，又需轉變結點指針

C：①挨次查找②循環(huán)查找③條件查找④二分法查找

D：①挨次查找②隨機查找③二分法查找

④分塊查找

E：①效率較低的線性查找②效率較低的非線性查找③效率較高的非線性查找④效率較高的線性查找

答案：A＝B＝C＝D＝E＝

8.散列法存儲的基本思想是按照A來打算B，碰撞（矛盾）指的是C，處理碰撞的兩類主要辦法是D。

供挑選的答案

A，B：①存儲地址②元素的符號③元素個數

④關鍵碼值

⑤非碼屬性⑥平均檢索長度⑦負載因子⑧散列表空間

C:①兩個元素具有相同序號②兩個元

素的關鍵碼值不同，而非碼屬性相同

③不同關鍵碼值對應到相同的存儲地址④負載因子過大⑤數據元素過多

D：①線性探查法和雙散列函數法②建溢出區(qū)法和不建溢出區(qū)法

③除余法和折疊法④拉鏈法和開地址法

答案：A＝B＝C＝D＝

9.考慮具有如下性質的二叉樹：除葉子結點外，每個結點的值都大于其左子樹上的一切結點的值。并小于等于其右子樹上的一切結點的值。

現把9個數1，2，3，…，8，9填入下圖所示的二叉樹的9個結點中，并使之具有上述性質。此時，n1的值是A，n2的值是B，n9的值是C?，F欲把10放入此樹并使該樹保持前述性質，增強的一個結點可以放在D或E。

供挑選的答案

A～C：①1②2③3④

4⑤

5⑥6

⑦7⑧8⑨9

D～E：①n7下面②n8下面

③n9下面

④n6下面⑤n1與n2之間

⑥n2與n4之間

⑦n6與n9之間⑧n3與n6之間

答案：A＝B＝C＝

D＝E＝

四、簡答題（每小題5分，共25分）

1.說明線性表、棧與隊的異同點。

2.試寫出如圖所示的二叉樹分離按先序、中序、后序遍歷時得到的結點序列

3.假設正讀和反讀都相同的字符序列為“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’則不是回文。假設一字符序列已存入計算機，請分析用線性表、堆棧和隊列等方式正確輸出其回文的可能性？

4.試比較挨次存儲結構和鏈式存儲結構的優(yōu)缺點。在什么狀況下用挨次表比鏈表好？

5.給定二叉樹的兩種遍歷序列，分離是：

前序遍歷序列：D，A，C，E，B，H，F，G，I；

中序遍歷序列：D，C，B，E，H，A，G，I，F，

試畫出二叉樹B，并簡述由隨意二叉樹B的前序遍歷序列和中序遍歷序列求二叉樹B的思想辦法。

五、閱讀理解（每小題5分，共20分）

1、已知L是無表頭結點的單鏈表，且P結點既不是首元結點，

也不是尾元結點，請寫出在P結點后插入S結點的核心語句序列。

2、閱讀下列算法，若有錯，改正之。

1.寫出下列程序段的輸出結果（隊列中的元素類型QElemType為char）。

voidmain(){

QueueQ;InitQueue(Q);

Charx=’e’;y=’c’;

EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,’y’);

DeQueue(Q,x);EnQueue(Q,x);

DeQueue(Q,x);EnQueue(Q,’a’);

while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);};Printf(x);

}

2.簡述以下算法的功能（棧和隊列的元素類型均為int）。voidalgo3(Queueintd;

InitStack(S);

while(!QueueEmpty(Q)){

DeQueue(Q,d);Push(S,d);

};

while(!StackEmpty(S)){

Pop(S,d);EnQueue(Q,d);

}

}

六、算法設計（每小題5分，共15分。至少要寫出思路）

1.寫出在挨次存儲結構下將線性表逆轉的算法，要求使用最少的附加空間。

2.編寫程序，將若干整數從鍵盤輸入，以單鏈表形式存儲起來，然后計算單鏈表中結點的個數（其中指針P指向該鏈表的第一個結點）。

3.試寫一個算法，判別讀入的一個以‘@’為結束符的字符序列是否是“回文”。

答案

一、填空題（每空1分，共15分）

1.向量、棧和隊列都是線性結構，可以在向量的任何位置插入和刪除元素；對于棧只能在棧頂插入和刪除元素；對于隊列只能在隊尾插入和隊首刪除元素。

2.棧是一種特別的線性表，允許插入和刪除運算的一端稱為棧頂。不允許插入和刪除運算的一端稱為棧底。

3.數據結構是一門討論非數值計算的程序設計問題中計算機的操作對象以及它們之間的關系和運算等的學科。

4.在挨次表中插入或刪除一個元素，需要平均移動表中一

半元素，詳細移動的元素個數與表長和該元素在表中的位置有關。

5.在具有n個單元的循環(huán)隊列中，隊滿時共有n-1個元

素。

8.假設在有序線性表a[20]上舉行折半查找，則比較一次查

找勝利的結點數為1；比較兩次查找勝利的結點數為

2；比較四次查找勝利的結點數為8；平均查找長

度為3.7。解：明顯，平均查找長度＝O（log2n）top0Ｂ．ST->top=0

Ｃ．ST->topm0Ｄ．ST->top=m0

(B)4、設矩陣A是一個對稱矩陣，為了節(jié)約存儲，將

其下三角部分（如下圖所示）按行序存放在一維數組B[1,

n(n-1)/2]中，對下三角部分中任一元素ai,j(i≤j),在一維數

組B中下標k的值是：

Ａ．i(i-1)/2+j-1Ｂ．i(i-1)/2+jＣ．i(i+1)/2+j-1Ｄ．i(i+1)/2+j

（C）5．具有n(n>0)個結點的徹低二叉樹的深度

為。

(Ａ)?log2(n)?(Ｂ)?log2(n)?(Ｃ)?log2(n)

?+1(Ｄ)?log2(n)+1?

（C）6.有8個結點的無向連通圖最少有條邊。

A．5B.6C.7??????

????????=nnnnaaaaaaA,2,1,2,21,21,1ΛΛ

D.8

7、答案：A＝④B＝②C＝④D＝①E＝③

8、答案：A＝④B＝①C＝③D＝④

9、答案：A＝⑦B＝④C＝⑥D＝②E＝⑥

四、簡答題（每小題4分，共20分）

1.說明線性表、棧與隊的異同點。

劉答：相同點：都是線性結構，都是規(guī)律結構的概念。都可以用挨次存儲或鏈表存儲；棧和隊列是兩種特別的線性表，即受限的線性表，只是對插入、刪除運算加以限制。

不同點：①運算規(guī)章不同，線性表為隨機存取，而棧是只允許在一端舉行插入、刪除運算，因而是后進先出表LIFO；隊列是只允許在一端舉行插入、另一端舉行刪除運算，因而是先進先出表FIFO。

②用途不同，堆棧用于子程調用和庇護現場，隊列用于多道作業(yè)處理、指令寄存及其他運算等等。

2.試寫出如圖所示的二叉樹分離按先序、中序、后序遍歷時得到的結點序列。

答：DLR：ABDFJGKCEHILM

LDR:BFJDGKACHELIM

LRD：JFKGDBHLMIECA

3.假設正讀和反讀都相同的字符序列為“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’則不是回文。假設一字符序列已存入計算機，請分析用線性表、堆棧和隊列等方式正確輸出其回文的可能性？

答：線性表是隨機存儲，可以實現，靠循環(huán)變量（j--）從表尾開頭打印輸出；

堆棧是后進先出，也可以實現，靠正序入棧、逆序出棧即可；

隊列是先進先出，不易實現。

哪種方式最好，要詳細狀況詳細分析。若正文在機內已是挨次存儲，則直接用線性表從后往前讀取即可，或將堆棧棧頂開到數組末尾，然后直接用POP動作實現。（但堆棧是先減后壓還是……）

若正文是單鏈表形式存儲，則等同于隊列，需開輔助空間，可以從鏈首開頭入棧，所有壓入后再依次輸出。

4.試比較挨次存儲結構和鏈式存儲結構的優(yōu)缺點。在什么狀況下用挨次表比鏈表好？

答：①挨次存儲時，相鄰數據元素的存放地址也相鄰（規(guī)律與物理統(tǒng)一）；要求內存中可用存儲單元的地址必需是延續(xù)的。

優(yōu)點：存儲密度大（＝1？），存儲空間利用率高。缺點：插入或刪除元素時不便利。

②鏈式存儲時，相鄰數據元素可任意存放，但所占存儲空間分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針

優(yōu)點：插入或刪除元素時很便利，使用靈便。缺點：存儲密度?。╪ext=P->next;

P->next=S;

2、答：這是找結點后繼的程序。

共有3處錯誤。

注：當rtag

＝1時說明內裝后繼指針，可直接返回，第一句無錯。

當rtag＝0時說明內裝右孩子指針，但孩子未必是后繼，需要計算。中序遍歷應該先左再根再右，所以應該找左子樹直到葉子處。r=r->lchild;直到LTag=1；

應改為：while(!r->Ltag)r=r->Lchild;

3.寫出下列程序段的輸出結果（隊列中的元素類型QElem

Type為char）。

voidmain(){

QueueQ;InitQueue(Q);

Charx=’e’;y=’c’;

EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,y);

DeQueue(Q,x);EnQueue(Q,x);

DeQueue(Q,x);EnQueue(Q,’a’);

while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);};Printf(x);

}

答：輸出為“char”。

4.簡述以下算法的功能（棧和隊列的元素類型均為int）。voidalgo3(Queueintd;

InitStack(S);

while(!QueueEmpty(Q)){

DeQueue(Q,d);Push(S,d);

};

while(!StackEmpty(S)){

Pop(S,d);EnQueue(Q,d);

}

}

答：該算法的功能是：利用堆棧做輔助，將隊列中的數據元素舉行逆置。

六、算法設計（每小題5分，共15分。至少要寫出