數(shù)據(jù)結(jié)構(gòu)真題及答案

06數(shù)據(jù)構(gòu)造〔50分〕

一、單項(xiàng)選擇題(在每題的四個(gè)備選答案中，選出一個(gè)正確的答案，并將其號(hào)碼

填寫(xiě)在題干后面的括號(hào)內(nèi)。每題1分，共10分)

1.數(shù)據(jù)的根本單位是()

A.數(shù)據(jù)項(xiàng)B.數(shù)據(jù)類型C.數(shù)據(jù)對(duì)象D.數(shù)據(jù)元素

2.假設(shè)頻繁的對(duì)線性表進(jìn)展插入和刪除操作，則該線性表應(yīng)當(dāng)承受存儲(chǔ)構(gòu)造。()

A.挨次B.鏈?zhǔn)紺.散列D.任意

3.假設(shè)進(jìn)棧序列為3,5,7,9,進(jìn)棧過(guò)程中可以出棧，則不行能的出棧次序是()

A.7,5,3,9B.9,7,5,3C.7,5,9,3D.9,5,7,3

4.下面的說(shuō)法中，正確的選項(xiàng)是()

A.字符串的長(zhǎng)度指串中包含的字母的個(gè)數(shù)B.字符串的長(zhǎng)度指串中包含的不同字符的個(gè)數(shù)C.

一個(gè)字符串不能說(shuō)是其自身的一個(gè)子串D.假設(shè)T包含在S中，則T肯定是S的一個(gè)子

串5.廣義表Ka,b),(c,d))的表尾是()

A.dB.c,dC.(c,d)D.(c,d)

6.n個(gè)頂點(diǎn)的連通圖，其生成樹(shù)有條邊。()

A.n-1B.nC.n+1D.不確定

7.假設(shè)一棵二叉樹(shù)有8個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)的葉節(jié)點(diǎn)個(gè)數(shù)為()

A.7B.8C.9D.不確定

&在有n個(gè)節(jié)點(diǎn)的二叉鏈表中有個(gè)空鏈域。()

A.n+1B.nC.n-1D.不確定

9.在等概率的狀況下，承受挨次插查找法查找長(zhǎng)度為n的線性表，平均查找長(zhǎng)度為()

A.nB.n/2C.(n+l)/2D.(n-l)/2

10.以下排序方法中，排序的比較次數(shù)與序列的初始排列狀態(tài)無(wú)關(guān)的是()

A.選擇排序B.插入排序C.冒泡排序D.快速排序

二、填空題(本大題共10小題，每題1分，共10分)

1.假定一個(gè)挨次隊(duì)列的隊(duì)首和隊(duì)尾分別為f和r,則推斷隊(duì)空的條件為。

2.在挨次存儲(chǔ)的線性表中插入或刪除一個(gè)元素平均約移動(dòng)表中的元素。

3.設(shè)有一個(gè)二維數(shù)組A[5|[4|,按行序優(yōu)先存儲(chǔ)，A|O|[O]的存儲(chǔ)地址是10,每個(gè)數(shù)組元素占

2個(gè)字節(jié)，則A⑶⑵的存儲(chǔ)地址是。

4.深度為k的二叉樹(shù)至多有個(gè)結(jié)點(diǎn)。(k》l)

5.在有n個(gè)結(jié)點(diǎn)，e條邊的有向圖的鄰接表中有個(gè)表結(jié)點(diǎn)。

6.對(duì)一棵二叉樹(shù)進(jìn)展遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)關(guān)鍵字的有序序列。

7.在一個(gè)圖中，全部頂點(diǎn)的度數(shù)之和是邊數(shù)的倍。

8.假設(shè)有序表(15,21,33,46,58,80,87)中折半查找元素33時(shí)，與關(guān)鍵字比較

次查找成功。

9.設(shè)哈希表長(zhǎng)m=14,哈希函數(shù)H(key)=keyMOD11。表中已有4個(gè)元素：

012345678910111213

III1Iis1381611841II~~rn~~rn

假設(shè)用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的記錄的存儲(chǔ)位置是

10.具有n個(gè)頂點(diǎn)的無(wú)向完全圖，有條邊。

三、推斷題（本大題共5小題，每題1分，共5分）

1.算法在執(zhí)行時(shí)，對(duì)同樣的輸入可以得到不同的結(jié)果。（）

2.線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造的內(nèi)存單元地址肯定不連續(xù)。（）

3.隊(duì)列允許插入的一段成為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。（）

4.拓?fù)渑判蚴莾?nèi)部排序。（）

5.樹(shù)轉(zhuǎn)換成二叉樹(shù)，其根結(jié)點(diǎn)的右子樹(shù)肯定為空。（）

四、綜合應(yīng)用題（本大題共3小題，每題5分，共15分）

1.畫(huà)出具有三個(gè)結(jié)點(diǎn)的二叉樹(shù)的全部形態(tài)（不考慮數(shù)據(jù)信息的組合狀況）。（5分）

2.寫(xiě)出以下圖的鄰接矩陣，并寫(xiě)出其從VI動(dòng)身的深度優(yōu)先搜尋遍歷序列（5分）

3.將以下圖所示的樹(shù)轉(zhuǎn)換成二叉樹(shù)，并寫(xiě)出該二叉樹(shù)的先序遍歷序列。（5分）

五、算法設(shè)計(jì)（本大題共1小題，共10分）

1.線性表承受鏈?zhǔn)酱鎯?chǔ)構(gòu)造，結(jié)點(diǎn)類型定義如下，試編寫(xiě)一個(gè)算法，在帶頭結(jié)點(diǎn)的單鏈表L

中，刪除全部值為x的結(jié)點(diǎn)。

typedefstructLNode

{ElemTypedata;

structLNode"next;

}LNode,*Linklist;

07數(shù)據(jù)構(gòu)造〔50分〕

一、單項(xiàng)選擇題（10分，每題1分）

1.按二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有種。（）

A.3B.4C.5D.6

2.假設(shè)一個(gè)棧的入棧序列是1,2,3,…，n,其輸出序列為pl,p2,p3.....pn,假設(shè)

pl=n,則pi為（）

A.iB.n=iC.n-i+qD.不確定

3.下面結(jié)論是正切的。（）

A.樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的先序遍歷序列一樣

B.樹(shù)的后根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的先序遍歷序列一樣

C.樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的中序遍歷序列一樣

D.以上都不對(duì)

4.評(píng)價(jià)一個(gè)算法時(shí)間性能的主要標(biāo)準(zhǔn)是（）

A.算法易于調(diào)試B.算法易于理解

C.算法的穩(wěn)定性和正確性D.算法的時(shí)間簡(jiǎn)單度

5.線性表的挨次存儲(chǔ)構(gòu)造是一種的存儲(chǔ)構(gòu)造。（）

