北理工《数据结构与算法》在线作业-00003参考答案.pdf

北理工《数据结构与算法》在线作业-00003

试卷总分:100得分:100

一、单选题(共40道试题,共100分)

1.若构造一棵具有n个结点的二叉排序树，最坏情况下，其深度不会

超过()。

A.n/2

B.n

C.(n+1)/2

D.n+1

答案:B

2.设有一个矩阵A8×6，以行序为主序存储，a11为第一个元素，其

存储地址为1，每个元素占一个地址空间，则a56地址为()。

A.23

B.30

C.31

D.45

答案:B

3.队列的操作特点是()。

A.先进先出

B.后进先出

C.先进后出

D.只能从队尾出队

答案:A

4.当待排序列基本有序时，下列排序方法中()最好。

A.直接插入排序

B.快速排序

C.堆排序

D.归并排序

答案:A

5.已知广义表LS=(A,(B,C,D),E)运用head和tail函数，取出LS中B

的运算()。

A.Gethead(Gethead(LS))

B.Gettail(Gethead(LS))

C.Gethead(Gethead(Gettail(LS)))

D.Gethead(Gettail(LS))

答案:C

6.以下排序方法中，稳定的排序方法是()。

A.直接插入排序和希尔排序

B.直接插入排序和冒泡排序

C.希尔排序和快速排序

D.冒泡排序和快速排序

答案:B

7.在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成

功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元

素的概率都相等）为().

A.n

B.n/2

C.(n+1)/2

D.(n-1)/2

答案:C

8.n个顶点的连通图至少有()条边。

A.n-1

B.n

C.n+1

D.0

答案:A

9.设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，

rear为队尾指针，则执行出队操作的语句为()

A.front=front+1

B.front=(front+1)%m

C.rear=(rear+1)%m

D.front=(front+1)%(m+1)

答案:D

10.栈与一般的线性表的区别在于()。

A.数据元素的类型不同

B.运算是否受限制

C.数据元素的个数不同

D.逻辑结构不同

答案:B

11.以下不稳定的排序方法是()

A.直接插入排序

B.冒泡排序

C.直接选择排序

D.二路归并排序

答案:C

12.下列不属于栈基本运算的是()。

A.入栈

B.删除栈底元素

C.判断栈是否为空

D.建立一个空栈

答案:B

13.设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点

B的度数数为()

A.3

B.4

C.5

D.1

答案:B

14.以二叉链表作为二叉树的存贮结构时，在具有n个结点的二叉链

表中(n0)，空指针域的个数为()。

A.2n-1

B.n+1

C.n-1

D.2n+1

答案:B

15.一棵高度（假定树根结点为第0层）为4的完全二叉树中的结点

数最少为()。

A.15

B.16

C.17

D.31

答案:B

16.若一个具有n个结点、k条边的非连通无向图是一个森林(nk)，

则该森林中必有()棵树。

A.k

B.n

C.n-k

D.n+k

答案:C

17.顺序表是线性表的()

A.链式存储结构

B.顺序存储结构

C.索引存储结构

D.散列存储结构

答案:B

18.3个结点的无向完全连通图至少有()条边。

A.3

B.4

C.5

D.6

答案:A

19.对于经常要存取线性表任意指定位置元素的应用，线性表应采用()

存储结构。

A.顺序存储结构

B.链式存储结构

C.线性链表

D.栈

答案:A

20.以下关于线性表的说法不正确的是()。

A.线性表中的数据元素可以是数字、字符、记录等不同类型

B.线性表中包含的数据元素个数不是任意的

C.线性表中的每个结点都有且只有一个直接前趋和直接后继

D.存在这样的线性表：表中各结点都没有直接前趋和直接后继

答案:C

21.栈的插入和删除操作在()进行。

A.栈顶

B.栈底

C.任意位置

D.指定位置

答案:A

22.一个栈的入栈序列是abcde，则栈的不可能的输出序列是()。

A.edcba

B.decba

C.dceab

D.abcde

答案:C

23