数据结构上机作业

1. 已知输入x、y、z三个不相等的整数，试设计一个算法，使这三个数按从小到大的顺序进行排序并输出，并考虑此算法的比较次数和元素的移动次数。

2. 猴子吃桃子问题。猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个；第二天早上又将剩下的桃子吃掉了一半，又多吃了一个；以后每天早上都吃了前一天剩下的一半加一个，到第十天早上再想吃时，发现只剩下一个桃子了。

求第一天共摘了多少个桃子。

3. 给定一个数组，要求在此数组中插入一个元素、删除一个元素，并显示每次操作之后的输出。

4. 验证课本p11程序2-1和p13程序2-2，体会顺序存储结构下线性表的插入和删除操作。

5. 有顺序存储结构下的线性表a和b，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表c，要求c的元素也是从小到大升序排列。如：

线性表a为

线性表b为

合并之后的线性表c为

6. 试写出在顺序存储结构下逆转线性表的算法，要求使用最少的附加空间。

7. 试编程实现，在一个有序线性表中（顺序存储结构）插入一个元素后仍然是有序线性表。

8. 设顺序存储结构下线性表中有多个0元，编程实现所有非零元依次移到线性表的前端。

9. 验证课本p16程序2-3和p17程序2-4，体会线性链表的建立和查找操作。

10. 思考题：将程序2-4稍作修改，改为“在单链表中查找指定结点的前一个结点”，为将来的插入和删除操作做准备。

11. 试编写一个在单链表中数据域值为a的结点之后，插入一个新结点的算法。若原链表中无数据域值为a的结点，则把新结点插入到表尾。设新结点数据域值为x。

12. 已知线性单链表，试编写一个删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法。

13. 设有两个有序线性单链表，头指针分别为ah和bh。试写出将这两个有序线性单链表合并为一个头指针为ch的有序线性单链表的算法。

14. 试写出逆转线性单链表的算法，要求修改各结点的指针域使其倒置。（注意：不要修改结点的数据域！）

15. 设有一个线性单链表，其结点值均为整数（正整数，0，负整数），且按绝对值从小到大链接。试写出一个算法，将此线性单链表中的结点按值从小到大链接。

16. （选做）设有一个线性单链表，其结点值均为正整数，且按值从大到小链接。试写出一个算法，将该线性单链表分解为两个线性单链表，其中一个链表中的结点值均为奇数，而另一个链表中的结点值均为偶数，且这两个链表均按值从小到大链接。

17. （选做）设有一个线性单链表，其结点值均为正整数，试写出一个算法，反复找出链表中结点值最小的结点，并输出该值，然后将该结点从链表中删除，直到链表空为止。

18. （选做）试写出双向链表插入与删除的算法。

19. 验证《数据结构实训与习题解析》p66.“栈的应用－表达式求值问题”的算法，体会栈的结构特性及其典型操作。

20. 编写算法，实现将一个非负十进制整数转换成二进制。

21. 编写算法，求一个具有maxqsize个单元的循环队列中元素的个数。

22. （选做）假设一个算术表达式中包含圆括弧、方括弧和花括弧3种类型的括弧，编写一个判别表达式中括弧是否正确配对的函数。以字符“#”作为算术表达式的结束符。

23. 建立一棵二叉树，如下图所示：

并对此二叉树进行先序、中序和后序遍历，输出其先序、中序和后序遍历序列。

24. 课本p129习题5.11和5.12。

25. 验证课本p177程序7-1，体会顺序查找的算法思想。

26. 验证课本p179程序7-2，体会二分法查找的算法思想。

27. 课本p194“上机实验”实验7.1 分块查找。

28. 给定序列（56，78，34，45，85，45，36，91，84，78），编写程序构造二叉排序树，在二叉排序树上查找结点36，并输出查找成功时的比较次数。若查找结点55，需要比较多少次？

并输出比较次数。

29. 利用直接插入排序算法，将序列（43，86，55，67，23，90，13，79，86）进行排序，并输出排序好的序列。

30. 利用快速排序算法，将序列（43，86，55，67，23，90，13，79，86）进行排序，要求输出第一趟排序结果和最后排序好的序列。