數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)期末考試試卷

試卷（A卷）

《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)》試卷

開課單位：計(jì)算機(jī)學(xué)院，考試形式：閉卷，允許帶入場(chǎng)

身題序一二三四五六七八總分

眇

送

得分

世

評(píng)卷人

I.基本概念部分（第9小題10分,其余每小題6分，共70分）

1在右邊空白處畫出下面的BST中刪除值為22的結(jié)點(diǎn)以后的BST的形狀。

奈

般

(郛

.

蹴.

.

和.

.

.

郛.

.

蔚.

.

.

囹.

.

).

.

.

笨.

.

赭

——2請(qǐng)畫出向下面所示的最小堆中插入一個(gè)元素值14以后的堆的形狀。

點(diǎn)

亳

和652632

《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)》試卷第1頁共8頁

3給出下圖所示的樹的前序遍歷序列。

4下面給出了某二叉樹的前序和中序訪問序列，請(qǐng)畫出該二叉樹的形狀。

前序序列：2354568920766790784531

中序序列：5654208976239078674531

《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)》試卷第2頁共8頁

5下圖所示是雙鏈表結(jié)點(diǎn)的刪除過程，在fence結(jié)點(diǎn)后面刪除一個(gè)值為23的結(jié)

點(diǎn)，已知fence->next是指向fence的后繼結(jié)點(diǎn)，fence->prev是指向fence的

前驅(qū)結(jié)點(diǎn)，Itmp是一個(gè)值為NULL的鏈表結(jié)點(diǎn)指針，請(qǐng)把這一刪除過程用代碼表

示出來：

這一過程的代碼:

6給出下圖從結(jié)點(diǎn)C開始的深度優(yōu)先搜索樹，并按搜到的順序標(biāo)上序號(hào)。

姓名:學(xué)號(hào):系另U：年級(jí)專業(yè)：

（密封線內(nèi)不答題）

密封......................線

S

澄

3

同

處

.

0

?

0

7畫出下圖以相鄰矩陣表示法時(shí)的相鄰矩陣。

8畫出下圖的最小支撐樹。

《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)》試卷第4頁共8頁

ABCDEF

A

B

C

D

E

F

9下圖是一個(gè)表示課程之間優(yōu)先關(guān)系的有向圖，根據(jù)你在數(shù)據(jù)結(jié)構(gòu)課程中所學(xué)的

拓?fù)渑判虻挠嘘P(guān)知識(shí)，給出該圖的拓?fù)渑判蛐蛄小?此小題10分)

10設(shè)將整數(shù)1、2、3、4依次進(jìn)棧，但只要出棧時(shí)棧非空，則可將出棧操作按任

何次序夾入其中，請(qǐng)回答下有問題：

(1)若入棧次序?yàn)閜ush(l),pop(),push(2),push(3),pop(),pop(),push(4),

pop(),則出棧的數(shù)字序列是什么？

(2)能否得到出棧序列423和432?并說明為什么不能得到或如何得到。

姓名：—學(xué)號(hào)：系別：年級(jí)專業(yè):

（密封線內(nèi)不答題）

密...................................封.............................線...........................

S

澄

5

同

處

8

疔

11假設(shè)用于通信的電文是由字符集㈤卜勒必^力口力中的字符構(gòu)成，這9

個(gè)字符在電文中出現(xiàn)的概率分別為

{0.26,0.10,0.02,0.06,0.16,0.03,0.12,0.07,0.18}。

請(qǐng)畫出對(duì)應(yīng)的Huffman樹（按左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán)的次

序構(gòu)造）。

《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)》試卷第6頁共8頁

II.綜合應(yīng)用部分（每小題1（）分，共30分）

1設(shè)有一個(gè)鏈表（u“U2,…，u?）,試編寫一個(gè)函數(shù)將這個(gè)鏈表原地逆置，即鏈

表為（u,?...?U2,U.）,并要求算法的空間復(fù)雜度為0（1）。（帶頭結(jié)點(diǎn)的實(shí)現(xiàn)）

2設(shè)指針p指向單鏈表的首結(jié)點(diǎn)，指針x指向單鏈表中的任意一個(gè)結(jié)點(diǎn)，寫出在

x前插入一個(gè)結(jié)點(diǎn)1的算法。（不帶頭結(jié)點(diǎn)的實(shí)現(xiàn)）

《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)》試卷第7頁共8頁

一

黑

版

(邦

.

蹴.

.