A.隨機(jī)存取B.挨次存取C.索引存取D.散列存取

6.在挨次表中，只要知道,就可在一樣時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址。（）

A.基地址B.結(jié)點(diǎn)大小C.向量大小D.基地址和結(jié)點(diǎn)大小

7.在中序線索二叉樹(shù)中，假設(shè)某結(jié)點(diǎn)有右孩子，則該結(jié)點(diǎn)的直接后繼是（）

A.左子樹(shù)的最右下結(jié)點(diǎn)B.右子樹(shù)的最右下結(jié)點(diǎn)C.

左子樹(shù)的最左下結(jié)點(diǎn)D.右子樹(shù)耳朵最左下結(jié)點(diǎn)

&一個(gè)棧的入棧序列是abcde,則棧的不行能輸出序列是（）

A.edcbaB.decbaC.dceabD.abcde

9.廣義表是線性表的推廣，它們之間的區(qū)分在于（）

A.能否使用子表B.能否使用原子項(xiàng)C.表的長(zhǎng)度D.是否能為空

10.假設(shè)一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)的度為0的結(jié)點(diǎn)的個(gè)數(shù)是（）

A.9B.llC.12D.不確定

二、填空題（每空1分，共10分）

1.挨次表中規(guī)律上相鄰的元素的物理位置____________________。

2.在分塊查找方法中，首先查找索引表，然后再用挨次查找方法查找相應(yīng)的

3.安排排序的兩個(gè)根本過(guò)程是

4.在拓?fù)渑判蛑?，拓?fù)湫蛄械牡谝粋€(gè)頂點(diǎn)必定是為0的頂點(diǎn)。

5.有n個(gè)結(jié)點(diǎn)的二叉鏈表中。其中空的指針域?yàn)?

6.有向圖的鄰接表表示適于求頂點(diǎn)的。

7.有向圖的鄰接矩陣表示中，第i____________________上非零元素的個(gè)數(shù)為頂點(diǎn)vi的入度。

8.在樹(shù)的表示法中，求指定結(jié)點(diǎn)的雙親或祖先格外便利，但是求指定結(jié)

點(diǎn)的孩子或其他后代可能要遍歷整個(gè)數(shù)組。

9.由五個(gè)分別帶權(quán)值為9,2,3,5,14的葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹(shù)，該樹(shù)的帶權(quán)路徑長(zhǎng)度為

10.具有n個(gè)頂點(diǎn)的有向圖最多有條邊。

三、填空題（30分）

1.寫(xiě)出頭插法建立單鏈表的算法（5分）

2.求單源最短路徑（從源點(diǎn)0開(kāi)頭），要求寫(xiě)出過(guò)程。（5分）

3.某二叉樹(shù)的中序遍歷序列：dfaechi

后序遍歷序列：fdbehica

（1）請(qǐng)構(gòu)造出該二叉樹(shù)；（3分）

（2）寫(xiě)出前序遍歷序列；［2分）

4.設(shè)查找的關(guān)鍵字序列｛15,4,30,4111,22,1｝。畫(huà)出對(duì)應(yīng)的二叉排序樹(shù)。（5分）

5.寫(xiě)出圖的廣度優(yōu)先搜尋算法（用鄰接表存儲(chǔ)）（5分）

6.線性表的關(guān)鍵字集合：

｛19,14,23,01,68,20,84,27,55,11,10,79｝散列函數(shù)為：H（k）=k%13,承受拉鏈法處理沖突,

并設(shè)計(jì)出鏈表構(gòu)造。（5分）

08數(shù)據(jù)構(gòu)造〔50分〕

一、單項(xiàng)選擇題（10分，每題1分）

1.假設(shè)一個(gè)棧的輸入序列為1,2,3,…，n,輸出序列的第一個(gè)元素是i,則第i個(gè)輸出元

素是（）

A.i-j-1B.i-jC.j-i+1D.不確定的

2.循環(huán)隊(duì)列存儲(chǔ)在數(shù)組中，則入隊(duì)的操作為（）

A.rear=rear+1B.rear=(rear+1)mod(m-1)

C.rear=(rear+l)modmD.rear=(rear+1)mod(m+1)

3.二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的串，其行下表i=0,1,…，8,列下表

j=l,2........10。假設(shè)A按行序?yàn)橹餍虼鎯?chǔ)，元素A[8][5]的起始地址與當(dāng)A按列序?yàn)橹餍?/p>

存儲(chǔ)時(shí)的元素的起始地址一樣。(設(shè)每個(gè)字符占一個(gè)字節(jié))()

A.A[8][5]B.A[3][10]C.A[5][8]D.A[0][9]

4.下面說(shuō)法不正確的選項(xiàng)是0

A.廣義表的表頭總是一個(gè)廣義表B.廣義表的表尾總是一個(gè)廣義表C.

廣義表難以用挨次存儲(chǔ)構(gòu)造D.廣義表可以是一個(gè)多層次的構(gòu)造

5.算術(shù)表達(dá)式A+B*C-D/E轉(zhuǎn)為前綴表達(dá)式后為0

A.-A*C/DEB.-A+B*CD/EC.-+ABC/DED.-+A*BC/DE

6.有n個(gè)葉子的哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為0

A.不確定B.2nC.2n+1D.2n-1

7.假設(shè)X是中序線索二叉樹(shù)中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，則X的前驅(qū)為()

A.X的雙親B.X的右子樹(shù)中最左的結(jié)點(diǎn)

C.X的左子樹(shù)中最右結(jié)點(diǎn)D.X的左子樹(shù)中最右葉結(jié)點(diǎn)

8.無(wú)向圖G=(V,E),其中V={a,b,c,d,e,f},E={{a,b),{a,e},{atc}.{b.e},

{c,f},{f,d},{e,d}},對(duì)該圖進(jìn)展廣度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的選項(xiàng)是()

A.a,b,e,c,d,fB.a,c,f,e,b,d

C.a,e,b,c,f,dD.a,e,d,f,c,b

9.假定有k個(gè)關(guān)鍵字互為同義詞，假設(shè)用線性探測(cè)法把這k個(gè)關(guān)鍵字存入散列表中，至少

要進(jìn)展探測(cè)。()

A.k-1次B.k次C.k+1次D.k(k+1)/2次

10.以下排序算法中，在每一趟都能選出一個(gè)元素放到其最終位置上，并且其時(shí)間性能受數(shù)

據(jù)初始特性影響的是()

A.直接插入排序B.快速排序C.直接選擇排序D.堆排序

二、填空題(5分，每題1分)

1.在有序表AI1..12]中，承受折半查找算法查等于A|12|的元素，所比較的元素下標(biāo)依次為

2.求圖的最小生成樹(shù)有兩種算法，算法適合于求稀疏圖的最小生成樹(shù)。

