數據結構：期末考第六次測試（總復習）

一、單選題（共50題，100分）

1、表長為n的順序存儲的線性表，當在任何位置上插入或刪除一個元素的概率相等時，插入一個元素所需移動元素的平均個數為（ D ）.（2.0）
A、（n?1）/2
B、 n
C、 n+1
D、 n/2

2、設棧S和隊列Q的初始狀態為空，元素e1、e2、e3、e4、e5和e6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的序列為e2、e4、e3、e6、e5和e1，則棧S的容量至少應該為（ C ）。（2.0）
A、 6
B、 4
C、 3
D、 2

3、設棧的輸入序列為1、2、3… n，若輸出序列的第一個元素為n，則第i個輸出的元素為（ B ）。（2.0）
A、不確定
B、 n?i+1
C、 i
D、 n?i

4、在一個長度為n的順序表中刪除第i個元素（1<=i<=n）時，需向前移動（）個元素。（2.0）
A、 n?i
B、 n?i+1
C、 n?i?1
D、 i

5、若長度為n的線性表采用順序存儲結構存儲，在第i個位置上插入一個新元素的時間復雜度為（）。（2.0）
A、O(n)
B、 O(1)
C、O( $n^2$ )
D、O( $n^3$ )

6、表達式a(b+c)?d的后綴表達式是（）。（2.0）
A、 abcd+?
B、 abc+d?
C、 abc+d?
D、 ?+abcd

7、順序循環隊列中（數組的大小為n），隊頭指示front指向隊列的第1個元素，隊尾指示rear指向隊列最后元素的后1個位置，則循環隊列中存放了n - 1個元素，即循環隊列滿的條件為（）。（2.0）
A、 (rear+1)%n=front?1
B、 (rear+1)%n=front
C、 (rear)%n=front
D、 rear+1=front

8、兩個有序線性表分別具有n個元素與m個元素且n≤m，現將其歸并成一個有序表，其最少的比較次數是（）。（2.0）
A、n
B、 m
C、 n?1
D、 m+n

9、在一個具有n個結點的有序單鏈表中插入一個新結點并保持單鏈表仍然有序的時間復雜度是（）。（2.0）
A、O(1)
B、O(n)
C、O( $n^2$ )
D、O( $nlog_{2^n}$ )

10、若從鍵盤輸入n個元素，則建立一個有序單向鏈表的時間復雜度為（）。（2.0）
A、O(n)
B、O( $n^2$ )
C、O( $n^3$ )
D、O( $n×log2^n$ )

11、在一個單鏈表中，若p所指結點不是最后結點，在p之后插入s所指結點，則執行（）。（2.0）
A、 s->next=p;p->next=s;
B、 s->next=p->next;p->next=s;
C、 s->next=p->next;p=s;
D、 p->next=s;s->next=p;

12、前序遍歷和后序遍歷結果相同的二叉樹為（）。（2.0）
A、一般二叉樹
B、只有根結點的二叉樹
C、根結點無左孩子的二叉樹
D、根結點無右孩子的二叉樹
E、所有結點只有左子樹的二叉樹
F、所有結點只有右子樹的二叉樹

13、一棵具有5層的滿二叉樹所包含的結點個數為（）。（2.0）
A．15 B．31 C．63 D．32

14、如果某圖的鄰接矩陣是對角線元素均為零的上三角矩陣，則此圖是（）。（2.0）
A、有向完全圖
B、連通圖
C、強連通圖
D、有向無環圖

15、若鄰接表中有奇數個表結點，則一定（）。（2.0）
A、圖中有奇數個頂點
B、圖中有偶數個頂點
C、圖為無向圖
D、圖為有向圖

16、假設一個有n個頂點和e條弧的有向圖用鄰接表表示，則刪除與某個頂點vi相關的所有弧的時間復雜度是（）。（2.0）
A、 O(n)
B、 O(e)
C、 O(n+e)
D、 O( $n ? e$ )

17、下列哪一個選項不是圖8.34所示有向圖的拓撲排序結果（）。（2.0）

A、 AFBCDE
B、 FABCDE
C、 FACBDE
D、 FADBCE

18、判斷一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以利用（）。（2.0）
A、單源最短路Dijkstra算法
B、所有頂點對最短路Floyd算法
C、廣度優先遍歷算法
D、深度優先遍歷算法

