數(shù)據(jù)結(jié)構(gòu)（綿陽師范學(xué)院）智慧樹知到期末考試答案2024年

數(shù)據(jù)結(jié)構(gòu)（綿陽師范學(xué)院）智慧樹知到期末考試答案2024年數(shù)據(jù)結(jié)構(gòu)（綿陽師范學(xué)院）算法的時(shí)間復(fù)雜度表征的是（）。

A:執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間B:算法的難易程度C:執(zhí)行算法所耗費(fèi)的時(shí)間D:算法的可讀性答案:執(zhí)行算法所耗費(fèi)的時(shí)間在雙向鏈表中，一個(gè)結(jié)點(diǎn)包含（）個(gè)指針。

A:3B:4C:2D:1答案:2用直接插入排序方法對(duì)下面4個(gè)序列進(jìn)行排序(由小到大)，元素比較次數(shù)最少的是()。

A:30，40，22，46．69，93，90，80B:93，30，40，90，80，46，22，69C:22，30，46，40，80，69，90，93D:90，69，80，46，22，30，93，40答案:22，30，46，40，80，69，90，93在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素，而且要存儲(chǔ)（）。

A:數(shù)據(jù)元素的類型B:數(shù)據(jù)的操作方法C:數(shù)據(jù)元素之間的關(guān)系D:數(shù)據(jù)的存取方法答案:數(shù)據(jù)元素之間的關(guān)系數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)在計(jì)算機(jī)中的映像分別稱為結(jié)構(gòu)、結(jié)點(diǎn)、（）。

A:數(shù)據(jù)域B:數(shù)據(jù)范圍C:數(shù)據(jù)庫D:數(shù)據(jù)單位答案:數(shù)據(jù)域設(shè)有100個(gè)元素的有序表，采用折半查找方法，在等概率時(shí)成功時(shí)最大的比較次數(shù)是（）。

A:20B:25C:10D:7答案:7一個(gè)圖的鄰接矩陣是對(duì)稱矩陣，則該圖是（）

A:其余選項(xiàng)都不對(duì)B:無向圖或者有向圖C:無向圖D:有向圖答案:無向圖在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，構(gòu)成強(qiáng)連通圖時(shí)至少有（）條邊

A:n-1B:n+1C:nD:n/2答案:n在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)約為（）的元素，具體移動(dòng)元素的個(gè)數(shù)與插入或刪除位置有關(guān)。

A:表長全部B:表長四分之一C:表長三分之一D:表長一半答案:表長一半二路歸并排序的時(shí)間復(fù)雜度為()。

A:O(n2)B:O(n)C:O(㏒2n)D:O(n㏒2n)答案:O(n㏒2n)二叉樹左、右子樹的深度差叫該二叉樹根結(jié)點(diǎn)的（）。

A:高度B:深度C:無法確定D:平衡因子答案:平衡因子一個(gè)有向圖G=(V，E)，V={0，1，2，3，4}，E={，2>，，3>，，4>，，5>，，2>，，5>，，3>}，現(xiàn)按深度優(yōu)先遍歷算法遍歷，從頂點(diǎn)0出發(fā)，所得到的頂點(diǎn)序列是（）。

A:1,4,3,2,5B:1,2,5,3,4C:1,4,3,5,2D:1,2,5,4,3答案:1,4,3,2,5空的鏈隊(duì)列的判決條件是（）。

A:頭指針和尾指針均不指向頭結(jié)點(diǎn)B:頭指針和尾指針均指向頭結(jié)點(diǎn)C:尾指針指向頭結(jié)點(diǎn)D:頭指針指向頭結(jié)點(diǎn)答案:頭指針和尾指針均指向頭結(jié)點(diǎn)直接插入排序在最壞情況下的時(shí)間復(fù)雜度為（）。

A:O(n2)B:O(n)C:O(n㏒2n)D:O(㏒2n)答案:O(n??)采用順序查找方法查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為（）。

A:(n-1)/2B:n/2C:(n+1)/2D:n答案:(n+1)/2對(duì)二叉排序樹進(jìn)行（），可得到結(jié)點(diǎn)的有序排列。

A:無法確定B:后序C:中序D:先序答案:中序設(shè)正文串長度為n，模式串長度為m，則模式匹配的KMP算法的時(shí)間復(fù)雜度為（

）。

A:O(n)B:O(m)C:O(m*n)D:O(m+n)答案:O(m+n)對(duì)特殊矩陣采用壓縮存儲(chǔ)的目的主要是（）。

