數(shù)據(jù)結(jié)構(gòu)（寧夏大學(xué)）智慧樹知到期末考試答案章節(jié)答案2024年寧夏大學(xué)

數(shù)據(jù)結(jié)構(gòu)（寧夏大學(xué)）智慧樹知到期末考試答案+章節(jié)答案2024年寧夏大學(xué)在鏈隊列中，即使不設(shè)置尾指針也能實現(xiàn)入隊操作。

答案:對

答案:012435###023145###032145下列存儲形式中，(

)不是樹的存儲形式。

答案:廣義表表示法子串“ABC”在主串“AABCABCDABCD”中的位置為(

)。

答案:2某算法的空間復(fù)雜度為O(1)，表明執(zhí)行該算法時(

)。

答案:需要的臨時存儲空間為常量執(zhí)行下面的程序段的時間復(fù)雜度為（

）。

for(i=0;i答案:O(m.n)在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是（

）

答案:直接選擇排序設(shè)p指向線索二叉樹的某結(jié)點，該結(jié)點沒有左孩子的充要條件是（

）

答案:p->ltag==1設(shè)有向無環(huán)圖G中的有向邊集合E={<1，2>，<1，3>，<2，3>，<2，5>，<4，5>}，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖牵?/p>

）。

答案:1，4，2，5，3表達(dá)式a*(b+c)-d的后綴表達(dá)式是（

）。

答案:abc+*d-假設(shè)一個6階的下三角矩陣A按行優(yōu)先順序壓縮存儲在一維數(shù)組B中，其中B[0]存儲矩陣中第1個元素a1,1，則B[8]中存放的元素是（

）。

答案:A4,3假設(shè)一個9階的上三角矩陣A按行優(yōu)先順序壓縮存儲在一維數(shù)組B中，其中B[0]存儲矩陣中第1個元素a1,1，則B[31]中存放的元素是（

）。

答案:A5,6中綴表達(dá)式A*(B+C)/(D-E+F)的后綴表達(dá)式是（

）。

答案:ABC+*DE-+/設(shè)有一個10階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順序存儲到連續(xù)的55個存儲單元中，每個數(shù)組元素占1個字節(jié)的存儲空間，則A[5][4]地址與A[0][0]的地址之差為（

）。

答案:19

答案:GDJHKBEACFMI以下（

）不是隊列的基本運算。

答案:從隊列中刪除第i個元素一棵二叉樹有67個結(jié)點，這些結(jié)點的度要么是0，要么是2。這棵二叉樹中度為2的結(jié)點有(

)個

答案:33串是一種特殊的線性表，其特殊性體現(xiàn)在（

）

答案:數(shù)據(jù)元素是一個字符鏈表不具備的特點是（

）

答案:可隨機(jī)訪問任一結(jié)點空串是任何串的子串。

答案:對

答案:014532###015423###031542

答案:102345###103254###102354

答案:104532###105423

答案:014235###012345###031425已知一個圖的頂點集V各邊集G如下：V={1，2，3，4，5，6，7，8，9}；E={（1，2），（1，3），（3，4），（3，6），（6，8），（4，5），（6，7），（8，9）}用深度優(yōu)先遍歷從1點出發(fā)的序列是（

）

答案:1，3，4，5，6，7，8，9，2解決散列法中出現(xiàn)的沖突問題常采用的方法是（

）。

答案:線性探測法、拉鏈地址法下列選項中，（

）是鏈表不具有的特點。

答案:可以隨機(jī)訪問表中的任意元素希爾排序的增量序列必須是（

）。

答案:遞減的在決定選取何種存儲結(jié)構(gòu)時，一般不考慮（

）

答案:各結(jié)點的值如何已知二叉樹中葉子數(shù)為30，僅一個孩子的結(jié)點數(shù)為20，則總結(jié)點數(shù)為（

）。

答案:79允許對隊列進(jìn)行的基本操作有（

）。

答案:刪除隊頭元素已知二叉樹中葉子數(shù)為50，僅一個孩子的結(jié)點數(shù)為30，則總結(jié)點數(shù)為（

）。

答案:129順序表具有隨機(jī)存取特性，是指(

)。

答案:查找序號值為i的元素的時間與順序表中元素個數(shù)n無關(guān)

答案:gdbhefca串的長度是指（

）。

答案:串中所含字符的個數(shù)判斷一個環(huán)形隊列qu(最多元素為MaxSize)為滿隊列的條件是（

）。

答案:(qu->rear+1)%MaxSize==qu->front對于無向圖的鄰接矩陣來說，下面正確的是（

）。

答案:第i行上的非零元素個數(shù)和第i列的非零元素個數(shù)一定相等已知一棵二叉樹的前序遍歷序列為abdgcehf，中序遍歷序列為dgbaehcf,則該二叉樹的后序遍歷序列是（

）

答案:gdbhefca一組記錄的排序碼為(49、38、65、97、76、13、27、50)，按從小到大的順序排序，則直接選擇排序算法的第一趟結(jié)果是(

)。

答案:13、38、65、97、76、49、27、50

答案:dgbaehcf判定一個順序棧st(最多元素為MaxSize)為棧滿的條件是（

）。

答案:st->top==MaxSize-1將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層上從左到右依次對結(jié)點進(jìn)行編號，根結(jié)點的編號為1，則編號為23的結(jié)點的左孩子編號為（

）。

答案:46某算法的時間復(fù)雜度為O(n2)，表明該算法的(

)。

答案:執(zhí)行時間與n2成正比在長度為n的順序表的第i(1≤i≤n+1)個位置上插入一個元素，元素的移動次數(shù)為（

）。

答案:n-i+1在含有124個元素的順序表中插入一個新元素，平均移動元素的次數(shù)是(

)。

答案:62函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為（

）。

答案:“STRUCTURE”下面程序段的時間復(fù)雜度是（

）

for（i＝0；i＜n；i＋＋）for（j＝0；j＜m；j＋＋）

A[i][j]＝0；

答案:O(n*m)已知一個圖的頂點集V和邊集E分別為：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}用克魯斯卡爾算法得到最小生成樹依次得到的各條邊的序號是（