19、在一個帶權連通圖G中，權值最小的邊一定包含在G的（）。（2.0）
A、最小生成樹中
B、深度優先生成樹中
C、廣度優先生成樹中
D、深度優先生成森林中

20、適用于折半查找的表的存儲方式及元素排列要求為（）。（2.0）
A、鏈式方式存儲，元素無序
B、鏈式方式存儲，元素有序
C、順序方式存儲，元素無序
D、順序方式存儲，元素有序

21、設順序存儲的線性表共有123個元素，按分塊查找的要求等分成3塊。若對索引表采用順序查找來確定塊，并在確定的塊中進行順序查找，則在查找概率相等的情況下，分塊查找成功時的平均查找長度為（）。（2.0）
A、 21
B、 23
C、 41
D、 62

22、已知含10個結點的二叉排序樹是一棵完全二叉樹，則該二叉排序樹在等概率情況下查找成功的平均查找長度等于（）。（2.0）
A、 1.0
B、 2.9
C、 3.4
D、 5.5

23、以下各選項所示的各棵二叉樹中，二叉排序樹是（）。（2.0）

A、

B、

C、

D、

24、有數據{53，30，37，12，45，24，96}，從空二叉樹開始逐步插入數據形成二叉排序樹，若希望高度最小，則應該選擇下列（）的序列輸入。（2.0）
A、 37,24,12,30,53,45,96
B、 45,24,53,12,37,96,30
C、 12,24,30,37,45,53,96
D、 30,24,12,37,45,96,53

25、對于哈希函數H(key)=key%13，被稱為同義詞的關鍵字是（）。（2.0）
A、 35和41
B、 23和39
C、 15和44
D、 25和51

26、下列序列中，（）是執行第一趟快速排序后得到的序列。（2.0）
A、 [da,ax,eb,de,bb]ff[ha,gc]
B、 [cd,eb,ax,da]ff[ha,gc,bb]
C、 [gc,ax,eb,cd,bb]ff[da,ha]
D、 [ax,bb,cd,da]ff[eb,gc,ha]

27、下面的序列中初始序列構成最小堆（小根堆）的是（）。（2.0）
A、 10、60、20、50、30、26、35、40
B、 70、40、36、30、20、16、28、10
C、 20、60、50、40、30、10、8、72
D、 10、30、20、50、40、26、35、60

28、在下列算法中，（）算法可能出現下列情況：在最后一趟開始之前，所有的元素都不在其最終的位置上。（2.0）
A、堆排序
B、插入排序
C、冒泡排序
D、快速排序

29、若需在O（nlogn）的時間內完成對數組的排序，且要求排序算法是穩定的，則可選擇的排序方法是（）。（2.0）
A、歸并排序
B、堆排序
C、快速排序
D、直接插入排序

30、以下排序方法中，不穩定的排序方法是（）。（2.0）
A、直接選擇排序
B、二分法插入排序
C、歸并排序
D、基數排序

31、一個序列中有10000個元素，若只想得到其中前10個最小元素，最好采用（）方法。（2.0）
A、快速排序
B、堆排序
C、插入排序
D、二路歸并排序

32、若要求盡可能快地對實數數組進行穩定的排序，則應選（）。（2.0）
A、快速排序
B、堆排序
C、歸并排序
D、基數排序

33、排序的趟數與待排序元素的原始狀態有關的排序方法是（）。（2.0）
A、冒泡排序
B、快速排序
C、插入排序
D、選擇排序

34、直接插入排序在最好情況下的時間復雜度為（）。（2.0）
A、 O（n）
B、 O（log n）
C、 O（nlog n）
D、 O（n2）

35、下面程序運行后的輸出結果是（）。（2.0）

#include <stdio.h>
void f(int p);
int main()
{  int a[5]={1,2,3,4,5},r=a;f(r);printf("%d\n",r);
}
void f(int p)
{  p=p+3;printf("%d,",p);
}

A、 1,3
B、 3,3
C、 3,1
D、 4,1

36、下面程序的輸出結果是什么（）。（2.0）

\#include <stdio.h>
int main( ){int x=20,y=40,p;p=&x;printf("%d,",p);p=x+10;p=&y;printf("%d,",p);p=y+20;printf("%d,%d\n",x,y);return 0;
}

