计算机软件技术基础（2）
要求:
1. 独立完成，作答时要写明题型、题号；
2. 作答方式：手写作答或电脑录入，使用A4格式白纸；
3. 提交方式：以下两种方式任选其一，
1）手写作答的同学可以将作业以图片形式打包压缩上传；
2）提交电子文档的同学可以将作业以word文档格式上传；
4. 上传文件命名为“中心-学号-姓名-科目.rar ”或“中心-学号-姓名-科
目.doc ”；
5. 文件容量大小：不得超过10MB
请在以下五组题目中任选一组作答，满分100分。
第一组：
一、程序编写题（每小题25分，共100分）
（一）
在编写的程序中，要求：
1）用fun函数完成：求n以内（不包括n）能被3整除的所有自然数之和，并把结果作为函数值返回。
2）在main函数中输入一个自然数，调用fun函数，输出fun函数返回的结果。
#in elude <>
int fun （i nt n）
{
int sum,k;
sum=0;
for（k=1;k< n;k++）
if（k%3==0） sum=sum+k;
return sum;
}
void mai n（）
{
int n,s;
printf（" 输入自然数n:\n"）;
sea nf（"%d",&n）;
s=fu n（n）;
printf（"\nn 以内（不包括n）能被3整除的所有自然数之和为%d",s）;
(二)
请编写函数int fun(char *str) ，该函数的功能是：判断字符串是否为回文若是则函数返
回1主函数中输出yes，否则返回0,主函数中输出no。
回文是指顺读和倒读都是一样的字符串。
#include <>
int fun(char *str)
{
int i=0,j=0;
while(str[i]!='\0') i++;
i--;
for(;j<=i;i--,j++)
{
if(str[i]!=str[j]) break;
}
if(j<=i)
return 0;
else
return 1;
}
void main()
{
char a[100];
int flat=0;
printf(" 请输入字符串：\n");
gets(a);
flat=fun(a);
switch(flat){
case 1:printf("yes\n"); break;
case 0:printf("no\n"); break;
}
}
(三)
设A、B是两个线性表，其表中元素递增有序，长度分别为m和n。
试写一算法分别以顺序存储和链式存储将A和B归并成一个仍按元素值递增有序的线性表Co
1. 顺序存储
SeqList *Seqmerge(SeqList A,SeqList B,SeqList *C)
{
i=0;j=0;k=0; 式存储
void MergeList_L （Listlink &La,Listlink &Lb,Listlink &Lc ）
{
Listlink *pa,*pb,*pc; pa=La->next;pb=Lb->next;
Lc=pc=La; 编写程序，计算并输出 X 3+X 5
4. 数学中，阶乘函数的递归定义为：
若 n=0, n!= 1;
若 n>0, n!=n*（n-1）!;
编写程序，计算并输出 n!
（一）
设指针 la 和 lb 分别指向两个不带头结点的单链表的首结点，设计从表 la 中删除第 i 个元 素起共 len 个元素，并将这些元素插入到 lb 中第 j 个结点之前的算法。
（二）
1. 编写递归函数求 1+2+3+,, +m 的值。
2. 设指针 la 和 lb 分别指向两个不带头结点的单链表的首结点，设计从表
la 中删除第 i 个
元素起共 len 个元素，并将这些元素插入到 lb 中第 j 个结点之前的算法。
第三组：
，其功能是计算并输出 100 以内的偶数之和 ，它的功能是：计算
并输出 1 00以内的所有素数 5!+6!
（X 3）2 并编写一个按指数值递增次序输入所产生的多项式链表的 过程 （三） 1. 单链表 L 是一个递减有序表，试写一高效算法，删除表中值大
于 min 且小于 max 的 结点 （ 若表中有这样的结点 ） ，同时释放被删结点空间，这里
min 和 max 是两个给定 的参数。
2. 编写一个算法将一个头结点指针为 pa 的单链表A 分解成两个单链表 A 和B,其头结
点指针分别为pa 和pb ,使得A 链表中含有原链表 A 中序号为奇数的元素，
而B 链表 中含有原链表A 中序号为偶数的元素，且保持原来的相对顺序。
（四）
已知由单链表表示的线性表中,含有三类字符的数据元素 （ 如：字母字符、数字字符和其他 字符 ）,试编写算法构造三个以循环链表表示的线性表, 使得每个表中只含有同一类的字符, 且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间。
第四组：
一、 程序编写题（每小题 25 分，共 100分）
（一）
25 分，共 100 分）
一、 程序编写题（每小题
（一）
1. 2. 3. 4. （二） 编写函数 void fun （） 编写函数 void fun （） 编写程序，计算并输出
编写程序，计算并输出
给出用单链表存储多项式的结构，
1．试用顺序表作为存储结构，实现将线性表（a0 ，a1，a2 ，,an-1）就地逆置的操作，所谓“就地”是指辅助空间为O（1）。
2. 设顺序表L是一个递增（允许有相同的值）有序表，试写一算法将x插入L中，并使L仍为一
个有序表。
（二）根据上题的单链表存储多项式的结构，编写一个过程实现两个多项式相加的运算。
（三）
假设以两个元素值递增有序排列的线性表A、B分别表示两个集合，要求另辟空间构造一个线性表C,其元素为两集合的交集，且表C中的元素值也递增有序排列。
用顺序表实现并写出C的算法。
（四）
己知A、B和C为三个递增有序的线性表，现要求对A表进行如下操作：删去那些既在B表中出现又在C表中出现的元素。
试对顺序表编写实现上述操作的算法（注：题中未特别指明同一表中的元素值各不相同）。
第五组：
一、程序编写题（每小题25 分，共100分）
（一）
编程实现ret （）函数，函数功能是：将一维数组 a （有n个元素，且任何元素均不为零）分拆为两个数组b和c，使a中大于零的元素存放在b中，小于零的元素存放在c中。
（二）
1. 编写函数double fun （intn），它的功能是：计算并输出下列级数和：
s=1/1*2+1/2*3+ …+1/ n（n+1）
2. 请编写函数void fun （char *s,char t[]），其功能是：将s所指字符串中除了下标为偶数、同时ascii 值也为偶数的字符外，其余的全都删除；串中剩余字符所形成的一个新串放在t 所指的一个数组中。
（三）
设计一段程序：函数difference（A,B）用于求两集合之差C=A-B,即当且仅当e是A中的一个元素，且不是B中的元素时，e是C中的一个元素。
集合用有序链表实现，用一个空链表表示一个空集合，表示非空集合的链表根据元素之值按递增排列，执行C=A-B之后，表示集
合A和B的链表不变，若结果集合C非空，则表示它的链表应根据元素之值按递增序排列。
函数append（）用于在链表中添加结点。
（四）
具有n 个结点的完全二叉树，已经顺序存储在一维数组A[1..n] 中，设计一个算法将
A中顺序存储变为二叉链表存储的完全二叉树。