2023年408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)考研真題答案及解析

本文提供2023年408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)考研真題答案及解析，以下為具體內(nèi)容

1、下列對(duì)順序存儲(chǔ)的有序表（長(zhǎng)度為n）實(shí)現(xiàn)給定操作的算法中平均時(shí)間復(fù)雜度為O(1)的是（ ）。

A、查找包含指定值元素的值

B、插入包含指定值元素的算法

C、刪除第i個(gè)元素的算法

D、獲取第i個(gè)值的算法

2、現(xiàn)有非空雙向鏈表L，其結(jié)點(diǎn)結(jié)構(gòu)為prer是指向直接前驅(qū)結(jié)點(diǎn)的指針，next是指向直接后繼結(jié)點(diǎn)的指針。若要在L中指針p所指向的結(jié)點(diǎn)（非尾結(jié)點(diǎn)）之后插入指針s指向的新結(jié)點(diǎn)，則在執(zhí)行了語(yǔ)句序列：“s->next=p->next;p->next=s;”，后，還要執(zhí)行（ ）。

A、s->next->prer=p;s->prer=p;

B、p->next->prer=s;s->prer=p;

C、s->prer=s->next->prer;s->next->prer=s;

D、p->next->prer=s->prer;s->next->prer=p;

3、若采用三元組表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)稀疏矩陣M，則除三元組外，下列數(shù)據(jù)中還需要保存的是（ ）。I.M的行數(shù)II.M中包含非零元素的行數(shù)III.M的列數(shù)IV.M中包含非零元素的列數(shù)

A、僅I、III

B、僅I、II

C、僅III、IV

D、I、II、III、IV

4、在有6個(gè)字符組成的字符集S中，各個(gè)字符出現(xiàn)的頻次分別為3，4，5，6，8，10，為S構(gòu)造的哈夫曼樹(shù)的加權(quán)平均長(zhǎng)度為（ ）。

A、2.4

B、2.5

C、2.67

D、2.75

5、已知一棵二叉樹(shù)的樹(shù)形如圖，若其后序遍歷為f，d，b，e，c，a，則其先序列為（ ）。

A、aedfbc

B、acebdf

C、cabefd

D、dfebac

6、已知無(wú)向連通圖G中各邊的權(quán)值均為1，下列算法中一定能夠求出圖G中從某頂點(diǎn)到其余各個(gè)頂點(diǎn)最短路徑的是（ ）。I.普利姆算法II.克魯斯卡爾算法III.圖的廣度優(yōu)先搜索

A、僅III

B、僅I、II

C、僅I、III

D、I、II、III

7、下列關(guān)于非空B樹(shù)的敘述中，正確的是（ ）。I.插入操作可能增加樹(shù)的高度II.刪除操作一定會(huì)導(dǎo)致葉結(jié)點(diǎn)的變化III.查找某關(guān)鍵字一定是要查找到葉結(jié)點(diǎn)IV.插入的新關(guān)鍵字最終位于葉結(jié)點(diǎn)中

A、僅I

B、僅I、II

C、僅III、IV

D、僅I、II、IV

8、對(duì)含有600個(gè)元素的有序順序表進(jìn)行折半查找，關(guān)鍵字之間的比較次數(shù)最多是（ ）。

A、9

B、10

C、30

D、300

9、現(xiàn)有長(zhǎng)度為5，初始為空的散列表HT，散列表函數(shù)H（K）=（k+4）%5，用線(xiàn)性探查再散列法解決沖突。若將關(guān)鍵字序列2022，12，25依次插入HT中，然后刪除關(guān)鍵字25，則HT中查找失敗的平均查找長(zhǎng)度（ ）。

A、1

B、1.6

C、1.8

D、2.2