日期:2014-05-18  浏览次数:21023 次

一些算法的问题,求解各位高人,无比感谢!!
我学C#没多久,逛了很多书店,没看到有合适的C#数据结构的书,遇到一些问题,求助各位高手。在此先谢过各位老师了。 问题如下: (能答一题,我都非常感激了)

1.有数据类型为整型的顺序表La和Lb,其数据元素均按从小到大的升序排列,编写一个算法将它们合并成一个表Lc,要求Lc中数据元素也按

升序排列 

2.已知一个存储整数的单链表Ha,试构造单链表Hb,要求单链表Hb中只包含单链表Ha中所有值不相同的结点


3.将一个十进制数N转换为八进制数(应用栈)


4.编程判断一个字符串是否是回文。回文是指一个字符序列以中间字符为基准两边字符完全相同,如字符序列“ACBDEDBCA”是回文


5.曹操南下攻打刘备,刘备派关羽守锦州,关羽派张飞去守城门。刘备又派诸葛亮去向孙权求援。孙权派兵攻打曹操! 请画出UML图 


6.已知:s=”(XYZ)+*”,t=”(X+Z)*Y”,试利用连接、求子串和替换等基本运算,将s转化为t


7.编写算法,在二叉树中查找值为value的结点

8.统计出二叉树中叶子结点的数目


9.已知结点的后序序列和中序序列如下:
后序序列:A B C D E F G
中序序列:A C B G D F E
请构造该二叉树。


10.编写算法,判断给定的二叉树是否为完全二叉树


11.假设有10000个1~10000的互不相同的数构成一无序集合。试设计一个算法实现排序,要求以尽可能少的比较次数和移动次数实现


12.一个线性表中的数据元素为正整数或负整数。试设计一算法,将正整数和负整数分开,使线性表的前一部分的数据元素为负整数,后一

部分的数据元素为正整数。不要求对这些数据元素有序,但要求尽量减少交换的次数


13.编写一个算法,利用折半查找算法在一个有序表中插入一个记录(关键码为x),并保持表的有序性

14.已知一个长度为12的记录的关键码序列为(37,7,32,29,20,28,22,15,17,23,1,9),要求: (1)按各记录的顺序构造一棵

二叉排序树。 (2)在(1)的基础上插入关键码为41的记录,画出对应的二叉排序树。 (3)在(2)的基础上删除关键码为29的记录,画

出对应的二叉排序树??

15.有n个结点的二叉排序树共有多少种不同的形态? 

16.以顺序表作为静态查找表实现顺序查找算法,并将监视哨设在顺序表的高端

17.在哈希表的存储结构中,发生冲突的可能性与哪些因素有关?为什么?


------解决方案--------------------
其实都是一些很基本的算法,

比如说这个题,
12.一个线性表中的数据元素为正整数或负整数。试设计一算法,将正整数和负整数分开,使线性表的前一部分的数据元素为负整数,后一 
部分的数据元素为正整数。不要求对这些数据元素有序,但要求尽量减少交换的次数 

我说两种算法思想,

1. 其实可以用空间换时间了,额外申请两个数组即可,顺序扫描一下线性表,时间复杂度为O(N),一个数组放负数,一个数组放正数,最后把两个数组重新写回到原来的线性表。
2. 顺序扫描线性表a[N],使用索引值 i,遇到负数不管并且++i,遇到正数时,使用另外一个索引值j,从后面向前依次扫描,遇到整数不管并且--j,遇到负数后,a[j] 与 a[i] 交换.
然后继续在从i+1 开始向前扫描即可,直到i == j,跳出循环



最后向楼主推荐一本书 <算法导论>,基本覆盖了主要的算法问题

English Edition is <Introdution to algorithms> the first writer is 'Thomas H.Cormen