A、 20,40,20,40
B、 20,40,30,60
C、 20,40,20,40
D、 30,60,30,60

37、二維數組M[i][j]的元素是4個字符（每個字符占一個存儲單元）組成的串，行下標i的范圍是0_{4，列下標j的范圍是0}5，M按行存儲時元素M[3][5]的起始地址與M按列存儲時地址相同的元素是（）。（2.0）
A、 M[2][4]
B、 M[3][ 4]
C、 M[3][5]
D、 M[4][4]

38、將三對角矩陣A[1…100][1…100]按行優先存入一維數組B[1…298]中，A中元素A[66][65]在數組B中的位置為（）。（2.0）
A、 198
B、 195
C、 197
D、 196

39、按照二叉樹的定義，具有三個結點的二叉樹有（）棵。（2.0）
A、 5
B、 4
C、 3
D、 6

40、二叉樹中第5層上的結點個數最多為( )（2.0）
A、 8
B、 15
C、 16
D、 20

41、一棵完全二叉樹上有768個結點，則該二叉樹中葉子結點的個數是（）。（2.0）
A、 257
B、 258
C、 384
D、 385

42、若G是一個非連通無向圖，共有28條邊，則該圖至少有多少個頂點（）。（2.0）
A、 7
B、 8
C、 9
D、 27

43、【2014統考真題】下列選項中，不可能是快速排序第2趟排序結果是（）。（2.0）
A、 2，3，5，4，6，7，9
B、 2，7，5，6，4，3，9
C、 3，2，5，4，7，6，9
D、 4，2，3，5，7，6，9

44、【2010統考真題】采用遞歸方式對順序表進行快速排序。下列關于遞歸次數的敘述中，正確的是（）。（2.0）
A、遞歸次數與初始數據的排列次序無關
B、每次劃分后，先處理較長的分區可以減少遞歸次數
C、每次劃分后，先處理較短的分區可以減少遞歸次數
D、遞歸次數與每次劃分后得到的分區的處理順序無關

45、【2019統考真題】排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱為一“趟”。下列序列中，不可能是快速排序第二趟結果的是（）。（2.0）
A、 5，2，16，12，28，60，32，72
B、 2，16，5，28，12，60，32，72
C、 2，12，16，5，28，32，72，60
D、 5，2，12，28，16，32，72，60

46、【2011統考真題】為實現快速排序算法，待排序序列宜采用的存儲方式是（）。（2.0）
A、順序存儲
B、散列存儲
C、鏈式存儲
D、索引存儲

47、【2010統考真題】對一組數據（2，12，16，88，5，10）進行排序，若前3趟排序結果如下：
第1趟排序結果：2，12，16，5，10，88
第2趟排序結果：2，12，5，10，16，88
第3趟排序結果：2，5，10，12，16，88
則采用的排序的方法可能是（）。（2.0）
A、冒泡排序
B、希爾排序
C、歸并排序
D、基數排序

48、【2012統考真題】在內部排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱為一趟排序。下列排序方法中，每趟排序結束后都至少能夠確定一個元素最終位置的方法是（）。
Ⅰ．簡單選擇排序 Ⅱ．希爾排序 Ⅲ．快速排序 Ⅳ．堆排序 Ⅴ．2路歸并排序（2.0）

A、僅Ⅰ、Ⅲ、Ⅳ
B、僅Ⅰ、Ⅲ、Ⅴ
C、僅Ⅱ、Ⅲ、Ⅳ
D、僅Ⅲ、Ⅳ、Ⅴ

49、【2015統考真題】下列排序算法中，元素的移動次數與關鍵字的初始排列次序無關的是（）。（2.0）
A、直接插入排序
B、冒泡排序
C、基數排序
D、快速排序

50、【2017統考真題】下列排序方法中，若將順序存儲更換為鏈式存儲，則算法的時間效率會降低的是（）。
Ⅰ．插入排序 Ⅱ．選擇排序 Ⅲ．冒泡排序 Ⅳ．希爾排序 Ⅴ．堆排序（2.0）
A、僅Ⅰ、Ⅱ
B、僅Ⅱ、Ⅲ
C、僅Ⅲ、Ⅳ
D、僅Ⅳ、Ⅴ