3.一棵左子樹(shù)為空的二叉樹(shù)在先序線索化后，其中的空鏈域的個(gè)數(shù)為。

4.在單鏈表L中，指針p所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是。

5.一個(gè)深度為k,具有最少結(jié)點(diǎn)數(shù)的完全二叉樹(shù)按層次，(同層次從左到右)用自然數(shù)依次

對(duì)結(jié)點(diǎn)編號(hào)，則編號(hào)是i的結(jié)點(diǎn)所在的層次號(hào)是(跟所在的層次

號(hào)規(guī)定為1層)。

三、推斷題(5分，每題1分)

1.鏈表是承受鏈?zhǔn)酱鎯?chǔ)構(gòu)造的線性表，進(jìn)展插入、刪除操作時(shí)，在鏈表中比在挨次存儲(chǔ)構(gòu)

造中效率圖。()

2.對(duì)一棵二叉樹(shù)進(jìn)展層次遍歷時(shí)，應(yīng)借助于一個(gè)棧。（)

3.將一棵樹(shù)轉(zhuǎn)成二叉樹(shù)，跟節(jié)點(diǎn)沒(méi)有左子樹(shù)。（）

4.一個(gè)有向圖的鄰接表和逆鄰接表中結(jié)點(diǎn)的個(gè)數(shù)可能不等。（）

5.在待排序數(shù)據(jù)有序的狀況下，快速排序效果好。（）

四、應(yīng)用題（20分，每題5分）

1.用集合｛46,88,45,39,70,58,101,10,66,34｝建立一棵二叉排序樹(shù)，畫(huà)出該樹(shù)，

并求在等概率狀況下的平均查找長(zhǎng)度。

2.設(shè)一組關(guān)鍵字｛9,01,23,14,55,20,84,27｝,承受哈希函數(shù)：H（key）=key

mod7和二次探測(cè)再散列法解決沖突，對(duì)該關(guān)鍵字序列構(gòu)造表長(zhǎng)為10的哈希表。

3.假設(shè)用于通訊的電文僅由8個(gè)字母組成，字母在電文中消滅的頻率分別為0.07、0.19、

0.02、0.06、0.32、0.03、0.21、0.10,試為這8個(gè)數(shù)字設(shè)計(jì)哈夫曼編碼。

4.用普里姆算法構(gòu)造以下圖的一棵最小生成樹(shù)，并給出選點(diǎn)挨次。（以①為起點(diǎn)）

五、算法設(shè)計(jì)題（10分）

編寫(xiě)一個(gè)算法來(lái)交換單鏈表中指針P所指接點(diǎn)與其后繼結(jié)點(diǎn)，HEAD是該鏈表的頭結(jié)點(diǎn)，P

指向該鏈表中的某一結(jié)點(diǎn)。

山東省2022年一般高等教育專升本統(tǒng)一考試

數(shù)據(jù)構(gòu)造（50分）

一、單項(xiàng)選擇題（1（）分，每題1分）

1.【答案】D

【解析】棧的根本性質(zhì)是后進(jìn)先出，此題中，在輸出序列第一個(gè)元素是i時(shí)，只能確定1-

i-1這些元素的輸出的先后次序，但是不能確定出第i個(gè)元素具體輸出哪個(gè)元素。

2.【答案】D

【解析】在循環(huán)隊(duì)列中，rear指針指示隊(duì)尾，此題中存儲(chǔ)數(shù)組實(shí)質(zhì)上為A[m+1]。所以，入

隊(duì)列的操作應(yīng)當(dāng)是修改rear=（rear+l）%（m+l）,答案C是錯(cuò)誤的。

3.【答案】B

【解析】此題中二維數(shù)組屬于9行10列。所以，首先確定以行序?yàn)橹餍虻拇鎯?chǔ)中，A[8][5]

在全部元素排列中的位置為第85位，同樣確實(shí)定以列序?yàn)橹餍虻牡?5個(gè)存儲(chǔ)元素的元素

應(yīng)當(dāng)為A[3][10]。

4.【答案】A

【解析】構(gòu)成廣義表的數(shù)據(jù)元素可以是單個(gè)元素，也可以是廣義表。廣義表的表頭就是廣

義表中的第一個(gè)元素，可以是單個(gè)元素，也可以是子表。選項(xiàng)B、C、D都是正確的。

5.【答案】D

【解析】在算數(shù)表達(dá)式的前綴表達(dá)式實(shí)質(zhì)上就是運(yùn)算符寫(xiě)在兩個(gè)運(yùn)算數(shù)的前面，固然在實(shí)

現(xiàn)轉(zhuǎn)換時(shí)，要考慮運(yùn)算數(shù)的相對(duì)位置不變，而且考慮運(yùn)算的優(yōu)先級(jí)問(wèn)題。固然，也可以采

用二叉樹(shù)表示出算數(shù)表達(dá)式，這樣，前序遍歷挨次即為前綴表達(dá)式（波蘭式），后序遍歷即

位后綴表達(dá)式（逆波蘭式），此題答案選D。

6.【答案】D

【解析】哈夫曼樹(shù)的特點(diǎn)是沒(méi)有度為1的結(jié)點(diǎn)，依據(jù)二叉樹(shù)的性質(zhì)3,n0=n2+l,所以，具

有n個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)具有n-l個(gè)度為2的結(jié)點(diǎn)，因此，答案選D。

7.【答案】C

【解析】由于在中序線索二叉樹(shù)中，結(jié)點(diǎn)X有左子樹(shù)，所以，該結(jié)點(diǎn)前驅(qū)在左子樹(shù)中，左

子樹(shù)中最右的結(jié)點(diǎn)是子樹(shù)中最終一個(gè)遍歷的結(jié)點(diǎn)，該結(jié)點(diǎn)可能為葉子結(jié)點(diǎn)，也可能是度為

1的結(jié)點(diǎn)（即有左孩子）。

8.【答案】A

【解析】依據(jù)此題無(wú)向圖的定義，可以圖G如右圖所示：、,

依據(jù)廣度優(yōu)先遍歷的算法思想，可以確定A是正確的，選項(xiàng)B、C、D都是錯(cuò)誤的。

9.【答案】D

【解析】實(shí)行線性探測(cè)法存儲(chǔ)這k個(gè)同義詞，則第一個(gè)關(guān)鍵字可以直接存儲(chǔ)，其余的k-1

個(gè)元素中，抱負(fù)的狀況下，第1個(gè)元素探測(cè)1次可以存儲(chǔ)，第2個(gè)元素探測(cè)2次才能存儲(chǔ)，

以此類推，因此，至少需要探測(cè)的次數(shù)為k（k+l）/2。

10.【答案】B

