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

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

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

A:3B:4C:2D:1答案:2用直接插入排序方法對下面4個序列進行排序(由小到大)，元素比較次數(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在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素，而且要存儲（）。

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

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

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

A:其余選項都不對B:無向圖或者有向圖C:無向圖D:有向圖答案:無向圖在一個具有n個頂點的有向圖中，構(gòu)成強連通圖時至少有（）條邊

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

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

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

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

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空的鏈隊列的判決條件是（）。

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

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

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

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

）。

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

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

A:2種B:5種C:3種D:1種答案:5設有一個10階的對稱矩陣A，采用下三角的壓縮存儲方式，以行序為主序，a[1][1]為第一元素，其存儲地址為1，每個元素占一個地址空間，則a[8][5]的地址為（）。

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

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

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

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

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

A:錯B:對答案:對當待排序元素序列的初始排列基本有序時，希爾排序比直接插入排序快。

A:錯B:對答案:錯串'student'和'Student'相等。

A:錯B:對答案:錯鏈式存儲結(jié)構(gòu)比順序存儲結(jié)構(gòu)更能方便的表示各種邏輯結(jié)構(gòu)。

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

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

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

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

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

A:錯B:對答案:對連續(xù)存儲設計時，存儲單元的地址一定連續(xù)。

A:對B:錯答案:對算法的時間復雜度與實現(xiàn)時采用的程序設計語言無關。

A:對B:錯答案:對刪除棧頂元素不是棧的基本操作。

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

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

A:對B:錯答案:錯KMP算法的特點是在模式匹配時指示主串的指針不會回溯。

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

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

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

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

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

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

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

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

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

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

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

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

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

）。

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

A:20B:16C:19D:15答案:15###16###20下列關于串的敘述，錯誤的是（）。

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

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

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