数据结构(第二版) 模拟试题自测卷AB卷带答案3 .pdfVIP

试卷B

一、选择题（本题共20分,每题2分）

1．在数据结构中，从逻辑上可以把数据结构分成（）。

A．动态结构和静态结构B.线性结构和非线性结构

C.紧凑结构和非紧凑结构D.内部结构和外部结构

2.下列程序段的时间复杂度是（）

count=0;

for(k=1;k=n;k*=2)

for(j=1;j=n;j++)

count++;

A.O(nlog2n)B.O(n)C.O(log2n)D.O(n2)

3.以下描述错误的是：（）

A.线性表是n个数据元素的有限非空集合。

B.栈和队列都是操作受限的线性表。

C.串（或字符串）是由零个或多个字符组成的有限序列。

D.非空栈中的栈顶指针top始终指向栈顶元素的下一个位置。

4.若采用少用一个队列空间的方法来区分队满队空两种状态，则判定一个顺序循环队列Q

（最大队列长度MAXSIZE）为满队列的条件是()。

A.Q.front=Q.rearB.Q.front!=Q.rear

C.Q.front=(Q.rear+1)%MAXSIZED.Q.front!=(Q.rear+1)%MAXSIZE

5.按照二叉树的定义，具有3个结点的二叉树有（）种。

A.3B.4C.5D.6

6.设矩阵A（如下图所示）是一个对称矩阵，为了节省存储，将其下三角（包括对角线）

部分按行序存放在一维数组B[n(n+1)/2]中，对下三角部分中任一元素ai,j(i≥j)，在一维数

组B的下标位置k的值是（）。

A.i(i-1)/2+j-1B.i(i-1)/2+j

C.i(i+1)/2+j-1D.i(i+1)/2+j

a



0,0



aa

A1,01,1

............



aa...a

n1,0n1,1n1,n1

7.有一个有序表为｛5,18，23,33,42,54,56,78｝，当折半查找56时，经过（）次比较后

查找成功。

A.1B.2C.3D.8

8.一组记录的排序关键字为（39，19，36，68，35，84），则利用快速排序方法进行正序排

列时，以第一个记录为基准得到的一次划分结果为（）。

A.35，36，19，39，68，84B.19，35，36，39，68，84

C.35，19，36，39，84，68D.35，19，36，39，68，84

9.若对下图a中的二叉树进行先序线索化，则结点x的左、右线索指向的结点分别是（）

A.e,cB.e,aC.d,cD.b,a

a

bc

d

x

e

(a)(b)

10.已知一有向图的邻接表存储结构如上图b所示，根据有向图的广度优先遍历算法，从顶

点v1出发，所得到的顶点序列是（）。

A.v1，v2，v