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

一、單選題（共４０道試題，共10０分。)Ｖ１.３個(gè)結(jié)點(diǎn)的無向完全連通圖至少有()條邊。A.3B.4Ｃ.５D.6２．設(shè)有一個(gè)二維數(shù)Ａ[m][n］,以行序?yàn)橹餍虼鎯?chǔ)。假設(shè)A［0］［0]存放位置在6４4(10）,A[2］［2]存放位置在６7６（10),每個(gè)元素占一個(gè)空間,則Ａ[4][5]在()位置，(１0)表白用10進(jìn)數(shù)表達(dá)。Ａ.６9２(10）B.626(10)C.709(10）Ｄ.7２4(1０）3.具有ｎ個(gè)頂點(diǎn)的有向完全圖有()條弧。A．nB.ｎ*(ｎ-1）C．n＊(n+1)D.n*n４.隊(duì)列的操作特點(diǎn)是（)。A.先進(jìn)先出B.后進(jìn)先出C.先進(jìn)后出D.只能從隊(duì)尾出隊(duì)５.一個(gè)棧的入棧序列是ａbcde，則棧的不也許的輸出序列是(）。A.edcbaB．decbaC．dceabD．a(chǎn)bcdｅ6．某二叉樹的前序和后序序列正好相同，則該二叉樹一定是()的二叉樹。A.空或只有一個(gè)結(jié)點(diǎn)B.高度等于其結(jié)點(diǎn)數(shù)C.任一結(jié)點(diǎn)無左孩子Ｄ.任一結(jié)點(diǎn)無右孩子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è)無向連通圖的最小生成樹()。Ａ．只有一棵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)1０．線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí),結(jié)點(diǎn)的存儲(chǔ)地址（)A.必須是不連續(xù)的B.連續(xù)與否均可C.必須是連續(xù)的D.和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)11．一棵高度（假定樹根結(jié)點(diǎn)為第０層)為4的完全二叉樹中的結(jié)點(diǎn)數(shù)最少為（)。A．15Ｂ．16C.1７D.3１12.順序查找適合于存儲(chǔ)結(jié)構(gòu)為()的查找表。A.壓縮存儲(chǔ)B.散列存儲(chǔ)C.索引存儲(chǔ)D.順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)１3.設(shè)連通圖Ｇ中的邊集E={（a,b），(a,e）,(a，c)，(b，e)，(ｅ,ｄ),(d,ｆ)，(ｆ,ｃ)}，則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為(）A．a(chǎn)bedfcB.ａｃfeｂdC.aebdfｃD.aedｆcb１4.評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)重要是()。A．執(zhí)行時(shí)間Ｂ.輔助空間C.算法自身的復(fù)雜度D.執(zhí)行時(shí)間和所需的輔助空間１5．根據(jù)二叉樹的定義可知二叉樹共有（)種不同的形態(tài)。A．4Ｂ．5C.6D.7１6．在一棵具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（)。A.31B.32C.3３Ｄ．1６1７．從1０00個(gè)元素中選出其中五個(gè)最大值元素()排序最適合。A.冒泡B.快速排序Ｃ.堆排序Ｄ.選擇排序18.快速排序?qū)儆谀欠N排序類型()。A.選擇排序B.插入排序C.互換排序D．基數(shù)排序１９.下列排序算法中，其中(）是穩(wěn)定的。Ａ.堆排序,冒泡排序B．快速排序，堆排序C．直接選擇排序，希爾排序Ｄ.歸并排序,冒泡排序２0.在有序表(3,8,１３,１５,16,17,２1，2４,45）中,用二分查找法查找關(guān)鍵字21，所需進(jìn)行關(guān)鍵字比較的次數(shù)為（)。A.2B.3Ｃ.４Ｄ．52１.數(shù)據(jù)結(jié)構(gòu)重要研究(）。Ａ.數(shù)據(jù)的邏輯結(jié)構(gòu)B.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C．?dāng)?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*nB．ｎ*n/2C.n*（n+１）/2Ｄ.（ｎ+1)*（n+1)/２２3.對(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í)()。Ａ.僅修改頭指針Ｂ．頭、尾指針都要修改Ｃ.僅修改尾指針D．頭、尾指針也許都要修改25.線性鏈表是通過（)方式表達(dá)元素之間的關(guān)系A(chǔ)．后繼元素地址B.元素的存儲(chǔ)順序C.左、右孩子地址D.元素的相對(duì)存儲(chǔ)位置2６．某二叉樹的前序遍歷序列為abｄｇcefｈ，中序遍歷序列為ｄgbaｅｃhf,則其后序遍歷序列為()。A．ｂdｇecｅfｈaB．gｄbｅcfhaC．bdｇaecｈｆD.gdbehfcａ27．下列不屬于?；具\(yùn)算的是()。Ａ.入棧Ｂ.刪除棧底元素C．判斷棧是否為空D．建立一個(gè)空棧28.快速排序方法在（)情況下最不利于發(fā)揮其長(zhǎng)處。A．被排序的數(shù)據(jù)量太大B.被排序數(shù)據(jù)中具有多個(gè)相同值C．被排序數(shù)據(jù)已基本有序D.被排序數(shù)據(jù)數(shù)目為奇數(shù)2９.具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是()A．赫夫曼樹B.棧C.圖D.樹30.具有6５個(gè)結(jié)點(diǎn)的完全二叉樹其深度為(根的層次號(hào)為1)(）。Ａ.８Ｂ.7C．6D.531．假如結(jié)點(diǎn)a有三個(gè)兄弟,并且b為a的雙親，則b的度為（)。A.3Ｂ.4C.5D.23２.在表達(dá)式求值算法中，需要用()個(gè)棧？Ａ.０B.1Ｃ.２D.３３３.二分查找(又稱折半查找）規(guī)定查找表中的記錄按關(guān)鍵字()。Ａ.有序Ｂ．無序C.既可有序也可無序３4．下列關(guān)于AOE網(wǎng)的敘述中，不對(duì)的的是（)。Ａ.關(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ǔ)Ｂ.以鏈接方式存儲(chǔ)C．以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列D.以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列3６．以下不穩(wěn)定的排序方法是()A.直接插入排序B.冒泡排序Ｃ.直接選擇排序D.二路歸并排序37.下列存儲(chǔ)表達(dá)中，哪一個(gè)不是樹的存儲(chǔ)形式（)。Ａ.雙親表達(dá)法B.孩子鏈表表達(dá)法Ｃ.順序存儲(chǔ)表達(dá)法D．孩子兄弟表達(dá)法３8.中序遍歷一棵二叉排序樹所得到的結(jié)點(diǎn)序列是鍵值的()序列。A.遞增或遞減B．遞減Ｃ.遞增D.無序3９.對(duì)哈希（HＡSH)函數(shù)Ｈ(k)＝kMODm,一般來說,m應(yīng)取(）。A．素?cái)?shù)B.很大的數(shù)C.偶數(shù)D.奇數(shù)４0.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種()的存儲(chǔ)結(jié)構(gòu)。Ａ．隨機(jī)存取B.順序存?。?索引存取D.散列存取一、單選題（共40道試題，共1０0分。)V1．線性鏈表是通過(）方式表達(dá)元素之間的關(guān)系Ａ.后繼元素地址B．元素的存儲(chǔ)順序C.左、右孩子地址D．元素的相對(duì)存儲(chǔ)位置2.n個(gè)頂點(diǎn)的連通圖至少有（)條邊。A.n－1B.ｎＣ.ｎ＋1D．０3.在一個(gè)長(zhǎng)度為ｎ的順序線性表中順序查找值為x的元素時(shí),查找成功時(shí)的平均查找長(zhǎng)度(即ｘ與元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等)為（).Ａ.nB.n/2Ｃ.（n+１)/2D．（n-1)／24.下列存儲(chǔ)表達(dá)中，哪一個(gè)不是樹的存儲(chǔ)形式()。A.雙親表達(dá)法B.孩子鏈表表達(dá)法C.順序存儲(chǔ)表達(dá)法Ｄ．孩子兄弟表達(dá)法５.對(duì)線性表進(jìn)行二分查找時(shí)，規(guī)定線性表必須()。A．以順序方式存儲(chǔ)Ｂ.以鏈接方式存儲(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.２n-１B．n+１Ｃ.ｎ-1D．２n＋１8.當(dāng)待排序列基本有序時(shí),下列排序方法中()最佳。A．直接插入排序Ｂ.快速排序C．堆排序Ｄ.歸并排序9．長(zhǎng)度為２56的表,采用分塊查找,每塊最佳長(zhǎng)度為(）。Ａ.１4B.16C．１8D.261０．假如結(jié)點(diǎn)a有三個(gè)兄弟,并且b為a的雙親，則ｂ的度為()。A．3B.４C.5D．２11．采用順序搜索方法查找長(zhǎng)度為n的順序表時(shí),搜索成功的平均搜索長(zhǎng)度為（)。A.nB.n/2Ｃ．（n－1)/2D.（n+1)/2１2.鑒定一個(gè)隊(duì)列Ｑ(最多元素為m0)為滿隊(duì)列的條件是(）A.rear－fｒoｎt=＝m0Ｂ.rｅar-front－１＝＝ｍ０C.front==reaｒＤ.ｆront==rear+1１3.具有n個(gè)頂點(diǎn)的有向完全圖有()條弧。A．ｎB.n*（ｎ-1)C.n*（ｎ+1）Ｄ.n*ｎ１4.具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是(）A.赫夫曼樹B.棧Ｃ．圖D.樹１5.若構(gòu)造一棵具有n個(gè)結(jié)點(diǎn)的二叉排序樹,最壞情況下,其深度不會(huì)超過(）。Ａ.n／2B.nC．（n+１)/２Ｄ.ｎ+1１6.以下不穩(wěn)定的排序方法是（)A．直接插入排序B.冒泡排序C.直接選擇排序D.二路歸并排序17．設(shè)有５０行60列的二維數(shù)組A[50］[６０]，其元素長(zhǎng)度為４字節(jié)，按行優(yōu)先順序存儲(chǔ)，基地址為２00,則元素Ａ［18］[25]的存儲(chǔ)地址為()。A.３700B.4３７6C．３900D.４62018.從1００0個(gè)元素中選出其中五個(gè)最大值元素()排序最適合。A.冒泡B.快速排序C.堆排序D．選擇排序１9.以下關(guān)于線性表的說法不對(duì)的的是(）。A.線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型B.線性表中包含的數(shù)據(jù)元素個(gè)數(shù)不是任意的Ｃ．線性表中的每個(gè)結(jié)點(diǎn)都有且只有一個(gè)直接前趨和直接后繼D．存在這樣的線性表:表中各結(jié)點(diǎn)都沒有直接前趨和直接后繼20.設(shè)有7000個(gè)無序的元素,希望用最快的速度挑選出其中前5個(gè)最大的元素,最佳選用()法。A.冒泡排序B.快速排序C.堆排序D.基數(shù)排序21.（)是ＨＡＳH查找的沖突解決方法。A.求余法B.平方取中法C.二分法D.開放定址法２2.評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)重要是（)。A.執(zhí)行時(shí)間B.輔助空間C.算法自身的復(fù)雜度D.執(zhí)行時(shí)間和所需的輔助空間23.快速排序?qū)儆谀欠N排序類型()。Ａ.選擇排序B.插入排序Ｃ.互換排序Ｄ.基數(shù)排序24．隊(duì)列的操作特點(diǎn)是()。Ａ.先進(jìn)先出B.后進(jìn)先出C.先進(jìn)后出D.只能從隊(duì)尾出隊(duì)25.稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即()。A．二維數(shù)組和三維數(shù)組B.三元組表和散列表Ｃ．三元組表和十字鏈表D．散列表和十字鏈表26.一棵高度（假定樹根結(jié)點(diǎn)為第0層）為4的完全二叉樹中的結(jié)點(diǎn)數(shù)最少為()。A.１５Ｂ.16C.17D.3127.具有65個(gè)結(jié)點(diǎn)的完全二叉樹其深度為(根的層次號(hào)為1)（)。A.8B.7C.６D.5２8.已知一棧的進(jìn)棧序列為:1２3４,則下列序列中不也許的出棧序列是()。Ａ.１234B.4３21C.2143D.41２329.從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較,然后將其放在已排序序列的合適位置,該排序方法稱為()排序法。A.插入Ｂ.選擇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.雙向鏈表Ｄ.給出表尾指針的雙向循環(huán)鏈表31.順序查找適合于存儲(chǔ)結(jié)構(gòu)為（)的查找表。A.壓縮存儲(chǔ)Ｂ.散列存儲(chǔ)C.索引存儲(chǔ)D.順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)32.向一個(gè)棧頂指針為HS的鏈棧中將一個(gè)S指針?biāo)傅慕Y(jié)點(diǎn)入棧,執(zhí)行(）。Ａ.HＳ->next=sB.Ｓ->ｎexｔ=HＳ－＞neｘt;HS->next=sC．S->ｎext＝HS;HＳ＝ｓD.S->next=HS;HS＝HS->nexｔ3３.一個(gè)n*n對(duì)稱矩陣,假如以行或列為主序存入內(nèi)存,則其容量為（)。Ａ.n*nB.n＊n/2Ｃ.n*（n+１）/2Ｄ.(n+1)*(n+1)/2３４.用鏈接方式存儲(chǔ)的隊(duì)列,在進(jìn)行插入運(yùn)算時(shí)()。A．僅修改頭指針B.頭、尾指針都要修改Ｃ．僅修改尾指針D.頭、尾指針也許都要修改35.某二叉樹的前序遍歷序列為abdgｃefh,中序遍歷序列為dgbaecｈf，則其后序遍歷序列為()。A.bｄgｅｃeｆhaB.gdbecfhaC.ｂdgａechfD．gdbｅhfca36．下述幾種排序方法中，平均查找長(zhǎng)度最小的是()。A.插入排序Ｂ.選擇排序Ｃ.快速排序D.歸并排序37．關(guān)鍵途徑是指ＡＯE(ＡｃtivitｙOnEｄｇe)網(wǎng)中（）。Ａ.最長(zhǎng)的回路B.最短的回路C．從源點(diǎn)到匯點(diǎn)（結(jié)束頂點(diǎn))的最長(zhǎng)途徑D.從源點(diǎn)到匯點(diǎn)(結(jié)束頂點(diǎn))的最短途徑38.一個(gè)棧的入棧序列是aｂｃde，則棧的不也許的輸出序列是()。A.ｅdcbaB.ｄecbaC.dceaｂＤ.ａbcdｅ39．棧是一種(）的數(shù)據(jù)結(jié)構(gòu)。A．存取受限的線性結(jié)構(gòu)B.存取不受限的線性結(jié)構(gòu)C.存取受限的非線性結(jié)構(gòu)D.存取不受限的非線性結(jié)構(gòu)40．有一個(gè)有序表為{1,3,9,12，3２,41,45，62,75，77,８2,９５,100｝,當(dāng)采用折半查找值為82的節(jié)點(diǎn)時(shí)，()次比較后查找成功。A.1B.2C．4D.8一、單選題(共4０道試題，共100分。）V1.若一個(gè)具有n個(gè)結(jié)點(diǎn)、k條邊的非連通無