数据结构与算法-等级考试试题(程序员软考 2015年秋数组的定义与实现)

单项选择（2015年秋程序员软考）

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

A、j*(n-1)+i

B、(j-1)*n+i-1

C、j*(m-1)+i

D、(j-1)*m+i-1

答案解析

D

【解析】

在按列存储方式下，元素a[i,j]之前有j-1列，每列m个元素，在a[i,j]所在列(即第j列)，排在它之前的元素有i-1个，因此，a[i,j]之前共有(j-1)*m+i-1个元素。

讨论

数据结构与算法

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

算术表达式a+b-c*d的后缀式是【】(-、+、*表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)。

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

根据枢轴元素(或基准元素)划分序列而进行排序的是【】。

设有关键码序列(10，40，30，20)，根据该序列构建的二叉排序树是【】。

某图G的邻接表如下所示。以下关于图G的叙述中，正确的是【】。

在一个线性表上可以进行二分查找(折半查找)的充分必要条件是【】。

若元素a、b、c、d、e、f依次进栈，允许进栈、出栈操作交替进行。但不允许连续三次进行出栈工作，则不可能得到的出栈序列是【】。

对于顺序栈和链栈，【】不是两者共有的运算特征。

含有n个元素的线性表采用顺序存储，等概率删除其中任一个元素，平均需要移动【】个元素。

数组和广义表

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

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

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

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

含有n个元素的线性表用顺序存储方式时，对其运算速度最快的操作是【】。

在数据结构中，【】是与存储结构无关的术语。

已知某二叉树的先序遍历序列为ABCD，后序遍历序列为CDBA，则该二叉树为【】。

在有13个元素构成的有序表data[1..13]中，用折半查找(即二分查找，计算时向下取整)方式查找值等于data[8]的元素时，先后与【】等元素进行了比较。

对于下图，从顶点1进行深度优先遍历时，不可能得到的遍历序列是【】

函数 Reverselist(LinkList headptr)的功能是将含有头结点的单链表就地逆置。处理思路是将链表中的指针逆转，即将原链表看成由两部分组成，已经完成逆置的部分和未完成逆置的部分，令s指向未逆置部分的第一个结点，并将该结点插入已完成部分的表头(头结点之后)，直到全部结点的指针域都修改完成为止。例如，某单链表如图所示，逆置过程中指针s的变化情况如图(a)(b)所示。链表结点类型定义如下：typedef struct Node{ int data， struct Node *next;}Node， *LinkList;void ReverseList (LinkList headptr){//含头结点的单链表就地逆置， headptr为头指针 LinkList p，s; if(__(1)__) return;//空链表(仅有头结点)时无需处理 p=__(2)__;//令p指向第一个元素结点 if (!p->next) return;//链表中仅有一个元素结点时无需处理 s= p->next;//s指向第二个元素结点 __(3)__=NULL;//设置第一个元素结点的指针域为空 while (s){ p=s;//令p指向未处理链表的第一个结点 s=__(4)__; p-> next= headptr-> next;//将p所指结点插入已完成部分的表头 headptr-> next=__(5)__; }}

数组的定义与实现

算术表达式a*(b-c)+d的后缀式是【】(-、+、*表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)。

对于一个初始为空的栈，其入栈序列为abc时，其出栈序列可以有【】种。

在数据结构中，【】是与存储结构无关的术语。

算术表达式a+(b-c)*d的后缀式是【】(-、+、*表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)。

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

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

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

完全二叉树的特点是叶子结点分布在最后两层，且除最后一层之外，其他层的结点数都达到最大值，那么25个结点的完全二叉树的高度(即层数)为【】。

某二叉排序树如下所示，新的元素45应作为【】插入该二叉树中。

已知某带权图G的邻接表如下所示，其中表结点的结构为:以下关于该图的叙述中，正确的是【】。