作业8解答

查找与索引技术 作业8 单项选择题

1．ISAM文件和VASM文件属于（ ）。（北方名校经典试题）

A）索引非顺序文件 B）索引顺序文件 C）顺序文件 D）散列文件

【分析】ISAM为索引顺序存取存取方法（indexed Sequential Access Method）的缩写，是一种索引顺序文件。

VSAM为虚拟存取方法（Virtual Storage Access Method）的缩写，此方法利用了操作系统的虚拟存储器的功能，但实质也是一种索引顺序文件。

【答案：B】

2．用ISAM组织文件适合于（ ）。（北方名校经典试题）

A）磁带 B）磁盘 C）磁鼓 D）前面都不正确 【分析】ISAM为索引顺序存取存取方法（indexed Sequential Access Method），是一种专为磁盘存取设计的文件组织形式。

【答案：B】

3．若在线性表中采用折半查找法查找元素，该线性表应该（ ）。（北方名校经典试题）

A）元素按值有序 B）采用顺序存储结构 C）元素按值有序，且采用顺序存储结构 D）元素按值有序，且采用链式存储结构

【分析】能采用折半查找法查找元素的线性表，必须是有序表，且是顺序存储的，不能是链式存储。这题由于折半查找要求能够直接定位线性表中任一元素，而链式结构无法做到这一点。

【答案：C】

4．在下列查找方法中，平均查找速度是快的是（ ）。

A）顺序查找 B）折半查找 C）分块查找 D）二叉排序树查找

2

【分析】顺序查找的平均时间复杂度为O(n)，分块查找的平均时间复杂度为O((n/s+1)/2+1)或O(log2(n/s+1)+s/2)，都比折半查找平均时间复杂度O(log2n)大，虽然二叉排序树查找时在随机情况下的时间复杂度也为O(log2n)，但是折半查找在最坏情况下的时间复杂度为O(log2n)，而当二叉排序树查找为单支树时，查找时与顺序查找相同，时间复杂度为O(n2)，所以本题应选择B。

【答案：B】

5．在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与

326 数据结构

（ ）量级相当。（东部名校经典试题）

A）顺序查找 B）折半查找 C）分块查找 D）前面都不正确 【分析】在随机的情况下，二叉排序树的平均查找长度的数据量级为O(log2n)，与折半查找同数量级。

【答案：B】

6．采用分块查找时，如某线性表中共有256个元素，查找每个元素的概率相同，假设采用顺序查找来确定元素所在的块，则每块包含（ ）个结点时，平均查找长度最小。（东部名校经典试题）

A）256 B）15 C）16 D）18

【分析】对于分块查找方法设长度为n的表均匀地分成b块，每块含有s个元素，用顺序查找确定所在的块时平均查找长度为

1n1n当s=n=16时，(?s)?1取(?s)?1，

2s2s最小值n+1=17。

【答案：C】

二、综合题

1．已知关键字序列{23，13，5，28，14，25}，试构造二叉排序树。（东部名校经典

试题）

【解答】构造二叉排序树的过程如下图所示。

图 构造二叉排序树的过程示意图

构造的二叉排序树如下图所示：

图 二叉排序树示意图

2．已知一组关键字为（19，14，23，1，68，20，84，27，55，11，10，79），哈希

第9章 文件与动态存储管理 327 函数：H(key)=key MOD 13，哈希地址空间为0~12，请构造用链地址法处理冲突的哈希表，并求平均查找长度。（东部名校经典试题）

【解答】哈希表如下图所示：

图 哈希表示意图

平均查找长度为ASL=1(1*6+2*4+3*1+4*1)=1.75

123．已知哈希表地址空间是0..8，哈希函数是H(k)=k%7，采用线性探测再散列处理冲突，将序列{100,20,21,35,3,78,99,45}数据序依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度。（东部名校经典试题）

【解答】哈希表及查找各关键字的比较次数如下表所示：

