2023年北理工春秋數(shù)據(jù)結(jié)構(gòu)與算法在線作業(yè)

一、單選題(共40道試題，共100分。)V1.3個(gè)結(jié)點(diǎn)的無(wú)向完全連通圖至少有()條邊。

A.3

B.4

C.5

D.6

2.設(shè)有一個(gè)二維數(shù)A[m][n],以行序?yàn)橹餍虼鎯?chǔ)。假設(shè)A[0][0]存放位置在644(10),A[2]

[2]存放位置在676(10),每個(gè)元素占一個(gè)空間，則A⑷⑸在0位置,(10)表白用10進(jìn)

數(shù)表達(dá)。

A.692(10)

B.626(10)

C.709(10)

D.724(10)

3.具有n個(gè)頂點(diǎn)的有向完全圖有()條弧。

A.n

B.n*(n-1)

C.n*(n+1)

D.n*n

4.隊(duì)列的操作特點(diǎn)是

A.先進(jìn)先出

B.后進(jìn)先出

C.先進(jìn)后出

D.只能從隊(duì)尾出隊(duì)

5.一個(gè)棧的入棧序列是abcde,則棧的不也許的輸出序列是()。

A.edcba

B.decba

C.dceab

D.abede

6.某二叉樹的前序和后序序列正好相同，則該二叉樹一定是()的二叉樹。

A.空或只有一個(gè)結(jié)點(diǎn)

B.高度等于其結(jié)點(diǎn)數(shù)

C.任一結(jié)點(diǎn)無(wú)左孩子

D.任一結(jié)點(diǎn)無(wú)右孩子

7.學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)重要目的是()。

A.解決數(shù)值計(jì)算問題

B.研究程序設(shè)計(jì)技巧

C.選取合適數(shù)據(jù)結(jié)構(gòu)，寫出更有效的算法

D.是計(jì)算機(jī)硬件課程的基礎(chǔ)

8.任何一個(gè)無(wú)向連通圖的最小生成樹0。

A.只有一棵

B.有一棵或多棵

C.一定有多棵

D.也許不存在

9.棧是一種()的數(shù)據(jù)結(jié)構(gòu)。

A.存取受限的線性結(jié)構(gòu)

B.存取不受限的線性結(jié)構(gòu)

C.存取受限的非線性結(jié)構(gòu)

D.存取不受限的非線性結(jié)構(gòu)

10.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址()

A.必須是不連續(xù)的

B.連續(xù)與否均可

C.必須是連續(xù)的

D.和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)

11.一棵高度(假定樹根結(jié)點(diǎn)為第0層)為4的完全二叉樹中的結(jié)點(diǎn)數(shù)最少為()。

A.15

B.16

C.17

D.31

12.順序查找適合于存儲(chǔ)結(jié)構(gòu)為0的查找表。

A.壓縮存儲(chǔ)

B.散列存儲(chǔ)

C.索引存儲(chǔ)

D.順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)

13.設(shè)連通圖G中的邊集E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},

則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為()

A.abedfc

B.acfebd

C.aebdfc

D.aedfcb

14.評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)重要是()。

A.執(zhí)行時(shí)間

B.輔助空間

C.算法自身的復(fù)雜度

D.執(zhí)行時(shí)間和所需的輔助空間

15.根據(jù)二叉樹的定義可知二叉樹共有()種不同的形態(tài)。

A.4

B.5

C.6

D.7

16.在一棵具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（）。

A.31

B.32

C.33

D.16

17.從1000個(gè)元素中選出其中五個(gè)最大值元素0排序最適合。

A.冒泡

B.快速排序

C.堆排序

D.選擇排序

18.快速排序?qū)儆谀欠N排序類型（）。

A.選擇排序

B.插入排序

C.互換排序

D.基數(shù)排序

19.下列排序算法中，其中（）是穩(wěn)定的。

A.堆排序，冒泡排序

B.快速排序，堆排序

C.直接選擇排序，希爾排序

D.歸并排序，冒泡排序

20.在有序表（3,8,13,15,16,17,21,24,45）中，用二分查找法查找關(guān)鍵字21,所需

進(jìn)行關(guān)鍵字比較的次數(shù)為（）。

A.2

B.3

