1：29和一個(gè)具有n個(gè)頂點(diǎn)的完全無向圖的邊數(shù)為()八

l.n(n+l)/2

2.n(n-l)/2

3.n(n-l)

4.n(n+l)

2：48對(duì)有n個(gè)記錄的有序表采用二分查找，其平均查找長(zhǎng)度的量級(jí)為()。

1.O(log2n)

2.O(nlog2n)

3.O(n)

4.0(n2)

3：1.線性鏈表中各結(jié)點(diǎn)之間的地址()。

1.必須連續(xù)

2.一定不連續(xù)

3.部分地址必須連續(xù)

4連續(xù)與否無所謂

4：8帶頭結(jié)點(diǎn)的單鏈表head為空的判斷條件是()。

Lhead==NULL

2.head->next==NULL

3.hcad->ncxt==hcad

4.head!=NULL

5：49.冒泡排序的時(shí)間復(fù)雜度是()。

1.0(n2)

2.O(nlog2n)

3.0(n)

4.O(log2n)

6：50對(duì)有n個(gè)記錄的表按記錄鍵值有序建立二叉排序樹，在這種情況下，其平均查找長(zhǎng)度的量級(jí)為

()。

l.O(n)

2.O(nlog2n)

3.0(1)

4.O(log2n)

7：19棧和隊(duì)列都是()

1.順序存儲(chǔ)的線性表

2.鏈?zhǔn)酱鎯?chǔ)的線性表

3.限制存取點(diǎn)的線性結(jié)構(gòu)

4.限制存取點(diǎn)的非線性結(jié)構(gòu)

8：18.設(shè)輸入序列為的A,B,CD,借助一個(gè)棧不可以得到的輸出序列是()。

l.A,B,C,D

2.A,C.D,B

4D、C,R,A

4.D,A,B,C

9：7.鏈棧和順序棧相比，有一個(gè)較明顯的優(yōu)點(diǎn)是（）。

1.通常不會(huì)出現(xiàn)棧滿的情況

2.通常不會(huì)出現(xiàn)?？盏那闆r

3.插入操作更加方便

4.刪除操作更加方便

10：21.鏈表不具有的特點(diǎn)是（）。

L可隨機(jī)訪問任一元素

2.插入刪除不需要移動(dòng)元素

3.不必事先估計(jì)存儲(chǔ)空間

4.所需空間與線性表長(zhǎng)度成正比

11：28.使具有9個(gè)頂點(diǎn)的無向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是（）。

1.6

2.8

3.5

4.4

12：40任何一個(gè)無向連通圖的最小生成樹（）。

L只有一棵

2.有一棵或多棵

3.一定有多棵

4.可能不存在

13：11若某鏈表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則采用（）存

儲(chǔ)方式最節(jié)省空間。

L單鏈表

2.雙鏈表

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

4.單循環(huán)鏈表

14：43數(shù)據(jù)表A中有10000個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用（）排序算法最節(jié)

省空間。

1.堆排序

2.希爾排序

3.快速排序

4.直接選擇排序

15：16設(shè)輸入序列為的123,4,借助一個(gè)?？梢缘玫降妮敵鲂蛄惺牵ǎ?。

1.1,3,4,2

23,1,4,2

3.4,3,1,2

4.4,1,2,3

16：34在線索二叉樹中，結(jié)點(diǎn)（九）沒有左子樹的充要條件是（）。

l.t->left==NULL

2.t->ltag==l

3.t->ltag==l&&t->left==NULL

4.以上都不對(duì)

17：14在一個(gè)單鏈表中，已知產(chǎn)q)結(jié)點(diǎn)是(他)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在(*q^M*p)之間插入(*§)結(jié)點(diǎn)，則執(zhí)

行()。

1.s->next=p->next;p->next=s;

2.p->next=s->nexl;s->next=p;

3.q->next=s;s->next=p;

4.p->next=s;s->next=q;

18：42下列排序算法中,某一趟結(jié)束后未必能選出一個(gè)元素放其最終位置上的是（）。

L堆排序

2.冒泡排序

3.快速排序

4.直接插入排序

19：5.線性表的長(zhǎng)度是指（）

1.順序存儲(chǔ)方式下數(shù)組所占的空間大小

2.鏈?zhǔn)酱鎯?chǔ)方式下所有結(jié)點(diǎn)占莊的空間大小

3.表中的元素個(gè)數(shù)

4.所能存儲(chǔ)的最大的結(jié)點(diǎn)個(gè)數(shù)

20：6.某數(shù)組第一個(gè)元索的存儲(chǔ)地址為200,每個(gè)元素的長(zhǎng)度為4,則第五個(gè)元素的地址是：）。

1.210

2.208

3.216

4.220

1：22.若已知一個(gè)棧的輸入序列為1,2,3,4,......n,其輸出序列pl,p2..........pn（>若pl=n,則pi

為

l.i

2,n-i

3.n-i+l

4.不確定

2：31按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有（）種。

1.3

2.4

3.5

4.6

3：5.線性表的長(zhǎng)度是指（）

1.順序存儲(chǔ)方式下數(shù)組所占的空間大小

2.鏈?zhǔn)酱鎯?chǔ)方式下所有結(jié)點(diǎn)占用的空間大小

3.表中的元素個(gè)數(shù)

4.所能存儲(chǔ)的最大的結(jié)點(diǎn)個(gè)數(shù)

4：23對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)是為了（）

1.便于進(jìn)行矩陣運(yùn)算

2.便于輸入和輸出

3.節(jié)省存儲(chǔ)空間

4.降低運(yùn)算的時(shí)間復(fù)雜度

5：4.不帶頭結(jié)點(diǎn)的單鏈表head為空的判斷條件是（）。

l.head==NULL

2,head->next==NULL

3.hcad->ncxt==hcad

4..head!=NULL

6：35在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要（）邊。

Ln

2.n+l

3.n-l

4.n/2

7：30某二叉樹的前序和后序序列正好相同，則該二叉樹一定是（）的二叉樹。

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

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

3.任一結(jié)點(diǎn)無左孩子

4.任一結(jié)點(diǎn)無右孩子

8：49.冒泡排序的時(shí)間復(fù)雜度是()。

1.0(n2)

2.O(nlog2n)

3.O(n)

4.O(log2n)

9：29.在一個(gè)具有n個(gè)頂點(diǎn)的完全無向圖的邊數(shù)為（）。

l.n（n+l）/2

2.n（n-l）/2

3.n（n-l）

4.n（n+l）

10：48對(duì)有n個(gè)記錄的有序表采用二分查找，其平均查找長(zhǎng)度的量級(jí)為（）。

1.O（log2n）

2.O（nlog2n）

3O(n)

