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

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

第1页（共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)=3key mod 11，哈希表的长度为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分）

第2页（共4页）

C语言部分（共50分）

一、选择题（5分，每小题1分）

1. C语言中的变量名只能由字母,数字和下划线三种字符组成,且第一个字符__________。

A）必须为字母 B）必须为下划线

C）必须为字母或下划线

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

main()

{ int a=12, b=12;

printf(\ }

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

main( ) { int m=5；

if (++m>6) printf(\，m--); else printf(\，m--); }

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

main( )

{ int a[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(\

A) 60 B) 68 C) 99 D) 108

5. 下面的程序运行后，输出下列____________所示的图形（不考虑图形的起始位置）。

#include main() { int i,j;

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

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

A) * B) * *** *** ***** ***** C) % D) % %%% %%% %%%%% %%%%%

第3页（共4页）

二、编程题（45分）

1．从键盘上输入两个正整数m和n，求它们的最大公约数。（15分）

2．下面程序中函数fun( )的功能是求一维数组array的最大值，请将程序补充完整。（15分） int fun(int array[ ]) { }

void main( )

{ int a[10], i,max; for(i=0;i<10;i++) scanf(\ max=fun(a);

printf(\ }

3．给出一个四位以下的正整数m（m的值从键盘输入），编写程序分别按顺序和逆序输出它的每一位数字。例如给出正整数5328，则输出以下结果：（15分） m=5328 5 3 2 8 8 2 3 5

第4页（共4页）