【艾琪出品】-【数据结构课程设计】测试题系列四，二叉树的建立与遍历、实现两个链表的合并、建立通信网络、任意长的整数加减法运算

痛定思痛。 2023-10-09 12:27 8阅读 0赞

一.课程设计题目  
  
1. 任意长的整数加减法运算  
设计算法，实现一个任意长的整数进行加法、减法运算的演示程序。例如：1234，5123，4512，3451，2345与-1111，1111，1111，1111，1111的加法结果为：0123，4012，3401，2340，1234。基本要求如下：  
（1） 利用链表实现长整数的存储，每个节点含一个整型变量；  
（2） 整型变量的范围：-（2^15 -1）~（2^15 -1）；  
（3） 输入与输出形式每四位一组，组间用逗号分隔开。如：1986,8213,1935,2736,3299；  
（4） 界面友好，每步给出适当的操作提示，并且系统具有一定的容错能力。  
至少给出下面的测试数据：  
（1）0； 0  
（2）-2345,6789； -7654,3211  
（3）-9999,9999； 1,0000,0000,0000  
（4）1,0001,0001； -1,0001,0001  
（5）1,0001,0001； -1,0001,0000  
（6）-9999,9999,9999； -9999,9999,9999  
（7）1,0000,9999,9999； 1  
  
2. 建立通信网络  
在n个城市建设通信网络，只需架设n-1条线路即可。设计算法，求出如果以最低的经济代价建设这个通信网络。要求如下：  
（1） 至少包含10个城市；  
（2） 城市数n由键盘录入；  
（3） 城市坐标由随机函数产生小于100的整数；  
（4） 输出生成树中各条边以及它们的权值；

3. 实现两个链表的合并  
基本功能要求：  
（1）建立两个链表A和B，链表元素个数分别为m和n个。  
（2）假设元素分别为(x1,x2,…xm)，和(y1,y2, …yn)。把它们合并成一个线性表C，使得：  
当m>=n时，C=x1,y1,x2,y2,…xn,yn,…,xm  
当n>m时，C=y1,x1,y2,x2,…ym,xm,…,yn  
输出线性表C  
（3）用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。  
测试数据：  
（1） A表（30，41，15，12，56，80）  
B表（23，56，78，23，12，33，79，90，55）  
（2） A表（30，41，15，12，56，80，23，12，34）  
B表（23，56，78，23，12）

4. 二叉树的建立与遍历  
\[问题描述\]  
建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。  
\[基本要求\]  
从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。  
\[测试数据\]  
ABCффDEфGффFффф（其中ф表示空格字符）  
则输出结果为 先序：ABCDEGF  
中序：CBEGDFA  
后序：CGBFDBA