《数据结构2264》22春在线作业2-00001

试卷总分:100  得分:100

一、单选题 (共 25 道试题,共 50 分)

1.二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（ ）。

A.1207

B.1209

C.1211

D.1213

2.在线性表的下列运算中，不改变数据元素之间的结构关系的运算是（ ）。

A.插入

B.删除

C.排序

D.查找

3.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（ ）。

A.1，2，3

B.9，5，2，3

C.9，5，3

D.9，4，2，3

4.树最适合用来表示（ ）。

A.有序数据元素

B.无序数据元素

C.元素之间具有分支层次关系的数据

D.元素之间无联系的数据

5.有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行（ ）遍分配与收集。

A.n

B.d

C.r

D.n - d

6.若有序表为（ ），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（ ）。

A.f,c,b

B.f,d,b

C.g,c,b

D.g,d,b

7.队列的特点是（ ）。

A.先进后出

B.先进先出

C.任意位置进出

D.前面都不正确

8.下列关于数据结构的叙述中，正确的是（ ）。

A.数组是不同类型值的集合

B.递归算法的程序结构比迭代算法的程序结构更为精炼

C.树是一种线性结构

D.用一维数组存储一棵完全二叉树是有效的存储方法

9.从二叉搜索树中查找一个元素时，其时间复杂度大致为（ ）。

A.O(n)

B.O(1)

C.O(log2n)

D.O(n2)

10.对于线性表（ ）进行散列存储时，若选用H（ ）=K % 9作为散列函数，则散列地址为1的元素有（ ）个。

A.1

B.2

C.3

D.4

11.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（ ）。

A.单链表

B.仅有头指针的单循环链表

C.双链表

D.仅有尾指针的单循环链表

12.k层（ ）二叉树的结点总数最多为（ ）。

A.2k-1

B.2K+1

C.2K-1

D.2k-1

13.对线性表，在下列哪种情况下应当采用链表表示？（ ）

A.经常需要随机地存取元素

B.经常需要进行插入和删除操作

C.表中元素需要占据一片连续的存储空间

D.表中元素的个数不变

14.对一棵有100个结点的完全二叉树按层编号，根结点编号为1，则编号为49的结点的父结点的编号为（ ）。

A.24

B.5

C.98

D.99

15.设Huffman树的叶子结点数为m，则结点总数为（ ）。

A.2m

B.2m-1

C.2m+1

D.m+1

16.数据的基本单位是（ ）。

A.数据项

B.数据类型

C.数据元素

D.数据变量

17.设有6个结点的无向图，该图至少应有（ ）条边才能确保是一个连通图。

A.5

B.6

C.7

D.8

18.中缀表达式2+X*（ ）的后缀形式是（ ）。

A.3 Y X 2 + * +

B.Y 3 + X * 2 +

C.2 X Y 3 * + +

D.2 X Y 3 + * +

19.以下数据结构中哪一个是非线性结构？（ ）

A.队列

B.栈

C.线性表

D.二叉树

20.在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（ ）。

A.i

B.i+1

C.n-i

D.n-i+1

21.对关键字序列（ ）进行增量为3的一趟希尔排序的结果为（ ）。

A.(19, 23, 56, 34, 78, 67, 88, 92)

B.(23, 56, 78, 66, 88, 92, 19, 34)

C.(19, 23, 34, 56, 67, 78, 88, 92)

D.(19, 23, 67, 56, 34, 78, 92, 88)

22.一散列表长度m为100，采用除留余数法构造散列函数，即H（ ）=K%P （ ）,，为使散列函数具有较好的性能，P的选择应是（ ）。

A.99

B.100

C.97

D.93

23.若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G，后序遍历的序列为B、D、C、A、F、G、E。 则该二叉树结点的前序遍历的序列为（ ）。

A.G、F、A、C、D、B

B.A、G、C、F、B、D

C.A、C、B、D、G、F

D.G、A、C、D、F、B

24.带有头结点的单循环链表的头指针为head，则该链表为空的判定条件是（ ）。

A.head= =NUL

B.head->next= =NULL

C.head!=NULL

D.head->next= =head

25.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（ ）语句序列。

A.p=q; p->next=q;

B.p->next=q; q->next=p;

C.p->next=q->next; p=q;

D.q->next=p->next; p->next=q;

二、多选题 (共 4 道试题,共 20 分)

26.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列为（ ）。

A.3，2，6，1，4，5

B.3，4，2，1，6，5

C.1，2，5，3，4，6

D.5，6，4，2，3，1

E.6，5，4，3，2，1

27.下述（ ）是顺序存储方式的优点。

A.存储密度大

B.插入和删除运算方便

C.获取符合某种条件的元素方便

D.查找运算速度快

E.可以很方便地存取第i个元素

28.以下哪些是队列的基本运算？（ ）

A.在队列第i个元素之后插入一个元素

B.从队头删除一个元素

C.判断一个队列是否为空

D.读取队头元素的值

E.将队列中的元素排序

29.对一个算法的评价，主要包括如下（ ）方面的内容。

A.健壮性和可读性

B.并行性

C.正确性

D.时空复杂度

E.界面友好性

三、判断题 (共 15 道试题,共 30 分)

30.快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。

31.用字符数组存储长度为n的字符串，数组长度至少为n+1。

32.邻接矩阵适用于稠密图（ ），邻接表适用于稀疏图（ ）。

33.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。

34.为度量一个搜索算法的效率，需要在时间和空间两个方面进行分析。

35.线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。

36.一个广义表（ ）,（ ）,c),（ ）))) 的表尾是（ ）,c),（ ）))。

37.链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。

38.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。

39.线性表的长度是线性表所占用的存储空间的大小。

40.二维数组是数组元素为一维数组的线性表，因此二维数组元素之间是线性结构。

41.存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（ ）三角部分。

42.在采用线性探测法处理冲突的哈希表中，所有同义词在表中相邻。

43.在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。

44.栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。