单项选择(2014年春程序员软考)

特殊矩阵是非零元素有规律分布的矩阵,以下关于特殊矩阵的叙述中,正确的是【 】。

A、特殊矩阵适合采用双向链表进行压缩存储

B、特殊矩阵适合采用单向循环链表进行压缩存储

C、特殊矩阵的所有非零元素可以压缩存储在一维数组中

D、特殊矩阵的所有零元素可以压缩存储在一维数组中

答案解析

C

【解析】

对于矩阵,压缩存储的含义是为多个值相同的元素只分配一个存储单元,对零元素不分配存储单元。如果矩阵的零元素有规律地分布,则可将其非零元素压缩存储在一维数组中,并建立起每个非零元素在矩阵中的位置与其在一维数组中的位置之间的对应关系。

讨论

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

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

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

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

序列【 】可能是第一趟冒泡排序后的结果。

对二叉树中的结点如下编号:树根结点编号为1,根的左孩子结点编号为2、右孩子结点编号为3,以此类推,对于编号为i的结点,其左孩子编号为2i、右孩子编号为2i+1。例如,下图所示二又树中有6个结点,结点a、b、c、d、e、f的编号分别为1、2、3、5、7、11。那么,当结点数为n(n>0)的【 】时,其最后一个结点编号为2n-1。

某二又树的先序遍历序列为 ABCDFGE,中序遍历序列为 BAFDGCE。以下关于该二又树的叙述中,正确的是【 】。

对于关键码序列(54,34,5,14,50,36,47,83),用链地址法(或拉链法)解决冲突构造散列表(即将冲突的元素存储在同一个单链表中,单链表的头指针存入散列地址对应的单元),设散列函数为H(Key)= Key MOD7(MOD表示整除取余运算),则构造散列冲突次数最多的哈希单元的地址是【 】。

对于n个元素的关键码序列{k1,k2,…,kn},当且仅当满足下列关系时称其为堆。或以下关键码序列中,【 】不是堆。

对于一个初始为空的栈,其入栈序列为 1,2,3,...,n(n>3),若出栈序列的第一个元素是1则出栈序列的第n个元素【 】