【解析】直接插入排序的算法思想是從第2到最終一個(gè)元素，依次插入到前面的有序序列中,

因此，每趟執(zhí)行完畢，不能確定出一個(gè)元素最終的位置：快速排序的每趟可以確定出樞軸元

素的最終位置，而且，當(dāng)元素根本有序時(shí)，其排序性能會(huì)降低，所以選Bo選項(xiàng)C、D能符

合第一條要求，但是其時(shí)間性能跟待排元素的序列無(wú)關(guān)。

二、填空題（本大題共10小題，每題1分，共10分）

1.【答案】6、9、11、12

【解析】依據(jù)有序表的折半查找的mid的取值為（low+high）/2,可以確定判定樹(shù)的形態(tài)如下，

10J112

查找下標(biāo)為12的元素時(shí)，先后要與下標(biāo)為：6、9、11、

12四個(gè)元素進(jìn)展比較。

2.【答案】克魯斯卡爾（Kruskal）

【解析】求解最小生成樹(shù)的算法主要有兩種，普里姆算法（Prim）時(shí)間簡(jiǎn)單度為O（n2）,

與網(wǎng)中的邊數(shù)無(wú)關(guān)，因此適合于求邊稠密的網(wǎng)的最小生成樹(shù)；而克魯斯卡爾（Kruskal）算

法時(shí)間簡(jiǎn)單度為O（eloge）,因此，適合于求邊稀疏的網(wǎng)的最小生成樹(shù)。

3.【答案】2

【解析】左子樹(shù)為空，則根結(jié)點(diǎn)沒(méi)有前驅(qū)，左孩子指針域?yàn)榭?，另外，根結(jié)點(diǎn)右子樹(shù)中最

終一個(gè)結(jié)點(diǎn)沒(méi)有后繼，右孩子指針域也為空，所以，該二叉樹(shù)中空鏈域的個(gè)數(shù)為2。

4.【答案】p->next!=NULL（或文字說(shuō)明“指針P所指結(jié)點(diǎn)的指針域不等于NULL”）

【解析】在單鏈表L中，指針p所指結(jié)點(diǎn)有后繼，前提是指針P所指結(jié)點(diǎn)的指針域不等于

NULL,假設(shè)指針域默認(rèn)為next,則可以表示為“p->next!=NULL”。（注：NULL肯定是

大寫(xiě)）

Llogzj+i

5.【答案】2

【解析】深度為K的結(jié)點(diǎn)已經(jīng)構(gòu)成完全二叉樹(shù)，所以前i個(gè)結(jié)點(diǎn)也為完全二叉樹(shù)，所以依

據(jù)性質(zhì)4可以確定第i個(gè)結(jié)點(diǎn)的深度為L(zhǎng)°g2J+1。

三、推斷題（5分，每題1分）

1.【答案】V

【解析】鏈?zhǔn)酱鎯?chǔ)構(gòu)造的線性表的優(yōu)點(diǎn)就在于實(shí)現(xiàn)插入和刪除操作時(shí)，不需要大量元素的

移動(dòng)，因此，比挨次存儲(chǔ)構(gòu)造中實(shí)現(xiàn)插入刪除操作效率高。

2【答案】X

【解析】實(shí)現(xiàn)二叉樹(shù)的按層遍歷時(shí)，應(yīng)借助于一個(gè)隊(duì)列作為關(guān)心構(gòu)造。

3【答案】V

【解析】樹(shù)轉(zhuǎn)換為二叉樹(shù)是依據(jù)的孩子兄弟表示法這種存儲(chǔ)構(gòu)造，樹(shù)根沒(méi)有兄弟，所以，

一棵樹(shù)轉(zhuǎn)換成二叉樹(shù)，對(duì)應(yīng)二叉樹(shù)根結(jié)點(diǎn)沒(méi)有左子樹(shù)。

4【答案】X

【解析】有向圖的鄰接表中結(jié)點(diǎn)的個(gè)數(shù)與逆鄰接表中結(jié)點(diǎn)的個(gè)數(shù)是相等的，都等于圖中全

部頂點(diǎn)的入度和（或出度和）的值。

5【答案】X

【解析】就平均時(shí)間而言，快速排序目前被認(rèn)為是最好的一種內(nèi)部排序方法，但是，當(dāng)待

排序列根本有序時(shí)，快速排序?qū)⑼懟癁槊芭菖判颍虼?，排序效果反而降低?/p>

四、綜合應(yīng)用題（本大題共3小題，每題5分，共15分）

1-答：依據(jù)結(jié)點(diǎn)畫(huà)出二叉排序的過(guò)程如下圖：

等概率狀況下，平均查找長(zhǎng)度為：15*2+4*2+3*3+2*2+1*1)/10=3.2

2.答：依據(jù)哈希函數(shù)和處理沖突的方法為二次探測(cè)再散列，構(gòu)造哈希表如下圖:

0123456789

14192384275520

【解析】留意關(guān)鍵字的挨次,9%7=2;1%7=1;23%7=2,沖突，但是(2+12)%10=3;14%7=0;

55%7=6;20%7=6,沖突，但是(6+12)%10=7;84%7=0,沖突，但是(0+12)%10=1,已經(jīng)占用，由于函數(shù)

值己經(jīng)是0了，在這里不能再摸索-12,因此(0+22)%10必,所以84存儲(chǔ)在下標(biāo)4的單元格內(nèi)。

最終27%7=6,沖突,(6+12)%10=7,仍舊沖突,(6-12)%10=5,所以27存儲(chǔ)在下標(biāo)5的單

元格內(nèi)。

3.答：依據(jù)每個(gè)字符消滅的頻率，我們可以求解哈夫曼樹(shù)，為便利求解，不妨將頻率變?yōu)?/p>

整數(shù)，則權(quán)值分別為：7,19,2,6,32,3,21,10,由此構(gòu)造哈夫曼如圖：

由此可以設(shè)定每個(gè)字符的哈夫曼編碼：0.02：00000：0.03:00001;0.06:0001;

0.07:0010;0.1:0011;0.32:01;0.19:10;0.21:11.

4.答:依據(jù)普里姆算法構(gòu)造最小生成樹(shù)，如以下圖所示：

五、算法設(shè)計(jì)(本大題共1小題，共1()分)

答：Linklistexchange(Linklist&head,Linklistp)

{q=head->next;

pre=head;//初始化q、pre指針，當(dāng)q指針移動(dòng)到與P指針相等時(shí)，貝！Ipre指針正好指向前

驅(qū)結(jié)點(diǎn)；

while(q!=NULL&&q!=p){pre=q;q=q->next;}

if(p->next==NULL)printf("p無(wú)后繼結(jié)點(diǎn)\n");

else{q=p->next;〃利用q、pre、p三個(gè)指針聯(lián)合實(shí)現(xiàn)當(dāng)前結(jié)點(diǎn)與前驅(qū)結(jié)點(diǎn)的交換；

pre->next=q;

p->next=q->next;

q->next=p;

)

}