4.0(n2)

II：21.鏈表不具有的特點(diǎn)是（）。

I.可隨機(jī)訪問任一元素

2.插入刪除不需要移動(dòng)元素

3.不必事先估計(jì)存儲(chǔ)空間

4.所需空間與線性表長(zhǎng)度成正比

12；46下列四個(gè)關(guān)鍵字序列中,（）不是堆。

I.{05,23,16,68,94,72,71,731

2.{05/6,23,68,94,72,71,73}

3.{05,23,16,73,94,72,71,681

4.{05,23,16,68,73,71,72,94}

13：14在一個(gè)單鏈表中，已知（*q）結(jié)點(diǎn)是（*p）結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在（%）和（*十）之間插入。s）結(jié)

點(diǎn),則執(zhí)行（）。

I.s->next=p->next;p->next=s;

2.p->nex(=s->next;s->next=p;

3.q->next=s;s->next=p;

4.p->next=s;s->next=q;

14：28.使具有9個(gè)頂點(diǎn)的無向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是（）。

1.6

2.8

3.5

4.4

15：20.設(shè)輸入序列為12345,借助一個(gè)?？梢缘玫降妮敵鲂蛄惺牵ǎ?。

1.241,3,5

234,1,5,2

332,4,1,5

4.4』,3,2,5

16：47.當(dāng)初始序列已經(jīng)按犍值有序時(shí)，用直接插入算法進(jìn)行排序，需要比較的次數(shù)為（）。

I.n2

2.nlog2n

3.1og2n

4.n-1

17：45.若表i"在排序前已按元素鍵值遞增順序排列，采用（）方法比較次數(shù)較少。

1.直接插入排序

2.快速排序

3.歸并排序

4.選擇排序

IX：3若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu),在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)

間復(fù)雜度為（）。（l?i?n+l）

1.0(0)

2.0(1)

3.0(n)

4.0(n2)

19：2線性表是具有n個(gè)（）的有限序列。

I.表元素

2.字符

3.數(shù)據(jù)元素

4.信息項(xiàng)

20：13非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p指針?biāo)福M足（）。

1.p->ncxt==NULL

2.p==NULL

3.p->ncxt==hcad

4.p=head

I：20.設(shè)輸入序列為12345,借助一個(gè)?？梢缘玫降妮敵鲂蛄惺牵ǎ?。

1.2,4,1,3,5

2.3,4,152

3.3,241,5

4.4,1,3,2,5

2：7.鏈棧和順序枝相比，有一個(gè)較明顯的優(yōu)點(diǎn)是（）。

I.通常不會(huì)出現(xiàn)棧滿的情況

2.通常不會(huì)出現(xiàn)?？盏那闆r

3.插入操作更加方便

4.刪除操作更加方便

3：26.具有n個(gè)頂點(diǎn)的有向圖最多可包含（）條有向邊。

l.n-1

2.n

3.n（n-l）/2

4.n（n-l）

4：18.設(shè)輸入序列為的A,B,C,D,借助一個(gè)棧不可以得到的輸出序列是（）。

I.A,B,C,D

2.A,C,D,B

3.D,C,B,A

4.D,A,B,C

5：35在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要（）邊。

l.n

2.n+l

3n-l

4.n/2

6：29.在一個(gè)具有n個(gè)頂點(diǎn)的完全無向圖的邊數(shù)為()。

l.n(n+l)/2

2.n(n-l)/2

3.n(n-l)

4.n(n+l)

7；9在單鏈表中增加頭結(jié)點(diǎn)的目的是為了()。

1.方便運(yùn)算的實(shí)現(xiàn)

2.用于標(biāo)識(shí)單鏈表

3.使單鏈表中至少有一個(gè)結(jié)點(diǎn)

4.用于標(biāo)識(shí)起始結(jié)點(diǎn)的位置

8：31按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有()種。

1.3

2.4

3.5

4.6

9：50對(duì)有n個(gè)記錄的表按記錄鍵值有序建立二叉排序樹，在這種情況下，其平均查找長(zhǎng)度

的量級(jí)為()。

l.O(n)

2.O(nlog2n)

3.0(1)

4.O(log2n)

10：46下列四個(gè)關(guān)鍵字序列中,()不是堆。

1.{05,23,16,68,94,72,71,73)

2.{05,16,23,68,94,72,71,73}

3.{05,23,16,73,94,72,71,681

4.{05,23,16,68,73,71,72,94}

11：48對(duì)有n個(gè)記錄的有序表采用二分查找，其平均查找長(zhǎng)度的量級(jí)為()。

I.O(log2n)

2.O(nlog2n)

3.0(n)

4.O(n2)

12：32有64個(gè)節(jié)點(diǎn)的完全二叉樹的高度為()(根的層次為I)。

1.8

2.7

3.6

4.5

13vz.用分劃交換排序方法對(duì)包含有n個(gè)關(guān)鍵的序列進(jìn)行排序.最壞情況卜.執(zhí)行的時(shí)間雜度

為（）。

l.O（n）

2.O（log2n）

3.O（nlog2n）

4.O（n2）

14：47.當(dāng)初始序列已經(jīng)按犍值有序時(shí)，用直接插入算法進(jìn)行排序，需要比較的次數(shù)為（）。

I.n2

2.nlog2n

3.log2n

4.n-1

15：38.鄰接表的存儲(chǔ)結(jié)構(gòu)下圖的深度優(yōu)先遍歷類似于二叉樹（樹）的（）。

I.先序遍歷

2.中序遍歷

3.后序遍歷

4.按層遍歷

16：30某二叉樹的前序和后序序列正好相同，則該二叉樹一定是（）的二叉樹。

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

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

3.任一結(jié)點(diǎn)無左孩子

4.任一結(jié)點(diǎn)無右孩子

17：14在一個(gè)單鏈表中，已知(*q)結(jié)點(diǎn)是(叩)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在(*q)和(*p)之間插入(右)結(jié)

點(diǎn),則執(zhí)行()。

1.s->next=p->next;p->next=s;

2.p->next=s->next;s->next=p;

3.q->next=s;s->next=p;

4.p->ncxt=s;s->next=q;

18：11若某鏈表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則

采用（）存儲(chǔ)方式最節(jié)省空間。

1.單鏈表

2.雙鏈表

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

4.單循環(huán)鏈表

19：45.若表r在排序前已按元素鍵值遞增順序排列，采用（）方法比較次數(shù)較少。

I.直接插入排序

2.快速排序

3.歸并排序

4.選擇排序

20：13非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p指針?biāo)福M足（）。

I.p->next==NUIJ.

2.p==NULL

3.p->next==head

4.p=head

I：7.鏈棧和順序棧相比，有一個(gè)較明顯的優(yōu)點(diǎn)是（）。

