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

《数据结构》试题（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)个结点的完全二叉树的深度为 。 （ ）

(Ａ) 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，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/”，则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(+1>ze) 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.

++;

for(i=-1;[i]>x&&i>=0;i--)

[i+1]=[i];

[i+1]=x;

return OK; }

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

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

学号： 姓名： 座号：

系别： 年级： 专业：