资源描述
2008 年、1. 高度为k,且有个结点的二叉树称为二叉树。【答案】2k-1,满2. 线性表的顺序映象就是逻辑上的两个数据元素，在物理存储上赋予位置的一种存储分配方式。【答案】相连，相邻3. 线性表的链式存储结构是一种存取的存储结构。【答案】顺序4. Hash表查找要研究的两个主要问题分别是和。【答案】均匀性，冲突的解决5. 数据元素之间的相互关系由一组运算和规则描述的数据元素的集合，称为数据的结构。【答案】逻辑6. 对于由n个数据元素构成的序列实施冒泡排序时，最少的比较次数是。冒泡排序的结束条件是。【答案】n-1，刚做完的一趟排序没有交换元素二、1. 在一棵包含n个结点的顺序二叉树上，最远的两个结点有多远。【答案】在一棵树包含N个节点完全二叉树上，相距最远的两节点的距离是21ogN-3大约21ogN,选A2. 折半查找不成功时，指针Low和High的关系是。【答案】LowHigh3. 在构造了一颗二叉排序树以后,为了产生一个用于打印的有序数字数组，通常应该做的操作是。【答案】中序遍历这道题网上没有答案，但是我觉得应该是这个4. 在列车调度网络中，有四个车皮编号分别为1, 2，3, 4,并按此顺序随时送入栈中进行调度，这些车皮取出的顺序可以是。【答案】32415.某二叉树先序遍历的结点序列是abdgcefh，中序遍历的结点序列是dgbaechf，则 其后序遍历的结点序列是。【答案】gdbehfca三、1、（1）为什么说算法是当今计算机学科的支柱之一？【答案】在我们计算机学科里面，你做的任何一件事情，你要编程，你要设计，你 都毫无疑问的涉及到我们这个算法，没有算法，你怎么去进行程序的编写呢，你都 不会利用算法将一个大问题分成小问题，你怎么知道去解决这个大问题呢，这不是 开玩笑么，这就是为什么算法作为计算机学科的核心概念，而不是其他的语言。（2）已知X=2，要求精度R=3，请给出用算盘求解ex的算法设计过程及算法，并给 出满足给定条件的解。【答案】没有找到2. 欲得到一个逆序排列的数据元素序列的正序输出序列的有效方法是什么？如果 这个逆序序列的数据元素正好存满了一维数组的从1到n的所有分量的话。【答案】顺序表的倒置for （i = 0; i = n / 2; i+）t = ai;ai = an - i;an - i = t;这道题应该没错,，但是帮忙问问人吧还是，网上没有答案,，我没有十足的把握3. 请问表达式（8+3*6） /（2+3*5-4）的逆波兰形式是什么？【答案】8 3 6*+2 3 5*+4-4. 请问什么是稳定排序？和非稳定排序相比，它有什么优点？为什么说快速排序、 希尔排序等时间性能较好的排序方法都是不稳定的？数据元素序列为R，R，R，R123n若 K=K（K为关键字值）i j且lWiWn , lWjWn , iH j如果排序前R领先于R，排序后R仍领先于R，则称此排序是为稳定排序。反ijij之为非稳定排序。可以看出，稳定排序与非稳定排序相比，减少了元素的不必要的移动次数。快速排序、希尔排序等时间性能较好的排序方法之所以是不稳定的，我们可以 通过分析它们的排序过程得到解释。由于这些方法在排序过程中的“比较”不是在 “相邻的两个记录关键字”之间进行的，因此，这样的比较产生的交换，就有可能 改变了关键字值相同的数据元素原先的顺序，所以是不稳定的。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个学生的身高值按从小到大的顺序存在一个一维数组中，若用户需要以身 高值为关键字查询某学生的相关信息，请设计一个有效的算法，完成这个功能。2. 二题过去都有，第一题是折半查找，第二题是高分39页53. 设有一个由正整数组成的无序的线性链表，请设计一个算法，能在一趟扫描过程 中找出该序列的最大数和最小数。这道题我还有点疑问，想清楚了给你发图片
展开阅读全文