1.通常不會(huì)出現(xiàn)棧滿的情況

2.通常不會(huì)出現(xiàn)?？盏那闆r

3.插入操作更加方便

4.刪除操作更加方便

2：6.某數(shù)組第一個(gè)元素的存儲(chǔ)地址為200,每個(gè)元素的長(zhǎng)度為4,則第五個(gè)元素的地址是（）。

1.210

2.208

3.216

4.220

3：30某二叉樹的前序和后序序列正好相同，則該二叉樹一定是（）的二叉樹。

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

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

3.任一結(jié)點(diǎn)無左孩子

4.任一結(jié)點(diǎn)無右孩子

4：3若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間

復(fù)雜度為（）。（l?i?n+l）

1.0(0)

2.0(1)

3.0(n)

4.O(n2)

5：41.如果待排序序列中兩個(gè)數(shù)據(jù)元素具有相同的值，在排序后它們的位置發(fā)生顛倒，則稱

該排序是不穩(wěn)定的。（）就是不穩(wěn)定的排序方法。

1.起泡排序

2.歸并排序

3.直接插入法排序

4.簡(jiǎn)單選擇排序

6：28.使具有9個(gè)頂點(diǎn)的無向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是（）。

1.6

2.8

3.5

4.4

7：5.線性表的長(zhǎng)度是指（）

I.順序存儲(chǔ)方式下數(shù)組所占的空間大小

2.鏈?zhǔn)酱鎯?chǔ)方式下所有結(jié)點(diǎn)占用的空間大小

4.表中的元素個(gè)數(shù)

4.所能存儲(chǔ)的最大的結(jié)點(diǎn)個(gè)數(shù)

8：44下列排序算法中，第一趟排序完畢后，其最大或最小元素一定在其最終位置上的算法是

()o

I.歸并排序

2.直接插入排序

3.快速排序

4.冒泡排序

9：20.設(shè)輸入序列為1,2,345,借助一個(gè)?？梢缘玫降妮敵鲂蛄惺?)。

1.2,4,13,5

2.341,5,2

3.3,241,5

4.4,1,3,2,5

10：15在一個(gè)單鏈表中，若刪除(*p)結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行()。

I.p->next=p->nexl->next:

2.p=p-^next;p->nexi=p->nex(->nex(;

3.p->next=p->next;

4.p=p->next->next;

11：21.鏈表不具有的特點(diǎn)是()。

1.可隨機(jī)訪問任一元素

2.插入刪除不需要移動(dòng)元素

3.不必事先估計(jì)存儲(chǔ)空間

4.所需空間與線性表長(zhǎng)度成正比

12：50對(duì)有n個(gè)記錄的表按記錄鍵值有序建立二叉排序褥，在這種情況下，其平均查找長(zhǎng)度

的量級(jí)為()。

l.O(n)

2.O(nlog2n)

3.0(1)

4.O(log2n)

13：11若某鏈表最常用的慷作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則

采用()存儲(chǔ)方式最節(jié)省空間。

1.單鏈表

2.雙鏈表

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

4.單循環(huán)鏈表

14：49.冒泡排序的時(shí)間復(fù)雜度是()。

I.0(n2)

2.O(nlog2n)

3.0(n)

4.O(1og?n)

15：22.若已知一個(gè)棧的輸入序列為1,2,3,4,....n,其輸出序列pl,p2,....pno若pl=n,則pi

為

l.i

2.n-i

3.n-i+l

4.不確定

16；43數(shù)據(jù)表A中有10000個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用（）排序

算法最節(jié)省空間。

I.堆排序

2.希爾排序

3.快速排序

4.直接選擇排序

17：31按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有（）種。

1.3

2.4

3.5

4.6

18：46下列四個(gè)關(guān)鍵字序列中,（）不是堆。

1.{05,23,16,68,94,72,71,73}

2.{05,16,23,68,94,72,71,73}

3.{05,23,16,73,94,72,71,68)

4.[05,23,16,68,73,71,72,94)

19：19棧和隊(duì)列都是（）

1.順序存儲(chǔ)的線性表

2.鏈?zhǔn)酱鎯?chǔ)的線性表

3.限制存取點(diǎn)的線性結(jié)構(gòu)

4.限制存取點(diǎn)的非線性結(jié)構(gòu)

20：23對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)是為了（）

I.便于進(jìn)行矩陣運(yùn)算

2.便于輸入和輸出

3.節(jié)省存儲(chǔ)空間

4.降低運(yùn)算的時(shí)間復(fù)雜度

1：50對(duì)有n個(gè)記錄的表按記錄鍵值有序建立二叉排序樹，在這種情況下，其平均查找長(zhǎng)度

的量級(jí)為（）。

1.0（n）

2.O（nlog2n）

3.0（1）

4.O（log2n）

2：34在線索二叉樹中，結(jié)點(diǎn)（?。]有左子樹的充要條件是（）“

|.t->left==NULL

2.t->ltag==l

3.t->ltag==l&&t->left==NULL

4.以上都不對(duì)

3：20.設(shè)輸入序列為123,4,5,借助一個(gè)?？梢缘玫降妮敵鲂蛄惺牵ǎ?。

124,1,3,5

234,1,5,2

33,2,4,1,5

4.4,1,3,2,5

4：30某二叉樹的前序和后序序列正好相同，則該二叉樹一定是（）的二叉樹。

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

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

3.任一結(jié)點(diǎn)無左孩子

4.任一結(jié)點(diǎn)無右孩子

5：47.當(dāng)初始序列己經(jīng)按鍵值有序時(shí)，用直接插入算法進(jìn)行排序，需要比較的次數(shù)為（）。

l.n2

2.nlog2n

3.1og2n

4.n-1

6：43數(shù)據(jù)表A中有10000個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用（）排序算

法最節(jié)省空間。

I.堆排序

2.希爾排序

3.快速排序

4.直接選擇排序

7：49.冒泡排序的時(shí)間復(fù)雜度是()。

1.0(n2)

2.O(nlog2n)

3.O(n)

4.O(log2n)

8：1.線性鏈表中各結(jié)點(diǎn)之間的地址（）。

I.必須連續(xù)

2.一定不連續(xù)

3.部分地址必須連續(xù)

4.連續(xù)與否無所謂

9：24串是（）

I.一些符號(hào)構(gòu)成的序列

2.一些字母構(gòu)成的序列

4一個(gè)以上字符構(gòu)成的序列

4.任意有限個(gè)字符構(gòu)成的序列

10：37.用分劃交換排序方法對(duì)包含有n個(gè)關(guān)鍵的序列進(jìn)行排序，最壞情況下執(zhí)行的時(shí)間雜度