山東省2022年一般高等教育專升本統(tǒng)一考試

計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)綜合二試卷參考答案

數(shù)據(jù)構(gòu)造(50分)

一、單項(xiàng)選擇題(每題1分，共10分)

1.【答案】C

【解析】具有三個(gè)結(jié)點(diǎn)的二叉樹(shù)的形態(tài)共有5種，而具有三個(gè)結(jié)點(diǎn)的樹(shù)的形態(tài)是2種。

2.【答案】C

【解析】假設(shè)輸出的第一個(gè)元素為n,則全部元素均已經(jīng)入棧，所以出棧挨次即為元素的

逆序排列，因此，輸出的第i個(gè)元素的值為n-i+L

3.【答案】A

【解析】依據(jù)樹(shù)與二叉樹(shù)的相互轉(zhuǎn)換數(shù)關(guān)系，以及樹(shù)及二叉樹(shù)的遍歷挨次，有以下結(jié)論：

(1)樹(shù)的先根遍歷挨次與對(duì)應(yīng)二叉樹(shù)的先序遍歷挨次一樣；(2)樹(shù)的后根遍歷挨次與對(duì)

應(yīng)二叉樹(shù)的中序遍歷挨次一樣。

4.【答案】D

【解析】算法的時(shí)間性能的評(píng)價(jià)主要使用算法的時(shí)間簡(jiǎn)單度，算法的空間性能的評(píng)價(jià)主要

承受空間簡(jiǎn)單度。

5.【答案】A

【解析】線性表的挨次存儲(chǔ)構(gòu)造要求安排連續(xù)的存儲(chǔ)空間，因此，可以實(shí)現(xiàn)數(shù)據(jù)元素的順

序存取以及隨機(jī)存取。但元素的插入和刪除需要涉及大量元素的移動(dòng)；而線性表的鏈?zhǔn)酱?/p>

儲(chǔ)便利于元素的插入與刪除，但是不能實(shí)現(xiàn)隨機(jī)存取，只能進(jìn)展挨次存取。

6.【答案】D

【解析】挨次表要求存儲(chǔ)空間是連續(xù)，所以，只要知道基地址，知道每個(gè)元素所占的字節(jié)

數(shù)，就可以求每個(gè)元素的存儲(chǔ)起始地址。

7.【答案】D

【解析】在中序線索二叉樹(shù)中，假設(shè)某結(jié)點(diǎn)有右子樹(shù)，則在訪問(wèn)完該結(jié)點(diǎn)后要訪問(wèn)右子樹(shù)

中最左邊的結(jié)點(diǎn)，所以答案選D。

8.【答案】C

【解析】棧的根本性質(zhì)是后進(jìn)先出，在入棧序列為abcde,出棧的第一個(gè)元素為d時(shí)，則己

經(jīng)入棧，所以，此時(shí)“abc”三個(gè)元素的出棧序列中，肯定是cba的挨次，而不能消滅cab

的挨次，所以選項(xiàng)C是錯(cuò)誤的。

9.【答案】A

【解析】構(gòu)成廣義表的數(shù)據(jù)元素可以單個(gè)元素，也可以是由假設(shè)干個(gè)元素所組成的子表。

廣義表屬于特別的線性表，特別的地方在于廣義表的元素中能否使用子表。

10.【答案】B

【解析】依據(jù)二叉樹(shù)的根本性質(zhì)3,對(duì)于任意一棵二叉樹(shù)，滿足度為0的結(jié)點(diǎn)為度為2的

結(jié)點(diǎn)數(shù)加1。所以，答案選B

二、填空題（本大題共10小題，每題1分，共10分）

1.【答案】肯定相鄰

【解析】挨次表承受連續(xù)存儲(chǔ)空間作為元素的存儲(chǔ)構(gòu)造，所以，規(guī)律上相鄰的數(shù)據(jù)元的物

理存儲(chǔ)空間也肯定相鄰。

2.【答案】塊

【解析】在索引挨次表中，將全部的關(guān)鍵字進(jìn)展分塊，塊與塊之間關(guān)鍵字大小有序，在每

個(gè)塊內(nèi)部元素排列無(wú)序，可以把每個(gè)組中最大元素值作為該組的索引參加到索引表中排列，

所以，索引表中元素排列是有序的，因此，在查找元素時(shí)，先查找索引表，獲得查找元素

所在組后，再使用挨次查找去查找相應(yīng)的塊。

3.【答案】安排和收集

【解析】安排法排序?qū)儆谝环N典型的多關(guān)鍵字排序，安排排序的根本思想是排序過(guò)程無(wú)須

比較關(guān)鍵字，而是通過(guò)“安排”和“收集”過(guò)程來(lái)實(shí)現(xiàn)排序。

4.【答案】入度

【解析】拓?fù)渑判蛎看味歼x擇沒(méi)有前驅(qū)的結(jié)點(diǎn)進(jìn)展輸出，其中結(jié)點(diǎn)沒(méi)有前驅(qū)，即入度為0。

5.【答案】n+1

【解析】二叉鏈表中，每個(gè)結(jié)點(diǎn)有2個(gè)指針域，具有n個(gè)結(jié)點(diǎn)的二叉鏈表一共有2n個(gè)指針

域，其中，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)需要一個(gè)指針來(lái)指向，所以空的指針域的個(gè)數(shù)為n+1。6.

【答案】出度

【解析】有向圖的鄰接表是指:全部頂點(diǎn)建立頂點(diǎn)結(jié)點(diǎn)，以每個(gè)頂點(diǎn)為弧尾的全部弧對(duì)應(yīng)的

另外一個(gè)頂點(diǎn)序號(hào)構(gòu)成表結(jié)點(diǎn)鏈接形成的單鏈表。所以，通過(guò)計(jì)數(shù)每個(gè)單鏈表中表結(jié)點(diǎn)的

個(gè)數(shù)，可以計(jì)算每個(gè)頂點(diǎn)的出度。

7.【答案】列

【解析】有向圖的鄰接矩陣的特點(diǎn)是，通過(guò)求解每一行上1的個(gè)數(shù)，可以求解每個(gè)頂點(diǎn)的

出度；通過(guò)求解每一列上1的個(gè)數(shù)，可以求解每個(gè)頂點(diǎn)的出度。無(wú)向圖的鄰接矩陣屬于對(duì)

稱矩陣，每個(gè)頂點(diǎn)的度即為行或列上1的個(gè)個(gè)數(shù)。

8.【答案】雙親

【解析】樹(shù)的表示方法一共有三種，雙親表示法、孩子表示法以及孩子兄弟表示法。其中

