數(shù)據(jù)結(jié)構(gòu)（寧夏大學）知到章節(jié)測試答案智慧樹2023年最新第一章測試

在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（

）。

參考答案:

線性結(jié)構(gòu)和非線性結(jié)構(gòu)

算法分析的兩個主要方面是（

）。

參考答案:

時間復雜度和空間復雜度

計算機算法必須具備輸入、輸出和（

）等5個特性。

參考答案:

可行性、確定性和有窮性

數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的（

）以及它們之間的相互關(guān)系。

參考答案:

物理結(jié)構(gòu)，邏輯結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（

）結(jié)構(gòu)。

參考答案:

邏輯

組成數(shù)據(jù)的基本單位是（

）。

參考答案:

數(shù)據(jù)元素

設數(shù)據(jù)結(jié)構(gòu)A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，則數(shù)據(jù)結(jié)構(gòu)A是（

）。

參考答案:

圖型結(jié)構(gòu)

下面程序的時間復雜為（

）for（i=1，s=0；

i<=n；

i++）

{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}

參考答案:

O(n2)

程序段s=i=0；do{i=i+1；

s=s+i；}while(i<=n)；的時間復雜度為（

）。

參考答案:

O(n)

算法指的是（

）

參考答案:

解決問題的有限運算序列

算法就是程序。

參考答案:

錯

在C語言中，inti,

*p

=

&i；是不正確的變量聲明。

參考答案:

錯

第二章測試

在一個單鏈表中，若p所指結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行（

）。

參考答案:

s->next=p->next;p->next=s

線性表是具有n個（

）的有限序列（n≠0）。

參考答案:

數(shù)據(jù)元素

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

）。

參考答案:

p->next=p->next->next

線性表采用鏈式存儲時，結(jié)點的存儲地址（

）。

參考答案:

連續(xù)與否均可

在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在q所指結(jié)點和p所指結(jié)點之間插入s結(jié)點，則執(zhí)行（

）。

參考答案:

q->link=s;s->link=p

順序存儲的線性表（a0,a1,…,an-1）,在任一結(jié)點前插入一個新結(jié)點時所需移動結(jié)點的平均次數(shù)為（

）。

參考答案:

n/2

若線性表最常用的操作是存取第i個元素及其前趨的值，則采用（

）存儲方式節(jié)省時間。

參考答案:

順序表

若某鏈表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點刪除最后一個結(jié)點，則采用（

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

參考答案:

單循環(huán)鏈表

下面關(guān)于線性表的敘述錯誤的是（

）。

參考答案:

線性表采用順序存儲便于插入和刪除操作的實現(xiàn)

設一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復雜度為（

）。

參考答案:

O(1)

順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為（

）。

參考答案:

O(n)

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

）。

參考答案:

head->next==head

線性表的唯一存儲形式是鏈表。

參考答案:

錯

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

參考答案:

對

對鏈表進行插入和刪除操作時不必移動鏈表中結(jié)點。

參考答案:

對

第三章測試

棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是（

）。

參考答案:

鏈表存儲結(jié)構(gòu)和數(shù)組

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

）。

參考答案:

(R-F+N)%N

隊列操作的原則是（

）。

參考答案:

先進先出

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

）。

參考答案:

54132

設棧S和隊列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出列的順序為E2、E4、E3、E6、E5和E1，則棧S的容量至少應該是（

）。

參考答案:

3

設用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（

）。

參考答案:

必須判別棧是否為空

設一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，則該操作的時間復雜度為（

）。

參考答案:

O(n)

設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為（

）。

參考答案:

top=top->next;

以下屬于隊列的基本運算的是（

）。

參考答案:

刪除隊頭元素

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

）。

參考答案:

只帶隊首指針的非循環(huán)雙鏈表

在鏈隊列中，即使不設置尾指針也能進行入隊操作。

參考答案:

對

非空的雙向循環(huán)鏈表中任何結(jié)點的前驅(qū)指針均不為空。

參考答案:

對

走迷宮問題只能用隊列來求解。

