内容发布更新时间 : 2024/5/19 23:57:06星期一 下面是文章的全部内容请认真阅读。
《数据结构》试题（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
11. 假设有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(n>0)个结点的完全二叉树的深度为 。 （ ）
(Ａ) ?log2(n)? (Ｂ) ? log2(n)? (Ｃ) ? log2(n) ?+1 (Ｄ) ?log2(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，100）。若查找表中元素58，则它将依次与表中 比较大小，查找结果是失败。 （ ） （A）20，70，30，50 （B）30，88，70，50 （C）20，50 （D）30，88，50
18．链表是一种采用 存储结构存储的线性表。 （ ）
（A）顺序 （B）链式 （C）星式 （D）网状
19．不含任何结点的空树 。 （ ） （Ａ）不是一棵树; （Ｂ）不是一棵二叉树; （Ｃ）是一棵树也是一棵二叉树; （Ｄ）既不是树也不是二叉树 20．在一个图中，所有顶点的度数之和等于图的边数的 倍。 （ ）
A．1/2 B. 1 C. 2 D. 4 得分 评卷人 二、试题类型：判断题（每小题1分，共10分）
（类型说明：判断正确答案，选项并在“答题卡”的相应位置填涂，认为正确的涂“A”错误的涂“B ”。多涂、少涂、错误均无分。）
21. 二叉树中每个结点的两棵子树是有序的。 （ ）22. 顺序存储方式只能用于存储线性结构。 （ ）23. 二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。 （ ）
24. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ ）25. 二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （ ）
26. 队列是一种先进后出型结构。 （ ）27. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 （ ）28. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先
出型结构。（ ）
29. 线性表在物理存储空间中也一定是连续的。 （ ）30. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
（ ）
第II卷
得分 评卷人 三、试题类型：填空题（每空1分，共10分） （类型说明：请将正确答案填于试题预留的横线上。）
31. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 。不允许插入和删除运算的一端称为 。
32. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 个元素。
33. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动 个元素。
34. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 ；末尾元素A57的第一个字节地址为 ；若按行存储时，元素A14的第一个字节地址为 ；若按列存储时，元素A47的第一个字节地址为 。
35. 设S=“A;/document/Mary.doc”，则strlen(s)= , “/”的字符定位的位置为 。
得分 评卷人 四、试题类型：简答题（每小题5分，共30分） （类型说明： ）
36. 已知二维数组Am,m采用按行优先顺序存放，每个元素占K个存储单元，并且第
一个元素的存储地址为Loc(a11)，请写出求Loc(aij)的计算公式。
37. 用三元组表表示下列稀疏矩阵：