C.4

D.5

21.數(shù)據(jù)結(jié)構(gòu)重要研究()。

A.數(shù)據(jù)的邏輯結(jié)構(gòu)

B.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

C.數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)

D.數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及數(shù)據(jù)在操作上的實(shí)現(xiàn)

22.一個(gè)n*n對(duì)稱矩陣，假如以行或列為主序存入內(nèi)存，則其容量為()。

A.n*n

B.n*n/2

C.n*(n+1)/2

D.(n+1)*(n+l)/2

23.對(duì)于經(jīng)常要存取線性表任意指定位置元素的應(yīng)用，線性表應(yīng)采用()存儲(chǔ)結(jié)構(gòu)。

A.順序存儲(chǔ)結(jié)構(gòu)

B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

C.線性鏈表

D.棧

24.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)0。

A.僅修改頭指針

B.頭、尾指針都要修改

C.僅修改尾指針

D.頭、尾指針也許都要修改

25.線性鏈表是通過()方式表達(dá)元素之間的關(guān)系

A.后繼元素地址

B.元素的存儲(chǔ)順序

C.左、右孩子地址

D.元素的相對(duì)存儲(chǔ)位置

26.某二叉樹的前序遍歷序列為abdgcefh,中序遍歷序列為dgbaechf,則其后序遍歷

序列為（）。

A.bdgecefha

B.gdbecfha

C.bdgaechf

D.gdbehfca

27.下列不屬于棧基本運(yùn)算的是0。

A.入棧

B.刪除棧底元素

C.判斷棧是否為空

D.建立一個(gè)空棧

28.快速排序方法在（）情況下最不利于發(fā)揮其長(zhǎng)處。

A.被排序的數(shù)據(jù)量太大

B.被排序數(shù)據(jù)中具有多個(gè)相同值

C.被排序數(shù)據(jù)已基本有序

D.被排序數(shù)據(jù)數(shù)目為奇數(shù)

29.具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是0

A.赫夫曼樹

B.棧

C.圖

D.樹

30.具有65個(gè)結(jié)點(diǎn)的完全二叉樹其深度為（根的層次號(hào)為1）（）。

A.8

B.7

C.6

D.5

31.假如結(jié)點(diǎn)a有三個(gè)兄弟，并且b為a的雙親，則b的度為（）。

A.3

B.4

C.5

D.2

32.在表達(dá)式求值算法中，需要用0個(gè)棧？

A.0

B.1

C.2

D.3

33.二分查找（又稱折半查找）規(guī)定查找表中的記錄按關(guān)鍵字0。

A.有序

B.無(wú)序

C.既可有序也可無(wú)序

34.下列關(guān)于A0E網(wǎng)的敘述中，不對(duì)的的是（）。

A.關(guān)鍵活動(dòng)不按期完畢就會(huì)影響整個(gè)工程的完畢時(shí)間

B.任何一個(gè)關(guān)鍵活動(dòng)提前完畢,那么整個(gè)工程將會(huì)提前完畢

C.所有的關(guān)鍵活動(dòng)提前完畢，那么整個(gè)工程將會(huì)提前完畢

D.某些關(guān)鍵活動(dòng)提前完畢，那么整個(gè)工程將會(huì)提前完畢

35.對(duì)線性表進(jìn)行二分查找時(shí),規(guī)定線性表必須（）。

A.以順序方式存儲(chǔ)

B.以鏈接方式存儲(chǔ)

C.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列

D.以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列

36.以下不穩(wěn)定的排序方法是（）

A.直接插入排序

B.冒泡排序

C.直接選擇排序

D.二路歸并排序

37.下列存儲(chǔ)表達(dá)中，哪一個(gè)不是樹的存儲(chǔ)形式（）。

A.雙親表達(dá)法

B.孩子鏈表表達(dá)法

C.順序存儲(chǔ)表達(dá)法

D.孩子兄弟表達(dá)法

38.中序遍歷一棵二叉排序樹所得到的結(jié)點(diǎn)序列是鍵值的（）序列。

A.遞增或遞減

B.遞減

C.遞增

D.無(wú)序

39.對(duì)哈希（HASH）函數(shù)H（k）=kMODm,一般來(lái)說,m應(yīng)?。ǎ?。

