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

为支持函数调用及返回,常采用称为“【 】”的数据结构。

A、队列

B、栈

C、多维数组

D、顺序表

答案解析

B

【解析】

程序运行过程中若函数 A 调用函数 B,函数 B 又调用了函数 C,那么正常情况下,函数 C运行结束后需要返回到函数 B,函数 B 运行结束后再返回函数 A 继续执行。实现该控制处理的数据结构必须为栈。

讨论

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

某二叉树的先序遍历(根、左、右)序列为 EFHIGJK、中序遍历(左、根、右)序列为HFIEJKG,则该二叉树根结点的左孩子结点和右孩子结点分别是【 】

采用【 】算法对序列{18,12,10,11,23,2,7}进行一趟递增排序后,其元素的排列变为{12,10,11,18,2,7,23}。

表达式可采用后缀形式表示。例如,“a+b”的后缀式为“ab+”。那么,表达式“a*(b-c)+d”的后缀表示为【 】

设某无向图的顶点个数为n,则该图最多有______条边;若将该图用邻接矩阵存储,则矩阵的行数和列数分别为______。

搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询串的长度不超过255 字节。假设目前有一千万个查询记录(重复度比较高,其实互异的查询串不超过三百万个;显然,一个查询串的重复度越高,说明查询它的用户越多,也就是越热门)。现要统计最热门的 10 个查询串,且要求使用的内存不能超过 1GB。以下各方法中,可行且效率最高的方法是【 】。

对于一般的树结构,可以采用孩子-兄弟表示法,即每个结点设置两个指针域,一个指针(左指针)指示当前结点的第一个孩子结点,另一个指针(右指针)指示当前结点的下一个兄弟结点。某树的孩子-兄弟表示如下图所示。以下关于结点 D 与 E 的关系的叙述中,正确的是【 】。

若要求对大小为n的数组进行排序的时间复杂度为 O(nlog2n),且是稳定的(即如果待排序的序列中两个数据元素具有相同的值,在排序前后它们的相对位置不变),则可选择的排序方法是【 】

设元素a、b、c、d依次进入一个初始为空的栈,则不可能通过合法的栈操作序列得到【 】。

若某线性表长度为n且采用顺序存储方式,则运算速度最快的操作是【 】。