数据结构上机考试(含答案)

1、设有两个有序序列，利用归并排序将它们排成有序表，并输出。

2、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果在输出“YSE”；否则，将它插入到序列中使它仍然有序，并输出排序后的序列。

3、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果不在，则输出“NO”，否则，将它从序列中删除它，并输出删除后的序列。

4、从键盘输入一组任意数据，建立一个有序链表，并从链头开始输出该链，使输出结果是有序的。

5、从键盘输入一组任意数据，建立一个包含所有输入数据的单向循环链表，并从链表的任意开始，依次输出该链表中的所有结点。

10、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果不在，则输出“NO“，否则，将它从链表中删除，并输出删除后的链表。

11、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果在输出“YSE”，否则，将它从插入到链头，并输出插入后的链表。

12、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果在输出“YSE”，否则，将它从插入到链尾，并输出插入后的链表。

13、编写栈的压栈push、弹栈pop函数，从键盘输入一组数据，逐个元素压入堆栈，然后再逐个从栈中弹出它们并输出。

14、编写栈的压栈push、弹栈pop函数，用它判别（）的匹配问题。

15、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树中序遍历的结果。

16、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树先序遍历的结果。

17、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树后序遍历的结果。

18、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树的总结点数。

19、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树叶子结点数。

20、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出此二叉树的高度。

21、给出一个无向图的邻接矩阵，输出各个顶点的度。

22、给出一个有向图的邻接矩阵，输出各个顶点的入度与出度。

23、输入一个有序序列，利用折半查找来查找一个数是否在序列中，如在，则输出其位置，否则输出“NO”。

24、用插入排序方法对一组数据进行排序，并输出每趟排序的结果。

25、用选择排序方法对一组数据进行排序，并输出每趟排序的结果。

26、用希尔（SHELL）排序方法对一组数据进行排序，并输出每趟排序的结果。

27、用快速排序方法对一组数据进行排序，并输出每趟排序的结果。．

答案：

1. #include

#include

#define N 5

#define NULL 0

//链表的存储结构

typedef struct LNode

{

}LNode,*list;

//顺序创建链表

void creatList(list &l,int n)

{

 开辟头结点

 指针p指向头结点

  新的结点

  的下一个结点指向新开辟的结点q

  将p指针指向q

}

//归并排序

void mergeList(list &la,list &lb,list &lc)  

{  //将已经排好序的la,lb中的数重新排列成有序（非递减）

 默认将la做为lc的头结点（lb亦可）

 让pc接到数据小的结点上，直到pa,pb两者有一指向空结点

 如果最后la有剩余结点，即将其直接加入到lc中，反之将lb的剩余结点加到lc中

}

void printList(list l)

{

}

void main()

{

 创建两个含%d个元素的链表，请输入：\\n",N);

}

2. #include

#include

#define N 5

#define NULL 0

#define OK 1

#define ERROR 0

//链表的存储结构

typedef struct LNode

{

}LNode,*list;

//创建链表

void creatList(list &l,int n)

{

}

//判断元素e是否在链表中

int inList(list l,int e)

{

        return OK;   //发现在里面，返回真值

  否则指针后移,继续找

  未找到，返回假值（没有执行return OK;语句）

}

//插入元素

void insertList(list &l,int &e)

{

 为新插入的元素开辟一个存储空间的指针，s为p前一个指针，方便插入

  发现要插入的元素e比后面的小,开辟空间，并将e放入空间的数据域中

   找到p前的一个指针

   画图好好理解

   s->next=q; // q--->

}

//输出链表

void printList(list l)

{

}

void main()

{

 创建%d个元素的链表，请输入%d个元素：\\n",N,N);

 请输入要判断的元素：");

}

3. #include

#include

#define N 5

#define NULL 0

#define OK 1

#define ERROR 0

//链表的存储结构

typedef struct LNode

{

}LNode,*list;

//创建链表

void creatList(list &l,int n)

{

}

//判断元素e是否在链表中

int insertDeleteList(list l,int e)

{

   找到p前一个结点，方便删除操作

   删除结点p

  发现在里面，返回真值

  否则指针后移,继续找

  未找到，返回假值（没有执行return OK;语句）

}

//输出链表

void printList(list l)

{

}

void main()

{

 创建%d个元素的链表，请输入%d个元素：\\n",N,N);

 请输入要判断的元素");

}

4. #include

#include

#define N 5

#define NULL 0

#define OK 1

#define ERROR 0

//链表的存储结构

typedef struct LNode

{

}LNode,*list;

//创建链表

void creatList(list &l,int n)

{

}

//链表排序

void sortList(list &l)

