數(shù)據(jù)結(jié)構(gòu)期中考試試題及答案

1、數(shù)據(jù)結(jié)構(gòu)期中考試試題及答案1.在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的基本單位是（）A.數(shù)據(jù)項(xiàng).數(shù)據(jù)元素（正確答案）C.數(shù)據(jù)對(duì)象D.數(shù)據(jù)文件.數(shù)據(jù)結(jié)構(gòu)是（）A. 一種數(shù)據(jù)類型B.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C. 一組性質(zhì)相同的數(shù)據(jù)元素的集合D.相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合（正確答案）.在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為（）A.內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)B.靜態(tài)結(jié)構(gòu)與動(dòng)態(tài)結(jié)構(gòu)C.線性結(jié)構(gòu)與非線性結(jié)構(gòu)（正確答案）D.緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)。.算法指的是（）0A.計(jì)算機(jī)程序.解決問(wèn)題的計(jì)算方法C.排序算法D.解決問(wèn)題的有限運(yùn)算序列（正確答案）.算法分析的目的是（）A.區(qū)分?jǐn)?shù)據(jù)結(jié)構(gòu)的合理性評(píng)價(jià)算法的效率（正確答案）C.研

2、究算法中輸入與輸出的關(guān)系D.鑒別算法的可讀性ABCDBCDACDBADCBA(正確答案)48.對(duì)一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹按層序編號(hào)，那么編號(hào)為49的結(jié)點(diǎn)，它 的左孩子的編號(hào)為()9998 (正確答案)9750.有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，其結(jié)點(diǎn)總數(shù)是()2m-1 (正確答案)2m2m+l2(m+l).廣義表中元素分為()A.原子元素B.表元素C.原子元素和表元素(正確答案)D.任意元素.廣義表 A=(), (a), (b, (c, d)的長(zhǎng)度為()23(正確答案)4552. 一棵深度為6的二叉樹至多有()個(gè)結(jié)點(diǎn)6432c. 31（正確答案）D. 6353.將含100個(gè)結(jié)點(diǎn)的完全二叉樹從根第

3、一層開始，每層上從左到右依次對(duì)結(jié) 點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為1,編號(hào)為49的結(jié)點(diǎn)X的雙親編號(hào)為（）24（正確答案）2523D.無(wú)法確定.鏈表適用于（）查找A.順序（正確答案）B.二分法C.順序，也能二分法D.隨機(jī).在順序表中，只要知道（），就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址A.基地址B.結(jié)點(diǎn)大小C.向量大小D.基地址和結(jié)點(diǎn)大小（正確答案）.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)A.隨機(jī)存?。ㄕ_答案）B.順序存取C.索引存取D.散列存取.數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存儲(chǔ)器中的表示是指（）A.數(shù)據(jù)結(jié)構(gòu)B.數(shù)據(jù)元素之間的關(guān)系C.數(shù)據(jù)的邏輯結(jié)構(gòu)D.數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)（正確答案）58.對(duì)二叉樹的結(jié)點(diǎn)從1開始編

4、號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左孩子（如果 有的話）的編號(hào)，而小于其右（孩子如果有的話）的編號(hào)，那么可以采用（B）次序的遍歷 實(shí)現(xiàn)二叉樹的結(jié)點(diǎn)編號(hào)A.先序B.中序（正確答案）C.后序D.層次遍歷59.（）是一棵滿二叉樹A.二叉排序樹B.深度為5有31個(gè)結(jié)點(diǎn)的二叉樹（正確答案）C.有15個(gè)結(jié)點(diǎn)的完全二叉樹D.哈夫曼（Huffman）樹60.某二叉樹結(jié)點(diǎn)的中序序列為BDAECF,后序序列為DBEFCA,那么該二叉樹對(duì)應(yīng) 的森林包括（）棵樹123（正確答案）D. 4.某程序的時(shí)間復(fù)雜度為3n+nlog2n+rf2+8,其數(shù)量級(jí)表示為（）0（n）0（nlog2n）0（rf2）（正確答案）0（log2n）

