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

數(shù)據(jù)結(jié)構(gòu)（寧夏大學(xué)）知到智慧樹章節(jié)測試課后答案2024年秋寧夏大學(xué)第一章單元測試

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

）。

A:緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)B:動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)C:內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)D:線性結(jié)構(gòu)和非線性結(jié)構(gòu)

答案:線性結(jié)構(gòu)和非線性結(jié)構(gòu)算法分析的兩個(gè)主要方面是（

）。

A:數(shù)據(jù)復(fù)雜性和程序復(fù)雜性B:正確性和簡單性C:可讀性和文檔性D:時(shí)間復(fù)雜度和空間復(fù)雜度

答案:時(shí)間復(fù)雜度和空間復(fù)雜度計(jì)算機(jī)算法必須具備輸入、輸出和（

）等5個(gè)特性。

A:確定性、有窮性和穩(wěn)定性B:可行性、確定性和有窮性C:可行性、可移植性和可擴(kuò)充性D:易讀性、穩(wěn)定性和安全性

答案:可行性、確定性和有窮性數(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)

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

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

A:物理和存儲B:邏輯C:物理D:存儲

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

）。

A:數(shù)據(jù)項(xiàng)B:數(shù)據(jù)類型C:數(shù)據(jù)元素D:數(shù)據(jù)變量

