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

河南科技大学825数据结构与C语言真题09河南科技大学825数据结构与C语言真题09河南科技大学825数据结构与C语言真题09xxx公司河南科技大学825数据结构与C语言真题09文件编号：文件日期：修订次数：第1.0次更改批准审核制定方案设计，管理制度河南科技大学2009年硕士研究生入学考试试题考试科目代码：825考试科目名称：数据结构与C语言（如无特殊注明，所有答案必须写在答题纸上，否则以“0”分计算）数据结构部分（共100分）一、判断下列叙述是否正确，正确的打√，不正确的打×（每题1分，共10分）线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性。循环队列的引入，目的是为了克服假溢出。稀疏矩阵压缩存储后，必会失去随机存取功能。在一个有向图的邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零。在栈空的情况下，不能做退栈运算，否则产生下溢。在拓扑排序中，拓扑序列的第一个顶点必定是入度为0的顶点。连通网的最小生成树是唯一的。对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它们得到的序列顺序是一样的。当待排序记录已经按照从小到大或从大到小排序时，快速排序的执行时间最少。10、堆排序的方法是稳定的排序方法。二、简答题（共24分）：1、线性表有哪两种存储结构各有什么特点（6分）

2、如果两个串含有相等的字符，能否说它们相等（4分）3、求网的最小生成树有哪些算法各适用于何种情况为什么（4分）4、5、什么是冲突解决冲突的方法有哪些（6分）

三、应用题（共44分）：1、已知二叉树如图所示，要求：写出先序遍历序列（2分）。写出中序遍历序列（2分）写出后序遍历序列（2分）。

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分）

C语言部分（共50分）一、选择题（5分，每小题1分）C语言中的变量名只能由字母,数字和下划线三种字符组成,且第一个字符__________。

A）必须为字母

B）必须为下划线

C）必须为字母或下划线

D）可以是字母,数字或下划线中的任意一种以下程序的输出结果是____________。

main()

{inta=12,b=12;

printf("%d,%d\n",--a,++b);

}

A）10,10 B）12,12 C）11,10 D）11,13以下程序输出结果是____________。

main()

{intm=5；

if(++m>6)printf("%d\n"，m--);

elseprintf("%d\n"，m--);

}

A)8B)7C)6D)5下面程序运行后的输出结果是________。

main()

{inta[3][4]={1,3,5,7,9,11,13,15,17,19,21,23},i,j,k=0;

for(i=0;i<3;i++)

for(j=0;j<2;j++)k+=a[i][j];

printf("%d\n",k);}

A)60B)68 C)99D)108下面的程序运行后，输出下列____________所示的图形（不考虑图形的起始位置）。

#include<stdio.h>

main()

{inti,j;

for(i=0;i<=3;i++)

{for(j=0;j<=2*i+1;j++)

printf("%c",'%');

printf("\n");

}

}

A)*B)*

******

**********

C)%D)%

%%%%%%

%%%%%%%%%%

二、编程题（45分）1．从键盘上输入两个正整数m和n，求它们的最大公约数。（15分）2．下面程序中函数fun()的功能是求一维数组array的最大值，请将程序补充完整。（15分）

intfun(intarray[])

{

}

voidmain()

{inta[10],i,max;

for(i=0;i<10;i++)

scanf("%d",&a[i]);

max=fun(a);

print