數(shù)據(jù)結(jié)構(gòu)Ⅰ學(xué)習(xí)通超星期末考試答案章節(jié)答案2024年

數(shù)據(jù)結(jié)構(gòu)Ⅰ學(xué)習(xí)通超星期末考試章節(jié)答案2024年3、以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，出棧操作必須判別棧空的情況。

答案:對1、棧和隊(duì)列都是受限的線性結(jié)構(gòu)。

答案:對4、在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。

答案:錯(cuò)2、在單鏈表中，要訪問某個(gè)結(jié)點(diǎn)，只要知道該結(jié)點(diǎn)的地址即可；因此，單鏈表是一種隨機(jī)存取結(jié)構(gòu)。

答案:錯(cuò)5、對于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。

答案:對4、設(shè)循環(huán)隊(duì)列的容量為70，現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)操作后，front為20，rear為11，則隊(duì)列中元素的個(gè)數(shù)為_______。

答案:611、設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5,e6依次通過棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e2,e4,e3,e6,e5,e1，則棧的容量至少應(yīng)該是_______。

答案:35、已知循環(huán)隊(duì)列的存儲(chǔ)空間大小為20，且當(dāng)前隊(duì)列的頭指針和尾指針的值分別為8和3，且該隊(duì)列的當(dāng)前的長度為_______。

答案:152、一個(gè)循環(huán)隊(duì)列Q的存儲(chǔ)空間大小為M,其隊(duì)頭和隊(duì)尾指針分別為front和rear，則循環(huán)隊(duì)列中元素的個(gè)數(shù)為：_______。

答案:(rear-front+M3、設(shè)計(jì)一個(gè)判別表達(dá)式中括號是否配對的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。

答案:棧順序結(jié)構(gòu)實(shí)現(xiàn)的循環(huán)隊(duì)列，刪除一個(gè)元素時(shí)，位置指針的變化是

答案:front+=16、一個(gè)順序棧S，其棧頂指針為top，則將元素e入棧的操作是（）。

答案:*S->top=e;S->top++;8、五節(jié)車廂以編號1，2，3，4，5順序進(jìn)入鐵路調(diào)度站（棧），可以得到（）的編組。

答案:3，5，4，2，19、在一個(gè)鏈隊(duì)列中，front和rear分別為頭指針和尾指針，則插入一個(gè)結(jié)點(diǎn)s的操作為（）。

答案:rear->next=s;rear=s;10、依次在初始為空的隊(duì)列中插入元素a,b,c,d以后，緊接著做了兩次刪除操作，此時(shí)的隊(duì)頭元素是（）。

答案:c4、若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)rear和front的值分別為0，3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為（）。

答案:2和45、循環(huán)隊(duì)列的隊(duì)頭和隊(duì)尾指針分別為front和rear，則判斷循環(huán)隊(duì)列為空的條件是（）。

答案:front==rear2、判斷一個(gè)循環(huán)隊(duì)列Q（最多n個(gè)元素）為滿的條件是（）。

答案:Q->front==(Q->rear+1)%n1、一個(gè)棧的輸入序列為：a，b，c，d，e，則棧不可能輸出的序列是（）。

答案:d,c,e,a,b7、三元素組表中的每個(gè)結(jié)點(diǎn)對應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的________、________和________。

答案:行下標(biāo);列下標(biāo);元素值2、廣義表運(yùn)算式HEAD(TAIL((a,b,c),(x,y,z)))的結(jié)果是：________。