5、.以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？（）A.隊(duì)列.棧C.線性表D.二叉樹（正確答案）.設(shè)順序表有9個(gè)元素，那么在第3個(gè)元素前插入一個(gè)元素所需移動(dòng)元素的個(gè) 數(shù)為（）567 （正確答案）9.線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（）A.必須是連續(xù)的必須是局部連續(xù)的C. 一定是不連續(xù)的D.連續(xù)和不連續(xù)都可以（正確答案）10.線性表是具有相同數(shù)據(jù)類型的n個(gè)（）的有限序列A.數(shù)據(jù)項(xiàng)B.數(shù)據(jù)元素（正確答案）C.表兀素D.字符.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí) 間復(fù)雜度是（）0（1）0（n）（正確答案）0（rT2）0 （nlog2n）.用鏈接方式存儲(chǔ)的隊(duì)列，在

6、進(jìn)行插入運(yùn)算時(shí)（）A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針（正確答案）D.頭、尾指針可能都要修改.在長(zhǎng)度為n的順序表中刪除第i個(gè)元素（IWiWn）時(shí)，元素移動(dòng)的次數(shù)為n-i+1ii+1n-i （正確答案）.假設(shè)帶頭結(jié)點(diǎn)的單鏈表的頭指針為head,那么該鏈表為空的判定條件是（）head二二NULLhead-nextNULL （正確答案）head!=NULLhead-next-head.棧的最大容量為4。假設(shè)進(jìn)棧序列為1, 2, 3, 4, 5, 6,且進(jìn)棧和出棧 可以穿插進(jìn)行，那么可能出現(xiàn)的出棧序列為（）A. 5, 4, 3, 2,A. 5, 4, 3, 2,1, 6B. 2, 3

7、, 5, 6, 1, 4C. 3, 2, 5, 4,C. 3, 2, 5, 4,1, 6（正確答案）D. 1, 4, 6, 5, 2,.假設(shè)某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素, 那么采用O存儲(chǔ)方式最節(jié)省時(shí)間A.單鏈表B.雙鏈表C.單向循環(huán)D.順序表（正確答案）.對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（）方面的內(nèi)容A.健壯性和可讀性B.并行性（正確答案）C.正確性D.時(shí)空復(fù)雜度.隊(duì)列的刪除操作是在（）進(jìn)行A.隊(duì)首（正確答案）B.隊(duì)尾C.隊(duì)前D.對(duì)后.計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象被統(tǒng)稱為（）A.數(shù)據(jù)（正確答案）B.數(shù)據(jù)元素C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)類型.串是任意有限個(gè)（）A.符號(hào)構(gòu)成

8、的序列B.符號(hào)構(gòu)成的集合C.字符構(gòu)成的序列（正確答案）D.字符構(gòu)成的集合.如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，那么退棧操作時(shí)（）A.必須判別棧是否滿B.對(duì)棧不作任何判別C.必須判別棧是否空（正確答案）D.判別棧元素的類型.隊(duì)列的插入操作是在（）進(jìn)行A.隊(duì)首B.隊(duì)尾（正確答案）C.隊(duì)前D.對(duì)后. 一棵具有5層滿二叉樹中節(jié)點(diǎn)總數(shù)為（）A、31（正確答案）B、32C、33D、16.廣義表是線性表的推廣，它們之間的區(qū)別在于（）A.能否使用子表（正確答案）B.能否使用原子項(xiàng)C.表的長(zhǎng)度D.是否能為空.與線性表相比，串的插入和刪除操作的特點(diǎn)是（）A.通常以串整體作為操作對(duì)象（正確答案）B.需要更多的輔助空間C.算