雙親表示法為每個(gè)樹(shù)中元素建立一個(gè)結(jié)點(diǎn)，包括存儲(chǔ)數(shù)據(jù)元素本身，以及該結(jié)點(diǎn)的雙親結(jié)

點(diǎn)的存儲(chǔ)下標(biāo)，所以，該存儲(chǔ)方法可以很簡(jiǎn)潔的求解結(jié)點(diǎn)的雙親以及祖先，但是求解結(jié)點(diǎn)

的孩子及后代需要遍歷整個(gè)數(shù)組。

樹(shù)的帶權(quán)路徑長(zhǎng)度為:

(2+3)*4+5*3+9*2+14*1=67

10.【答案】n(n-l)

【解析】在有n個(gè)頂點(diǎn)的有向完全圖中，從每個(gè)頂點(diǎn)出去的弧有n-1條，所以總弧數(shù)為

n(n-l)。

四、綜合題(30分，每題5分)

1.答：viodcreat(Linklist&L)

{L=(Linklist)malloc(sizeof(Lnode));

L->next=NULL;

for(i=n;i>0;i++)

{p=(Linklist)malloc(sizeof(Lnode));

scanf(&p-〉data);

p->next=L->next;

L->next=p;

}

}留意：除了使用頭插法，還有尾插法，可以查閱資料寫(xiě)出算法。

2.答：

求頂點(diǎn)0其余各頂點(diǎn)的最短路徑

110///

(0,1)

2OO6050/

(0,1,2)(0,3,2)

33030//

(0,3)(0,3)

41001009060

(0,4)(0,4)(0,3,4)(0,3,2,4)

添加132

頂點(diǎn)

3.答：依據(jù)（1）中序遍歷的特點(diǎn)：左子樹(shù)、根、右子樹(shù)的遍歷挨次；（2）后序遍歷的特

點(diǎn)：左子樹(shù)、右子樹(shù)、根：（3）二叉樹(shù)的每棵子樹(shù)也符合該特性。所以，該二叉樹(shù)的構(gòu)造

過(guò)程為：

由此可得到二叉樹(shù)的前序遍歷挨次為：abdfceih

5.答：

該鄰接表的構(gòu)造描述如下：

#defineVERTEX.MAX100

typedefstructnode

{intadjvex;

structnode*next;

}Edgenode;〃表結(jié)點(diǎn)的類型定義

typedefstructvnode

{vextypevertex;

Edgenode*firstedge;

}VertexNode;〃頂點(diǎn)結(jié)點(diǎn)的類型定義

Typedefstruct

{VertexNodeadjlist[VERTEXJIAX];

intn,e;〃頂點(diǎn)數(shù)和邊數(shù)

}ALGraph;〃鄰接表的類型定義

voidBFS(ALGraph*G){

for(v=0;v<g->n;v++)visited[v]=FALSE;

InitQueue(Q)；

for(v=0;v<g->n;v++)

if(!visited[v])

{visited[v]=TURE;

Printf(,G->adjlist[v].vertex);

EnQueue(Q,v)

while(!QueueEmpty(Q)){

DeQueue(Q,u)；

for(p=G->adjlist[u].firstedge;p;p=p->next)

if(!visited[p->adjvex])

{visited[p->adjvex]=TRUE;

Printf(,G->adjlist[p->adjvex].vertex);

EnQueue(Q,p->adjvex);

)

)

)

)

6.答：依據(jù)哈希函數(shù)以及拉鏈法解決沖突，構(gòu)造如下哈希表：

0

1

2

3

4

5

6

8

9

10

11

山東省2022年一般高等教育專升本統(tǒng)一考試

數(shù)據(jù)構(gòu)造（50分）

一、單項(xiàng)選擇題（每題1分，共10分）

1.【答案】D

【解析】全部能輸入到計(jì)算機(jī)中的符號(hào)的總稱為數(shù)據(jù)，數(shù)據(jù)元素是構(gòu)成數(shù)據(jù)的根本單位，

數(shù)據(jù)元素可以由假設(shè)干條記錄組成，每條記錄又可由假設(shè)干數(shù)據(jù)項(xiàng)組成。一樣性質(zhì)的數(shù)據(jù)

元素的集合構(gòu)成數(shù)據(jù)對(duì)象。數(shù)據(jù)元素的類型稱為數(shù)據(jù)類型。

2.【答案】B

【解析】承受挨次存儲(chǔ)構(gòu)造的線性表在進(jìn)程插入和刪除元素時(shí)需要涉及大量元素的移動(dòng)問(wèn)

題。而鏈?zhǔn)酱鎯?chǔ)構(gòu)造可以很簡(jiǎn)潔的實(shí)現(xiàn)插入和刪除操作，因此選B。

3.【答案】D

【解析】假設(shè)9作為第一個(gè)出棧元素，前提是3,5,7已經(jīng)依次入棧了，所以，此時(shí)輸出

挨次只能為9,7,5,3。選項(xiàng)D是錯(cuò)誤的。

4.【答案】D

【解析】字符串的長(zhǎng)度應(yīng)當(dāng)是串中全部包含的字符的個(gè)數(shù)，所以選項(xiàng)A只提到了字母，選

項(xiàng)B提到了不同字符的個(gè)數(shù)，均是錯(cuò)誤的，每個(gè)字符串都屬于自己的子串，因此選項(xiàng)C錯(cuò)

誤。

5.【答案】D

【解析】廣義表的表頭是廣義表中的頭元素，廣義表的表尾是指除去表頭元素，其余元素

所組成的廣義表，因此，答案選D而不是C,更不是A和B。

6.【答案】A

【解析】圖的生成樹(shù)是指包含圖中全部的n個(gè)頂點(diǎn)，但僅包含連通這個(gè)n個(gè)頂點(diǎn)的n-1條

邊。

7.【答案】C

【解析】依據(jù)二叉樹(shù)的根本性質(zhì)3：對(duì)于任意一棵二叉樹(shù)滿足nO=n2+I,所以，當(dāng)度為2的

結(jié)點(diǎn)數(shù)為8時(shí)，葉子結(jié)點(diǎn)個(gè)數(shù)為9。

8.【答案】A

【解析】在二叉鏈表中每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，而除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均需要占用其

中一個(gè)指針域，所以空的指針域個(gè)數(shù)為：2*n-(nT)=n+l個(gè)。

9.【答案】C

【解析】在等概率的狀況下，每個(gè)元素的查找概率都是1/n,其中查找最終一個(gè)元素需要

比較1次，查找第n-1個(gè)結(jié)點(diǎn)需要比較2次，依次類推，查找第1個(gè)結(jié)點(diǎn)需要比較n次，

平均查找長(zhǎng)度為：(1+2+3+,,)/n=(n+l)/2o

10.【答案】A

