算法和数据结构习题2.doc

第  PAGE 8 页 共  NUMPAGES 8 页 《算法与数据结构》习题2 一、单项选择题 1. 在数组A8×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．算法的优劣与算法描述语言无关，但与所用计算机有关。（