數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)測試卷

第頁數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)測試卷1.冒泡排序的方法對n個數(shù)據(jù)進行排序，第一趟排序共需要比較（）次。A、1B、2C、n-1D、n【正確答案】：C2.在一棵具有五層的滿二叉樹中，結(jié)點的點數(shù)為（）。A、16B、31C、32D、33【正確答案】：B3.樹最適合用來表示（）。A、有序數(shù)據(jù)元素B、無序數(shù)據(jù)元素C、元素之間無聯(lián)系的數(shù)據(jù)D、元素之間有分支的層次關(guān)系【正確答案】：D4.線性表是具有n個（）的有限序列（n>0）。A、表元素B、字符C、數(shù)據(jù)元素D、數(shù)據(jù)項【正確答案】：C5.算法能正確的實現(xiàn)預(yù)定功能的特性稱為算法的（）。A、正確性B、易讀性C、健壯性D、高效性【正確答案】：A6.在順序表示的環(huán)形隊列中，paqu是指向隊列的指針，判斷隊列是否為空的語句是（）。A、paqu->f==0；B、paqu->r==0；C、paqu->f==paqu->r；D、（paqu->r+1）%MAXNUM==paqu->f【正確答案】：D7.設(shè)front、rear分別為循環(huán)雙向鏈表結(jié)點的左指針和右指針，則指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是（）。A、P==LB、P->front==LC、P==NULLD、P->rear==L【正確答案】：D8.以下關(guān)于線性表的論述，不正確的是（）。A、線性表中的元素可以是數(shù)字、字符、記錄等不同類型B、線性順序表中包含的元素個數(shù)不是任意的C、線性表中的每個結(jié)點都有且僅有一個直接前驅(qū)和一個直接后繼D、存在這樣的線性表，即表中沒有任何結(jié)點【正確答案】：C9.一個有N個頂點的有向圖最多有（）條邊。A、NB、N（N-1）C、N（N-1）/2D、2N【正確答案】：B10.元素A、B、C、D依次進隊以后，隊頭元素是（）。ABCD【正確答案】：A11.設(shè)有一個入棧的次序A、B、C、D、E，則棧不可能的輸出序列是（）。A、EDCBAB、DECBAC、DCEABD、ABCDE【正確答案】：C12.深度為k的滿二叉樹有____個葉子結(jié)點。A、2k-1B、C、2k+1D、2k-1+1【正確答案】：B13.用鏈表存儲的線性表，其優(yōu)點是（）。A、便于隨機存取B、花費的存儲空間比順序表少C、便于插入和刪除D、數(shù)據(jù)元素的物理順序與邏輯順序相同【正確答案】：C14.在圖的表示法中，表示形式唯一的是（）。A、鄰接矩陣表示法B、鄰接表表示法C、逆鄰接表表示法D、鄰接表和逆鄰接表表示法【正確答案】：A15.圖的廣度優(yōu)先遍歷類似于二叉樹的（）。A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷【正確答案】：D16.插入和刪除操作只能在一端進行的線性表，稱為（）。A、隊列B、循環(huán)隊列C、棧D、循環(huán)?！菊_答案】：C17.評價排序算法好壞的標(biāo)準主要是（）。A、執(zhí)行時間B、輔助空間C、算法本身的復(fù)雜度D、執(zhí)行時間和所需的輔助空間【正確答案】：D18.在有n個結(jié)點的順序表上做插入、刪除結(jié)點運算的時間復(fù)雜度為（）。A、O（1）B、O（n）C、O(n2)D、O(log2n)【正確答案】：B19.下列排序方法中，（）是不穩(wěn)定的。A、折半插入排序B、快速排序C、歸并排序D、冒泡排序【正確答案】：B20.數(shù)據(jù)項是（）。A、數(shù)據(jù)的基本單位B、數(shù)據(jù)的最小單位C、一個結(jié)點D、一個記錄【正確答案】：B21.把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（）。A、唯一的B、有多種C、有多種，但根結(jié)點都沒有左孩子D、有多種，但根結(jié)點都沒有右孩子【正確答案】：A22.元素A、B、C、D依次進棧以后，棧底元素是（）。ABCD【正確答案】：A23.在雙鏈表的一個結(jié)點中有（）。A、0個指針B、1個指針C、2個指針D、3個指針【正確答案】：C24.在一個具有n個頂點的無向圖中，要連通全部頂點至少需要（）條邊。A、nB、n+1C、n-1D、n/2【正確答案】：C25.鏈表不具有的特點是（）。A、插入、刪除不需要移動元素B、可隨機訪問任一元素C、不必事先估計存儲空間D、所需空間與線性長度成正比【正確答案】：B26.算法分析的兩個主要方面是（）。A、空間復(fù)雜性和時間復(fù)雜性B、正確性和簡明性C、可讀性和文檔性D、數(shù)據(jù)復(fù)雜性和程序復(fù)雜性【正確答案】：A27.在一個長度為n的順序存儲的線性表中，刪除第i個元素（0≤i≤n-1）時，需要從前向后依次前移()個元素。A、n-iB、n-i+1C、n-i-1D、I【正確答案】：C28.()又是一棵滿二叉樹。A、二叉排序樹B、深度為5有31個結(jié)點的二叉樹C、有15個結(jié)點的完全二叉樹D、哈夫曼(Huffman)樹【正確答案】：C29.有n(n>0)個結(jié)點的完全二叉樹的深度是____。A、élog2(n)ùB、élog2(n)+1ùC、?log2(n+1)?D、?log2(n)+1?【正確答案】：D30.每一個存儲結(jié)點不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是（）。A、順序B、鏈式C、索引D、散列【正確答案】：B31.具有100個結(jié)點的完全二叉樹的深度為()。A、6B、7C、8D、9【正確答案】：B32.根據(jù)二叉樹的定義，具有3個結(jié)點的二叉樹有（）種樹型。A、3B、4C、5D、6【正確答案】：C33.兩個指針P和Q，分別指向單向鏈表的兩個元素，P所指元素是Q所指元素直接后繼的條件是（）。A、P->next==Q->nextB、P->next==QC、Q->next==PD、P==Q【正確答案】：C34.排序是根據(jù)（）的大小重新安排各元素的順序。A、關(guān)鍵字B、數(shù)組C、元素件D、結(jié)點【正確答案】：A35.數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的（）及它們之間的相互關(guān)系。A、存儲結(jié)構(gòu)和邏輯結(jié)構(gòu)B、存儲和抽象C、聯(lián)系和抽象D、聯(lián)系與邏輯【正確答案】：A36.在棧中存取數(shù)據(jù)的原則是（）。A、先進先出B、先進后出C、后進后出D、隨意進出【正確答案】：B37.同一隊列內(nèi)的各元素的類型（）。A、必須一致B、不能一致C、可以不一致D、不限制【正確答案】：A38.隊和棧的主要區(qū)別是（）。A、邏輯結(jié)構(gòu)不同B、存儲結(jié)構(gòu)不同C、所包含的運算個數(shù)不同D、限定插入和刪除的位置不同【正確答案】：D39.下列數(shù)據(jù)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)。A、棧B、隊列C、完全二叉樹D、堆【正確答案】：C40.在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的（）倍。A、1/2B、1C、2D、4【正確答案】：C41.已知二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為()。A、DEBAFCB、DEFBCAC、DEBFCADEBCFA【正確答案】：C42.表達式a?[b+c]-d的后綴表達式是()。A、abcd?+-B、abc+?d-C、abc?+d-D、-+?abcd【正確答案】：B43.圖的深度優(yōu)先遍歷類似于二叉樹的（）。A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷【正確答案】：A44.在隊列中存取數(shù)據(jù)的原則是（）。A、先進先出B、先進后出C、后進先出D、隨意進出【正確答案】：A45.有8個結(jié)點的有向完全圖有（）條邊。A、14B、28C、56D、112【正確答案】：C46.數(shù)據(jù)在計算機存儲內(nèi)表示時，物理地址和邏輯地址相同并且是連續(xù)的，稱之為（）。A、存儲結(jié)構(gòu)B、邏輯結(jié)構(gòu)C、順序存儲結(jié)構(gòu)D、鏈式存儲結(jié)構(gòu)【正確答案】：C47.下列算法的時間復(fù)雜度是（）。for(i=0;i<n;i++)for(j=o;i<n;j++)c[i][j]=i+j;A、O（1）B、O（n）C、(log2n)D、O(n2)【正確答案】：D48.任何一棵二叉樹的葉結(jié)點在前序、中序、后序遍歷序列中的相對次序（）。A、不發(fā)生改變B、發(fā)生改變C、不能確定D、以上都不對【正確答案】：A49.下面程序段的時間復(fù)雜度為____________。for(inti=0;i<m;i++)for(intj=0;j<n;j++)A[i][j]=i?j;A、O(m2)B、O(n2)C、O(m?n)D、O(m+n)【正確答案】：C50.兩個指針P和Q，分別指向單向鏈表的兩個元素，P所指元素是Q所指元素前驅(qū)的條件是（）A、P->next==Q->nextB、P->next==QC、Q->next==PD、P==Q【正確答案】：B51.已知二維數(shù)組A[6][10]，每個數(shù)組元素占4個存儲單元，若按行優(yōu)先順序存儲存放數(shù)組元素a[3][5]的存儲地址是1000，則a[0][0]的存儲地址是（）。A、872B、860C、868D、864【正確答案】：B52.已知一個順序存儲的線性表，設(shè)每個結(jié)點占m個存儲單元，若第一個結(jié)點的地址為B，則第i個結(jié)點的地址為（）。A、B+(i-1)×mB+i×mC、B-i×mD、B+(i+1)×m【正確答案】：A53.在單鏈表中，增加頭結(jié)點的目的是（）。A、使單鏈表至少有一個結(jié)點B、標(biāo)志表中首結(jié)點的位置C、方便運算的實現(xiàn)D、說明該單鏈表是線性表的鏈式存儲結(jié)構(gòu)【正確答案】：C54.在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。A、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C、線性結(jié)構(gòu)和非線性結(jié)構(gòu)D、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)【正確答案】：C55.插入和刪除操作只能在一端進行的線性表，稱為（）。A、隊列B、順序棧C、棧D、循環(huán)?！菊_答案】：C56.元素A、B、C、D依次進棧以后，棧頂元素是（）。ABCD【正確答案】：D57.在順序表中，只要知道（），就可以求出任一結(jié)點的存儲地址。A、基地址B、結(jié)點大小C、向量大小D、基地址和結(jié)點大小【正確答案】：D58.鏈表不具備的特點是（）。A、隨機訪問B、不必事先估計存儲空間C、插入刪除時不需要移動元素D、所需空間與線性表成正比【正確答案】：A59.4個元素按A、B、C、D順序連續(xù)進隊Q，則隊尾元素是（）ABCD【正確答案】：D60.二叉樹中第5層上的結(jié)點個數(shù)最多為()。A、8B、15C、16D、32【正確答案】：C1.算法是對解題方法和步驟的描述。（）A、正確B、錯誤【正確答案】：A2.算法在發(fā)生非法操作時可以作出相應(yīng)處理的特性稱為算法的健壯性。（）A、正確B、錯誤【正確答案】：A3.除了插入和刪除以外，數(shù)組的操作還有存取、修改、檢索和排序。（）A、正確B、錯誤【正確答案】：A4.從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。（）A、正確B、錯誤【正確答案】：A5.在?？盏那闆r下，不能作出棧操作，否則產(chǎn)生上溢。（）A、正確B、錯誤【正確答案】：B6.鏈表的每個結(jié)點都恰好包含一個指針域。（）A、正確B、錯誤【正確答案】：B7.鏈隊列在一定范圍內(nèi)不會出現(xiàn)隊滿的情況。（）A、正確B、錯誤【正確答案】：A8.一個算法應(yīng)具有有窮性，確定性，可行性，輸入和輸出這五個特性。（）A、正確B、錯誤【正確答案】：A9.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）A、正確B、錯誤【正確答案】：B10.如果某種排序算法不穩(wěn)定，則該排序方法就沒有實用價值。（）A、正確B、錯誤【正確答案】：B11.圖可以沒有邊，但不能沒有頂點。（）A、正確B、錯誤【正確答案】：A12.在無向圖中，[v1，v2]與[v2，v1]是兩條不同的邊。（）A、正確B、錯誤【正確答案】：B13.完全二叉樹一定是滿二叉樹。（）A、正確B、錯誤【正確答案】：B14.二分查找法要求待查表的關(guān)鍵字值必須有序。（）A、正確B、錯誤【正確答案】：A15.鏈表的每個結(jié)點都恰好包含一個指針域。（）A、正確B、錯誤【正確答案】：B16.二分查找法要求待查表的關(guān)鍵字值必須有序。（）A、正確B、錯誤【正確答案】：A17.線性結(jié)構(gòu)的基本特征是：每個結(jié)點有且僅有一個直接前驅(qū)和一個直接后繼。（）A、正確B、錯誤【正確答案】：B18.采用希爾排序時，若原始關(guān)鍵字的排列雜亂無序，則效率最低。（）A、正確B、錯誤【正確答案】：B19.數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)實際的存儲形式。（）A、正確B、錯誤【正確答案】：A20.一個圖具有生成樹的必要條件是該圖必須是連通圖。（）A、正確B、錯誤【正確答案】：B21.隊列的特點是“先進先出”。（）A、正確B、錯誤【正確答案】：A22.數(shù)組元素可以由若干數(shù)據(jù)項組成。（）A、正確B、錯誤【正確答案】：A23.數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)是相同的。（）A、正確B、錯誤【正確答案】：B24.隊列是限制在兩端進行操作的線性表。（）A、正確B、錯誤【正確答案】：A25.樹結(jié)構(gòu)中每個結(jié)點最多只有一個直接前驅(qū)。（）A、正確B、錯誤【正確答案】：A26.在完全二叉樹中，若一個結(jié)點沒有左孩子，則它必然是葉子結(jié)點。（）A、正確B、錯誤【正確答案】：A27.冒泡排序是不穩(wěn)定的排序。（）A、正確B、錯誤【正確答案】：B28.線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲。（）A、正確B、錯誤【正確答案】：B29.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）A、正確B、錯誤【正確答案】：B30.滿二叉樹一定是完全二叉樹，而完全二叉樹不一定是滿二叉樹。（）A、正確B、錯誤【正確答案】：A填空題1.在非空二叉樹的i層上，至多有_____（）___個結(jié)點。（）【正確答案】：2i|i>=02.順序表中訪問任意一個結(jié)點的時間復(fù)雜度均為（））?！菊_答案】：O（13.大多數(shù)排序算法都有兩個基本的操作：（）和移動?！菊_答案】：比較4.在樹中，一個結(jié)點所擁有的子樹數(shù)稱為該結(jié)點的__（）__。【正確答案】：度5.在隊列中，允許刪除的一端稱為（））?！菊_答案】：隊首（或隊頭6.已知序列（），按照順序插入法建立一棵二叉排序列樹，該樹的深度是____（）__________?！菊_答案】：54，76，34，45，18，26，92，65，|47.隊列的特點是____（）_______?！菊_答案】：_先進先出8.在隊列中，允許進行插入操作的一端稱為____（）___?！菊_答案】：隊尾9.在隊列中，允許插入的一端稱為（）?！菊_答案】：隊尾10.在一個長度為n的順序表中刪除第i（）個元素，要移動（）個元素?！菊_答案】：1<=i<=n|n-i11.若進棧的次序是A、B、C、D、E，執(zhí)行3次出棧操作以后，棧頂元素為（）?！菊_答案】：B12.數(shù)據(jù)結(jié)構(gòu)的三個要素分別是邏輯結(jié)構(gòu)、_（）_和操作。【正確答案】：存儲結(jié)構(gòu)13.在棧中，允許進行刪除操作的一端稱為____（）___?！菊_答案】：棧頂14.線性結(jié)構(gòu)中的元素之間存在（）的關(guān)系?！菊_答案】：一對一15.樹中結(jié)點的最大層次稱為樹的（））?！菊_答案】：深度（或高度16.允許在線性表一端插入，另一端進行刪除操作的線性表稱為____（）