数据结构 上机作业.doc

《数据结构 上机作业.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.已知输入x、y、z三个不相等的整数，试设计一个算法，使这三个数按从小到大的顺序进行排序并输出，并考虑此算法的比较次数和元素的移动次数。2.猴子吃桃子问题。猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个；第二天早上又将剩下的桃子吃掉了一半，又多吃了一个；以后每天早上都吃了前一天剩下的一半加一个，到第十天早上再想吃时，发现只剩下一个桃子了。求第一天共摘了多少个桃子。3.给定一个数组，要求在此数组中插入一个元素、删除一个元素，并显示每次操作之后的输出。4.验证课本P11程序2-1和P13程序2-2，体会顺序存储结构下线性表的插入和删除操作。5.有顺序存储结构下的线性表A和B

2、，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大升序排列。如：线性表A为：1、5、9、12、18、25线性表B为：2、3、6、10、16、19、20、26、28、30、35合并之后的线性表C为：1、2、3、5、6、9、10、12、16、18、19、20、25、26、28、30、356.试写出在顺序存储结构下逆转线性表的算法，要求使用最少的附加空间。7.试编程实现，在一个有序线性表中（顺序存储结构）插入一个元素后仍然是有序线性表。8.设顺序存储结构下线性表中有多个0元，编程实现所有非零元依次移到线性表的前端。9.验证课本P16程序2-3和P17

3、程序2-4，体会线性链表的建立和查找操作。10.思考题：将程序2-4稍作修改，改为“在单链表中查找指定结点的前一个结点”，为将来的插入和删除操作做准备。11.试编写一个在单链表中数据域值为a的结点之后，插入一个新结点的算法。若原链表中无数据域值为a的结点，则把新结点插入到表尾。设新结点数据域值为x。12.已知线性单链表，试编写一个删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法。13.设有两个有序线性单链表，头指针分别为AH和BH。试写出将这两个有序线性单链表合并为一个头指针为CH的有序线性单链表的算法。14.试写出逆转线性单链表的算法，要求修改各结点的指针域使其

4、倒置。（注意：不要修改结点的数据域！）15.设有一个线性单链表，其结点值均为整数（正整数，0，负整数），且按绝对值从小到大链接。试写出一个算法，将此线性单链表中的结点按值从小到大链接。16.（选做）设有一个线性单链表，其结点值均为正整数，且按值从大到小链接。试写出一个算法，将该线性单链表分解为两个线性单链表，其中一个链表中的结点值均为奇数，而另一个链表中的结点值均为偶数，且这两个链表均按值从小到大链接。17.（选做）设有一个线性单链表，其结点值均为正整数，试写出一个算法，反复找出链表中结点值最小的结点，并输出该值，然后将该结点从链表中删除，直到链表空为止。18.（选做）试写出双向链表插入

5、与删除的算法。19.验证《数据结构实训与习题解析》P66.“栈的应用－表达式求值问题”的算法，体会栈的结构特性及其典型操作。20.编写算法，实现将一个非负十进制整数转换成二进制。21.编写算法，求一个具有MAXQSIZE个单元的循环队列中元素的个数。22.（选做）假设一个算术表达式中包含圆括弧、方括弧和花括弧3种类型的括弧，编写一个判别表达式中括弧是否正确配对的函数。以字符“#”作为算术表达式的结束符。23.建立一棵二叉树，如下图所示：ABCDFGIEHJK并对此二叉树进行先序、中序和后序遍历，输出其先序、中序和后序遍历序列。7.课本P129习题5.11和5.12。8.验证课本P177程

6、序7-1，体会顺序查找的算法思想。9.验证课本P179程序7-2，体会二分法查找的算法思想。10.课本P194“上机实验”实验7.1分块查找。11.给定序列（56，78，34，45，85，45，36，91，84，78），编写程序构造二叉排序树，在二叉排序树上查找结点36，并输出查找成功时的比较次数。若查找结点55，需要比较多少次？并输出比较次数。12.利用直接插入排序算法，将序列（43，86，55，67，23，90，13，79，86）进行排序，并输出排序好的序列。13.利用快速排序算法，将序列（43，86，55，67，23，90，13，79，86）进行排序，要求输出第一趟排序结果和最后排

7、序好的序列。