[奥鹏]川大《数据结构2264》22春在线作业1[答案]

川大《数据结构2264》22春在线作业1[答案]

正确答案:A

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

正确答案:C

试卷总分:100  得分:100

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

1.设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（ ）。

A.m-n-1

B.n+1

C.m-n+1

D.m-n

正确答案:A

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

A.99

B.100

C.97

D.93

正确答案:C

3.对n个记录进行堆排序，所需要的辅助存储空间为（ ）。

A.O（1og2n

B.O（n）

C.O（1）

D.O（n2）

正确答案:C

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

A.2m

B.2m-1

C.2m+1

D.m+1

正确答案:C

5.已知一个图的顶点集V={1,2,3,4,5,6,7}；边集E={（ ）3, （ ）5, （ ）8, （ ）10, （ ）6, （ ）15, （ ）12, （ ）9, （ ）4, （ ）20, （ ）21, （ ）25}，用克鲁斯卡尔算法得到最小生成树，则在最小生成树中依次得到的各条边为（ ）。

A.(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20

B.(1,2)3, (4,6)4, (1,3)5, (2,3)6, (1,4)8, (3,6)9

C.(1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20

D.(1,2)3, (1,3)5, (1,4)8, (2,5)10, (4,6)4, (4,7)20

正确答案:D

6.在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（ ）

A.都不相同

B.完全相同

C.先序和中序相同，而与后序不同

D.中序和后序相同，而与先序不同

正确答案:C

7.对关键字序列（ ）进行增量为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)

正确答案:A

8.采用开放定址法处理散列表的冲突时，其平均查找长度（ ）。

A.低于链接法处理冲突

B.高于链接法处理冲突

C.与链接法处理冲突相同

D.高于二分查找

正确答案:A

9.AOV网是一种（ ）。

A.有向图

B.无向图

C.无向无环图

D.有向无环图

正确答案:B

10.如表r有100000个元素，前99999个元素递增有序，则采用（ ）方法比较次数较少。

A.直接插入排序

B.快速排序

C.归并排序

D.选择排序

正确答案:A

11.对于关键字序列（ ）进行散列存储时，若选用H（ ）=K%7作为散列函数，则散列地址为0的元素有（ ）个。

A.1

B.2

C.3

D.4

正确答案:A

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

A.3 Y X 2 + * +

B.Y 3 + X * 2 +

C.2 X Y 3 * + +

D.2 X Y 3 + * +

正确答案:B

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

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

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

C.树是一种线性结构

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

正确答案:C

14.从一个长度为n的顺序表中删除第i个元素（ ）时，需向前移动的元素个数是（ ）。

A.n-i

B.n-i+1

C.n-i-1

D.i

正确答案:B

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

A.24

B.5

C.98

D.99

正确答案:D

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

正确答案:C

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

正确答案:D

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

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

正确答案:C

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

正确答案:A

17.对广义表L=（ ）,（ ）,（ ）执行操作tail（ ）的结果是（ ）。

A.(e,f)

B.((e,f))

C.(f)

D.( )

正确答案:D

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

A.2k-1

B.2K+1

C.2K-1

D.2k-1

正确答案:A

19.对线性表进行二分法查找，其前提条件是（ ）。

A.线性表以链接方式存储，并且按关键码值排好序

B.线性表以顺序方式存储，并且按关键码值的检索频率排好序

C.线性表以顺序方式存储，并且按关键码值排好序

D.线性表以链接方式存储，并且按关键码值的检索频率排好序

正确答案:A

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

正确答案:A

A.head= =NUL

正确答案:C

B.head->next= =NULL

正确答案:D

C.head!=NULL

正确答案:A

D.head->next= =head

正确答案:B

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

A.1，2，3

B.9，5，2，3

C.9，5，3

D.9，4，2，3

正确答案:C