數據結構與算法題庫一、單選題（共86題，每題1分，共86分）1.雙鏈表-刪除結點在雙鏈表中，刪除p所指結點的后繼結點，其語句應該為▁▁▁▁▁。A、s=p->next;s->next->prev=p;p->next=s->next->next;B、s=p;s->next->prev=p;p->next=s->next;C、s=p;s->next->prev=p->prev;p->next=s->next;D、s=p->next;s->next->prev=p;p->next=s->next;正確答案：D2.對于先序遍歷與中序遍歷結果相同的二叉樹為（）A、一般二叉樹B、任一結點均無右孩子的二叉樹C、任一結點均無左子樹的二叉樹D、以上都不是正確答案：C3.被計算機加工的數據元素不是孤立的，它們彼此之間一般存在某種關系，通常把數據元素之間的這種關系稱為A、結構B、運算C、集合D、規則正確答案：A4.如果AVL樹的深度為5（空樹的深度定義為0），則此樹最少有多少個結點？A、12B、20C、33D、64正確答案：A5.在評價一個搜索引擎時，下列哪項不是我們關注的要點？A、搜索的速度B、搜索結果集的相關性C、索引的速度D、界面的友好程度正確答案：D6.下列哪個函數是O(N)的？A、N2/1000B、N(logN)2C、(logN)2D、(NlogN)/1000正確答案：C7.一棵度為4的樹中有20個度為4的結點、10個度為3的結點、1個度為2的結點和10個度為1的結點，則樹的葉子結點數為▁▁▁▁▁。A、122B、41C、113D、82正確答案：D8.循環隊列的引入，目的是為了克服()。A、假溢出問題B、真溢出問題C、操作不方便D、空間不夠用正確答案：A9.斐波那契數列FN的定義為：F0=0,F1=1,FN=FN?1+FN?2,N=2,3,…。用遞歸函數計算FN的時間復雜度是：A、O(logN)B、O(N!)C、NlogN2和NlogND、O(N)正確答案：C10.若結點p與q在二叉樹T的中序遍歷序列中相鄰，且p在q之前，則下列p與q的關系中，不可能的是I.q是p的雙親II.q是p的右孩子III.q是p的右兄弟IV.q是p的雙親的雙親A、僅II、IVB、僅II、IIIC、僅IIID、僅I正確答案：C11.一棵高度為8的完全二叉樹至少有（）葉子節點A、64B、128C、127D、63正確答案：A12.對一棵二叉樹的結點從1開始順序編號。要求每個結點的編號大于其左子樹所有結點的編號、但小于右子樹中所有結點的編號?？刹捎猫x▁▁▁▁實現編號。A、中序遍歷B、層次遍歷C、先序遍歷D、后序遍歷正確答案：A13.用二分查找從100個有序整數中查找某數，最壞情況下需要比較的次數是：A、10B、99C、50D、7正確答案：D14.以二叉鏈表作為二叉樹的存儲結構，在具有n個結點的二叉鏈表中（n>0），空鏈域的個數為__A、n?1B、無法確定C、n+1D、n正確答案：C15.下列代碼if(A>B){for(i=0;i<N;i++)for(j=N*N;j>i;j--)A+=B;}else{for(i=0;i<N*2;i++)for(j=N*2;j>i;j--)A+=B;}A、O(N)B、O(N2)C、O(N3)D、O(N4)正確答案：C16.線性表L在什么情況下適用于使用鏈式結構實現？A、L中含有大量的結點B、需不斷對L進行刪除插入C、需經常修改L中的結點值D、L中結點結構復雜正確答案：B17.對N個記錄進行歸并排序，歸并趟數的數量級是：A、O(N)B、O(N2)C、O(NlogN)D、O(logN)正確答案：D18.有兩個垃圾郵件檢測系統，分別用帶有10000封正常郵件和2000封垃圾郵件的數據集進行測試。系統A檢測出了300封正常郵件和1600封垃圾郵件，系統B檢測出了315封正常郵件和1800封垃圾郵件。如果我們重點關注的是保證重要郵件的安全，下列哪句陳述是正確的？A、我們應重點關注準確率，系統A更好一些。B、我們應重點關注召回率，系統B更好一些。C、我們應重點關注準確率，系統B更好一些。D、我們應重點關注召回率，系統A更好一些。正確答案：C19.設T是非空二叉樹，若T的先序遍歷和后序遍歷序列相同，則T的形態是A、只有一個根結點B、沒有度為1的結點C、所有結點只有左孩子D、所有結點只有右孩子正確答案：A20.對10TB的數據文件進行排序，應使用的方法是：A、希爾排序B、堆排序C、歸并排序D、快速排序正確答案：C21.已知初始為空的隊列Q的一端僅能進行入隊操作，另外一端既能進行入隊操作又能進行出隊操作。若Q的入隊序列是1、2、3、4、5，則不能得到的出隊序列是：A、4、1、3、2、5B、5、3、1、2、4C、5、4、3、1、2D、4、2、1、3、5正確答案：A22.有組記錄的排序碼為{46，79，56，38，40，84}，則利用堆排序的方法建立的初始堆為：A、84，79，56，38，40，46B、79，46，56，38，40，80C、84，79，56，46，40，38D、84，56，79，40，46，38正確答案：A23.給定A[]={46,23,8,99,31,12,85}，調用非遞歸的歸并排序加表排序執行第1趟后，表元素的結果是：A、1,2,3,4,5,6,7B、1,0,2,3,5,4,6C、3,6,1,5,2,7,4D、0,2,1,4,3,5,6正確答案：B24.我們用一個有向圖來表示航空公司所有航班的航線。下列哪種算法最適合解決找給定兩城市間最經濟的飛行路線問題？A、Dijkstra算法B、Kruskal算法C、深度優先搜索D、拓撲排序算法正確答案：A25.設一個堆棧的入棧順序是1、2、3、4、5。若第一個出棧的元素是4，則最后一個出棧的元素必定是：A、5B、3C、1D、1或者5正確答案：D26.下列程序段的時間復雜度為（）。x=n;/*n>1*/y=0;while(x>=(y+1)*(y+1))y=y+1;A、Θ(n)B、Θ(n?)C、Θ(1)D、Θ(n2)正確答案：B27.設高為h的二叉樹（規定葉子結點的高度為1）只有度為0和2的結點，則此類二叉樹的最少結點數和最多結點數分別為：A、2h,2h?1B、2h?1,2h?1C、2h?1+1,2h?1D、2h?1,2h?1?1正確答案：B28.某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作。若元素a、b、c、d、e依次入此隊列后再進行出隊操作，則不可能得到的出隊序列是：A、dbcaeB、dbaceC、bacdeD、ecbad正確答案：A29.對一棵二叉樹的結點從1開始順序編號。要求每個結點的編號都小于其子樹所有結點的編號，且左子樹所有結點的編號都小于右子樹所有結點的編號?？刹捎猫x▁▁▁▁實現編號。A、后序遍歷B、中序遍歷C、先序遍歷D、層次遍歷正確答案：C30.雙鏈表-插入結點在雙鏈表中，將s所指新結點插入到p所指結點之前，其語句應該為▁▁▁▁▁。A、p->prev->next=s;p->prev=s;s->prev=p->prev;s->next=p;B、s->prev=p->prev;s->next=p;p->prev=s;p->prev->next=s;C、p->prev=s;p->prev->next=s;s->prev=p->prev;s->next=p;D、s->prev=p->prev;s->next=p;p->prev->next=s;p->prev=s;正確答案：A31.對給定序列{110，119，7，911，114，120，122}采用次位優先（LSD）的基數排序，則兩趟收集后的結果為：A、7,110,119,114,911,120,122B、7,110,119,114,911,122,120C、7,110,911,114,119,120,122D、110,120,911,122,114,7,119正確答案：C32.采用多項式的非零項鏈式存儲表示法，如果兩個多項式的非零項分別為N1和N2個，最高項指數分別為M1和M2，則實現兩個多項式相乘的時間復雜度是：A、O(M1+M2)B、O(N1×N2)C、O(M1×M2)D、O(N1+N2)正確答案：B33.在下述結論中，正確的是：①只有2個結點的樹的度為1；②二叉樹的度為2；③二叉樹的左右子樹可任意交換；④在最大堆（大頂堆）中，從根到任意其它結點的路徑上的鍵值一定是按非遞增有序排列的。A、①②③B、②③④C、①④D、②④正確答案：C34.將1,2,3,6,5,4順序一個個插入一棵初始為空的AVL樹，會經歷下列哪些旋轉？A、兩個“右-右”旋和一個“右-左”旋B、一個“右-右”旋、一個“右-左”旋、一個“左-右”旋C、一個“右-右”旋和兩個“右-左”旋D、兩個“右-右”旋和一個“左-右”旋正確答案：C35.下面算法所執行的加法次數（）。輸入：n，其中n=2t，t為正整數輸出：kk←0whilen>=1doforj←1tondok=k+1n←n/2returnkA、n2B、nlognC、lognD、2n-1正確答案：D36.元素A,B,C,D依次入棧，出棧無限制，則以下（）是可能的出棧序列。A、C,A,B,DB、B,A,D,CC、B,D,A,CD、A,D,B,C正確答案：B37.Forthefollowingpieceofcodefor(i=0;i<n;i++)for(j=i;j>0;j/=2)printf(“%d\n”,j);thetimecomplexityis:A、O(N×i)B、O(N2)C、O(N)D、O(NlogN)正確答案：D38.二叉樹中第5層（根的層號為1）上的結點個數最多為：A、15B、16C、8D、32正確答案：B39.給定散列表大小為11，散列函數為H(Key)=Key%11。采用平方探測法處理沖突：hi(k)=(H(k)±i2)%11將關鍵字序列{6，25，39，61}依次插入到散列表中。那么元素61存放在散列表中的位置是：A、8B、7C、5D、6正確答案：C40.設有一個12×12的對稱矩陣M，將其上三角部分的元素mi,j（1≤i≤j≤12）按行優先存入C語言的一維數組N中，元素m6,6在N中的下標是：A、50B、51C、55D、66正確答案：A41.對于7個數進行冒泡排序，需要進行的比較次數為：A、7B、21C、14D、49正確答案：B42.設散列表的地址區間為[0,16]，散列函數為H(Key)=Key%17。采用線性探測法處理沖突，并將關鍵字序列{26，25，72，38，8，18，59}依次存儲到散列表中。元素59存放在散列表中的地址是：A、8B、11C、9D、10正確答案：B43.現有長度為7、初始為空的散列表HT，散列函數H(k)=k%7，用線性探測再散列法解決沖突。將關鍵字22,43,15依次插入到HT后，查找成功的平均查找長度是：A、2B、3C、1.5D、1.6正確答案：A44.將線性表La和Lb頭尾連接，要求時間復雜度為O(1)，且占用輔助空間盡量小。應該使用哪種結構？A、帶頭結點的雙循環鏈表B、單循環鏈表C、單鏈表D、帶尾指針的單循環鏈表正確答案：D45.為解決計算機主機與打印機之間速度不匹配問題，通常設置一個打印數據緩沖區，主機將要輸出的數據依次寫入該緩沖區，而打印機則依次從該緩沖區中取出數據。該緩沖區的邏輯結構應該是？A、隊列B、樹C、圖D、堆棧正確答案：A46.對于一個有N個結點、K條邊的森林，共有幾棵樹？A、不能確定B、N?KC、N?K+1D、N?K?1正確答案：B47.表達式a*(b+c)-d的后綴表達式是：A、-+*abcdB、abcd*+-C、abc*+d-D、abc+*d-正確答案：D48.若用大小為6的數組來實現循環隊列，且當前front和rear的值分別為0和4。當從隊列中刪除兩個元素，再加入兩個元素后，front和rear的值分別為多少？A、2和2B、2和4C、2和0D、2和6正確答案：C49.桶排序算法的時間復雜度T(M,N)是多少？voidBucket_Sort(ElementTypeA[],intN){count[]初始化;while(讀入1個學生成績grade)將該生插入count[grade]鏈表;for(i=0;i<M;i++){if(count[i])輸出整個count[i]鏈表;}}A、O(M)B、O(N)C、O(MN)D、O(M+N)正確答案：D50.將M個元素存入用長度為S的數組表示的散列表，則該表的裝填因子為：A、S+MB、M×SC、M/SD、M?S正確答案：C51.已知一棵二叉樹的先序遍歷結果是ABC，則以下哪個序列是不可能的中序遍歷結果：A、ABCB、BACC、CBAD、CAB正確答案：D52.在雙向鏈表存儲結構中，刪除p所指的結點，相應語句為：A、p->next=p->prior->prior;p->prior=p->next->next;B、p->prior=p->prior->prior;p->prior->next=p;C、p->next->prior=p;p->next=p->next->next;D、p->prior->next=p->next;p->next->prior=p->prior;正確答案：D53.數據結構研究的內容是（）。A、數據的邏輯結構B、數據的存儲結構C、建立在相應邏輯結構和存儲結構上的算法D、包括以上三個方面正確答案：D54.對N個記錄進行堆排序，需要的額外空間為：A、O(N)B、O(logN)C、O(1)D、O(NlogN)正確答案：C55.任何一個帶權無向連通圖的最小生成樹——A、有可能不唯一B、有可能不存在C、是唯一的D、是不唯一的正確答案：A56.下面代碼段的時間復雜度是（）。x=n;//n>1y=0;while(x≥(y+1)*(y+1))y++;A、O(n)B、O(1)C、O(n1/2)D、O(log2n)正確答案：C57.堆的形狀是一棵：A、完全二叉樹B、二叉搜索樹C、非二叉樹D、滿二叉樹正確答案：A58.在將數據序列（6,1,5,9,8,4,7）建成大根堆時，正確的序列變化過程是：A、6,9,5,1,8,4,7→6,9,7,1,8,4,5→9,6,7,1,8,4,5→9,8,7,1,6,4,5B、6,9,5,1,8,4,7→9,6,5,1,8,4,7→9,6,7,1,8,4,5→9,8,7,1,6,4,5C、6,1,7,9,8,4,5→6,9,7,1,8,4,5→9,6,7,1,8,4,5→9,8,7,1,6,4,5D、6,1,7,9,8,4,5→7,1,6,9,8,4,5→7,9,6,1,8,4,5→9,7,6,1,8,4,5→9,8,6,1,7,4,5正確答案：C59.在數據結構中，從邏輯上可以把數據結構分成（）。A、線性結構和非線性結構B、緊湊結構和非緊湊結構C、動態結構和靜態結構D、內部結構和外部結構正確答案：A60.下列排序算法中，哪種算法可能出現：在最后一趟開始之前，所有的元素都不在其最終的位置上？（設待排元素個數N>2）A、堆排序B、快速排序C、冒泡排序D、插入排序正確答案：D61.對于有向圖，其鄰接矩陣表示比鄰接表表示更易于：A、進行圖的廣度優先遍歷B、求一個頂點的出邊鄰接點C、進行圖的深度優先遍歷D、求一個頂點的入度正確答案：D62.下面的程序段違反了算法的（）原則。voidsam(){intn=2;while(n%2==0)n+=2;printf(“%d”,n);}A、可行性B、確定性C、有窮性D、健壯性正確答案：C63.圖的深度優先遍歷類似于二叉樹的：A、層次遍歷B、后序遍歷C、中序遍歷D、先序遍歷正確答案：D64.一棵非空二叉樹，若先序遍歷與中序遍歷的序列相同，則該二叉樹▁▁▁▁▁。A、所有結點均無左孩子B、所有結點均無右孩子C、只有一個葉子結點D、為任意二叉樹正確答案：A65.下列程序的時間復雜度為（）。i=0;s=0;while(s<n){i++;s=s+i;}A、Θ(n2)B、Θ(1)C、Θ(n?)D、Θ(n)正確答案：C66.下列幾組概念中，那一組不完全跟搜索引擎有關？A、詞干提取，壓縮，召回率B、閾值設置，動態規劃，準確率C、停用詞，倒排表，動態索引D、分布式索引，哈希散列，倒排文件索引正確答案：B67.創建一個初始堆，含有N個記錄，其時間復雜度是：A、O(N2)B、O(logN)C、O(NlogN)D、O(N)正確答案：D68.將{5,11,13,1,3,6}依次插入初始為空的二叉搜索樹。則該樹的后序遍歷結果是：A、3,1,6,13,11,5B、3,1,5,6,13,11C、1,3,5,6,13,11D、1,3,11,6,13,5正確答案：A69.已知字符集{a,b,c,d,e,f}，若各字符出現的次數分別為{6,3,8,2,10,4}，則對應字符集中各字符的哈夫曼編碼可能是：A、00,1011,01,1010,11,100B、0011,10,11,0010,01,000C、00,100,110,000,0010,01D、10,1011,11,0011,00,010正確答案：A70.給定無向圖G，從V0出發進行深度優先遍歷訪問的邊集合為：{(V0,V1),(V0,V4),(V1,V2),(V1,V3),(V4,V5),(V5,V6)}。則下面哪條邊不可能出現在G中？A、(V0,V6)B、(V4,V6)C、(V1,V5)D、(V0,V2)正確答案：C71.設有1000個元素的有序序列，如果用二分插入排序再插入一個元素，則最大比較次數是：A、1000B、500C、999D、10正確答案：D72.關于存儲結構▁▁▁▁▁的特點是借助指示元素存儲地址的指針來表示數據元素之間的邏輯關系。A、散列存儲結構B、鏈式存儲結構C、順序存儲結構D、索引存儲結構正確答案：B73.兩個有相同鍵值的元素具有不同的散列地址A、可能會B、一定會C、有萬分之一的可能會D、一定不會正確答案：A74.已知一棵二叉樹的前序遍歷結果為ABCDEFG,中序遍歷結果為BCAEDGF,則后序遍歷的結果為（）。A、CBAEGFDB、CBEGFDAC、BCEGFDAD、CBEFGDA正確答案：B75.在用鄰接表表示有N個結點E條邊的圖時，深度優先遍歷算法的時間復雜度為：A、O(N2)B、O(N)C、O(N2×E)D、O(N+E)正確答案：D76.若將n個頂點e條弧的有向圖采用鄰接表存儲，則拓撲排序算法的時間復雜度是：A、O(n)B、O(n+e)C、O(n×e)D、O(n2)正確答案：B77.若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用哪種存儲方式最節省時間？A、雙鏈表B、帶頭結點的雙循環鏈表C、順序表D、單循環鏈表正確答案：C78.對于一個具有N個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是：A、N2B、N?1C、(N?1)2D、N正確答案：A79.如果AVL樹的深度為6（空樹的深度定義為?1），則此樹最少有多少個結點？A、12B、20C、33D、64正確答案：C80.WhichoneofthefollowingisthelowestupperboundofT(n)forthefollowingrecursionT(n)=2T(n/2)+nlogn?A、O(nlog2n)B、O(n2logn)C、O(n2)D、O(nlogn)正確答案：A81.對初始數據序列{8,3,9,11,2,1,4,7,5,10,6}進行希爾排序。若第一趟排序結果為（1,3,7,5,2,6,4,9,11,10,8），第二趟排序結果為（1,2,6,4,3,7,5,8,11,10,9），則兩趟排序采用的增量（間隔）依次是：A、5,3B、3,2C、3,1D、5,2正確答案：A82.算法分析的目的是()A、找出數據結構的合理性B、分析算法的易讀性和文檔性C、研究算法中的輸入和輸出的關系D、分析算法的效率以求改進正確答案：D83.已知有向圖G=(V,E)，其中V={v1,v2,v3,v4,v5,v6}，E={<v1,v2>,<v1,v4>,<v2,v6>,<v3,v1>,<v3,v4>,<v4,v5>,<v5,v2>,<v5,v6>}。G的拓撲序列是：A、v1,v3,v4,v5,v2,v6B、v3,v4,v1,v5,v2,v6C、v1,v3,v4,v5,v2,v6D、v3,v1,v4,v5,v2,v6正確答案：D84.若一棵二叉樹的后序遍歷序列是{1,3,2,6,5,7,4}，中序遍歷序列是{1,2,3,4,5,6,7}，則下列哪句是錯的？A、2是1和3的父結點B、7是5的父結點C、這是一棵二叉搜索樹D、這是一棵完全二叉樹正確答案：D85.設h為不帶頭結點的單向鏈表。在h的頭上插入一個新結點t的語句是：A、h=t;t->next=h;B、h=t;t->next=h->next;C、t->next=h->next;h=t;D、t->next=h;h=t;正確答案：D86.在快速排序的一趟劃分過程中，當遇到與基準數相等的元素時，如果左指針停止移動，而右指針在同樣情況下卻不停止移動，那么當所有元素都相等時，算法的時間復雜度是多少？A、O(N)B、O(logN)C、O(NlogN)D、O(N2)正確答案：D二、多選題（共3題，每題1分，共3分）1.鏈表-時間復雜度在包含n個數據元素的鏈表中，▁▁▁▁▁的時間復雜度為O(n)。A、在第i(1≤i≤n)個結點后插入一個新結點B、訪問第i個數據元素C、將n個元素按升序排序D、刪除第i(1≤i≤n)個結點正確答案：ABD2.非空線性表的結構特征非空線性表具有哪些結構特征？A、除終端結點外，每個結點只有一個后繼結點B、只有唯一的開始結點和唯一的終端結點C、除開始結點外，每個結點只有一個前驅結點D、可擁有多個的開始結點和多個終端結點正確答案：ABC3.排序算法的穩定性下列關于順序表的排序算法中，▁▁▁▁▁是穩定的。A、歸并排序B、快速排序C、冒泡排序D、選擇排序正確答案：AC三、判斷題（共26題，每題1分，共26分）1.若一個棧的輸入序列為{1,2,3,4,5}，則不可能得到{3,4,1,2,5}這樣的出棧序列。A、正確B、錯誤正確答案：A2.用一維數組G[]存儲有4個頂點的無向圖如下：G[]={0,1,0,1,1,0,0,0,1,0}則頂點2和頂點0之間是有邊的。A、正確B、錯誤正確答案：A3.已知一棵二叉樹的先序遍歷結果是ABC,則CAB不可能是中序遍歷結果。A、正確B、錯誤正確答案：A4.在用數組表示的循環隊列中，front值一定小于等于rear值。A、正確B、錯誤正確答案：B5.循環隊列也存在空間溢出的問題。A、正確B、錯誤正