A.素?cái)?shù)

B.很大的數(shù)

C.偶數(shù)

D.奇數(shù)

40.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)。

A.隨機(jī)存取

B.順序存取

C.索引存取

D.散列存取

一、單選題（共40道試題，共100分。）V1.線性鏈表是通過（）方式表達(dá)元素之間的關(guān)系

A.后繼元素地址

B.元素的存儲(chǔ)順序

C.左、右孩子地址

D.元素的相對(duì)存儲(chǔ)位置

2.n個(gè)頂點(diǎn)的連通圖至少有()條邊。

A.n-1

B.n

C.n+1

D.0

3.在一個(gè)長(zhǎng)度為n的順序線性表中順序查找值為x的元素時(shí),查找成功時(shí)的平均查找長(zhǎng)度(即

X與元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等)為().

A.n

B.n/2

C.(n+1)/2

D.(n-1)/2

4.下列存儲(chǔ)表達(dá)中，哪一個(gè)不是樹的存儲(chǔ)形式()。

A.雙親表達(dá)法

B.孩子鏈表表達(dá)法

C.順序存儲(chǔ)表達(dá)法

D.孩子兄弟表達(dá)法

5.對(duì)線性表進(jìn)行二分查找時(shí)，規(guī)定線性表必須()。

A.以順序方式存儲(chǔ)

B.以鏈接方式存儲(chǔ)

C.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列

D.以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列

6.下列說法哪個(gè)是不對(duì)的的()。

A.快速排序?qū)儆诓环€(wěn)定排序。

B.希爾排序?qū)儆诓环€(wěn)定排序。

C.直接插入排序?qū)儆诓环€(wěn)定排序。

D.堆排序?qū)儆诓环€(wěn)定排序。

7.以二叉鏈表作為二叉樹的存貯結(jié)構(gòu)時(shí)，在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中（n>0）,空指針域的

個(gè)數(shù)為（）。

A.2n-1

B.n+1

C.n-1

D.2n+1

8.當(dāng)待排序列基本有序時(shí),下列排序方法中（）最佳。

A.直接插入排序

B.快速排序

C.堆排序

D.歸并排序

9.長(zhǎng)度為256的表,采用分塊查找，每塊最佳長(zhǎng)度為（）。

A.14

B.16

C.18

D.26

10.假如結(jié)點(diǎn)a有三個(gè)兄弟，并且b為a的雙親，則b的度為。。

A.3

B.4

C.5

D.2

11.采用順序搜索方法查找長(zhǎng)度為n的順序表時(shí),搜索成功的平均搜索長(zhǎng)度為0。

A.n

B.n/2

C.(n-l)/2

D.(n+l)/2

12.鑒定一個(gè)隊(duì)列Q(最多元素為mO)為滿隊(duì)列的條件是()

A.rear—front==mO

B.rear-front-1==m0

C.front==rear

D.front==rear+l

13.具有n個(gè)頂點(diǎn)的有向完全圖有()條弧。

A.n

B.n*(n-1)

C.n*(n+1)

D.n*n

14.具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是()

A.赫夫曼樹

B.棧

C.圖

D.樹

15.若構(gòu)造一棵具有n個(gè)結(jié)點(diǎn)的二叉排序樹,最壞情況下,其深度不會(huì)超過0。

A.n/2

B.n

C.(n+1)/2

D.n+1

16.以下不穩(wěn)定的排序方法是0

A.直接插入排序

B.冒泡排序

C.直接選擇排序

D.二路歸并排序

17.設(shè)有5。行60列的二維數(shù)組A[50][60],其元素長(zhǎng)度為4字節(jié)，按行優(yōu)先順序存儲(chǔ),

基地址為200,則元素A[18][25]的存儲(chǔ)地址為()。

A.3700

B.4376

C.3900

D.4620

18.從1000個(gè)元素中選出其中五個(gè)最大值元素()排序最適合。

A.冒泡

B.快速排序

C.堆排序

D.選擇排序

19.以下關(guān)于線性表的說法不對(duì)的的是()。

A.線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型

B.線性表中包含的數(shù)據(jù)元素個(gè)數(shù)不是任意的

