數(shù)據(jù)結構知到章節(jié)答案智慧樹2023年山東建筑大學

數(shù)據(jù)結構知到章節(jié)測試答案智慧樹2023年最新山東建筑大學第一章測試

方法f1的時間復雜度是（）

publicintf1(intn){

intx=0;

while(n>=(x+1)*(x+1)){

x=x+1;

}

returnx;

}

參考答案:

O(n1/2)

方法f2的時間復雜度是（）

publicintf2(intn){

inti=0;

intsum=0;

while(sum<n){

sum+=++i;

}

returni;

}

參考答案:

O(n1/2)

方法f3的時間復雜度是（）

publicintf3(intn){

intx=2;

while(x<n/2){

x=2*x;

}

returnx;

}

參考答案:

O(logn)

方法f4的時間復雜度是（）

publicintf4(intn){

intcount=0;

for(intk=1;k<=n;k*=2){

for(intj=1;j<=n;j++){

count++;

}

}

returncount;

}

參考答案:

O(nlogn)

記問題的規(guī)模n=a.length，方法f5的時間復雜度是（）

publicvoidf5(int[]a,intx){

intj=a.length;

for(inti=0;i<a.length;i++){

if(x>a[i]){

j=i;

break;

}

}

for(inti=a.length;i>j;i--){

a[i]=a[i-1];

}

a[j]=x;

}

參考答案:

O(n)

第二章測試

數(shù)據(jù)對象是指（）

參考答案:

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

數(shù)據(jù)結構的研究內(nèi)容涉及（）

參考答案:

數(shù)據(jù)如何組織;數(shù)據(jù)如何存儲;數(shù)據(jù)的運算如何實現(xiàn)

數(shù)據(jù)的邏輯結構分為線性結構和非線性結構。（）

參考答案:

對

數(shù)據(jù)的存儲結構包括數(shù)據(jù)的表示和數(shù)據(jù)之間關系的表示。（）

參考答案:

對

如果使用Java語言描述，鏈式存儲是利用引用變量來表示數(shù)據(jù)之間的關系。（）

參考答案:

對

第三章測試

以下不是順序表特點的是（）。

參考答案:

無需預分配空間

刪除順序表（共有n個數(shù)據(jù)元素）中第i（0≤i≤n-1）個數(shù)據(jù)元素時需要移動（）個數(shù)據(jù)元素。

參考答案:

n-i-1

在線性表中若經(jīng)常要存取第i個數(shù)據(jù)元素及其前驅(qū)，則宜采用（）存儲方式。

參考答案:

順序表

在一個有序單鏈表（含有n個結點）中插入一個新結點，使單鏈表仍然保持有序的算法的時間復雜度是（）。

參考答案:

O（n）

在帶頭結點的雙向循環(huán)鏈表中的p結點之后插入一個新結點s，其修改鏈的Java語句序列是（）

參考答案:

s.next=p.next;s.prior=p;p.next.prior=s;p.next=s;

第四章測試

有六個元素6，5，4，3，2，1的順序進棧，問下列哪一個不是合法的出棧序列？（）。

參考答案:

346521

若一個棧的輸入序列為1,2,3,…,n，輸出序列的第一個元素是i，則第j個輸出元素是（）。

參考答案:

不確定

若已知一個棧的入棧序列是1,2,3,…,n，其輸出序列為p1,p2,p3，…，pN,若pN是n，則pi是（）。

參考答案:

不確定

設有三個元素X，Y，Z順序進棧（進的過程中允許出棧），下列得不到的出棧排列是（）。

參考答案:

ZXY

遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為（）的數(shù)據(jù)結構。

參考答案:

棧

第五章測試

用鏈接方式存儲的隊列，在進行刪除運算時（）。

參考答案:

頭、尾指針可能都要修改

用不帶頭結點的單鏈表存儲隊列時,其隊頭指針指向隊頭結點,其隊尾指針指向隊尾結點，則在進行刪除操作時（）。

參考答案:

隊頭、隊尾指針都可能要修改

棧與隊列是一種特殊操作的線性表。（）

參考答案:

對

