算法与数据结构习题2
《算法与数据结构》习题2
一、单项选择题
1. 在数组A 8×10中，行列下标从0开始，每一个数组元素占用3个字节存储，所有数据元素相继存放在一个地址连续的存储空间中，则存放该数组至少需要的字节数是（ ）。
A ．240 B ．100
C ．80 D ．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-1
B ．n C ．n/2
D ．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
Int j =1; While(j
Int k=1; While(k
Printf(‚i=%d,j=%d,k=%d\n‛,i,j,k); K=k+1; } J=j+1; } i=i+1; }
4. 链接存储的优缺点分别是什么？
5. 在堆排序、快速排序和归并排序这三种中，若只从存储空间考虑，则应该首
选_______,其次选取_______算法，最后选取_______算法；若只从排序结果的稳定性来考虑，则应该选取_______算法，其次选取_______算法，最后选取_______算法。若只从最坏情况下排序要快，并且要节省内存考虑，则选择_______算法。 6. 什么是二叉树的高度？ 7. 什么是内排序？
《算法与数据结构》习题2答案
一、单项选择题
二、多项选择题
三、填空题
四、判断题
五、简答题
1. 答：索引表是由索引组成的表，每个索引项是一条记录的关键码和指向该记录的指针组成的二元组。实际中的索引表是很大的，需要存放在外存储器上，因此索引表也是一种文件。索引表本身可以用不同的方式来组织。主文件的记录可以在外存储器上按关键码的顺序排列，也可以不按关键码的顺序排列。 2. 答：先递归调用本算法，以转换除去末位外剩余的字符串，结果乘以10；再转换末位。将两结果相加即为所求。
Int stringTolnt1(char *s, int start, int end){ /*把整数字符串s 中从start 到end 的部分转换为整数*/ If （start>end）return -1; /*转换失败*/
If （start= =end）return s[end]-‘0’; /*只有一个字符，直接转换*/ Return stringTolnt1(s,start,end-1)*10+s[end]-‘0’; /*先转换其他位，再转换末位*/ }
Int stringTolnt(char *s){ Int i=0;
While (s[i]!=’\0’)i++; /*计算字符串的长度*/
Return stringTolnt1(s,0,i-1) }
3. 答：循环控制变量i 从1增加到n ，最外层循环体执行n 次，循环控制变量j 从1增加到n ，中间层循环体执行n*i，循环控制变量k 从1增加到n ，最内层循环体执行n 次，所以该程序段总的时间代价为
T(n)=1+n+n{1+n+n[1+n+2n+1]+1+1}+1=3n3+3n2+4n+2=O（n 3） 4. 答：优点：1. 插入和删除比较灵活，不需要大量移动结点。
2.动态分配空间比较灵活，不需要预先申请最大的连续空间。 缺点：1. 增加指针的空间开销
2.检索必须沿链进行，不能随机存取。 5. 答： （1）堆排序 （2）快速排序 （3）归并排序 （4）归并排序 （5）堆排序 （6）快速排序 （7）堆排序
6. 答：规定根的层数为0，其余结点的层数等于其父结点的层数加1. 二叉树中结点的最大层数称为二叉树的高度。
7. 答：排序过程中，数据全放在内存中处理的排序方法称为‚内排序‛。