?？啤稊?shù)據(jù)結(jié)構(gòu)》-試卷-答案

?？啤稊?shù)據(jù)結(jié)構(gòu)》一、（共75題，共150分）lo數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)內(nèi)部存儲表示稱為為數(shù)據(jù)的（）。（2分）Ao數(shù)據(jù)結(jié)構(gòu) Bo邏輯關(guān)系物理結(jié)構(gòu) D.數(shù)據(jù)元素的內(nèi)部結(jié)構(gòu).標(biāo)準(zhǔn)答案:C2。 （）是數(shù)據(jù)的不可分割的最小單位?（2分）Ao數(shù)據(jù)對象B數(shù)據(jù)元素 Co數(shù)據(jù)類型 Do數(shù)據(jù)項(xiàng)。標(biāo)準(zhǔn)答案：D算法的時(shí)間復(fù)雜度是對算法（）的度量。（2分）Ao時(shí)間效率Bo空間效率Co可讀性 D.健壯性。標(biāo)準(zhǔn)答案:A（）是限制了插入和刪除操作在一端進(jìn)行的線性表?（2分）A.棧 B隊(duì)列C.串 D.數(shù)組麻準(zhǔn)答案:A5。 數(shù)組通常采用順序存儲的優(yōu)點(diǎn)是（）。（2分）Ao便于增加存儲空間 Bo便于依據(jù)下標(biāo)進(jìn)行隨機(jī)存取Co避免數(shù)據(jù)元素的移動 D.防止下標(biāo)溢出麻準(zhǔn)答案：B6o采用帶頭結(jié)點(diǎn)雙向鏈表存儲的線性表,在插入一個(gè)元素時(shí)，需要修改指針（）次。（2分）l Bo2 C.3 Do4麻準(zhǔn)答案:D7O線性表的順序存儲結(jié)構(gòu)是一種（）的存儲結(jié)構(gòu)。（2分）A.順序存取 Bo隨機(jī)存取 C.索引存取D.Hash存取.標(biāo)準(zhǔn)答案:E8。 數(shù)組a[1..256]采用順序存儲口的首地址為10,每個(gè)元素占2字節(jié)，則a[21]的地址是（）。（2分）10 B.30Co50 D.70。標(biāo)準(zhǔn)答案：C深度為4的二叉樹，第4層至少有（）個(gè)結(jié)點(diǎn)。（2分）A.OB.l Co8 Do15麻準(zhǔn)答案：B10o若二叉樹對應(yīng)的二叉鏈表共有11個(gè)非空鏈域，則該二叉樹有（）個(gè)結(jié)點(diǎn)的二叉樹?（2分）A.10Bo11Co20Do21.標(biāo)準(zhǔn)答案：A下面敘述錯(cuò)誤的是（）。（2分）A。借助于隊(duì)列可以實(shí)現(xiàn)對二叉樹的層遍歷B棧的特點(diǎn)是先進(jìn)后出Co對于單鏈表進(jìn)行插入操作過程中不會發(fā)生上溢現(xiàn)象在無向圖的鄰接矩陣中每行1的個(gè)數(shù)等于對應(yīng)的頂點(diǎn)度.標(biāo)準(zhǔn)答案：C以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是()。(2分)A。循環(huán)隊(duì)列Bo雙向鏈表 C.哈希表 Do數(shù)組.標(biāo)準(zhǔn)答案：D13o在一個(gè)長度為n的鏈?zhǔn)疥?duì)列中入隊(duì)實(shí)現(xiàn)算法的時(shí)間復(fù)雜度為().(2分)Ao0(1) B.O(logn)C.O(n) D.O(n2)o標(biāo)準(zhǔn)答案：A在具有2個(gè)葉子的二叉樹中，必有()個(gè)度數(shù)為2的結(jié)點(diǎn)。(2分)Ao4 Bo3 Co2 D.l.標(biāo)準(zhǔn)答案：D在關(guān)鍵字序列(10,15,20,25,30)中采用折半法查找20,依次與()關(guān)鍵字進(jìn)行了比較。(2分)Ao30,20 B.30,10,20 C.40,20 D.20.標(biāo)準(zhǔn)答案：B16某二叉樹的后序遍歷序列和和中序遍歷序列分別為cbda和bead,該二叉樹的前序遍歷序列是()。(2分)A.cbdaBodebaC.abcdD.dcbao標(biāo)準(zhǔn)答案：C4個(gè)頂點(diǎn)的無向連通圖的生成樹，至少有()個(gè)邊。(2分)A.OBo1 C.2 D.3。標(biāo)準(zhǔn)答案：D可以采用()這種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)圖的深度優(yōu)先遍歷運(yùn)算。(2分)Ao隊(duì)列B樹Co棧Do集合.標(biāo)準(zhǔn)答案:C19o設(shè)單鏈表中指針p指向結(jié)點(diǎn)A,q指向新兀素結(jié)點(diǎn)，若要A之后插入一個(gè)新元素，則所需修改指針的操作為()。(2分)Aop->next=q,q一〉next=p一>nextB.q—>next=p->next,p->next=qC.p一〉next=q—>next,q->next=pDop->next=p,q—〉next=p一〉next.標(biāo)準(zhǔn)答案:E20.序列(21,19,37,5,2)經(jīng)簡單選擇排序法由小到大排序，在第一趟后所得結(jié)果為().(2分)A.(19,21,5,2,37)Bo(21,19,5,37,2)Co(21,19,2,5,37)Do(37,21,19,5,2).標(biāo)準(zhǔn)答案：C21o單鏈表可作為()的存儲結(jié)構(gòu)。(2分)Ao線性表 B棧 C.隊(duì)列 D.廣義表.標(biāo)準(zhǔn)答案:A,B,C在下列排序方法中，()的平均時(shí)間復(fù)雜度為O(n2)。其中，n為參加排序的元素個(gè)數(shù)。(2分)A。選擇排序 B?？焖倥判駽。直接插入排序 D。冒泡排序.標(biāo)準(zhǔn)答案：A,C,D下列各項(xiàng)鍵值()序列是大頂堆的。(2分)A。{23,68,94,16,5B°{94,68,23,16,5C.{94,23,68,16,5 D.{94,16,68,23,5。標(biāo)準(zhǔn)答案:B,C下列是二叉樹4種常見的遍歷方法。其中,()屬于深度優(yōu)先遍歷。(2分)A.前序遍歷 B.中序遍歷 C.后序遍歷 D。層序遍歷。標(biāo)準(zhǔn)答案：A,B,C若已知一個(gè)棧的入棧序列是(1,2,3,4),其可能出棧序列為()。(2分)A.(1,4,2,3) B.(3,4,1,2)C。(4,3,2,1) D°(2,3,4,1).標(biāo)準(zhǔn)答案：C,D物理結(jié)構(gòu)的在計(jì)算機(jī)內(nèi)部的基本存儲表示方法有()種。(2分)A。2 B。3 C。4 D.5.標(biāo)準(zhǔn)答案：A數(shù)據(jù)元素的存儲結(jié)構(gòu),通常采用()。(2分)A.順序結(jié)構(gòu) B.鏈?zhǔn)浇Y(jié)構(gòu)C。順序和鏈?zhǔn)浇M合結(jié)構(gòu) D.散列結(jié)構(gòu).標(biāo)準(zhǔn)答案：A28。 算法的空間復(fù)雜度是對算法()的度量。(2分)A.時(shí)間效率B?？臻g效率C.可讀性 D。健壯性。標(biāo)準(zhǔn)答案：B線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí),要求結(jié)點(diǎn)的存儲單元地址()。(2分)A。必須是連續(xù)的 B。部分地址必須是連續(xù)的C.必須是不連續(xù)的 D.連續(xù)或不連續(xù)都可以。標(biāo)準(zhǔn)答案:D()是限制了插入和刪除操作分別在兩端進(jìn)行的線性表。(2分)A。棧B。隊(duì)列C.串 D。數(shù)組.標(biāo)準(zhǔn)答案:B串通常采用塊鏈存儲的優(yōu)點(diǎn)是()。 (2分)A.防止聯(lián)接操作溢出 B。提高運(yùn)算效率C。避免數(shù)據(jù)元素的移動 D.提高存儲效率。標(biāo)準(zhǔn)答案:D采用順序存儲的線性表,若表長為9,在刪除第4號元素時(shí),需要移動()個(gè)元素。(2分)A。0 B。4 C.5D。9。標(biāo)準(zhǔn)答案：C數(shù)組采用順序存儲，a的首地址為1024，每個(gè)元素占2字節(jié)，則a[1]的地址是()。(2分)A。1024 B。1026 C.1028 D.1030

。標(biāo)準(zhǔn)答案：A34。 深度為4的二叉樹最多有()個(gè)結(jié)點(diǎn)。(2分)A。1 B.3C。7 D.15。標(biāo)準(zhǔn)答案：D35。 3個(gè)結(jié)點(diǎn)的二叉樹,其對應(yīng)的二叉鏈表共有()個(gè)非空鏈域。(2分)A.2 B.3 C.4 D。5。標(biāo)準(zhǔn)答案：C36。 下面敘述錯(cuò)誤的是().(2分)A。 借助于?？梢詫?shí)現(xiàn)對圖的深度優(yōu)先遍歷對矩陣進(jìn)行壓縮存儲后無法實(shí)現(xiàn)對其元素進(jìn)行隨機(jī)訪問樹的結(jié)點(diǎn)度是指結(jié)點(diǎn)的分支數(shù)D。 空串的長度為零.標(biāo)準(zhǔn)答案：B37。 以下數(shù)據(jù)結(jié)構(gòu)中,()是線性結(jié)構(gòu).(2分)A.二維數(shù)組B。二叉樹 C。特殊矩陣D。棧.標(biāo)準(zhǔn)答案：D38。 在一個(gè)長度為n的鏈?zhǔn)綏Ｖ谐鰲?shí)現(xiàn)算法的時(shí)間復(fù)雜度為().(2分)TOC\o"1-5"\h\zA。 O(1)B。 O(logn)C。 O(n)D。。標(biāo)準(zhǔn)答案：A39。 在具有4個(gè)葉子的二叉樹中,必有()個(gè)度數(shù)為2的結(jié)點(diǎn).(2分)A.4 B。3 C。2 D。1.標(biāo)準(zhǔn)答案：B40。 在關(guān)鍵字序列(10,15,20,25,30)中,采用折半法查找25,關(guān)鍵字之間比較需要()次。 (2分)A.1 B.2 C.3 D。4.標(biāo)準(zhǔn)答案：B41。 某二叉樹的后序遍歷序列和和中序遍歷序列分別為cba和bca,該二叉樹的前序遍歷序列是()。(2分)A.cbaB.bcaC.abcD。acb。標(biāo)準(zhǔn)答案：C42。 4個(gè)頂點(diǎn)的無向連通網(wǎng)的最小成本樹,至少有()個(gè)邊。(2分)A。0 B。1 C.2D。3。標(biāo)準(zhǔn)答案：D43。 可以采用()這種數(shù)據(jù)結(jié)構(gòu),實(shí)現(xiàn)二叉樹的層次遍歷運(yùn)算。(2分)A.隊(duì)列B。樹C.棧D。集合.標(biāo)準(zhǔn)答案:A44。 線性表采用帶頭結(jié)點(diǎn)單鏈表實(shí)現(xiàn)，head為頭指針，則判斷表空的條件為()。(2分)A.B.C.Do.標(biāo)準(zhǔn)答案：C45。在關(guān)鍵字序列（149,138,165,197,176,113,127）中采用最低位優(yōu)先排序（LSD）基數(shù)排序，第一趟之后所得結(jié)果為（）。（2分）Ao149,138,165,197,176,113,127Bo128,149,165,197,113,176,127Co128,149,165,197,113,127,176Do113,127,138,149,165,176,197。標(biāo)準(zhǔn)答案：B46o算法分析的內(nèi)容是對算法的（）分析.（2分）A.時(shí)間效率B空間效率Co可行性 D.正確性.標(biāo)準(zhǔn)答案：A,B47o在n個(gè)數(shù)據(jù)元素中進(jìn)行查找，（）方法的平均時(shí)間復(fù)雜度為0（logn）。（2分）A.順序查找 Bo折半查找C.二叉排序樹查找 Do分塊查找.標(biāo)準(zhǔn)答案：B,C下列各項(xiàng)鍵值（）序列不是堆的.（2分）A.{94,68,23,16,5Bo{94,23,68,5,16{94,23,16,68,5D。{94,16,68,23,5。標(biāo)準(zhǔn)答案:C,D下列（）是限制了插入和刪除操作的特殊線性表。（2分）Ao棧Bo隊(duì)列Co串Do數(shù)組.標(biāo)準(zhǔn)答案:A,E下列（）哈希函數(shù)構(gòu)造方法所得的哈希函數(shù)，使得查找時(shí)間復(fù)雜度通常不能到達(dá)0（l）o （2分）A.直接定地法B數(shù)字分析法Co平方取中法Do折疊法。標(biāo)準(zhǔn)答案：B,C,D數(shù)據(jù)的邏輯結(jié)構(gòu)是由（）部分組成的。（2分）2 B.3 Co4 D.5。標(biāo)準(zhǔn)答案：A下列時(shí)間復(fù)雜度中，（）表示的復(fù)雜度是最高的。（2分）AoO（n2）CoO（n）o標(biāo)準(zhǔn)答案：B棧和隊(duì)列的共同點(diǎn)是（）。（2分）A.進(jìn)出原則都是先進(jìn)先出B進(jìn)出原則都是后進(jìn)先出Co都是插入刪除操作受限的線性表Do不允許在任意端點(diǎn)處插入和刪除元素。標(biāo)準(zhǔn)答案:C54。 （）是限制了數(shù)據(jù)元素的內(nèi)部結(jié)構(gòu)僅為一個(gè)字符的線性表?（2分）Ao棧Bo隊(duì)列C.串Do數(shù)組。標(biāo)準(zhǔn)答案：B二維數(shù)組通常采用順序存儲，其優(yōu)點(diǎn)是（）。（2分）Ao便于增加存儲空間 Bo防止下標(biāo)溢出Co避免數(shù)據(jù)元素的移動 D.便于依據(jù)下標(biāo)進(jìn)行隨機(jī)存取.標(biāo)準(zhǔn)答案：D56O下列給出的操作中，（）是允許對隊(duì)列進(jìn)行的操作.（2分）A.刪除隊(duì)首元素 Bo取出最近進(jìn)隊(duì)的元素Co按元素大小排序 Do中間插入元素。標(biāo)準(zhǔn)答案：A57。 采用帶頭結(jié)點(diǎn)的單鏈表存儲的線性表，若表長為9,在第4號元素之前插入一個(gè)元素時(shí)，需要移動指針（）次?（2分）Ao1 B.2 C.3 Do4.標(biāo)準(zhǔn)答案：C58。 數(shù)組采用順序存儲，a的首地址為1024,每個(gè)元素占4字節(jié)，則a[17]的地址是（）.（2分）Ao1040Bo1056Co1072D。1088.標(biāo)準(zhǔn)答案：D59。 深度為4的二叉樹，第4層最多有（）個(gè)結(jié)點(diǎn)。（2分）Ao0B.l Co8 Do15。標(biāo)準(zhǔn)答案：C60o若二叉樹對應(yīng)的二叉鏈表共有4個(gè)非空鏈域,則該二叉樹有（）個(gè)結(jié)點(diǎn)的二叉樹。（2分）A.2 B.3 Co4 Do5.標(biāo)準(zhǔn)答案：B61.下面敘述錯(cuò)誤的是（）.（2分）A。借助于隊(duì)列可以實(shí)現(xiàn)對圖的廣度優(yōu)先遍歷Bo二叉樹中序遍歷的序列是有序Co只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0D.空格串是指由1個(gè)或以上的空格符號組成的串。標(biāo)準(zhǔn)答案:E62o以下（）術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)（2分）A.串B哈希表Co線索樹 D.單鏈表。標(biāo)準(zhǔn)答案：A63o在一個(gè)長度為n的鏈?zhǔn)疥?duì)列中出隊(duì)實(shí)現(xiàn)算法的時(shí)間復(fù)雜度為（）。（2分）A.0（1）BoO（logn）CoO（n）D。O（n2）o標(biāo)準(zhǔn)答案：A64.在具有4個(gè)度數(shù)為2的二叉樹中，必有（）個(gè)葉子結(jié)點(diǎn)。（2分）Ao2 Bo3 C.4 D.5。標(biāo)準(zhǔn)答案：D65。在關(guān)鍵字序列（10，15,20,25，30）中采用折半法查找25，依次與（）關(guān)鍵字進(jìn)行了比較。（2分）A.30，25 B。20,25 C。20,30，25D.25.標(biāo)準(zhǔn)答案：B66。 某二叉樹的前序遍歷序列和和中序遍歷序列分別為abc和bca，該二叉樹的后序遍歷序列是（）。（2分）A.cbaB。bcaC.abc D。acb。標(biāo)準(zhǔn)答案：A67。 4個(gè)頂點(diǎn)的無向圖，最多有（）個(gè)邊。（2分）A。3 B。4 C.5 D.6。標(biāo)準(zhǔn)答案：D68。 可以采用（）這種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)表達(dá)式中左右括號是否配對出現(xiàn)判別的運(yùn)算。（2分）A.隊(duì)列 B。樹 C.棧 D。集合。標(biāo)準(zhǔn)答案：C69。 假設(shè)以數(shù)組A[0。.n-1]存放循環(huán)隊(duì)列的元素，其頭指針front指向隊(duì)頭元素、尾指針rear指向隊(duì)尾元素一個(gè)，則在少用一個(gè)元素空間的前提下，隊(duì)列空的判定條件為（）。（2分）A。B。C.D..標(biāo)準(zhǔn)答案:A70。 在關(guān)鍵字序列（35,10,15,20,25）中采用最低位優(yōu)先排序（LSD）基數(shù)排序，第一趟之后所得結(jié)果為（）。（2分）A.10,20，15， 25， 35 B.10， 20， 35，15， 25C.20，10,35， 25， 15 D.20， 10， 35,15,25.標(biāo)準(zhǔn)答案：B71。 算法具有的5個(gè)特性，（）均為算法的特性之一。（2分）A.有窮性 B.確定性 C?？尚行訢。正確性.標(biāo)準(zhǔn)答案:A,B,C72。 在下列數(shù)據(jù)結(jié)構(gòu)中，（）屬于非線性結(jié)構(gòu)。（2分）A。串 B.棧 C.樹