9、法的時(shí)間復(fù)雜度較高D.涉及移動(dòng)的元素更多.假設(shè)帶頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針為head,那么該鏈表為空的判定條件 是（）A.head二二NULLB.head - next=NULLC.head!=NULLD.head - next= 二head （正確答案）.在單鏈表中，指針p指向值為x的結(jié)點(diǎn)，能實(shí)現(xiàn)“刪除x的后繼”的語(yǔ)句 是（）p=p-next;p=p-next-next;p-next=p;p-next=p-next-next;（正確答案）. 一個(gè)棧的入棧序列是a, b, c, d, e,那么棧的輸出序列不可能是（）dceab （正確答案）decbaedcbaabcde.假設(shè)進(jìn)棧序列為a,

10、b, c,進(jìn)棧過(guò)程中允許出棧，那么以下O是不可能得到 的出棧序列a, b, cb, a, cc, a, b （正確答案）c, b, a.假設(shè)進(jìn)棧序列為1, 2, 3, 4,進(jìn)棧過(guò)程中允許出棧，那么可能的出棧序列是（）2, 4, 1, 33, 1, 4, 23, 4, 1, 21, 2, 3, 4（正確答案）.設(shè)有一個(gè)棧，按A、B、C、D的順序進(jìn)棧，那么可能為出棧序列的是（）DCBA （正確答案）CDABC. DBACD. DCAB. 一個(gè)最多能容納m個(gè)元素的順序存儲(chǔ)循環(huán)隊(duì)列Q,其頭尾指針?lè)謩e為 front和rear,那么判定該隊(duì)列為滿的條件是()(Q. rear+1)% m=Q. front

11、(正確答案)Q. front=Q. rearQ rear+l=Q. front(Q. front+l)%m=Q. rear.設(shè)數(shù)組Datam作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear 為隊(duì)尾指針，那么執(zhí)行出隊(duì)操作的語(yǔ)句為()front=front+lfront= (front+1)% m(正確答案)rear=(rear+1)%mfront=(front+1)%(m+1). 60.廣義表 A： ( ), (a), (b, (c, d)的深度為().(答案：undefined).假設(shè)以數(shù)組An存放循環(huán)隊(duì)列的元素，其頭、尾指針?lè)謩e為front和 rearo假設(shè)設(shè)定尾指針指向隊(duì)列中的隊(duì)

12、尾元素，頭指針指向隊(duì)列中隊(duì)頭元素的前一個(gè) 位置，那么當(dāng)前存于隊(duì)列中的元素個(gè)數(shù)為()(rear-front-1) %n(rear-front) %n(front-rear+1) %n(rear-front+n)%n(正確答案).假設(shè)用一個(gè)大小為6的一維數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的 值分別為0和3o當(dāng)從隊(duì)里中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的 值分別是()1 和 55 和 12 和 44和2(正確答案)37.兩個(gè)字符串相等的條件是（）A.串的長(zhǎng)度相等B.含有相同的字符集C.都是非空串D.串的長(zhǎng)度相等且對(duì)應(yīng)的字符相同（正確答案）38.如下陳述中正確的選項(xiàng)是（）

13、A.串是一種特殊的線性表（正確答案）B.串的長(zhǎng)度必須大于零C.串中元素只能是字母D.空串就是空格串一棵含18個(gè)結(jié)點(diǎn)的二叉樹的高度至少為（）345（正確答案）640.將一棵有40個(gè)結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編 號(hào)，根結(jié)點(diǎn)的編號(hào)為1,那么編號(hào)為15的結(jié)點(diǎn)的左孩子的編號(hào)為（）1630（正確答案）313241.在程序的執(zhí)行過(guò)程中，對(duì)實(shí)現(xiàn)函數(shù)的遞歸調(diào)用應(yīng)該借助于（）結(jié)構(gòu)A.線性表B.棧（正確答案）C.隊(duì)列D.樹42.具有100個(gè)結(jié)點(diǎn)的完全二叉樹的深度為（）A. 6B.7 （正確答案）89.二叉樹的先序遍歷序列為ABDECF,中序遍歷序列為DBEAFC,那么后序 遍歷序列為（）DEBAFCDEFBCADEBCFADEBFCA（