數(shù)據(jù)結(jié)構(gòu)與游戲算法復(fù)習(xí)題(有答案)

數(shù)據(jù)結(jié)構(gòu)與游戲算法復(fù)習(xí)題一、選擇題(每小題1分)2．5個(gè)頂點(diǎn)的無向圖最多有()條邊。CA5B10C20D253.算法分析的主要目的是()。CA分析數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性B分析算法的有窮性和確定性C分析算法的時(shí)空效率以求改進(jìn)D分析數(shù)據(jù)結(jié)構(gòu)的合理性4.從一個(gè)長(zhǎng)度為100的順序表中刪除第30個(gè)元素時(shí)，需向前移動(dòng)的元素個(gè)數(shù)是()。AA30B70C71D695.有64個(gè)結(jié)點(diǎn)的完全二叉樹的深度為（）（根的層次為1）。BA8 B7 C5 D66.二維數(shù)組A按行順序存儲(chǔ)，其中每個(gè)元素占1個(gè)存儲(chǔ)單元。若A[1][1]的存儲(chǔ)地址為420，A[3][3]的存儲(chǔ)地址為446，則A[5][5]的存儲(chǔ)地址為（）。CA470B471C472D4737.稀疏矩陣是指（）。DA行數(shù)和列數(shù)很少的矩陣 B有少量零元素的矩陣C元素很少的矩陣 D少量非零元素的矩陣8.從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功情況下，則平均比較結(jié)點(diǎn)個(gè)數(shù)為（）。AA(n+1)/2BnCn/2D(n-1)/29.在字符串的替換操作中，設(shè)替換前的字符串為str=”ABCDEFG”，把從第2個(gè)字符開始的連續(xù)3個(gè)字符替換成”abcd”，則替換后str=”（）”DAAabcdBCDEFG BAabcBCDEFGCAabcEFG DAabcdEFG10.如下陳述中正確的是（）。AA串是一種特殊的線性表B串的長(zhǎng)度必須大于零C串中元素只能是字母D空串就是空白串11.堆的形狀是一棵（）。CA二叉排序樹B滿二叉樹C完全二叉樹 D平衡二叉樹12.在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，若在p和q之間插入s結(jié)點(diǎn)，則執(zhí)行（）。DAp->next=s；s->next=q； Bp->next=s->next；s->next=p;Cq->next=s->next；s->next=p； Ds->next=q；p->next=s；13.當(dāng)利用大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)循環(huán)隊(duì)列，且約定隊(duì)列為空的條件為隊(duì)尾指針等于隊(duì)頭指針時(shí)，該隊(duì)列的最大長(zhǎng)度為（）。AAN-1BN-2CNDN+114.一個(gè)棧的入棧序列a，b，c，d，e，則棧的可能輸出棧序列是（）。BAcdabe BdecbaCcabde Ddabec15.就平均查找速度而言，下列幾種查找速度從慢至快的關(guān)系是（）。CA順序折半哈希分塊B順序哈希分塊折半C順序分塊折半哈希D分塊折半哈希順序16.在一個(gè)具有N個(gè)單元的順序表中,假定以地址低端(即下標(biāo)為1的單元)作為底,以top作為頂指針,則當(dāng)做進(jìn)棧處理時(shí)top變化為()。DAtop=topBtop=0Ctop=top-1Dtop=top+117.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的（）和運(yùn)算的科學(xué).DA算法 B結(jié)構(gòu) C運(yùn)算 D關(guān)系18在一個(gè)單鏈表HL中，若要在指針q所指結(jié)點(diǎn)的后面插入一個(gè)由指針p所指向的結(jié)點(diǎn)，則執(zhí)行（）。DAq->next=p->next；p->next=q；Bq->next=p->next；p->next=q;Cp->next=q->next；q=p；Dp->next=q->next；q->next=p；19．假定一個(gè)鏈隊(duì)的隊(duì)首和隊(duì)尾指針分別為front和rear，則判斷隊(duì)空的條件為（）。AAfront==rear Bfront!=NULLCrear!=NULL Dfront==NULL20．一組待排序記錄的關(guān)鍵字為（46,79,56,38,40,84），則利用快速排序，以第一個(gè)記錄為基準(zhǔn)元素得到的一次劃分結(jié)果為（）。DA（38,40,46,56,79,84） B（40,38,46,84,56,79）C（40,38,46,79,56,84） D（40,38,46,56,79,84）21.線性表若采用鏈表存儲(chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（）。DＡ必須是不連續(xù)的Ｂ部分地址必須是連續(xù)的Ｃ一定是連續(xù)的Ｄ連續(xù)不連續(xù)都可以22.存取數(shù)據(jù)采用先進(jìn)后出原則的是（）。CA字符串 B隊(duì)列C棧 D線性表23．設(shè)有100個(gè)元素，用折半查找法進(jìn)行查找時(shí)，在查找成功的情況下，最大比較次數(shù)是（）。DA100 B50 C99 D724.判斷一個(gè)順序循環(huán)隊(duì)列（QU）（最多元素為m）為滿的條件是（）。D AQU->front==QU->rearBQU->front!=QU->rearCQU->front!=(QU->rear+1)%mDQU->front==(QU->rear+1)%m25.下面程序片段的時(shí)間復(fù)雜度為（）。Cfor(inti=0;i<m;i++)for(intj=0;j<n;j++)A[i][j]=i*j;AO(m2)BO(n2)CO(m*n)DO(m+n)26.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（）倍。BA4 B2C1 D1/227.由權(quán)值分別為9，2，3，5，14的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為（）。CA50B66C67D6828.在完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有（），則它必定是葉子結(jié)點(diǎn)。BA兄弟B左子結(jié)點(diǎn)C右子結(jié)點(diǎn)D左子結(jié)點(diǎn)或右子結(jié)點(diǎn)29.若已知一棵二叉樹先序序列為ABCDEFG，中序序列為CBDAEGF，則其后序序列為（）。AACDBGFEABCDBAGFECCDBFGEADBCDAGFE30.從鄰接矩陣可以看出，該圖共有（）頂點(diǎn)。BA9B3C6D131.鏈?zhǔn)綏Ｅc順序棧相比，比較明顯的優(yōu)點(diǎn)是（）。BA插入操作更加方便 B通常不會(huì)出現(xiàn)棧滿的情況C不會(huì)出現(xiàn)?？盏那闆r D刪除操作更加方便32、在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并使鏈表仍然有序的時(shí)間復(fù)雜度是（）。BAO（1）BO（n）CO(nlogn)DO(n2)33.由分別帶權(quán)為9，2，5，7的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為（）。CA23 B37C44 D4634.下面（）方法可以判斷出一個(gè)有向圖中是否有環(huán)。AA深度優(yōu)先遍歷B拓樸排序C求最短路徑D求關(guān)鍵路徑35.已知一個(gè)順序存儲(chǔ)的線性表，若第一個(gè)結(jié)點(diǎn)的地址是d，第三個(gè)結(jié)點(diǎn)的地址是5d，則第n個(gè)結(jié)點(diǎn)的地址是（）。BA[2*(n-1)-1]*d B[2*(n-1)+1]*dC(n+1)*d D2*(n-1)*d36.將一棵有50個(gè)結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為16的結(jié)點(diǎn)的右孩子的編號(hào)為()。DA30 B31C32 D3337.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（）結(jié)構(gòu)。CA存儲(chǔ) B物理C邏輯 D物理和存儲(chǔ)38.從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為（A）排序法。A插入B選擇C冒泡D都不是39.二叉樹的先序遍歷和中序遍歷如下，則該二叉樹右子樹的樹根是（）。C 先序序列：EFHIGJK中序序列：HFIEJKG AEBFCGDH40.設(shè)無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為（）。D Aaedfbc Bacfebd Caebcfd Daedfcb41．對(duì)一個(gè)滿二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h，則有()。DAn=h+m Bh+m=2nCm=h-1 Dn=2h-142．在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是()。AA選擇排序 B冒泡排序 C插入排序 D希爾排序43．下面()是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)。CA存儲(chǔ)密度大B插入運(yùn)算方便C查找方便D適合各種邏輯結(jié)構(gòu)的存儲(chǔ)表示44．用鏈?zhǔn)椒绞酱鎯?chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)，（B）。A僅修改頭指針B僅修改尾指針C頭、尾指針都要修改D頭、尾指針可能都要修改45．設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作（）。CA插入字串B連接字串C模式匹配D替換字串46．設(shè)有一組關(guān)鍵字序列{Q、H、C、Y、P、A、M、S、R、D、F、X}。若在排序過程中，某趟排序結(jié)果為{F、H、C、D、P、A、M、Q、R、S、Y、X}，則該排序算法是()。DA起泡排序 B初始步長(zhǎng)為4的shell的排序C二路歸并排序 D以第一個(gè)元素為分界元素的快速排序47．二叉樹中第5層上的結(jié)點(diǎn)個(gè)數(shù)最多為()。CA8 B15 C16 D3248．（）的鄰接矩陣是對(duì)稱矩陣。BA有向圖B無向圖CAOV網(wǎng)DAOE網(wǎng)49．若在線性表中采用折半查找法查找元素，該線性表應(yīng)該（）。CA元素按值有序B采用順序存儲(chǔ)結(jié)構(gòu)C元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu)D元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)50．?dāng)?shù)據(jù)序列（8,9,10,4,5,6,20,1,2）只能是下列排序算法中()的兩趟排序后的結(jié)果。BA選擇排序 B插入排序 C堆排序 D冒泡排序二、判斷題（每題1分）1、哈夫曼樹一定是滿二叉樹。（×）2、在一棵二叉樹中，假定每個(gè)結(jié)點(diǎn)只有左子女，沒有右子女，對(duì)它分別進(jìn)行中序遍歷和后序遍歷，則具有相同的結(jié)果。（√）3、線性表的邏輯順序與物理順序總是一致的。(×)4、棧和隊(duì)列都是非線性數(shù)據(jù)結(jié)構(gòu)。(×）5、用一維數(shù)組存儲(chǔ)二叉樹時(shí)，總是以先序遍歷的順序存儲(chǔ)結(jié)點(diǎn)。（×）6、當(dāng)對(duì)一個(gè)線性表進(jìn)行插入和刪除操作較頻繁時(shí)，線性表應(yīng)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（√）7、已知一棵二叉樹的先根遍歷序列和后根遍歷序列可以唯一地構(gòu)造出該二叉樹。（×）8、設(shè)有n個(gè)結(jié)點(diǎn)的完全二叉樹順序存放在數(shù)組a[n]中，對(duì)任一結(jié)點(diǎn)a[i]，它的左孩子結(jié)點(diǎn)所在下標(biāo)為2i。（×）9、若某堆棧的輸入序列為1,2,3,4，則4,3,1,2不可能是堆棧的輸出序列之一。（×）10、二叉樹可以是一棵空樹。（√）11、在平均情況下，快速排序法最快，堆積排序法最節(jié)省空間。（√）12、具有n個(gè)結(jié)點(diǎn)的無向圖至少應(yīng)有n-1條邊才能保證是連通圖。（√）13、完全二叉樹不可以用順序存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)。（×）14、任一AOE網(wǎng)中至少有一條關(guān)鍵路徑，且是從源點(diǎn)到匯點(diǎn)的路徑中最短的一條。（×）15、鏈?zhǔn)酱鎯?chǔ)的線性表可以實(shí)現(xiàn)隨機(jī)存取。（×）16、用一維數(shù)組存儲(chǔ)二叉樹時(shí)，總是以先序遍歷的順序存儲(chǔ)結(jié)點(diǎn)。（×）17、已知指針P指向鍵表L中的某結(jié)點(diǎn)，執(zhí)行語句P=P-〉next不會(huì)刪除該鏈表中的結(jié)點(diǎn)。（√）18、哈夫曼樹，又稱最優(yōu)二叉樹，對(duì)n個(gè)葉子構(gòu)成的哈夫曼樹，樹形是唯一的。（×）19、算法可以沒有輸入，但是必須有輸出。（√）20、在哈希法中，一個(gè)可用散列函數(shù)必須保證絕對(duì)不產(chǎn)生沖突。（×）21、順序表和單鏈表都是隨機(jī)存取的線性存儲(chǔ)結(jié)構(gòu)。(×)22、快速排序是一種不穩(wěn)定的排序方法。（√）23、二叉樹按某種順序線索化后，任一結(jié)點(diǎn)均有指向其直接前驅(qū)和直接后繼的線索。（×）24、在平均情況下，快速排序法最快，堆積排序法最節(jié)省空間。（√）25、關(guān)鍵字序列{12，16，28，25，47，31}是一個(gè)堆。（√）26、有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有6條邊才能確保是一個(gè)連通圖。（×）27、用一組地址連續(xù)的存儲(chǔ)單元存放的元素一定構(gòu)成線性表。（×）28、單鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)。（×）29、在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)頭指針指向隊(duì)頭元素的后一個(gè)位置。（×）30、圖的深度優(yōu)先遍歷類似于二叉樹的先序遍歷。（√）31、若圖G的最小生成樹不唯一，則G的邊數(shù)一定多于n-1，并且權(quán)值最小的邊有多條（其中n為G的頂點(diǎn)數(shù)）。（×）32、根據(jù)樹與二叉樹的轉(zhuǎn)換規(guī)則可知，樹的先根遍歷序列與轉(zhuǎn)換后的二叉樹的先根遍歷序列相同，樹的后根遍歷序列與轉(zhuǎn)換后的二叉樹的中根遍歷序列相同。（√）33、在隊(duì)列的存儲(chǔ)過程中，為了規(guī)避假溢出現(xiàn)象使用的方法是構(gòu)造循環(huán)隊(duì)列。（√）34、數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。(√)35、線性表中的每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)后繼。（√）36、在鏈隊(duì)列中，即使不設(shè)置尾指針也能進(jìn)行入隊(duì)操作。（√）37、單鏈表中邏輯上相鄰的元素物理位置也相鄰。（×）38、已知完全二叉樹的第8層有8個(gè)葉子結(jié)點(diǎn)，則該樹葉子結(jié)點(diǎn)的個(gè)數(shù)為56個(gè)。（×）39、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。(基本單位)（×）40、含尾指針的單鏈循環(huán)表可以被用于隊(duì)列操作。（√）41、設(shè)結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)且結(jié)點(diǎn)B為A的雙親結(jié)點(diǎn)，則結(jié)點(diǎn)B的度數(shù)為4。（√）42、根據(jù)二叉樹的定義，可知二叉樹共有4種不同的形態(tài)。（×）43、有向圖用鄰接表表示，頂點(diǎn)i的出度是對(duì)應(yīng)頂點(diǎn)i鏈表中結(jié)點(diǎn)個(gè)數(shù)。（√）44、刪除二叉排序樹中一個(gè)結(jié)點(diǎn)，再重新插入上去，一定能得到原來的二叉排序樹。（×