為()。

I.O(n)

2.O(log2n)

3.O(nlog2n)

4.O(n2)

II：6.某數(shù)組第一個(gè)元素的存儲(chǔ)地址為200,每個(gè)元素的長(zhǎng)度為4,則第五個(gè)元素的地址是()。

1.210

2.208

3.216

4.220

12：28.使具有9個(gè)頂點(diǎn)的無向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是()。

1.6

2.8

3.5

4.4

13：22.若已知一個(gè)棧的輸入序列為1,2,3,4....,n,其輸出序列pl,p2,....pn?若pl=n，則pi

為

Li

2.n-i

3.n-i+l

44確定

14：14在一個(gè)單鏈表中，已知(*q)結(jié)點(diǎn)是(*p)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在(*4)和(*十)之間插入(*5)結(jié)

點(diǎn),則執(zhí)行()。

I.s->next=p->next;p->nexi=s;

2.p->next=s->next;s->next=p;

3.q->next=s;s->nexl=p;

4.p->next=s;s->next=q;

15：40任何一個(gè)無向連通圖的最小生成樹()。

1.只有一棵

2.有一棵或多棵

3.一定有多棵

4.可能不存在

16：18.設(shè)輸入序列為的A,B,C,D,借助一個(gè)棧不可以得到的輸出序列是()。

1ABeD

2.A,C,D,B

3.D,C,B,A

4D,A,R,C

17：41.如果待排序序列中兩個(gè)數(shù)據(jù)元素具有相同的值，在排序后它們的位置發(fā)生顛倒，則

稱該排序是不穩(wěn)定的。（）就是不穩(wěn)定的排序方法。

1.起泡排序

2.歸并排序

3.直接插入法排序

4.簡(jiǎn)單選擇排序

18；33.任何一棵二叉樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)位置。。

I.不發(fā)生變化

2.發(fā)生變化

3.不能確定

4.一定發(fā)生改變

19：48對(duì)有n個(gè)記錄的有序表采用二分查找，其平均查找長(zhǎng)度的量級(jí)為（）。

1.O（log2n）

2.O（nlog2n）

3.O（n）

4.0（n2）

20：7.鏈棧和順序棧相比，有一個(gè)較明顯的優(yōu)點(diǎn)是（）。

1.通常不會(huì)出現(xiàn)棧滿的情況

2.通常不會(huì)出現(xiàn)?？盏那闆r

3.插入操作更加方便

4.刪除操作更加方便

I：39.鄰接表的存儲(chǔ)結(jié)構(gòu)下圖的廣度優(yōu)先遍歷類似于二叉樹（樹）的（）。

1.先序遍歷

2.中序遍歷

3.后序遍歷

4.按層遍歷

2：45.若表r在排序前已按元素鍵值遞增順序排列，采用（）方法比較次數(shù)較少。

I.直接插入排序

2.快速排序

3.歸并排序

4.選擇排序

3：3若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間

復(fù)雜度為（）。（l?i?n+l）

1.0(0)

2.0(1)

3.0(n)

4.0(n2)

4：44下列排序算法中，第一趟排序完畢后，其最大或最小元素一定在其最終位置上的算法是

（K

I.歸并排序

2.直接插入排序

3.快速排序

4.冒泡排序

5：7.鏈棧和順序棧相比，有一個(gè)較明顯的優(yōu)點(diǎn)是（）。

I.通常不會(huì)出現(xiàn)棧滿的情況

2.通常不會(huì)出現(xiàn)棧空的情況

3.插入操作更加方便

4.刪除操作更加方便

6：15在一個(gè)單鏈表中，若刪除（*p）結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行（）。

I.p->next=p->next->next;

2.p=p->ncxt;p->ncxt=p->ncxt->ncxt;

3,p->next=p->next;

4.p=p->next->ncxt;

7：47.當(dāng)初始序列己經(jīng)按鍵值有序時(shí)，用直接插入算法進(jìn)行排序，需要比較的次數(shù)為（）。

l.n2

2.nlog2n

3.1og2n

4.n-1

8：18.設(shè)輸入序列為的A,B,CD,借助一個(gè)棧不可以得到的輸出序列是（）。

1.A,B,C,D

2.A,C,D,B

3.D,C,B,A

4.D,A,B,C

9：23對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)是為了（）

I.便于進(jìn)行矩陣運(yùn)算

2.便于輸入和輸出

3.節(jié)省存儲(chǔ)空間

4.降低運(yùn)算的時(shí)間復(fù)雜度

10：11若某鏈表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則

采用（）存儲(chǔ)方式最節(jié)省空間。

1.單鏈表

2.雙鏈表

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

4.單循環(huán)鏈表

11：25.某二叉樹的前序和后序序列正好相反，則該二叉樹一定是（）二叉樹。

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

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

4任意結(jié)點(diǎn)無左孩子

4.任意結(jié)點(diǎn)無右孩子

12：22.若已知一個(gè)棧的輸入序列為1,2,3,4,……,n,其輸出序列pl,p2,…,pn。若pl=n，則pi

為

Li

2.n-i

3.n-i+l

4不確定

13：46下列四個(gè)關(guān)鍵字序列中,（）不是堆。

1.{05,23,16,68,94,72,71,73}

2.{05,16,23,68,94,72,71,73)

3.{05,23,16,73,94,72,71,68)

4.{05,2316,68,73,71,72,94}

14：35在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要（）邊。

2.n+l

3.n-l

4.n/2

15：43數(shù)據(jù)表A中有10000個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用（）排序

算法最節(jié)省空間。

1.堆排序

2.希爾排序

3.快速排序

4.直接選擇排序

16：17.以下敘述正確的是（）。

1.在順序存儲(chǔ)的線性表中,邏輯上相鄰的兩個(gè)數(shù)據(jù)元素在物理上并不一定相鄰

2.鏈?zhǔn)酱鎯?chǔ)的線性表可以隨機(jī)存取

3.順序存儲(chǔ)的線性表可以隨機(jī)存取

4.在線性表的順序存儲(chǔ)結(jié)構(gòu)中，插入和刪除元素時(shí)，移動(dòng)元素的個(gè)數(shù)僅于該元素的位置有關(guān)

17：34在線索二叉樹中，結(jié)點(diǎn)（*t）沒有左子樹的充要條件是（）。

|.t->left==NULL

2.t->ltag==l

3.t->llag==l&&t->left==NULL

4.以上都不對(duì)

18：24串是（）

I.一些符號(hào)構(gòu)成的序列

2.一些字母構(gòu)成的序列

3.一個(gè)以上字符構(gòu)成的序列

4.任意有限個(gè)字符構(gòu)成的序列

19：33.任何一棵二叉樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)位置（）。

