搜索
第1页(共3页)数据结构部分（100分）一、判断题：（每题1分，共6分）：1、线性表只能用顺序存储结构实现。2、为了很方便地插入和删除数据,可以使用双向链表存放数据。3、队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。4、完全二叉树一定存在度为1的结点。5、在AOE网中，关键路径上的某个活动时间的缩短，整个工程的时间也就必定缩短。6、装填因子是哈希表的一个重要参数，它反映哈希表的装满程度。二、简答题（共22分）1、已知完全二叉树有30个结点，则整个二叉树有多少个度为0的结点？（4分）2、对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些？（4分）3、设一数列的输入序列为345678,运用栈操作,能否得到输出顺序为547863的序列？为什么？（4分）4、简述顺序表查找法、有序表查找法和索引顺序表查找法对被查找表中元素的要求？（6分）5、用线性探测法解决冲突时，如何处理被删除的结点？为什么？（4分）三、应用题（共48分）1、一棵二叉树的先序、中序和后序序列如下，其中一部分未标出，请构造出该二叉树。（8分）先序序列：CDEGHIK中序序列：CBFAJKIG后序序列：EFDB_JIHA2、对于任意一棵非空的二叉树，若度为2的结点个数为n2，叶子结点个数为n0，请给出n0和n2之间所满足的关系式n0=f(n2），要求给出推导过程。（10分）3、下图所示是一带权有向图的邻接表存储表示，请根据邻接表：（1）、画出该带权有向图的图形。（4分）（2）、以顶点V1为起点的广度优先遍历的顶点序列及对应的生成树。（4分）（3）、以顶点V1为起点的深度优先遍历的顶点序列及对应的生成树。（4分）4、按下述顺序输入关键字：（23，7，8，22，24，10，5，13，4，14，21，12），画出平衡二叉树的构造与调整过程，并为每一次的平衡处理指明旋转类型。（10分）5、已知待排序的记录关键字集为{8，3，2，5，9，1，7}，要求按照从大到小进行排序，写出用直接插入排序法进行排序的全过程。（8分）河南科技大学2007年硕士研究生入学考试试题考试科目代码：443考试科目名称：数据结构与C语言（如无特殊注明，所有答案必须写在答题纸上，否则以“0”分计算）第2页(共3页)四、算法设计题（共24分）1、已知线性表中的元素以值非递减有序排列，并以单链表作存储结构（带头结点），设计算法删除表中所有数值相同的多余元素（使操作后的线性表中的所有元素的数值均不相同），同时释放被删结点空间。（10分）2、在一棵以二叉链表表示的二叉树上，写出按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。（14分）C语言部分（共50分）一、单项选择题（每题1分，共5分）：1、以下程序的输出结果是main（）{intx=2，y=-1，z=2；if（xy）if(y0)z=0；elsez+=1；printf（“%d\n”，z）；}A）3B）2C）1D）02、下列程序执行后输出的结果是main（）{inty=10；do{y--；}while（--y）；printf（“%d\n”，y--）；}A）-1B）1C）8D）03、有一程序main(){inta[10]={1，2，3，4，5，6，7，8，9，10}，*p=a；printf（“%d\n”，*（p+2））；}该程序的输出结果是A）3B）4C）1D）24、若有定义和语句：chars[10]；s=“abcd”；printf（“%s\n”，s）；则结果是（以下[]代表空格）A）输出abcdB）输出aC）输出abcd[][][][][]D）编译不通过第3页(共3页)5、下列程序执行后输出的结果是intm=13；intfun2（intx，inty）{intm=3；return（x*y-m）；}main(）{inta=7，b=5；printf（“%d\n”，fun2(a，b)/m）；}A）1B）2C）7D）10二、程序设计题（共45分）1、有m个学生，每人考n门课程，编程计算每个学生的总分，并统计输出90分以上科目的学生。（9分）2、有一行文字，要求编写程序，将其中的每个单词的首字母由大写改为小写，假定单词之间以空格分隔。（10分）3、编写程序，利用冒泡排序法，对m个学生的成绩按照从高分到低分的顺序进行排序。（12分）4、从键盘输入数组元素，要求最小的与第一个元素交换，最大的与最后一个元素交换，并输出数组，请利用指针编写程序。（14分）