一、
1. 高度为k，且有_____个结点的二叉树称为_____二叉树。 【答案】2k-1，满
2. 线性表的顺序映象就是逻辑上_____的两个数据元素，在物理存储上赋予_____位置的一种存储分配方式。 【答案】相连，相邻
3. 线性表的链式存储结构是一种_____存取的存储结构。 【答案】顺序
4. Hash表查找要研究的两个主要问题分别是_____和_____。 【答案】均匀性，冲突的解决
5. 数据元素之间的相互关系由一组运算和规则描述的数据元素的集合，称为数据的_____结构。 【答案】逻辑
6. 对于由n个数据元素构成的序列实施冒泡排序时，最少的比较次数是_____。冒泡排序的结束条件是_____。 【答案】 n-1，刚做完的一趟排序没有交换元素
二、
1. 在一棵包含n个结点的顺序二叉树上,最远的两个结点有多远_____。 【答案】在一棵树包含N个节点完全二叉树上,相距最远的两节点的距离是2logN-3 大约2logN。选A
2. 折半查找不成功时，指针Low和High的关系是_____。【答案】Low>High
3. 在构造了一棵二叉排序树以后,为了产生一个用于打印的有序数字数组，通常应该做的操作是_____。 【答案】中序遍历
4. 在列车调度网络中，有四个车皮编号分别为1，2，3，4，并按此顺序随时送入栈中进行调度，这些车皮取出的顺序可以是_____。【答案】3241
5. 某二叉树先序遍历的结点序列是abdgcefh，中序遍历的结点序列是dgbaechf，则其后序遍历的结点序列是_____。 【答案】gdbehfca
三、
1、(1)为什么说算法是当今计算机学科的支柱之一？(2)已知X=2，要求精度R=3，请给出用算盘求解e^x的算法设计过程及算法，并给出满足给定条件的解。
【答案】在我们计算机学科里面，你做的任何一件事情，你要编程，你要设计，你都毫无疑问的涉及到我们这个算法，没有算法，你怎么去进行程序的编写呢，你都不会利用算法将一个大问题分成小问题，你怎么知道去解决这个大问题呢，这不是开玩笑么，这就是为什么算法作为计算机学科的核心概念，而不是其他的语言。
【答案】没有找到
2. 欲得到一个逆序排列的数据元素序列的正序输出序列的有效方法是什么？如果这个逆序序列的数据元素正好存满了一维数组的从1到n的所有分量的话。
【答案】顺序表的倒置
for (i = 0; i <= n / 2; i++) {
t = a[i];
a[i] = a[n - i];
a[n - i] = t;
}
3. 请问表达式(8+36)/(2+35-4)的逆波兰形式是什么？
1.首先将这个中缀表达式的所有运算加括号;
2.然后将所有运算符放到括号后面;
3.把所有括号去掉，最后得出的结果就是后缀表达式;
【答案】8 3 6+2 3 5+4-/
4. 请问什么是稳定排序？和非稳定排序相比，它有什么优点？为什么说快速排序、希尔排序等时间性能较好的排序方法都是不稳定的？
【答案】数据元素序列为R1 ，R2，R3，……，Rn 若 Ki=Kj (K为关键字值) 且 1≤i≤n ， 1≤j≤n ，i≠ j
如果排序前Ri领先于Rj，排序后Ri仍领先于Rj，则称此排序是为稳定排序。反之为非稳定排序。
可以看出，稳定排序与非稳定排序相比，减少了元素的不必要的移动次数。 快速排序、希尔排序等时间性能较好的排序方法之所以是不稳定的，我们可以通过分析它们的排序过程得到解释。由于这些方法在排序过程中的“比较”不是在“相邻的两个记录关键字”之间进行的，因此，这样的比较产生的交换，就有可能改变了关键字值相同的数据元素原先的顺序，所以是不稳定的。
5. 某高校一个班21位同学外出实习，学生的学号为1到21，住在一个没有一个旅客，却有许多房间，且房间按从1到n的顺序编号的旅馆里。若班主任以学号为查找条件查找任一个同学，如不计住宿费用，请问如何安排房间可使得查找效率最高？
【答案】没有答案
6. 在对于大规模复杂问题求解时，是否求解的硬件系统包含的CPU数目越多，效率就越高？为什么？
【答案】不一定，CPU数目也是一方面，CPU的线程、硬盘的性能、主板芯片的能力，显卡的档次都能影响到效率，电脑效率是一个综合指标,算法简单说有这几个：
1，先来先服务(Frist Come First Servies简写FCFS)算法
FCFS算法是一种最简单的调度算法，不支持进程的抢先操作。仅仅是按照进程到达就绪队列的顺序，先进入就绪队列的先执行。实现FCFS调度算法非常简单，仅仅需要编写一个队列的数据结构处理即可。
2，短任务优先(Shortest Job First简写SJF)算法
SJF算法是理论上最好的调度算法，是平均等待时间最少的算法。同样是非抢先的操作。对于SJF算法实现上面需要对于就绪队列中进程CPU时间片为关键码执行排序。这里可以使用任何一种排序算法，不过考虑效率和动态添加来看这里最佳的排序算法应该是考虑堆排序，不仅开销上面可以控制在nlogn级别上，而且还可以动态的将新的就绪进程添加到CPU等待队列中。虽然SJF算法是最好的算法，但是由于需要依赖进程到达和CPU时间片做依赖，所以SJF算法一般不直接作为主要的调度算法，而是和其他算法搭配使用。
3，轮转(Round-Robin简写RR)算法
RR算法是一种抢先的调度算法，是专门为分时操作系统设计的。通过一个单元时间片不断的循环处理就绪队列的进程。对于RR算法实现的数据结构类似于FCFS算法，通过队列实现。需要注意的是对于在时间片内处理完成的进程直接队头删除，对于没有完成的需要在执行时间减去时间片后再次加入队列尾部。对于真个算法的性能关键是单元时间片的设置，如果单元时间片超过最大等待进程的进程CPU时间片，该算法将等同于FCFS算法的效率。
4，优先级调度(Priority Scheduling简写PS)算法
优先级调度可以是抢先或者是非抢先的调度。优先级算法会更具就绪进程队列的优先级作为关键玛进行排序，然后再和上面FCFS、SJF或者RR算法组合使用。对于实现上面主要需要一个排序算法来处理优先级的排序。 网上找的，，不过怎么看怎么不想数据结构倒像是操作系统
四、
1. 现有n个学生的身高值按从小到大的顺序存在一个一维数组中，若用户需要以身高值为关键字查询某学生的相关信息，请设计一个有效的算法，完成这个功能。（12分）
- 某高校为在数千学生中,预选参加全国程序设计大赛的选手,需 要先将学生按参赛要求给定的一个程序设计课程分数,把学生按程序 设计课程成绩分成两部分,使前一部分学生的成绩低于给定分数值，后一部分学生的成绩等于、高于给定分数值。请设计一个有效的算法，完成这个功能。（18分）
3. 设有一个由正整数组成的无序的线性链表，请设计一个算法，能在一趟扫描过程中找出该序列的最大数和最小数。
int MaxAndMin( int a[],int n ,int max,int min ) //a[]为数组 n为数组元素个数
{
max = min = a[0];
for( int i =1; i < n ;i ++ )
{
if (a[i] > max ) { max = a[i]; }
else if (a[i] < min ){ min = a[i]; }
}
return 0;
}
网友评论