1.不發(fā)生變化

2.發(fā)生變化

3.不能確定

4.一定發(fā)生改變

20：32有64個(gè)節(jié)點(diǎn)的完全二叉樹的高度為（）（根的層次為1）o

1.8

2.7

3.6

4.5

19：27.二分查找法要求查找表中各元素的鍵值必須是（）排列。

1.遞增或遞減

2.遞增

3.遞減

4無序

9：12.單鏈表的存儲(chǔ)密度（）。

「1.大于1

「2.等于1

④3.小于1

’4.不能確定

20：36在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（）倍。

「1.1/2

3.2

r4.4

數(shù)據(jù)結(jié)構(gòu)

（-）

一、單選題

1.

下列排序算法中,某一趟結(jié)束后未必能選出一個(gè)元素放其最終位置上的是（）。

A.堆排序

B.冒泡排序

C.快速排序

D.直接插入排序

得分：4

答案D

2.

棧和隊(duì)列都是（）

A.順序存儲(chǔ)的線性表

B.鏈?zhǔn)?7儲(chǔ)的線性表

C.限制存取點(diǎn)的線性結(jié)構(gòu)

D.限制存取點(diǎn)的非線性結(jié)構(gòu)

答案C

3.

串是（）

A.一些符號(hào)構(gòu)成的序列

B.一些字母構(gòu)成的序列

C.一個(gè)以上字符構(gòu)成的序列

D.任意有限個(gè)字符構(gòu)成的序列

答案D

任何一棵二叉樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)位置（）0

A.不發(fā)生變化

B.發(fā)生變化

C.不能確定

D.一定發(fā)生改變

答案A

某二叉樹的前序和后序序列正好相反，則該二叉樹一定是（）二叉樹。

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

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

C.任意結(jié)點(diǎn)無左孩子

D.任意結(jié)點(diǎn)無右孩子

答案B

冒泡排序的時(shí)間復(fù)雜度是（）。

A.0(n2)

B.O(nlog2n)

C.O(n)

D.O(log2n)

答案A

使具有9個(gè)頂點(diǎn)的無向圖成為?個(gè)述通圖至少應(yīng)有邊的條數(shù)是（）.

A.6

B.8

C.5

D.4

答案B

8.

數(shù)據(jù)表A中有10000個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用（）排序算法最節(jié)省空間。

A.堆排序

B.希爾排序

C.快速排序

D.直接選擇排序

答案A

9.

在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要（）邊。

B.n+1

C.n-1

D.n/2

答案C

10.

在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（）倍。

A.1/2

答案B

11.

鏈表不具有的特點(diǎn)是（）c

A.可隨機(jī)訪問任一元素

B.插入刪除不需要移動(dòng)元素

C.不必事先估計(jì)存儲(chǔ)空間

D.所需空間與線性表長(zhǎng)度成正比

答案A

12.

二分查找法要求查找表中各元素的鍵值必須是（）排列。

A.遞增或遞減

B.遞增

C.遞減

D.無序

答案A

13.

下列四個(gè)關(guān)鍵字序列中,（）不是堆。

A.{05,23,16,68,94,72,71,73}

B.{05,16,23,68,94.72,71,73}

C.{05,23,16,73,94,72,71,68}

D.{05,23,16.68,73,71,72,94}

答案C

14.

下列排序算法中，第一趟排序完畢后，其最大或最小元素一定在其最終位置上的算法是（）。

A.歸并排序

B.直接插入排序

C.快速排序

D.冒泡排序

答案D

15.

對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)是為了（）

A.便于進(jìn)行矩陣運(yùn)算

B.便于輸入和輸出

C.節(jié)省存儲(chǔ)空間

D.降低運(yùn)算的時(shí)間復(fù)雜度

答案C

16.

任何一個(gè)無向連通圖的最小生成樹Oc

A.只有一棵

B.有一棵或多棵

C.一定有多棵

D.可能不存在

答案B

17.

若已知一個(gè)棧的輸入序列為1,2,3,4,.........n其輸出序列pl,p2,piio若pl=n,則pi為

A.i

B.n-i

C.n-i+1

D.不確定

答案C

18.

鄰接表的存儲(chǔ)結(jié)構(gòu)下圖的廣度優(yōu)先遍歷類似于二叉樹(樹)的()。

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.按層遍歷

答案D

19.

若表r在排序前已按元素鍵值遞增順序排列，采用()方法比較次數(shù)較少。

A.直接插入排序

B.快速排序

C.歸并排序

D.選擇排序

答案A

2().

對(duì)有n個(gè)記錄的有序表采用二分查找，其平均查找長(zhǎng)度的量級(jí)為()。

A.O(Iog2n)

B.O(nlog2n)

C.0(n)

D.0(n2)

答案A

21.

有64個(gè)節(jié)點(diǎn)的完全二叉樹的高度為（）（根的層次為1）。

A.8

B.7

C.6

D.5

答案B

22.

如果待排序序列中兩個(gè)數(shù)據(jù)元素具有相同的值，在排序后它們H勺位置發(fā)生顛倒，則稱該排序是不穩(wěn)定的。

（）就是不穩(wěn)定的排序方法。

A.起泡排序

B.歸并排序

C.直接插入法排序

D.簡(jiǎn)單選擇排序

答案D

23.

按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有（）種。

A.3

B.4

C.5

D.6

答案C

24.

設(shè)輸入序列為123,4.5,借助一個(gè)?？梢缘玫降妮敵鲂蛄惺牵ǎ?。

A.2,4,135

B.3,4』,5,2

C.3,2,4,1,5

D.4,1,325

答案C

25.

鄰接表的存儲(chǔ)結(jié)構(gòu)下圖的深度優(yōu)先遍歷類似于二叉樹（樹）的（）。

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.按層遍歷

答案A

（二）

一、單選題

1.

下列排序算法中,某?趟結(jié)束后未必能選出??個(gè)元素放其最終位置上的是（）。

A.堆排序

B.冒泡排序

C.快速排序

D.直接插入排序

得分：4

答案D

2.

棧和隊(duì)列都是（）

A.順序存儲(chǔ)的線性表

B.鏈?zhǔn)酱鎯?chǔ)的線性表

C.限制存取點(diǎn)的線性結(jié)構(gòu)

D.限制存取點(diǎn)的非線性結(jié)構(gòu)

答案C

3.

串是（）

A.一些符號(hào)構(gòu)成的序列

B.一些字母構(gòu)成的序列

C.一個(gè)以上字符構(gòu)成的序列

D.任意有限個(gè)字符構(gòu)成的序列

答案D

任何一棵二義樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)位置（）。

A.不發(fā)生變化

B.發(fā)生變化

C.不能確定

D.一定發(fā)生改變

