數(shù)據(jù)結構樣卷

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結構樣卷第1頁

一.選擇題（30分，每題2分）（請將答案填寫到表格中）

1．從規(guī)律上可以把數(shù)據(jù)結構分為（）兩大類。

A.動態(tài)結構和靜態(tài)結構C.線性結構和非線性結構

A．廣義表B.串

C.稀疏矩陣

D.二叉樹

B.順序結構和鏈式結構D.初等結構和構造型結構

2．以下數(shù)據(jù)結構中，哪一個是線性結構（）？

3．如下圖所示，若要刪除p所指的結點后一個結點，需要執(zhí)行的操作是______。

A.p->link=p->link->link;deletep;C.q=p->link;p->linkp=q->link;deletep;

B.q=p->link;p->link=q->link;deleteq;D.p=p->link;deletep;

4．下面關于線性表的表達中，錯誤的是______。

A.線性表采用鏈接存儲，存儲密度大。B.線性表采用順序存儲，是一種隨機存取結構。C.線性表采用順序存儲，必需占用一片連續(xù)的存儲單元。D.線性表采用鏈接存儲，便于插入和刪除操作。

5．已知廣義表A((a,b,c),(d,e,f))，從A中取出原子d的運算是______。A.Head(Tail(Head(A)))C.Head(Head(Tail(A)))

A.便于進行矩陣運算C.節(jié)省存儲空間

7．有5個元素按1，2，3，4，5的順序進棧，______不是合法的出棧序列。

A.12345A.49

B.45312

C.34521

D.23415

B.Head(Tail(Head(Tail(A))))D.Head(Head(Tail(Tail(A))))

6．用三元組表對稀疏矩陣進行壓縮存儲目的是______。

B.便于輸入和輸出D.降低運算的時間繁雜度

8．一棵具有25個葉子結點的二叉樹至少有______個結點。

B.50

C.51

D.52

9．表達式a*(b+c)-d的后綴表達式是()。第2頁

A.abcd*+-

B.abc+*d-C.abc*+d-D.-+*abcd

10．已知圖的鄰接矩陣如下圖所示，則從頂點0出發(fā)按深度優(yōu)先遍歷的結果是______。

A.0243156

A.串

B.0136542

C.0134256

D.0361542

11．實現(xiàn)廣度優(yōu)先探尋算法中需要使用______作為輔助結構。

B.線性表

C.棧

D.隊列

12．假使要求一個線性表既能較快的查找，又能適應動態(tài)變化的要求，則可采用______查找法。

A.分塊B.順序

13．有關串的表達中，______是錯誤的。A.串只是一種操作特別的線性表

B.串的匹配是一種重要的操作D.串可以順序存儲，也可以鏈式存儲

C.子串替換可以由一些基本的串操作實現(xiàn)

C.折半

D.基于屬性

14．分別以以下序列構造二叉排序樹，與用其它三個序列所構造的結果不同的是()。

A.（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，120，110，130）D.(100，80，60，90，120，130，110)

15．下面給出的四種排序法中______排序法是不穩(wěn)定性排序法。

A.直接插入B.冒泡C.二路歸并D.堆排序

選擇題答案1二.判斷題：（10分，每題1分）

1．算法的優(yōu)劣與所用計算機無關，但與算法描述語言相關……………（）2．順序存儲方式也能用于存儲非線性結構…………………（.）3．任何遞歸算法都需要利用棧，才能轉化為非遞歸算法………………..（）4．數(shù)組是線性表的推廣，因此，數(shù)組是一種線性結構……………（）5．KMP算法的特點是在模式匹配時指示主串的指針不會變小…………（）

23456789101112131415第3頁

6．若X是二叉中序線索樹中一個有左孩子的結點，且X不為根，則X的前驅為X的左子樹中最右的葉子結點…………………………（）7．貪新算法旨在由局部最優(yōu)，從而達到全局最有，因此，貪心算法總能求得最優(yōu)解…（）8．有一個長度為12的有序表，按二分查找法對該表進行查找，在表內(nèi)各元素查找概率相等的狀況下，查找成功所需的平均比較次數(shù)為39/12………….………….…………（.）9．散列函數(shù)有兩條標準：簡單和均勻………………..………………..………………..（）10．排序算法中的比較次數(shù)與初始元素序列的排列無關………..（）

三．讀程序：（每題5分，共10分）現(xiàn)有一個單向鏈表類，如下所示：#include

templateclassLinkedList;templateclassListNode{Tdata;

//結點數(shù)據(jù)域

ListNode*link;//結點指針域

friendclassLinkedList;

ListNode(ListNode*ptr=NULL){link=ptr;}

ListNode(constT//鏈表結點數(shù)據(jù)類型

templateclassLinkedList{public:

LinkedList(){first=newListNode;}//初始化帶頭結點的單向鏈表~LinkedList(){makeEmpty();}voidmakeEmpty();intLength()const;

ListNode*Search(constT

ListNode*getHead()const{returnfirst;}ListNode*getData(inti);voidsetData(inti,Tx);intInsert(inti,Tx);intRemove(inti,intk);

intIsEmpty()const{returnfirst->link==NULL;}voidinput();voidoutput();

voidA(LinkedListprivate:

ListNode*first;//定義頭指針};//鏈表模板類第4頁

1．其中，Search函數(shù)的功能是若鏈表中存在值為x的結點，則返回該結點的地址；否則，返回空指針。在下面的Search函數(shù)實現(xiàn)代碼的空白處填上適當?shù)腃++語句，使之能實現(xiàn)指定的功能。template

boolLinkedList::Search(Tintn=Length();while(p){

if(!Search(p->data)){Insert(n,p->data);}p=p->link;}

return;}

（1）A函數(shù)實現(xiàn)的具體操作是：______________________________________________________

_________________________________________________________________________________。

（2）假定鏈表類中定義的其他函數(shù)均已實現(xiàn)，編寫一個main函數(shù)，建立兩個鏈表，運行A函數(shù)，并寫出運行結果（兩個鏈表建立后效果如下所示）。

②：⑤③：ListNode*p=______①__;while(②){}

⑤;if(③__)returnp;_______④_________;第5頁

四.簡答題：（30分）

1．什么是隊列？試例舉出一個隊列在實際應用中的實例，說明隊列的特點。（4分）