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

第一章測(cè)試在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（

）。

A:內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

B:動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

C:緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

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

答案:D算法分析的兩個(gè)主要方面是（

）。

A:數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

B:正確性和簡(jiǎn)單性

C:時(shí)間復(fù)雜度和空間復(fù)雜度

D:可讀性和文檔性

答案:C計(jì)算機(jī)算法必須具備輸入、輸出和（

）等5個(gè)特性。

A:可行性、確定性和有窮性

B:確定性、有窮性和穩(wěn)定性

C:可行性、可移植性和可擴(kuò)充性

D:易讀性、穩(wěn)定性和安全性

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

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

A:抽象結(jié)構(gòu)，邏輯結(jié)構(gòu)

B:理想結(jié)構(gòu)，物理結(jié)構(gòu)

C:理想結(jié)構(gòu)，抽象結(jié)構(gòu)

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

答案:D數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（

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

A:物理

B:存儲(chǔ)

C:邏輯

D:物理和存儲(chǔ)

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

）。

A:數(shù)據(jù)類(lèi)型

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

C:數(shù)據(jù)項(xiàng)

D:數(shù)據(jù)變量

答案:B設(shè)數(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是（

）。

A:線性結(jié)構(gòu)

B:集合

C:樹(shù)型結(jié)構(gòu)

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

答案:D下面程序的時(shí)間復(fù)雜為（

）for（i=1，s=0；

i<=n；

i++）

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

A:O(n)

B:O(n4)

C:O(n3)

D:O(n2)

答案:D程序段s=i=0；do{i=i+1；

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

）。

A:O(n)

B:O(nlog2n)

C:

O(n2)

D:O(n3/2)

答案:A算法指的是（

）

A:解決問(wèn)題的計(jì)算方法

B:排序算法

C:解決問(wèn)題的有限運(yùn)算序列

D:計(jì)算機(jī)程序

答案:C算法就是程序。

A:對(duì)

B:錯(cuò)

答案:B在C語(yǔ)言中，inti,

*p

=

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

A:錯(cuò)

B:對(duì)

答案:A第二章測(cè)試在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行（

）。

A:s->next=p;p->next=s

B:p->next=s;s->next=p

C:s->next=p->next;p->next=s

D:s->next=p->next;p=s

答案:C線性表是具有n個(gè)（

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

A:表元素

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

C:字符

D:數(shù)據(jù)項(xiàng)

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

）。

A:p=p->next->next;

B:p=p->next;p->next=p->next->next

C:p->next=p->next->next

D:p->next=p->next

答案:C線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（

）。

A:必須是連續(xù)的

B:必須是不連續(xù)的

C:和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)

D:連續(xù)與否均可

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

）。

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

B:s->link=p->link;p->link=s

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

D:p->link=s->link;s->link=p

答案:A順序存儲(chǔ)的線性表（a0,a1,…,an-1）,在任一結(jié)點(diǎn)前插入一個(gè)新結(jié)點(diǎn)時(shí)所需移動(dòng)結(jié)點(diǎn)的平均次數(shù)為（

）。

A:n/2

B:(n+1)/2

C:n

D:n+1

答案:A若線性表最常用的操作是存取第i個(gè)元素及其前趨的值，則采用（

）存儲(chǔ)方式節(jié)省時(shí)間。

A:單循環(huán)鏈表

B:順序表

C:單鏈表

D:雙鏈表

答案:B若某鏈表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)刪除最后一個(gè)結(jié)點(diǎn)，則采用（

）存儲(chǔ)方式最節(jié)省時(shí)間。

A:雙鏈表

B:單鏈表

C:帶頭結(jié)點(diǎn)的雙循環(huán)鏈表

D:單循環(huán)鏈表

答案:D下面關(guān)于線性表的敘述錯(cuò)誤的是（

）。

A:線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間

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

C:線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間

D:線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)

答案:B設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為（

）。

A:O(n2)

B:O(1)

C:O(n)

D:O(nlog2n)

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

）。

A:O(n1/2)

B:O(n2)

C:O(n)

D:O(1og2n)

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

）。

A:head->next==head

B:head==NULL

C:head!=

NULL

D:head->next==

NULL

答案:A線性表的唯一存儲(chǔ)形式是鏈表。

A:對(duì)

B:錯(cuò)

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

A:對(duì)

B:錯(cuò)

答案:A對(duì)鏈表進(jìn)行插入和刪除操作時(shí)不必移動(dòng)鏈表中結(jié)點(diǎn)。

A:錯(cuò)

B:對(duì)

答案:B第三章測(cè)試棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（

）。

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

B:散列方式和索引方式

C:線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)

D:線性存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)

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

）。

A:R-F

B:(F-R+N)%N

C:(R-F+N)%N

D:N-(R-F)

答案:C隊(duì)列操作的原則是（

）。

A:只能進(jìn)行刪除

B:先進(jìn)先出

