数据结构期末考试题答案详细讲解

《数据结构》试题（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. 用三元组表表示下列稀疏矩阵：

下载可编辑

000002000090000000

005000

000000000030

38. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。

39. 把如图所示的树转化成二叉树。

.专业.整理.

40. 已知如图所示的有向图，请给出该图的邻接表。 41. 请对下图的无向带权图，求其最小生成树；

下载可编辑

得分 评卷人 五、试题类型：分析题（每小题5分，共5分） （类型说明： ）

42. 已知一组关键字序列： 49 38 65 97 13 27 按照快速排序方法对此序列进行排序，写出每趟排序的结果。 得分 评卷人 六、试题类型：编程题（每小题5分，共5分） （类型说明： ）

43. 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。顺序表的存储结构如下： typedef struct {

ElemType *elem; //指向存放线性表中数据元素的基地址 int length; //线性表的当前长度

int listsize; //当前分配的存储容量 }SqList；

Status InsertSqList(SqList &va,int x)//把x插入递增有序表va中

.专业.整理.

{ if(va.length+1>va.listsize) return ERROR;

《数据结构》A卷信管本科专业标准答案及评分标准（按试题顺序排列）

一、单项选择题（每小题2分，共40分）

1、A 2、C 3、C 4、 B 5、A 6、D 7、B 8、C 9、B 10、D 11、A 12、C 13、C 14、A 15、D 16、A 17、A 18、B 19、C 20、C

二、判断题（每小题1分，共10分）

21. A 22. B 23. B 24. A 25. B 26. B 27. B 28. A 29. B 30. B 三、填空题（每空1分，共10分） 31. 栈顶 栈底 32. n-i+1

33. n-i

34. 288 B 1282 1072 1276 35. 20 3

四、简答题（每小题5分，共30分）

36. Loc(aij)= Loc(a11) +[ (i-1)*m+(j-1) ] * K

下载可编辑

37. 6 6 4 1 6 -2 2 5 9 4 3 5 6 5 3

38.

先序： A B D F J G K C E H I L M---------2分 中序: B F J D G K A C H E L I M----------2分 后序： J F K G D B H L M I E C A----------1分 39.

40.

41.

.专业.整理.

五、试题类型：分析题（每小题5分，共5分）

42. 初始序列：49 38 65 97 13 27

第一趟排序结果：27 38 13 49 97 65 第二趟排序结果：13 27 38 49 65 97 六、试题类型：编程题（每小题5分，共5分）

43. va.length++;

for(i=va.length-1;va.elem[i]>x&&i>=0;i--)

va.elem[i+1]=va.elem[i]; va.elem[i+1]=x; return OK; }

《数据结构》试题（100分）

（供2005级信息管理与信息系统本科专业使用）

学号： 姓名： 座号： 系别： 年级： 专业：

下载可编辑

题号 一 二 三 四 五 六 七 八 总计 得分 总分合计人： 复核人：

说明：本试卷分为两部分，第I卷（选择题和判断题）必须在“答题卡”上按规定要求填、涂；第II卷直接在试卷上作答。不按规定答题、填涂，一律无效。

第I卷

得分 评卷人 一、试题类型：单项选择题（每小题2分，共40分）

（类型说明：在每小题列出的四个选项中只有一个选项是符合题目要求的，请选出正确选项并在“答题卡”的相应位置上涂黑。多涂、少涂、错误均无分。）

1. 非线性结构是数据元素之间存在一种 。 ( )

(A) 一对多关系 (B) 多对多关系 (C) 多对一关系 (D) 一对一关系 2. 数据结构中，与所使用的计算机无关的是数据的 结构。 ( )

（A） 存储 （B） 物理 （C） 逻辑 （D） 物理和存储 3. 算法分析的两个主要方面是 。 （ ）

（A） 空间复杂性和时间复杂性 （B） 正确性和简明性

（C） 可读性和文档性 （D） 数据复杂性和程序复杂性

4. 计算机算法指的是 。 ( )

（A） 计算方法 （B） 排序方法 （C） 解决问题的有限运算序列 （D） 调度方法

5. 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之

为 。 ( ) （A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构 6. 一个向量第一个元素的存储地址是500，每个元素的长度为2，则第10个元素的地址

是 。 ( ) （A）510 （B）508 （C）518 （D）520 7. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是 。 ( )

（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B）在第i个结点后插入一个新结点（1≤i≤n） （C）删除第i个结点（1≤i≤n） （D）将n个结点从小到大排序

.专业.整理.

8. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址 。( )

（A）必须是连续的 （B）部分地址必须是连续的 （C）一定是不连续的 （D）连续或不连续都可以 9. 线性表Ｌ在 情况下适用于使用链式结构实现。 ( )

（Ａ）需经常修改Ｌ中的结点值 （Ｂ）需不断对Ｌ进行删除插入 （Ｃ）Ｌ中含有大量的结点 （Ｄ）Ｌ中结点结构复杂 10. 栈中元素的进出原则是 。 ( )

(Ａ) 先进先出 (Ｂ) 后进先出 (Ｃ) 栈空则进 (Ｄ) 栈满则出 11. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，

若p1=n，则pi为 。 ( ) （Ａ） i （Ｂ） n=i （Ｃ） n-i+1 （Ｄ） 不确定 12. 设有两个串p和q，求q在p中首次出现的位置的运算称作 。 ( )

（Ａ） 连接 （Ｂ） 模式匹配 （Ｃ） 求子串 （Ｄ） 求串长 13. 串是一种特殊的线性表，其特殊性体现在 。 ( )

（Ａ） 可以顺序存储 （Ｂ） 数据元素是一个字符 （Ｃ） 可以链式存储 （Ｄ） 数据元素可以是多个字符

14. 假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为

10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为 。（无第0行第0列元素） ( ) （Ａ） 16902 (Ｂ) 16904 (Ｃ) 17262 (Ｄ) 答案A, B, C均不对 15. 二叉树是非线性数据结构，所以 。 ( )

（Ａ）它不能用顺序存储结构存储; （Ｂ）它不能用链式存储结构存储; （Ｃ）顺序存储结构和链式存储结构都能存储; （Ｄ）顺序存储结构和链式存储结构都不能使用

16. 具有n(n>0)个结点的完全二叉树的深度为 。 ( )

(Ａ) log2(n) (Ｂ)  log2(n) (Ｃ)  log2(n) +1 (Ｄ) log2(n)+1 17. 对22个记录的有序表作折半查找，当查找失败时，至少需要比较 次关键字。

( )

(A) 3 (B) 4 (C) 5 (D) 6 18. 链表适用于 查找。 ( ) (A) 顺序 (B) 二分法 (C) 顺序，也能二分法 (D) 随机 19. 堆的形状是一棵 。 ( )

(Ａ) 二叉排序树 (Ｂ) 满二叉树 (Ｃ) 完全二叉树 (Ｄ) 平衡二叉树 20. 下列关键字序列中， 是堆。 ( )

下载可编辑

(Ａ) 16, 72, 31, 23, 94, 53 (Ｂ) 94, 23, 31, 72, 16, 53 (Ｃ) 16, 53, 23, 94，31, 72 (Ｄ) 16, 23, 53, 31, 94, 72 得分 评卷人 二、试题类型：判断题（每小题1分，共10分） （类型说明：判断正确答案，选项并在“答题卡”的相应位置填涂，认为正确的涂“A”错误的涂“B ”。多涂、少涂、错误均无分。）

21. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 ( )

22. 顺序存储方式只能用于存储线性结构。 ( ) 23. 线性表的逻辑顺序与存储顺序总是一致的。 ( ) 24. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结

构。 ( ) 25. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 ( ) 26. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指

针域。 ( ) 27. 对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i

—1个结

点。 ( ) 28. 用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中 有n+1个为空指针。 （ ）

29. 二叉树中每个结点的两棵子树是有序的。 （ ）30. 二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。 （ ）第II卷

得分 评卷人 三、试题类型：填空题（每小题1分，共20分） （类型说明：请将正确答案填于试题预留的横线上。）

31. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的 有

限集合。

32. 数据结构包括数据的逻辑结构、数据的存储结构和数据的 这三个方面的内容。

.专业.整理.

33. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和 。 34. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结

构中元素之间存在 关系。

35. 在 中，第一个结点没有前驱结点，其余每个结点有且只有 1个前驱结

点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。

36. 在 中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；

叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 37. 在图形结构中，每个结点的前驱结点数和后续结点数可以 。

38. 数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 、 链式 、 索引

和 。

39. 一个算法的效率可分为 效率和空间效率。

40. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重

新排列，则冒泡排序一趟扫描的结果是 。

41. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 。 42. 线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法

检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 次。 43. 假设在有序线性表a[20]上进行折半查找，平均查找长度为 。

下载可编辑

44. 散列法存储的基本思想是由 决定数据的存储地址。 45. 有8个结点的无向连通图最少有 条边。

46. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 47. 在一个图中，所有顶点的度数之和等于图的边数的 倍。 48. 在具有n个单元的循环队列中，队满时共有 个元素。 49. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 。

50. 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线

性表。 得分 评卷人 四、试题类型：综合题（每小题5分，共25分） （类型说明： ）

51. 请对下图的无向带权图，写出它的邻接矩阵，并按普里姆算法求其最小生成树；

52. 写出下图AOE-网的关键路径。

.专业.整理.

53. 写出下图的拓扑排序序列。

54. 已知某二叉树的中序遍历序列结点序列是B F J D G K A C H E L I M、后序遍历结

下载可编辑

点序列J F K G D B H L M I E C A是，试写出其先序遍历结点序列并画出此二叉树。 （类型说明： ）

55. 下图是某树的二叉树表示法，试画出此树。

A B E C K F H D

L G I M J 得分 评卷人 五、试题类型：编程（每小题5分，共5分）

56. 已知11个元素的有序表为（05 13 19 21 37 56 64 75 80 88 92）, 请

写出折半查找的算法程序，查找关键字为key的数据元素。

.专业.整理.

下载可编辑

《数据结构》B卷信管本科专业标准答案及评分标准（按试题顺序排列）

一、单项选择题（每小题2分，共40分）

1. B 2. C 3. A 4. C 5. C 6. C 7. A 8. D 9. B 10. B 11. C 12. B 13. B 14. C 15. C 16. C 17. C 18. A 19. C 20. D 二、判断题（每小题1分，共10分）

21. B 22. B 23. B 24. A 25. B 26. A 27. B 28. A 29. A 30. B

三、填空题（每小题1分，共20分）

31. 关系 32. 运算

33. 非线性结构 34. 多对多 35. 线性结构 36. 树形结构 37. 任意多个 38. 散列 39. 时间

40. H C Q P A M S R D F X Y 41．顺序查找（线性查找） 42. 8 43. 3.7

44. 关键字的值 45. 7 46．1 47. 2 48. n-1 49. 栈顶 50. 队列

四、综合题（每小题5分，共25分）

51.

043

 4055 35 5059075

9570634 63052 55420660

.专业.整理.

下载可编辑

52. 有两条关键路径（v1,v2,v5,v7,v9）和（v1.v2.v5.v8.v9），写出一种即可。

53. 拓扑排序序列有（v5，v1，v3，v4，v2，v6），（v1，v5，v3，v4，v2，v6），（v1，

v4，v2，v5，v3，v6）等，写出一种即可。 54.

DLR：A B D F J G K C E H I L M

55.

五、试题类型：编程（每小题5分，共5分） 56.解：

折半查找的一个递归算法如下：

int Search_Bin_Recursive(SSTable ST, int key, int low, int high) //找的递归算法

{

if(low>high) return 0; mid=(low+high)/2;

if(ST.elem[mid].key= =key) return mid; else if(ST.elem[mid].key>key)

return Search_Bin_Recursive(ST, key, low, mid-1); else return Search_Bin_Recursive(ST, key, mid+1, high); }

.专业.整理.

折半查