考研数据结构及程序设计在线题库每日一练（九）

本文提供考研数据结构及程序设计在线题库每日一练，以下为具体内容

1、在下列排序方法中，（  ）方法可能出现这种情况: 在最后一趟开始之前， 所有的元素都不在其最终应在的正确位置上。

A、快速排序

B、冒泡排序

C、堆排序

D、插入排序

2、以下对二维数组a进行初始化正确的是（ ）。

A、int a[1][2]={{1,2},{3,4},{5,6}};

B、int a[][3]={1,2,3,4,5,6};

C、int a[2][]={1,2,3,4,5,6};

D、int a[2][]={{1,2},{3,4}};

3、n个结点的线索二叉树上含有的线索数为（ ）。

A、2n

B、n-1

C、n+1

D、n

4、某二叉树的前序序列和中序序列正好相反，则该二叉树一定具有（ ）的特征。

A、二叉树为空或只有一个结点

B、若二叉树不为空，则任一结点不能同时拥有左孩子和右孩子

C、若二叉树不为空，则任一结点没有左孩子

D、者二叉树不为空，则任一结点没有右孩子

5、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E={<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>，<V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>}，G的拓扑序列是（ ）。

A、V1，V3，V4，V6，V2，V5，V7

B、V1，V3，V2，V6，V4，V5，V7

C、V1，V3，V4，V5，V2，V6，V7

D、V1，V2，V5，V3，V4，V6，V7

1、试题答案：D

试题解析：

【考点】本题考查几种常见的排序算法。
【解析】
（1）快速排序：每一趟排序都可以确定枢轴元素的最终位置。
（2）冒泡排序：每一趟排序都可以确定一个最大或最小元素的最终位置。
（3）堆排序：每一趟都选取堆顶元素（最大或最小元素）加入有序序列，即可确定最大或最小元素的最终位置。
（4）插入排序：最后一趟插入的可能是最小元素，导致所有元素都不在其最终位置上。
综上所述，本题选D。

2、试题答案：B

试题解析：

【考点】本题考查二维数组的初始化。
【解析】二维数组必须指定列的数量，行的数量可以不指定，所以选项C和D初始化错误。
选项A：在{ }内部再用{ }把各行分开，第一对{ }中的初值1，2是0行的2个元素的初值。第二对{ }中的初值3，4是1行的2个元素的初值。第三对{ }再赋值就超过数组元素的个数了，所以选项A不正确。
选项B： a数组的第一维的定义被省略，初始化数据共6个，第二维的长度为3，即每行3个数，所以a数组的第一维是2。初始化各元素值为a[0][0]=1，a[0][1]=2，a[0][2]=3，a[1][0]=4，a[1][1]=5，a[1][2]=6。因此，选项B中的初始化正确。故本题选B。

3、试题答案：C

试题解析：

【考点】本题考查数据结构--树与二叉树--二叉树--线索二叉树--线索二叉树的性质。
【解析】n个结点共有链域指针2n个，其中，除根结点外，每个结点都被一个指针指向。剩余的链域建立线索，共2n-(n-1)=n+1个线索。故本题选C。

4、试题答案：D

试题解析：

【考点】本题考查二叉树。
【解析】前序遍历的过程是根左右，中序遍历的过程是左根右。若某二叉树不为空，且其中所以结点均没有右孩子，那么前序遍历的过程是根左，中序遍历的过程是左根，此时，得到的前序序列和中序序列正好相反。综上所述，本题选D。

5、试题答案：A

试题解析：

【考点】本题考查拓扑排序。
【解析】生成拓扑序列的过程如下所示，由此可知本题选A。