C:后進(jìn)先出

D:只能進(jìn)行插入

答案:B一個(gè)棧的輸入序列為12345，則下列序列中不可能是棧的輸出序列的是（

）。

A:23145

B:15432

C:54132

D:23415

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

）。

A:6

B:4

C:2

D:3

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

）。

A:必須判別棧是否為滿

B:判別棧元素的類(lèi)型

C:必須判別棧是否為空

D:對(duì)棧不作任何判別

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

）。

A:O(n)

B:O(log2n)

C:O(n2)

D:O(1)

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

）。

A:top=top+1;

B:top->next=top;

C:top=top-1;

D:top=top->next;

答案:D以下屬于隊(duì)列的基本運(yùn)算的是（

）。

A:刪除隊(duì)頭元素

B:取出最近進(jìn)隊(duì)元素

C:在隊(duì)列中某元素之后插入元素

D:對(duì)隊(duì)列中的元素排序

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

）。

A:只帶隊(duì)尾指針的非循環(huán)雙鏈表

B:只帶隊(duì)尾指針的循環(huán)雙鏈表

C:只帶隊(duì)首指針的循環(huán)雙鏈表

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

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

A:對(duì)

B:錯(cuò)

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

A:錯(cuò)

B:對(duì)

答案:B走迷宮問(wèn)題只能用隊(duì)列來(lái)求解。

A:對(duì)

B:錯(cuò)

答案:B第四章測(cè)試下面關(guān)于串的敘述中，哪一個(gè)是不正確的？（

）。

A:模式匹配是串的一種重要運(yùn)算

B:串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)

C:串是字符的有限序列

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

答案:D字符串采用結(jié)點(diǎn)大小為1的鏈表作為其存儲(chǔ)結(jié)構(gòu)，是指（

）。

A:鏈表的長(zhǎng)度為1

B:鏈表的每個(gè)鏈結(jié)點(diǎn)的數(shù)據(jù)域中只存放了一個(gè)字符

C:鏈表的每個(gè)鏈結(jié)點(diǎn)的數(shù)據(jù)域中不只存放了一個(gè)字符

D:鏈表只存放1個(gè)字符

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

i,

