算法与数据结构复习纲要二.doc

201209学期算法与数据结构复习纲要二一、单项选择题1. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用 （ ）存储方式最节省运算时间。 A单链表 B给出表头指针的单循环链表 C双链表 D带头结点的双循环链表 2. 在循环双链表的p所指的结点之前插入s所指结点的操作是（ ）。 Ap-prior = s；s-next = p；p-prior-next = s；s-prior = p-prior Bp-prior = s；p-prior-next = s；s-next = p；s-prior = p-prior Cs-next = p；s-prior = p-prior；p-prior = s；p-prior-next = s Ds-next = p；s-prior = p-prior；p-prior-next = s；p-prior = s 3. 如果最常用的操作是取第i个结点及其前驱，则采用（ ）存储方式最节省时间。 A单链表 B双链表 C顺序表 D单循环链表 4. 与单链表相比，双链表的优点之一是（ ）。 A顺序访问相邻结点更灵活 B可以进行随机访问 C可以省略表头指针或表尾指针 D插入、删除操作更简单 5. 单链表中，增加一个头结点的目的是为了（ ）。 A使单链表至少有一个结点 B标识表结点中首结点的位置 C方面运算的实现 D说明单链表是线性表的链式存储 二、多项选择题1. 下列说法正确的有（ ）。A. 算法和程序原则上没有区别，在讨论数据结构时二者通用 B. 从逻辑关系上讲，数据结构分为线性结构和非线性结构两大类C. 所谓数据的逻辑结构是指数据元素之间的逻辑关系 D. 同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数相等 E. 数据的逻辑结构与数据元素本身的内容和形式无关 F. 数据结构是指相互之间存在一种或多种关系的数据元素的全体2. 下列说法正确的有（ ）。 A. 对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的 B. 在二叉搜索树上插入新结点时，不必移动其它结点，仅需要改动某个结点的指针，使它由空变为非空即可 C. 对于两棵具有相同关键码集合而形状不同的二叉搜索树，按中序遍历它们得到的序列的各元素的顺序是一样的 D. 在二叉搜索树上删除一个结点时，不必移动其它结点，只要将该结点的双亲结点的相应指针域置空即可3. 下列说法正确的有（ ）。 A. 存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关 B. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关 C. 任何一个关键活动提前完成，那么整个工程就会提前完成 D. 有n(n1)个顶点的有向强连通图最少有n条边三、填空题1在各种查找方法中，平均查找长度与结点个数n无关的查找方法是_。 2在分块索引查找方法中，首先查找_，然后查找相应的块表。 3一个无序序列可以通过构造一棵_树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。 4带头结点的循环链表L中只有一个元素结点的条件是_。 5栈是限定仅在表尾进行插入或删除操作的线性表，其运算遵循_的原则。6空串是_，其长度等于零。 四、判断题1对于任意一个图，从它的某个结点进行一次深度或广度优先遍历可以访问到该图的每个顶点。（ ） 2在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，称这种排序为稳定排序。（ ）3在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。（ ）4拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。（ ） 5冒泡排序算法关键字比较的次数与记录的初始排列次序无关。（ ） 五、简答题1. 用数组结构实现堆栈时，由于数组结构的特点，我们完全可以访问数组中的任何一个元素，为什么只是从栈顶访问元素？2. 试写出求循环队列长度的算法。3. 描述快速排序的处理过程。4. 假设有如下的结构定义：struct node char data; struct node * link; * p, *pre; 而且pre指向链表中非空元素，写一段程序生成构造p结点，并将其链入到pre之后。5. 假设某棵树为三叉树，树结点中data为数据域，first,second, third分别表示三叉树的三个链域。设计算法，对以t为根结点的三叉树进行前序遍历。6. 简述顺序表和链表存储方式的特点。 201209学期算法与数据结构复习纲要二 答案 一、单项选择题题号12345答案DDCAC二、多项选择题题号123答案BCEBCBD三、填空题（1）散列查找法（2）索引表（3）二叉排序 （4）L-next-next=L（5）后进先出 （6）零个字符的串 四、判断题题号12345答案TTTFF五、简答题1答案:由于数组结构的固有特点，我们完全可以访问数组中的任何一个元素，但是，用数组结构实现堆栈时，面对的是堆栈，数组只是堆栈的物理结构，椎栈限定所有的插入与删除操作只能在一端进行，如果是任意访问数组的元素，则破坏了堆栈的结构。2 答案:/ 是存贮空间的长度，队头指针为front, 队尾指针为rear int QueueLen(Q) int l = 0, f = front ; while ( f != rear) f = (f + 1 ) mod n; l+; return l; 3 答案:快速排序其处理过程是：取出某一记录，以该记录所对应的关键字为基准，将待排序的记录分成两部分，便得基准位置前所有记录的关键字均小于或等于基准位置记录的关键字，基准位置后面的记录的关键字将大于或等于基准位置记录的关键字，然后再分别对基准位置前后的记录序列作为待排序的子序列，重复上述过程，直到所有记录全部排序好为止。4答案:ch=getchar(); /取一个数据元素/ p=(struct node *)malloc(sizeof(struct node); /申请一个新结点/ p-data=ch; p-link = pre-link; pre-link = p;5 答案:void tran( t) if (t = NULL) return ; printf(t-data); tran( t-first); tran( t-second); tran( t-third); 6 答案：顺