《《數(shù)據(jù)結(jié)構(gòu)》期末考試題及答案6頁》由會員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu)》期末考試題及答案6頁（6頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、2011-2012學年第一學期期末考查
《數(shù)據(jù)結(jié)構(gòu)》試卷
（答案一律寫在答題紙上，在本試卷上做答無效）
一、選擇（每題1分，共10分）
1.長度為n的線性表采用順序存儲結(jié)構(gòu)，一個在其第i個位置插入新元素的算法時間復雜度為（D）
A.O(0) B.O(1) C.O(n) D.O(n2)
2.六個元素按照6，5，4，3，2，1的順序入棧，下列哪一個是合法的出棧序列？（ D）
A.543612 B.453126
2、 C.346512 D.234156
3.設(shè)樹的度為4，其中度為1、2、3、4的結(jié)點個數(shù)分別是4、2、1、2，則樹中葉子個數(shù)為（B ）
A.8 B.9 C.10 D.11
4.設(shè)森林F對應(yīng)的二叉樹B有m個結(jié)點，B的右子樹結(jié)點個數(shù)為n，森林F中第一棵樹的結(jié)點個數(shù)是（ B ）
A.
3、 m-n B.m-n-1 C.n+1 D.m+n
5.若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（ B）
A.9 B.11 C.15 D.不確定
6.下列哪一個方法可以判斷出一個有向圖是否有環(huán)。（ A）
A.深度優(yōu)先遍歷 B.拓撲排序 C.求最短路徑 D.求關(guān)鍵路徑
7.第7層有10個葉子結(jié)點的完全二叉
4、樹不可能有（B ）個結(jié)點。
A.73 B.234 C.235 D.236
8.分別用以下序列構(gòu)造二叉排序樹，與用其他三個序列構(gòu)造的結(jié)果不同的是（ B）
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）
9.對一組數(shù)據(jù)（84，47，25，1
5、5，21）排序，數(shù)據(jù)的排列次序在排序過程中變化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84則采用的排序方法是（B ）
A.選擇排序 B.起泡排序 C.快速排序 D.插入排序
10.對線性表進行折半查找時，要求線性表必須（ D）
A.以順序方式存儲 B.以順序方式存儲，且數(shù)據(jù)元素有序
C.以鏈接方式存儲 D.以鏈接方式存儲，且數(shù)據(jù)元素有序
二、填空（每空1分，共15分）
1.數(shù)據(jù)結(jié)構(gòu)中評價算
6、法的兩個重要指標是 時間復雜度 、空間復雜度。
2.在單鏈表中，指針P所指結(jié)點有后繼的條件是 p->next.data!=null 。（結(jié)點構(gòu)成：data和next）
3.棧的特點是 先進后出 。
4.判斷循環(huán)隊列是否隊滿的條件表達式是 。
5.完全二叉樹中的結(jié)點個數(shù)為n，則編號最大的分支結(jié)點的編號為 2^n-1 。
6.如果A有7個兄弟，而B是A的雙親，則B的度是 2 。
7.如果二叉樹中有20個葉子節(jié)點，30個度為1的結(jié)點，則該二叉樹的總結(jié)點數(shù)為 。
8
7、.設(shè)二叉樹中每個結(jié)點均用一個字母表示，若一個結(jié)點的左子樹或者右子樹為空，用.表示?，F(xiàn)前序遍歷二叉樹的結(jié)點序列為ABD.G…CE.H..F..，則中序遍歷二叉樹的結(jié)點序列為 。
9.若用n表示圖中的頂點數(shù)目，則有 條邊的無向圖被稱為完全圖。
10.如果具有n個頂點的圖是一個環(huán)，則它有 棵生成樹。
11.克魯斯卡爾算法的時間復雜度是 ，它適合求 圖的最小生成樹。
12.順序查找n個元素的線性表，若查找成功時的平均查找長度為 。
13.高度為5的完全二叉樹，其結(jié)點最少有
8、 個。
14.直接插入排序中使用的監(jiān)視哨的作用是 。
三、判斷題（每題1分，共10分）
1.算法獨立于具體的程序設(shè)計語言，與具體的計算機無關(guān)。（ ）
2.線性表采用鏈式存儲時，結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。（ ）
3.棧和隊列的存儲方式，既可以是順序方式，又可以是鏈式方式。（ ）
4.哈夫曼樹的結(jié)點總個數(shù)一定是偶數(shù)。（ ）
5.已知二叉樹的先序遍歷序列和中序遍歷序列，可以畫出這棵二叉樹（ ）。
6.有e條邊的無向圖，在其對應(yīng)的鄰接表中有e個結(jié)點。（ ）
7.連通分量指的是無向圖的極大連通子圖。（ ）
8.在哈希表的查找過程中的“比較”
9、操作是無法避免的。（ ）
9.完全二叉樹肯定是平衡二叉樹。（ ）
10.堆排序是穩(wěn)定的排序算法。（ ）
四、簡答題（共30分）
1.線性結(jié)構(gòu)的特點是？（4分）
2.已知圖的鄰接矩陣存儲如下所示，請根據(jù)該鄰接矩陣畫出對應(yīng)的圖，并給出從A出發(fā)的廣度優(yōu)先搜索序列，以及相應(yīng)的廣度優(yōu)先生成樹。（6分）
A B C D E F
0
1
0
0
1
0
1
0
0
0
1
1
0
0
0
1
0
1
0
0
1
0
0
1
1
1
0
0
0
0
0
1
1
1
0
0
10、A
B
C
D
E
F
3.已知一棵二叉樹的后序遍歷序列為EICBGAHDF，中序遍歷序列為CEIFGBADH，請畫出這棵二叉樹，并把這棵二叉樹轉(zhuǎn)換成相應(yīng)的樹（或森林）。（6分）
4.已知電文內(nèi)容為：ACACBACDAACDBAACADAA，字符集為A，B，C，D，設(shè)計一套二進制編碼，使得上述電文的編碼最短。（6分）
5.已知有序序列{3，7，11，20，45，77，90}，請分別寫出折半查找10和查找99的過程，并求出ASL（4分）
6.已知序列{34，17，6，29，33，11，80，37}
11、請用快速排序的方法進行排序，并給出詳細過程。（4分）
五、算法填空（每空5分，共20分）
（1）按先序次序輸入二叉樹中的結(jié)點值(字符)構(gòu)造二叉樹
Status CreateBiTree(BiTree &T)
{
char ch;
read(ch);
if( ch== )
T = NULL;
else {
T = (BiTree)malloc(sizeof(BiTNode));
(1) ;
CreateBiTree(T->lch
12、ild);
(2) ;
}
return OK;
}
（2）在順序表L的第 i 個元素之前插入新的元素e
Status ListInsert(SqList &L, int i, ElemType e)
{
if (i < 1 || i > L.length+1) return ERROR; // 插入位置不合法
for ( j= L.length ; j>i ; j - - )
(3) ;
L.elem[i-1] = e ; // 插入
13、e
(4) ;
return OK;
} // ListInsert_Sq
六、寫算法（共15分）
1.請寫出鏈式存儲的線性表中，刪除第i個位置數(shù)據(jù)元素的實現(xiàn)算法。（給出相應(yīng)的結(jié)構(gòu)體定義，關(guān)鍵部分給出注釋。）
2011－2012學年第一學期期末考查
《數(shù)據(jù)結(jié)構(gòu)》標準答案
一、 選擇（每題1分，共10分）
1-5 DBBBB 6-10 ACCDB
二、填空（每空1分，共15分）
1.時間復雜度，空間復雜度
2.FIFO，LIFO
c
d
f
e
b
14、
a
3.Q.rear==Q.front
4.7
5.8
6.O(n2) ，稠密圖
7.極大連通子圖
8.n(n-1)
9.n-1
10.集合結(jié)構(gòu)，樹形結(jié)構(gòu)，圖狀結(jié)構(gòu)
三、判斷題（每題1分，共10分）
1. 2. √ 3. √ 4. 5. √ 6. 7. 8. 9. 10.
四、簡答題（共30分）
1.
(1)在二叉樹的第 i 層上至多有2i-1 個結(jié)點； (i≥1)
(2)深度為 k 的二叉樹上至多含 2k-1 個結(jié)點（k≥1）；
(3)對任何一棵二叉樹，若它含有n0 個葉子結(jié)點、n2 個度為 2 的
15、結(jié)點，則必存在關(guān)系式：n0 = n2+1；
(4)具有 n 個結(jié)點的完全二叉樹的深度為 log2n +1 。
(5)若對含 n 個結(jié)點的完全二叉樹從上到下且從左至右進行 1 至 n 的編號，則對完全二叉樹中任意一個編號為 i 的結(jié)點： 若 i=1，則該結(jié)點是二叉樹的根，無雙親，否則，編號為 i/2 的結(jié)點為其雙親結(jié)點；若 2i>n，則該結(jié)點無左孩子，否則，編號為 2i 的結(jié)點為其左孩子結(jié)點；若 2i+1>n，則該結(jié)點無右孩子結(jié)點，否則，編號為2i+1 的結(jié)點為其右孩子結(jié)點。
評分標準：答對5條中的4條得4分。
2.
深度優(yōu)先遍歷序列：abefdc
深度優(yōu)先生成樹：a-.>b
16、->c->e->f->d->c
評分標準：深度優(yōu)先遍歷序列3分，深度優(yōu)先生成樹3分。
3.(1)T->next->next=P->next;
(2)Q=T;
While(Q->!=P)
{Q=Q->next;}
Q->next=P->next;A
B
C
D
E
F
free(P);
評分標準：回答（1）或者（2）都正確。4.5.{11，3，7，77，20，45，90}
查找過程：11，3，7，77或者90，45，20，77
6.{34，17，6，29，33，11，80，37}
d=5 11，17，6，29，33，34，80，37
d=3
17、 11，17，6，29，33，34，80，37
d=1 6，11，17，29，33，34，37，80
五、算法填空（每空5分，共20分）
1. (1)visit(T->data); 或者printf(T->data);
(2)PreOrderTraverse(T->rchild);
2.(1)return mid;
(2)high=mid-1;
六、寫算法（共15分）
//刪除表L中第i個元素，結(jié)果用e返回，操作成功返回OK，失敗時返回ERROR
Status ListDelete(SqList &L, int i, ElemType &e)
{
if(i<1||i>L.length)return ERROR;
e=L.elem[i-1];
for(int j=i+1;j<=L.length;j++)
L.elem[j-2]=L.elem[j-1];
L.length--;
return OK;
}
《數(shù)據(jù)結(jié)構(gòu)》期末考試題及答案6頁
