算法与数据结构习题.doc

算法与数据结构习题2一、单项选择题1. 在数组A810中，行列下标从0开始，每一个数组元素占用3个字节存储，所有数据元素相继存放在一个地址连续的存储空间中，则存放该数组至少需要的字节数是（ ）。A240 B100 C80 D270 2. 如果把由树转换得到的二叉树叫做这棵树所对应的二叉树，则下面结论正确的是（ ）。 A等同于该二叉树对应的树林结点的先根次序序列 B等同于该二叉树对应的树林结点的后根次序序列 C等同于该二叉树对应的树林结点的层次次序序列 D不等于上述任何一种序列3. 哈夫曼树可应用于（ ）。 A组织文件索引 B动态存储管理 C字符串的模式匹配算法 D外排序中确定二路并归的最佳归并次序4. 中缀表达式A*(B+C)/(D-E+F)的后缀表达式为（ ）。AA*B+C/D-E+F BAB*C+D/E-F+CABC+*DE-F+/ DABCDEF*+/-+5连续存储设计时，存储单元的地址（ ）。A一定连续 B一定不连续 C不一定连续 D部分连续，部分不连续6. 比较次数与排序码的初始排列状态无关的排序算法是（ ）。A直接插入排序 B直接选择排序 C快速排序 D归并排序7. 一个具有n个顶点的连通无向图的生成树中有（ ）条边。An-1 Bn Cn/2 Dn+18. 设计最佳二叉排序树的构造算法的主要技术是（ ）。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 k=1;While(kend）return -1; /*转换失败*/If（start= =end）return send-0; /*只有一个字符，直接转换*/Return stringTolnt1(s,start,end-1)*10+send-0;/*先转换其他位，再转换末位*/ Int stringTolnt(char *s) Int i=0; While (si!=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+n1+n+n1+n+2n+1+1+1+1=3n3+3n2+4n+2=O（n3）4. 答：优点：1.插入和删除比较灵活，不需要大量移动结点。 2.动态分配空间比较灵活，不需要预先申请最大的连续空间。 缺点：1.增加指针的空间开销 2.检索必须沿链进行，不能随机存取。5. 答：（1）堆排序 （2）快速排序 （3）归并排序 （4）归