隊列是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結構。（）

參考答案:

錯

通常使用隊列來處理函數(shù)或過程的調(diào)用。（）

參考答案:

錯

第六章測試

在有n個結點的二叉樹的二叉鏈表存儲結構中有（）個空的指針域。

參考答案:

n+1

若某棵二叉樹的先根遍歷序列為ABCDEF,中根遍歷序列為CBDAEF,則這棵二叉樹的后根遍歷序列為（）。

參考答案:

CDBFEA

具有10個葉結點的二叉樹中有度為2的結點有（）個

參考答案:

9

一個具有1025個結點的二叉樹的深度為（）

參考答案:

11至1025之間

利用二叉鏈表存儲樹，則根結點的右指針是（）。

參考答案:

空

第七章測試

對有n個頂點，e條邊且使用鄰接表存儲的有向圖進行廣度優(yōu)先搜索，其算法時間復雜度是（）

參考答案:

O(n+e)

設無向圖的頂點個數(shù)為n，則該圖最多有（）條邊

參考答案:

n(n-1)/2

使用鄰接表存儲圖所用的空間大?。ǎ?/p>

參考答案:

與圖的頂點數(shù)和邊數(shù)都有關

用鄰接表存儲圖時，拓撲排序算法的時間復雜度是（）

參考答案:

O(n+e)

為了實現(xiàn)圖的廣度優(yōu)先搜索，除了需要一個數(shù)組標志已經(jīng)訪問過的結點外，還需要隊列。（）

參考答案:

對

第八章測試

已知一個長度為16的順序表L，其元素按關鍵字有序排列。若采用二分查找法查找一個L中不存在的元素，則關鍵字的比較次數(shù)最多是（）。

參考答案:

5

二分查找從100個有序整數(shù)中查找某數(shù)，最壞情況下需要比較的次數(shù)是（）。

參考答案:

7

若二叉搜索樹是有N個結點的完全二叉樹，則不正確的說法是（）。

參考答案:

最大值一定在葉結點上

將{32,2,15,65,28,10}依次插入初始為空的二叉搜索樹。則該樹的前序遍歷結果是（）。

參考答案:

32,2,15,10,28,65

對二叉搜索樹進行什么遍歷可以得到從小到大的排序序列？（）。

參考答案:

后序遍歷

第九章測試

從待排序的序列當中選出關鍵字值最大的記錄放到有序序列中，該排序方法稱為（）。

參考答案:

冒泡排序

當待排序序列基本有序時，以下排序序列當中最不利于其優(yōu)勢的發(fā)揮（）。

參考答案:

快速排序

下面給出的4種排序算法中（）是不穩(wěn)定的排序

參考答案:

堆排序

下列排序方法中，（）所需要的輔助空間最大。

參考答案:

歸并排序

執(zhí)行排序操作時，根據(jù)使用的存儲器，可將排序算法分為內(nèi)排序和外排序。（）

參考答案:

對

若不考慮基數(shù)排序，則在排序過程中主要進行的兩種基本操作是比較，移動。（）

參考答案:

對

第十章測試

已知8個數(shù)據(jù)元素為（34，76，45，18，26，54，92，65），按照依次插入結點的方法生成一棵二叉搜索樹后，最后兩層上的結點總數(shù)為（）。

參考答案:

2

最小生成樹是指該樹中（）。

參考答案:

所有邊的權值之和為最小

使用迪杰斯特拉（Dijkstra）算法求下圖中從頂點1到其他各頂點的最短路徑，依次得到的各最短路徑的目標頂點是（）。

參考答案:

5,2,3,6,4

用一個有向圖來表示航空公司所有航班的航線。下列哪種算法最適合解決找給定兩城市間最經(jīng)濟的飛行路線問題？（）。

參考答案:

Dijkstra算法

Dijkstra算法用來解決哪個問題？（）

參考答案:

最短路徑

在n個結點的無向圖中，若邊數(shù)>n-1，則該圖必是連通圖。（）

參考答案:

錯

鄰接表法只能用于有向圖的存儲，而鄰接矩陣法對于有向圖和無向圖的存儲都適用。（）