長沙理工大學(xué)數(shù)據(jù)結(jié)構(gòu)期末考試試卷

1、 4/4長沙理工大學(xué)數(shù)據(jù)結(jié)構(gòu)期末考試試卷 長沙理工大學(xué)計算機(jī)與通信工程學(xué)院 2013-2014學(xué)年二學(xué)期數(shù)據(jù)結(jié)構(gòu)期末考試試卷(C卷) 班級:_學(xué)號:_姓名:_得分:_ 題目部分，(卷面共有32題,100分,各大題標(biāo)有題量和總分) 一、應(yīng)用題(2小題,共16分) 1分析下列程序段的時間復(fù)雜度： （1）for (i=1; inext=top; D top=top-next; 5若串S=SOFTWARE，其子串的數(shù)目最多是：（）。 A35 B36 C37 D38 6對于完全二叉樹中的任一結(jié)點(diǎn)，若其右分支下的子孫的最大層次為h，則其左分支下的子孫的最大層次為（）。 A h B h+1 C h或h+1

2、D 任意 7下列命題正確的是（）。 A 一個圖的鄰接矩陣表示是唯一的，鄰接表表示也唯一 B 一個圖的鄰接矩陣表示是唯一的，鄰接表表示不唯一 C 一個圖的鄰接矩陣表示不唯一的，鄰接表表示是唯一 D 一個圖的鄰接矩陣表示不唯一的，鄰接表表示也不唯一 8設(shè)某散列表的長度為100，散列函數(shù)H(k)=k % P，則P通常情況下最好選擇（）。 A 99 B 97 C 91 D 93 9堆的形狀是一棵（）。 A二叉排序樹 B滿二叉樹 C完全二叉樹 D 判定樹 10設(shè)一組初始記錄關(guān)鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X)，則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是（）。 A F，H，C，D

3、，P，A，M，Q，R，S，Y，X B P，A，C，S，Q，D，F(xiàn)，X，R，H，M，Y C A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，X D H，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y 四、算法設(shè)計題(4小題,共32分) 1設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計出三個單鏈表的算法，使每個單鏈表只包含同類字符。 2設(shè)有兩個集合A和集合B，要求設(shè)計生成集合C=AB的算法，其中集合A、B和C 用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。 3對給定的帶頭結(jié)點(diǎn)的單鏈表L，編寫一個刪除L中值為X的結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)的算法。4設(shè)計一個在鏈?zhǔn)酱鎯Y(jié)構(gòu)上統(tǒng)計二叉樹中結(jié)點(diǎn)個數(shù)的算

4、法。 五、填空題(11小題,共22分) 1已知順序棧S，在對S進(jìn)行進(jìn)棧操作之前首先要判斷（），在對S進(jìn)行出棧操作之前首先要判斷（）。 2設(shè)循環(huán)隊(duì)列存放在向量sq.data0:M中，若用犧牲一個單元的辦法來區(qū)分隊(duì)滿和隊(duì)空（設(shè)隊(duì)尾指針sq.rear）,則隊(duì)滿的條件為_。 3廣義表(a), (b),c),(d)的表頭是（），表尾是（）。 4在有n個葉子的哈夫曼樹中，葉子結(jié)點(diǎn)總數(shù)為（），分支結(jié)點(diǎn)總數(shù)為（）。 5一棵二叉樹的第i（i1）層最多有（）個結(jié)點(diǎn)；一棵有n（n0）個結(jié)點(diǎn)的滿二叉樹共有（）個葉子結(jié)點(diǎn)和（）個非終端結(jié)點(diǎn)。 6希爾排序法屬于（） 7對n個待排序記錄序列進(jìn)行快速排序，所需要的最好時間復(fù)雜

5、度是（），最壞時間復(fù)雜度是（）。 8假設(shè)線性表的長度為n，則在最壞情況下，冒泡排序需要的比較次數(shù)為（） 9對于鍵值序列（12，13，11，18，60，15，7，18，25，100），用篩選法建堆，必須從鍵值為（）的結(jié)點(diǎn)開始。 10圖形結(jié)構(gòu)的元素之間存在（）的關(guān)系。 11數(shù)據(jù)的存儲結(jié)構(gòu)是指（） 長沙理工大學(xué)計算機(jī)與通信工程學(xué)院 2013-2014學(xué)年二學(xué)期數(shù)據(jù)結(jié)構(gòu)期末考試試卷(C卷)答案部分，(卷面共有32題,100.0分,各大題標(biāo)有題量和總分) 一、應(yīng)用題(2小題,共22分) 1O(log2n) （2）O(n2) 2【解答】構(gòu)造的哈夫曼樹如圖所示。 樹的帶權(quán)路徑長度為： WPL=24+34+5

6、3+73+83+92+112 =120 二、判斷正誤(5小題,共22分) 1錯 2對 3錯 4對 5對 三、單項(xiàng)選擇題(10小題,共22分) 1棧 2A 3A 4D 5C 6C 7B 8B 9C 10D 四、算法設(shè)計題(4小題,共22分) 1typedef char datatype; typedef struct node datatype data; struct node *next;lklist; void split(lklist *head,lklist * ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) head=p-next; p-next=0;

7、 if (p-data=A ha=p; else if (p-data=0 hb=p; else p-next=hc; hc=p; 2typedef struct node int data; struct node *next; lklist; void intersection(lklist *ha,lklist *hb,lklist * For(p=ha,hc=0;p!=0;p=p-next) for(q=hb;q!=0;q=q-next) if (q-data=p-data) break; if(q!=0) t=(lklist *)malloc(sizeof(lklist); t-da

8、ta=p-data; t-next=hc; hc=t; 3解： void delete(ListNode *L) ListNode *p=L,*q; if (L-next-data=X) printf (“值為x的結(jié)點(diǎn)是第一個結(jié)點(diǎn)，沒有直接前趨結(jié)點(diǎn)可以刪除”); return; for (;p-next-data!=X; q=p; p=p-next); / 刪除指針p所指向的結(jié)點(diǎn)q-next=p-next; delete p; 4void countnode(bitree *bt,int countnode(bt-lchild,count); countnode(bt-rchild,count); 五、填空題(11小題,共22分) 1棧是否滿棧是否空 2(sq.rear+1