答案:(x,y,z6、設(shè)數(shù)組a[1…60,1…70]的基地址為2048，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[32,58]的存儲(chǔ)地址為________。

答案:89503、二維數(shù)組，可以按照________________兩種不同的存儲(chǔ)方式。

答案:按行優(yōu)先和按列優(yōu)先5、設(shè)矩陣A是一個(gè)對稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角部分按行序存放在一維數(shù)組B[1,n(n-1)/2]中，對下三角部分中任一元素ai,j(i>=j)，在一維數(shù)組B的下標(biāo)位置k的值是（）。

答案:i(i-1)/2+j7、采用稀疏矩陣的三元組表形式進(jìn)行壓縮存儲(chǔ)，若要完成對三元組表進(jìn)行轉(zhuǎn)置，只要將行和列對換，這種說法（）。

答案:錯(cuò)誤8、常對數(shù)組進(jìn)行兩種基本操作是（）。

答案:查找和修改9、對一些特殊矩陣采用壓縮存儲(chǔ)的目的主要是為了（）。

答案:減少不必要的存儲(chǔ)空間的開銷2、廣義表((a),a)的表尾是（）。

答案:(a)2.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于1。

答案:錯(cuò)5.二叉樹中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。

答案:錯(cuò)1.若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹鏈表中只有n-1個(gè)非空指針域。

答案:對4.二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。

答案:錯(cuò)3.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。

答案:對2、哈夫曼樹是其樹的帶權(quán)路徑長度________的二叉樹。

答案:最小1、具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度是________。

答案:?log2n?+13、在一棵二叉樹中，度為0的結(jié)點(diǎn)的個(gè)數(shù)是n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，則有n0=____。

答案:n2+15、按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有________種。

答案:57、將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層上從左到右依次對結(jié)點(diǎn)進(jìn)行編號，根結(jié)點(diǎn)的編號為1，則編號為49的結(jié)點(diǎn)的左孩子編號為________。

答案:989、假定一棵二叉樹，度為2的結(jié)點(diǎn)數(shù)為15，度為1的結(jié)點(diǎn)數(shù)為30，則葉子結(jié)點(diǎn)數(shù)為（）。

答案:167、在線索二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是（）。

答案:t->ltag==115、某二叉樹的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結(jié)點(diǎn)數(shù)目為

答案:414、根據(jù)使用頻率為5的字符設(shè)計(jì)的哈夫曼編碼不可能是（）

答案:00，100，101，110，1118、任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對次序（）。

答案:不發(fā)生改變12、樹的先根序列等同于與該樹對應(yīng)的二叉樹的（）。

答案:先序序列6、樹最適合用來表示（

）。

答案:元素之間具有分支層次關(guān)系的數(shù)據(jù)6、判定一個(gè)有向圖是否存在回路，可以利用________。

答案:拓?fù)渑判?、一個(gè)連通圖的生成樹是一個(gè)_____，它包含圖中所有頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊。

答案:極小連通子圖5、在散列存儲(chǔ)中，裝填因子α的值越大，則存取元素時(shí)發(fā)生沖突的可能性就越_______；α值越小，則存取元素發(fā)生沖突的可能性就越_______。

答案:大;小3、一組待排序序列為（46,79,56,38,40,84），則利用堆排序的方法建立的初始堆為______________。

答案:84,79,56,38,40,464、遍歷圖的基本方法有深度優(yōu)先搜索和廣度優(yōu)先搜索，其中________是一個(gè)遞歸過程。

答案:深度優(yōu)先搜索8、若一組記錄的排序碼值序列為{50，80，30，40，70，60}利用快速排序方法，以第一個(gè)記錄為基準(zhǔn)，得到一趟快速排序的結(jié)果為_______。

答案:40,30,50,80,70,6010、高度為6的平衡二叉排序樹，其每個(gè)分支結(jié)點(diǎn)的平衡因子均為0，則該二叉樹共有_____個(gè)結(jié)點(diǎn)。

答案:636、有一個(gè)有序表為{1,3,9,12,32,41,45,62,75,77,82,95,100}，當(dāng)折半查找值為82的結(jié)點(diǎn)時(shí)，需進(jìn)行_______次比較后查找成功。

答案:310、對一組整數(shù){60，40，90，20，10，70，50，80}進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)整數(shù)50插入到有序表中時(shí)，為尋找插人位置需比較_______次。

答案:45、設(shè)哈希表長m=14，哈希函數(shù)H(key)=keyMOD11。表中已有4個(gè)結(jié)點(diǎn)：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7其余地址為空，如用二次探測再散列處理沖突，則關(guān)鍵字為49的地址為（）。

答案:93、關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（）。

答案:從源點(diǎn)到匯點(diǎn)的最長路徑5、快速排序方法在（）情況下最不利于發(fā)揮其長處。

答案:要排序的數(shù)據(jù)已基本有序9、在對n個(gè)元素的序列進(jìn)行排序時(shí)，堆排序所需要的附加存儲(chǔ)空間是（）。

答案:O(1)2、如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定是（）。

答案:連通圖1、若需要在O(nlog2n)的時(shí)間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（）。

答案:歸并排序8、在各種查找方法中，平均查找承擔(dān)與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是（）。

答案:哈希查找10、對線性表進(jìn)行折半查找時(shí)，要求線性表必須（）存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序。

答案:以順序方式7、在任何情況下，時(shí)間復(fù)雜度均為O(nlogn)的不穩(wěn)定的排序方法是（）。

答案:堆排序6、在散列查找中，平均查找長度主要與（）