河南科技大学825数据结构与C语言真题09

第1页（共4页）河南科技大学2009年硕士研究生入学考试试题考试科目代码：825考试科目名称：数据结构与C语言（如无特殊注明，所有答案必须写在答题纸上，否则以“0”分计算）数据结构部分（共100分）一、判断下列叙述是否正确，正确的打√，不正确的打×（每题1分，共10分）1、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性。2、循环队列的引入，目的是为了克服假溢出。3、稀疏矩阵压缩存储后，必会失去随机存取功能。4、在一个有向图的邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零。5、在栈空的情况下，不能做退栈运算，否则产生下溢。6、在拓扑排序中，拓扑序列的第一个顶点必定是入度为0的顶点。7、连通网的最小生成树是唯一的。8、对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它们得到的序列顺序是一样的。9、当待排序记录已经按照从小到大或从大到小排序时，快速排序的执行时间最少。10、堆排序的方法是稳定的排序方法。二、简答题（共24分）：1、线性表有哪两种存储结构？各有什么特点？（6分）2、如果两个串含有相等的字符，能否说它们相等？（4分）3、求网的最小生成树有哪些算法？各适用于何种情况？为什么？（4分）4、已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点数最多是多少？（4分）5、什么是冲突？解决冲突的方法有哪些？（6分）三、应用题（共44分）：1、已知二叉树如图所示，要求：（1）写出先序遍历序列（2分）。（2）写出中序遍历序列（2分）（3）写出后序遍历序列（2分）。第2页（共4页）2、已知带权连通图G的邻接表如下图所示，要求：（1）画出该带权连通图G。（4分）（2）根据带权连通图G的邻接表，从顶点A出发，分别写出进行深度优先搜索遍历和广度优先搜索遍历所得顶点序列，画出对应的生成树。（8分）3、给定一组数列（15，8，10，21，6，19，3），分别代表字符A，B，C，D、E，F，G出现的频度，要求：（1）画出哈夫曼树。（4分）（2）写出7个字符的哈夫曼编码。（2分）4、已知哈希函数h(key)=3keymod11，哈希表的长度为11，关键字集合{32,13,49,24，38，21，4，12}，要求：（1）使用线性探测再散列法解决冲突构造哈希表。（5分）（2）使用链地址法解决冲突构造哈希表。（5分）（3）针对上述两种情况下，求出在等概率情况下，查找成功时的平均查找长度。（4分）5、待排序的数据元素序列为{49，38，65，97，76，13，27，50}，画出用快速排序进行排序时的一趟排序过程。（6分）四、算法设计题（共22分）1、有一个单向循环链表的长度大于1，且表中既无头结点也无头指针，已知p为指向链表中某结点的指针，试设计出在链表中删除p所指结点的前驱结点的算法。（10分）2、已知一棵二叉树以二叉链表作存储结构，编写非递归算法，将二叉树中所有结点的左、右子树交换位置。（12分）第3页（共4页）C语言部分（共50分）一、选择题（5分，每小题1分）1.C语言中的变量名只能由字母,数字和下划线三种字符组成,且第一个字符__________。A）必须为字母B）必须为下划线C）必须为字母或下划线D）可以是字母,数字或下划线中的任意一种2.以下程序的输出结果是____________。main(){inta=12,b=12;printf(%d,%d\n,--a,++b);}A）10,10B）12,12C）11,10D）11,133.以下程序输出结果是____________。main(){intm=5；if(++m6)printf(%d\n，m--);elseprintf(%d\n，m--);}A)8B)7C)6D)54.下面程序运行后的输出结果是________。main(){inta[3][4]={1,3,5,7,9,11,13,15,17,19,21,23},i,j,k=0;for(i=0;i3;i++)for(j=0;j2;j++)k+=a[i][j];printf(%d\n,k);}A)60B)68C)99D)1085.下面的程序运行后，输出下列____________所示的图形（不考虑图形的起始位置）。#includestdio.hmain(){inti,j;for(i=0;i=3;i++){for(j=0;j=2*i+1;j++)printf(%c,'%');printf(\n);}}A)*B)*****************C)%D)%%%%%%%%%%%%%%%%%第4页（共4页）二、编程题（45分）1．从键盘上输入两个正整数m和n，求它们的最大公约数。（15分）2．下面程序中函数fun()的功能是求一维数组array的最大值，请将程序补充完整。（15分）intfun(intarray[]){}voidmain(){inta[10],i,max;for(i=0;i10;i++)scanf(%d,&a[i]);max=fun(a);printf(max=%d\n,max);}3．给出一个四位以下的正整数m（m的值从键盘输入），编写程序分别按顺序和逆序输出它的每一位数字。例如给出正整数5328，则输出以下结果：（15分）m=532853288235