答案:數(shù)據(jù)元素設(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:線性結(jié)構(gòu)C:集合D:樹型結(jié)構(gòu)

答案:圖型結(jié)構(gòu)下面程序的時(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(n4)B:O(n2)C:O(n3)D:O(n)

答案:O(n2)程序段s=i=0；do{i=i+1；

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

）。

A:O(n3/2)B:O(n)C:

O(n2)D:O(nlog2n)

答案:O(n)算法指的是（

）

A:解決問題的有限運(yùn)算序列B:解決問題的計(jì)算方法C:計(jì)算機(jī)程序D:排序算法

答案:解決問題的有限運(yùn)算序列算法就是程序。

A:對B:錯(cuò)

答案:錯(cuò)在C語言中，inti,

*p

=

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

A:對B:錯(cuò)

答案:錯(cuò)

第二章單元測試

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

）。

A:s->next=p->next;p=sB:s->next=p;p->next=sC:p->next=s;s->next=pD:s->next=p->next;p->next=s

答案:s->next=p->next;p->next=s線性表是具有n個(gè)（

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

A:數(shù)據(jù)元素B:數(shù)據(jù)項(xiàng)C:字符D:表元素

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

）。

A:p->next=p->nextB:p=p->next;p->next=p->next->nextC:p=p->next->next;D:p->next=p->next->next

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

）。

A:和頭結(jié)點(diǎn)的存儲地址相連續(xù)B:必須是連續(xù)的

C:必須是不連續(xù)的D:連續(xù)與否均可

答案:連續(xù)與否均可

在一個(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:p->link=s->link;s->link=pB:q->link=s;s->link=pC:s->link=p->link;p->link=sD:p->link=s;s->link=q

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

）。

A:n/2B:(n+1)/2C:n+1D:n

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

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

A:單鏈表B:雙鏈表

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

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

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

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

答案:單循環(huán)鏈表下面關(guān)于線性表的敘述錯(cuò)誤的是（

）。

A:線性表采用順序存儲便于插入和刪除操作的實(shí)現(xiàn)B:線性表采用順序存儲必須占用一片連續(xù)的存儲空間C:線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實(shí)現(xiàn)D:線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間

答案:線性表采用順序存儲便于插入和刪除操作的實(shí)現(xiàn)設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為（

）。

A:O(n2)B:O(1)C:O(n)D:O(nlog2n)

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

）。

A:O(1og2n)B:O(n2)C:O(n)D:O(n1/2)

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

）。

A:head!=

NULLB:head->next==headC:head==NULLD:head->next==

NULL

答案:head->next==head線性表的唯一存儲形式是鏈表。

A:對B:錯(cuò)

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

A:錯(cuò)B:對

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

A:對B:錯(cuò)

答案:對

第三章單元測試

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

）。

A:線性存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)B:鏈表存儲結(jié)構(gòu)和數(shù)組C:線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)D:散列方式和索引方式

答案:鏈表存儲結(jié)構(gòu)和數(shù)組設(shè)循環(huán)隊(duì)列Q[N]的頭尾指針為F、R，頭指針F總是指在隊(duì)列中的第一個(gè)元素的前一位置，則隊(duì)列中元素計(jì)數(shù)為（

）。

A:(F-R+N)%NB:(R-F+N)%N

C:N-(R-F)D:R-F

答案:(R-F+N)%N

隊(duì)列操作的原則是（

）。

A:只能進(jìn)行刪除B:后進(jìn)先出C:只能進(jìn)行插入D:先進(jìn)先出

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

）。

A:15432B:54132C:23415D:23145

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

）。

A:2B:3C:4D:6

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

）。

A:必須判別棧是否為空B:判別棧元素的類型C:對棧不作任何判別D:必須判別棧是否為滿

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

）。

A:O(log2n)B:O(n2)C:O(1)D:O(n)

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

）。

A:top->next=top;B:top=top+1;C:top=top->next;D:top=top-1;

答案:top=top->next;以下屬于隊(duì)列的基本運(yùn)算的是（

）。

A:在隊(duì)列中某元素之后插入元素B:取出最近進(jìn)隊(duì)元素C:刪除隊(duì)頭元素D:對隊(duì)列中的元素排序

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

）。

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

答案:只帶隊(duì)首指針的非循環(huán)雙鏈表在鏈隊(duì)列中，即使不設(shè)置尾指針也能進(jìn)行入隊(duì)操作。

A:對B:錯(cuò)

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

A:對B:錯(cuò)

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

A:錯(cuò)B:對

答案:錯(cuò)

第四章單元測試

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

）。

A:模式匹配是串的一種重要運(yùn)算B:空串是由空格構(gòu)成的串C:串是字符的有限序列D:串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?/p>

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

）。

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

答案:鏈表的每個(gè)鏈結(jié)點(diǎn)的數(shù)據(jù)域中只存放了一個(gè)字符設(shè)串s1=’ABCDEFG’，s2=’PQRST’，下標(biāo)從0開始，函數(shù)con(x,y)返回x和y串的連接串，subs(s,

i,

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

2,

len(s2)),

subs(s1,

len(s2),

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

）。

A:CDEFGFGB:CDEFGC:CDEFGGD:CDPQRST

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

）。

A:-1，0，1，2B:0，1，0，0C:0，0，1，2D:-1，1，2，0

答案:-1，0，1，2兩個(gè)串相等必有串長度相等且（

）。

A:串的各位置字符任意B:兩個(gè)串含有相同的字符C:兩個(gè)串所含字符任意D:串中各對應(yīng)位置字符均相等

答案:串中各對應(yīng)位置字符均相等若有以下定義和語句:char*s1="12345",*s2="1234";printf("%d\n",strlen(strcpy(s1,s2)));則輸出結(jié)果是（

）。

A:9B:4C:5

D:10

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

）。

A:從左起輸出該字串,右補(bǔ)空格B:輸出錯(cuò)誤信息C:按原字符長從左向右全部輸出D:右對齊輸出該字串,左補(bǔ)空格

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

）。

A:都不對B:O(1)C:O(n)D:O(n2)

答案:O(n2)C語言中，char

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

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

A:對B:錯(cuò)

答案:錯(cuò)C語言中，語句static

char

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

A:錯(cuò)B:對

答案:對

第五章單元測試

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

）位置。

A:626B:672C:724D:709

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

）處。

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

C:(i+3)*i/2D:(i+1)*i/2

答案:(i+3)*i/2設(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:(3,1,5)B:(2,3,-1)C:(3,2,-1)

D:(2,1,3)

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

）。

A:1和3B:1和2C:1和1D:2和3

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

）。

A:aB:(b,c,d,e)C:c,dD:空表

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

）。

A:非零元素個(gè)數(shù)B:元素值C:列號D:行號

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

）。

A:string

s="string";

B:inta[5]={0,1,2,3,4,5};C:chara[]={0,1,2,3,4,5};D:inta[]="string";

答案:chara[]={0,1,2,3,4,5};若有以下定義和語句:

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

）。

A:a[10]B:*a

C:a[p-a]D:*p

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

A:錯(cuò)B:對

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

A:對B:錯(cuò)

答案:錯(cuò)

第六章單元測試

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

）。

A:7B:6C:5D:4

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

）。

A:x是y的左兄弟B:x是y的右兄弟C:

y是x的孩子D:y是x的祖先

答案:

y是x的孩子

A:BB:DC:AD:C

答案:C深度為5的二叉樹至多有（

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

A:16B:31C:10D:32

答案:31如圖所示二叉樹的后序遍歷序列是（

）。

A:gdbfheca

B:dgbafche

C:abdgcefh

D:gdbehfca

答案:gdbfheca

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

）。

A:gdbehfcaB:abcdefghC:abdgcefhD:dgbafche

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

）。

A:2n-1B:2n+1C:n+1D:n-1

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

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

A:中序B:無序C:從根開始的層次遍歷D:后序

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

）的二叉樹。

A:高度等于其結(jié)點(diǎn)數(shù)B:任一結(jié)點(diǎn)無右孩子C:空或只有一個(gè)結(jié)點(diǎn)D:任一結(jié)點(diǎn)無左孩子

答案:任一結(jié)點(diǎn)無左孩子一棵非空的二叉樹的先序序列和后序序列正好相同，則該二叉樹一定滿足（

）。

A:其中只有一個(gè)結(jié)點(diǎn)B:其中任意一結(jié)點(diǎn)均無左孩子C:是任意一棵二叉樹D:其中任意一結(jié)點(diǎn)均無右孩子

答案:其中任意一結(jié)點(diǎn)均無右孩子一棵左右子樹均不空的二叉樹在先序線索化后，其空指針域數(shù)為（

）。

A:不確定B:2C:0D:1

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

A:對B:錯(cuò)

答案:錯(cuò)二叉樹就是度為2的樹。

A:錯(cuò)B:對

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

A:對B:錯(cuò)

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

A:錯(cuò)B:對

答案:對

第七章單元測試

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

）。

A:n(n-1)/2B:n2C:n2-1D:

n(n-1)

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

）

A:O(n)B:O(ne)C:O(n3)D:

O(n2)

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

）。

A:一棵樹B:完全圖C:有回路的圖D:連通圖

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

）。

A:第i行非∞且非0的元素個(gè)數(shù)B:第i列非∞的元素之和C:第i行非∞的元素之和D:第i列非∞且非0的元素個(gè)數(shù)

答案:第i列非∞的元素之和以下對AOV網(wǎng)的描述中，錯(cuò)誤的是（

）。

A:所有關(guān)鍵活動(dòng)都提前完成，整個(gè)工程也將提前完成。B:關(guān)鍵活動(dòng)不近期完成就會影響整個(gè)工程的完成時(shí)間。C:任何一個(gè)關(guān)鍵活動(dòng)提前完成，整個(gè)工程也將提前完成。D:在AOV網(wǎng)中可能存在多條關(guān)鍵路徑。

答案:任何一個(gè)關(guān)鍵活動(dòng)提前完成，整個(gè)工程也將提前完成。設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn)，則該圖中有（

）條有向邊。

A:n-1B:nC:mD:m-1

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

）。

A:O(n3)B:O(n+e)C:O(n2)D:O(ne)

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

）。

A:只與圖的邊數(shù)有關(guān)B:只與圖的頂點(diǎn)數(shù)與關(guān)C:與邊數(shù)的平方有關(guān)D:與圖的頂點(diǎn)和邊數(shù)與關(guān)

答案:與圖的頂點(diǎn)和邊數(shù)與關(guān)深度優(yōu)先遍歷類似于二叉樹的（

）。

A:層次遍歷B:中序遍歷C:先序遍歷D:后序遍歷

答案:先序遍歷用

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

）。

A:是不同的B:其余都不對C:可能相同也可能不同

D:是相同的

答案:可能相同也可能不同

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

）

A:對B:錯(cuò)

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

A:對B:錯(cuò)

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

A:對B:錯(cuò)

答案:錯(cuò)任意一個(gè)AOV網(wǎng)都