數(shù)據(jù)結(jié)構(gòu)山東聯(lián)盟智慧樹知到超星爾雅網(wǎng)課答案

1、數(shù)據(jù)結(jié)構(gòu)（山東聯(lián)盟） 2019 智慧樹知到超星爾雅網(wǎng)課答案2019智慧樹知到超星爾雅網(wǎng)課答案大全第1章單元測試1 、算法的時間復(fù)雜度取決于 _。答案： A和 B2、數(shù)據(jù)在計(jì)算機(jī)內(nèi)存中的表示是指（）答案：數(shù)據(jù)的存儲結(jié)構(gòu)3、算法指的是（）答案：求解特定問題的指令有限序列4、在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的數(shù)據(jù)結(jié)構(gòu)是（）答案：邏輯7、某線性表采用順序存儲結(jié)構(gòu), 每個元素占4 個存儲單元 , 首地址為 100, 則第 12 個元素的存儲地址為 ( ) 。答案： 1448、算法能正確地實(shí)現(xiàn)預(yù)定功能的特性稱為算法的（）。答案：正確性第2章單元測試1 、鏈表不具備的特點(diǎn)是（ ）。答案：可隨機(jī)訪問任意一個

2、結(jié)點(diǎn)3、線性表的順序存儲表示優(yōu)于鏈?zhǔn)酱鎯Ρ硎?。答案：錯4、順序存儲結(jié)構(gòu)的缺點(diǎn)是不便于修改 , 插入和刪除需要移動很多結(jié)點(diǎn)。答案：對5、在設(shè)頭、尾指針的單鏈表中, 與長度 n 有關(guān)的操作是 ( ) 。答案：刪除最后一個結(jié)點(diǎn)6、設(shè)指針 q 指向單鏈表中結(jié)點(diǎn) A,指針 p 指向單鏈表中結(jié)點(diǎn) A 的后繼結(jié)點(diǎn) B,指針 s 指向被插入的結(jié)點(diǎn) X, 則在結(jié)點(diǎn) A 和結(jié)點(diǎn) B 間插入結(jié)點(diǎn) X 的操作序列為 ( ) 。答案： q>next=s; s>next=p;7、對于只在表的首、尾兩端進(jìn)行插入操作的線性表, 宜采用的存儲結(jié)構(gòu)為 () 。答案：用尾指針表示的循環(huán)單鏈表8、在一個單鏈表中 , 若

3、p 所指節(jié)點(diǎn)不是最后節(jié)點(diǎn) , 在 p 之后插入 s 所指節(jié)點(diǎn) ,則執(zhí)行() 。答案： s>link=p>link;p>link=s;9、在雙向鏈表存儲結(jié)構(gòu)中，刪除p 所指的結(jié)點(diǎn)時須修改指針_。答案： p>next>prior=p>prior; p>prior>next=p>next;10、若事先不知道線性表的長度, 則處理線性表時較好的存儲結(jié)構(gòu)是() 。答案：單鏈表11、向一個有127 個元素的順序表中插入一個新元素并保存順序不變 , 平均要移動 ( ) 個元素。答案： 63.512、某線性表采用順序存儲結(jié)構(gòu), 每個元素占4 個存儲單元址為

4、 100, 則第 12 個元素的存儲地址為( ) 。, 原來, 首地答案： 14413、在一個以h為頭的單循環(huán)鏈表中,p指針指向鏈尾的條件是( ) 。答案： p>next = h14、在表頭指針為 head 且表長大于 1 的單向循環(huán)鏈表中 , 指針 p 指向表中的某個結(jié)點(diǎn) , 若 p>next>next=head, 則( ) 。答案： *p 的直接后繼是尾結(jié)點(diǎn)15、線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址 _。答案：連續(xù)或不連續(xù)都可以16、在單鏈表中 , 指針 p 指向元素為 x 的結(jié)點(diǎn) , 實(shí)現(xiàn)“刪除x 的后繼”的語句是 ( ) 。答案： p>nex