【解析】對(duì)含有n個(gè)元素的線性表，執(zhí)行選擇排序時(shí)，無(wú)論序列的初始排列如何，均需要進(jìn)

展n-1趟排序，每次都需要n-i次比較，確定出第i個(gè)位置上的元素來(lái)，所以答案選A。而

插入排序、冒泡排序當(dāng)元素已經(jīng)有序時(shí)，比較次數(shù)可以降低為n-1次；快速排序當(dāng)元素排列

根本有序時(shí)，性能反而降低。

二、填空題(本大題共10小題，每題1分，共10分)

1.【答案】f==r

【解析】在循環(huán)隊(duì)列中，分別用f指示隊(duì)頭，r指向隊(duì)尾。所以當(dāng)f==r時(shí)，表示隊(duì)列中沒(méi)

有元素存在，通常當(dāng)(r+I)%maxsize==f時(shí)，表示該循環(huán)隊(duì)列已滿。(以犧牲一個(gè)存儲(chǔ)空間

偉代價(jià))。在此留意是“=="，而不是。

2.【答案】1/2

【解析】假設(shè)在長(zhǎng)度為n的挨次表中插入元素時(shí)，插入位置有n+1個(gè)，平均需要移動(dòng)元素

數(shù)量為(0+l+2?+n)/(n+l)=n/2；當(dāng)刪除元素時(shí)，刪除位置有n個(gè)，平均需要移動(dòng)的元

素個(gè)數(shù)為：(0+l+2+?+(n-l))/n=(n-l)/2o都接近1/2的元素個(gè)數(shù)。

3.【答案】38

【解析】二位數(shù)組每行中有5個(gè)元素，每個(gè)元素占2個(gè)字節(jié)，因此LOC(3,2)

=LOC(O,0)+(3*4+2)*2=38

4.【答案】2K-1

【解析】二叉樹(shù)的根本性質(zhì)2。

5.【答案】e

【解析】有向圖的鄰接表是以圖中全部頂點(diǎn)作為頭結(jié)點(diǎn)，將全部以該頂點(diǎn)為弧尾的弧生成

表結(jié)點(diǎn)構(gòu)成的。所以，表結(jié)點(diǎn)數(shù)與弧數(shù)是一一對(duì)應(yīng)的。

6.【答案】中序

【解析】二叉排序樹(shù)中全部左子樹(shù)中結(jié)點(diǎn)均比根結(jié)點(diǎn)的值小，所以右子樹(shù)中結(jié)點(diǎn)值均比根

結(jié)點(diǎn)的值大，假設(shè)左右子樹(shù)不空，左右子樹(shù)都滿足該特性，所以二叉排序樹(shù)的中序遍歷挨

次是由小到大的挨次排列的。

7.【答案】2

【解析】無(wú)論在有向圖還是在無(wú)向圖中，每條邊或弧在計(jì)算頂點(diǎn)的度時(shí)均被用過(guò)2次，所

以，得到的頂點(diǎn)的度的和就是邊數(shù)的2倍。

8.【答案】3

【解析】該有序表中包含7個(gè)元素，因此先與第4個(gè)元素進(jìn)展比較，然后和第2個(gè)元素進(jìn)

展比較，最終和第3個(gè)元素進(jìn)展比較，所以共需要比較3次成功。

9.【答案】9

【解析】依據(jù)哈希函數(shù)求得函數(shù)值為5,查找覺(jué)察沖突，依據(jù)二次探測(cè)再散列，分別將函

數(shù)值+12、-12、+22、-2z,,,并對(duì)表進(jìn)步行取余，進(jìn)展摸索。所以答案填9。

10.【答案】n(n-l)/2

【解析】在有n個(gè)頂點(diǎn)的無(wú)向完全圖中，從每個(gè)頂點(diǎn)出去的邊有nT條邊，但每條邊被用

過(guò)2次，所以總邊數(shù)為n(n-1)/2。

三、推斷題(本大題共5小題，每題1分，共5分)

1.【答案】X

【解析】算法的特性包含確定性。確定性就是指每條指令必需是確定的含義，不能產(chǎn)生二

義性，并且，在任何條件下，算法只有唯一的一條執(zhí)行路徑，即對(duì)一樣的輸入只能得出一

樣的輸出。

2.【答案】X

【解析】線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造的存儲(chǔ)單元地址不要求連續(xù)，但是可以連續(xù)；而線性表的

挨次存儲(chǔ)構(gòu)造肯定要求安排連續(xù)的存儲(chǔ)單元。

3.【答案】V

【解析】隊(duì)列屬于特別的線性表，要求在表的一端進(jìn)展插入，在表的另一端進(jìn)程刪除，能

夠插入的一端稱為隊(duì)尾，能夠刪除的一端稱為對(duì)頭。

4.【答案】X

【解析】?jī)?nèi)部排序指的是待排記錄存放在計(jì)算機(jī)隨機(jī)存儲(chǔ)器中進(jìn)展的排序過(guò)程，外部排序

指的是待排記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過(guò)程中尚需對(duì)外存

進(jìn)展訪問(wèn)的排序過(guò)程。拓?fù)渑判虿粚儆趦?nèi)部排序。

5.【答案】V

【解析】一棵樹(shù)轉(zhuǎn)化為二叉樹(shù)，其根結(jié)點(diǎn)肯定沒(méi)有右孩子，即該二叉樹(shù)沒(méi)有右子樹(shù)。只有

2棵及以上的非空樹(shù)組成的森林轉(zhuǎn)化為二叉樹(shù)，才能使得對(duì)應(yīng)二叉樹(shù)有右子樹(shù)。

四、綜合應(yīng)用題(本大題共3小題，每題5分，共15分)

1,答：具有三個(gè)結(jié)點(diǎn)的二叉樹(shù)共有5種根本形態(tài)，具體如以下圖所示：

VI-V4-V5-V2-V3或VI-V2-*V5-V4-V3或VI-V3-*V2-*V5-*V4或VI-V3-*V4-*V5-

V2

3.答：樹(shù)轉(zhuǎn)換為二叉樹(shù)為：其中該二叉樹(shù)的先序遍歷挨次為A,B,C,E,F,G,D

五、算法設(shè)計(jì)(本大題共1小題，共10分)

答：Linklistdelete(Linklist&L,Elemtypex)

