電子科技大學(xué)22春“計(jì)算機(jī)應(yīng)用技術(shù)”《數(shù)據(jù)結(jié)構(gòu)》期末考試高頻考點(diǎn)版(帶答案)試卷號5

書山有路勤為徑，學(xué)海無涯苦作舟！住在富人區(qū)的她電子科技大學(xué)22春“計(jì)算機(jī)應(yīng)用技術(shù)”《數(shù)據(jù)結(jié)構(gòu)》期末考試高頻考點(diǎn)版（帶答案）一.綜合考核(共50題)1.下面程序段的時(shí)間復(fù)雜度為()。for(i=0;iA.O(n2)

B.O(m2)

C.O(m+n)

D.O(m*n)

參考答案：D2.設(shè)串s1=″DataStructureswithJava″，s2=″it″，則子串定位函數(shù)index(s1,s2)，的值為()。

A、15

B、16

C、17

D、18

參考答案：D3.一棵含18個(gè)結(jié)點(diǎn)的二叉樹的高度至少為()。

A.6

B.5

C.4

D.3

參考答案：B4.在二叉樹的第i層上至多可以有2i個(gè)結(jié)點(diǎn)。()

A、錯(cuò)誤

B、正確

參考答案：A5.已知函數(shù)Sub(s,i,j)的功能是返回串s中從第i個(gè)字符起長度為j的子串，函數(shù)Scopy(s,t)的功能為復(fù)制串t到s。若字符串S=″SCIENCESTUDY″，則調(diào)用函數(shù)Scopy(P,Sub(S,1,7))后得到()。

A、P=″SCIENCE″

B、P=″STUDY″

C、S=″SCIENCE″

D、S=″STUDY″

參考答案：A6.一棵樹可以只有1個(gè)結(jié)點(diǎn)。()

A.正確

B.錯(cuò)誤

參考答案：A7.已知函數(shù)Sub(s，i，j)的功能是返回串s中從第i個(gè)字符起長度為j的子串，函數(shù)Scopy(s，t)的功能為復(fù)制串t到s。若字符串S=“SCIENCESTUDY”，則調(diào)用函數(shù)Scopy(P，Sub(S，1，7))后得到()。

A.S=“STUDY”

B.S=“SCIENCE”

C.P=“STUDY”

D.P=“SCIENCE”

參考答案：D8.高度為5的完全二叉樹中含有的結(jié)點(diǎn)數(shù)至少為()。

A.32

B.31

C.17

D.16

參考答案：D9.在一個(gè)長度為n的循環(huán)鏈表中，刪除其元素值為x的結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n)。()

A.正確

B.錯(cuò)誤

參考答案：A10.一個(gè)具有4個(gè)頂點(diǎn)的無向完全圖有6條邊。()

A.正確

B.錯(cuò)誤

參考答案：A11.圖的存儲結(jié)構(gòu)有()。

A、鄰接矩陣

B、鄰接表

C、鄰接多重表

D、十字鏈表

參考答案：AD12.若進(jìn)棧序列為a，b，c，則通過入出棧操作可能得到的a，b，c的不同排列個(gè)數(shù)為()。

A、4

B、5

C、6

D、7

參考答案：B13.高度為5的完全二叉樹中含有的結(jié)點(diǎn)數(shù)至少為()。

A、16

B、17

C、31

D、32

參考答案：A14.產(chǎn)生沖突現(xiàn)象的兩個(gè)關(guān)鍵字稱為該散列函數(shù)的同義字。()

A.正確

B.錯(cuò)誤

參考答案：A15.對某二叉樹進(jìn)行先序遍歷的結(jié)果為ABDEFC，中序遍歷的結(jié)果為DBFEAC，則后序遍歷的結(jié)果是()。

A、DBFEAC

B、DFEBCA

C、BDFECA

D、BDEFAC

參考答案：B16.關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中()。

A、從源點(diǎn)到匯點(diǎn)的最長路徑

B、從源點(diǎn)到匯點(diǎn)的最短路徑

C、最長的回路

D、最短的回路

參考答案：A17.有向圖用鄰接矩陣表示后，頂點(diǎn)i的入度等于鄰接矩陣中第i列的元素個(gè)數(shù)。()

A、錯(cuò)誤

B、正確

參考答案：B18.在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并使鏈表仍然有序的時(shí)間復(fù)雜度是()。

A、O(1)

B、O(n)

C、O(n㏒n)

D、O(n2)

參考答案：B19.在一個(gè)長度為n的單鏈表L中，刪除鏈表中*p的前驅(qū)結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n)。()

A.正確

B.錯(cuò)誤

參考答案：A20.深度為15的滿二叉樹上，第11層有2∧11個(gè)結(jié)點(diǎn)。()

A.正確

B.錯(cuò)誤

參考答案：B21.在無向圖中，若從頂點(diǎn)a到頂點(diǎn)b存在通路，則稱a與b之間是連通的。()

A、錯(cuò)誤

B、正確

參考答案：B22.兩個(gè)串相等的充分必要條件是兩個(gè)串的長度相等且字母相同。()

A.正確

B.錯(cuò)誤

參考答案：A23.二叉樹中的葉子結(jié)點(diǎn)就是二叉樹中沒有左右子樹的結(jié)點(diǎn)。()

A、錯(cuò)誤

B、正確

