數(shù)據(jù)結(jié)構(gòu)期末考試試題和標(biāo)準(zhǔn)答案及評分標(biāo)準(zhǔn)(共11頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)試題（A卷）（考試時間： 90分鐘） 一、單項選擇題（本大題共15小題，每小題2分，共30分）（每題只有一個選項是正確的,將答案填寫在括號內(nèi)，錯選、多選不得分）1.（ ）是組成數(shù)據(jù)的基本單位，是一個數(shù)據(jù)整體中相對獨立的單元。A數(shù)據(jù) B.數(shù)據(jù)元素C.數(shù)據(jù)對象D.數(shù)據(jù)結(jié)構(gòu)2.算法計算量的大小稱為算法的（ ）。A.效率     B.復(fù)雜度 C.數(shù)據(jù)元素之間的關(guān)系    D.數(shù)據(jù)的存儲方法3.若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入或刪除運(yùn)算，則采用以下（

2、）方式最節(jié)省時間。A.鏈?zhǔn)酱鎯?B. 索引存儲 C.順序存儲 D.散列存儲4.下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？（ ）A.存儲密度大  B.插入運(yùn)算方便  C.刪除運(yùn)算方便  D.可方便地用于各種邏輯結(jié)構(gòu)的存儲表示5.在一個單鏈表中，若刪除p所指結(jié)點的后續(xù)結(jié)點，則執(zhí)行（ ）。A.p->next=p->next->next B.p->next=p->nextC.p=p->next;p->next=p->next->next D.p=p->next->next 6.帶頭結(jié)點的單鏈表head為空的判定條件是

3、（ ）。A.head=NULL B.head->next=NULLC.head->next=headD.head!=NULL7.非空的循環(huán)單鏈表head的尾結(jié)點(由p所指向)滿足（ ）。A.p->head=NULLB.p=NULLC.p->next=head D.p=head8.下面關(guān)于線性表的敘述中，錯誤的是哪一個？（ ）A.線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B.線性表采用順序存儲，便于進(jìn)行插入和刪除操作。C.線性表采用鏈?zhǔn)酱鎯?，不必占用一片連續(xù)的存儲單元。D.線性表采用鏈?zhǔn)酱鎯?，便于插入和刪除操作。9.隊列操作的原則是（ ）。A.后進(jìn)先出B.先進(jìn)先出C

4、.只能進(jìn)行插入D.只能進(jìn)行刪除10.棧中允許進(jìn)行插入和刪除的一端稱為（ ）。 A.棧首 B.棧尾 C.棧頂 D.棧底11假設(shè)以數(shù)組An存放循環(huán)隊列的元素，其首尾指針分別為front和rear，則當(dāng)前隊列中的元素個數(shù)為（ ）。A（rear-front+n）%n B. rear-front+1C. (front-rear+n)%n D.(rear-front)%n12.最大容量為n的循環(huán)隊列，隊尾指針是rear，隊首指針是front，則隊空的判斷條件是（ ）。A.（rear+1）%n=front B.rear=frontC.rear+1=front D.(rear-1)%n=front13. 將一

5、個十進(jìn)制的數(shù)轉(zhuǎn)換成二進(jìn)制的數(shù)，可以使用以下一種稱為（ ）的數(shù)據(jù)結(jié)構(gòu)。A. 圖 B. 樹 C. 廣義表 D. 棧14. 把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（ ）。A. 有2種 B. 有3種 C. 有4種 D. 唯一的15.一棵左右子樹均不空的二叉樹在先序線索化后，其中空鏈域的個數(shù)是（ ）。A. 3 B. 2 C. 0 D. 不確定二、填空題（本大題共10個空，每空2分，共計20分）1數(shù)據(jù)結(jié)構(gòu)是研究程序設(shè)計中計算機(jī)操作的 以及它們之間的關(guān)系和運(yùn)算的一門學(xué)科。2在一個單鏈表中，已知指針q所指結(jié)點是指針p 所指結(jié)點的前驅(qū)結(jié)點，若在q和p之間插入結(jié)點s，則應(yīng)執(zhí)行兩條語句：_ _ ， 。3字符串采