）。

答案:(1,2)，(4,6)，(1,3)，(1,4)，(2,5)，(4,7)AOV網(wǎng)一定存在拓?fù)渑判颉?/p>

答案:錯若圖G的最小生成樹不唯一，則G的邊數(shù)一定多于n-1，并且權(quán)值最小的邊有多條（其中n為G的頂點數(shù)）。

答案:錯

答案:032145###023145

答案:103245###102345###102354###103254

答案:031254###012354###021354

答案:103245###102435在一個長度為n（n＞1）的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行（

）操作與鏈表的長度有關(guān)。

答案:刪除單鏈表中的最后一個元素在下列情況中，可稱為二叉樹的是（

）。

答案:哈夫曼樹若某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點，則采用(

)存儲方式最節(jié)省運算時間。

答案:帶頭結(jié)點的雙循環(huán)鏈表一個棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能的輸出序列是（

）。

答案:dceab一組記錄的關(guān)鍵碼為（46,79,56,38,40,84），則利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為（

）。

答案:40,38,46,56,79,84設(shè)有一個棧，元素依次進(jìn)棧的順序為A、B、C、D、E。下列（

）是不可能的出棧序列。

答案:E，A，B，C，D子串“BC”在主串“AABCABCDABCD”中的位置為（

）

答案:3二叉樹的深度為k，則二叉樹最多有（

）個結(jié)點。

答案:2k-1算法分析的兩個主要方面是（

）

答案:空間復(fù)雜度和時間復(fù)雜度已知二叉樹中僅一個孩子的結(jié)點數(shù)為50，葉子數(shù)為41，則總結(jié)點數(shù)為（

）。

答案:131

答案:abdgcehf在帶有頭結(jié)點的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行（

）。

答案:p->next=HL->next;HL->next=p;若有文件的關(guān)鍵字序列為：[265][301][751][129][937][863][742][694][076][438]，以下為二路歸并排序過程，第二趟為(

)

答案:[129265301751][694742863937][076438]下列關(guān)于二叉樹周游的敘述中，正確的是（

）

答案:若有一個樹葉是某二叉樹的對稱序最后一個結(jié)點，則它必是該二叉樹的先根序最后一個結(jié)點

