军队文职-计算机-数据结构与算法-强化练习三.pdfVIP

军队文职-计算机-数据结构与算法-强化练习三

[单选题]1.在一棵度为3的树中，度为3的节点个数为2，度为2的节点个数为

1，则度为0的节点个数为()。

A.4

B.5

C.6

D.7

参（江南博哥）考答案：C

参考解析：根据题干中的描述可以画出树，度为0的节点共6个。

[单选题]2.采用开放定址法处理散列表的冲突时，其平均查找长度()。

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

B.高于二分查找

C.低于链接法处理冲突

D.高于链接法处理冲突

正确答案：D

参考解析：开放定址法处理冲突的平均查找长度高于链接法。

[单选题]3.

A.O（m*n*t）

B.O（m+n+t）

C.O（m*t+n）

D.O（m+n*t）

正确答案：A

参考解析：在程序段中，有两段循环程序，第一段是一个双层嵌套循环，另一

个是三层嵌套循环，所以基本操作是c[i][j]=c[i][j]+a[i][k]×b[k][j]，此

基本操作共执行m×t×n次。

[单选题]4.设有向无环图G中的有向边集合E={＜1，2＞，＜2，3＞，＜3，4

＞，＜1，4＞}，则下列属于该有向图G的一种拓扑排序序列的是()。

A.1，2，3，4

B.2，3，4，1

C.1，2，4，3

D.1，4，2，3

正确答案：A

参考解析：

[单选题]5.设顺序表的长度为n，则顺序查找的平均比较次数为()。

A.（n-1）/2n

B.n/2

C.（n+1）/2

D.n

正确答案：C

参考解析：顺序查找是顺序遍历查找表，直至找到或查找失败，所以最好的情

况是第一个节点即想找的元素，最坏的情况是查找失败，所以平均查找次数为

（n+l）/2。

[单选题]6.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X

的最多比较次数不超过()。

A.

B.

C.

D.

正确答案：C

参考解析：

[单选题]7.下述排序方法中，比较次数与待排序记录的初始状态无关的是()。

A.选择排序和归并排序

B.插入排序和归并排序

C.插入排序和快速排序

D.归并排序和快速排序

正确答案：A

参考解析：

[单选题]8.一组数22，31，35，25，45，63，72，93，二路归并排序第一次后

的顺序为()。

A.22，31，25，35，45，63，72，93

B.22，31，35，25，45，63，72，93

C.22，31，35，25，63，45，72，93

D.22，31，35，72，25，45，63，93

正确答案：A

参考解析：归并（Merge）排序法是将两个或两个以上有序表合并成一个新的有

序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有

序子序列合并为整体有序序列。若将两个有序表合并成一个有序表，称为2-路

归并。对初始化序列22，31，35，25，45，63，72，93进行一次排序后得

（22，31），（25，35），（45，63），（72，93），因此本题答案为A。

[单选题]9.线索二叉树中某节点R没有左孩子的充要条件是()。

A.R.ltag=l

B.R.rchild=NULL

C.R.lchild=NULL

D.R.ltag=0

正确答案：D

参考解析：线索二叉树中某节点是否有左孩子，不能通过左指针域是否为空来

判断，而要判断左标志是否为0。

[单选题]10.设一组初始记录关键字序列（5，2，6，3，8），以第一个记录关

键字5为基准进行一趟快速排序的结果为()。

A.3，2，5，8，6

B.2，3，5，8，6

C.3，2，5，6，8

D.2，3，6，5，8

正确答案：C

参考解析：快速排序的每趟排序在待排序列中选取一个数为基准，将序列划分

为两段，一段的值比基准值小，另一段大于或等于基准值。

[单选题]11.设一组初始记录关键字序列为（345，253，674，924，627），则

用基数排序需要进行()趟的分配和回收才能使得初始关键字序列变成有序序

列。

A.3

B.8

C.5

D.6

正确答案：A

参考解析：因为待排序列中最大的数为三位数，所以需要进行3次。

[单选题]12.判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可

以用()。

A.广度优先遍历算法

B.深度优先遍历算法