点击联系发帖人
时间：2022-06-03 08:22
已经好长时间没有写算法了，今天就写了一个简单的折半查找的算法，很简单。来瞧瞧吧！好了，现在就开始吧！
所谓折半查找，哦，对了，以前的那篇折半排序博文，如果大家看过的话，折半查找那是小 case 了！当然不在话下了。
何为折半查找，就是查找一个数是否在一个给定的排好序的序列中。每次从序列的中间开始比较，如果，中间的数要比你要查找的数字大，那就忽略中间以右的那一部分（当然，我的前提是，序列是升序排列的），就在左部分查找你要查找的值，如果找到了，恭喜你，否则，抱歉，没有找到。就是这个思想，很简单。好了，贴出我的代码，代码才能说明问题，是吧！
一、单项选择题（每小题3分，共30分）
1、在有n 个叶子结点的哈夫曼树中，其结点总数为（）。
2、下列序列中，（）是执行第一趟快速排序得到的序列（排序的关键字类型是字符串）。
3、若线性表最常用的操作是存取第i 个元素及其前驱的值，则采用（）存储方式节省时间。
4、下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlogn)的是（）。
5、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。
6、下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（）。
7、快速排序算法在最好情况下的时间复杂度为（）。
8、已知数据表A中每个元素距其最终位置不远，则采用（）排序算法最省时间。
9、带权有向图G用邻接矩阵A存储，则顶点i的入度为A中（）。
A、第i行非∞的元素之和
B、第i列非∞的元素之和
C、第i行非∞且非0的元素之和
D、第i列非∞且非0的元素之和
10、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。
二、判断题（认为对的在题后的括号内打“√”，错的打“ⅹ”，每小题１分，
1.对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可
访问该图的每个顶点。( )
2. 在索引顺序表上实现分快查找，在等概率查找情况下，其平均查找长度不仅
与表的个数有关，而且与每一块中的元素个数有关。( )
3、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。( )
4、图G的最小生成树的代价一定小于其他生成树的代价。( )
5、已知一棵树的先序序列和后序序列，一定能构造出该树。( )
6、对一个堆按层次遍历，不一定能得到一个有序序列。( )
1.利用异或运算对输入的文本进行加密解密输出，用户输入一个文本（字符串,设不超过
20个字符），然后输入作为密钥的字符，程序输入加密及解密的字符串。
2.编写一个程序，用户输入年份及月份两个数据，程序输出该月份的天数。（提示：对2
月要考虑是否闰年，闰年年份要么能被4整除且不能被100整除，要么能被400整除，除次之外都不是闰年）。
3.某大桥按不同型号征收车辆过桥费：自行车免费，摩托车2元，小汽车5元，大客车
与货车8元，货柜车12元。编写一个程序，按车辆的不同型号计算通过该大桥应征的过桥费。（提示：可以用整数对不同型号的车辆进行编码）
5.旅行社的订票量小于10张时，航空公司给予10%的折扣；订票量大于或等于10张且
小于20张时，航空公司给予15%的折扣；订票量大于或等于20张且小于30张时，航空公司给予30%的折扣；订票量大于或等于30张时，航空公司给予最高的45%的折扣。
编程输入订票张数及单张机票票价，程序输出折扣率及应付款额。
6.用户输入一个整数流（输入1000表示数据输入结束），如
编写程序统计输入流中-1、0和+1的个数。
7.编写一个程序，求一个自然数中含有多少个2的因子。如，6含1个2的因子，8含3
个2的因子，11不含2的因子。（提示，程序应检查用户输入的合法性）。
8.编写一个程序解决爱因斯坦台阶问题：有人走以台阶，若以每步走2级则最后剩1级；
若每步走3级则最后剩2级；若以每步走4级则最后剩3级；若以每步走5级则最后剩4级；若以每步走6级则最后剩5级；若以每步走7级则最后刚好不剩。问台阶共有几级？
9.公鸡5元1只，母鸡3元1只，小鸡1元3只，花了100元钱买100只鸡，问公鸡、
10.编程实现解决下述问题的算法：一位顾客在购物时，如果买4个苹果剩下4角钱．如
果买5个苹果则缺5角钱，请问，该顾客带了多少钱？多少钱可以头一个苹果？
11.编写程序．计算100之内可以被13整除的自然数之和。