答案A

某二叉樹的前序和后序序列正好相反，則該二叉樹一定是()二叉樹。

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

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

C.任意結(jié)點(diǎn)無左孩子

D.任意結(jié)點(diǎn)無右孩子

答案B

冒泡排序的時(shí)間更雜度是()。

A.0(n2)

B.O(nlog2n)

C.O(n)

D.O(log2n)

答案A

使具有9個(gè)頂點(diǎn)的無向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是()。

A.6

B.8

C.5

D.4

答案B

數(shù)據(jù)表A中有10000個(gè)元素，如果僅要求求出其中最大的1()個(gè)元素，則采用()排序算法最節(jié)省空間。

A.堆排序

B.希爾排序

C.快速排序

D.直接選擇排序

答案A

9.

在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要()邊。

A.n

B.n+1

Cn-l

D.n/2

答案C

10.

在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（）倍。

A.1/2

B.1

C.2

D.4

答案B

11.

鏈表不具有的特點(diǎn)是（）。

A.可隨機(jī)訪問任一元素

B.插入刪除不需要移動(dòng)元素

C.不必事先估計(jì)存儲(chǔ)空間

D.所需空間與線性表度成正比

答案A

12.

二分查找法要求查找表中各元素的鍵值必須是（）排列。

A.遞增或遞減

B.遞增

C.遞減

D.無序

答案A

13.

下列四個(gè)關(guān)鍵字序列中,（）不是堆。

A.{05,23,16.68,94.72,71,73}

B.{05,16,23,68,94,72,71,73}

C.{05,23,16,73,94,72,71,68）

D.{05,23,16,68,73,71,72,94}

答案C

14.

下列排序算法中，第一趟排序完畢后，其最大或最小元素一定在其最終位置上的算法是（）。

A.歸并排序

R-直接插入排序

C.快速排序

D.冒泡排序

答案D

15.

對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)是為了（）

A.便于進(jìn)行矩陣運(yùn)算

B.便于輸入和輸出

C.節(jié)省存儲(chǔ)空間

D.降低運(yùn)算的時(shí)間復(fù)雜度

答案C

16.

任何一個(gè)無向連通圖的最小生成樹（）。

A.只有一棵

B.有一棵或多棵

C.一定有多棵

D.可能不存在

答案B

17.

若已知一個(gè)棧的輸入序列為1,2,3,4,.......,n,其輸出序列pl,p2,…..,pn。若pl=n，貝4pi為

A.i

B.n-i

C.n-i+1

D.不確定

答案C

鄰接表的存儲(chǔ)結(jié)構(gòu)下圖的廣度優(yōu)先遍歷類似r?二叉樹（樹）的（）。

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.按層遍歷

答案D

19.

若表r在排序前已按元素鍵值遞增順序排列，采用（）方法比較次數(shù)較少。

A.直接插入排序

B.快速排序

C.歸并排序

D.選擇排序

答案A

20.

對(duì)有n個(gè)記錄的有序表采用二分查找，其平均查找長(zhǎng)度的量級(jí)為（）。

A.O（log2n）

B.O（nlog2n）

C.O（n）

D.O（n2）

答案A

21.

有64個(gè)節(jié)點(diǎn)的完全二叉樹的高度為（）（根的層次為1）。

A.8

B.7

C.6

D.5

答案B

22.

如果待排序序列中兩個(gè)數(shù)據(jù)元素具有相同的值，在排序后它們H勺位置發(fā)生顛倒，則稱該排序是不穩(wěn)定的。

（）就是不穩(wěn)定的排序方法。

A.起泡排序

B.歸并排序

C.直接插入法排序

D.簡(jiǎn)單選擇排序

答案D

23.

按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有（）種。

A.3

B.4

C.5

D.6

答案C

24.

設(shè)輸入序列為123,4,5,借助一個(gè)?？梢缘玫降妮敵鲂蛄惺牵ǎ?/p>

A.2,4,1,3,S

B.3,4,1,52

C.3,2,4,1,5

D.4,1,325

答案C

25.

鄰接表的存儲(chǔ)結(jié)構(gòu)下圖的深度優(yōu)先遍歷類似于二叉樹（樹）的（）。

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.按層遍歷

答案A

（三）

一、單選題

1.

卜.列排序算法中,某一趟結(jié)束后未必能選出一個(gè)元素放其最終位置上的是（）。

A.堆排序

B.冒泡排序

C.快速排序

D.直接插入排序

答案D

串是（）

A.一些符號(hào)構(gòu)成的序列

B.一些字母構(gòu)成的序列

C.一個(gè)以上字符構(gòu)成的序列

D.任意有限個(gè)字符構(gòu)成的序列

答案D

任何一棵二叉樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)位置.（）。

A.不發(fā)生變化

B.發(fā)生變化

C.不能確定

D.一定發(fā)生改變

答案A

某二叉樹的前序和后序序列正好相反，則該二叉樹一定是()二叉樹。

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

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

C.任意結(jié)點(diǎn)無左孩子

D.任意結(jié)點(diǎn)無右孩子

答案B

冒泡排序的時(shí)間復(fù)雜度是()。

A.O(n2)

B.O(nlog2n)

C.0(n)

D.O(log2n)

答案A

使具有9個(gè)頂點(diǎn)的無向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是()。

A.6

B.8

C.5

D.4

答案B

數(shù)據(jù)表A中有1(X)()O個(gè)元素，如果僅要求求出其中最大的1()個(gè)元素，則采用()排序算法最節(jié)省空間。

A.堆排序

B.希爾排序

C.快速排序

D.直接選擇排序

答案A

8.

線性鏈表中各結(jié)點(diǎn)之間的地址()。

A.必須連續(xù)

B.一定不連續(xù)

C.部分地址必須連續(xù)

D.連續(xù)與否無所謂

答案D

9.

在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要（）邊。

A.n

B.n+1

C.n-1

D.n/2

答案C

10.

鏈表不具有的特點(diǎn)是（）。

A.可隨機(jī)訪問任一元素

B.插入刪除不需要移動(dòng)元素

C.不必事先估計(jì)存儲(chǔ)空間

D.所需空間與線性表長(zhǎng)度成正比

答案A

二分查找法要求查找表中各兀素的鍵值必須是（）排列。

A.遞增或遞減

B.遞增

C.遞減

D.無序

答案A

12.

當(dāng)初始序列已經(jīng)按鍵值有序時(shí)，用直接插入算法進(jìn)行排序，需要比較的次數(shù)為（）。

A.112

B.nlog2n

C.Iog2n

D.n-I

答案D

13.

在線索二叉樹中，結(jié)點(diǎn)(啊)沒有左子樹的充要條件是()c

A.t->left==NULL

