計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)考試題庫單選題100道及答案

計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)考試題庫單選題100道及答案1.在一個(gè)長度為n的順序表中，若要在第i個(gè)元素（1≤i≤n+1）之前插入一個(gè)新元素，需要向后移動(dòng)多少個(gè)元素？A.n-i+1B.n-iC.iD.i-1答案：A解析：在第i個(gè)元素前插入新元素，從第i個(gè)元素開始到最后一個(gè)元素都要后移，共n-i+1個(gè)元素。2.一個(gè)棧的輸入序列為1,2,3,4，下面哪個(gè)不可能是其輸出序列？A.4,3,2,1B.3,4,2,1C.4,1,2,3D.2,3,4,1答案：C解析：棧是后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，4先出棧說明1、2、3都在棧內(nèi)，此時(shí)只能3先出，不可能1先出。3.若一個(gè)隊(duì)列的入隊(duì)序列為a,b,c,d，則其可能的出隊(duì)序列是？A.d,c,b,aB.a,b,c,dC.c,a,b,dD.b,a,d,c答案：B解析：隊(duì)列是先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，入隊(duì)順序?yàn)閍,b,c,d，出隊(duì)順序自然是a,b,c,d。4.已知一棵二叉樹的先序遍歷序列為ABC，中序遍歷序列為BAC，則該二叉樹的后序遍歷序列為？A.CBAB.BCAC.ACBD.ABC答案：B解析：根據(jù)先序和中序遍歷可確定二叉樹結(jié)構(gòu)，進(jìn)而得到后序遍歷為BCA。5.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的？A.1倍B.2倍C.一半D.無法確定答案：A解析：每條有向邊對應(yīng)一個(gè)入度和一個(gè)出度，所以入度之和等于出度之和。6.對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，采用鄰接表存儲(chǔ)時(shí)，其表頭結(jié)點(diǎn)的個(gè)數(shù)為？A.nB.n+1C.eD.e+1答案：A解析：鄰接表中表頭結(jié)點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)數(shù)相同。7.下面哪種排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.選擇排序C.堆排序D.插入排序答案：C解析：冒泡、選擇、插入排序最壞時(shí)間復(fù)雜度為O(n2)，堆排序?yàn)镺(nlogn)。8.已知一個(gè)有序表為(12,18,24,35,47,50,62,83,90,115,134)，當(dāng)用二分查找法查找值為90的元素時(shí)，需要比較幾次？A.1B.2C.3D.4答案：C解析：第一次取中間值50，第二次取中間值90，共比較3次。9.若要在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，其操作是？A.p->next=p->next->next;B.p=p->next;C.p->next=p;D.p=p->next->next;答案：A解析：要?jiǎng)h除p的后繼結(jié)點(diǎn)，只需將p的next指針指向后繼結(jié)點(diǎn)的后繼結(jié)點(diǎn)。10.一個(gè)完全二叉樹有100個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)的個(gè)數(shù)為？A.49B.50C.51D.52答案：B解析：根據(jù)完全二叉樹性質(zhì)計(jì)算可得葉子結(jié)點(diǎn)個(gè)數(shù)為50。11.在圖的深度優(yōu)先遍歷中，采用的數(shù)據(jù)結(jié)構(gòu)是？A.棧B.隊(duì)列C.堆D.鏈表答案：A解析：深度優(yōu)先遍歷借助棧來實(shí)現(xiàn)回溯。12.下面哪種哈希函數(shù)構(gòu)造方法的時(shí)間復(fù)雜度較高？A.直接定址法B.數(shù)字分析法C.平方取中法D.除留余數(shù)法答案：C解析：平方取中法需要進(jìn)行平方運(yùn)算，相對其他方法時(shí)間復(fù)雜度較高。13.對于一個(gè)有n個(gè)元素的有序數(shù)組進(jìn)行折半查找，其時(shí)間復(fù)雜度為？A.O(n)B.O(logn)C.O(n2)D.O(nlogn)答案：B解析：折半查找每次將查找范圍縮小一半，時(shí)間復(fù)雜度為O(logn)。14.若一個(gè)棧的初始狀態(tài)為空，將元素A、B、C、D、E依次入棧，然后依次出棧，則出棧順序?yàn)椋緼.A、B、C、D、EB.E、D、C、B、AC.C、D、E、A、BD.B、C、D、E、A答案：B解析：棧是后進(jìn)先出，入棧順序?yàn)锳、B、C、D、E，出棧順序則為E、D、C、B、A。15.已知一個(gè)二叉樹的中序遍歷序列為DBEAC，后序遍歷序列為DEBCA，則該二叉樹的先序遍歷序列為？A.ABCDEB.ACBDEC.ADBECD.ABDEC答案：C解析：根據(jù)中序和后序遍歷確定二叉樹結(jié)構(gòu)，得出先序遍歷為ADBEC。16.在一個(gè)無向圖中，若從頂點(diǎn)v出發(fā)進(jìn)行廣度優(yōu)先遍歷，所使用的數(shù)據(jù)結(jié)構(gòu)是？A.棧B.隊(duì)列C.堆D.鏈表答案：B解析：廣度優(yōu)先遍歷借助隊(duì)列來實(shí)現(xiàn)層次遍歷。17.下面哪種排序算法是穩(wěn)定的？A.快速排序B.堆排序C.歸并排序D.希爾排序答案：C解析：歸并排序是穩(wěn)定排序，其他幾種是不穩(wěn)定排序。18.若要在一個(gè)循環(huán)隊(duì)列中插入一個(gè)新元素，需要移動(dòng)幾個(gè)指針？A.0B.1C.2D.3答案：B解析：循環(huán)隊(duì)列插入元素只需移動(dòng)隊(duì)尾指針。19.對于一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖，其邊的數(shù)量為？A.n(n-1)/2B.n(n-1)C.n2D.n2/2答案：A解析：無向完全圖邊數(shù)公式為n(n-1)/2。20.已知一個(gè)哈希表的長度為10，采用除留余數(shù)法（H(key)=key%10），若要插入關(guān)鍵字為23的元素，其存儲(chǔ)地址為？A.2B.3C.23D.0答案：B解析：23%10=3，所以存儲(chǔ)地址為3。21.在一個(gè)順序存儲(chǔ)的線性表中，若要?jiǎng)h除第i個(gè)元素（1≤i≤n），需要向前移動(dòng)多少個(gè)元素？A.n-i+1B.n-iC.iD.i-1答案：B解析：刪除第i個(gè)元素，從第i+1個(gè)元素到最后一個(gè)元素都要前移，共n-i個(gè)元素。22.一個(gè)隊(duì)列的初始狀態(tài)為空，若依次執(zhí)行入隊(duì)操作：a,b,c，再執(zhí)行兩次出隊(duì)操作，然后再執(zhí)行入隊(duì)操作：d,e，此時(shí)隊(duì)列中的元素為？A.c,d,eB.a,b,d,eC.b,c,d,eD.d,e答案：A解析：入隊(duì)a,b,c，出隊(duì)兩次后剩下c，再入隊(duì)d,e，隊(duì)列元素為c,d,e。23.已知一棵二叉樹的先序遍歷序列為ABDECFG，中序遍歷序列為DBEACGF，則該二叉樹的后序遍歷序列為？A.DEBGFCAB.DEBACGFC.DBEFCAD.DEBGCAF答案：A解析：根據(jù)先序和中序遍歷確定二叉樹結(jié)構(gòu)，得到后序遍歷為DEBGFCA。24.在一個(gè)有向圖中，若存在一個(gè)頂點(diǎn)的入度為0，則該頂點(diǎn)是？A.源點(diǎn)B.匯點(diǎn)C.中間頂點(diǎn)D.孤立頂點(diǎn)答案：A解析：入度為0的頂點(diǎn)是源點(diǎn)。25.下面哪種排序算法的平均時(shí)間復(fù)雜度與最壞時(shí)間復(fù)雜度相同？A.快速排序B.堆排序C.冒泡排序D.希爾排序答案：B解析：堆排序平均和最壞時(shí)間復(fù)雜度都是O(nlogn)。26.若一個(gè)哈希表采用開放定址法解決沖突，當(dāng)發(fā)生沖突時(shí)，通常采用的方法是？A.線性探測法B.鏈地址法C.再哈希法D.建立公共溢出區(qū)答案：A解析：開放定址法常用線性探測法解決沖突。27.對于一個(gè)有n個(gè)元素的無序數(shù)組進(jìn)行簡單選擇排序，其比較次數(shù)為？A.n(n-1)/2B.n(n-1)C.n2D.n2/2答案：A解析：簡單選擇排序比較次數(shù)為n(n-1)/2。28.在一個(gè)單鏈表中，若要查找值為x的結(jié)點(diǎn)，平均需要比較多少次？A.nB.n/2C.lognD.nlogn答案：B解析：單鏈表查找元素平均比較次數(shù)為n/2。29.已知一個(gè)完全二叉樹的第6層有8個(gè)葉子結(jié)點(diǎn)，則該完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多為？A.71B.72C.73D.74答案：B解析：根據(jù)完全二叉樹性質(zhì)計(jì)算可得最多有72個(gè)結(jié)點(diǎn)。30.在圖的拓?fù)渑判蛑?，所使用的?shù)據(jù)結(jié)構(gòu)是？A.棧B.隊(duì)列C.堆D.鏈表答案：B解析：拓?fù)渑判蚪柚?duì)列來實(shí)現(xiàn)。31.下面哪種哈希函數(shù)構(gòu)造方法適用于關(guān)鍵字位數(shù)較多的情況？A.直接定址法B.數(shù)字分析法C.平方取中法D.除留余數(shù)法答案：B解析：數(shù)字分析法適用于關(guān)鍵字位數(shù)多的情況。32.對于一個(gè)有n個(gè)元素的有序數(shù)組進(jìn)行順序查找，其平均查找長度為？A.nB.(n+1)/2C.lognD.nlogn答案：B解析：順序查找平均查找長度為(n+1)/2。33.若一個(gè)棧的初始狀態(tài)為空，將元素1,2,3依次入棧，然后出棧一次，再入棧元素4，最后出棧所有元素，則出棧順序?yàn)?？A.3,4,2,1B.3,2,4,1C.3,2,1,4D.4,3,2,1答案：A解析：入棧1,2,3，出棧3，入棧4，再出棧4,2,1，順序?yàn)?,4,2,1。34.已知一個(gè)二叉樹的中序遍歷序列為IFDGJHEA，后序遍歷序列為IFDJHGBAE，則該二叉樹的先序遍歷序列為？A.EABDFGHIJB.EABDFGJHIC.EABDFHJGID.EABDFHJIG答案：A解析：根據(jù)中序和后序遍歷確定二叉樹結(jié)構(gòu)，得出先序遍歷為EABDFGHIJ。35.在一個(gè)無向圖中，若從頂點(diǎn)v出發(fā)進(jìn)行深度優(yōu)先遍歷，訪問到的第一個(gè)頂點(diǎn)是v，第二個(gè)頂點(diǎn)可能是？A.v的任意一個(gè)鄰接頂點(diǎn)B.v的度最大的鄰接頂點(diǎn)C.v的度最小的鄰接頂點(diǎn)D.按照頂點(diǎn)編號順序的第一個(gè)鄰接頂點(diǎn)答案：A解析：深度優(yōu)先遍歷從v出發(fā)，第二個(gè)頂點(diǎn)可以是v的任意一個(gè)鄰接頂點(diǎn)。36.下面哪種排序算法的空間復(fù)雜度最低？A.冒泡排序B.快速排序C.歸并排序D.堆排序答案：A解析：冒泡排序空間復(fù)雜度為O(1)，是最低的。37.若要在一個(gè)循環(huán)隊(duì)列中刪除一個(gè)元素，需要移動(dòng)幾個(gè)指針？A.0B.1C.2D.3答案：B解析：循環(huán)隊(duì)列刪除元素只需移動(dòng)隊(duì)頭指針。38.對于一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖，其邊的數(shù)量為？A.n(n-1)/2B.n(n-1)C.n2D.n2/2答案：B解析：有向完全圖邊數(shù)公式為n(n-1)。39.已知一個(gè)哈希表的長度為11，采用除留余數(shù)法（H(key)=key%11），若要插入關(guān)鍵字為45的元素，其存儲(chǔ)地址為？A.1B.2C.4D.5答案：C解析：45%11=1，所以存儲(chǔ)地址為4。40.在一個(gè)順序存儲(chǔ)的線性表中，若要在表尾插入一個(gè)新元素，其時(shí)間復(fù)雜度為？A.O(1)B.O(n)C.O(logn)D.O(nlogn)答案：A解析：在表尾插入元素，直接添加，時(shí)間復(fù)雜度為O(1)。41.一個(gè)隊(duì)列的初始狀態(tài)為空，若依次執(zhí)行入隊(duì)操作：10,20,30，再執(zhí)行一次出隊(duì)操作，然后再執(zhí)行入隊(duì)操作：40，此時(shí)隊(duì)列的隊(duì)頭元素為？A.10B.20C.30D.40答案：B解析：入隊(duì)10,20,30，出隊(duì)10，再入隊(duì)40，隊(duì)頭元素為20。42.已知一棵二叉樹的先序遍歷序列為ABDECFG，后序遍歷序列為DEBGFCA，則該二叉樹的中序遍歷序列為？A.DBEACGFB.DBEAGCFC.DBEAGFCD.DBEACFG答案：A解析：根據(jù)先序和后序遍歷確定二叉樹結(jié)構(gòu)，得到中序遍歷為DBEACGF。43.在一個(gè)有向圖中，若存在一個(gè)頂點(diǎn)的出度為0，則該頂點(diǎn)是？A.源點(diǎn)B.匯點(diǎn)C.中間頂點(diǎn)D.孤立頂點(diǎn)答案：B解析：出度為0的頂點(diǎn)是匯點(diǎn)。44.下面哪種排序算法在最好情況下的時(shí)間復(fù)雜度為O(n)？A.快速排序B.堆排序C.冒泡排序D.希爾排序答案：C解析：冒泡排序在有序情況下時(shí)間復(fù)雜度為O(n)。45.若一個(gè)哈希表采用鏈地址法解決沖突，當(dāng)插入一個(gè)新元素時(shí)，需要在鏈表中進(jìn)行的操作是？A.頭插法B.尾插法C.按關(guān)鍵字大小插入D.隨機(jī)插入答案：A解析：鏈地址法插入元素常用頭插法。46.對于一個(gè)有n個(gè)元素的無序數(shù)組進(jìn)行冒泡排序，其最好情況下的比較次數(shù)為？A.nB.n-1C.n(n-1)/2D.n2答案：B解析：冒泡排序最好情況是數(shù)組有序，比較次數(shù)為n-1。47.在一個(gè)單鏈表中，若要在p所指結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)s，其操作是？A.s->next=p->next;p->next=s;B.p->next=s;s->next=p->next;C.s->next=p;p->next=s;D.p->next=s->next;s->next=p;答案：A解析：先讓s的next指向p的后繼，再讓p的next指向s。48.已知一個(gè)完全二叉樹的第7層有10個(gè)葉子結(jié)點(diǎn)，則該完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最少為？A.75B.76C.77D.78答案：A解析：根據(jù)完全二叉樹性質(zhì)計(jì)算可得最少有75個(gè)結(jié)點(diǎn)。49.在圖的最小生成樹算法中，Prim算法使用的數(shù)據(jù)結(jié)構(gòu)是？A.棧B.隊(duì)列C.優(yōu)先隊(duì)列D.鏈表答案：C解析：Prim算法使用優(yōu)先隊(duì)列來優(yōu)化。50.下面哪種哈希函數(shù)構(gòu)造方法簡單且效率高？A.直接定址法B.數(shù)字分析法C.平方取中法D.除留余數(shù)法答案：D解析：除留余數(shù)法簡單且效率高。51.對于一個(gè)有n個(gè)元素的有序數(shù)組進(jìn)行二分查找，其最壞情況下的比較次數(shù)為？A.?log?n?+1B.?log?(n+1)?C.nD.n/2答案：B解析：二分查找最壞情況是要查找到最后一個(gè)元素才找到或確定不存在，比較次數(shù)為?log?(n+1)?。52.若一個(gè)棧的初始狀態(tài)為空，將元素a、b、c、d依次入棧，然后出棧兩次，再入棧元素e，最后全部出棧，則出棧順序?yàn)?？A.c、d、e、b、aB.d、c、e、b、aC.d、c、b、e、aD.c、d、b、e、a答案：B解析：入棧a、b、c、d，出棧d、c，入棧e，再出棧e、b、a，出棧順序?yàn)閐、c、e、b、a。53.已知一個(gè)二叉樹的中序遍歷序列為HGIEFDBCA，后序遍歷序列為HIGFEDCBA，則該二叉樹的先序遍歷序列為？A.ABCDEFGHIB.ABCDEGFHIC.ABCEDGFHID.ABCEDFGHI答案：A解析：根據(jù)中序和后序遍歷確定二叉樹結(jié)構(gòu)，得出先序遍歷為ABCDEFGHI。54.在一個(gè)無向圖中，若圖的頂點(diǎn)數(shù)為n，邊數(shù)為e，且e=n-1，則該圖一定是？A.連通圖B.樹C.有環(huán)圖D.非連通圖答案：B解析：無向圖中頂點(diǎn)數(shù)為n，邊數(shù)為n-1的連通圖是樹。55.下面哪種排序算法是不穩(wěn)定的，且在平均情況下時(shí)間復(fù)雜度為O(nlogn)？A.歸并排序B.堆排序C.冒泡排序D.插入排序答案：B解析：堆排序不穩(wěn)定，平均時(shí)間復(fù)雜度為O(nlogn)。56.若一個(gè)哈希表采用線性探測再散列法解決沖突，當(dāng)插入一個(gè)關(guān)鍵字為k的元素時(shí)，發(fā)生沖突，下一個(gè)可能的存儲(chǔ)地址是？A.H(k)+1B.H(k)-1C.2H(k)D.H(k)2答案：A解析：線性探測再散列法沖突后下一個(gè)地址是H(k)+1。57.對于一個(gè)有n個(gè)元素的無序數(shù)組進(jìn)行簡單插入排序，在最壞情況下的比較次數(shù)為？A.n(n-1)/2B.n(n-1)C.n2D.n2/2答案：A解析：簡單插入排序最壞情況比較次數(shù)為n(n-1)/2。58.在一個(gè)雙鏈表中，若要?jiǎng)h除p所指結(jié)點(diǎn)，需要修改幾個(gè)指針？A.1B.2C.3D.4答案：D解析：要修改p的前驅(qū)的后繼指針和p的后繼的前驅(qū)指針，共4個(gè)指針。59.已知一個(gè)完全二叉樹的第8層有12個(gè)葉子結(jié)點(diǎn)，則該完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多為？A.247B.248C.249D.250答案：B解析：根據(jù)完全二叉樹性質(zhì)計(jì)算可得最多有248個(gè)結(jié)點(diǎn)。60.在圖的最短路徑算法中，Dijkstra算法使用的數(shù)據(jù)結(jié)構(gòu)是？A.棧B.隊(duì)列C.優(yōu)先隊(duì)列D.鏈表答案：C解析：Dijkstra算法使用優(yōu)先隊(duì)列優(yōu)化。61.下面哪種哈希函數(shù)構(gòu)造方法對關(guān)鍵字分布要求較高？A.直接定址法B.數(shù)字分析法C.平方取中法D.除留余數(shù)法答案：B解析：數(shù)字分析法需要關(guān)鍵字分布有一定規(guī)律。62.對于一個(gè)有n個(gè)元素的有序數(shù)組進(jìn)行順序查找，若查找成功，平均比較次數(shù)為？A.(n+1)/2B.n/2C.lognD.nlogn答案：A解析：順序查找成功時(shí)平均比較次數(shù)為(n+1)/2。63.若一個(gè)棧的初始狀態(tài)為空，將元素5、6、7、8依次入棧，然后出棧一次，再入棧元素9，接著出棧兩次，最后入棧元素10，出棧所有元素，則出棧順序?yàn)?？A.8、9、6、5、10、7B.8、9、7、5、10、6C.8、9、7、6、10、5D.8、9、6、7、10、5答案：C解析：入棧5、6、7、8，出棧8，入棧9，出棧9、7，入棧10，再出棧6、5、10，出棧順序?yàn)?、9、7、6、10、5。64.已知一個(gè)二叉樹的先序遍歷序列為ABDECFG，中序遍歷序列為DBEACGF，若要將該二叉樹轉(zhuǎn)化為森林，森林中樹的棵數(shù)為？A.1B.2C.3D.4答案：B解析：根據(jù)先序和中序遍歷確定二叉樹，轉(zhuǎn)化為森林后樹的棵數(shù)為2。65.在一個(gè)有向圖中，若所有頂點(diǎn)的入度都大于0，則該圖一定？A.存在環(huán)B.不存在環(huán)C.是連通圖D.是非連通圖答案：A解析：所有頂點(diǎn)入度大于0，必然存在環(huán)。66.下面哪種排序算法在數(shù)據(jù)基本有序時(shí)效率最高？A.快速排序B.堆排序C.插入排序D.選擇排序答案：C解析：插入排序在數(shù)據(jù)基本有序時(shí)效率高。67.若一個(gè)哈希表采用二次探測再散列法解決沖突，當(dāng)插入一個(gè)關(guān)鍵字為k的元素時(shí)，發(fā)生沖突，第一次探測的地址可能是？A.H(k)+12B.H(k)-12C.2H(k)D.H(k)2答案：A解析：二次探測再散列法第一次探測地址是H(k)+12。68.對于一個(gè)有n個(gè)元素的無序數(shù)組進(jìn)行堆排序，其建堆的時(shí)間復(fù)雜度為？A.O(n)B.O(nlogn)C.O(n2)D.O(logn)答案：A解析：堆排序建堆時(shí)間復(fù)雜度為O(n)。69.在一個(gè)單循環(huán)鏈表中，若要在表頭插入一個(gè)新結(jié)點(diǎn)s，需要修改幾個(gè)指針？A.1B.2C.3D.4答案：B解析：修改頭指針和尾指針。70.已知一個(gè)完全二叉樹的第9層有15個(gè)葉子結(jié)點(diǎn)，則該完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最少為？A.262B.263C.264D.265答案：B解析：根據(jù)完全二叉樹性質(zhì)計(jì)算可得最少有263個(gè)結(jié)點(diǎn)。71.在圖的拓?fù)渑判蛑?，若一個(gè)有向圖存在環(huán)，則拓?fù)渑判?？A.無法進(jìn)行B.可以進(jìn)行，但結(jié)果不唯一C.可以進(jìn)行，且結(jié)果唯一D.可以進(jìn)行，結(jié)果可能不唯一答案：A解析：有向圖存在環(huán)則無法進(jìn)行拓?fù)渑判颉?2.下面哪種哈希函數(shù)構(gòu)造方法適合關(guān)鍵字是整數(shù)的情況？A.直接定址法B.數(shù)字分析法C.平方取中法D.除留余數(shù)法答案：D解析：除留余數(shù)法適合整數(shù)關(guān)鍵字。73.對于一個(gè)有n個(gè)元素的有序數(shù)組進(jìn)行二分查找，若查找失敗，最多比較次數(shù)為？A.?log?n?+1B.?log?(n+1)?C.nD.n/2答案：B解析：二分查找失敗最多比較次數(shù)為?log?(n+1)?。74.若一個(gè)棧的初始狀態(tài)為空，將元素m、n、p、q依次入棧，然后出棧三次，再入棧元素r，最后全部出棧，則出棧順序?yàn)椋緼.q、p、n、r、mB.q、p、r、n、mC.q、r、p、n、mD.r、q、p、n、m答案：A解析：入棧m、n、p、q，出棧q、p、n，入棧r，再出棧r、m，出棧順序?yàn)閝、p、n、r、m。75.已知一個(gè)二叉樹的中序遍歷序列為JIHGFEDCBA，后序遍歷序列為JIHGFEDCBA，則該二叉樹的先序遍歷序列為？A.ABCDEFGHIJB.AGFEDCBHIJC.AGBFEDCHIJD.AGBFEDCIHJ答案：A解析：根據(jù)中序和后序遍歷確定二叉樹結(jié)構(gòu)，得出先序遍歷為ABCDEFGHIJ。76.在一個(gè)無向圖中，若圖的邊數(shù)e=n，則該圖一定？A.有環(huán)B.無環(huán)C.是連通圖D.是非連通圖答案：A解析：無向圖邊數(shù)e=n時(shí)一定有環(huán)。77.下面哪種排序算法在平均情況下的空間復(fù)雜度為O(logn)？A.快速排序B.堆排序C.冒泡排序D.插入排序答案：A解析：快速排序平均空間復(fù)雜度為O(logn)。78.若一個(gè)哈希表采用鏈地址法解決沖突，當(dāng)查找一個(gè)關(guān)鍵字為k的元素時(shí)，需要在鏈表中進(jìn)行的操作是？A.從頭開始遍歷B.從尾開始遍歷C.按關(guān)鍵字大小查找D.隨機(jī)查找答案：A解析：鏈地址法查找元素從頭開始遍歷鏈表。79.對于一個(gè)有n個(gè)元素的無序數(shù)組進(jìn)行希爾排序，其時(shí)間復(fù)雜度與什么有關(guān)？A.增量序列B.元素個(gè)數(shù)C.元素大小D.元素順序答案：A解析：希爾排序時(shí)間復(fù)雜度與增量序列有關(guān)。80.在一個(gè)雙循環(huán)鏈表中，若要?jiǎng)h除p所指結(jié)點(diǎn)，需要修改幾個(gè)指針？A.2B.3C.4D.5答案：C解析：修改p的前驅(qū)的后繼指針、p的后繼的前驅(qū)指針。81.已知一個(gè)完全二叉樹的第10層有18個(gè)葉子結(jié)點(diǎn)，則該完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多為？A.510B.511C.512D.513答案：B解析：根據(jù)完全二叉樹性質(zhì)計(jì)算可得最多有511個(gè)結(jié)點(diǎn)。82.在圖的深度優(yōu)先搜索中，若要記錄訪問過的頂點(diǎn)，通常使用的數(shù)據(jù)結(jié)構(gòu)是？A.棧B.隊(duì)列C.數(shù)組D.鏈表答案：C解析：使用數(shù)組標(biāo)記訪問過的頂點(diǎn)。83.下面哪種哈希函數(shù)構(gòu)造方法的隨機(jī)性較強(qiáng)？A.直接定址法B.數(shù)字分析法C.平方取中法D.除留余數(shù)法答案：C解析：平方取中法隨機(jī)性較強(qiáng)。84.對于一個(gè)有n個(gè)元素的有序數(shù)組進(jìn)行順序查找，若查找失敗，平均比較次數(shù)為？A.nB.n+1C.(n+1)/2D.n/2答案：B解析：順序查找失敗平均比較n+1次。85.若一個(gè)棧的初始狀態(tài)為空，將元素x、y、z、w依次入棧，然后出棧兩次，再入棧元素v，最后全部出棧，則出棧順序?yàn)?？A.z、w、v、y、xB.w、z、v、y、xC.w、z、y、v、xD.z、w、y、v、x答案：A解析：入棧x、y、z、w，出棧w、z，入棧v，再出棧v、y、x，出棧順序?yàn)閦、w、v、y、x。86.已知一個(gè)二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBDAEGF，則該二叉樹的后序遍歷序列為？A.CDBGFEAB.CDBGEFAC.CDBFGEAD.CDBFEGA答案：A解析：根據(jù)先序和中序遍歷確定二叉樹結(jié)構(gòu)，得到后序遍歷為CDBGFEA。87.在一個(gè)有向圖中，若存在一個(gè)頂點(diǎn)的入度和出度都為0，則該頂點(diǎn)是？A.源點(diǎn)B.匯點(diǎn)C.孤立頂點(diǎn)D.中間頂點(diǎn)答案：C解析：入度和出度都為0的頂點(diǎn)是孤立頂點(diǎn)。88.下面哪種排序算法在最壞情況下空間復(fù)雜度為O(n)？A.快速排序B.堆排序C.歸并排序D.選擇排序答案：C解析：歸并排序最壞空間復(fù)雜度為O(n)。89.若一個(gè)哈希表采用再哈希法解決沖突，當(dāng)發(fā)生沖突時(shí)，使用的第二個(gè)哈希函數(shù)為H?(key)，則下一個(gè)可能的存儲(chǔ)地址是？A.H?(key)+H?(key)B.H?(key)-H?(key)C.H?(key)D.H?(key)*H?(key)答案：A解析：再哈希法下一個(gè)地址是H?(key)+H?(key)。90.對于一個(gè)有n個(gè)元素的無序數(shù)組進(jìn)行選擇排序，其比較次數(shù)和交換次數(shù)分別為？A.n(n-1)/2，n-1B.n(n-1)，nC.n2，nD.n2/2，n-1答案：A解析：選擇排序比較次數(shù)為n(n-1)/2，交換次數(shù)為n-1。91.在一個(gè)單鏈表中，若要查找倒數(shù)第k個(gè)結(jié)點(diǎn)，通常使用的方法是？A.兩次遍歷B.快慢指針C.遞歸D.棧答案：B解析：使用快慢指針可以一次遍歷找到倒數(shù)第k個(gè)結(jié)點(diǎn)。92.已知一個(gè)完全二叉樹的第11層有20個(gè)葉子結(jié)點(diǎn)，則該完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最少為？A.1022B.1023C.1024D.1025答案：B解析：根據(jù)完全二叉樹性質(zhì)計(jì)算可得最少有1023個(gè)結(jié)點(diǎn)。93.在圖的廣度優(yōu)先搜索中，若要記錄頂點(diǎn)的層次，通常使用的數(shù)據(jù)結(jié)構(gòu)是？A.棧B.隊(duì)列C.數(shù)組D.鏈表答案：C解析：使用數(shù)組記錄頂點(diǎn)層次。94.下面哪種哈希函數(shù)構(gòu)造方法對關(guān)鍵字的分布不敏感？A.直接定址法B.數(shù)字分析法C.平方取中法D.除留余數(shù)法答案：D解析：除留余數(shù)法對關(guān)鍵字分布不敏感。95.對于一個(gè)有n個(gè)元素的有