一、单项选择题。
1. 在数组a8×10中，行列下标从0开始，每一个数组元素占用3个字节存储，所有数据元素相继存放在一个地址连续的存储空间中，则存放该数组至少需要的字节数是（ ）
a．240b．100
c．80d．270
2. 如果把由树转换得到的二叉树叫做这棵树所对应的二叉树，则下面结论正确的是（ ）
a．等同于该二叉树对应的树林结点的先根次序序列。
b．等同于该二叉树对应的树林结点的后根次序序列。
c．等同于该二叉树对应的树林结点的层次次序序列。
d．不等于上述任何一种序列。
3. 哈夫曼树可应用于（ ）
a．组织文件索引。
b．动态存储管理。
c．字符串的模式匹配算法。
d．外排序中确定二路并归的最佳归并次序。
4. 中缀表达式a*(b+c)/(d-e+f)的后缀表达式为（ ）
a．a*b+c/d-e+f
b．ab*c+d/e-f+
c．abc+*de-f
d．abcdef*+/
5．连续存储设计时，存储单元的地址（ ）
a．一定连续。
b．一定不连续。
c．不一定连续。
d．部分连续，部分不连续。
6. 比较次数与排序码的初始排列状态无关的排序算法是（ ）
a．直接插入排序。
b．直接选择排序
c．快速排序。
d．归并排序。
7. 一个具有n个顶点的连通无向图的生成树中有（ ）条边。
a．n-1b．n
c．n/2d．n+1
8. 设计最佳二叉排序树的构造算法的主要技术是（ ）
a．分治法。
b．贪心法。
c．动态规划法。
d．分支限界法。
二、多项选择题。
1. 下列属于算法的重要特征的是（ ）
a. 有穷性。
b. 确定性。
c. 可行性。
d. 输入和输出。
2. 图的四种存储结构包括（ ）
a. 邻接矩阵。
b. 邻接表。
c. 邻接多重表。
d. 十字链表。
3. 下列说法正确的有：（
a. 算法和程序原则上没有区别，在讨论数据结构时二者通用。
b. 从逻辑关系上讲，数据结构分为两大类：线性结构和非线性结构。
c. 所谓数据的逻辑结构是指数据元素之间的逻辑关系。
d. 同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数相等。
e. 数据的逻辑结构与数据元素本身的内容和形式无关。
f. 数据结构是指相互之间存在一种或多种关系的数据元素的全体。
4. 线性表的特点正确的（ ）
a. 存在唯一的一个被称作“第一个”的数据元素。
b. 不存在唯一的一个被称作“第一个”的数据元素。
c. 存在唯一的一个被称作“最后一个”的数据元素。
d. 不存在唯一的一个被称作“最后一个”的数据元素。
三、填空题。
1. 在n个结点的单链表中要删除已知结点*p，需找到它的___的地址，其时间复杂度为___
2．在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较___次。
3. 数据的存储结构可用四种基本的存储方法表示，其中三种分别是任选三种）
4．某线性表采用顺序存储结构，每个元素占据4个存储单元，首地址为100，则下标为11（第12个）的元素的存储地址为___
四、判断题。
1. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（
2. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。（
3. 任意图都是其自身的子图。（
4. 如果图中有一部分边的权为负值，那么用dijkstra算法求图的最短路径是可行的。（
5．算法的优劣与算法描述语言无关，但与所用计算机有关。（
6．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（
7. 算法可以用不同的语言描述，如果用c语言或pascal语言等高级语言来描述，则算法实际上就是程序了。（
五、简答题。
1．什么是索引文件？它有什么特点？
2. 写一个递归算法，用来把整数字符串转换为整数。例如：“43567”->43567。
3．计算下列程序片段的时间代价（写明计算步骤）。
int i=1;
while (i<=n)
int j =1;
while(j<=n)
int stringtolnt(char *s)+1=3n3+3n2+4n+2=o（n3）
4. 答：优点：1.插入和删除比较灵活，不需要大量移动结点。
2.动态分配空间比较灵活，不需要预先申请最大的连续空间。
缺点：1.增加指针的空间开销。
2.检索必须沿链进行，不能随机存取。
5. 答：1）堆排序
2）快速排序
3）归并排序
4）归并排序
5）堆排序。
6）快速排序
7）堆排序。
6. 答：规定根的层数为0，其余结点的层数等于其父结点的层数加1.二叉树中结点的最大层数称为二叉树的高度。
7. 答：排序过程中，数据全放在内存中处理的排序方法称为“内排序”。
算法与数据结构习题
一 单项选择题。1 算法的时间复杂度的表示方法是 a 实现算法的程序在指定机器上执行的时间。b 标准程序在机器上的执行时间。c 基本操作重复次数，即问题规模n的某个函数。d 与刻画基本操作重复次数的函数同阶无穷大的函数f n 2 在一个双向链表中，假设结点的域分别为left,right,以及data...
算法与数据结构习题
6 页共 8 页。一 单项选择题。1.在数组a8 10中，行列下标从0开始，每一个数组元素占用3个字节存储，所有数据元素相继存放在一个地址连续的存储空间中，则存放该数组至少需要的字节数是 a 6 页共 8 页。算法与数据结构 习题2 一 单项选择题。1.在数组a8 10中，行列下标从0开始，每一个数...
算法与数据结构习题
习题3一 单项选择题。1.将一棵有100个结点的完全二叉树从根开始，每层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶子结点的编号为 a 48b 49 c 50d 51 2.在待排序的元素序列基本有序的前提下，效率最高的排序算法是 a 选择排序。b 插入排序。c 快速排序。d 归并排序...