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

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

A、线性表采用顺序存储且元素有序排列

B、线性表采用顺序存储且元素无序排列

C、线性表采用单链表存储且元素有序排列

D、线性表采用单链表存储且元素无序排列

答案解析

A

【解析】

二分查找(折半査找)过程令处于中间位置记录的关键字与给定值比较,若相等,则查找成功:若不等,则缩小范围,直至新的查找区间中间位置记录的关键字等于给定值或者查找区间没有元素时(表明查找不成功)为止。

显然,在折半查找过程中需要对元素进行随机访问,且需要元素有序排列。

讨论

负载因子(装填因子)是散列表的一个重要参数,它反映散列表的装满程度。

假定有K个关键字互为同义词,若用线性探测法把这K个关键字存入散列表中,至少要进行【 】次探测。

若杂凑表(Hash)的地址范围为[0,9],杂凑函数为H(key)=(key2+2) MOD 9,并采用链地址法处理冲突,请画出元素7、4、5、3、6、2、8、9依次插入杂凑表的状态。

设有12个数据{25,40,33,47,12,66,72,87,94,22,5,58},它们存储在散列表中,利用双散列解决冲突,要求插入新数据的平均查找次数不超过3次。① 该散列表的大小m应该设计多大?② 试为该散列表设计相应的散列函数(用除留余数法)并计算寻找下一个“空位”时向前跨步步长的再散列函数。③ 顺次将各个数据散列到表中。④ 计算查找成功的平均查找次数。

设a、b、c、d和e这5个字符的编码分别为1、2、3、4和5,并设标识符依以下次序出现ac、bd、aa、be、ab、ad、cd、bc、ae和cd。要求用哈希(Hash)方式将它们存放在具有10个位置的表中。① 对上述关键字(标识符)构造一个哈希函数,使得发生冲突尽可能地少。② 用线性探测再散列法解决冲突。写出上述各关键字在表中的位置。

若散列表的负载因子α<1,则可避免碰撞的产生。

下列哪两个数据结构,同时具有较高的查找和删除性能【 】

最优二叉树(哈夫曼树)、最优查找树均为平均查找路径长度wihi最小的树,其中对最优二叉树,n表示__________,对最优查找树,n表示__________,构造这两种树均__________。(1)结点数(2)叶结点数(3)非叶结点数(4)度为2的结点数(5)需要一张n个关键字的有序表(6)需要对n个关键字进行动态插入(7)需要n个关键字的查找概率表(8)不需要任何前提

用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。

若在线性表中采用折半查找元素,该线性表应该【 】。

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

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

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

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

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

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

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

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

对于下图,从顶点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)__; }}