A:表達(dá)變得簡單B:去掉矩陣中的多余元素C:減少不必要的存儲(chǔ)空間D:對(duì)矩陣元素的存儲(chǔ)變得簡單答案:減少不必要的存儲(chǔ)空間具有3個(gè)結(jié)點(diǎn)的二叉樹有（）種不同形態(tài)。

A:2種B:5種C:3種D:1種答案:5設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用下三角的壓縮存儲(chǔ)方式，以行序?yàn)橹餍?，a[1][1]為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a[8][5]的地址為（）。

A:33B:13C:40D:18答案:33元素a,b,c,d依次進(jìn)入初始為空的棧中,若元素進(jìn)棧后，可停留、可出棧,直到所有元素都出棧,則在所有可能的出棧序列中,以元素c開頭的序列個(gè)數(shù)是（）。

A:3B:6C:4D:5答案:5下述幾種排序方法中，要求內(nèi)存量最大的是（）。

A:歸并排序B:快速排序C:插入排序D:冒泡排序答案:歸并排序若廣義表滿足GetHead(A)=GetTail(A)，則A為（）。

A:((),())B:()C:(())D:((),(),())答案:(())非空無向圖的鄰接矩陣是上三角矩陣。

A:對(duì)B:錯(cuò)答案:錯(cuò)哈希函數(shù)H(k)=kMODp，p通常取小于等于表長的素?cái)?shù)。

A:錯(cuò)B:對(duì)答案:對(duì)當(dāng)待排序元素序列的初始排列基本有序時(shí)，希爾排序比直接插入排序快。

A:錯(cuò)B:對(duì)答案:錯(cuò)串'student'和'Student'相等。

A:錯(cuò)B:對(duì)答案:錯(cuò)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)更能方便的表示各種邏輯結(jié)構(gòu)。

A:對(duì)B:錯(cuò)答案:錯(cuò)多維數(shù)組可以看作是一種特殊的線性表。

A:錯(cuò)誤B:正確答案:正確完全二叉樹中,若一個(gè)結(jié)點(diǎn)沒有左孩子,則它必是葉結(jié)點(diǎn)

A:錯(cuò)誤B:正確答案:正確一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除結(jié)點(diǎn),則選用帶頭結(jié)點(diǎn)的雙循環(huán)鏈表最節(jié)省時(shí)間。

A:錯(cuò)B:對(duì)答案:對(duì)一個(gè)稀疏矩陣Am*n采用三元組順序表形式表示，若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換，并把m和n的值互換，則就完成了Am*n的轉(zhuǎn)置運(yùn)算。

A:錯(cuò)B:對(duì)答案:錯(cuò)已知一棵二叉樹的中序、后序序列分別如下：中序：DCEFBHGAKJLIM后序：DFECHGBKLJMIA，該二叉樹的先序序列ABCDEFGHIJKLM

A:錯(cuò)B:對(duì)答案:對(duì)連續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址一定連續(xù)。

A:對(duì)B:錯(cuò)答案:對(duì)算法的時(shí)間復(fù)雜度與實(shí)現(xiàn)時(shí)采用的程序設(shè)計(jì)語言無關(guān)。

A:對(duì)B:錯(cuò)答案:對(duì)刪除棧頂元素不是棧的基本操作。