{

 标记排序的轮数

 用于交换结点中的数据

  每次比较从首结点开始

   发现前一个比后一个大，交换数据

   相邻间下一个比较

  下一轮比较

}

//输出链表

void printList(list l)

{

}

void main()

{

 创建%d个元素的链表，请输入%d个元素：\\n",N,N);

}

5. #include

#include

#define N 5

#define NULL 0

#define OK 1

#define ERROR 0

//链表的存储结构

typedef struct LNode

{

}LNode,*list;

//创建链表

void creatList(list &l,int n)

{

 头结点也添加元素，方便输出

 让最后一个p->next指针指向头结点，构成循环链表

}

//输出链表

void printList(list l,int pos)

{

 找到指定位置的前一个位置

  如果指定位置为1，即按原样输出

  不然，p先移到指定的位置，输出其数据

  结束条件（p移到的下一个位置不是q，即不是最初的p,完成循环输出）

}

void main()

{

 创建%d个元素的循环链表，请输入%d个元素：\\n",N,N);

 请指明从第几个位置输出循环链表中的元素：");

  输入的位置不存在，请重新输入... ");

}

11#include

#include

#define N 5

#define NULL 0

#define OK 1

#define ERROR 0

//链表的存储结构

typedef struct LNode

{

}LNode,*list;

//创建链表

void creatList(list &l,int n)

{

 头结点也添加元素，方便输出

 让最后一个p->next指针指向头结点，构成循环链表

}

//输出链表

void printList(list l,int pos)

{

 找到指定位置的前一个位置

  如果指定位置为1，即按原样输出

  不然，p先移到指定的位置，输出其数据

  结束条件（p移到的下一个位置不是q，即不是最初的p,完成循环输出）

}

void main()

{

 创建%d个元素的循环链表，请输入%d个元素：\\n",N,N);

 请指明从第几个位置输出循环链表中的元素：");

  输入的位置不存在，请重新输入... ");

}

12#include

#include

#define N 5

#define NULL 0

#define OK 1

#define ERROR 0

//链表的存储结构

typedef struct LNode

{

}LNode,*list;

//创建链表

void creatList(list &l,int n)

{

}

//判断元素e是否在链表中

int inList(list l,int e)

{

        return OK;   //发现在里面，返回真值

  否则指针后移,继续找

 没有执行return OK;语句,说明未找到

 找到链尾

 为链尾重新开辟空间

 接到链尾

 未找到，返回假值

}

//输出链表

void printList(list l)

{

}

void main()

{

 创建%d个元素的链表，请输入%d个元素：\\n",N,N);

 请输入要判断的元素：");

}

13#include

#include

#define OK 1

#define Error 0

#define NULL 0

#define maxSize 100

//栈的存储结构

typedef struct 

{

}stack;

//栈的初始化（顺序存储）

int initStack(stack &s)

{开辟maxSize大小的空间，base和top都指向基地址,同时判断是否开辟成功，不成功返回0

 栈的大小为maxSize

}

//进栈操作

int push(stack &s,int e)

{

 先将元素e赋值给s.top所指的存储空间

 指针上移

}

//出栈操作

int pop(stack &s,int &e)

{

 如果栈为空，返回0

 指针先后移

 将其所指的元素值赋给e

} 

void main()

{

 请输入要创建栈的元素的个数：");

}

14#include

#include

#include

#include

#define stackincrement 8

#define OK 1

#define Error 0

#define NULL 0

#define maxSize 100

//栈的存储结构

typedef struct 

{

 由于要存放括号，所以为char类型

}stack;

//栈的初始化（顺序存储）

int initStack(stack &s)

{注意开辟的空间为char类型

 栈的大小为maxSize

}

//进栈操作

int push(stack &s,int e)

{

 先将元素e赋值给s.top所指的存储空间

 指针上移

}

int isEmpty(stack s)

{

}

//出栈操作

char pop(stack &s,char &e)

{

 如果栈为空，返回0

 指针先后移

 将其所指的元素值赋给e

} 

//括号匹配

int match()

{

 用于标记，如果匹配，值为1，否则为0

 先将所有输入的括号存放在数组ch[]中  

 数组的长度，不包括'\\n'

 先将第一个括号压栈

 如果第一个压入的是右括号，则肯定不匹配，flag=0

  弹出先前压入的元素，将后继输入的括号与先前压入的比较

 左右小括号与左右大括号的ASCII码都相差1，左右中括号相差2，如果不满足，则不匹配，直接退出循环

     else   push(s,ch[i]);       //输入的是左括号，直接压入

    if(!isEmpty(s)) flag=0;         //通过不断的压栈和弹栈，如果最后栈不为空，则肯定是左括号多于右括号，不匹配

}

void main()

