廈門理工學院12級數(shù)據(jù)結(jié)構(gòu)期末試卷與答案(共15頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上考 生 信 息 欄 系 專業(yè) 級 班級 姓名 學號 裝 訂 線廈門理工學院試卷20122013學年 第 一 學期課程名稱數(shù)據(jù)結(jié)構(gòu)與算法試卷卷別 A B 專業(yè) 2011 級 班級 考試方式閉卷 開卷 本試卷共 四 大題(4頁)，滿分100分，考試時間120分鐘。請在答題紙上作答，在試卷上作答無效。 一、選擇題：（本題共20小題，每題2分，共40分）1、鏈式存儲的存儲結(jié)構(gòu)所占存儲空間（ ）。 A 分兩部分，一部分存放結(jié)點的值，另一部分存放表示結(jié)點間關(guān)系的指針 B 只有一部分，存放結(jié)點的值 C 只有一部分，存儲表示結(jié)點間關(guān)系的指針 D 分兩部分，一部分存放結(jié)點的值，另一部分

2、存放結(jié)點所占單元素2、已知一個順序存儲的線性表，設(shè)每個結(jié)點占m個存儲單元，若第一個結(jié)點的地址為B，則第i個結(jié)點的地址為（ ）。A B+(i-1)*m BB+i*m C B-i*m D B+(i+1)*m3、兩個指針P和Q，分別指向單鏈表的兩個元素，P所指元素是Q所指元素前驅(qū)的條件是（ ）。AP->next=Q->next BP->next= Q CQ->next= P DP=Q4、下面關(guān)于線性表的敘述中，錯誤的是（ ）關(guān)系。A順序表必須占一片地址連續(xù)的存儲單元 B順序表可以隨機存取任一元素C鏈表不必占用一片地址連續(xù)的存儲單元 D鏈表可以隨機存取任一元素5、等概率情況下，

3、在有n個結(jié)點的順序表上做插入結(jié)點運算，需平均移動結(jié)點的數(shù)目為（ ）。AnB(n-1)/2 C n/2 D(n+1)/26、設(shè)數(shù)組datam作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針front值為（ ）。 Afront=front+1 Bfront=(front+1)%(m-1) Cfront=(front-1)%m Dfront=(front+1)%m7、下列算法的時間復雜度是（ ）。 for (i=0;i<n;i+) for (j=0;j<n;j+) cij=i+j; A. O（1） B. O（ n） C. O（log2n） D

4、. O（n2）8、從一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用x保存被刪除的結(jié)點的值，應執(zhí)行下列 ( )命令。 Ax=top; top=top->next; Btop=top->next; x=top->data; Cx=top->data; Dx=top->data; top=top->next;9、經(jīng)過下列棧的運算后，x的值是（ ）。 InitStack(s) （初始化棧）;Push(s, a);Push(s, b);ReadTop(s);Pop(s, x);Aa Bb C1 D010、一個棧的入棧次序ABCDE，則棧的不可能的輸出序列是 ( )。

5、AEDCBA BDECBA CDCEAB DABCDE11、設(shè)某棵二叉樹中有2000個站點，則該二叉樹的最小高度為（ ）。 A、9 B、10 C、11 D、1212、若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前front和rear的值分別為3和0，當從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別為( )。 A5和1 B4和2 C2和4 D1和513、根據(jù)二叉樹的定義，具有3個結(jié)點的二叉樹有（ ）種樹型。 A3 B4 C5 D614、如右圖所示的二叉樹，后序遍歷的序列是（ ）ABADECFGHI A A、B、C、D、E、F、G 、H、I B A、B、D、H、I、E、C、F、

6、G C H、D、I、B、E、A、F、C、G D H、I、D、E、B、F、G、C、A15、下列陳述正確的是（ ）。A二叉樹是度為2的有序樹B二叉樹中結(jié)點只有一個孩子時無左右之分C二叉樹中必有度為2的結(jié)點 D二叉樹中最多只有兩棵子樹，且有左右子樹之分16、在有n個葉子結(jié)點的哈夫曼樹中，非葉子結(jié)點的總數(shù)是（ ）。n-1 n 2n-1 2n17、對于一個具有n個頂點的有向圖的邊數(shù)最多有（ ）。 An Bn(n-1) Cn(n-1)/2 D2n18、對于一個具有n個頂點和e條邊的無向圖，采用鄰接表表示，則表頭向量大小為（ ）。 An-1Bn+1 Cn Dn+e19、下面關(guān)于圖的存儲結(jié)構(gòu)的敘述中正確的是（

7、 ）。A 用鄰接矩陣存儲圖，占用空間大小只與圖中頂點數(shù)有關(guān)，而與邊數(shù)無關(guān)B 用鄰接矩陣存儲圖，占用空間大小只與圖中邊數(shù)有關(guān)，而與頂點數(shù)無關(guān) C 用鄰接表存儲圖，占用空間大小只與圖中頂點數(shù)有關(guān)，而與邊數(shù)無關(guān) D 用鄰接表存儲圖，占用空間大小只與圖中邊數(shù)有關(guān)，而與頂點數(shù)無關(guān)20、二叉樹為二叉排序樹的（ ）條件是其任一結(jié)點的值均大于其左孩子的值，小于其右孩子的值。A充分不必要 B必要不充分 C充分必要 D既不充分也不必要二、分析運算題（本題共6小題，每題5分，共30分）1、如果輸入序列為1 2 3,先進入棧結(jié)構(gòu)后進入隊列結(jié)構(gòu)，試寫出所有的出隊列序列。2、 假設(shè)一棵二叉樹的前序(先序)遍歷序列為ABD

8、ECF和中序序列為DBEAFC，畫出二叉樹并寫出后序遍歷序列。 圖 1 圖 2 圖33、用二叉樹表示算術(shù)表達式如圖1所示。 按圖畫出對應的算術(shù)表達式 寫出后序（后綴）表達式4、請寫出有向圖2中頂點1-6的入度和出度。5、給定一組項及其權(quán)值，假定項都存放于二叉樹的樹葉結(jié)點，則具有最小帶權(quán)外部路徑長度的樹稱為huffman(赫夫曼) 樹。給定項及相應的權(quán)如下表：畫出相應的huffman樹。序號 1 2 3 4 5 6 7 8 9項 A B C D E F G H I權(quán)值15 6 71225 4 6 1156、 已經(jīng)鄰接矩陣如圖3所示，判斷該圖是有向圖還是無向圖，用頂點1-6畫出該圖。三、程序填空題

9、（本題共5空，每空2分，共10分）1、下面程序段的功能是在單鏈表中查找元素數(shù)據(jù)x，若找到，返回指向該結(jié)點的指針；否則返回空指針，請在下劃線處填上正確的內(nèi)容。 / 在單鏈表L中查找元素xtypedef struct LNode DataType data; struct LNode *next; LNode, *LinkList;LinkList Find ( LinkList L, DataType x ) p = L->next; / L為帶頭節(jié)點的單鏈表 while ( （1） ) if ( p->data = = x ) return p; / 找到x （2） return

10、NULL; / 未找到2、下面程序段的功能實現(xiàn)刪除隊列中的隊頭數(shù)據(jù)（若隊列不空），并用x返回其值，要求在下劃線處填上正確的語句。typedef struct QNode DataType data; struct QNode *next; QNode, *QueuePtr;typedef struct LQ QueuePtr front; QueuePtr rear;LinkQueue;int DeQueue ( LinkQueue &Q, DataType &x ) if ( （3） ) return ERROR;p= Q.front->next;x=p->dat

11、a; （4） if (Q.rear= =p) （5） free(p); return OK;線 訂 裝考 生 信 息 欄 系 專業(yè) 級 班級 姓名 學號 裝 訂 線四、算法設(shè)計題（本題共2小題，共20分）1、（10分）已知一個順序表，每個元素都是整數(shù)，試設(shè)計用最少時間把所有值為負數(shù)的元素移動到全部正數(shù)值元素前面的算法。typedef struct int *elem; int length ; int listSize; sqlist;2、（10分）以二叉鏈表為存儲結(jié)構(gòu)，編寫計算二叉樹中葉子結(jié)點數(shù)目的遞歸函數(shù)。typedef struct BiTNode int data; struct Bi

12、TNode *lchild, *rchild;BiTNode,*BiTree;數(shù)據(jù)結(jié)構(gòu)與算法A卷答案12-13學年第一學期一、選擇題：（本題共20小題，每題2分，共40分）1-5：AABDC 6-10：DDDBC 11-15：CBCDD 16-20：ABCAB二、分析運算題（本題共6小題，每題5分，共30 分）(1) 如果輸入序列為1 2 3,先進入棧結(jié)構(gòu)后進入隊列結(jié)構(gòu)，試寫出所有的出隊列序列。輸出序列1 2 3（1分）輸出序列1 3 2（1分）輸出序列2 1 3（1分）輸出序列2 3 1（1分）輸出序列3 2 1（1分）輸出序列3 1 2（扣3分）(2) 假設(shè)一棵二叉樹的前序(先序)遍歷序列

13、為ABDECF和中序序列為DBEAFC，畫出二叉樹并寫出后序遍歷序列。 （3分）后序遍歷：DEBFCA （2分）(3) 用二叉樹表示算術(shù)表達式如圖1所示。 按圖畫出對應的算術(shù)表達式 寫出后序（后綴）表達式算術(shù)表達式：(a+b+c*(d+e)+f)*(g+h) （2分）后序表達式：ab+cde+*+f+gh+*（3分）(4) 請寫出有向圖2中頂點1-6的入度和出度1: 入度：3出度：02: 入度：2出度：23: 入度：1出度：24: 入度：1出度：35: 入度：2出度：16: 入度：2出度：3(入度2.5分，出度2.5分)(5) 給定一組項及其權(quán)值，假定項都存放于二叉樹的樹葉結(jié)點，則具有最小帶權(quán)

14、外部路徑長度的樹稱為huffman(赫夫曼) 樹。給定項及相應的權(quán)如下表：畫出相應的huffman樹。(5分)9153382825E15I2315A1312D116G7C6B54F1H(6)已經(jīng)鄰接矩陣如圖3所示，判斷該圖是有向圖還是無向圖，用頂點1-6畫出該圖。有向圖（2分）（3分）三、程序填空題（本題共5空，每空2分，共10分）(1)：p!=NULL(2)：p = p->next;(3): Q.front= =Q.rear(4): Q.front->next=p->next;(5): Q.rear=Qfront;四、算法設(shè)計題（本題共2小題，共20分）1、（10分）算法如下：void move(sqlist L) int i=0,j=L.lenght-1,k; 1分 int temp; while(i<j) 1分 while(L.elemi<=0) i+; 2分while(L.elemj>=0) j-; 2分if(i<j) 1分 temp=L.elemi; L.elemi=L.elemj; L.e