扬州大学858程序设计与数据结构专业课（编程题篇）_858c语言程序设计与数据结构

author：江上_酒
23扬大信工考研交流群：714584589

前言

     各位考生在对858程序设计与数据结构做了了解之后会发现其整体的难度不大，存在难度的地方主要是程序设计与数据结构算法实现部分，其中程序设计的难度又低于算法设计。因此本篇主要是针对858程序设计与数据结构的程序设计与算法设计，尤其是算法设计做一个全面的总结，以期在考前能让大家不再盲目复习，能够有针对性的看一些题目。

程序设计

     程序设计主要是指C程序设计（可以用其它语言来实现），主要考察的是基础的编程能力，如对循环结构的灵活使用，函数的定义及调用、指针的运用等。程序设计的题目分值一般占当年考察代码题总分的一半。对于有着基本的编程思维，平时能够敲一下简单的代码的同学来说这就是送分题。

题型一：基本程序设计

1. 求和、求均值（求均值的过程一般包含求和，这里以求均值为例）

• 题目要求：从键盘上输入10个数，求其平均值。
• 设计实现：

  void average()
  {
      int a,i,sum=0;
      float ave;
      for(i=0;i<10;i++)
      {
          scanf("%d",&a);
          sum+=a;
      }
      ave=sum/10;
      printf("十个数的平均数ave=%.2f",ave);
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12

2. 求乘积

• 题目要求：编写程序实现求1-10之间的所有数的乘积并输出。
• 设计实现：

  void product()
  {
      int i,product=1;
      for(i=1;i<=10;i=i+1)
          product=product*i;
      printf("1-10之间所有数的乘积为:%d",product);
  }
  1
  2
  3
  4
  5
  6
  7

3. 值类型统计（正数、负数和零的个数或者奇数、偶数的个数、或者质数、合数的个数）

• tip：针对这些值类型本身也可以考察：例如：输出1-100之间的所有质数、或者判断一个数是否为质数（质数别称素数）等等。
• 题目要求：从键盘输入10个整数，统计其中正数、负数和零的个数，并在屏幕上输出。
• 设计实现：

  void statistics()
  {
      int a;
      int r=0,s=0,t=0;
      printf("请输入10个数据：");
      for(int i=0;i<10;i++)
      {
          scanf("%d",&a);
          if(a>0)
              r++;
          else if(a<0)
              s++;
          else
              t++;
      }
  	printf("正数：%d,负数：%d,零：%d\n",r,s,t);
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

4. 更多习题见《程序设计与算法讲义》：page4(6)、page6(10)、page7(11)

题型二：数组与矩阵（矩阵本质上是一个二维数组，故归为一类）

1. 数组及矩阵的遍历（题目较多仅举两列）

• tip：这里主要的难点在于能否根据题目要求实现按行、按列或按需求遍历数组和矩阵，可以在此多加练习一通百通。
• 题目一要求：设二维数组a[1…m, 1…n] 含有m*n 个整数。判断a中所有元素是否互不相同?输出相关信息(yes/no)。
• 设计实现:点此链接查看详解
• 题目二要求：若矩阵Am*n中存在某个元素aij满足：aij是第i行中的最小值且是第j列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。
• 设计实现:点此链接查看详解
• 更多习题见《程序设计与算法讲义》：page8(15)、page9(17)、page10(20)、page11(22)

2. 数组的递归逆序和非递归逆序

• 题目一要求：将一个有10个元素的数组中的值(整数)按逆序重新存放。
• 设计实现：

  #define N 10
  void reverse_order()
  {
      int a[N],i,temp;
      printf("请输入数组：");
      for(i=0;i<N;i++)
          scanf("%d",&a[i]);
      for(i=0;i<N/2;i++)
      {
          temp=a[i];
          a[i]=a[N-i-1];
          a[N-i-1]=temp;
      }
      printf("逆序后的数组为：");
      for(i=0;i<N;i++)
          printf("%d",a[i]);
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

• 题目二要求：编写对数组求逆的递归算法。
• 设计实现：

  void reverse(int a[],int n)
  {
      if(n==0 || n==1) 
          {return;}
      int temp=a[0];
      a[0]=a[n-1];
      a[n-1]=temp;
      reverse(a+1,n-2);
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9

3. 数组的合并

• 数组的合并与数据结构的线性表合并其在本质上是一致的，这种题型包括：两个升序合并为一个升序序列、一个升序一个降序合并为一个升序（或降序）序列等等，考生对这种题型应该多加分析与练习，掌握其规律做到胸有成竹。
• 题目要求一：给定有m个整数的递增有序数组a[1…m]和有n个整数的递减有序数组b[1…n]，试写出算法：将a数组和b数组归并为递增有序数组c[1…m+n]。（要求算法的时间复杂度为O（m+n））。
• 设计实现：

  void merge(int a[],int b[],int c[],int m,int n)
  {
      int i=1,j=n,k=1;
      while(i<=m && j>=1)
      {
          if(a[i]<b[j]) c[k++]=a[i++];
          else c[k++]=b[j--];
      }
      while(i<=m) c[k++]=a[i++];
      while(j>=1) c[k++]=b[j--];
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11

• 题目二要求：给定有m个整数的递增有序数组a和有n个整数的递减有序数组b，将a数组和b数组归并为递增有序数组c。
• 设计实现：

  void merge(int a[],int b[],int c[],int m,int n)
  {
      int i=0,j=n-1,k=0;
      while(i<m && j>=0)
      {
          if(a[i]<b[j]) c[k++]=a[i++];
          else c[k++]=b[j--];
      }
      while(i<m) c[k++]=a[i++];
      while(j>=0) c[k++]=b[j--];
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11

题型三：字符串相关程序设计

• tip：字符串在操作时一般是将其转换为字符数组，这里仅举两例（有一道真题）。

1. 题目要求：编写程序，功能是删除字符串s中的所有空格。
   设计实现：

   void reduce_space(char s[])
   {
       int i,j;
       for(i=j=0;s[i]!='\0';i++)
       {
           if(s[i]!=' ')s[j++]=s[i];
           else s[j]=s[i]; 
       }   
       s[j]='\0';
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10

2. 题目要求：编写算法，求得所有包含在串s中而不包含在串t中的字符（s中重复的字符只选一个）构成的新串r，以及r中每个字符在s中第一次出现位置。
   设计实现:点此链接查看详解

数据结构算法设计

数据结构的算法设计主要考察的是对线性表（顺序表、链表）、栈、队列、树等四种结构的算法设计、图的代码目前没有过考察不用担心。还有就是查找排序的相关实现等，接下来我就从几个方面做一个大概总结。

线性表

1. 顺序表

• 顺序表的基本操作：查找、插入等
• 顺序表的合并，可以参考数组的合并，两者本质上来说是一致的
• 有序表的插入和删除（插入删除后仍保持顺序表有序）

2. 链表

• 链表的基本操作：查找、插入、求元素个数等
• 链表的整表创建（头插法、尾插法，建议掌握头插法）
• 链表的逆置（使用头插法实现链表逆置）
• 链表的合并，其原理跟数组和顺序表的合并一致，只是实现上有差异

3. 题目参见《程序设计与算法讲义》：page21-page23

栈和队列

1. 栈本身的考点：掌握链栈和顺序栈的实现
2. 栈的应用

• 用于进制转换
• 用于判断字符是否回文 代码详解见此
• 用于判断括号是否匹配
• 用于二叉树的前序非递归遍历

3. 队列本身的考点：掌握链队和顺序队（循环队列）的 实现
4. 队列的应用

• 用于二叉树的层序遍历
• 用于求二叉树的最大宽度
• 用于判定二叉树是否为完全二叉树

树和二叉树

1. 二叉树的遍历与创建（创建的过程就是遍历的过程）

• 二叉树的前序遍历、中序遍历、后续遍历的的递归实现
• 二叉树前序遍历的非递归实现 代码详解见此
• 二叉树的层序遍历

2. 拓展

• 判断两棵二叉树是否相似
• 计算二叉树的高度（深度）
• 计算二叉树中叶子结点的个数
• 计算二叉树的宽度
• 完全二叉树的创建与判断一棵树是否为完全二叉树

3. 题目参见《程序设计与算法讲义》：page42-page46

查找

1. 顺序表的查找
2. 有序表的查找

• 折半查找的递归和非递归实现
• 差值查找（与折半查找只在折半的过程上有差异，不用特意去看，差值公式不需要记）

3. 二叉排序树

• 见模拟题中的程序填空题

4. 散列表查找

• 代码考过一次，再考可能性不大，重点在应用题

排序

1. 需要掌握的排序（顺序表和链表的都应该会，如果分开掌握有难度，建议掌握顺序表实现的，然后将其改写成链表实现的）

• 冒泡排序
• 简单选择排序
• 直接插入排序

2. 剩下的四种排序能写出过程即可
3. 其它类型的排序根据题目要求具体看待（不大可能出现，上一次是13年）