2010年
一、
1. 所谓的双向链表，是指在每一个结点中，有两个指针域，其中一个指向该结点的直接后继结点，而另一个则指向 。
【答案】其直接前趋结点
2. 线性表的顺序存储结构是一种
【答案】随机
3. 若一棵根树的每个结点最多只有分，次序不能颠倒，则称此根树为 。
【答案】两个，左、右，二叉树
4. 满二叉树是指高度为k，且有个结点的二叉树。二叉树的每一层上，最多有 个结点。
【答案】2k-1 2i-1
5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 。
【答案】哈希表查找法
6. 广义表(a,(a,b),d,e,((i,j),k))的长度是 ，深度是 。
【答案】5，3
二、
1.下面哪一种情况不利于发挥堆排序的优势
【答案】待排序的数据量小
2. 如果采用直接选择排序法来排序一个长度为5，且已按相反顺序排序的数组，共需的比较次数是 。
【答案】10
3. 在一棵包含n个结点的顺序二叉树上,最远的两个结点有多远。
【答案】在一棵树包含N个节点完全二叉树上,相距最远的两节点的距离是2logN-3
4. 折半查找不成功时，指针Low和High的关系是
【答案】Low>High
5. 在待排元素序列基本有序的前提下，下面给出的几种排序方法效率最高的是 。
【答案】直接插入排序
6. 设A是一个包含有10个数据元素的有序数组，如果我们利用折半查找法在A中查找任意的数据元素X，假定在确定目标元素是否等于、小于或大于A[i]时仅需比较一次。则平均的查找成功时间是 。
【答案】2.9
三、
1. 能在线性表上进行的操作，就一定能在栈上进行。
【答案】错
2. 如果关键字是主关键字的话，则对一个无序的数据元素序列经按主关键字排序后得到的结果是唯一的。
【答案】对
3. 由于线性链表的存取必须顺序进行，所以在线性链表上删除一个结点时，必须移动其后的所有结点，才能继续保持一个顺序存取的关系。
【答案】错
4. 线性表顺序存储结构的存储密度大于线性表的链式存储结构。
【答案】对
5. 二叉树按某种顺序线索化后，任一结点均有指向其前趋和后继的线索。
【答案】错
6. 由于二叉树的每个结点最多只能有两个孩子，所以它是一种特殊的根树。
【答案】错
7. 任何一棵二叉树的叶子结点在先序、中序、后序遍历得到序列中的相对次序是不发生变化的。
【答案】对
8. 线性表的链式存储结构和顺序存储结构不同，它要求内存中可用的存储单元的地址一定是不连续的。
【答案】错
四、
1. 如果一个逆序序列是用单链表表示的话，欲得到这个逆序排列的数据元素序列的正序输出序列的有效方法是什么？
【答案】栈
2. 假设我们在有20个数据元素的有序线性表上实施折半查找，则比较五次查找成功的节点数是多少？平均的查找长度是多少？
【答案】5，3.7
【类似】假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的节点数为1；比较两次查找成功的结点数为（ ），比较四次查找成功的结点数为（ ）；平均查找长度为（ ）。
二次为2个
四次的为8个
平均查找长度为（1x1+2x2+3x4+4x8+5x5)/20=74/20
先构造长度为20的折半查找判定树，其他的就OK了，判定树如下




3. 对于由n个数据元素构成的序列实施冒泡排序时，数据元素的最少交换次数是多少？此种情况说明该数据元素序列已具备有什么特征？
【答案】0，已按排序要求有序的
4. 有一组随机数25，84，21，47，15，27，68，35，20，现在采用某种算法对它们进行排序，具体过程如下：
（1）25 84 21 47 15 27 68 35 20
（2）20 15 21 25 47 27 68 35 84
（3）15 20 21 25 35 27 47 68 84
（3）15 20 21 25 27 35 47 68 84
请根据以上情况，判断所用的排序方法是什么？
【答案】 快速排序
5. 某二叉树先序遍历的结点序列是abdgcefh，中序遍历的结点序列是dgbaechf，则其后序遍历的结点序列是什么？
【答案】 gdbehfca
五、
1. 一个有序的数据元素序列，以线形链表存储。请设计一个算法，在该链表上插入一个新的数据元素，并保持链表的有序性。
【答案】 这是我在网上找的，你参考看看
int insert(List **lptr, ElemType e)
{
//lptr为有序的链表,e为要插入的元素，如果插入成功则返回1，否则返回0
List *newNode, *cur, *prior;
newNode = (List*)malloc(sizeof(List));
if (newNode == NULL) return 0; //分配空间失败
newNode->data = e;
cur = *lptr;
prior = *lptr;
while (cur != NULL && cur->data < e){//查找插入的位置
prior = cur;
cur = cur->next;
}
if (cur == *lptr){
//插入到链表的头部
newNode->next = *lptr;
*lptr = newNode; //lptr指向链表的第一个元素
}else{
//插入到prior之后
prior-> = newNode;
newNode->next = cur;
}
return 1;
}
2. 已知一个数据值为整数的线性表，欲以表中第一个数据元素为参考点，将该表划分为左右两部分，使其参考点左边的每个数据元素值均小于等于参考点的值，而参考点右边的每个数据元素值均大于参考点的值。若不考虑空间负责度，利用异地处理方式，设计一个求解该问题的有效方法。
【答案】这是我在网上找的，你参考看看
int Partition(SqList &L, int low, int high) {
// 交换顺序表L中子序列L.r[low..high]的记录，使枢轴记录到位，
// 并返回其所在位置，此时，在它之前（后）的记录均不大（小）于它
KeyType pivotkey;
RedType temp;
pivotkey = L.r[low].key; // 用子表的第一个记录作枢轴记录
while (low<high) { // 从表的两端交替地向中间扫描
while (low<high && L.r[high].key>=pivotkey) --high;
temp=L.r[low];
L.r[low]=L.r[high];
L.r[high]=temp; // 将比枢轴记录小的记录交换到低端 while (low<high && L.r[low].key<=pivotkey) ++low;
temp=L.r[low];
L.r[low]=L.r[high];
L.r[high]=temp; // 将比枢轴记录大的记录交换到高端 }
return low; // 返回枢轴所在位置
} // Partition
PS:快速排序的Partition()函数代码