答案:ABDGHJKECFIM

答案:GJKHDEBMIFCA帶頭結(jié)點的單鏈表head為空的判定條件是（

）。

答案:head->next==NULL

答案:(4,6)，(1,3)，(3,4)，(5,6)，(2,1)設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作（

）。

答案:模式匹配

答案:26設(shè)一組權(quán)值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長度為（

）。

答案:229一個棧的進(jìn)棧序列是a,b,c,d,e,則棧的可能的輸出序列是（

）。

答案:decba設(shè)有向無環(huán)圖G中的有向邊集合E={<1，2>，<2，3>，<3，4>，<1，4>}，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖牵?/p>

）。

答案:1，2，3，4

答案:a，e，d，f，c，b若串str=”DataBase”，其子串的數(shù)目是（

）。

答案:37

答案:v1，v2，v5，v6，v7，v3，v4在以下的敘述中，正確的是（

）。

答案:二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表線性表是(

)。

答案:一個有限序列，可以為空采用直接選擇排序，比較的次數(shù)與移動次數(shù)分別是（

）。

答案:O(n2)，O(n)任何一棵二叉樹的葉子結(jié)點在前序、中序和后序遍歷序列中的相對次序（

）。

答案:不發(fā)生改變廣義表B=（(a,b,(e,h)),(c,d)）,則下面式子tail(head(B))的值為（

）。

答案:(b,(e,h))執(zhí)行下面的程序段的時間復(fù)雜度為（

）。

s=0;

fori=0;i答案:O(n2)設(shè)有一個二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644，A[2][2]存放位置在676，每個元素占一個空間，問A[3][3]存放在什么位置（

）。

答案:692由五個分別帶權(quán)值為9，2，3，5，14的葉子結(jié)點構(gòu)成的一棵哈夫曼樹，該樹的帶權(quán)路徑長度為(

)

答案:67下列排序算法中不穩(wěn)定的是（

）。

答案:快速排序廣義表A=（(a,b),(c,d)）,則下面式子tail(head(A))的值為（

）

答案:b一個具有n個頂點的連通無向圖的生成樹中有(

)條邊。

答案:n-1從一個長度為100的順序表中刪除第30個元素時需向前移動（

）個元素

答案:70判定一個順序棧st(最多元素為MaxSize)為空的條件是（

）。

答案:st->top==-1有一個9階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順序存儲到連續(xù)的45個存儲單元中，每個數(shù)組元素占1個字節(jié)的存儲空間，則A[4][3]地址與A[0][0]的地址之差為（

）。

答案:13某線性表中最常用的操作是存取序號為i的元素和在最后進(jìn)行插入和刪除運算，則采用（

）存儲方法時間性能最好。

答案:順序表以下穩(wěn)定的排序方法是（

）

答案:冒泡排序?qū)τ诖笪募呐判蛞芯吭谕庠O(shè)上的排序技術(shù)，即（

）。

答案:外排序法排序的目的是為了以后對已排序的數(shù)據(jù)元數(shù)進(jìn)行（

）操作。

答案:查找快速排序在最壞的情況下的時間復(fù)雜度是（

）。

答案:O(n2)在文件局部有序或文件長度較小的情況下，最佳的排序方法是（

）。

答案:冒泡排序以下時間復(fù)雜性不是O(nlog2n)的排序方法是（

）。

答案:直接插入排序以下說法錯誤的是（

）。

答案:堆排序的空間復(fù)雜度為O(n)。當(dāng)初始序列已按健值有序時，用直接插入算法進(jìn)行排序，需要比較的次數(shù)為（

）。

答案:n-1以下時間復(fù)雜性不是O(n2)的排序方法是（

）

答案:歸并排序以下不穩(wěn)定的排序方法是（

）

答案:直接選擇排序鄰接表比鄰接矩陣更節(jié)省空間。

答案:錯圖的廣度優(yōu)先遍歷算法中用到的輔助隊列，每個頂點最多進(jìn)隊的次數(shù)不確定。

答案:錯任意一個AOV網(wǎng)都可以有拓?fù)渑判颉?/p>

答案:錯任一AOV網(wǎng)中至少有一條關(guān)鍵路徑，且是從源點到匯點的路徑中最長的一條。（

