計(jì)算機(jī)專業(yè)(基礎(chǔ)綜合)模擬試卷259

一、單選題(本題共40題，每題1.0分，共40分。)

I、根據(jù)使用頻率為5個(gè)字符設(shè)計(jì)的赫夫曼編碼不可能是()。

A、000,001,010,Oil,1

B、0000,0001,001,01,I

C、000,001,01,10,II

D、00,100,101,110,111

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：赫夫曼樹(shù)中只有度為0或2的結(jié)點(diǎn)，由D選項(xiàng)可以畫出對(duì)應(yīng)的二叉

樹(shù)，如圖1-8所示。圖"D選項(xiàng)對(duì)應(yīng)的二叉樹(shù)由赫夫曼樹(shù)的性質(zhì)可知，樹(shù)

中不應(yīng)該含度為1的結(jié)點(diǎn)，因此D選項(xiàng)不可能。

2、簡(jiǎn)單無(wú)向圖的鄰接矩陣是對(duì)稱的，可以對(duì)其進(jìn)行壓縮存儲(chǔ)。若無(wú)向圖G有n個(gè)

結(jié)點(diǎn)，其鄰接矩陣為A[l..n,1.?n],且壓縮存儲(chǔ)在B[l..k1,貝k的值至

少為()。

A、n(n+1)/2

B、n2/2

C、(n-l)(n+l)/2

D、n(n-l)/2

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：簡(jiǎn)單無(wú)向圖的鄰接矩陣是對(duì)稱的，且對(duì)角線元素均是0,故壓縮存儲(chǔ)

只需存儲(chǔ)下三角或是上三角(均不包括對(duì)角線)即可。故有(上三角形式)：k=(n—1)

+(n-2)+…+1+0=?！?1+2+…+n)—n(n-1)/2。

3、下列關(guān)于二叉樹(shù)的敘述中正確的是()。I.對(duì)于任何一棵二叉樹(shù)，葉子結(jié)點(diǎn)數(shù)

都是度為2的結(jié)點(diǎn)數(shù)加In.二叉樹(shù)的左右子樹(shù)不可以任意地交換in.二叉樹(shù)只

適合使用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)，不可能用順序結(jié)構(gòu)存儲(chǔ)iv.結(jié)點(diǎn)按層序編號(hào)的二叉樹(shù)，

第i個(gè)結(jié)點(diǎn)的左孩子(假設(shè)存在)的編號(hào)為2i

A僅

、

n

僅i、

B、

僅n

c、

v

僅n、i

D、

口、m

案：B

標(biāo)準(zhǔn)答

種

做這

生在

以考

，所

才成立

情況下

叉樹(shù)的

非空二

只有在

的描述

I:I

解析：

知識(shí)點(diǎn)

樹(shù)

右子

的左

叉樹(shù)

n：二

誤。

以I錯(cuò)

況，所

特殊情

到這種

要先想

候一定

目的時(shí)

概念題

結(jié)

順序

使用

不能

確實(shí)

叉樹(shù)

的二

一般

。皿

口正確

，所以

意交換

不能隨

序的，

是有順

。

錯(cuò)誤

以in

儲(chǔ)，所

結(jié)構(gòu)存

用順序

般都使

叉樹(shù)一

和滿二

二叉網(wǎng)

是完全

儲(chǔ)，但

構(gòu)存

正確。

只有口

述，

綜上所

誤。

w錯(cuò)

，所以

才成立

二叉樹(shù)

對(duì)完全

結(jié)論只

iv：該

現(xiàn)過(guò)

的實(shí)

訪問(wèn)

互斥

資源，

個(gè)臨界

問(wèn)同一

都要訪

和P2

程P］

個(gè)進(jìn)

中，兩

標(biāo)志法

4、單

：

程如下

進(jìn)程P?

P,

進(jìn)程

---⑤

-----

-----

-----

-----

-----

-----

;---

=2)

rn!

e(tu

whil

①

----

-----

-----

-----

-----

-----

-----

);-

=1

m!

e(lu

whil

--⑥

-----