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

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

A、abc-*d+

B、abcd*-+

C、abcd-*+

D、ab-c*d+

答案解析

A

【解析】

后缀形式表达式中不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行。

按照表达式“a*(b-c)+d”的求值方式,其后缀表示为“abc-*d+”。

讨论

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

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

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

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

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

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

线性表采用单循环链表存储的主要特点是【 】

在单 CPU 计算机系统中,完成相同功能的递归程序比非递归程序【 】

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

对n个记录进行非递减排序,在第一趟排序之后,一定能把关键码序列中的最大或最小元素放在其最终排序位置上的排序算法是【 】。