5、t=p>next>next;17、可以用帶表頭結(jié)點(diǎn)的鏈表表示線性表，也可以用不帶表頭結(jié)點(diǎn)的鏈表表示線性表，前者最主要的好處是（）答案：使空表和非空表的處理統(tǒng)一18、與單鏈表相比 , 雙向鏈表的優(yōu)點(diǎn)之一是()。答案：順序訪問相鄰結(jié)點(diǎn)更加靈活19、如果最常用的操作是取第 i 個結(jié)點(diǎn)及其前驅(qū) , 最節(jié)省時間的存儲方式( ) 。答案：順序表21、對順序存儲的線性表, 設(shè)其長度為n, 在任何位置上插入或刪除操作都是等概率的。插入一個元素時平均要移動表中的 ( ) 個元素。答案： n/222、鏈表是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表, 進(jìn)行插入、刪除操作時，在鏈表中比在順序存儲結(jié)構(gòu)中效率高。答案：23、

6、在一個帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中前插入一個新結(jié)點(diǎn), 則需要相繼修改 (答案： 424、具有線性關(guān)系的集合中，若a， b, 若要在 p 所指向的結(jié)點(diǎn)之)個指針域的值。是集合中的任意兩個元素，則必有 a答案：錯第3章單元測試1 、設(shè) abcdef 以所給次序進(jìn)棧，若在進(jìn)棧操作時允許退棧，則下列得不到的序列為（）答案： cabdef2、若已知一個棧的進(jìn)棧序列是p2， p3， pn， 若 p1=3， 則p21，2，3 n，其輸出序列是為（）p1，答案：可能是23、假定循環(huán)隊(duì)列的隊(duì)首和隊(duì)尾指針分別為隊(duì)滿的條件為（）。答案： (rear 1) mod MAXSIZE = = frontfront和rear，

7、則判斷4、隊(duì)列和棧都是運(yùn)算受限的線性表，只允許在表的兩端進(jìn)行運(yùn)算。答案：對6、兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機(jī)會，應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。答案：×7、循環(huán)隊(duì)列A0.m1 存放其元素值，用front和 rear 分別表示隊(duì)頭和隊(duì)尾，則當(dāng)前隊(duì)列中的元素?cái)?shù)是()。答案： (rearfront+m)%m8、不論棧是用數(shù)組實(shí)現(xiàn)，還是用鏈表實(shí)現(xiàn)，入棧和出棧的時間復(fù)雜度均為 O(n) 。答案：錯9、若棧采用順序存儲方式存儲，兩棧共享空間 A1.m ， topi 代表第 i 個棧（ i=1, 2 ）的棧頂，棧 1 的底在 A1 ，棧 2 的底在 Am ，

8、則棧滿的條件是（）。答案： top1+1=top210、輸入序列為ABC，若出棧的順序?yàn)镃BA時，經(jīng)過的棧操作為（ ） 。答案： push,push,push,pop,pop,pop11、棧和隊(duì)都是（）。答案：限制存取點(diǎn)的線性結(jié)構(gòu)13、鏈棧與順序棧相比，有一個比較明顯的優(yōu)點(diǎn)是（）。答案：通常不會出現(xiàn)棧滿的情況14、設(shè)計(jì)一個判別表達(dá)式中左, 右括號是否配對出現(xiàn)的算法, 采用 ()數(shù)據(jù)結(jié)構(gòu)最佳答案：線性表的順序存儲結(jié)構(gòu)第4章單元測試8 、設(shè)有一個 10 階的對稱矩陣 A，采用壓縮存儲方式，以行序?yàn)橹鞔鎯Γ?a11 為第 1 個元素，其存儲地址為1，每個元素占用1個地址空間，則a85 的地址為（）。

9、答案： 339、對于以行為主序的存儲結(jié)構(gòu)來說在數(shù)組Ac1.d1,c2.d2中，c1 和 d1 分別為數(shù)組A 的第一維下標(biāo)的下、上界，c2 和 d2 分別為第二維下標(biāo)的下、上界每個數(shù)據(jù)元素占k 個存儲單元，二維數(shù)組中任一元素ai,j的存儲位置可由（）確定。答案： Loci,j=Locc1,c2+(d2c2+1)(ic1)+(jc2)×k10、 AN， N是對稱矩陣，將下面三角（包括對角線）以行序存儲到一維數(shù)組TN（ N+1）/2 中，則對任一上三角元素aij對應(yīng)Tk 的下標(biāo) k 是答案： j （ j1 ） /2+i11、對矩陣壓縮存儲是為了答案：減少存儲空間第5章單元測試1 、二叉樹是

