搜索
《数据结构》上机练习题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.#includestdio.h#includestdlib.h#defineN5#defineNULL0//链表的存储结构typedefstructLNode{intdata;structLNode*next;}LNode,*list;//顺序创建链表voidcreatList(list&l,intn){inti;listp,q;l=(list)malloc(sizeof(LNode));//开辟头结点p=l;//指针p指向头结点for(i=0;in;i++){q=(list)malloc(sizeof(LNode));//新的结点scanf(%d,&q-data);p-next=q;//p的下一个结点指向新开辟的结点qp=q;//将p指针指向q}p-next=NULL;}//归并排序voidmergeList(list&la,list&lb,list&lc){//将已经排好序的la,lb中的数重新排列成有序（非递减）listpa,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);}voidprintList(listl){listp;p=l-next;while(p){printf(%d,p-data);p=p-next;}}voidmain(){listla,lb,lc;printf(创建两个含%d个元素的链表，请输入：\n,N);creatList(la,N);creatList(lb,N);mergeList(la,lb,lc);printList(lc);}2.#includestdio.h#includestdlib.h#defineN5#defineNULL0#defineOK1#defineERROR0//链表的存储结构typedefstructLNode{intdata;structLNode*next;}LNode,*list;//创建链表voidcreatList(list&l,intn){listp,q;l=(list)malloc(sizeof(LNode));p=l;for(inti=0;in;i++){q=(list)malloc(sizeof(LNode));scanf(%d,&q-data);p-next=q;p=q;}p-next=NULL;}//判断元素e是否在链表中intinList(listl,inte){listp;p=l-next;while(p){if(p-data==e)returnOK;//发现在里面，返回真值p=p-next;//否则指针后移,继续找}returnERROR;//未找到，返回假值（没有执行returnOK;语句）}//插入元素voidinsertList(list&l,int&e){listp,q,s;//q为新插入的元素开辟一个存储空间的指针，s为p前一个指针，方便插入p=l-next;s=l;while(p){if(e=p-data){//发现要插入的元素e比后面的小,开辟空间，并将e放入空间的数据域中q=(list)malloc(sizeof(LNode));q-data=e;while(s-next!=p)s=s-next;//找到p前的一个指针q-next=p;//画图好好理解---s---p---s-next=q;//q---break;}p=p-next;}}//输出链表voidprintList(listl){listp;p=l-next;while(p){printf(%d,p-data);p=p-next;}}voidmain(){listl;inte;printf(创建%d个元素的链表，请输入%d个元素：\n,N,N);creatList(l,N);printf(请输入要判断的元素：);scanf(%d,&e);if(inList(l,e))printf(YES);else{insertList(l,e);printList(l);}}3.#includestdio.h#includestdlib.h#defineN5#defineNULL0#defineOK1#defineERROR0//链表的存储结构typedefstructLNode{intdata;structLNode*next;}LNode,*list;//创建链表voidcreatList(list&l,intn){listp,q;l=(list)malloc(sizeof(LNode));p=l;for(inti=0;in;i++){q=(list)malloc(sizeof(LNode));scanf(%d,&q-data);p-next=q;p=q;}p-next=NULL;}//判断元素e是否在链表中intinsertDeleteList(listl,inte){listp,q;p=l-next;q=l;while(p){if(p-data==e){while(q-next!=p)q=q-next;//找到p前一个结点，方便删除操作q-next=p-next;//删除结点pfree(p);returnOK;}//发现在里面，返回真值p=p-next;//否则指针后移,继续找}returnERROR;//未找到，返回假值（没有执行returnOK;语句）}//输出链表voidprintList(listl){listp;p=l-next;while(p){printf(%d,p-data);p=p-next;}}voidmain(){listl;inte;printf(创建%d个元素的链表，请输入%d个元素：\n,N,N);creatList(l,N);printf(请输入要判断的元素);scanf(%d,&e);if(!insertDeleteList(l,e))printf(NO);elseprintList(l);}4.#includestdio.h#includestdlib.h#defineN5#defineNULL0#defineOK1#defineERROR0//链表的存储结构typedefstructLNode{intdata;structLNode*next;}LNode,*list;//创建链表voidcreatList(list&l,intn){listp,q;l=(list)malloc(sizeof(LNode));p=l;for(inti=0;in;i++){q=(list)malloc(sizeof(LNode));scanf(%d,&q-data);p-next=q;p=q;}p-next=NULL;}//链表排序voidsortList(list&l){listp,q,r;//p标记排序的轮数intchang;//用于交换结点中的数据p=l-next;while(p-next!=NULL){q=l-next;//每次比较从首结点开始while(q-next!=NULL){r=q-next;if(q-datar-data)//发现前一个比后一个大，交换数据{chang=q-data;q-data=r-data;r-data=chang;}q=q-next;//相邻间下一个比较}p=p-next;//下一轮比较}}//输出链表voidprintList(listl){listp;p=l-next;while(p){printf(%d,p-data);p=p-next;}}voidmain(){listl;printf(创建%d个元素的链表，请输入%d个元素：\n,N,N);creatList(l,N);sortList(l);printList(l);}5.#includestdio.h#includestdlib.h#defineN5#defineNULL0#defineOK1#defineERROR0//链表的存储结构typedefstructLNode{intdata;structLNode*next;}LNode,*list;//创建链表voidcreatList(list&l,intn){listp,q;l=(list)malloc(sizeof(LNode));scanf(%d,&l-data);//头结点也添加元素，方便输出p=l;for(inti=1;in;i++){q=(list)malloc(sizeof(LNode));scanf(%d,&q-data);p-next=q;p=q;}p-next=l;//让最后一个p-next指针指向头结点，构成循环链表}//输出链表voidp