數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案

1、試卷一參考答案一、單項(xiàng)選擇題1. 【答案】C【解析】數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可以分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)以及圖狀結(jié)構(gòu)，集合不在課程討論范圍之內(nèi)，樹形結(jié)構(gòu)與圖狀結(jié)構(gòu)可統(tǒng)稱為非線性結(jié)構(gòu)，因此答案選C。2【答案】B【解析】P指向x結(jié)點(diǎn)，p->next指向x結(jié)點(diǎn)的后繼結(jié)點(diǎn)，p->next->next指向x后繼結(jié)點(diǎn)的后繼結(jié)點(diǎn)，因此在刪除x的后繼結(jié)點(diǎn)時(shí),即修改p->next的指向，答案選B。3. 【答案】C【解析】根據(jù)二叉樹的性質(zhì)4，具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為。而完全二叉樹是n個(gè)結(jié)點(diǎn)所組成的二叉樹中具有最小深度的樹的形態(tài),所以,答案選C。4【答案】C【解析】棧的基本性質(zhì)是后進(jìn)先

2、出，入棧順序是1，2，3，4，則出棧順序已定不可能存在答案C的順序，因?yàn)?作為第一個(gè)出棧的元素，則1，2，3均已經(jīng)入棧，因此，出棧順序只能為4，3，2，1。5. 【答案】B【解析】本題考查循環(huán)隊(duì)列隊(duì)滿的條件，注意該循環(huán)隊(duì)列的數(shù)組中MAXSIZE=m，因此，答案選B而不能選擇D。6【答案】B【解析】對(duì)稱矩陣的壓縮存儲(chǔ)的特點(diǎn)就是存儲(chǔ)對(duì)角線及其以下的所有元素，a11為第一個(gè)元素,且存儲(chǔ)地址為1,所以,只要確定a85在所有存儲(chǔ)元素中的名次就可以確定其地址。(1+7)*7/2+5=33，因此答案選B7. 【答案】D【解析】根據(jù)后序遍歷的特點(diǎn)即最后一個(gè)元素為根結(jié)點(diǎn)，中序遍歷的特點(diǎn)即以根為分界點(diǎn)，左邊的元素

3、都屬于左子樹中，右邊的所有元素屬于右子樹中元素，其中，左右子樹又滿足以上特點(diǎn)，可以構(gòu)造出二叉樹，先序遍歷序列為D。8【答案】B【解析】本題考查頂點(diǎn)的度的概念，頂點(diǎn)的度即與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，或者選項(xiàng)B，在此，答案A，C，D都是錯(cuò)誤的。9. 【答案】B【解析】根據(jù)二叉排序樹的定義，本題答案選B，這也是二叉排序樹的特征。10【答案】A【解析】快速排序的基本思想是通過一趟快速排序，確定出樞軸元素的確定位置，且使得左右兩邊元素相對(duì)均勻，然后可以在兩邊同時(shí)實(shí)施快速排序，此時(shí)效率最高，當(dāng)元素基本有序時(shí)，大多數(shù)元素集中在樞軸元素的一邊，反而使得快速排序逐步蛻化為冒泡排序，性能降低。二、填空題1. 【答案

4、】n/2【解析】線性表采用順序存儲(chǔ)，插入位置一共n+1個(gè)位置,且等概率,則在最后一個(gè)位置插入元素,不需要移動(dòng)元素,在第n個(gè)元素前面插入元素需要移動(dòng)1個(gè)元素,依此類推，在第1個(gè)元素前面插入元素，需要移動(dòng)n個(gè)元素，因此，平均一定次數(shù)為（0+1+2+n）/( n+1 )=n/2。2【答案】33【解析】根據(jù)二叉樹的性質(zhì)3，n0=n2+1，本題中只有度為2的結(jié)點(diǎn)和度為0的結(jié)點(diǎn)，因此n0=34,n2=33。3. 【答案】n-1【解析】根據(jù)圖的生成樹的定義，包括全部n個(gè)頂點(diǎn)，只包含足以連通n個(gè)頂點(diǎn)的n-1條邊。4【答案】隊(duì)尾、隊(duì)頭【解析】本題考查隊(duì)列的基本定義。5. 【答案】4【解析】本題考查樹中結(jié)點(diǎn)的度、

5、兄弟的定義。6【答案】前驅(qū)、后繼【解析】線索二叉樹的特點(diǎn)就是根據(jù)某種遍歷順序，確定出每個(gè)結(jié)點(diǎn)的前驅(qū)與后繼，將結(jié)點(diǎn)中空的左孩子指針指向結(jié)點(diǎn)的前驅(qū)，空的右孩子指針指向結(jié)點(diǎn)的后繼。該過程也稱為線索化。7. 【答案】關(guān)鍵路徑【解析】AOE網(wǎng)絡(luò)可以表示工程完成進(jìn)度圖，本題考查關(guān)鍵路徑的定義。8【答案】邊稠密、邊稀疏【解析】根據(jù)普里姆算法和克魯斯卡爾算法的算法思想，Prim算法適合于求邊稠密的網(wǎng)的最小生成樹，Kruskal算法適于求邊稀疏的網(wǎng)的最小生成樹9. 【答案】4【解析】根據(jù)折半查找的算法思想，可以形成具有11個(gè)結(jié)點(diǎn)的判定樹如下，本題查找元素20，需要與第4及第5個(gè)元素比較之后才能確定該元素不存在，

6、因此需要比較4次。10【答案】比較、移動(dòng)【解析】通過元素之間的比較確定出待排元素的位置，通過元素的移動(dòng)后，將待排元素插入到恰當(dāng)?shù)奈恢?。三、綜合應(yīng)用題1答：首先畫出哈夫曼樹如下圖，注意要求樹中左孩子結(jié)點(diǎn)的權(quán)值小于右孩子結(jié)點(diǎn)的權(quán)值?？梢詫⑺械淖蠓种гO(shè)為0，右分支設(shè)為1，則從樹根到每個(gè)葉子結(jié)點(diǎn)可以形成相應(yīng)字符的哈夫曼編碼a:11;b:1010;c:100;d:01;e:1011;f:002答：V0到其他各頂點(diǎn)的最短路徑V1100（v0，v1）25（v0，v1）-V220（v0，v2）-V360（v0，v2，v3）60（v0，v2，v3）55（v0，v4，v3）-V430（v0，v4）30（v0，v4）30（v0，v4）-V580（v0，v5）80（v0，v5）80（v0，v5）80（v0，v5）70（v0，v4，v3，v5）添加頂點(diǎn)V2V1V4V33答：根據(jù)關(guān)鍵字序列及處理沖突的方法構(gòu)造表長為11的哈希表如下：等概率情況下，該哈希表的平均查找長度:(1*3+2*2+3*1+5*1)/7=15/7。四、算法設(shè)計(jì)題void insert_L(Linklist &L,int n) p=L;while(p->next->data!=x&&p) p=p->next;for(i=