2017年中国林业科学研究院考研专业课815数据结构与程序设计考试真题.pdf
共 4 页 第 1 页 中国林业科学研究院 2017年硕士研究生入学考试 数据结构与程序设计 试题 注:所有答案一律写在答题纸上,写在试题纸上无效 一、名词解释 ( 每题 9 分,共 5 题,共 45 分 ) 1、数据结构 2、对角矩阵 3、 内排序 4、 遍历 5、 图 二、简答题 ( 每题 10 分,共 6 题 ,共 60 分 ) 1、 设有整数序列 a0,a1,an-1, 给出求解最大值的递归程序 。 2、 给出以下程序运行后的输出结果。 # include # include void fun (char *s, int p, int k) int i; For (i=p;ilink=NULL; else while (p0-infolink!=NULL) p2=p1; p1=p1-link; if (p0-info=p1-info) if (head=p1) (1) ; head=p0; else p2-link=p0; (2) ; else p1-link=p0; (3) ; return (head); 4、 分析下列程序,写出程序运行结果 。 # include # include using namespace std; int main() fstream outfile, infile; 共 4 页 第 3 页 outfile.open(“data.txt”,ios:out); for(int i=0;i26;i+) outfile(char)(A+i); outfile.close(); infile.open(“data.txt”,ios:in); char ch; infile.seekg(6,ios:beg); if (infile.get(ch) coutch; infile.seekg(8,ios:beg); if(infile.get(ch) outch; infile.seekg(-8, ios:end); if(infile.get(ch) coutch; coutendl; infile.close(); return 0; 5、 给定一个长度为 n的一维整数数组 a, a中连续的相等元素构成的子序列 称 为平台。试设计算法,求出 a中最长平台的长度。 6、 给定 有 m个整数的递增有序数组 am和有 n个整数的递减有序数组 bn,试写出算法:将数组 a和数组 b归并为递增有序数组 cm+n。 (要求:算法的时间复杂度为 O(m+n)。) 三、 论述题 ( 每题 15 分, 共 3 题 ,共 45 分 ) 1、 以下列序列为输入,从空树开始构造 AVL搜索树 。 ( 1) A,Z,B,Y,C,X; ( 2) A,V,L,T,R,E,I,S,O,K。 共 4 页 第 4 页 2、 设二叉树以二叉链表存储,编写程序求解下列问题的递归算法。 ( 1) 删除一棵二叉树,并释放所有的结点空间。 ( 2) 求一棵二叉树中的度为 1 的结点个数。 ( 3) 交换一棵二叉树中每个结点的左、右子树。 3、 设一棵先序线索二叉树的结点由 5 个域组成 : LTag、 LChild、 Element、 RChild和RTag,并已经建成先序线索树。试设计并实现下列三个函数: BTNode* PreGoFirst(BTNode* t) /*指针 t指 示先序线索树的根结点,函数返回该树上按先序次序遍历的第一个结点 的 指针*/ BTNode* PreNext(BTNode* p) /*p指示先序线索树 上某个结点,函数返回按先序 遍历的后继结点 指针 */ void TPreOrder(BTNode* t, void(*Visit)(BTNode* u) /*指针 t指示先序线索树的根结点, 此 函数 先序 遍历 该线索树, Visit为函数指针参数,它访问指针 u指示的结点。请调用前两个函数实现 */