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