A:錯(cuò)B:對(duì)答案:錯(cuò)高度為h(h>0）的完全二叉樹對(duì)應(yīng)的森林所含的樹的個(gè)數(shù)一定是hIV.一棵樹中的葉子數(shù)一定是h

A:錯(cuò)B:對(duì)答案:錯(cuò)兩個(gè)對(duì)稱矩陣相加，結(jié)果是對(duì)稱矩陣；兩個(gè)對(duì)稱矩陣相乘，結(jié)果仍然是對(duì)稱矩陣。

A:對(duì)B:錯(cuò)答案:錯(cuò)KMP算法的特點(diǎn)是在模式匹配時(shí)指示主串的指針不會(huì)回溯。

A:錯(cuò)誤B:正確答案:正確串的堆分配存儲(chǔ)表示是用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列，但它們的存儲(chǔ)空間是在程序執(zhí)行過程中動(dòng)態(tài)分配得到的。

A:錯(cuò)B:對(duì)答案:對(duì)冒泡算法是穩(wěn)定的

A:錯(cuò)誤B:正確答案:正確下列關(guān)于循環(huán)隊(duì)列的敘述中錯(cuò)誤的是（）。

A:在循環(huán)隊(duì)列中，只需要隊(duì)頭指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況B:在循環(huán)隊(duì)列中，只需要隊(duì)尾指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況C:循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定D:循環(huán)隊(duì)列有隊(duì)頭和隊(duì)尾兩個(gè)指針，因此，循環(huán)隊(duì)列是非線性結(jié)構(gòu)答案:循環(huán)隊(duì)列有隊(duì)頭和隊(duì)尾兩個(gè)指針，因此，循環(huán)隊(duì)列是非線性結(jié)構(gòu);在循環(huán)隊(duì)列中，只需要隊(duì)頭指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況;在循環(huán)隊(duì)列中，只需要隊(duì)尾指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況下面關(guān)于字符串的敘述，不正確的有()。

A:字符串是由字母和數(shù)字組成的序列。B:字符串是任意個(gè)字母組成的序列。C:字符串是由零個(gè)或多個(gè)字符組成的有限序列。D:字符串是不少于一個(gè)字符的序列。答案:字符串是不少于一個(gè)字符的序列###字符串是由字母和數(shù)字組成的序列###字符串是任意個(gè)字母組成的序列設(shè)記錄數(shù)為n，則冒泡排序算法在最好情況下所作的比較次數(shù)不可能為（）。

A:n+1B:2nC:nD:n-1答案:n###n+1###2n在n個(gè)元素的線性表的數(shù)組表示中,時(shí)間復(fù)雜度為O(1)的操作是（）。

A:在最后一個(gè)結(jié)點(diǎn)后插入一個(gè)新值B:刪除第1個(gè)結(jié)點(diǎn)C:訪問第i(1答案:訪問第i(1###在最后一個(gè)結(jié)點(diǎn)后插入一個(gè)新值下列排序方法中不穩(wěn)定的是（）。

A:直接插入排序B:直接選擇排序C:堆排序D:快速排序答案:快速排序有六個(gè)元素6，5，4，3，2，1的順序進(jìn)棧，問下列哪些是不合法的出棧序列（）？

A:453126B:235416C:234156D:346521答案:3關(guān)于線性表說法正確的是（）。

A:取線性表的第i個(gè)元素的時(shí)間與i的大小有關(guān)B:在長度為n的有序單鏈表中插入一新節(jié)點(diǎn)并仍保持有序的時(shí)間復(fù)雜度為O(n)C:靜態(tài)鏈表需要分配連續(xù)空間，插入和刪除不需要移動(dòng)元素D:順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)答案:靜態(tài)鏈表需要分配連續(xù)空間，插入和刪除不需要移動(dòng)元素;在長度為n的有序單鏈表中插入一新節(jié)點(diǎn)并仍保持有序的時(shí)間復(fù)雜度為O(n)下列數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)的是（）。

A:圖B:二叉樹C:隊(duì)列D:棧答案:棧###隊(duì)列如果某二叉樹的先根次序遍歷結(jié)果為stuwv，中序遍歷為uwtvs，那么該二叉樹的后序不可能為（）。

A:wutsvB:vwutsC:wuvtsD:uwvts答案:wuvts以下（）操作屬于串類型的最小操作子集。

A:求串長StrLengthB:串定位IndexC:串復(fù)制StrCopyD:串賦值StrAssign答案:串賦值StrAssign###求串長StrLength適用于壓縮存儲(chǔ)稀疏矩陣的存儲(chǔ)結(jié)構(gòu)是（

）。

A:二叉鏈表B:鄰接多重表C:十字鏈表D:三元組表答案:三元組表###十字鏈表以權(quán)值分別為4，3，2，1的四個(gè)葉子結(jié)點(diǎn)構(gòu)成的哈夫曼樹，其帶權(quán)路徑長度WPL不可能是（）。

A:20B:16C:19D:15答案:15###16###20下列關(guān)于串的敘述，錯(cuò)誤的是（）。

A:串中的元素只能是字母。B:若串S的長度為n，則S的子串個(gè)數(shù)為n*(n+1)/2。C:空串與空格串是相同的。D:串是一種數(shù)據(jù)對(duì)象和操作都特殊的線性表。答案:若串S的長度為n，則S的子串個(gè)數(shù)為n*(n+1)/2。;空串與空格串是相同的。;串中的元素只能是字母。構(gòu)造哈希函數(shù)有三種方法，分別為()法、()法、()法

A:折迭移位B:平方取中C:除留余數(shù)D:其余說法都不對(duì)答案:平方取中###除留余數(shù)###折迭移位數(shù)據(jù)結(jié)構(gòu)描述（）。

A:鄰接關(guān)系B:數(shù)據(jù)組織形式C:數(shù)據(jù)對(duì)