哈西表及查找各关键字的比较次数

哈希地址 关键字 比较次数 0 21 1 1 35 2 2 100 1 3 3 1 4 78 4 5 99 5 6 20 1 7 45 5 8 平均查找长度=4?1?1?2?1?4?2?5?2.5

84．已知关键字序列{12,26,38,89,56}，试构造平衡二叉树。 【解答】

在构造平衡二叉树时，与构造二叉排序树类似，也是从空二叉树开始，用二叉排序树的方法依次插入结点，如出现不平衡时，作适当的旋转操作使用变成平衡二叉树即可，本题构造过程如下图7-32所示：

328 数据结构

图 构造平衡二叉树的过程示意图

如下图所示：

图 平衡二叉树示意图

5．编写判定给定的二叉树是否是二叉排序树的函数。（南方名校经典试题） 注：此题选做。

【解答】判定二叉树是否为二叉排序树同样是建立在中序遍历的框架基础下，在遍历中附设一指针pre指向当前访问结点的中序直接前驱，每访问一个结点便比较前驱结点pre和此结点是否有序，若遍历结束后各结点和其中序直接前驱均满足有序，则此二叉树为二叉排序树；否则只要有一个结点不满足，那么此二叉树就不是二叉排序树。

C++语言版测试程序见8_2_5c++，具体算当如下：

template

bool IsBST(Binary_node *sub_root,Binary_node *pre=NULL) // 判断二叉树sub_root是否为二叉排序树,pre为当前被遍历结点的前驱，初值为空 { if(sub_root) { if(IsBST(sub_root->left,pre)==false) return false; //如左子树不为二叉排序树，则返回false if(pre) { if(pre->data>sub_root->data) return false;//如果pre与当前结点无序，则返回false } pre=sub_root; if(IsBST(sub_root->right,pre)==false) return false; //如左子树不为二叉排序树，则返回false } return true; }

第9章 文件与动态存储管理 329

template

bool IsBST(const Binary_tree &T) // 判断二叉树T是否为二叉排序树 { return IsBST(T.get_root()); }

C语言版测试程序见8_2_5c，具体算当如下：

Status IsBST(BiTree T,BiTNode *pre=NULL) // 判断二叉树T是否为二叉排序树,pre为当前被遍历结点的前驱，初值为空 { if(T) { if(IsBST(T->lchild,pre)==FALSE) return FALSE; //如左子树不为二叉排序树，则返回FALSE if(pre) { if(pre->data.key>=T->data.key) return FALSE;//如果pre与当前结点无序，则返回FALSE } pre=T; if(IsBST(T->rchild,pre)==FALSE) return FALSE; //如左子树不为二叉排序树，则返回FALSE } return TRUE; }

6．试编写一用链地址法解决冲突解决冲突的哈希表插入函数。（东部名校经典试题） 注：此题选做。

【解答】对此哈希表的插入，首先通过哈希函数确定此关键字要插入的链表，然后在此链表中插入此关键字。

C++语言版测试程序见8_2_6c++，具体算当如下：

template int Hash(Key K) // 哈希函数 { return K % CHAINNUM; }

template

void InsertHash(LList *HT[CHAINNUM],Elem e) // 使用链地址法解决冲突的哈希表的插入 { int i=Hash(e.key); //i为在K所对应的链表 //将p插入到链表HT[i]的首部 cout<

330 数据结构

}

HT[i]->append(e);

C语言版测试程序见8_2_6c，具体算当如下：

int Hash(KeyType K) // 哈希函数 { return K % CHAINNUM; }

void InsertHash(ChainHash &HT,HElemType e) // 使用链地址法解决冲突的哈希表的插入 { int i=Hash(e.key); //i为在K所对应的链表 ChainNode *p=new ChainNode;//生成所插入的结点 //将p插入到链表HT[i]的首部 cout<data=e;p->next=HT[i];HT[i]=p; }

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库作业8解答在线全文阅读。