東北大學(xué)23春“計(jì)算機(jī)科學(xué)與技術(shù)”《數(shù)據(jù)結(jié)構(gòu)Ⅱ》考試高頻考點(diǎn)參考題庫帶答案

長風(fēng)破浪會(huì)有時(shí)，直掛云帆濟(jì)滄海。東北大學(xué)23春“計(jì)算機(jī)科學(xué)與技術(shù)”《數(shù)據(jù)結(jié)構(gòu)Ⅱ》考試高頻考點(diǎn)參考題庫帶答案（圖片大小可自由調(diào)整）第I卷一.綜合考核(共15題)1.一棵左右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個(gè)數(shù)是()。A.0B.1C.2D.32.已知二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為A.DEFBCAB.DEBFCAC.DEBCFAD.DEBAFC3.設(shè)一個(gè)棧的輸入序列為1、2、3、4、5，則借助一個(gè)棧所得到的輸出序列不可能是()。A.23415B.54132C.23145D.154324.連通網(wǎng)的最小生成樹是其所有生成樹中()。A.頂點(diǎn)集最小的生成樹B.邊集最小的生成樹C.頂點(diǎn)權(quán)值之和最小的生成樹D.邊的權(quán)值之和最小的生成樹5.若允許表達(dá)式內(nèi)多種括號(hào)混合嵌套，則為檢查表達(dá)式中括號(hào)是否正確配對(duì)的算法，通常選用的輔助結(jié)構(gòu)是()。A.棧B.線性表C.隊(duì)列D.二叉排序樹6.對(duì)于順序存儲(chǔ)的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為()。A.O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)7.倒排文件的主要優(yōu)點(diǎn)是()。A.便于進(jìn)行插入和刪除運(yùn)算B.便于進(jìn)行文件的恢復(fù)C.便于進(jìn)行多關(guān)鍵字查詢D.節(jié)省存儲(chǔ)空間8.若采用孩子兄弟鏈表作為樹的存儲(chǔ)結(jié)構(gòu)，則樹的后序遍歷應(yīng)采用二叉樹的()。A.層次遍歷算法B.前序遍歷算法C.中序遍歷算法D.后序遍歷算法9.樹有先根遍歷和后根遍歷，樹可以轉(zhuǎn)化為對(duì)應(yīng)的二叉樹。下面的說法正確的是A.樹的后根遍歷與其對(duì)應(yīng)的二叉樹的后根遍歷相同B.樹的后根遍歷與其對(duì)應(yīng)的二叉樹的中根遍歷相同C.樹的先根遍歷與其對(duì)應(yīng)的二叉樹的中根遍歷相同D.以上都不對(duì)10.在下列各種文件中，不能進(jìn)行順序查找的文件是()。A.順序文件B.索引文件C.散列文件D.多重表文件11.以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語是()。A.循環(huán)隊(duì)列B.鏈表C.哈希表D.棧12.在計(jì)算機(jī)內(nèi)實(shí)現(xiàn)遞歸算法時(shí)所需的輔助數(shù)據(jù)結(jié)構(gòu)是A.隊(duì)列B.樹C.棧D.圖13.二維數(shù)組A按行優(yōu)先順序存儲(chǔ)，其中每個(gè)元素占1個(gè)存儲(chǔ)單元。若A[1][1]的存儲(chǔ)地址為420，A[3][3]的存儲(chǔ)地址為446，則A[5][5]的存儲(chǔ)地址為()。A.470B.471C.472D.47314.在目標(biāo)串T[0..n-1]=“xwxxyxy”中，對(duì)模式串P[0..m-1]=“xy”進(jìn)行子串定位操作的結(jié)果是()。A.1B.2C.3D.515.在以單鏈表為存儲(chǔ)結(jié)構(gòu)的線性表中，數(shù)據(jù)元素之間的邏輯關(guān)系用()。A.數(shù)據(jù)元素的相鄰地址表示B.數(shù)據(jù)元素在表中的序號(hào)表示C.指向后繼元素的指針表示D.數(shù)據(jù)元素的值表示第II卷一.綜合考核(共15題)1.對(duì)長度為n的關(guān)鍵字序列進(jìn)行堆排序的空間復(fù)雜度為()。A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)2.連通圖是指圖中任意兩個(gè)頂點(diǎn)之間()。A.都連通的無向圖B.都不連通的無向圖C.都連通的有向圖D.都不連通的有向圖3.對(duì)于哈希函數(shù)H(key)=key%13，被稱為同義詞的關(guān)鍵字是()。A.35和41B.23和39C.15和44D.25和514.棧和隊(duì)列都是A.順序存儲(chǔ)的線性結(jié)構(gòu)B.限制存取位置的非線性結(jié)構(gòu)C.限制存取位置的線性結(jié)構(gòu)D.鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)5.引入二叉線索樹的目的是A.加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B.使二叉樹的遍歷結(jié)果唯一C.為了能方便的找到雙親D.為了能在二叉樹中方便的進(jìn)行插入與刪除6.在一個(gè)單鏈表中，若刪除*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行操作()。A.q=p->next;p->next=q->next;free(q)B.p=p->next;p->next=p->next->next;free(p)C.p->next=q->next;free(p->next)D.p=p->next->next;free(p->next)7.下列說法正確的是：(1)二叉樹按某種方式線索化后，任一節(jié)點(diǎn)均有指向前趨和后繼的線索;(2)二叉樹的前序遍歷序列中，任意一個(gè)節(jié)點(diǎn)均處于在子孫節(jié)點(diǎn)前;(3)二叉排序樹中任一節(jié)點(diǎn)的值大于其左孩子的值，小于右孩子的值。A.(1)(2)(3)B.(1)(2)C.(1)(3)D.前面的可選答案都不對(duì)8.如果在數(shù)據(jù)結(jié)構(gòu)中每個(gè)數(shù)據(jù)元素只可能有一個(gè)直接前驅(qū)，但可以有多個(gè)直接后繼，則該結(jié)構(gòu)是()。A.棧B.隊(duì)列C.樹D.圖9.下面關(guān)于線性表的敘述中，錯(cuò)誤的是A.線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B.線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作C.線性表采用鏈接存儲(chǔ)，便于插入和刪除操作D.線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元10.為使平均查找長度達(dá)到最小，當(dāng)由關(guān)鍵字集合{05，11，21，25，37，40，41，62，84}構(gòu)建二叉排序樹時(shí)，第一個(gè)插入的關(guān)鍵字應(yīng)為()。A.5B.37C.41D.6211.希爾排序的增量序列必須是()。A.遞增的B.隨機(jī)的C.遞減的D.非遞減的12.在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是A.隊(duì)列B.線性表C.棧D.有序表13.若X是二叉中序線索樹中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，則x的前驅(qū)為()。A.X的雙親B.X的右子樹中最左的結(jié)點(diǎn)C.X的左子樹中最右結(jié)點(diǎn)D.X的左子樹中最右葉結(jié)點(diǎn)14.抽象數(shù)據(jù)類型的三個(gè)組成部分分別為()。A.數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本操作B.數(shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)C.數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素和數(shù)據(jù)類型D.數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型15.對(duì)長度為15的有序順序表進(jìn)行二分查找，在各記錄的查找概率均相等的情況下，查找成功時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)的平均值為A.55/15B.51/15C.49/15D.39/15第III卷一.綜合考核(共15題)1.倒排文件的主要優(yōu)點(diǎn)是A.節(jié)省存儲(chǔ)空間B.便于進(jìn)行文件的恢復(fù)C.便于進(jìn)行插入和刪除運(yùn)算D.便于進(jìn)行多關(guān)鍵字查詢2.下列編碼中屬于前綴編碼的是()。A.{1，01，000，001}B.{1，01，011，010}C.{0，10，110，11}D.{0，1，00，11}3.一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹最少的結(jié)點(diǎn)數(shù)有A.h+1B.2h-1C.2h+1D.2h4.如果求一個(gè)連通圖中以某個(gè)頂點(diǎn)為根的高度最小的生成樹，應(yīng)采用()。A.深度優(yōu)先搜索算法B.廣度優(yōu)先搜索算法C.求最小生成樹的prim算法D.拓?fù)渑判蛩惴?.n個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有()。A.n-1條有向邊B.n條有向邊C.n(n-1)/2條有向邊D.n(n-1)條有向邊6.下面說法錯(cuò)誤的是(1)算法原地工作的含義是指不需要任何額外的輔助空間(2)在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度O(2n)的算法(3)所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界(4)同一個(gè)算法，實(shí)現(xiàn)語言的級(jí)別越高，執(zhí)行效率就越低A.(1),(4)B.(1),(2)C.(3)D.(1)7.在一個(gè)帶權(quán)連通圖G中，權(quán)值最小的邊一定包含在G的A.深度優(yōu)先生成森林中B.深度優(yōu)先生成樹中C.最小生成樹中D.廣度優(yōu)先生成樹中8.三維數(shù)組A[4][5][6]按行優(yōu)先存儲(chǔ)方法存儲(chǔ)在內(nèi)存中，若每個(gè)元素占2個(gè)存儲(chǔ)單元，且數(shù)組中第一個(gè)元素A[0][0][0]的存儲(chǔ)地址為120，則元素A[3][4][5]的存儲(chǔ)地址為()。A.356B.358C.360D.3629.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為兩大類，即A.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)B.線性結(jié)構(gòu)、非線性結(jié)構(gòu)C.動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)D.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)10.已知廣義表LS=((a，b，c)，(d，e，f))，運(yùn)算head和tail函數(shù)取出元素e的運(yùn)算是()。A.head(tail(LS))B.tail(head(LS))C.head(tail(head(tail(LS))))D.head(tail(tail(head(LS))))11.下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)A.插入運(yùn)算方便B.存儲(chǔ)密度大C.可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示D.刪除運(yùn)算方便12.將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是()。A.nB.2n-1C.2nD.n-113.稠密索引是在索引表中()。A.為每個(gè)記錄建立一個(gè)索引項(xiàng)B.為每個(gè)頁塊建立一個(gè)索引項(xiàng)C.為每組記錄建立一個(gè)索引項(xiàng)D.為每個(gè)字段建立一個(gè)索引項(xiàng)14.快速排序在最壞情況下的時(shí)間復(fù)雜度是A.O(nlog2n)B.O(n2log2n)C.O(n2)D.O(log2n)15.棧是一種操作受限的線性結(jié)構(gòu)，其操作的主要特征是()。A.先進(jìn)先出B.后進(jìn)先出C.進(jìn)優(yōu)于出D.出優(yōu)于進(jìn)第I卷參考答案一.綜合考核1.參考答案：B2.參考答案：A3.參考答案：B4.參考答案：D5.參考答案：A6.參考答案：C7.參考答案：C8.參考答案：C9.參考答案：B10.參考答案：C11.參考答案：D12.參考答案：C13.參考答案：C14.參考答案：C15.參考答案：C第II卷參考答案一.綜合考核1.參考答案：B2.參考答案：A3.參考答案：D4.參考答案：C5.參考答案：A6.參考答案：A7.參考答案：D8.參考