6、用結(jié)點大小為2的鏈表作為其存儲結(jié)構(gòu)，是指鏈表的每個鏈結(jié)點的 域中只存放了2個字符。4廣義表（a,b,c,d）的表尾是 。5一棵深度為k的二叉樹，最多有 個結(jié)點。6已知有向圖G=（V，E），其中: V=v1,v2,v3,v4,v5,v6,v7,E=<v1,v2>,<v1,v3>,<v1,v4>,<v2,v5>,<v3,v5>,<v3,v6>,<v4,v6>,<v5,v7>,<v6,v7>,則G的拓?fù)湫蛄惺莀 _ _。7. 有n個頂點的連通圖至少有 條邊。8. 圖的存儲常采用 和 兩種方法。

7、三、判斷題（本大題共10小題，每題1分，共10分）（請在每小題后面的括號里寫出答案，如果正確，請寫“”，如果錯誤，請寫“×”）1.線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。（ ）2線性表就是順序存儲的表。（ ）3.當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)采用順序存儲結(jié)構(gòu)。（ ）4線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)所需要的存儲空間一般要多于順序存儲結(jié)構(gòu)。（ ）5.串的長度是指串中所含不同字符的個數(shù)。（ ）6.對稀疏矩陣進(jìn)行壓縮存儲的目的是節(jié)省存儲空間。（ ）7.二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以它不能采用順序存儲結(jié)構(gòu)存儲。（ ）8