10、非線性數(shù)據(jù)結(jié)構(gòu)，所以（ ）。答案：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都能存儲4、二叉樹中所有結(jié)點(diǎn)個數(shù)是2k11，其中 k 是樹的深度答案：錯5、二叉樹中每個結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹答案：錯6、在只有度為 0 和度為 2 的二叉樹中 , 設(shè)度為 0 的結(jié)點(diǎn)有 n0 個,度為 2 的結(jié)點(diǎn)有 n2 個, 則有 n0=n2+1。答案：對7、樹中所有結(jié)點(diǎn)的度之和等于所有結(jié)點(diǎn)數(shù)減1。答案：對8、設(shè)森林 F 中有 4 棵樹 , 第 1、 2、3、 4 棵樹的結(jié)點(diǎn)個數(shù)分別為n2、 n3、 n4, 當(dāng)把森林 F 轉(zhuǎn)換成一棵二叉樹后, 其根結(jié)點(diǎn)的左子樹中有 n1 個結(jié)點(diǎn)。答案：錯9、設(shè) Huffman 樹的葉子結(jié)

11、點(diǎn)數(shù)為m,則結(jié)點(diǎn)總數(shù)為2m1。n1、答案：對15、某二叉樹中序序列為 BDAECF,后序序列為 DBEFCA,則二叉樹對應(yīng)的森林包括 ( ) 棵樹。答案： 316、若一棵二叉樹具有 10 個度為 2 的結(jié)點(diǎn) ,5 個度為 1 的結(jié)點(diǎn) , 則度為 0 的結(jié)點(diǎn)的個數(shù)是 ( ) 。答案： 1117、任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對次序 ( ) 。答案：不發(fā)生改變18、設(shè)某棵二叉樹的高度為9,則該二叉樹上葉子結(jié)點(diǎn)最多有( )。答案： 25619、若完全二叉樹的結(jié)點(diǎn)個數(shù)為100,則第60 個結(jié)點(diǎn)的度為( )。答案：020、樹的基本遍歷策略分為先根遍歷和后根遍歷; 二叉樹的基本遍

12、歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里 , 我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對應(yīng)的二叉樹 , 其中結(jié)論 ( ) 是正確的。答案：樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同21、某二叉樹的先序和后序遍歷序列正好相反, 則該二叉樹一定是( ) 。答案：深度等于其結(jié)點(diǎn)數(shù)22、一棵二叉樹的高度為 h, 所有結(jié)點(diǎn)的度或?yàn)?0 或?yàn)?2, 則這棵二叉樹最少有 ( ) 個結(jié)點(diǎn)。答案： 2h123、如果一棵二叉樹中所有結(jié)點(diǎn)的值都大于其左子樹中的所有結(jié)點(diǎn)的值 , 且小于其右子樹中所有結(jié)點(diǎn)的值, 現(xiàn)欲得到各個結(jié)點(diǎn)的遞增序列 , 采用的方法是 ( ) 。答案：中序遍歷24、設(shè) n,m 為一棵二叉

13、樹上的兩個結(jié)點(diǎn) , 在中序遍歷中 ,n 在 m前的條件是 () 。答案： n 在 m的左子樹上25、深度為 5 的二叉樹至多有個結(jié)點(diǎn) ( )答案： 3126、由權(quán)值分別為11 、 8 、 6 、 2、 5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹 , 它的帶權(quán)路徑長度為( ) 。答案： 7127、如果一個完全二叉樹最底下一層為第六層( 根為第一層 ) 且該層共有 8 個葉結(jié)點(diǎn) , 那么該完全二叉樹共有多少個結(jié)點(diǎn)?()答案： 3928、某二叉樹的前序遍歷序列為ABDGCEFH,中序遍歷序列為DGBAECHF,則后序遍歷序列為（) 。答案： GDBEHFCA29、一個具有1025 個結(jié)點(diǎn)的二叉樹的高h(yuǎn) 為（ ）答

