泽熙美文[单选题]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.深度优先遍历算法
C.求关键路径的方法
D.求最短路径的方法
正确答案：B
参考解析：当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺序（退出DFSTraverse算法）即为逆向的拓扑序列。
[单选题]13.已知数据元素为（34，76，45，18，26，54，92，65），按照依次插入节点的方法生成一棵二叉排序树，则该树的深度为()。
A.6
B.7
C.4
D.5
正确答案：D
参考解析：根据二叉排序树插入节点算法，将上述8个数据元素按照依次插入节点的方法构造出一棵二叉排序树后，该树的最大层次为5，故该树的深度为5。
[单选题]14.以下数据结构中哪一个是非线性结构？()
A.线性表
B.栈
C.队列
D.二叉树
正确答案：D
参考解析：线性表、栈、队列都是线性结构，树、图是非线性结构。
[单选题]15.设某棵二叉树中有2000个节点，则该二叉树的最小高度为()。
A.12
B.10
C.11
D.9
正确答案：C
参考解析：想使二叉树的高度最小，即为完全二叉树的时候，所以高度最小为11。
[单选题]16.设有广义表D（a，b，D），其长度为3，深度为()
A.∞
B.3
C.2
D.5
正确答案：A
参考解析：长度为3，但是因第三个元素是一个广义表，所以深度为无穷。
[单选题]17.一趟排序结束后不一定能够选出一个元素放在其最终位置上的是
