数据结构与算法-等级考试试题(程序员软考 2014年春特殊矩阵)

单项选择（2014年春程序员软考）

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

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

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

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

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

答案解析

C

【解析】

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

讨论

数据结构与算法

设有字符串S和P，串的模式匹配是指确定【】。

以下关于栈和队列的叙述中，错误的是【】。

线性表采用单链表存储时的特点是【】。

正规式(ab|c)(0|1|2)表示的正规集合中有【】个元素。

若需在O(log2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是【】。

堆排序是不是一种稳定的排序方法？为什么？

若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，应该选【】。

如果待排序序列中两个数据元素具有相同的值，在排序前后它们的位置发生颠倒，则称该排序算法是不稳定的，【】就是不稳定的排序算法。

若有n个元素已构成一个小根堆，那么如果增加一个元素Kn+1，请用文字简要说明如何在log2n的时间内将其重新调整为一个堆。

如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序序列，用【】方法最快

数组和广义表

若采用三元组表存储结构存储系数矩阵 M.则除三元组外，下列数据中还需要保存的是【】Ⅰ. M 的行数；Ⅱ. M 中包含非零元素的行数；Ⅲ. M 的列数；Ⅳ. M 中包含非零元素的列数.

设数组A[1..m,1..n]的每个元素占用1个存储单元，对于数组元素A[i,j](1≤证≤m，1≤j≤n)，在按行存储方式下，其相对于数组空间首地址的偏移量为【】

设数组A[1..m,1..n]的每个元素占用1个存储单元，对于数组元素A[i,j](1≤证≤m，1≤j≤n)，在按列存储方式下，其相对于数组空间首地址的偏移量为【】。

在C程序中有一个二维数组 A[7][8]，每个数组元素用相邻的 8 个字节存储，那么存储该数组需要的字节数为【】。

数组是程序语言提供的基本数据结构，对数组通常进行的两种基本操作是数组元素的【】。

对于连通无向图 G，以下叙述中，错误的是【】。

下图所示的非确定有限自动机(s0为初态，s3为终态)可识别字符串【】。

递归函数执行时，需要【】来提供支持。

对于初始为空的栈S，入栈序列为a、b、c、d，且每个元素进栈、出栈各1次。若出栈序列的第一个元素为d，则合法的出栈序列为【】。

对关键码序列(9，12，15，20，24，29，56，69，87)进行二分查找(折半查找)，若要查找关键码15，则需依次与【】进行比较。

特殊矩阵

对关键码序列(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个元素【】