{Linklistp,q;

q=L;p=L->next;〃初始化P指向第一個(gè)結(jié)點(diǎn)，q始終指向P結(jié)點(diǎn)的前驅(qū);

while(p!=NULL)

{if(p->data==x)//找到符合條件的結(jié)點(diǎn);

{q->next=p->next;

free(p);

p=q->next;〃刪除該結(jié)點(diǎn)，并修改P指針;

else

{q=p;

p=p->next;//先使q后移，p向后移動(dòng)。

}

06c語(yǔ)言程序設(shè)計(jì)〔50分〕

六、單項(xiàng)選擇題(在每題的四個(gè)備選答案中，選出一個(gè)正確的答案，并將其號(hào)碼

填寫(xiě)在題干后面的括號(hào)內(nèi)。每題1分，共15分)

1.C語(yǔ)言程序的根本單位是()

A.程序行B.語(yǔ)句C.函數(shù)D.字符

2.可用作C語(yǔ)言用戶標(biāo)識(shí)符的一組字符串是()

A.voiddefineWORDB.a3_b3_123IFC.ForabcCaseD.2aDOsizeof

3.設(shè)inta=12,則執(zhí)行完語(yǔ)句a+=a-=a*a后，a的值是()

A.552B.264C.144D.-264

4.以下表達(dá)正確的選項(xiàng)是()

A.do-while語(yǔ)句構(gòu)成的循環(huán)不能用其它語(yǔ)句構(gòu)成的循環(huán)來(lái)代替。

B.do-while語(yǔ)句構(gòu)成的循環(huán)只能用break語(yǔ)句退出。

C.用do-while語(yǔ)句構(gòu)成的循環(huán)，在while后的表達(dá)式為非零時(shí)完畢循環(huán)。

D.用do-while語(yǔ)句構(gòu)成的循環(huán)，在while后的表達(dá)式為零時(shí)完畢循環(huán)。

5.設(shè)有說(shuō)明int(*ptr)[10]其中的標(biāo)識(shí)符ptr是()

A.10個(gè)執(zhí)行整型變量的指針B.

指向10個(gè)整型變量函數(shù)指針

C.一個(gè)指向具有10個(gè)整型元素的一維數(shù)組的指針

D.具有10個(gè)指針元素的一維指針數(shù)組，每個(gè)元素都只能指向整型量

6.有以下程序段

typedefstruct

NODE(intnum;

structNODE*next;

}OLD;

則以下表達(dá)中正確的選項(xiàng)是()

A.以上的說(shuō)明形式非法B.NODE是一個(gè)構(gòu)造體類型

C.OLD是一個(gè)構(gòu)造體類型D.OLD是一個(gè)構(gòu)造體變量

7.以下不能正確計(jì)算代數(shù)式值的C語(yǔ)言表達(dá)式是()

A.l/3*sin(l⑵*sin(l/2)B.sin(0.5)*sin(0.5)/3

C.pow(sin(0.5),2)/3D.l/3.0*pow(sin(1.0/2),2)

8.C語(yǔ)言規(guī)定，程序中各函數(shù)之間()

A.既允許直接遞歸調(diào)用也允許間接遞歸調(diào)用B.

不允許直接遞歸調(diào)用也不允許間接遞歸調(diào)用C.

允許直接遞歸調(diào)用不允許間接遞歸調(diào)用

D.不允許直接遞歸調(diào)用允許間接遞歸調(diào)用

9.在宏定義#definePI3.14159中，用宏名PI代替一個(gè)()

A.單精度數(shù)B.雙精度數(shù)C.常量D.字符串

10.在C語(yǔ)言中，要求運(yùn)算數(shù)必需是整型的運(yùn)算符是()

A.%B./C.<D.!

11.為表示關(guān)系xeyez,應(yīng)使用的C語(yǔ)言表達(dá)式是()

A.(x>=y)&&(y>=z)B.(x>=y)AND(y>=z)

C.(x>=y>=z)D.(x>=y)&(y>=z)

12.有以下程序段

intk=0,a=3,b=4,c=5;k=a>c?c:k;

執(zhí)行該程序段后，k的值是()

A.3B.2C.lD.0

13.假設(shè)定義char*s="\\"Name\\Address\n",則指針S所指字符串的長(zhǎng)度為()

A.19B.15C.18D.說(shuō)明不合法

14.下述對(duì)C語(yǔ)言字符數(shù)組的描述中錯(cuò)誤的選項(xiàng)是

()A.字符數(shù)組可以存放字符串

B.字符數(shù)組中的字符串可以整體輸入、輸出

C.可以在賦值語(yǔ)句中通過(guò)賦值運(yùn)算符對(duì)字符數(shù)組整體賦值

D.不行以用關(guān)系運(yùn)算符對(duì)字符數(shù)組中的字符串進(jìn)展比較

15.設(shè)有如下的函數(shù)

exam(float

x){printf("\n%f

”,x*x);

}

則函數(shù)的類型為()

A.與參數(shù)x的類型一樣B.是voidC.是intD.無(wú)法確定

七、閱讀以下程序，寫(xiě)出其運(yùn)行結(jié)果(每題5分，共25分)

1、程序：

main

{inti,j,x;

for(i=l;i<=4;i++)

{for(j=1；jv=4-i;j++)

printf(““)；

for(j=0;j<=2*i+1;j++)

printf(“*")；

printf("\n”)；

)

)

答案：

2、程序：

main

{intk=3,n=0;

while(k>0)

{switch(k)

{case1:n+=k;

case2:

case3:n+=k;

default:break;

)

k-；

)

printf(a%d\n",n);

)

答案：

3、程序：

main

{inti,j,row,column,m;

staticintarray[3][3]={{100,200,300},{28,72,-30},{-850,2,6}};

m=array[0][0];

for(i=0;i<3;i++)

for(j=0;j<3;j++)

if(array[i](j]<m)

{m=array[i][j];

row=i;column=j;

)

printf(a%d,%d,%d\na,m,row,column);

)

答案：

4、程序

#include<stdio.h>

intp(intk,inta[])

{intm,i,c=0;

for(m=2;m<=k;m++)

for(i=2;i<m;i++)

{if(!(m%i))break;

if(i==m)a[c++]=m;

}

returnc;

#defineMAXN20

main

inti,m,s[MAXN];

m=p(13,s);

for(i=0;i<m;i++)

print-"％4d"聞i]);

printf(u\n");

)

答案：

5.程序：

intf(intn)

{if(n==0||n==1)

return1;

returnf(n-2)+2*f(n-l);

)

main

{intn=5;

printf(a%d“,f(5)

)；

)

答案：

八、程序填空：按要求完成下面的程序(函數(shù))(每空2分，共10分)

1.本函數(shù)用對(duì)分查找法，在以按字母次序從小到大排序的字符數(shù)組list中查找字符C,假設(shè)C

在數(shù)組中，函數(shù)返回字符C在數(shù)組中的下標(biāo)，否則返回-1。

intsearch(charlist[|,charc,intlen)

{intlow.hige,k;

low=0;high=len-l;

while((1))

{k=(low+high)/2;

if(⑵)returnk;

elseif((3))

high=k-1;

elselow=k+1;

)

return-1;

)

答案：⑴