j)返回串s的從序號(hào)i開(kāi)始的j個(gè)字符組成的子串，len(s)返回串s的長(zhǎng)度，則con(subs(s1,

2,

len(s2)),

subs(s1,

len(s2),

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

）。

A:CDEFGG

B:CDEFGFG

C:CDPQRST

D:CDEFG

答案:B模式串S=’aaab’，其N(xiāo)ext數(shù)組值分別為（

）。

A:0，1，0，0

B:-1，1，2，0

C:0，0，1，2

D:-1，0，1，2

答案:D兩個(gè)串相等必有串長(zhǎng)度相等且（

）。

A:串中各對(duì)應(yīng)位置字符均相等

B:兩個(gè)串所含字符任意

C:兩個(gè)串含有相同的字符

D:串的各位置字符任意

答案:A若有以下定義和語(yǔ)句:chars1=“12345”,s2=“1234”;printf(“%d”,strlen(strcpy(s1,s2)));則輸出結(jié)果是（

）。

A:4

B:10

C:9

D:5

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

）。

A:右對(duì)齊輸出該字串,左補(bǔ)空格

B:從左起輸出該字串,右補(bǔ)空格

C:按原字符長(zhǎng)從左向右全部輸出

D:輸出錯(cuò)誤信息

答案:A對(duì)于一個(gè)鏈串s，查找第i個(gè)元素的復(fù)雜度為（

）。

A:O(1)

B:O(n)

C:O(n2)

D:都不對(duì)

答案:CC語(yǔ)言中，char

c[4]=”abc”,d[4]=”abc”;等價(jià)于char

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

A:對(duì)

B:錯(cuò)

答案:BC語(yǔ)言中，語(yǔ)句static

char

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

A:錯(cuò)

B:對(duì)

答案:B第五章測(cè)試設(shè)有一個(gè)二維數(shù)組A[10][15]，數(shù)組按行存放，假設(shè)A[0][0]存放位置在644，每個(gè)元素占1個(gè)空間，則A[4][5]在（

）位置。

A:724

B:626

C:672

D:709

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

）處。

A:(2n-i-1)i/2

B:(2n-i+1)i/2

C:(i+3)i/2

D:(i+1)i/2

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

）。

A:(2,3,-1)

B:(2,1,3)

C:(3,2,-1)

D:(3,1,5)

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

）。

A:2和3

B:1和3

C:1和2

D:1和1

答案:C廣義表運(yùn)算，Tail(Head(((a,b,c,d,e))))=（

）。

A:a

B:(b,c,d,e)

C:c,d

D:空表

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

）。

A:列號(hào)

B:非零元素個(gè)數(shù)

C:行號(hào)

D:元素值

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

）。

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

B:inta[5]={0,1,2,3,4,5};

C:inta[]=“string”;

D:string

s=“string”;

答案:A若有以下定義和語(yǔ)句:

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

）。

A:a[10]

B:p

C:*a

D:a[p-a]

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

A:錯(cuò)

B:對(duì)

答案:AC語(yǔ)言中，可以在賦值語(yǔ)句中通過(guò)賦值運(yùn)算符”=”對(duì)字符數(shù)組整體賦值。

A:對(duì)

B:錯(cuò)

答案:B第六章測(cè)試設(shè)二叉樹(shù)根結(jié)點(diǎn)的層次為1，所有含有63個(gè)結(jié)點(diǎn)的二叉樹(shù)中，最小高度是（

）。

A:7

B:6

C:5

D:4

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

）。

A:y是x的祖先

B:x是y的左兄弟

C:

y是x的孩子

D:x是y的右兄弟

答案:CA:D

B:B

C:A

D:C

答案:D深度為5的二叉樹(shù)至多有（

）個(gè)結(jié)點(diǎn)。

A:10

B:32

C:31

D:16

答案:C如圖所示二叉樹(shù)的后序遍歷序列是（

）。

A:gdbfheca

B:dgbafche

C:abdgcefh

D:gdbehfca

答案:A如圖所示二叉樹(shù)的中序遍歷序列是（

）。

A:dgbafche

B:abdgcefh

C:abcdefgh

D:gdbehfca

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

）。

A:n+1

B:2n+1

C:2n-1

D:n-1

答案:D對(duì)二叉樹(shù)從1開(kāi)始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左右孩子的編號(hào)，同一個(gè)結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，則可采用（

）遍歷實(shí)現(xiàn)編號(hào)。

A:中序

B:無(wú)序

C:后序

D:從根開(kāi)始的層次遍歷

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

）的二叉樹(shù)。

A:任一結(jié)點(diǎn)無(wú)左孩子

B:空或只有一個(gè)結(jié)點(diǎn)

C:高度等于其結(jié)點(diǎn)數(shù)

D:任一結(jié)點(diǎn)無(wú)右孩子

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

）。

A:其中任意一結(jié)點(diǎn)均無(wú)左孩子

B:是任意一棵二叉樹(shù)

C:其中任意一結(jié)點(diǎn)均無(wú)右孩子

D:其中只有一個(gè)結(jié)點(diǎn)

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

）。

A:2

B:1

C:不確定

D:0

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

A:錯(cuò)

B:對(duì)

答案:A二叉樹(shù)就是度為2的樹(shù)。

A:對(duì)

B:錯(cuò)

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

A:對(duì)

B:錯(cuò)

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

A:錯(cuò)

B:對(duì)

答案:B第七章測(cè)試具有n個(gè)頂點(diǎn)的無(wú)向完全圖的邊數(shù)為（

）。

A:

n(n-1)

B:n2

C:n(n-1)/2

D:n2-1

答案:C對(duì)含有n個(gè)頂點(diǎn)e條邊的有向圖，F(xiàn)loyd算法的時(shí)間復(fù)雜度為（

）

A:O(n)

B:

O(n2)

C:O(ne)

D:O(n3)

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

）。

A:一棵樹(shù)

B:完全圖

C:連通圖

D:有回路的圖

答案:C帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度等于A中（

）。

A:第i行非∞且非0的元素個(gè)數(shù)

B:第i行非∞的元素之和

C:第i列非∞且非0的元素個(gè)數(shù)

D:第i列非∞的元素之和

答案:D以下對(duì)AOV網(wǎng)的描述中，錯(cuò)誤的是（

）。

A:關(guān)鍵活動(dòng)不近期完成就會(huì)影響整個(gè)工程的完成時(shí)間。

B:在AOV網(wǎng)中可能存在多條關(guān)鍵路徑。

C:所有關(guān)鍵活動(dòng)都提前完成，整個(gè)工程也將提前完成。

D:任何一個(gè)關(guān)鍵活動(dòng)提前完成，整個(gè)工程也將提前完成。

答案:D設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn)，則該圖中有（

）條有向邊。

A:m

B:n-1

C:n

D:m-1

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

）。

A:O(n3)

B:O(ne)

C:O(n+e)

D:O(n2)

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

）。

A:只與圖的邊數(shù)有關(guān)

B:與邊數(shù)的平方有關(guān)

C:只與圖的頂點(diǎn)數(shù)與關(guān)

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

答案:D深度優(yōu)先遍歷類(lèi)似于二叉樹(shù)的（

）。

A:層次遍歷

B:后序遍歷

C:先序遍歷

D:中序遍歷

答案:C用

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

）。

A:可能相同也可能不同

B:是不同的

C:其余都不對(duì)

D:是相同的

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

）

A:錯(cuò)

B:對(duì)

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

A:對(duì)

B:錯(cuò)

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

A:對(duì)

B:錯(cuò)

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

A