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

v .. . ..

《数据结构》上机练习题

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

. . . 资 料. .

v .. . ..

//链表的存储结构 typedef struct LNode { int data; struct LNode *next; }LNode,*list;

//顺序创建链表

void creatList(list &l,int n) { int i; list p,q; l=(list)malloc(sizeof(LNode)); //开辟头结点 p=l; //指针p指向头结点 for(i=0;inext=q; //p的下一个结点指向新开辟的结点q p=q; //将p指针指向q } p->next=NULL; }

//归并排序

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

{ //将已经排好序的la,lb中的数重新排列成有序（非递减） list pa,pb,pc; pa=la->next;pb=lb->next; lc=pc=la; //默认将la做为lc的头结点（lb亦可） while(pa&&pb) { //让pc接到数据小的结点上，直到pa,pb两者有一指向空结点 if(pa->data<=pb->data) { pc->next=pa;pc=pa;pa=pa->next; } else { pc->next=pb;pc=pb;pb=pb->next; } } pc->next=pa?pa:pb; //如果最后la有剩余结点，即将其直接加入到lc中，反之将lb的剩余结点加到lc中 free(lb); }

. . . 资 料. .

v .. . ..

void printList(list l) { list p; p=l->next; while(p) { printf(\ }

void main() { list la,lb,lc; printf(\创建两个含%d个元素的链表，请输入：\\n\ creatList(la,N); creatList(lb,N); mergeList(la,lb,lc); printList(lc); }

2. #include #include #define N 5 #define NULL 0 #define OK 1 #define ERROR 0 //链表的存储结构 typedef struct LNode { int data; struct LNode *next; }LNode,*list;

//创建链表

void creatList(list &l,int n) { list p,q; l=(list)malloc(sizeof(LNode)); p=l; for(int i=0;inext=q;

. . . 资 料. .