）

答案:錯深度優(yōu)先遍歷類似于二叉樹的（

）。

答案:先序遍歷如果從無向圖的任一頂點出發(fā)進(jìn)行一次深度優(yōu)先搜索可訪問所有頂點，則該圖一定是（

）。

答案:連通圖具有n個頂點的無向完全圖的邊數(shù)為（

）。

答案:n(n-1)/2帶權(quán)有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中（

）。

答案:第i列非∞的元素之和對含有n個頂點e條邊的有向圖，F(xiàn)loyd算法的時間復(fù)雜度為（

）

答案:O(n3)用鄰接表存儲圖所用的空間大?。?/p>

）。

答案:與圖的頂點和邊數(shù)與關(guān)設(shè)某有向圖的鄰接表中有n個表頭結(jié)點和m個表結(jié)點，則該圖中有（

）條有向邊。

答案:m設(shè)某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復(fù)雜度為（

）。

答案:O(n+e)以下對AOV網(wǎng)的描述中，錯誤的是（

）。

答案:任何一個關(guān)鍵活動提前完成，整個工程也將提前完成。用

Prim和Kruskal兩種算法構(gòu)造同一連通圖的最小生成樹，所得的最小生成樹（

）。

答案:可能相同也可能不同給定一棵二叉樹的前序和后序遍歷序列，可以唯一地確定出這棵二叉樹形態(tài)。

答案:錯哈夫曼編碼是一種前綴碼。

答案:對二叉樹就是度為2的樹。

答案:錯一棵左右子樹均不空的二叉樹在先序線索化后，其空指針域數(shù)為（

）。

答案:1把一棵樹轉(zhuǎn)換成二叉樹后，這棵二叉樹形態(tài)是唯一的。

答案:對對二叉樹從1開始進(jìn)行連續(xù)編號，要求每個結(jié)點的編號大于其左右孩子的編號，同一個結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，則可采用（

）遍歷實現(xiàn)編號。

答案:后序一棵非空的二叉樹的先序序列和后序序列正好相同，則該二叉樹一定滿足（

）。

答案:其中任意一結(jié)點均無右孩子設(shè)二叉樹根結(jié)點的層次為1，所有含有63個結(jié)點的二叉樹中，最小高度是（

）。

答案:6

答案:dgbafche某二叉樹的中序序列和后序序列正好相反，則該二叉樹一定是（

）的二叉樹。

答案:任一結(jié)點無左孩子

答案:gdbfheca設(shè)結(jié)點x和結(jié)點y是二叉樹T中的任意兩個結(jié)點，若在前序序列中x在y之前，而在后序序列中x在y之后，則x和y的關(guān)系是（

）。

答案:y是x的孩子深度為5的二叉樹至多有（

）個結(jié)點。

答案:31

答案:C在有n個結(jié)點的二叉鏈表中，值為非空的鏈域的個數(shù)為（

）。

答案:n-1C語言中，設(shè)inta[][4]={1,2,3,4,5,6,7,8,9};則數(shù)組a的第一維大小是5。

答案:錯設(shè)已知一個稀疏矩陣的三元組如下：(1,2,3),(1,6,1),(3,1,5),(3,2,-1),(4,5,4),(5,1,-3),則其轉(zhuǎn)置矩陣的三元組表中第3個三元組為（

）。

答案:(2,1,3)設(shè)有一個二維數(shù)組A[10][15]，數(shù)組按行存放，假設(shè)A[0][0]存放位置在644，每個元素占1個空間，則A[4][5]在（

）位置。

答案:709C語言中，合法的數(shù)組定義是（

）。

答案:chara[]={0,1,2,3,4,5};C語言中，可以在賦值語句中通過賦值運算符”=”對字符數(shù)組整體賦值。

答案:錯在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點都具有相同的（

）。

答案:行號若有以下定義和語句:

inta[10]={1,2,3,4,5,6,7,8,9,10},*p=a;不能表示a數(shù)組元素的表達(dá)式是（

）。

答案:a[10]設(shè)有一個n行n列的對稱矩陣A將其下三角部分按行存放在一維數(shù)組B中，A[0][0]存放于B[0]中，那么第i行的對角元素A[i][i]存放于B中（

