2017年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研冲刺密押题
● 摘要
目录
2017年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研冲刺密押题（一） .... 2 2017年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研冲刺密押题（二） .. 12 2017年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研冲刺密押题（三） .. 26 2017年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研冲刺密押题（四） .. 35 2017年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研冲刺密押题（五） .. 45
一、算法设计题
1． 编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A ～Z 这26个字母和0～9这10个数字）。
【答案】算法如下：
2． 令G=（V , E）为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下 条件：若从顶点i 至顶点j 有一条弧，则应使i 【答案】算法如下： //对以邻接表存储的DAG 图g 重新编号, 使若有 i< j //求各顶点的入度 //记录结点的逆序序号 3． 假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法（注： 己知树中的结点数）。 【答案】算法如下： int Depth （PTree t） //求以双亲表示法作为存储结构的树的深度 {int maxdepth=O; For （i=l; i<=t.n; i++） {temp=0; f=i; while （f>0） {temp++; f=t.nodes[f].parent; } // 深度加1，并取新的双亲 if （temp>maxdepth） maxdepth=temp; //最大深度更新 } return （maxdepth}; //返问树的深度） //结束Depth 4． 设在4地 之间架设有6座桥，如图所示。 图 要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。 （1）试就以上图形说明：此问题有解的条件是什么？ （2）设图中的顶点数为n ，试用C 或一个算法，找出满足要求的一条回路。 【答案】 （1）只有所有的顶点的度都是偶数，才能有解。 （2）算法如下: 语言描述与求解此问题有关的数据结构并编写 修改常规访问标志数组该边尚未访问。 5． 已知一棵高度为K 具有n 个结点的二叉树，按顺序方式存储。 （1）编写用前序遍历树中每个结点的非递归算法； （2）编写将树中最大序号叶结点的祖先结点全部打印输出的算法。 【答案】（1）算法如下: //全局变量 的含义：当元素值为1时表示该边已访问；当元素值为0时表示 void PreOrder（ElemType bt[], i ） //递归遍历以顺序方式存储的二叉树bt , i 是根结点下标初始调用时为1） {int top=0, s[]; //top是栈s 的栈顶指针, 栈容置足够大 while （i<=m||top>0） {while（i<=m） {if（bt[i]!=0）printf （bt[i]）; //访问根结点，设虚结点以0表示 if （bt[i]l=0 && 2*i+l<=m） s[++topj=2*i+l; //右子女的下标位置入栈 i=2*i; //沿左子女向下 } if （top>0） i=s[top--）; //取出栈顶元素