8、.任意一棵二叉樹中至少有一個結(jié)點的度為2。（ ）9.對線性表進(jìn)行二分查找時，要求線性必須以順序方式存儲，且結(jié)點按關(guān)鍵字有序排序。（ ）10.采用線性探測法解決沖突問題，所產(chǎn)生的一系列后繼散列地址必須大于等于原散列地址。（ ）四、應(yīng)用題（本小題共5小題，每小題6分，共30分）1.簡述以下算法的功能（假設(shè)棧和隊列的元素類型均為int）(6分)void fun1(Queue &Q)Stack S;int x;Initstack(S);While(!QueueEmpty(Q) DeQueue(Q,x); Push(S,x); While(!StackEmpty(S) Pop(S,x); EnQ

9、ueue(Q,x); 2.請將如圖4.1所示的一棵樹轉(zhuǎn)換成一棵二叉樹。（6分）圖4.1 一棵樹3.給定葉結(jié)點(a,b,c,d,e,f,g)，權(quán)值分別為23,12,15,7,17,2,8，畫出對應(yīng)的哈夫曼樹，并寫出各葉結(jié)點的哈夫曼編碼。（6分）4.（6分）已知圖G的鄰接表如圖4.2所示，則：從頂點v1出發(fā)的深度優(yōu)先搜索序列為_ _ _。從頂點v1出發(fā)的廣度優(yōu)先搜索序列為_ _ _。圖4.2 圖G的鄰接表ââââââââââââââââ&#

10、226;âââââââââââââââââââââââââââââââââââââââââââââââââ&#

11、226;âââââââââââââââââââââââââââââââââââââââââââââââââ&#

12、226;âââââââââââââââââââââââââââââââââââââââââââââââââ&#

13、226;âââââââââââââââââââââââââââââââââââââââââââââââââ&#

14、226;âââââââââââââââââââââââââââââââââââââââââââââââââ&#

15、226;âââââââââââââââââââââââââââââââââââââââââââââââââ&#

16、226;ââââââââââââââââââââââââââââââââââââââââ密封線密封線5.求構(gòu)造圖4.3所示無向網(wǎng)的最小生成樹（6分）圖4.3 無向網(wǎng)五、算法設(shè)計題（本大題共1小題，每小

17、題10分，共10分）1.已知查找表的數(shù)據(jù)元素類型如下：Typedef struct Rectypeint num;char name8;Rectype; 假設(shè)查找表中有n個記錄，并且是按num降序順序存儲Typedef Rectype Sqlist100;要求：（1）寫出對給定值K進(jìn)行二分查找的算法和main函數(shù)。（2）二分查找算法的函數(shù)頭部為“int binsearch(Sqlist R,int n,int K) “（3）在main函數(shù)中建立該查找表、調(diào)用二分查找算法，并輸出查找結(jié)果。數(shù)據(jù)結(jié)構(gòu)試題（B卷）（考試時間：90 分鐘） 一、單項選擇題（本大題共15小題，每小題2分，共30分）（每題

18、只有一個選項是正確的,將答案填寫在括號內(nèi)，錯選、多選不得分）1在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的（ ）結(jié)構(gòu)是獨立于計算機(jī)的。A.邏輯 B.存儲 C.散列 D.索引2下列程序段的時間復(fù)雜度為（ ）。for(i=0;i<n;i+) x=x-2;A.O（2n）    B.O（n） C. O（1） D. O（n2）3. 鏈?zhǔn)酱鎯Y(jié)構(gòu)表示的線性表也稱為（ ）。 A.鏈表 B.順序表 C.雙鏈表 D.物理表4.不帶頭結(jié)點的單鏈表（頭指針為head）為空的判定條件是（ ）。 Ahead=NULL Bhead->next=head Chead->next=NULL Dhead!=NUL

19、L5線性表若采用順序結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（ ）。A一定是不連續(xù)的 B部分地址是連續(xù)的C一定是連續(xù)的 D連續(xù)不連續(xù)都可以6. 對于單鏈表，在兩個結(jié)點之間插入一新結(jié)點需要修改的指針共（ ）個。A.0B.1 C.2 D.47.若線性表中有n個元素，算法（ ）在單鏈表上實現(xiàn)要比在順序表上實現(xiàn)效率更高。A.刪除所有值為x的元素 B.在最后一個元素的后面插入一個新元素C.順序輸出前k個元素 D.交換其中某兩個元素的值8.對于順序表，訪問結(jié)點和增加、刪除結(jié)點的時間復(fù)雜度分別為（ ）。A.O(n)O(n) B. O(1)O(n) C. O(n) O(1)D. O(1) O(1)9.隊列的刪除操

20、作是在（ ）進(jìn)行。A隊首 B隊尾 C隊首前一單元 D隊尾后一單元10.下列關(guān)于棧的敘述中，正確的是（ ）。A棧底元素一定是最后入棧的元素 B棧操作遵循先進(jìn)后出的原則C棧頂元素一定是最先入棧的元素 D以上三種說法都不對11.設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧S ,一個元素出棧后即進(jìn)入Q，若6個元素出隊的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少是（ ）個。A.3 B. 4 C.5 D.612.假設(shè)為循環(huán)隊列分配的向量空間為Q20,若隊列的長度和隊頭指針值分別為13和17，則當(dāng)前尾指針的值為_。A.10 B.11 C.12  D

21、.1313.銀行業(yè)務(wù)叫號系統(tǒng)采用了 數(shù)據(jù)結(jié)構(gòu)。A棧 B廣義表 C隊列D圖14.按照二叉樹的定義，具有3個結(jié)點的不同形狀的二叉樹有_種。A.3B.4 C.5 D.615. n個結(jié)點的線索二叉樹上含有的線索數(shù)為_。A.0B.n-1 C.n+1 D.2n二、填空題（本大題共10個空，每空2分，共20分）1數(shù)據(jù)結(jié)構(gòu)包含三個方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu) 、數(shù)據(jù)的 結(jié)構(gòu)和對數(shù)據(jù)所施加的操作。2已知指針q值為NULL、指針p指向單鏈表L中的某結(jié)點，則刪除其后繼結(jié)點（要求由指針q指向）的語句是 ， ，free(q)。3設(shè)廣義表L=（a,( )） ,則Head(L)= 。4當(dāng)且僅當(dāng)兩個串的 相等并且各個對應(yīng)位置

22、上的字符都相等時，稱這兩個串相等。5.二叉樹的第4層結(jié)點數(shù)最多為 個。6除了利用求關(guān)鍵路徑的方法，還可以利用 方法判斷出一個有向圖是否有環(huán)（回路）。7圖的遍歷主要有 和 兩種方法。8. 具有4個頂點的無向完全圖有 條邊。三、判斷題（本大題共10小題，每題1分，共10分）（請在每小題后面的括號里寫出答案，如果正確，請寫“”，如果錯誤，請寫“×”）1.對于一個線性表，采用順序存儲方式進(jìn)行插入和刪除結(jié)點時效率太低，采用鏈?zhǔn)酱鎯Ψ绞礁?。?）2.所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。（ ）3.在順序表中，最后一個元素有一個后繼。（ ）4.線性表就是鏈?zhǔn)酱鎯Φ谋怼＃?）5.串是一種特殊的線性

