2018春數(shù)據(jù)結(jié)構(gòu)試卷(A)

1、 PAGE PAGE 5 PAGE PAGE 4裝裝訂線華南農(nóng)業(yè)大學(xué)期末考試試卷（A 卷）2017-2018 學(xué)年第 2 學(xué)期考試科目： 數(shù)據(jù)結(jié)構(gòu)考試類型（閉卷）考試考試時(shí)間： 120分學(xué)號(hào)姓名年級(jí)專業(yè)題號(hào)題號(hào)一二三四總分得分評(píng)閱人考生須知：答案必須寫在“答卷”上，寫在試卷上不得分；考試結(jié)束時(shí)，只回收答卷，不回收試卷；必須在答卷上正確填寫班級(jí)、學(xué)號(hào)、姓名等內(nèi)容，否則沒有考試成績。得分得分一、選擇題（本大題共 10 小題，每小題 2 分，共 20 分）1、 算法分析的兩個(gè)主要方面是（。A.時(shí)間復(fù)雜度和空間復(fù)雜度B.正確性和簡明性C.可讀性和正確性D.程序復(fù)雜性和數(shù)據(jù)復(fù)雜性2、下面程序段的時(shí)間復(fù)雜

2、度為（ ）for（i=1，s=0； i=n； i+）t=1；for(j=1；j=i；j+) t=t*j；s=s+t；AO(1)BO(n)CO(nlog2n)3、單鏈表中，增加頭結(jié)點(diǎn)的目的是（ 。A.使得單鏈表至少有一個(gè)節(jié)點(diǎn)B. 標(biāo)示表中首節(jié)點(diǎn)的位置C.方便運(yùn)算D. 說明這是線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)4、一個(gè)棧的入棧次序是1,2,3,30，出棧次序是P1，P2，.，P30，若P1=30，則P10等于（）A.10B.21C. 11D.205、語言中用數(shù)DM作為循環(huán)隊(duì)Q的存儲(chǔ)空間為隊(duì)頭指針為隊(duì)尾指針則執(zhí)行出隊(duì)操作的語句為（。A. front = front +1B. front = （front+1）%M

3、C. rear = （rear+1）%MD. front = （front+1）%（M+1）6、二維數(shù)組A的行下標(biāo)從0到8，其列下標(biāo)從0到91479637、。A按行優(yōu)先存儲(chǔ)，則元A74與下列哪一個(gè)按列優(yōu)先存儲(chǔ)的元素地址相同A.A28B.A74C.A39D. A477、若森林F10F（ 。A 4B 5C 6D 無法確定8、某二叉樹先序遍歷序列為 abdgcefh，中序遍歷序列為 dgbaechf，則其后續(xù)遍歷序列為（。A.bdgcefhaB.gdbecfhaC.bdgechfaD.gdbehfca9、有向圖G（，頂點(diǎn)集合V=VVVV3，邊集合E=,從頂點(diǎn)V0 開始深度遍歷則可能得到多少種不同的遍

4、歷序（。A 2B 3C 4D 510(60，80，55，40，42，85)60 準(zhǔn)而得到的一趟快速排序結(jié)果是（ 。A40，42，60，55，80，85C42，40，55，60，80，85得分得分二、應(yīng)用題（本大題共 6 小題，每小題5分，共30分，要求寫出解題過程）1、字母 的權(quán)值分別為 7,18,3,32,5,26,12,8，構(gòu)造對(duì)應(yīng)的哈夫曼樹（子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán)，并給出哈夫曼編碼。2、已知有 5 個(gè)頂點(diǎn)的圖G 如下圖所示。請(qǐng)寫出圖G 的鄰接矩陣（行列下標(biāo)從0 開始，并給出圖G 在鄰接矩陣A 度遍歷算法和廣度遍歷算法得到的深度遍歷序列和廣度遍歷序列。3、下圖為帶權(quán)無向圖，

5、使用普里姆（Prim）算法從頂點(diǎn)1 開始構(gòu)造最小生成樹，按步驟寫出構(gòu)造過程。4H(Key) = 3*Key % 32,13,49,24,38,21,4,15序樹，按步驟畫出插入與調(diào)整的過程，并求出等概率情況下查找成功的平均查找長度。6AOE 并給出關(guān)鍵路徑。裝訂得分三、程序填空題三、程序填空題本大題共 5 15 2 30 注意：每空只填一個(gè)語句）1、以遞歸的方法先序創(chuàng)建二叉樹，結(jié)點(diǎn)的值為字符型字符表示空線Status CreateBiTree(BiTree &T) char ch; scanf(%c,&ch);if (ch=#) T = NULL;else if (!(T = (BiTNode

6、 *)malloc(sizeof(BiTNode) return ERROR;（1）（2）（3）return OK; 2typedef structElemType *elem; int length;SSTable;int Search_Bin(SSTable ST,KeyType key)int low,high,mid; low=1; high=ST.length; while(low=high)（4）if EQ(key,ST.elemmid.key)return mid;else if LT(key,ST.elemmid.key) /* key值小于中點(diǎn) */（5）else（6）ret

7、urn 0;3、使用棧結(jié)構(gòu)實(shí)現(xiàn)整數(shù)十進(jìn)制至二進(jìn)制的轉(zhuǎn)換，入棧函數(shù)為Push，出棧函數(shù)為Pop void conversion() /* 對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的二進(jìn)制數(shù) */ SqStack s;intn，e; InitStack(s); scanf(%d,&n); while(n)（7）（8）while(!StackEmpty(s)（9）printf(%d,e);printf(n);4、在帶頭結(jié)點(diǎn)的單鏈線性表L i 個(gè)位置之前插入元素e單鏈表定義如下：typedef struct LNode ElemType data;struct LNode *next;LNo

8、de, *LinkList;Status ListInsert_L(LinkList &L, int i, ElemType e) LinkList p;p = L; j = 0;while(p & ji-1) return ERROR;/i 值不合法s = (LinkList) malloc (sizeof(LNode);/生成新結(jié)s-data = e;/插入L中（12）裝裝訂線return OK;/LinkInsert_L5、以下算法為鏈?zhǔn)骄€性表逆置算法，線性表仍占用原線性表的空間。int Reverse(LinkList &L) /將鏈表逆置LinkList p, 借用指針q 作為頭指針

9、，將原表中結(jié)點(diǎn)逐一插入表while(（13）) /原表中有未處理的結(jié)點(diǎn)p=L-next;/p 指向原表中頭結(jié)點(diǎn)后的結(jié)點(diǎn)L-next=p-next;p-next=q;/p 所指向結(jié)點(diǎn)插入到q 所指向鏈表頭部（14）（15）return OK;得分得分四、算法設(shè)計(jì)題本大題共 2 10 20 C 語言源代碼實(shí)現(xiàn)）1使得線性表前半部分均為負(fù)整數(shù)，后半部分均為正整數(shù)。不要求對(duì)這些元素排序，但 要求盡量減少元素交換次數(shù)。線性表使用順序存儲(chǔ)結(jié)構(gòu)，其定義如下：typedef struct int *elem； int int length；SqList統(tǒng)一使用函數(shù)名：void exchange(SqList L)2、以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，編寫求二叉