2010数据结构

一、填空题(共20分,每空2分。答案一律写在答题纸上,否则无效。)
1、所谓的双向链表,是指在每一个结点中,有两个指针域,其中一个指向该结点的直接后继结点,而另一个则指向_______________.
【答案】其直接前趋结点
2、线性表的顺序存储结构是一种____________存取的存储结构。
【答案】随机
3.若一棵根树的每个结点最多只有___________孩子,且孩子又有__________之分,次序不能颠倒,则称此树为_______________
【答案】两个，左、右，二叉树
4、满二叉树是指高度为k,且有______个结点的二叉树。二叉树的每一层上,最多有_____个结点。
【答案】2k-1 2i-1
5、在各种查找方法中,平均查找长度与结点个数n无关的查找方法是__________
【答案】哈希表查找法
6、广义表(a,(a,b),d,e,(i,j),k)的长度是_________,深度是__________.
【答案】5，3

二.单选题(共18分,每题3分。答案一律写在答题纸上,否则无效。)
1、下面哪一种情况不利于发挥堆排序的优势________
A、待排序的数据量很大     B、待排序的数据量小
C、待排序的数据中有的数值很大     D、待排厅的数据相同率高
【答案】待排序的数据量小
2、如果采用直接选择排序法来排序一个长度为5,且已按相反顺序排序的数组,共需的比较次数是
A、1     B、15     C、8     D、10
【答案】10
3、在一棵包含n个结点的顺序二叉树上,最远的两个结点有多远__________
A、大约log2n     B、大约2log2n     C、大约n^2     D、大约 nlog2n
【答案】2logN-3
4、折半查找不成功时,指针Low和High的关系是________
A、 Low <High     B、Low>High
C、Low与High无关 D、Low=High
【答案】Low>High
5、在待排元素序列基本有序的前提下,下面给出的几种排序方法效率最高的是__
A、直接插入排序 B、直接选择排序 C、归并排序 D、快速排序
【答案】直接插入排序
6、设A是一个包含有10个数据元素的有序数组,如果我们利用折半查找法在A中查找任意的数据元素X,假定我们在确定目标元素是否等于、小于或者大于A[i]时仅仅需比较一次的话。则平均的查找成功时间是_______
A、1.6     B、4.2     C、5.5     D、2.9
【答案】2.9
三、判断题（正确写Y,反之写N)
1、( X )能在线性表上进行的操作,就一定能在栈上进行。
2、( ✔ )如果关键字是主关键字的话,则对一个无序的数据元素序列经按主关键字排序后得到的结果是唯一的。
3、( X )由于线性链表的存取必须顺序进行,所以在线性链表上删除一个结点时,必须移动其后的所有结点,才能继续保持一个顺序存取的关系
4、( ✔ )线性表顺序存储结构的存储密度大于线性表的链式存储结构
5、( X )二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索。
6、( X )由于二叉树的每个结点最多只能有两个孩子,所以它是一种特殊的根树。
7、( ✔ )任何一棵二叉树的叶子结点在先序、中序、后序遍历得到序列中的相对次序是不发生变化的
8、( X )线性表的链式存储结构和顺序存储结构不同,它要求内存中可用的存储单元的地址一定是不连续的。

四、问答题(共66分)
1、(14分)如果一个逆序序列是用单链表表示的话。欲得到这个逆序排列的数据元素序列的正序输出序列的有效方法是什么?
【答案】栈
2、(15分)假设我们在有20个数据元素的有序线性表上实施折半查找,则比较五次查找成功的结点数是多少?平均的查找长度是多少？
【答案】5，3.7
【类似】假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的节点数为1；比较两次查找成功的结点数为（ ），比较四次查找成功的结点数为（ ）；平均查找长度为（ ）。
2个; 8个; 平均查找长度为（1x1+2x2+3x4+4x8+5x5)/20=74/20
先构造长度为20的折半查找判定树，其他的就OK了，判定树如下

3、(12分)对于由n个数据元素构成的序列实施冒泡排序时,数据元素的最少交换次数是多少?此种情况说明该数据元素序列己具有什么特征？
【答案】0，已按排序要求有序的
4、(15分)有一组随机数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
(4) 15 20 21 25 27 35 47 68 84
请问,根据以上情况判断所用的排序方法是什么?
【答案】 快速排序
5、(10分)某二义树先序遍历的结点序列是 abdgcefh,中序遍历的结点序列是 dgbaechf,请问,则其后序遍历的结点序列是什么?
【答案】 gdbehfca

五、算法设计题(共30分)
[注意:算法题应对数据结构(逻辑结构、存储结构)、主要数据类型等给出说明;算法可以用类C、类PASCAl、流程图等伪代码描述,或可用C语言、 PASCAL语言等可执行代码描述。]
1、(10分)一个有序的数据元素序列,以线性链表存储。请设计一个算法,在该链表上插入一个新的数据元素,并保持链表的有序性。

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、(20分)已知一个数据值为整数的线性表,欲以表中第一个数据元素为参考点,将该表划分为左右两部分,使其参考点左边的每个数据元素值均小于等于参考点的值,而参考点边的每个数据元素值均大于参考点的值。若不考虑空间复杂度, 利用异地处理方式,设计一个求解该问题的有效算法。

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()函数代码