B.t->llag==l

C.t->ltag==l&&t->left==NULL

D.以上都不對(duì)

答案B

14.

下列排序算法中，第?趟排序完畢后，其最大或最小元素?定在其最終位置上的算法是()。

A.歸并排序

B.直接插入排序

C.快速排序

D.冒泡排序

答案D

15.

若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為()o(1

與名n+1)

A.0(0)

B.0(l)

C.O(n)

D.0(n2)

答案C

16.

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

A.n(n+1)/2

B.n(n-l)/2

C.n(n-l)

D.n(n+l)

答案B

17.

對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)是為了()

A,便于進(jìn)行矩陣運(yùn)算

B.便于輸入和輸出

C.節(jié)省存儲(chǔ)空間

D.降低運(yùn)算的時(shí)間復(fù)雜度

答案C

18.

任何一個(gè)無向連通圖的最小生成樹()。

A.只有一棵

B.有一棵或多棵

C.一定有多棵

D.可能不存在

答案B

19.

若已知一個(gè)棧的輸入序列為1,2,3,4,.......,n,其輸出序列pl.p2,若pl=n,則pi為

A.i

B.n-i

C.n-i+1

D.不確定

答案C

2(J.

對(duì)有n個(gè)記錄的有序表采用二分查找，其平均查找長(zhǎng)度的量級(jí)為()。

A.O(log2n)

B.O(nlog2n)

C.0(n)

D.0(n2)

答案A

21.

如果待排序序列中兩個(gè)數(shù)據(jù)元素具有相同的值，在排序后它們的位置發(fā)生顛倒，則稱該排序是不穩(wěn)定的。

()就是不穩(wěn)定的排序方法。

A.起泡排序

B.歸并排序

C.直接插入法排序

D.簡(jiǎn)單選擇排序

答案D

22.

按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有()種。

A.3

B.4

C.5

D.6

答案C

23.

設(shè)輸入序列為123,4,5,借助?個(gè)?？梢缘玫降妮敵鲂蛄惺牵ǎ?/p>

A.2,4,1,3,5

B.3,4,152

C.324,1,5

D.4,1,325

答案C

24.

鄰接表的存儲(chǔ)結(jié)構(gòu)下圖的深度優(yōu)先遍歷類似;二叉樹（樹）的（）。

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.按層遍歷

答案A

25.

具有n個(gè)頂點(diǎn)的有向圖最多可包含（）條有向邊。

A.n-1

B.n

C.n（n-l）/2

D.n（n-l）

答案D

（四）

一、單選題

1.

下列排序算法中,某一趟結(jié)束后未必能選出一個(gè)元素放其最終位置上的是（）。

A.堆排序

B.冒泡排序

C.快速排序

D.直接插入排序

答案D

2.

線性表是具有n個(gè)（）的有限序列,

A.表元素

B.字符

C.數(shù)據(jù)元素

D.信息項(xiàng)

答案C

對(duì)有n個(gè)記錄的表按記錄鍵值有序建立二又排序樹，在這種情況下，其平均查找長(zhǎng)度的量級(jí)為（）°

A.0（n）

B.O（nlog2n）

C.0（1）

D.O（log2n）

答案A

任何一棵二叉樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)位置（）。

A.不發(fā)生變化

B.發(fā)生變化

C.不能確定

D.一定發(fā)生改變

答案A

5.

某二叉樹的前序和后序序列正好相同，則該二叉樹一定是（）的二叉樹。

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

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

C.任一結(jié)點(diǎn)無左孩子

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

答案A

某二叉樹的前序和后序序列正好相反，則該二叉樹一定是（）二叉樹。

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

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

C.任意結(jié)點(diǎn)無左孩子

D.任意結(jié)點(diǎn)無右孩子

答案B

7.

數(shù)據(jù)表A中有10000個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用（）排序算法最節(jié)省空間。

A.堆排序

B.希爾排序

C.快速排序

D.直接選擇排序

答案A

8.

線性鏈表中各結(jié)點(diǎn)之間的地址（）。

A.必須連續(xù)

B.一定不連續(xù)

C,部分地址必須連續(xù)

D.連續(xù)與否無所謂

答案D

在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要（）邊。

A.n

B.n+1

C.n-1

D.n/2

答案C

10.

在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（）倍。

A.1/2

B.1

C.2

D.4

答案B

11.

鏈表不具有的特點(diǎn)是（）。

A.可隨機(jī)訪問任一元素

B.插入刪除不需要移動(dòng)元素

C.不必事先估計(jì)存儲(chǔ)空間

D.所需空間與線性表長(zhǎng)度成正比

答案A

12.

二分查找法要求查找表中各元素的鍵值必須是（）排列。

A.遞增或遞減

B.遞增

C.遞減

D.無序

答案A

13.

當(dāng)初始序列已經(jīng)按鍵值有序時(shí)，用直接插入算法進(jìn)行排序，需要比較的次數(shù)為（）。

A.n2

B.niog2n

C.Iog2n

D.n-1

答案D

14.

在線索二叉樹中，結(jié)點(diǎn)（*t）沒有左子樹的充要條件是（）。

A.t->left==NULL

B.t->ltag==l

C.t->ltag==l&&t->left==NULL

D.以上都不對(duì)

答案B

15.

下列排序算法中，第一趟排序完畢后，其最大或最小元素一定在其最終位置上的算法是（）。

A.歸并排序

B.直接插入排序

C.快速排序

D.冒泡排序

答案D

16.

若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（）。

Wi±n+l）

A.0(0)

B.0(1)

C.O(n)

D0(n7)

答案C

17.

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

A.n(n+l)/2

B.n(n-l)/2

C.n(n-1)

D.n(n+|)

答案B

18.

任何一個(gè)無向連通圖的最小生成樹()。

A.只有一棵

B.有一棵或多棵

C.一定有多棵

D.可能不存在

答案B

19.

若已知一個(gè)棧的輸入序列為12,3,4,.......n其輸出序列pl,p2,……pn。若pl=n,則pi為

A.i

B.n-i

C.n-i+1

D.不確定

答案C

20.

若表r在排序前已按元素鍵值遞增順序排列，采用()方法比較次數(shù)較少。

A.直接插入排序

B.快速排序

C.歸并排序

D.選擇排序

答案A

21.

對(duì)有n個(gè)記錄的有序表采用二分查找，其平均查找長(zhǎng)度的量級(jí)為()。

A.O(log2n)

B.O(nlog2n)

CO(n)

D.0(n2)

答案A

22.

如果待排序序列中兩個(gè)數(shù)據(jù)元素具有相同的值，在排序后它們的位置發(fā)生顛倒，則稱該排序是不穩(wěn)定的。

