招生：管理科学与工程

试科目：423程序设计

试时间：3小时

一、简答题（本大题5小题，每小题5分，计25分）

1、试举例说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。

2、给出下算法的时间复杂度：

main()

{

intx,n,y;

scanf(“d”,&n);

x=n;y=0;

while(x>=(y 1)(y 1))

y ;

}

3、表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素？是否是稀疏矩阵？

4、对链表设置表头结点的作用是什么？（至少说出2条好处）

5、快速排序在什么情况下排序算法产生恶化，原因是什么？

二、给出下面问题的算法函数描述（本大题3小题，每小题10分，计30分）

1、设计一个将单循环链表逆置的算法函数。

2、给定一棵用二叉链表表示的二叉树，每个结点都有2个指针（lchild，rchild），分别用来指向其左右、子女，该树的根结点指针为t，试编写一个非递归求二叉树的叶子结点数目的算法函数。

3、设无向图采用邻接矩阵方法存储，请给出其广度优先搜索的算法函数。

三、下面是一段电文{CASETATASA}，根据字符出现的频率做权值构造一棵哈夫曼树，并给出每个字符的哈夫曼编码。（本大题1小题，每小题10分，计10分）

四、设散列表为HT[0..16]，即表的大小为m=17。现采用双散列法解决冲突。散列函数为：H0（key）=key；注：是求余数运算（=mod），

Hi=（REV（key 1） 1）；i=1,2,3,…,m-1

其中，函数REV（x）表示颠倒10进制数x的各位，如REV（37）=73，REV（7）=7等。若插入的关键码序列为{37,8,31,20,19,18,53,27}。试画出插入这8个关键码后的散列表。（本大题1小题，每小题10分，计10分）

五、算法及程序填空（本大题4小题，计10个空，每个空4分，计40分）

1、下算法程序是在栈顶指针为HS的链表中，计算该链栈中结点个数的函数。

函数：

typedefstructnode1

{

intdata；

structnode1next；

}node；

intcount（HS）

node*HS；

{

node*p；

intn=0；

p=HS；

while（p！=NULL）

{

（1）；

（2）；

}

return（n）；

}

2、设一棵二叉序列树b，下列算法函数是实现在b中插入一个结点s。

函数：

voidinsert（btree*b，btree*s）

{

if（b==NULL）b=s；

else

if（s->data==b->data）return();

else

if(s->data<b->data)

(3)；

else

(4)；

}

3、[程序说明]下面程序的功能是输出正文中含有字母‘s’的所有行。函数getline的作用是输入一行字符到数组中，并返回最后一个字母。

#include<stdio.h>

chargetline(chars[],intlim)

{inti；charc；

for（i=0；i<lim&&（5）!=’.’&&c!=’\n’；i ）

s[i]=c；

if（（6））

{s[i]=c；i ；}

s[i]=’\0’;

return(c)；

}

main()

{charch,line[500]；

intk；

do{ch=getline（line，5）；

for（k=0；line[k]！=’\0’；k ）

if（line[k]==’s’）

{printf（“s”，line）；

（7）；

}

}

while（ch！=’.’）；

}

4、数组按值从大到小的顺序排序后输出

voidsort（float*myarray，intarraysize）；

#include<stdio.h>

voidmain()

{

floata[7]={2,6,3,8,3,12,9}；

inti；

（8）

for（i=0；i<7；i ）

printf（“f”，a[i]）；

printf（“\n”）；

}

voidsort（（9））

{

inti，j，k；

floatt；

for（i=0；i<n-1；i ）

{

k=i；

for(j=j 1；j<n；j )

if（（10））

k=j；

t=*（p i）；

*（p i）=*（p k）；

*（p k）=t；

}

}

六、按下面的要求分别给出完整的C语言程序。（本大题3小题，第1小题10分，第2小题10分，第3小题15分，计35分）

1、试编写一个程序，将任意输入的一个整数求出该整数是几位数，并把它按逆序输出（例、原数据258，应输出852，原数据-357，应输出-753）。

2、已知某数列的前两项分别为2和3，其后继项根据当前最后两项之乘积按下列规则生成：

（1）若乘积为一位数，则该乘积即为数列的后继项；

（2）若乘积为二位数，则该乘积的十位数字和个位数字依次作为数列的两个后继项。

请编制一个函数sum（n，pa）生成并输出该数列的前n项以及它们的和。其中sum返回数列的前n项之和并将生成的前n项存放于首指针为pa的链表中。函数规定输入的参数n必须大于2且小于给定的常数MAXNUM。

3、有一组英文单词已按字典顺序排好存在一个二维字符数组中，现输入一个英文单词，要求将它插入到字符数组中，并保持数组中的单词仍然保持字典顺序不变。