825数据结构与C语言试题10

第1页（共3页）河南科技大学2010年硕士研究生入学考试试题考试科目代码：825考试科目名称：数据结构与C语言（如无特殊注明，所有答案必须写在答题纸上，否则以“0”分计算）数据结构部分（100分）一、判断题（正确的打√，错误的打×，每题1分，共5分）1、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。2、栈和队列都是限制存取点的线性结构。3、若一个广义表的表头为空，则此广义表亦为空表。4、二叉树就是结点度为2的树。5、用顺序表和单链表表示的有序表均可使用折半查找方法来提高查找速度。二、简答题（共27分）：1、链表所表示的元素是否是有序的？如果有序，则有序性体现在何处？链表所表示的元素是否一定要在物理上是相邻的？（6分）2、内存中一片连续空间（地址从1－m），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任何一个栈，仅当这部分空间全满时才发生上溢。（5分）3、从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转化为二叉树的基本目的是什么？并指出树和二叉树的主要区别。（6分）4、简述有向图和无向图各有哪几种存储结构？（6分）5、采用折半查找方法进行查找的数据文件应满足什么条件？（4分）三、应用题（共48分）：1、已知图中二叉排序树的各结点的值为22～30，请标出各结点的值。（7分）2、已知无向图G如下所示：（1）、根据图G，写出从顶点1出发的广度优先搜索的顶点序列和对应的生成树。（8分）（2）、写出对应的邻接矩阵（4分）（3）、画出对应的邻接表（4分）第2页（共3页）3、列出下图中从顶点1开始的所有拓扑排序序列。（9分）4、假定对长度为10的有序表进行折半查找：（1）画出描述折半查找过程的判定树（6分）（2)假定每个元素的查找概率相等，求查找成功时的平均查找长度(2分)5、判别以下序列是否为堆？如果不是，则把它调整为堆。（8分）（1）、（100，90，80，60，85，75，20，25，10，70，65，50）（2）、（100，70，50，20，90，75，60，25，10，85，65，80）四、算法设计题（共20分）：1、写出单链表（带头结点）逆置的算法（要求利用原来的存储空间）。（8分）2、已知一棵完全二叉树存储于顺序表sa中，sa.elem[1..sa.lenth]含结点值。编写算法由此顺序存储结构建立该二叉树的二叉链表。（12分）C语言部分（50分）五、选择题（5分，每小题1分）1.表达式:10!=9的值是____________。A)trueB)非零值C)0D)12.为了表示关系|x|≥3，应使用C语言表达式____________。A)(x=3)&&(x=-3)B)(x=3)OR(x=-3)C)(x=3||x=-3)D)(x=3)&(x=-3)3.下面程序的运行结果是____________。#includestdio.hvoidmain(){ints=0,i=1;s=s+i*i;i++;printf(%d,--i);}A)2B)1C)0D)-14.定义如下变量和数组:inti;intx[4][4]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};则下面语句的输出结果是__________。for(i=0;i4;i++)printf(%3d,x[i][i]);A)15913B)161116C)471013D)4812165.调用函数时，当实参和形参都是简单变量时，它们之间数据传递的过程是________。第3页（共3页）A)实参将其地址传递给形参，并释放原先占用的存储单元B)实参将其地址传递给形参，调用结束时形参再将其地址回传给实参C)实参将其值传递给形参，调用结束时形参再将其值回传给实参D)实参将其值传递给形参，调用结束时形参并不将其值回传给实参六、编程题（45分）1．从键盘上输入一元二次方程的系数a,b,c，编程计算方程的解，要求对于方程有两个相等的实根、两个不同的实根、一对共轭复根三种可能的情况分别进行处理，输出保留2位小数。(15分)2．编写程序，按以下公式计算S之值。（15分）99917151311S3．一个三位数，它的每个数字的立方之和等于它本身，这样的三位数称为水仙花数。例如407=43+03+73，407就是一个水仙花数。在主函数输入一个三位整数n，调用fun函数判断n是否为水仙花数。请将fun函数补充完整。（15分）#includestdio.h#includemath.hintfun(intn){}main(){intn;printf(EnteraInteger:\n);scanf(%d,&n);if(fun(n)==1)printf(%dis\n,n);elseprintf(%disnot\n,n);}