试题17．有一份成绩单，只有两个字段：姓名、成绩；数据量在百万级别。要求用最优的数据存储方式，能通过姓名快速查找出成绩。
答案：存储方式采用对姓名做hash。
试题18．快速排序的平均时间复杂度是多少？最坏时间复杂度是多少？在哪些情况下会遇到最坏的时间复杂度？
分析：考察考生对排序算法的了解。
参考答案：快速排序时间复杂度为O(nlogn)，最坏时间复杂度是O(n2)，在待排序列正序或者逆序的情况下会出现最坏时间复杂度。
试题19．请用任意你熟悉的语言实现一个冒泡算法，并写出它的时间复杂度。
分析：考察基本算法知识。
参考答案：见本章2.1.5。
试题20．栈和队列的共同特点是什么？
分析：考察栈和队列的概念。
答案：栈和队列都只能在端点处插入和删除元素。
试题21．栈通常采用的两种存储结构是什么？
分析：栈属于线性表的一种，线性表存储结构有两种。
答案：顺序存储和链表存储。
试题22．下列关于栈的叙述正确的是（ ）。
A栈是非线性结构 B栈是一种树状结构
C栈具有先进先出的特征 D栈具有后进先出的特征
分析：考察栈的概念。
答案：D。
试题23．链表不具有的特点是（ ）。
A不必实现估计存储空间 B可随机访问任一元素
C插入和删除不需要移动元素 D所需空间与线性表长度成正比
分析：该题考察链表的特点，B属于顺序存储结构的特点。
答案：B。
试题24．链表的优点是什么？
分析：考察链表的特点。
答案：便于插入和删除操作；动态申请空间。
试题25．线性表若采用链式存储，要求内存中可用的存储单元地址（ ）。
A连续 B部分地址连续 C一定不连续 D连续不连续都可以
分析：考察链表的特点。
答案：D。
试题26．在深度为5的满二叉树中，叶子结点的个数是多少？
分析：考察二叉树的特性以及满二叉树的概念。满二叉树叶子结点的个数为 。注意别计算成完全二叉树。
答案：31。
试题27．已知，二叉树后根遍历结果是dabec，中根遍历结果是debac，它的前根遍历结果是什么？
分析：考察二叉树的遍历方式，2.1.3中有讲解，先画出树来，再遍历。
答案：cedba。
试题28．已知，二叉树前根和中根遍历结果分别是ABDEGCFH和DBGEACHF，则该二叉树的后根遍历结果是什么？
分析：同试题27。
答案：DGEBHFCA。
试题29．串的长度定义是什么？
分析：考察串的概念。
答案：串中所包含的的字符个数。
试题30．判断两个数组中是否存在相同的数字，给定两个排好序的数组，怎样高效判断这两组数中有相同的数字？
分析：这个问题首先想到的是O(nlog2n)的算法。任意挑选一个数组，遍历这个数组的所有元素。在遍历过程中，在另一个数组中对第一个数组中的每个元素进行binary search。还有一个O(n)算法。因为两个数组都是排好序的，所以只需要遍历一次就行了。
答案：首先，设置两个下标，分别初始化为两个数组的起始地址，依次向前推进。推进的规则是比较两个数组中的数字，小的数组的下标向前推进一步，直到任何一个数组的下标到达数组末尾时，若还没有碰到相同的数字，说明数组中没有相同的数字。
试题31．在需要经常查找结点的前驱和后继的场合中，使用（ ）比较合适。
A单链表 B双链表 C顺序链表 D循环链表
分析：考察链表的运用。
答案：B。
试题32．对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数是多少？
分析：考察查找算法的熟练程度
答案：最坏比较N次。
试题33．最简单的交换排序方法是什么？
答案：冒泡排序。
试题34．线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数是多少？
分析：考察对冒泡排序的熟练程度。
答案：n(n-1)/2。
试题35．在待排序元素基本有序的前提下，效率最高的排序方法是什么？
答案：冒泡排序。
试题36．在最坏情况下，排序方法中时间复杂度最小的是什么？
答案：堆排序。
试题37．堆排序法属于什么？
答案：选择类排序。
试题38．对于输入为N个数进行快速排序算法的平均时间复杂度是多少？
分析：见本章2.1.5中表2.1。
答案：O(Nlog2N)
试题39．整数转换成字符串。
分析：本章2.1.2中有算法描述。
答案：
1．/*整数转化成字符串*/
2．char *IntToStr(int num, char str[])
3．{
4． int i = 0, j = 0;
5． char temp[100];
6． while(num)
7． {
8． temp[i] = num % 10 + '0'; //取模运算得到从后往前的每一个数字变成字符
9． num = num / 10;
10． i++;
11． }
12． temp[i] = 0; //字符串结束标志
13．
14． i = i - 1; //回到temp最后一个有意义的数字
15． while(i >= 0)
16． {
17． str[j] = temp[i];
18． i--;
19． j++;
20． }
21． str[j] = 0; //字符串结束标志
22． return str;
23．}
试题40．将字符串转化成整数。
分析：本章2.1.2中有算法描述。
答案：
1．/*字符串转换为整数，仅考虑十进制,不考虑非法字符*/
2．int StrToInt(char *str)
3．{
4． int value = 0;
5． int sign = 1;
6． assert(str != NULL);
7． if(*str == '-')
8． {
9． sign = -1;
10． str++;
11． }else if(*str == '+')
12． {
13． str++;
14． }
15． while(*str)
16． {
17． value = value * 10 +(*str - '0');
18． str++;
19．
20． }
21． return sign * value;
22．}
试题41．在不借助第三个变量的情况下，把两个int的变量X、Y的值互换，用任何自己熟悉的编程语言完成。
参考答案：思路为X=X+Y,Y=X-Y,X=X-Y。
版权声明：51Testing软件测试网获作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可，不得对本文内容复制、转载或进行镜像，否则将追究法律责任。
相关文章：
