/ 知识库     / 试卷库

等级2017年秋程序员软考( )

对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是:在插入第i个关键码ki时,其前面的 i-1 个关键码已排好序,因此令k与 ki-1、ki-2、…,依次比较,最多到 k1为止,找到插入位置并移动相关元素后将ki插入有序子序列的适当位置,完成本趟(即第 i-1 趟)排序。以下关于直接插入排序的叙述中,正确的是【 】 。

A、若原关键码序列已经升序排序,则排序过程中关键码间的比较次数最少

B、若原关键码序列已经降序排序,则排序过程中关键码间的比较次数最少

C、第1趟完成后即可确定整个序列的最小关键码

D、第1趟完成后即可确定整个序列的最大关键码

若原关键码序列已经升序排序,则排序过程中关键码间的比较次数最少

以4个元素(10,20,30,40)为例说明直接插入排序的特点。

若元素已经按照升序排列,即k1=10,k2=20,k3=30,k4=40,那么各趟排列结果如下:第一趟将20插入仅含元素10的子序列,20与10比较1次,得到10 20;

第二趟将30插入含有元素10、20的子序列,30与20比较1次,得到10 20 30;

第三趟将40插入10、20、30构成的子序列,40与30比较1次,得到10 20 30 40;

在上述过程中,由于待插入的元素比有序子序列的最大元素都要大,所以总共进行3次比较,也不需要移动元素。推广到有n个元素的序列,则是进行n-1次比较。

若元素已经按照降序排列,即k1=40,k2=30,k3=20,k4=10,那么各趟排列结果如下:

第一趟将30插入仅含元素40的子序列,30与40比较1次,将40后移,再将30插入40之前,得到30 40;

第二趟将20插入30、40构成的子序列,20与40比较1次,将40后移,再与30比较1次,将30后移,再将20插入30之前,得到20 30 40;

第三趟将10插入20、30、40构成的子序列,10与40比较1次,将40后移,再与30比较1次,将30后移,再与20比较1次,将20后移,再将10插入20之前,得到10 20 30 40;

在上述过程中,由于待插入的元素比有序子序列的所有元素都要小,所以总共进行1+2+3次比较,每次插入时有序子序列的所有元素都要移动。推广到有n个元素的序列,则总共进行1+2+…+(n-2)+(n-1)次比较。

等级2017年秋程序员软考( )

对于下面的有向图,采用邻接链表存储时,顶点 0的表结点个数为2,顶点3的表结点个数为0,顶点1的表结点个数为【 】。

A、0

B、1

C、2

D、3

2

等级2017年秋程序员软考( )

对于下面的有向图,其邻接矩阵是一个【 】的矩阵。

A、3×4

B、4×3

C、6×6

D、7×7

7×7

等级2017年秋程序员软考( )

对下图所示的二叉树进行中序遍历(左子树、根结点、右子树)的结果是【 】。

A、5 2 3 4 6 1

B、2 5 3 4 1 6

C、2 4 6 5 3 1

D、2 5 4 3 6 1

2 5 4 3 6 1

等级2017年秋程序员软考( )

对关键码序列(12,24,15,56,20,87,69,9)采用散列法进行存储和查找,并设散列函数为H(Key)=Key%11(%表示整除取余运算)。采用线性控查法(顺地探查可用存储单元)解决冲突所构造的散列表为【 】。

A、

B、

C、

D、

按顺序计算各关键码的哈希(散列)地址如下:

H(12)=12%11=1,H(24)=24%11=2,H(15)=15%11=4,H(56)=56%11=1,H(20)=20%11=9,H(87)=87%11=10,H(69)=69%11=3,H(9)=9%11=9

初始时哈希表为空,关键码12、24和15存入时没有发生冲突,因此这些关键码的存储位置即为由哈希函数计算所得,如下表所示。

存入关键码56时,计算得到其哈希地址为1,发生冲突,用线性探查法探查哈希地址为2的单元,仍然冲突,再探查哈希地址为3的单元,不再冲突,因此在3号单元存入 56,如下表所示。

接下来存入关键码20和87时,其对应的哈希单元都不冲突,因此依次在9号单元和10号单元存入20、87,如下表所示。

存入关键码69时,计算得到其哈希地址为3,发生冲突,用线性探查法探查哈希地址为4的单元,仍然冲突,再探查哈希地址为5的单元,不再冲突,因此在5号单元存入69,如下表所示。

存入关键码9时,计算得到其哈希地址为9,发生冲突,用线性探查法探查哈希地址为10的单元,仍然冲突,再探查哈希地址为0的单元,不再冲突,因此在0号单元存入9,如下表所示。