參考答案：B24.含n個(gè)頂點(diǎn)的無向連通圖中至少含有n條邊。()

A、錯(cuò)誤

B、正確

參考答案：A25.判斷兩個(gè)串大小的基本準(zhǔn)則是()。

A、兩個(gè)串長度的大小

B、兩個(gè)串中首字符的大小

C、兩個(gè)串中大寫字母的多少

D、對應(yīng)的第一個(gè)不等字符的大小

參考答案：B26.一棵含999個(gè)結(jié)點(diǎn)的完全二叉樹的深度為12。()

A、錯(cuò)誤

B、正確

參考答案：A27.已知在一棵含有n個(gè)結(jié)點(diǎn)的樹中，只有度為k的分支結(jié)點(diǎn)和度為0的葉子結(jié)點(diǎn)，則該樹中含有的葉子結(jié)點(diǎn)的數(shù)目為k。()

A、錯(cuò)誤

B、正確

參考答案：A28.數(shù)據(jù)結(jié)構(gòu)是()。

A.相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合

B.數(shù)據(jù)的存儲結(jié)構(gòu)

C.一組性質(zhì)相同的數(shù)據(jù)元素的集合

D.一種數(shù)據(jù)類型

參考答案：A29.在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的()。

A、1/2

B、2倍

C、4倍

D、8倍

參考答案：B30.在目標(biāo)串T[0...n-1]=″xwxxyxy″中，對模式串P[0...m-1]=″xy″進(jìn)行子串定位操作的結(jié)果是()。

A、0

B、2

C、3

D、5

參考答案：C31.已知在一棵度為3的樹中，度為2的結(jié)點(diǎn)數(shù)為4，度為3的結(jié)點(diǎn)數(shù)為3，則該樹中的葉子結(jié)點(diǎn)數(shù)為()。

A、5

B、8

C、11

D、18

參考答案：C32.數(shù)據(jù)的邏輯結(jié)構(gòu)描述數(shù)據(jù)元素之間的邏輯關(guān)系，與存儲方式無關(guān)。()

A.正確

B.錯(cuò)誤

參考答案：A33.采用兩類不同存儲結(jié)構(gòu)的字符串可分別簡稱為()。

A、主串和子串

B、順序串和鏈串

C、目標(biāo)串和模式串

D、變量串和常量串

參考答案：B34.若進(jìn)棧序列為a，b，c，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)6個(gè)不同的出棧序列。()

A.正確

B.錯(cuò)誤

參考答案：B35.在最好和最壞情況下的時(shí)間復(fù)雜度均為O(nlogn)且穩(wěn)定的排序方法是堆排序。()

A、錯(cuò)誤

B、正確

參考答案：A36.由于希爾排序的最后一趟與直接插入排序過程相同，因此前者一定比后者花費(fèi)的時(shí)間多。()

A、錯(cuò)誤

B、正確

參考答案：A37.若算法中語句的最大頻度為T(n)=2006n+6n㏒n+29㏒2n，則其時(shí)間復(fù)雜度為()。

A、O(㏒n)

B、O(n)

C、O(n㏒n)

D、O(㏒2n)

參考答案：C38.算法分析的目的是()。

A.鑒別算法的可讀性

B.辨別數(shù)據(jù)結(jié)構(gòu)的合理性

C.評價(jià)算法的效率

D.研究算法中輸入與輸出的關(guān)系

參考答案：C39.假設(shè)按照12345的進(jìn)棧順序，下面哪些是可能的出棧順序()。

A、12345

B、54321

C、43215

D、14325

參考答案：ABCD40.算法以下幾種特性()。

A.輸入和輸出

B.確定性

C.有窮性

D.可行性

參考答案：ABCD41.已知函數(shù)Sub(s,i,j)的功能是返回串s中從第i個(gè)字符起長度為j的子串，函數(shù)Scopy(s,t)的功能為復(fù)制串t到s。若字符串S=″SCIENCESTUDY″，則調(diào)用函數(shù)Scopy(P,Sub(S,1,7))后得到()。

A.S=″STUDY″

B.S=″SCIENCE″

C.P=″STUDY″

D.P=″SCIENCE″

參考答案：D42.在隊(duì)列中，允許進(jìn)行插入操作的一端稱為隊(duì)頭。()

A.正確

B.錯(cuò)誤

參考答案：A43.在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并使鏈表仍然有序的時(shí)間復(fù)雜度是()。

A.O(n㏒n)

B.O(n2)

C.O(n)

D.O(1)

參考答案：C44.判定一個(gè)順序棧S(棧空間大小為n)為空的條件是()。

A、S->top==0

B、S->top!=0

C、S->top==n

D、S->top!=n

參考答案：A45.通常將鏈串的結(jié)點(diǎn)大小設(shè)置為大于1是為了()。

A.提高存儲密度

B.提高串匹配效率

C.便于插入操作

D.便于刪除操作

參考答案：B46.執(zhí)行下列程序段后，串X的值為()。S=“abcdefgh”;T=“xyzw”;substr(X，S，2，strlen(T));substr(Y，S，stelen(T)，2);strcat(X，Y)

A.“cdxyzw”

B.“cdefxy”

C.“cdefgh”

D.“cdefef”

參考答案：D47.在一個(gè)小根堆中，具有最大值的元素一定是葉結(jié)點(diǎn)。()

T、對