一、单项选择题。
1．算法的时间复杂度的表示方法是（ ）
a、实现算法的程序在指定机器上执行的时间。
b、标准程序在机器上的执行时间。
c、基本操作重复次数，即问题规模n的某个函数。
d、与刻画基本操作重复次数的函数同阶无穷大的函数f(n)
2．在一个双向链表中，假设结点的域分别为left, right,以及data。其中left、right分别为两个链域，data是数据域。下一段程序是实现在h结点之后插入p结点的功能，其中h结点不空，h的下一个结点亦不空。
判断哪一段程序是正确的（ ）
a、p->right = h->right p->left = h h->right = p p->right->right = p
b、p->right = h->right p->left = h h->right = p p->right->left = p
c、h->right = p p->left = h p->right = h->right p->right->left = p
d、p->right = h->right p->left = h h->right = p h->right->left = p
3．在树中，树的度与结点的度之间的关系是（ ）
a、树的度就是结点的度。
b、树的度为2，结点的度可以是0，1和2
c、结点度中最大值为树的度。
d、树的度与结点的度无关。
4．文件的基本组织方式有（ ）
a、顺序组织、索引组织、散列组织和链接方式。
b、磁盘组织、磁带组织。
c、数据库组织。
d、关键字与非关键字。
5．为了区别循环队列中队满与队空的条件，采用的方法是（ ）
a、不需要特别的方法。
b、牺牲一个存贮空间
c、把队头永远放到队尾的前端。
d、每次出队后，移动数据。
6．一个具有n个顶点的连通无向图的生成树中有（ ）条边。
a、n-1b、n
c、n/2d、n+1
7．在待排序的元素序列基本有序的前提下，效率最高的排序算法是（ ）
a、选择排序。
b、插入排序。
c、快速排序。
d、归并排序。
8．关键路径是事件结点网络中（ ）
a、最长的回路。
b、最短的回路。
c、从开始结点到完成结点的最长路径。
d、从开始结点到完成结点的最短路径。
9．下面说法错误的是（ ）
a、算法原地工作的含义是指不需要任何额外的辅助空间。
b、在相同的规模n下，复杂度o(n)的算法在时间上总是优于复杂度o(2n)的算法。
c、所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
d、同一个算法，实现语言的级别越高，执行效率就越高。
10．由3个结点可以构造出（ ）种不同的有向树。
a、2b、3
c、4d、5
11．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）方法最快。
a、冒泡排序。
b、快速排序
c、希尔排序。
d、堆排序。
12．最大容量为n的循环队列，队尾指针是rear，队头指针是front，则队空的条件是（ ）
a、（rear+1）mod n=front
b、rear=front
c、rear+1=front
d、（rear-1）mod n=front
13．4个圆盘的hanoi塔，总的移动次数为（ ）
a、7b、-8
c、15d、16
14．一棵二叉树的前序遍历序列为abcdefg，它的中序遍历序列可能是（ ）
a、cabdefg
b、abcdefg
c、dacefbg
d、adcfeg
15．动态存储管理系统中，通常可有（ ）种不同的分配策略。
a、1b、2
c、3d、4
16. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（ ）存储方式最节省运算时间。
a．单链表。
b．给出表头指针的单循环链表
c．双链表。
d．带头结点的双循环链表
17. 在循环双链表的p所指的结点之前插入s所指结点的操作是（ ）
a．p->prior = s；s->next = p；p->prior->next = s；s->prior = p->prior
b．p->prior = s；p->prior->next = s；s->next = p；s->prior = p->prior
c．s->next = p；s->prior = p->prior；p->prior = s；p->prior->next = s
d．s->next = p；s->prior = p->prior；p->prior->next = s；p->prior = s
18. 如果最常用的操作是取第i个结点及其前驱，则采用（ ）存储方式最节省时间。
a．单链表。
b．双链表
c．顺序表。
d．单循环链表
19. 与单链表相比，双链表的优点之一是（ ）
a．顺序访问相邻结点更灵活。
b．可以进行随机访问
c．可以省略表头指针或表尾指针
d．插入、删除操作更简单
20. 单链表中，增加一个头结点的目的是为了（ ）
a．使单链表至少有一个结点。
b．标识表结点中首结点的位置
c．方面运算的实现。
d．说明单链表是线性表的链式存储
二、判断题。
1. 在单向链表中，在x指向的结点后插入结点，对应的方法与x是否是头指针无关。（
2. 在求最短路径的dijkstra算法和floyd算法中，dijkstra算法只能求从一点到其他各点的最短路径，而floyd算法可以求图中两点之间的最短路径。（
3. 线性结构中，每个点至多有一个前趋和一个后继，树中一个结点至多有一个前趋和多个后继，图中的结点可以有多个前趋和多个后继。（
4. 拓扑排序是图的另一种遍历。（
5. 如果入队与出队的操作顺序不同，其输出元素的顺序可以与输入元素的顺序不同。（
6. 快速排序是稳定的。（
7. 动态查找的概念是指查找中指定关键字不断发生变化的查找。（
8．对于任意一个图，从它的某个结点进行一次深度或广度优先遍历可以访问到该图的每个顶点。（
9．在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，称这种排序为稳定排序。（
10．在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。（
11．拓扑排序是按aoe网中每个结点事件的最早发生时间对结点进行排序。（
12．冒泡排序算法关键字比较的次数与记录的初始排列次序无关。（
三、简答题。
1. 算法与程序有什么区别？
2. 什么是线性表？
3. 什么是队列？什么叫队列的头？什么叫队列的尾？
4. 给出栈的最常用的至少4种操作，并说明它们的功能。
5. 二度树与二叉树有什么区别？
6. 对线性表进行二分检索的先决条件是什么？请简述二分检索的基本过程。
7. 什么是最佳二叉排序树？在各结点等权的情况下，什么样的二叉排序树是最佳的？
8. 用数组结构实现堆栈时，由于数组结构的特点，我们完全可以访问数组中的任何一个元素，为什么只是从栈顶访问元素？
9. 试写出求循环队列长度的算法。
10. 描述快速排序的处理过程。
11. 假设有如下的结构定义：struct node *p, *pre; 而且pre指向链表中非空元素，写一段程序生成构造p结点，并将其链入到pre之后。
12. 假设某棵树为三叉树，树结点中data为数据域，first,second, third分别表示三叉树的三个链域。设计算法，对以t为根结点的三叉树进行前序遍历。
13. 简述顺序表和链表存储方式的特点。
算法与数据结构》习题2参***
一、单项选择题。
二、判断题。
三、简答题。
1.答：算法与程序的关系十分密切，但并不等同。
一般来说，一个程序并不需要满足算法的有穷性等条件，例如操作系统的程序，只要整个系统不遭到破坏，操作系统程序就永不结束。另外，程序是用机器可执行的语言书写的，而算法通常没有这种限制。
2. 答：线性表是一个有穷元素的序列。
**性表中，有且仅有一个开始结点和一个终端结点。开始结点有一个后继但是没有前驱，终端结点有一个前驱但是没有后继。其他所有结点都有且仅有一个前驱和后继。
算法与数据结构习题
6 页共 8 页。一 单项选择题。1.在数组a8 10中，行列下标从0开始，每一个数组元素占用3个字节存储，所有数据元素相继存放在一个地址连续的存储空间中，则存放该数组至少需要的字节数是 a 6 页共 8 页。算法与数据结构 习题2 一 单项选择题。1.在数组a8 10中，行列下标从0开始，每一个数...
算法与数据结构习题
一 单项选择题。1.在数组a8 10中，行列下标从0开始，每一个数组元素占用3个字节存储，所有数据元素相继存放在一个地址连续的存储空间中，则存放该数组至少需要的字节数是 a 240b 100 c 80d 270 2.如果把由树转换得到的二叉树叫做这棵树所对应的二叉树，则下面结论正确的是 a 等同于该...
算法与数据结构习题
习题3一 单项选择题。1.将一棵有100个结点的完全二叉树从根开始，每层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶子结点的编号为 a 48b 49 c 50d 51 2.在待排序的元素序列基本有序的前提下，效率最高的排序算法是 a 选择排序。b 插入排序。c 快速排序。d 归并排序...