()就是不穩(wěn)定的排序方法。

A.起泡排序

B.歸并排序

C.直接插入法排序

D.簡(jiǎn)單選擇排序

答案D

23.

按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有()種。

A.3

B.4

C.5

D.6

答案C

24.

設(shè)輸入序列為123,4.5,借助一個(gè)?？梢缘玫降妮敵鲂蛄惺?。。

A.241,3,5

B.3,4,152

C.324,1,5

D.4,1,325

答案C

25.

具有n個(gè)頂點(diǎn)的有向圖最多可包含()條有向邊。

A.n-l

B.n

C.n(n-l)/2

D.n(n-l)

答案D

(五)

一、單選題

下列排序算法中,某一趟結(jié)束后未必能選出一個(gè)元素放其最終位置上的是（）。

A.堆排序

B.冒泡排序

C.快速排序

D.直接插入排序

答案D

對(duì)有n個(gè)記錄的表按記錄鍵值有序建立二又排序樹，在這種情況下，其平均查找長(zhǎng)度的量級(jí)為（）°

A.0(n)

B.O(nlog2n)

C.0(1)

D.O(log2n)

答案A

任何一棵二叉樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)位置（）。

A.不發(fā)生變化

B.發(fā)生變化

C.不能確定

D.一定發(fā)生改變

答案A

某二叉樹的前序和后序序列正好相反，則該二叉樹一定是（）二叉樹。

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

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

C.任意結(jié)點(diǎn)無左孩子

D.任意結(jié)點(diǎn)無右孩子

答案B

冒泡排序的時(shí)間復(fù)雜度是()。

A.0(n2)

B.O(nlog2n)

C.0(n)

D.O(log2n)

答案A

使具有9個(gè)頂點(diǎn)的無向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是（）。

A.6

B.8

C.5

D.4

答案B

數(shù)據(jù)表A中有10000個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用（）排序算法最節(jié)省空間。

A.堆排序

B.希爾排序

C.快速排序

D.直接選擇排序

答案A

8.

線性鏈表中各結(jié)點(diǎn)之間的地址（）。

A.必須連續(xù)

B.一定不連續(xù)

C.部分地址必須連續(xù)

D.連續(xù)與否無所謂

答案D

9.

在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要（）邊。

A.n

B.n+1

C.n-l

D.n/2

答案C

10.

鏈表不具有的特點(diǎn)是（）。

A.可隨機(jī)訪問任一元素

B.插入刪除不需要移動(dòng)元素

C.不必事先估計(jì)存儲(chǔ)空間

D.所需空間與線性表長(zhǎng)度成正比

答案A

11.

二分查找法要求查找表中各元素的鍵值必須是（）排列。

A.遞增或遞減

B.遞增

C.遞減

D.無序

答案A

12.

當(dāng)初始序列已經(jīng)按犍值有序時(shí)，用直接插入算法進(jìn)行排序，需要比較的次數(shù)為（）。

A.n2

B.nlog2n

C.Iog2n

D.n-1

答案D

13.

在線索二叉樹中，結(jié)點(diǎn)（*t）沒有左子樹的充要條件是（）。

A.t->left==NULL

B.t->ltag==l

C.t->ltag==l&&t->left==NULL

D.以上都不對(duì)

答案B

14.

下列排序算法中，第一趟排序完畢后，其最大或最小元素一定在其最終位置上的算法是（）。

A.歸并排序

B.直接插入排序

C.快速排序

D.冒泡排序

答案D

15.

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

A.n(n+l)/2

Rn(n-l)/2

C.n(n-l)

D.n(n+l)

答案B

16.

任何一個(gè)無向連通圖的最小生成樹()。

A.只有一棵

B.有一棵或多棵

C.一定有多棵

D.可能不存在

答案B

17.

若已知一個(gè)棧的輸入序列為1,2,3,4,.......,n,其輸出序列pl,p2,??-..,pno若pl=n，則pi為

A.i

B.n-i

C.n-i+1

D.不確定

答案C

18.

鄰接表的存儲(chǔ)結(jié)構(gòu)下圖的廣度優(yōu)先遍歷類似了二叉樹(樹)的()。

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.按層遍歷

答案D

19.

若表r在排序前已按元素鍵值遞增順序排列，采用()方法比較次數(shù)較少。

A.直接插入排序

B.快速排序

C.歸并排序

D.選擇排序

答案A

20.

對(duì)有n個(gè)記錄的有序表采用二分查找，其平均查找長(zhǎng)度的量級(jí)為()。

A.O（lng2n）

B.O（nlog2n）

C.0（n）

D.0（n2）

答案A

21.

如果待排序序列中兩個(gè)數(shù)據(jù)元素具有相同的值，在排序后它們的位置發(fā)生顛倒，則稱該排序是不穩(wěn)定的。

（）就是不穩(wěn)定的排序方法。

A.起泡排序

B.歸并排序

C.直接插入法排序

D.簡(jiǎn)單選擇排序

答案D

22.

按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二又樹有（）種。

A.3

B.4

C.5

D.6

答案C

23.

設(shè)輸入序列為12345,借助一個(gè)棧可以得到的輸出序列是（）。

A.2,4,135

B.3,41,5,2

C.3,2,4,1,5

D.4,1,325

答案C

24.

鄰接表的存儲(chǔ)結(jié)構(gòu)下圖的深度優(yōu)先遍歷類似于二叉樹（樹）的（）。

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.按層遍歷

答案A

25.

具有n個(gè)頂點(diǎn)的有向圖最多可包含（）條有向邊,

A.n-1

B.n

C.n(n-l)/2

D.n(n-l)

答案D

(六)

一、單選題

1.

下列排序算法中,某一趟結(jié)束后未必能選出一個(gè)元素放其最終位置上的是（）。

A.堆排序

B.冒泡排序

C.快速排序

D.直接插入排序

答案D

2.

棧和隊(duì)列都是（）

A.順序存儲(chǔ)的線性表

B.鏈?zhǔn)酱鎯?chǔ)的線性表

C.限制存取點(diǎn)的線性結(jié)構(gòu)

D.限制存取點(diǎn)的非線性結(jié)構(gòu)

答案C

3.

線性表是具有n個(gè)（）的有限序列。

A.表元素

B.字符

C.數(shù)據(jù)元素

D.信息項(xiàng)

答案C

對(duì)有n個(gè)記錄的表按記錄鍵值有序建立二叉排序樹，在這種情況下，其平均查找長(zhǎng)度的量級(jí)為（）。

A.0(n)

B.O(nlog2n)

C.0(1)

DO(log?n)

答案A

串是（）

A.一些符號(hào)構(gòu)成的序列

B.一些字母構(gòu)成的序列

C.一個(gè)以上字