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

《算法与数据结构复习纲要二》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、201209学期《算法与数据结构》复习纲要二一、单项选择题1.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间。A．单链表B．给出表头指针的单循环链表C．双链表D．带头结点的双循环链表2.在循环双链表的p所指的结点之前插入s所指结点的操作是（）。A．p->prior=s；s->next=p；p->prior->next=s；s->prior=p->priorB．p->prior=s；p->prior->next=s；s->next=p；s->prior=p->priorC．s->next=p；

2、s->prior=p->prior；p->prior=s；p->prior->next=sD．s->next=p；s->prior=p->prior；p->prior->next=s；p->prior=s3.如果最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节省时间。A．单链表B．双链表C．顺序表D．单循环链表4.与单链表相比，双链表的优点之一是（）。A．顺序访问相邻结点更灵活B．可以进行随机访问C．可以省略表头指针或表尾指针D．插入、删除操作更简单5.单链表中，增加一个头结点的目的是为了（）。A．使单链表至少有一个结点B．标识表结点中

3、首结点的位置C．方面运算的实现D．说明单链表是线性表的链式存储二、多项选择题1.下列说法正确的有（）。A.算法和程序原则上没有区别，在讨论数据结构时二者通用B.从逻辑关系上讲，数据结构分为线性结构和非线性结构两大类C.所谓数据的逻辑结构是指数据元素之间的逻辑关系D.同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数相等E.数据的逻辑结构与数据元素本身的内容和形式无关F.数据结构是指相互之间存在一种或多种关系的数据元素的全体2.下列说法正确的有（）。A.对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的

4、二叉搜索树都是相同的B.在二叉搜索树上插入新结点时，不必移动其它结点，仅需要改动某个结点的指针，使它由空变为非空即可C.对于两棵具有相同关键码集合而形状不同的二叉搜索树，按中序遍历它们得到的序列的各元素的顺序是一样的D.在二叉搜索树上删除一个结点时，不必移动其它结点，只要将该结点的双亲结点的相应指针域置空即可第3页共3页3.下列说法正确的有（）。A.存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关B.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关C.任何

5、一个关键活动提前完成，那么整个工程就会提前完成D.有n(n≥1)个顶点的有向强连通图最少有n条边三、填空题1．在各种查找方法中，平均查找长度与结点个数n无关的查找方法是__________。2．在分块索引查找方法中，首先查找__________，然后查找相应的块表。3．一个无序序列可以通过构造一棵__________树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。4．带头结点的循环链表L中只有一个元素结点的条件是__________。5．栈是限定仅在表尾进行插入或删除操作的线性表，其运算遵循__________的原则。6．空串是_

6、_________，其长度等于零。四、判断题1．对于任意一个图，从它的某个结点进行一次深度或广度优先遍历可以访问到该图的每个顶点。（）2．在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，称这种排序为稳定排序。（）3．在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。（）4．拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。（）5．冒泡排序算法关键字比较的次数与记录的初始排列次序无关。（）五、简答题1.用数组结构实现堆栈时，由于数组结构的特点，我们完全可以访问数组中的任何一个元素，

7、为什么只是从栈顶访问元素？2.试写出求循环队列长度的算法。3.描述快速排序的处理过程。4.假设有如下的结构定义：structnode{chardata;structnode*link;}*p,*pre;而且pre指向链表中非空元素，写一段程序生成构造p结点，并将其链入到pre之后。5.假设某棵树为三叉树，树结点中data为数据域，first,second,third分别表示三叉树的三个链域。设计算法，对以t为根结点的三叉树进行前序遍历。6.简述顺序表和链表存储方式的特点。第3页共3页201209学期《算法与数据结构》复习纲要二答案一、单项选择题题

8、号12345答案DDCAC二、多项选择题题号123答案BCEBCBD三、填空题（1）散列查找法（2）索引表（3）二叉排序（4）L->ne