数据结构与算法-等级考试试题(程序员软考 2015年春二叉排序树)

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

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

A、

B、

C、

D、

答案解析

C二又排序树又称为二叉查找树，它或者是一棵空树，或者是具有如下性质的二又树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值;若它的右子树非空，则右子树上所有结点的值均大于根结点的值;左、右子树本身就是二叉排序树。二叉查找树是通过依次输入数据元素并把它们插入到二又树的适当位置上构造起来的，具体的过程是:每读入一个元素，建立一个新结点，若二又查找树非空，则将新...

查看完整答案

讨论

查找

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

在n个记录的有序顺序表中进行折半查找，最大的比较次数是__________。

在分块检索中，对256个元素的线性表分成__________块最好，每块的最佳长度是__________；若每块的长度为8，其平均检索长度为__________。

有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。

用二分法查找一个线性表时，该线性表必须具有的特点是____________。

分块查找要求将待查找的表均匀地分成若干块，块中诸记录的顺序可以是任意的，但块与块之间____________。

在分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成__________块最好；若分成25块，其平均查找长度为__________。

利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素35要进行【】次元素间的比较。

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

在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与【】量级相当。

动态查找表

在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉排序树相同。

已知序列17，31，13，11，20，35，25，8，4，11，24，40，27，请画出该序列的二叉排序树，并分别给出下列操作后的二叉排序树：① 插入数据9；② 删除结点17；③ 再删除结点13。

一棵满二叉排序树深度为k，节点数为2k-1；节点值为1至（2k - 1），给出k和任意三个节点的值，输出包含该三个节点的最小子树的根节点。样例输入：4 10 15 13样例输出：12

最佳二叉树是AVL树（平衡二叉树）。

在分析二叉查找树性能时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点i所在层次为li，那么查找失败到达失败结点时所做的数据比较次数是多少？

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

下列关于非空 B 树的叙述中，正确的是【】Ⅰ. 插入操作可能增加树的高度Ⅱ. 删除操作一定会导致叶结点的变化Ⅲ. 查找某关键字一定是要查找到叶结点Ⅳ. 插入的新关键字最终位于叶结点中

设有二叉排序树如下图所示，根据关键码序列【】可构造出该二叉排序树。

【】不符合二叉排序树的定义。

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

二叉排序树

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

阅读以下说明和C函数，填补函数代码中的空缺(1)~(5)。队列是一种常用的数据结构，其特点是先入先出，即元素的插入在表头、删除在表尾进行。下面采用顺序存储方式实现队列，即利用一组地址连续的存储单元存放队列元素，同时通过模运算将存储空间看作一个环状结构(称为循环队列)。设循环队列的存储空间容量为 MAXQSIZE，并在其类型定义中设置base、rear和 length三个域变量，其中，base为队列空间的首地址，rear为队尾元素的指针， length表示队列的长度。#define MAXQSIZE 100typedef struct{ QElemType *base;/*循环队列的存储空间首地址* int real;/*队尾元素索引*/ int ength;/*队列的长度*/} SqQueue;例如，容量为8的循环队列如下图所示，初始时创建的空队列如图(a)所示，经过一系列的入队、出队操作后，队列的状态如图(b)所示(队列长度为3)。下面的C函数1、C函数2和C函数3用于实现队列的创建、插入和删除操作，请完善这些代码。【C函数1】创建一个空的循环队列int InitQueue (SqQueue *Q){ /*创建容量为 MAXQSIZE的空队列，若成功则返回1;否则返回0*/ Q->base =(QElemType *)malloc( MAXQSIZE*__ (1)__); if (! Q->base) return 0： Q->length=0; Q->rear =0; return 1;}/* InitQueue*/【C函数2】元素插入循环队列。int EnQueue( SqQueue *Q， QElemType e){/*元素e入队，若成功则返回1;否则返回0*/ if( Q->length>=MAXQSIZE) return 0; Q->rear=__(2)__; Q->base [Q->rear]=e; __(3)__; return 1;}/*EnQueue*/【C函数3】元素出循环队列。int DeQueue (SqQueue *Q，QElemType *e){ /*若队列不空，则删除队头元素，由参数e带回其值并返回1;否则返回0*/ if(__(4)__)return 0; *e=Q-base[(Q->rear-Q->length+1+MAXQSIZE)%MAXQSIZE]; __(5)__; return 1;}/*DeQueue*/

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

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

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

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

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

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

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

设有字符串S和P，串的模式匹配是指确定【】。