23、表，其特殊性體現(xiàn)在數(shù)據(jù)元素可以是多個字符。（ ）6.對稀疏矩陣進(jìn)行壓縮存儲的目的是便于輸入和輸出。（ ）7.任意一棵二叉樹中的度可以小于2。（ ）8.樹形結(jié)構(gòu)最適合用來表示元素之間具有分支層次關(guān)系的數(shù)據(jù)。（ ）9.當(dāng)采用分塊查找時，數(shù)據(jù)的組織方式為：數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)必須有序。（ ）10.順序查找法適合于存儲結(jié)構(gòu)為順序存儲或鏈?zhǔn)酱鎯Φ木€性表。（ ）四、應(yīng)用題（本小題共5小題，每小題6分，共30分）1. 下面是對二叉樹進(jìn)行操作的算法，其功能為 （6分）Void unknown(Btree BT)Btree p=BT,temp;If(p!=NULL) temp=p->lchild;p

24、->lchild=p->rchild;p->rchid=temp;unknown(p->lchild);unknown(p->rchild); 2. 請寫出如圖4.1所示二叉樹的先序遍歷序列、中序遍歷序列和后序遍歷序列。（6分）圖4.1 二叉樹3已知如圖4.2所示的有向圖，請給出：（共6分） 每個頂點的入度和出度；（2分）圖4.2 有向圖 鄰接矩陣；（4分）4.要求用普里姆算法畫出如圖4.3所示無向網(wǎng)的最小生成樹，假設(shè)從a頂點出發(fā)構(gòu)造最小生成樹，寫出各條邊加入生成樹的次序（用權(quán)值表示）。（6分）圖4.3 無向網(wǎng) 5.下列算法的運(yùn)行結(jié)果是 （棧的元素類型為char）

25、(6分)void main() stack S;char x=a,y=b;initstack(S);push(S,x); push(S,y); printf(“%c”,x);printf(“%c”,y);pop(S,x); pop(S,y); printf(“%c”,x); printf(“%c”,y);五、算法設(shè)計題（本大題共1小題，每題10分，共10分）1. 已知查找表的數(shù)據(jù)元素類型如下：Typedef struct Rectypeint num;char name8;Rectype; 假設(shè)查找表中有n個記錄，并且是采用順序存儲Typedef Rectype Sqlist100;要求：（1

26、）寫出對給定值K進(jìn)行從前端開始順序查找的算法和main函數(shù)。（2）順序查找算法的函數(shù)頭部為“int search(Sqlist R,int n,int K) “（3）在main函數(shù)中建立該查找表、調(diào)用順序查找算法，并輸出查找結(jié)果。 數(shù)據(jù)結(jié)構(gòu) （A卷）試題標(biāo)準(zhǔn)答案及評分標(biāo)準(zhǔn)一、單項選擇題（ 本大題共15小題，每小題2分，共計30分）1.B 2.B 3.C 4.A 5.A 6.B 7.C 8.B 9.B 10.C11.A 12.B 13.D 14.D 15.C 二、填空題（本大題共10個空，每空2分，共計20分）1.對象2.q->next=s,s->net=p3.數(shù)據(jù)4.（b,c,d）

27、5.2k-1 6.v1,v3,v4,v6,v2,v5,v77.n-18.鄰接矩陣，鄰接表（不分先后）三、判斷題（本大題共10小題，每小題1分，共計10分）1.× 2.× 3. 4. 5.× 6. 7. × 8. × 9. 10.×四、應(yīng)用題（本大題共5小題，每小題6分，共30分）1利用棧將隊列中的元素逆置（6分） 2.（6分） 3. （6分）其中：哈夫曼樹（2.5分） 哈夫曼編碼（3.5分）a:10 b:110 c:111 d:0111 e:00 f:0110 g:0114.（6分）其中深度優(yōu)先搜索序列為v1,v2,v3,v6,v5,

28、v4 (3分)廣度優(yōu)先搜索序列為v1,v2,v5,v4,v3,v6 (3分) 5.（6分）五、算法設(shè)計題（10分）int binsearch(Sqlist R,int n,int K) （5分）int low=0,high=n-1,mid;while(low<=high) mid=(low+high)/2; if(Rmid.key=K) return mid;else if(Rmid.key>K) low=mid+1; else high=mid-1; return -1; main() (5分) Sqlist R ;int n,k,i;scanf(“%d”,&n);for(i=0;i<n;i+)/*按num升序輸入數(shù)據(jù)*/scanf(“%dn”,&am