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