14、案： 11 到 1025 之間30、設(shè)森林中有三棵樹, 第一、二、三棵樹的結(jié)點(diǎn)個數(shù)分別為n2、 n3, 那么將森林轉(zhuǎn)換成二叉樹后, 其根結(jié)點(diǎn)的右子樹上有n1、( ) 個結(jié)點(diǎn)。答案： n2+n3第6章單元測試1 、任何一個無向連通圖的最小生成樹 （ ） 。答案：有一棵或多棵2、用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時，通常是采用來實(shí)現(xiàn)算法的。答案：隊(duì)列3、在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（）倍。答案： 14、已知有向圖 G = (V, E) ，其中 V=V1， V2， V3， V4，V5， V6， V7,E=<V1 ， V2>， <V1， V3>,<

15、;V1， V4>,<V2， V5>,<V3， V5>,<V3，V6>,<V4， V6>,<V5，V7>,<V6，V7>，G的拓?fù)溆行蛐蛄惺牵ǎ?。答案?V1，V3，V4，V6，V2，V5，V75、對于含有n 個頂點(diǎn)的帶權(quán)連通圖，它的最小生成樹是指圖中任意一個（）。答案：由 n 個頂點(diǎn)構(gòu)成的邊的權(quán)值之和最小的連通子圖6、用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間與圖中結(jié)點(diǎn)的個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。答案：對7、如果有向圖的所有頂點(diǎn)可以構(gòu)成一個拓?fù)渑判?，則說明該有向圖存在回路。答案：錯8、一個非

16、空圖可以沒有邊，但不能沒有頂點(diǎn)。答案：對9、有 n1 條邊的圖肯定都是生成樹。答案：錯第7章單元測試1、有一個有序表為1 ， 3，9， 12，32， 41， 45，62， 75， 77，82， 95， 100 ，當(dāng)用二分法查找值82 的結(jié)點(diǎn)時，（）次比較后查找成功。答案： 27、若根據(jù)查找表建立長度為m的哈希表，采用線性探測法處理沖突，假定對一個元素第一次計(jì)算的哈希地址為d，則下一次的哈希地址為()。答案： (d+1)%m8、若根據(jù)查找表 (23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13計(jì)算哈希地址，則元素64 的哈希地址為 () 。答案： 129、從具有

17、n 個結(jié)點(diǎn)的二叉排序樹中查找一個元素時，在最壞情況下的時間復(fù)雜度為() 。答案： O(n)10、對具有 n 個元素的有序表采用折半查找，則算法的時間復(fù)雜度為() 。答案： O(log2n)11、對于長度為18 的順序存儲的有序表，若采用折半查找，則查找第 15 個元素的比較次數(shù)為() 。答案： 412、二叉排序樹的左右子樹都是二叉排序樹。答案：對13、 1. 若查找每個元素的概率相等，則在長度為 n 的順序表上查找任一元素的平均查找長度為 ( ) 。答案： n+1/2第8章單元測試1 、69、 如果對 n 個元素進(jìn)行直接選擇排序，則進(jìn)行任一趟排序的進(jìn)程中，為尋找最小值元素所需要的時間復(fù)雜度為（

18、）答案： O(n)3、下列排序算法中，其中（）是穩(wěn)定的。答案：歸并排序，冒泡排序4、下列序列中，（）是執(zhí)行第一趟快速排序后所得的序列。答案： 27 ，38，18 49 93，735、(15 ， 9，7，8，20， 1， 4) 進(jìn)行排序，第一趟排序后的序列變?yōu)?1 ，9， 7， 8，20，15，4) ，則采用的排序方法是（）。答案：簡單選擇排序8、從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的排序方法稱為（）。答案：插入排序9、從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為（）。答案：選擇排序10、對 m個不同的關(guān)鍵字由小到大進(jìn)行冒泡排序，當(dāng)（）時比較的次數(shù)最多。答案：從大到小排列11、 69、 一組記錄的關(guān)鍵碼為（46，79， 56， 38， 40，84），則利用快速排序的方法，以第一個記