C.線性表中的每個(gè)結(jié)點(diǎn)都有且只有一個(gè)直接前趨和直接后繼

D.存在這樣的線性表:表中各結(jié)點(diǎn)都沒有直接前趨和直接后繼

20.設(shè)有7000個(gè)無(wú)序的元素,希望用最快的速度挑選出其中前5個(gè)最大的元素,最佳選用()法。

A.冒泡排序

B.快速排序

C.堆排序

D.基數(shù)排序

21.()是HASH查找的沖突解決方法。

A.求余法

B.平方取中法

C.二分法

D.開放定址法

22.評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)重要是()。

A.執(zhí)行時(shí)間

B.輔助空間

C.算法自身的復(fù)雜度

D.執(zhí)行時(shí)間和所需的輔助空間

23.快速排序?qū)儆谀欠N排序類型()。

A.選擇排序

B.插入排序

C.互換排序

D.基數(shù)排序

24.隊(duì)列的操作特點(diǎn)是()。

A.先進(jìn)先出

B.后進(jìn)先出

C.先進(jìn)后出

D.只能從隊(duì)尾出隊(duì)

25.稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即()。

A.二維數(shù)組和三維數(shù)組

B.三元組表和散列表

C.三元組表和十字鏈表

D.散列表和十字鏈表

26.一棵高度(假定樹根結(jié)點(diǎn)為第0層)為4的完全二叉樹中的結(jié)點(diǎn)數(shù)最少為()。

A.15

B.16

C.17

D.31

27.具有65個(gè)結(jié)點(diǎn)的完全二又樹其深度為(根的層次號(hào)為1)()。

A.8

B.7

C.6

D.5

28.已知一棧的進(jìn)棧序列為：1234,則下列序列中不也許的出棧序列是()。

A.1234

B.4321

C.2143

D.4123

29.從未排序序列中依次取出一個(gè)元素與己排序序列中的元素依次進(jìn)行比較,然后將其放在已

排序序列的合適位置,該排序方法稱為()排序法。

A.插入

B.選擇

C.互換

D.二路歸并

30.若某線性表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采

用哪一種存儲(chǔ)結(jié)構(gòu)算法的時(shí)間效率最高？()

A.單鏈表

B.給出表頭指針的單循環(huán)鏈表

C.雙向鏈表

D.給出表尾指針的雙向循環(huán)鏈表

31.順序查找適合于存儲(chǔ)結(jié)構(gòu)為()的查找表。

A.壓縮存儲(chǔ)

B.散列存儲(chǔ)

C.索引存儲(chǔ)

D.順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)

32.向一個(gè)棧頂指針為HS的鏈棧中將一個(gè)S指針?biāo)傅慕Y(jié)點(diǎn)入棧,執(zhí)行()。

A.IIS->next=s

B.S->next=HS—>next;HS->next=s

C.S->next=HS;IIS=s

D.S->next=HS;HS=HS->next

33.一個(gè)n*n對(duì)稱矩陣,假如以行或列為主序存入內(nèi)存,則其容量為0。

A.n*n

B.n*n/2

C.n*(n+1)/2

D.(n+l)*(n+l)/2

34.用鏈接方式存儲(chǔ)的隊(duì)列,在進(jìn)行插入運(yùn)算時(shí)()。

A.僅修改頭指針

B.頭、尾指針都要修改

C.僅修改尾指針

D.頭、尾指針也許都要修改

35.某二叉樹的前序遍歷序列為abdgcefh,中序遍歷序列為dgbaechf,則其后序遍歷序列為

()。

A.bdgecefha

B.gdbecfha

C.bdgaechf

D.gdbehfca

36.下述幾種排序方法中，平均查找長(zhǎng)度最小的是()。

A.插入排序

B.選擇排序

C.快速排序

D.歸并排序

37.關(guān)鍵途徑是指A0E（ActivityOnEdge）網(wǎng)中（）。

A.最長(zhǎng)的回路

B.最短的回路

C.從源點(diǎn)到匯點(diǎn)（結(jié)束頂點(diǎn)）的最長(zhǎng)途徑

D.從源點(diǎn)到匯點(diǎn)（結(jié)束頂點(diǎn)）的最短途徑

38.一個(gè)棧的入棧序列是ab