參考答案:

錯

第四章測試

下面關(guān)于串的敘述中，哪一個是不正確的？（

）。

參考答案:

空串是由空格構(gòu)成的串

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

）。

參考答案:

鏈表的每個鏈結(jié)點的數(shù)據(jù)域中只存放了一個字符

設串s1=’ABCDEFG’，s2=’PQRST’，下標從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

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

）。

參考答案:

-1，0，1，2

兩個串相等必有串長度相等且（

）。

參考答案:

串中各對應位置字符均相等

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

）。

參考答案:

4

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

）。

參考答案:

右對齊輸出該字串,左補空格

對于一個鏈串s，查找第i個元素的復雜度為（

）。

參考答案:

O(n2)

C語言中，char

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

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

參考答案:

錯

C語言中，語句static

char

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

參考答案:

對

第五章測試

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

）位置。

參考答案:

709

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

）處。

參考答案:

(i+3)*i/2

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

）。

參考答案:

(2,1,3)

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

）。

參考答案:

1和2

廣義表運算，Tail(Head(((a,b,c,d,e))))=（

）。

參考答案:

(b,c,d,e)

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

）。

參考答案:

行號

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

）。

參考答案:

chara[]={0,1,2,3,4,5};

若有以下定義和語句:

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

）。

參考答案:

a[10]

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

參考答案:

錯

C語言中，可以在賦值語句中通過賦值運算符”=”對字符數(shù)組整體賦值。

參考答案:

錯

第六章測試

設二叉樹根結(jié)點的層次為1，所有含有63個結(jié)點的二叉樹中，最小高度是（

）。

參考答案:

6

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

）。

參考答案:

y是x的孩子

參考答案:

C

深度為5的二叉樹至多有（

）個結(jié)點。

參考答案:

31

如圖所示二叉樹的后序遍歷序列是（

）。

參考答案:

gdbfheca

如圖所示二叉樹的中序遍歷序列是（

）。

參考答案:

dgbafche

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

）。

參考答案:

n-1

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

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

參考答案:

后序

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

）的二叉樹。

參考答案:

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

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

）。

參考答案:

其中任意一結(jié)點均無右孩子

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

）。

參考答案:

1

給定一棵二叉樹的前序和后序遍歷序列，可以唯一地確定出這棵二叉樹形態(tài)。

參考答案:

錯

二叉樹就是度為2的樹。

參考答案:

錯

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

參考答案:

對

哈夫曼編碼是一種前綴碼。

參考答案:

對

第七章測試

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

）。

參考答案:

n(n-1)/2

對含有n個頂點e條邊的有向圖，F(xiàn)loyd算法的時間復雜度為（

）

參考答案:

O(n3)

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

）。

參考答案:

連通圖

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

）。

參考答案:

第i列非∞的元素之和

以下對AOV網(wǎng)的描述中，錯誤的是（

）。

參考答案:

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

設某有向圖的鄰接表中有n個表頭結(jié)點和m個表結(jié)點，則該圖中有（

）條有向邊。

參考答案:

m

設某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復雜度為（

）。

參考答案:

O(n+e)

用鄰接表存儲圖所用的空間大小（

）。

參考答案:

與圖的頂點和邊數(shù)與關(guān)

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

）。

參考答案:

先序遍歷

用

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

）。

參考答案:

可能相同也可能不同

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

）

參考答案:

錯

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

參考答案:

錯

鄰接表比鄰接矩陣更節(jié)省空間。

參考答案:

錯

任意一個AOV網(wǎng)都可以有拓撲排序。

參考答案:

錯

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

參考答案:

錯

第八章測試

以下不穩(wěn)定的排序方法是（

）

參考答案:

直接選擇排序

以下穩(wěn)定的排序方法是（

）

參考答案:

冒泡排序

以下時間復雜性不是O(n2)的排序方法是（

）

參考答案:

歸并排序

以下說法錯誤的是（

）。

參考答案:

堆排序的空間復雜度為O(n)。

以下時間復雜性不是O(nlo