事業(yè)單位招錄計(jì)算機(jī)專(zhuān)業(yè)知識(shí)（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷2

事業(yè)單位招錄計(jì)算機(jī)專(zhuān)業(yè)知識(shí)（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷2一、單項(xiàng)選擇題(本題共23題，每題1.0分，共23分。)1、下列文件的物理結(jié)構(gòu)中，不利于文件長(zhǎng)度動(dòng)態(tài)增長(zhǎng)的文件物理結(jié)構(gòu)是()。A、順序結(jié)構(gòu)B、鏈?zhǔn)浇Y(jié)構(gòu)C、索引結(jié)構(gòu)D、Hash結(jié)構(gòu)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：順序結(jié)構(gòu)又稱(chēng)連續(xù)結(jié)構(gòu)。這是一種最簡(jiǎn)單的物理結(jié)構(gòu)，它把邏輯上連續(xù)的文件信息依次存放在連續(xù)編號(hào)的物理塊中，只要知道文件在存儲(chǔ)設(shè)備上的起始地址(首塊號(hào))和文件長(zhǎng)度(總塊數(shù))，就能很快地進(jìn)行存取。這種結(jié)構(gòu)的優(yōu)點(diǎn)是訪問(wèn)速度快，缺點(diǎn)是文件長(zhǎng)度增加困難。因此，順序結(jié)構(gòu)的磁盤(pán)空間利用率不高，不利于文件長(zhǎng)度動(dòng)態(tài)增長(zhǎng)。2、若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為()。A、1和5B、2和4C、4和2D、5和1標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：循環(huán)隊(duì)列是解決假溢出的問(wèn)題，通常把一維數(shù)組看成首尾相接。在循環(huán)意義下的加1運(yùn)算通常用求模運(yùn)算來(lái)實(shí)現(xiàn)。所以入隊(duì)和出隊(duì)時(shí)的操作分別為：Fear＝(rear＋1)％m，front＝(front＋1)％m。3、設(shè)森林F中有三棵樹(shù)，第一、第二、第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為M1、M2、和M3，與森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是多少()。A、M1B、M1＋M2C、M3D、M2＋M3標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：第一棵樹(shù)構(gòu)成根和左子樹(shù)，因此右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)就是M2＋M3，故D為正確答案。4、由圈權(quán)值為9．2．5．7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一顆哈夫曼樹(shù)，該樹(shù)的帶權(quán)路徑長(zhǎng)度為()。A、23B、37C、44D、46標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：如圖最終的帶權(quán)路徑長(zhǎng)度為9＋7＊2＋2＊3＋5＊3＝44。5、樹(shù)形結(jié)構(gòu)的特點(diǎn)是：一個(gè)結(jié)點(diǎn)可以有()。A、多個(gè)直接前驅(qū)B、多個(gè)直接后繼C、多個(gè)前D、一個(gè)后繼標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：樹(shù)的唯一根節(jié)點(diǎn)無(wú)前驅(qū)，葉子結(jié)點(diǎn)可以有多個(gè)且無(wú)后繼，樹(shù)的其他結(jié)點(diǎn)可以有多個(gè)后繼但只能有一個(gè)前驅(qū)。6、下面敘述正確的是()。A、二叉樹(shù)是特殊的樹(shù)B、二叉樹(shù)等價(jià)于度為2的樹(shù)C、完全二叉樹(shù)必為滿(mǎn)二叉樹(shù)D、二叉樹(shù)的左右子樹(shù)有次序之分標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：二叉樹(shù)是一類(lèi)與樹(shù)不同的數(shù)據(jù)結(jié)構(gòu)。兩者的區(qū)別在于：二叉樹(shù)可以是空集；二叉樹(shù)的任一結(jié)點(diǎn)都有兩棵子樹(shù)，并且這兩棵子樹(shù)之間有次序關(guān)系，也就是說(shuō)，它們的位置不能交換。7、如果一棵二叉樹(shù)結(jié)點(diǎn)的先根遍歷序列是A、B、C，后根遍歷序列是C、B、A，則該二叉樹(shù)結(jié)點(diǎn)的中根遍歷序列()。A、必為A、B、CB、必為A、C、BC、必為B、C、AD、不能確定標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：通常根據(jù)先根遍歷序列和后根遍歷序列不能確定一棵樹(shù)。如下圖先根遍歷序列是①、②、③，后根遍歷序列是③、②、①。8、已知二叉樹(shù)的前序序列為ABCDEFG，中序序列為DBCAFEG，則后序序列為()。A、DCBAFGEB、DCBFGEAC、DCBFEGAD、DCBGFEA標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：本題考查的是二叉樹(shù)的遍歷過(guò)程。在本題中，由于前序遍歷首先訪問(wèn)的是根結(jié)點(diǎn)，所以根結(jié)點(diǎn)是A，又由于后序遍歷最后訪問(wèn)的是根結(jié)點(diǎn)，所以排除選項(xiàng)A；根據(jù)中序序列知道，DBC是左子樹(shù)的結(jié)點(diǎn)，F(xiàn)EG是右子樹(shù)的結(jié)點(diǎn)。9、以下數(shù)據(jù)結(jié)構(gòu)中，屬于非線性數(shù)據(jù)結(jié)構(gòu)的是()。A、樹(shù)B、隊(duì)列C、棧D、字符串標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的有序(次序)集合。它有四個(gè)基本特征：(1)集合中必存在唯一的一個(gè)“第一個(gè)元素”；(2)集合中必存在唯一的一個(gè)“最后的元素”；(3)除最后元素之外，其它數(shù)據(jù)元素均有唯一的“后繼”；(4)除第一元素之外，其它數(shù)據(jù)元素均有唯一的“前撲”。數(shù)據(jù)結(jié)構(gòu)中線性結(jié)構(gòu)指的是數(shù)據(jù)元素之間存在著“一對(duì)一”的線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)。線性結(jié)構(gòu)包括線性表(如結(jié)構(gòu)體數(shù)組，結(jié)構(gòu)體鏈表)、一維數(shù)組、字符串、堆棧、隊(duì)列。10、無(wú)向圖G＝(V，E)，其中V＝{a,b,c,d,e,f}，E＝{(a,b)，(a,e)，(a，c)，(b，e)，(c，f)，(e，d)}，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是()。A、a，b，e，c，d，fB、a，c，f，e，b，dC、a，e，b，c，f，dD、a，e，d，f，c，b標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：假設(shè)給定圖G的初態(tài)是所有頂點(diǎn)均未曾訪問(wèn)過(guò)。在G中任選一頂點(diǎn)v為初始出發(fā)點(diǎn)(源點(diǎn))，則深度優(yōu)先遍歷可定義如下：首先訪問(wèn)出發(fā)點(diǎn)v，并將其標(biāo)記為已訪問(wèn)過(guò)；然后依次從v出發(fā)搜索v的每個(gè)鄰接點(diǎn)w。若w未曾訪問(wèn)過(guò)，則以w為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先遍歷，直至圖中所有和源點(diǎn)v有路徑相通的頂點(diǎn)(亦稱(chēng)為從源點(diǎn)可達(dá)的頂點(diǎn))均已被訪問(wèn)為止。若此時(shí)圖中仍有未訪問(wèn)的頂點(diǎn)，則另選一個(gè)尚未訪問(wèn)的頂點(diǎn)作為新的源點(diǎn)重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)均已被訪問(wèn)為止。11、對(duì)于具有n個(gè)頂點(diǎn)、6條邊的圖()。A、采用鄰接矩陣表示圖時(shí)，查找所有頂點(diǎn)的鄰接頂點(diǎn)的時(shí)間復(fù)雜度為O(n2)B、進(jìn)行廣度優(yōu)先遍歷運(yùn)算所消耗的時(shí)間與采用哪一種存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)C、采用鄰接表表示圖時(shí)，查找所有頂點(diǎn)的鄰接頂點(diǎn)的時(shí)間復(fù)雜度為O(n＊e)D、進(jìn)行深度優(yōu)先遍歷運(yùn)算所消耗的時(shí)間與采用哪一種存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：設(shè)某有向圖和無(wú)向圖如下所示。下面的矩陣A是該有向圖的鄰接矩陣，B為無(wú)向圖的鄰接矩陣。上面有向圖的鄰接鏈表如下圖所示。圖的遍歷運(yùn)算是按照某種策略訪問(wèn)圖中的每一個(gè)頂點(diǎn)，實(shí)質(zhì)上是通過(guò)邊或弧找鄰接點(diǎn)的過(guò)程，因此廣度優(yōu)先搜索遍歷圖和深度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度相同，其不同之處僅僅在于對(duì)頂點(diǎn)訪問(wèn)的次序不同。12、用鄰接矩陣A表示圖，判定任意兩個(gè)頂點(diǎn)Vi和Vj之間是否有長(zhǎng)度m路徑相連，則只要檢查()的第i行和第j列的元素是否為零即可。A、mAB、AC、AmD、Am－1標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：要判斷相鄰矩陣A中任意兩個(gè)頂點(diǎn)Vi和Vj之間是否有長(zhǎng)度為m的路徑相連，只要檢查Am的第i行第j的元素是否為0即可，若為0則無(wú)，否則就存在。13、在向圖的鄰接矩陣表示中，計(jì)算第i個(gè)頂點(diǎn)八度的方法是()。A、第i行非零元素個(gè)數(shù)B、第i列非零元素個(gè)數(shù)C、第i行零元素個(gè)數(shù)D、第i列零元素個(gè)數(shù)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：先用一個(gè)二維數(shù)組Edge存儲(chǔ)表示鄰接矩陣，輸入文件中頂點(diǎn)的序號(hào)是從1開(kāi)始，當(dāng)輸入一條有向邊＜u，v＞時(shí)，將Edge[u－1][v－1]＝1即可；第i＋1個(gè)頂點(diǎn)的出度等于鄰接矩陣中第i行所有元素中元素值為1的個(gè)數(shù)，把第i行所有元素值累加起來(lái)，得到的結(jié)果也是該頂點(diǎn)的出度，同理，在計(jì)算第i＋1個(gè)頂點(diǎn)的入度時(shí)，也只需要將第i列所有元素值累加起來(lái)即可。14、有種關(guān)系模式R＝＜U，F(xiàn)＞，U＝{C，T，H，X，S}，F(xiàn)＝{C→T，(H，X)→C，(H，T)→YC，(H，S)→Y}則表示模式R的碼是()。A、CB、(H，S)C、(H，Y)D、(H，T)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：由題可得如下推導(dǎo)：(H，S)＋R，(H，R)＋C，C－－4T，(H，T)－－4R，故可知(H，S)為關(guān)系模式的碼。15、在UML提供的圖中，用于按時(shí)間順序描述對(duì)象間交互的是()。A、類(lèi)圖B、狀態(tài)圖C、序列圖D、用例圖標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：暫無(wú)解析16、n個(gè)頂點(diǎn)的連通圖至少有多少條邊()。A、n－1B、nC、n＋1D、0標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：至少要有(n－1)條邊(也就是樹(shù))才能保證圖為連通圖。17、下列說(shuō)法中不正確的是()。A、圖的遍歷過(guò)程中每一頂點(diǎn)僅被訪問(wèn)一次B、遍歷圖的基本方法有深度優(yōu)先搜索和廣度優(yōu)先搜索兩種C、圖的深度優(yōu)先搜索的方法不適用于有向圖D、圖的深度優(yōu)先搜索是一個(gè)遞歸過(guò)程標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：圖的深度優(yōu)先搜索的方法對(duì)于有向圖和無(wú)向圖都適用。18、在有向圖中，所有頂點(diǎn)的度數(shù)之和是所有邊數(shù)的()倍。A、0．5B、1C、2D、4標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：在有向圖中，所有頂點(diǎn)的度數(shù)之和是所有邊數(shù)的2倍，因?yàn)橐粭l邊的兩個(gè)端點(diǎn)具有兩個(gè)“度”。19、在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度數(shù)之和為S，則所有頂點(diǎn)的人度數(shù)之和為()。A、SB、S－1C、S＋1D、n標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：圖的所有頂點(diǎn)的出度數(shù)之和等于所有頂點(diǎn)的入度數(shù)之和。故本題選A。20、表達(dá)式3＊2＾(4＊2＊2－6＊3)－5求值過(guò)程中當(dāng)掃描到6時(shí)，對(duì)象棧和算符棧為()，其中＾為乘冪。A、3,2,4,1,1；＊＾(＋＊－B、3,2,8；＊＾－C、3,2,4,2,2；＊＾(－D、3,2,8；＊＾(－標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：第一次：對(duì)象棧：3；算符棧：＊；第二次：對(duì)象棧：3，2；算符棧：＊，＾，(；第三次：對(duì)象棧：3，2，4；算符棧：＊，＾，(，＋；第四次：對(duì)象棧：3，2，4，2；算符棧：＊，＾，(，＋，＊；第五次：對(duì)象棧：3，2，4，4；算符棧：＊，＾，(，＋；第六次(掃描到6)：對(duì)象棧：3，2，8；算符棧：＊，＾，(，－21、從一個(gè)具有N個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于X結(jié)點(diǎn)時(shí)，查找成功的情況下，需平均比較()結(jié)點(diǎn)。A、NB、N／2C、(N－1)／2D、(N＋1)／2標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：x等于第一個(gè)元素的值。則要比較1次x等于第二個(gè)元素的值，則要比較2次x值剛好等于第n個(gè)元素，則要比較x次所以總次數(shù)是1＋2＋3＋……＋n－1＋n＝(n＋1)＊n／2所以平均需要：(n＋1)／2次。22、算法指的是()。A、計(jì)算機(jī)程序B、解決問(wèn)題的計(jì)算方法C、排序算法D、解決問(wèn)題的有限運(yùn)算序列標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：算法是精確定義的一系列規(guī)則，它指出怎樣從給定的輸入信息經(jīng)過(guò)有限步驟產(chǎn)生所求的輸出信息。它既不是計(jì)算機(jī)程序，也不是某種算術(shù)運(yùn)算。23、以下的算法設(shè)計(jì)中，哪一個(gè)是以獲取問(wèn)題最大優(yōu)解為目標(biāo)?()A、回溯法B、分治法C、動(dòng)態(tài)規(guī)則D、逆推標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：暫無(wú)解析二、簡(jiǎn)答題(本題共10題，每題1.0分，共10分。)24、在單鏈表上實(shí)現(xiàn)求線性表表長(zhǎng)的ListLength(L)運(yùn)算。標(biāo)準(zhǔn)答案：由于在單鏈表中只給出一個(gè)頭指針，所以只能用遍歷的方法來(lái)數(shù)點(diǎn)鏈表中的結(jié)點(diǎn)個(gè)數(shù)。算法描述如下：intListLength(LinkList＊L){／／求帶結(jié)點(diǎn)的單鏈表的表長(zhǎng)intlen＝0；LinkList＊p；p＝L；while(p－＞next!＝NULL){p＝p－＞next；len＋＋：}returnlen：}知識(shí)點(diǎn)解析：暫無(wú)解析25、什么是循環(huán)隊(duì)列?標(biāo)準(zhǔn)答案：用常規(guī)意義下順序存儲(chǔ)結(jié)構(gòu)的一維數(shù)組表示隊(duì)列，由于隊(duì)列的性質(zhì)(隊(duì)尾插入和隊(duì)頭刪除)，容易造成“假溢出”現(xiàn)象，即隊(duì)尾已到達(dá)一維數(shù)組的高下標(biāo)，不能再插入，然而隊(duì)中元素個(gè)數(shù)小于隊(duì)列的長(zhǎng)度(容量)。循環(huán)隊(duì)列是解決“假溢出”的一種方法。通常把一維數(shù)組看成首尾相接。在循環(huán)隊(duì)列下，通常采用“犧牲一個(gè)存儲(chǔ)單元”或“作標(biāo)記”的方法解決“隊(duì)滿(mǎn)”和“隊(duì)空”的判定問(wèn)題。知識(shí)點(diǎn)解析：暫無(wú)解析26、什么是隊(duì)列的上溢現(xiàn)象?一般有幾種解決方法，試簡(jiǎn)述之。標(biāo)準(zhǔn)答案：在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列的容量(即存儲(chǔ)的空間大小)為maxnum。當(dāng)有元素要加入隊(duì)列(即入隊(duì))時(shí)，若rear＝maxnum，則會(huì)發(fā)生隊(duì)列的上溢現(xiàn)象，此時(shí)就不能將該元素加入隊(duì)列。對(duì)于隊(duì)列，還有一種“假溢出”現(xiàn)象，隊(duì)列中尚余有足夠的空間，但元素卻不能入隊(duì)，一般是由于隊(duì)列的存儲(chǔ)結(jié)構(gòu)或操作方式的選擇不當(dāng)所致，可以用循環(huán)隊(duì)列解決。一般地，要解決隊(duì)列的上溢現(xiàn)象可有以下幾種方法：(1)可建立一個(gè)足夠大的存儲(chǔ)空間以避免溢出，但這樣做往往會(huì)造成空間使用率低，浪費(fèi)存儲(chǔ)空間。(2)要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決：①采用移動(dòng)元素的方法。每當(dāng)有一個(gè)新元素入隊(duì)，就將隊(duì)列中已有的元素向隊(duì)頭移動(dòng)一個(gè)位置，假定空余空間足夠。②每當(dāng)刪去一個(gè)隊(duì)頭元素，則可依次移動(dòng)隊(duì)列中的元素總是使front指針指向隊(duì)列中的第一個(gè)位置。③采用循環(huán)隊(duì)列方式。將隊(duì)頭、隊(duì)尾看作是一個(gè)首尾相接的循環(huán)隊(duì)列，即用循環(huán)數(shù)組實(shí)現(xiàn)，此時(shí)隊(duì)首仍在隊(duì)尾之前，作插入和刪除運(yùn)算時(shí)仍遵循“先進(jìn)先出”的原則。知識(shí)點(diǎn)解析：暫無(wú)解析27、樹(shù)、森林和二叉樹(shù)是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹(shù)、森林轉(zhuǎn)化為二叉樹(shù)的基本目的是什么，并指出樹(shù)和二叉樹(shù)的主要區(qū)別。標(biāo)準(zhǔn)答案：樹(shù)的孩子兄弟鏈表表示法和二叉樹(shù)二叉鏈表表示法，本質(zhì)是一樣的，只是解釋不同，也就是說(shuō)樹(shù)(樹(shù)是森林的特例，即森林中只有一棵樹(shù)的特殊情況)可用二叉樹(shù)唯一表示，并可使用二叉樹(shù)的一些算法去解決樹(shù)和森林中的問(wèn)題。樹(shù)和二叉樹(shù)的區(qū)別有三：一是，二叉樹(shù)的度至多為2，樹(shù)無(wú)此限制；二是，二叉樹(shù)有左右子樹(shù)之分，即使在只有一個(gè)分枝的情況下，也必須指出是左子樹(shù)還是右子樹(shù)，樹(shù)無(wú)此限制；三是，二叉樹(shù)允許為空，樹(shù)一般不允許為空。知識(shí)點(diǎn)解析：暫無(wú)解析28、一棵有n(n＞0)個(gè)結(jié)點(diǎn)的d度樹(shù)，若用多重鏈表表示，樹(shù)中每個(gè)結(jié)點(diǎn)都有d個(gè)鏈域，則在表示該樹(shù)的多重鏈表中有多少個(gè)空鏈域?為什么?標(biāo)準(zhǔn)答案：n(n＞0)個(gè)結(jié)點(diǎn)的d度樹(shù)共有nd個(gè)鏈域，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均有一個(gè)指針?biāo)?，故該?shù)的空鏈域有nd－(n－1)＝n(d－1)＋1個(gè)。知識(shí)點(diǎn)解析：暫無(wú)解析29、已知一棵二叉樹(shù)的中序序列和后序序列分別為DBEAFIHCG和DEBHIFGCA，畫(huà)出這棵二叉樹(shù)。標(biāo)準(zhǔn)答案：知識(shí)點(diǎn)解析：暫無(wú)解析30、設(shè)一棵二叉樹(shù)的先序、中序遍歷序列分別為先序遍歷序列：ABDFCEGH，中序遍歷序列：BFDAGEHC。(1)畫(huà)出這棵二叉樹(shù)。(2)將這棵二叉樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的樹(shù)。標(biāo)準(zhǔn)答案：知識(shí)點(diǎn)解析：暫無(wú)解析31、編寫(xiě)一個(gè)算法，求出鄰接矩陣表示的無(wú)向圖中序號(hào)為numb的頂點(diǎn)的度數(shù)。標(biāo)準(zhǔn)答案：intdegreel(Graph＆ga，intnumb){／／根據(jù)無(wú)向圖的鄰接矩陣求出序號(hào)為numb的頂點(diǎn)的度數(shù)intj，d＝0；for(j＝0；j＜ga．vexnum；j＋＋)if(ga．cost[numb][j]!＝0＆＆ga．cost[numb][j]!＝MAXINT)d＋＋；returnd：}知識(shí)點(diǎn)解析：暫無(wú)解析32、設(shè)有一個(gè)長(zhǎng)度為S的字符串，其字符順序存放在一個(gè)一維數(shù)組的第1至第S個(gè)單元中(每個(gè)單元存放一個(gè)字符)?，F(xiàn)要求從此字符串的第m個(gè)字符以后刪除長(zhǎng)度為t的子串，m＜S，t＜(S－m)，并將刪除后的結(jié)果復(fù)制在該數(shù)組的第S單元以后的單元中，試設(shè)計(jì)此刪除算法。標(biāo)準(zhǔn)答案：算法描述為：intdelete(r，S，t，m)／／從字符串的第m個(gè)字符以后刪除長(zhǎng)度為t的子串{charr[]；intS，t，m；inti，j；for(i＝1；i＜＝m；i＋＋)r[S＋i]＝r[i]；for(j＝m＋t－i；j＜＝S；j＋＋)r[S－t＋j]＝r[j]；return(1)；}知識(shí)點(diǎn)解析：暫無(wú)解析33、已知一組記錄為{46，74，53，14，26，38，86，65，27，34}，給出采用歸并排序法進(jìn)行排序時(shí)每一趟的排序結(jié)果。標(biāo)準(zhǔn)答案：(0)[46][74][53][14][26][38][86][65][27][34](1)[4674][1453][2638][6586][2734](2)[14465374][26386586][2734](3)[1426384653657486][2734](4)[14262734384653657486]知識(shí)點(diǎn)解析：暫無(wú)解析一、單項(xiàng)選擇題(本題共23題，每題1.0分，共23分。)34、下列文件的物理結(jié)構(gòu)中，不利于文件長(zhǎng)度動(dòng)態(tài)增長(zhǎng)的文件物理結(jié)構(gòu)是()。A、順序結(jié)構(gòu)B、鏈?zhǔn)浇Y(jié)構(gòu)C、索引結(jié)構(gòu)D、Hash結(jié)構(gòu)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：順序結(jié)構(gòu)又稱(chēng)連續(xù)結(jié)構(gòu)。這是一種最簡(jiǎn)單的物理結(jié)構(gòu)，它把邏輯上連續(xù)的文件信息依次存放在連續(xù)編號(hào)的物理塊中，只要知道文件在存儲(chǔ)設(shè)備上的起始地址(首塊號(hào))和文件長(zhǎng)度(總塊數(shù))，就能很快地進(jìn)行存取。這種結(jié)構(gòu)的優(yōu)點(diǎn)是訪問(wèn)速度快，缺點(diǎn)是文件長(zhǎng)度增加困難。因此，順序結(jié)構(gòu)的磁盤(pán)空間利用率不高，不利于文件長(zhǎng)度動(dòng)態(tài)增長(zhǎng)。35、若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為()。A、1和5B、2和4C、4和2D、5和1標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：循環(huán)隊(duì)列是解決假溢出的問(wèn)題，通常把一維數(shù)組看成首尾相接。在循環(huán)意義下的加1運(yùn)算通常用求模運(yùn)算來(lái)實(shí)現(xiàn)。所以入隊(duì)和出隊(duì)時(shí)的操作分別為：Fear＝(rear＋1)％m，front＝(front＋1)％m。36、設(shè)森林F中有三棵樹(shù)，第一、第二、第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為M1、M2、和M3，與森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是多少()。A、M1B、M1＋M2C、M3D、M2＋M3標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：第一棵樹(shù)構(gòu)成根和左子樹(shù)，因此右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)就是M2＋M3，故D為正確答案。37、由圈權(quán)值為9．2．5．7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一顆哈夫曼樹(shù)，該樹(shù)的帶權(quán)路徑長(zhǎng)度為()。A、23B、37C、44D、46標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：如圖最終的帶權(quán)路徑長(zhǎng)度為9＋7＊2＋2＊3＋5＊3＝44。38、樹(shù)形結(jié)構(gòu)的特點(diǎn)是：一個(gè)結(jié)點(diǎn)可以有()。A、多個(gè)直接前驅(qū)B、多個(gè)直接后繼C、多個(gè)前D、一個(gè)后繼標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：樹(shù)的唯一根節(jié)點(diǎn)無(wú)前驅(qū)，葉子結(jié)點(diǎn)可以有多個(gè)且無(wú)后繼，樹(shù)的其他結(jié)點(diǎn)可以有多個(gè)后繼但只能有一個(gè)前驅(qū)。39、下面敘述正確的是()。A、二叉樹(shù)是特殊的樹(shù)B、二叉樹(shù)等價(jià)于度為2的樹(shù)C、完全二叉樹(shù)必為滿(mǎn)二叉樹(shù)D、二叉樹(shù)的左右子樹(shù)有次序之分標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：二叉樹(shù)是一類(lèi)與樹(shù)不同的數(shù)據(jù)結(jié)構(gòu)。兩者的區(qū)別在于：二叉樹(shù)可以是空集；二叉樹(shù)的任一結(jié)點(diǎn)都有兩棵子樹(shù)，并且這兩棵子樹(shù)之間有次序關(guān)系，也就是說(shuō)，它們的位置不能交換。40、如果一棵二叉樹(shù)結(jié)點(diǎn)的先根遍歷序列是A、B、C，后根遍歷序列是C、B、A，則該二叉樹(shù)結(jié)點(diǎn)的中根遍歷序列()。A、必為A、B、CB、必為A、C、BC、必為B、C、AD、不能確定標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：通常根據(jù)先根遍歷序列和后根遍歷序列不能確定一棵樹(shù)。如下圖先根遍歷序列是①、②、③，后根遍歷序列是③、②、①。41、已知二叉樹(shù)的前序序列為ABCDEFG，中序序列為DBCAFEG，則后序序列為()。A、DCBAFGEB、DCBFGEAC、DCBFEGAD、DCBGFEA標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：本題考查的是二叉樹(shù)的遍歷過(guò)程。在本題中，由于前序遍歷首先訪問(wèn)的是根結(jié)點(diǎn)，所以根結(jié)點(diǎn)是A，又由于后序遍歷最后訪問(wèn)的是根結(jié)點(diǎn)，所以排除選項(xiàng)A；根據(jù)中序序列知道，DBC是左子樹(shù)的結(jié)點(diǎn)，F(xiàn)EG是右子樹(shù)的結(jié)點(diǎn)。42、以下數(shù)據(jù)結(jié)構(gòu)中，屬于非線性數(shù)據(jù)結(jié)構(gòu)的是()。A、樹(shù)B、隊(duì)列C、棧D、字符串標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的有序(次序)集合。它有四個(gè)基本特征：(1)集合中必存在唯一的一個(gè)“第一個(gè)元素”；(2)集合中必存在唯一的一個(gè)“最后的元素”；(3)除最后元素之外，其它數(shù)據(jù)元素均有唯一的“后繼”；(4)除第一元素之外，其它數(shù)據(jù)元素均有唯一的“前撲”。數(shù)據(jù)結(jié)構(gòu)中線性結(jié)構(gòu)指的是數(shù)據(jù)元素之間存在著“一對(duì)一”的線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)。線性結(jié)構(gòu)包括線性表(如結(jié)構(gòu)體數(shù)組，結(jié)構(gòu)體鏈表)、一維數(shù)組、字符串、堆棧、隊(duì)列。43、無(wú)向圖G＝(V，E)，其中V＝{a,b,c,d,e,f}，E＝{(a,b)，(a,e)，(a，c)，(b，e)，(c，f)，(e，d)}，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是()。A、a，b，e，c，d，fB、a，c，f，e，b，dC、a，e，b，c，f，dD、a，e，d，f，c，b標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：假設(shè)給定圖G的初態(tài)是所有頂點(diǎn)均未曾訪問(wèn)過(guò)。在G中任選一頂點(diǎn)v為初始出發(fā)點(diǎn)(源點(diǎn))，則深度優(yōu)先遍歷可定義如下：首先訪問(wèn)出發(fā)點(diǎn)v，并將其標(biāo)記為已訪問(wèn)過(guò)；然后依次從v出發(fā)搜索v的每個(gè)鄰接點(diǎn)w。若w未曾訪問(wèn)過(guò)，則以w為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先遍歷，直至圖中所有和源點(diǎn)v有路徑相通的頂點(diǎn)(亦稱(chēng)為從源點(diǎn)可達(dá)的頂點(diǎn))均已被訪問(wèn)為止。若此時(shí)圖中仍有未訪問(wèn)的頂點(diǎn)，則另選一個(gè)尚未訪問(wèn)的頂點(diǎn)作為新的源點(diǎn)重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)均已被訪問(wèn)為止。44、對(duì)于具有n個(gè)頂點(diǎn)、6條邊的圖()。A、采用鄰接矩陣表示圖時(shí)，查找所有頂點(diǎn)的鄰接頂點(diǎn)的時(shí)間復(fù)雜度為O(n2)B、進(jìn)行廣度優(yōu)先遍歷運(yùn)算所消耗的時(shí)間與采用哪一種存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)C、采用鄰接表表示圖時(shí)，查找所有頂點(diǎn)的鄰接頂點(diǎn)的時(shí)間復(fù)雜度為O(n＊e)D、進(jìn)行深度優(yōu)先遍歷運(yùn)算所消耗的時(shí)間與采用哪一種存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：設(shè)某有向圖和無(wú)向圖如下所示。下面的矩陣A是該有向圖的鄰接矩陣，B為無(wú)向圖的鄰接矩陣。上面有向圖的鄰接鏈表如下圖所示。圖的遍歷運(yùn)算是按照某種策略訪問(wèn)圖中的每一個(gè)頂點(diǎn)，實(shí)質(zhì)上是通過(guò)邊或弧找鄰接點(diǎn)的過(guò)程，因此廣度優(yōu)先搜索遍歷圖和深度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度相同，其不同之處僅僅在于對(duì)頂點(diǎn)訪問(wèn)的次序不同。45、用鄰接矩陣A表示圖，判定任意兩個(gè)頂點(diǎn)Vi和Vj之間是否有長(zhǎng)度m路徑相連，則只要檢查()的第i行和第j列的元素是否為零即可。A、mAB、AC、AmD、Am－1標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：要判斷相鄰矩陣A中任意兩個(gè)頂點(diǎn)Vi和Vj之間是否有長(zhǎng)度為m的路徑相連，只要檢查Am的第i行第j的元素是否為0即可，若為0則無(wú)，否則就存在。46、在向圖的鄰接矩陣表示中，計(jì)算第i個(gè)頂點(diǎn)八度的方法是()。A、第i行非零元素個(gè)數(shù)B、第i列非零元素個(gè)數(shù)C、第i行零元素個(gè)數(shù)D、第i列零元素個(gè)數(shù)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：先用一個(gè)二維數(shù)組Edge存儲(chǔ)表示鄰接矩陣，輸入文件中頂點(diǎn)的序號(hào)是從1開(kāi)始，當(dāng)輸入一條有向邊＜u，v＞時(shí)，將Edge[u－1][v－1]＝1即可；第i＋1個(gè)頂點(diǎn)的出度等于鄰接矩陣中第i行所有元素中元素值為1的個(gè)數(shù)，把第i行所有元素值累加起來(lái)，得到的結(jié)果也是該頂點(diǎn)的出度，同理，在計(jì)算第i＋1個(gè)頂點(diǎn)的入度時(shí)，也只需要將第i列所有元素值累加起來(lái)即可。47、有種關(guān)系模式R＝＜U，F(xiàn)＞，U＝{C，T，H，X，S}，F(xiàn)＝{C→T，(H，X)→C，(H，T)→YC，(H，S)→Y}則表示模式R的碼是()。A、CB、(H，S)C、(H，Y)D、(H，T)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：由題可得如下推導(dǎo)：(H，S)＋R，(H，R)＋C，C－－4T，(H，T)－－4R，故可知(H，S)為關(guān)系模式的碼。48、在UML提供的圖中，用于按時(shí)間順序描述對(duì)象間交互的是()。A、類(lèi)圖B、狀態(tài)圖C、序列圖D、用例圖標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：暫無(wú)解析49、n個(gè)頂點(diǎn)的連通圖至少有多少條邊()。A、n－1B、nC、n＋1D、0標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：至少要有(n－1)條邊(也就是樹(shù))才能保證圖為連通圖。50、下列說(shuō)法中不正確的是()。A、圖的遍歷過(guò)程中每一頂點(diǎn)僅被訪問(wèn)一次B、遍歷圖的基本方法有深度優(yōu)先搜索和廣度優(yōu)先搜索兩種C、圖的深度優(yōu)先搜索的方法不適用于有向圖D、圖的深度優(yōu)先搜索是一個(gè)遞歸過(guò)程標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：圖的深度優(yōu)先搜索的方法對(duì)于有向圖和無(wú)向圖都適用。51、在有向圖中，所有頂點(diǎn)的度數(shù)之和是所有邊數(shù)的()倍。A、0．5B、1C、2D、4標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：在有向圖中，所有頂點(diǎn)的度數(shù)之和是所有邊數(shù)的2倍，因?yàn)橐粭l邊的兩個(gè)端點(diǎn)具有兩個(gè)“度”。52、在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度數(shù)之和為S，則所有頂點(diǎn)的人度數(shù)之和為()。A、SB、S－1C、S＋1D、n標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：圖的所有頂點(diǎn)的出度數(shù)之和等于所有頂點(diǎn)的入度數(shù)之和。故本題選A。53、表達(dá)式3＊2＾(4＊2＊2－6＊3)－5求值過(guò)程中當(dāng)掃描到6時(shí)，對(duì)象棧和算符棧為()，其中＾為乘冪。A、3,2,4,1,1；＊＾(＋＊－B、3,2,8；＊＾－C、3,2,4,2,2；＊＾(－D、3,2,8；＊＾(－標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：第一次：對(duì)象棧：3；算符棧：＊；第二次：對(duì)象棧：3，2；算符棧：＊，＾，(；第三次：對(duì)象棧：3，2，4；算符棧：＊，＾，(，＋；第四次：對(duì)象棧：3，2，4，2；算符棧：＊，＾，(，＋，＊；第五次：對(duì)象棧：3，2，4，4；算符棧：＊，＾，(，＋；第六次(掃描到6)：對(duì)象棧：3，2，8；算符棧：＊，＾，(，－54、從一個(gè)具有N個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于X結(jié)點(diǎn)時(shí)，查找成功的情況下，需平均比較()結(jié)點(diǎn)。A、NB、N／2C、(N－1)／2D、(N＋1)／2標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：x等于第一個(gè)元素的值。則要比較1次x等于第二個(gè)元素的值，則要比較2次x值剛好等于第n個(gè)元素，則要比較x次所以總次數(shù)是1＋2＋3＋……＋n－1＋n＝(n＋1)＊n／2所以平均需要：(n＋1)／2次。55、算法指的是()。A、計(jì)算機(jī)程序B、解決問(wèn)題的計(jì)算方法C、排序算法D、解決問(wèn)題的有限運(yùn)算序列標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：算法是精確定義的一系列規(guī)則，它指出怎樣從給定的輸入信息經(jīng)過(guò)有限步驟產(chǎn)生所求的輸出信息。它既不是計(jì)算機(jī)程序，也不是某種算術(shù)運(yùn)算。56、以下的算法設(shè)計(jì)中，哪一個(gè)是以獲取問(wèn)題最大優(yōu)解為目標(biāo)?()A、回溯法B、分治法C、動(dòng)態(tài)規(guī)則D、逆推標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：暫無(wú)解析二、簡(jiǎn)答題(本題共10題，每題1.0分，共10分。)57、在單鏈表上實(shí)現(xiàn)求線性表表長(zhǎng)的ListLength(L)運(yùn)算。標(biāo)準(zhǔn)答案：由于在單鏈表中只給出一個(gè)頭指針，所以只能用遍歷的方法來(lái)數(shù)點(diǎn)鏈表中的結(jié)點(diǎn)個(gè)數(shù)。算法描述如下：intListLength(LinkList＊L){／／求帶結(jié)點(diǎn)的單鏈表的表長(zhǎng)intlen＝0；LinkList＊p；p＝L；while(p－＞next!＝NULL){p＝p－＞next；len＋＋：}returnlen：}知識(shí)點(diǎn)解析：暫無(wú)解析58、什么是循環(huán)隊(duì)列?標(biāo)準(zhǔn)答案：用常規(guī)意義下順序存儲(chǔ)結(jié)構(gòu)的一維數(shù)組表示隊(duì)列，由于隊(duì)列的性質(zhì)(隊(duì)尾插入和隊(duì)頭刪除)，容易造成“假溢出”現(xiàn)象，即隊(duì)尾已到達(dá)一維數(shù)組的高下標(biāo)，不能再插入，然而隊(duì)中元素個(gè)數(shù)小于隊(duì)列的長(zhǎng)度(容量)。循環(huán)隊(duì)列是解決“假溢出”的一種方法。通常把一維數(shù)組看成首尾相接。在循環(huán)隊(duì)列下，通常采用“犧牲一個(gè)存儲(chǔ)單元”或“作標(biāo)記”的方法解決“隊(duì)滿(mǎn)”和“隊(duì)空”的判定問(wèn)題。知識(shí)點(diǎn)解析：暫無(wú)解析59、什么是隊(duì)列的上溢現(xiàn)象?一般有幾種解決方法，試簡(jiǎn)述之。標(biāo)準(zhǔn)答案：在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列的容量(即存儲(chǔ)的空間大小)為maxnum。當(dāng)有元素要加入隊(duì)列(即入隊(duì))時(shí)，若rear＝maxnum，則會(huì)發(fā)生隊(duì)列的上溢現(xiàn)象，此時(shí)就不能將該元素加入隊(duì)列。對(duì)于隊(duì)列，還有一種“假溢出”現(xiàn)象，隊(duì)列中尚余有足夠的空間，但元素卻不能入隊(duì)，一般是由于隊(duì)列的存儲(chǔ)結(jié)構(gòu)或操作方式的選擇不當(dāng)所致，可以用循環(huán)隊(duì)列解決。一般地，要解決隊(duì)列的上溢現(xiàn)象可有以下幾種方法：(1)可建立一個(gè)足夠大的存儲(chǔ)空間以避免溢出，但這樣做往往會(huì)造成空間使用率低，浪費(fèi)存儲(chǔ)空間。(2)要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決：①采用移動(dòng)元素的方法。每當(dāng)有一個(gè)新元素入隊(duì)，就將隊(duì)列中已有的元素向隊(duì)頭移動(dòng)一個(gè)位置，假定空余空間足夠。②每當(dāng)刪去一個(gè)隊(duì)頭元素，則可依次移動(dòng)隊(duì)列中的元素總是使front指針指向隊(duì)列中的第一個(gè)位置。③采用循環(huán)隊(duì)列方式。將隊(duì)頭、隊(duì)尾看作是一個(gè)首尾相接的循環(huán)隊(duì)列，即用循環(huán)數(shù)組實(shí)現(xiàn)，此時(shí)隊(duì)首仍在隊(duì)尾之前，作插入和刪除運(yùn)算時(shí)仍遵循“先進(jìn)先出”的原則。知識(shí)點(diǎn)解析：暫無(wú)解析60、樹(shù)、森林和二叉樹(shù)是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹(shù)、森林轉(zhuǎn)化為二叉樹(shù)的基本目的是什么，并指出樹(shù)和二叉樹(shù)的主要區(qū)別。標(biāo)準(zhǔn)答案：樹(shù)的孩子兄弟鏈表表示法和二叉樹(shù)二叉鏈表表