数据结构期末考试试题答案详解.doc

《数据结构》试题（ 100 分） （供 2005 级信息管理与信息系统本科专业使用） 学号： 姓名： 座号： 系别： 年级： 专业：  说明：本试卷分为两部分， 第 I 卷（选择题和判断题） 必须在 “答题卡” 上按规定要求填、涂；第 II 卷直接在试卷上作答。不按规定答题、填涂，一律无效。 I 卷 得分 评卷人 一、试题类型：单项选择题（每小题 2 分，共 40 分） （类型说明：在每小题列出的四个选项中只有一个选项是符合 题目要求的，请选出正确选项并在“答题卡”的相应位置上涂 黑。多涂、少涂、错误均无分。 ） 1. 算法分析的两个主要方面是： 题号 一 二 三 四 五 六 七 八 总计 （ ） 得分 （ A) 空间复杂性和时间复杂性 （ B) 正确性和简明性 总分合计人： 复核人： （ C) 可读性和文档性 （ D) 数据复杂性和程序复杂性 2. 计算机算法指的是： （ ） （ A) 计算方法 （ B) 排序方法 （ C) 解决问题的有限运算序列 （ D) 调度方法 3． 数据在计算机存储器内表示时， 物理地址与逻辑地址相同并且是连续的， 称为：（ ） （A）存储结构 （B）逻辑结构 （C）顺序存储结构 （ D）链式存储结构 4. 一个向量第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是 。 （ ） （A） 110 （ B）108 （ C）100 （ D） 120 5. 链接存储的存储结构所占存储空间： （ ） （A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B）只有一部分，存放结点值 （C） 只有一部分，存储表示结点间关系的指针 （D） 分两部分，一部分存放结点值，另一部分存放结点所占单元数 6. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址 : （ ） （A）必须是连续的 （ B）部分地址必须是连续的 （C）一定是不连续的 （ D）连续或不连续都可以 7. 栈中元素的进出原则是： （ ） （Ａ）先进先出 （Ｂ）后进先出 （Ｃ）栈空则进 （Ｄ）栈满则出 8. 若已知一个栈的入栈序列是 1， 2，3， ， n，其输出序列为 p1，p2， p3， ， pn，若 p1=n，则 pi 为： （ ） （Ａ） i （Ｂ） n=i （Ｃ） n-i+1 （Ｄ） 不确定 9. 串是一种特殊的线性表，其特殊性体现在： （ ） （Ａ）可以顺序存储 （Ｂ）数据元素是一个字符 （Ｃ）可以链式存储 （Ｄ）数据元素可以是多个字符 10. 设串 s1=‘ABCDEFG’，s2=‘PQRST’，函数 con(x,y) 返回 x 和 y 串的连接串， subs(s, i, j) 返回串 s 的从序号 i 开始的 j 个字符组成的子串， len(s) 返回串 s 的长度，则 con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2)) 的结果串是： （ ） （Ａ） BCDEF （Ｂ） BCDEFG （Ｃ） BCPQRST （Ｄ） BCDEFEF 假设有 60 行 70 列的二维数组 a[1 60, 1 70] 以列序为主序顺序存储，其基地址为 10000，每个元素占 2 个存储单元，那么第 32 行第 58 列的元素 a[32,58] 的存储地址 为 。（无第 0 行第 0 列元素） （ ）  （Ａ） 16902 （Ｂ） 16904 （Ｃ） 14454 （Ｄ）答案 A, B, C 均不对 12．二叉树是非线性数据结构，所以 。 （ ） （Ａ）它不能用顺序存储结构存储 ; （Ｂ）它不能用链式存储结构存储 ; （Ｃ）顺序存储结构和链式存储结构都能存储 ; （Ｄ）顺序存储结构和链式存储结构都不能使用 13. 具有 n(n0) 个结点的完全二叉树的深度为 。 （ ） ( Ａ ) log 2(n) ( Ｂ ) log 2(n) ( Ｃ ) log 2(n) +1 ( Ｄ ) log 2(n)+1 14．把一棵树转换为二叉树后，这棵二叉树的形态是 。 （ ） （Ａ）唯一的 （Ｂ）有多种 （Ｃ）有多种，但根结点都没有左孩子 （Ｄ）有多种，但根结点都没有右孩子 15. 已知图的邻接表如下所示，则从顶点 0 出发按深度优先遍历的结点序列是 （ ） （ A） 0 1 3 2 （ B） 2 0 3 1 （ C） 1 3 2 0 （ D） 0 1 2 3 16. 已知图的邻接表如下所示，根据算法，则从顶点 0 出发按广度优先遍历的结点序列是 （ ） （ A） 0 3 2 1 （ B） 1 2 3 0 （ C） 3 2 1 0 （ D） 3 0 1 2 17．折半查找有序表（ 4，6， 10，12， 20， 30，50，70， 88