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

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

A、单链表

B、二叉树

C、哈希表

D、循环队列

答案解析

B

【解析】

单链表是与存储结构有关的术语,常用于线性表的链式存储,通过在结点中设置指针域指出当前元素的直接后继(或直接前驱)元素所在结点,从而表示出元素间的顺序关系(即逻辑关系)。

哈希表既是一种存储结构也是一种查找结构,它以记录的关键字为自变量计算一个函数(称为哈希函数)得到该记录的存储地址,从而实现快速存储和查找。

循环队列是指采用顺序存储结构实现的队列。在顺序队列中,为了降低运算的复杂度,元素入队时,只修改队尾指针;元素出队时,只修改队头指针。由于顺序队列的存储空间是提前设定的,因此队尾指针会有一个上限值,当队尾指针达到其上限时,就不能只通过修改队尾指针来实现新元素的入队操作了。此时,可将顺序队列假想成一个环状结构,称之为循环队列,并仍然保持队列操作的简便性。

讨论

设有字符串S= "software",其长度为3的子串数目为【 】。

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

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

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

函数 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)__; }}

对于下图,若采用邻接矩阵存储,则矩阵中的非0元素数目为【 】。

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

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

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

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