{

 判断输入的各种括号是否匹配：\\n");

 括号匹配正确 ^_^\\n");

 括号匹配错误 *.*\\n");

}

15#include "stdio.h"

#include "stdlib.h"

#define stackinitsize 100

#define OK 1

#define ERROR 0

//二叉树的二叉链表存储结构

typedef struct  BiTNode{ 

     int   data;

     struct  BiTNode  *lchild,*rchild;   //左右孩子指针

int  CreateBiTree(BiTree &T){

 按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。

 构造二叉链表表示的二叉树T.

 生成根结点

 构造左子树

 构造右子树

int  PrintElement(int e)

       {   //输出元素e的值

           printf("%c",e);        

int  InOrderTraverse(BiTree T,int(*Visit)(int e))

 采用二叉链表存储结构，visit是对数据元素操作的应用函数，

 中序遍历二叉树T的递归算法，对每个数据元素调用函数visit。

 调用实例：  InOrderTraverse(T,printElement);

void main()

{

  BiTree t;

  printf("请按先序遍历输入二叉树（当左右子树为空时用空格输入）\\n");

  CreateBiTree(t);

  printf("该二叉树的中序遍历为：\\n");

  InOrderTraverse(t,PrintElement);

  printf("\\n");

}

16#include "stdio.h"

#include "stdlib.h"

#define stackinitsize 100

#define OK 1

#define ERROR 0

//二叉树的二叉链表存储结构

typedef struct  BiTNode{ 

     int   data;

     struct  BiTNode  *lchild,*rchild;   //左右孩子指针

int  CreateBiTree(BiTree &T){

 按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。

 构造二叉链表表示的二叉树T.

 生成根结点

 构造左子树

 构造右子树

int  PrintElement(int e)

       {   //输出元素e的值

           printf("%c",e);        

int  PreOrderTraverse(BiTree T,int(*Visit)(int e))

 采用二叉链表存储结构，visit是对数据元素操作的应用函数，

 先序遍历二叉树T的递归算法，对每个数据元素调用函数visit。

 调用实例：  PreOrderTraverse(T,printElement);

void main()

{

  BiTree t;

  printf("请按先序遍历输入二叉树（当左右子树为空时用空格输入）\\n");

  CreateBiTree(t);

  printf("该二叉树的先序遍历为：\\n");

  PreOrderTraverse(t,PrintElement);

  printf("\\n");

}

17#include "stdio.h"

#include "stdlib.h"

#define stackinitsize 100

#define OK 1

#define ERROR 0

//二叉树的二叉链表存储结构

typedef struct  BiTNode{ 

     int   data;

     struct  BiTNode  *lchild,*rchild;   //左右孩子指针

int  CreateBiTree(BiTree &T){

 按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。

 构造二叉链表表示的二叉树T.

 生成根结点

 构造左子树

 构造右子树

int  PrintElement(int e)

       {   //输出元素e的值

           printf("%c",e);        

int  PostOrderTraverse(BiTree T,int(*Visit)(int e))

 采用二叉链表存储结构，visit是对数据元素操作的应用函数，

 后序遍历二叉树T的递归算法，对每个数据元素调用函数visit。

 调用实例：  PostOrderTraverse(T,printElement);

void main()

{

  BiTree t;

  printf("请按先序遍历输入二叉树（当左右子树为空时用空格输入）\\n");

  CreateBiTree(t);

  printf("该二叉树的后序遍历为：\\n");

  PostOrderTraverse(t,PrintElement);

  printf("\\n");

}

18#include "stdio.h"

#include "stdlib.h"

#define stackinitsize 100

#define OK 1

#define ERROR 0

//#define NULL 0

static int count=0;

//二叉树的二叉链表存储结构

typedef struct  BiTNode{ 

     int   data;

     struct  BiTNode  *lchild,*rchild;   //左右孩子指针

int  CreateBiTree(BiTree &T){

 按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。

 构造二叉链表表示的二叉树T.

 生成根结点

 构造左子树

 构造右子树

int  PrintElement(int e)

       {   //记录遍历结点数

int  PreOrderTraverse(BiTree T,int(*Visit)(int e))

 采用二叉链表存储结构，visit是对数据元素操作的应用函数，

void main()

{

  BiTree t;

  printf("请按先序遍历输入二叉树（当左右子树为空时用空格输入）\\n");

  CreateBiTree(t);

  printf("该二叉树的总结点数为: ");

  PreOrderTraverse(t,PrintElement);

  printf("%d\\n",count);

}

19#include "stdio.h"

#include "stdlib.h"

#define stackinitsize 100

#define OK 1

#define ERROR 0

static int count=0;

//二叉树的二叉链表存储结构

typedef struct  BiTNode{ 

     int   data;

     struct  BiTNode  *lchild,*rchild;   //左右孩子指针

int  CreateBiTree(BiTree &T){

 按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。

 构造二叉链表表示的二叉树T.

 生成根结点

 构造左子树

 构造右子树

int  PrintElement(int e)

    {   //判断叶子结点的个数，此函数可不做操作

int  PreOrderTraverse(BiTree T,int(*Visit)(int e))

 采用二叉链表存储结构，visit是对数据元素操作的应用函数，

 先序遍历二叉树T的递归算法，对每个数据元素调用函数visit。

 调用实例：  PreOrderTraverse(T,printElement);

    当左右结点都为空时，即是叶子结点

void main()

{

  BiTree t;

  printf("请按先序遍历输入二叉树（当左右子树为空时用空格输入）\\n");

  CreateBiTree(t);

  PreOrderTraverse(t,PrintElement);

  printf("该二叉树的叶子结点的个数为: %d\\n",count);

}

20#include "stdio.h"

#include "stdlib.h"

#define stackinitsize 100

#define OK 1

#define ERROR 0

//二叉树的二叉链表存储结构

typedef struct  BiTNode{ 

     int   data;

     struct  BiTNode  *lchild,*rchild;   //左右孩子指针

int  CreateBiTree(BiTree &T){

 按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。

 构造二叉链表表示的二叉树T.

 生成根结点

 构造左子树

 构造右子树

//首先分析二叉树的深度（高度）和它的左、右子树深度之间的关系。

//从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。

//由此，需先分别求得左、右子树深度,返回其最大值，然后加 1 。

int GetDepth(BiTree T){

 if(T) 

{

int depthLeft = GetDepth( T->lchild );

int depthRight= GetDepth( T->rchild );

return (depthLeft>depthRight?depthLeft:depthRight)+1;

else return ERROR;

}

void main()

{

  BiTree t;

  printf("请按先序遍历输入二叉树（当左右子树为空时用空格输入）\\n");

  CreateBiTree(t);

  printf("该二叉树的高度为: %d\\n",GetDepth(t));

}

21. // 21、给出一个无向图的邻接矩阵，输出各个顶点的度。

#include

#include

#include

using namespace std;

const int max=50;

typedef char type;

typedef struct 

{

 顶点个数、边数 

}graph;

int main()

{

 无向邻接矩阵为:"< 

  顶点"<}

22//22、给出一个有向图的邻接矩阵，输出各个顶点的入度与出度。

#include

#include

#include

using namespace std;

const int max=50;

typedef char type;

typedef struct 

{

 顶点个数、边数 

}graph;

int main()

{

 有向邻接矩阵为:"< 

  顶点"<}

23//23、输入一个有序序列，利用折半查找来查找一个数是否在序列中，

//如在，则输出其位置，否则输出"NO"。

#include

#include

#include

using namespace std;

typedef int type; 

struct  sqlist

{

};

int init_sqlist(sqlist &L,int n)

{

}

int binary_search(sqlist L,type n)

{

}

int main()

{

 请输入有序表长度:"< 请按从小到大的顺序输入"< 请输入要查找的数"<  在有序表中的位置是"<  不在有序表中"<}

24//24、用插入排序方法对一组数据进行排序，并输出每趟排序的结果。

#include

#include

#include

using namespace std;

typedef int type; 

struct  sqlist

{

};

int init_sqlist(sqlist &L,int n)

{

}

void straight_insert_sort(sqlist &L)

{

  第"< 

}

void binary_insert_sort(sqlist &L)

{

}

int main()

{

 请输入序列长度"< 请输入"< 

}

25//25、用选择排序方法对一组数据进行排序，并输出每趟排序的结果。

#include

#include

#include

using namespace std;

typedef int type; 

struct  sqlist

{

};

int init_sqlist(sqlist &L,int n)

{

}

void select_sort(sqlist &L)

{

  第"< 

}

int main()

{

 请输入元素个数:"< 请输入"<}

26//26、用希尔（SHELL）排序方法对一组数据进行排序，并输出每趟排序的结果。

//掌握得不是很好

#include

#include

#include

using namespace std;

typedef int type; 

struct  sqlist

{

};

int init_sqlist(sqlist &L,int n)

{

}

void Shell_Sort(sqlist &L,int dlta[],int t)

{

 第"<}

int main()

{

}

/*

10

49 38 65 97 76 13 27 49 55 04

*/

27. //27、用快速排序方法对一组数据进行排序，并输出每趟排序的结果。．

#include

#include

#include

using namespace std;

typedef int type; 

struct  sqlist

{

};

int init_sqlist(sqlist &L,int n)

{

}

void Quick_Sort(sqlist &L,int low,int high)

{

}

int main()

{

}