《2018年云南师范大学408计算机学科专业基础综合之数据结构考研强化五套模拟题.doc》由会员分享，可在线阅读，更多相关《2018年云南师范大学408计算机学科专业基础综合之数据结构考研强化五套模拟题.doc（5页珍藏版）》请在金锄头文库上搜索。
1、2018年云南师范大学408计算机学科专业基础综合之数据结构考研强化五套模拟题目录 2018年云南师范大学408计算机学科专业基础综合之数据结构考研强化五套模拟题（一） . 2 2018年云南师范大学408计算机学科专业基础综合之数据结构考研强化五套模拟题（二） . 8 2018年云南师范大学408计算机学科专业基础综合之数据结构考研强化五套模拟题（三） . 13 2018年云南师范大学408计算机学科专业基础综合之数据结构考研强化五套模拟题（四） . 20 2018年云南师范大学408计算机学科专业基础综合之数据结构考研强化五套模拟题（五） . 28一、算法设计题1 已知L 为没有头结点的的
2、单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符、数字字符或其他字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符(要求用最少的时间和最少的空间) 。【答案】算法如下: L 是不带头结点的单链表第一个结点的指针，链表中的数据域存放字符/本算法将链表L 分解成含有英文字母字符、数字字符和其他幸符的带头结点的三个循环链表 /建立三个链表的头结点 /置三个循环链表为空表 /分解原链表 /L指向待处理结点的后继 /处理字母字符 /处理数字字符/处理其他符号 /结束while(L!null) /算法结束 2 已知某哈希表HT 的装填因子小于1
3、，哈希函数H(key)为关键字的第一个字母在字母表中的序号。(1)处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。(2)处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。【答案】(1)算法如下: 按关键字第一个字母在字母表中的顺序输出各关键字哈希地址126 设哈希表初始值为null取关键字第一字母在字母表中的序号 (2)算法如下: 求链地址解决冲突的哈希表査找不成功时平均査找长度记査找不成功的总的次数 按我们约定，査找不成功指到空指针为止 3 已知一具有n个结点的二叉树的中序
4、遍历序列与后序遍历序列分别存放于数组 -和中(设该二叉树各结点的数据值均不相同) 。请写一建立该二叉树的二叉链表结构的非递归算法。该二叉链表的链结点结构为(lchild, data , rchild) ，其中data 为数据域，lchild 与rhild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用nil 表示) 。【答案】算法如下: 由二叉树的中序序列IN 和后序序列POST 建立二叉树 和 为栈，容量足够大 初始化 取出栈顶数据 在中序序列中査等于.根结点的值无左子树 将建立左子树的数据入栈 分別是中序序列和后序序列第一和最后元素的下标，初始调用时，的结点无右
5、子树 右子树数据入 结束: 4 试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为x 的结点，以及以它为根的子树，且释放相应存储空间。二叉树的三叉链表的描述为: 二叉树根结点的指针【答案】算法如下: 生成三叉链表的二叉树(题目给出PASCAL 定义，下面用类C 语言书写)是二叉树结点指针的一维数组，容量足够大一维数组最后元素的下标 元素或虚结点 根结点 双亲结点和子女结点用指针链上 结束 5 用邻接多重表存储结构，编写FERST-ADJ(G，V) 函数，函数返回值为第一个邻接点，若V 没有邻接点，返回零。【答案】算法如下: 在邻接多重表g 中，求v 的第一邻接点, 若存在，返回第一邻接点，否则返回 确定顶点v 在邻接多重表向量中的下标, 不考虑不存在v 的情况 返回第一邻接点，和中必有一个等于i取第一个边结点 考研试题