）處。

答案:(i+3)*i/2廣義表運算，Tail(Head(((a,b,c,d,e))))=（

）。

答案:(b,c,d,e)廣義表L=((a,b,c))，則L的長度和深度分別為（

）。

答案:1和2設(shè)串s1=’ABCDEFG’，s2=’PQRST’，下標(biāo)從0開始，函數(shù)con(x,y)返回x和y串的連接串，subs(s,

i,

j)返回串s的從序號i開始的j個字符組成的子串，len(s)返回串s的長度，則con(subs(s1,

2,

len(s2)),

subs(s1,

len(s2),

2))的結(jié)果串是（

）。

答案:CDEFGFG若有以下定義和語句:char*s1="12345",*s2="1234";printf("%d\n",strlen(strcpy(s1,s2)));則輸出結(jié)果是（

）。

答案:4C語言中，語句static

char

c[]=“after”;執(zhí)行后，數(shù)組c的長度為5。

答案:對C語言中，char

c[4]=”abc”,d[4]=”abc”;等價于char

c[4]=d[4]=”abc”;

答案:錯printf函數(shù)中用到格式符%5s,其中數(shù)字5表示輸出的字符串占用5列。如果字符串長度小于5,則輸出按方式（

）。

答案:右對齊輸出該字串,左補(bǔ)空格對于一個鏈串s，查找第i個元素的復(fù)雜度為（

）。

答案:O(n2)模式串S=’aaab’，其Next數(shù)組值分別為（

）。

答案:-1，0，1，2字符串采用結(jié)點大小為1的鏈表作為其存儲結(jié)構(gòu)，是指（

）。

答案:鏈表的每個鏈結(jié)點的數(shù)據(jù)域中只存放了一個字符兩個串相等必有串長度相等且（

）。

答案:串中各對應(yīng)位置字符均相等下面關(guān)于串的敘述中，哪一個是不正確的？（

）。

答案:空串是由空格構(gòu)成的串非空的雙向循環(huán)鏈表中任何結(jié)點的前驅(qū)指針均不為空。

答案:對在鏈隊列中，即使不設(shè)置尾指針也能進(jìn)行入隊操作。

答案:對走迷宮問題只能用隊列來求解。

答案:錯一個棧的輸入序列為12345，則下列序列中不可能是棧的輸出序列的是（

）。

答案:54132隊列操作的原則是（

）。

答案:先進(jìn)先出設(shè)循環(huán)隊列Q[N]的頭尾指針為F、R，頭指針F總是指在隊列中的第一個元素的前一位置，則隊列中元素計數(shù)為（

）。

答案:(R-F+N)%N以下屬于隊列的基本運算的是（

）。

答案:刪除隊頭元素設(shè)一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，則該操作的時間復(fù)雜度為（

）。

答案:O(n)以下各種不帶頭結(jié)點的鏈表中最不適合用作鏈隊的（

）。

答案:只帶隊首指針的非循環(huán)雙鏈表棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是（

）。

答案:鏈表存儲結(jié)構(gòu)和數(shù)組設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（

）。

答案:必須判別棧是否為空設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（

）。

答案:top=top->next;設(shè)棧S和隊列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S，一個元素出棧后即進(jìn)入隊列Q，若6個元素出列的順序為E2、E4、E3、E6、E5和E1，則棧S的容量至少應(yīng)該是（

）。

答案:3已知指針P指向鍵表L中的某結(jié)點，執(zhí)行語句P=P->next不會刪除該鏈表中的結(jié)點。

答案:對設(shè)帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（

）。

答案:head->next==head順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為（

）。

答案:O(n)線性表的唯一存儲形式是鏈表。

答案:錯對鏈表進(jìn)行插入和刪除操作時不必移動鏈表中結(jié)點。

答案:對在一個單鏈表中，若刪除p所指結(jié)點的后續(xù)結(jié)點，則執(zhí)行（

）。

答案:p->next=p->next->next線性表采用鏈?zhǔn)酱鎯r，結(jié)點的存儲地址（

）。

答案:連續(xù)與否均可線性表是具有n個（

）的