《数据结构》考试及答案

姓名 学号 。 分数 。 一、 单项选择题（每小题2分，共26分）

1、A 2、C 3、D 4、A 5、D 6、C 7、B 8、A 9、B 10、A 11、D 12、D 13 1。 数据结构是指（ ）。

A。数据元素的组织形式 B。数据类型 C。数据存储结构 D。数

据定义

2。 数据在计算机存储器内表示时,物理地址与逻辑地址不相同的,称之为（ ）。

A。存储结构 B.逻辑结构 C.链式存储结构 D。顺序存储结构

3。 树形结构是数据元素之间存在一种（ ）.

A。一对一关系 B.多对多关系 C。多对一关系 D。一对

多关系

4. 在一个长度为n的顺序表中删除第i个元素(0〈=i〈=n)时，需向前移动 个元素.

A．n—i B．n-i+l C．n—i—1 D．i 5。 线性表采用链式存储时，其地址________。

A．必须是连续的 B．一定是不连续的 C．部分地址必须是连续的 D．连续与否均可以 6。下图所示的是线性表的链接存储结构,采用的是（ ）链表.

H

a1 a2 … an

A。 单链表 B. 十字链表 C.双链表 D。循环链表

7。 一个二叉树按顺序方式存储在一个维数组中,如图

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I J 则结点E在二叉树的第（ ）层。

A。 1 B。 2 C. 3 D.4

8．线性表采用链式存储时,结点的存储地址（ ）

A．连续与否均可 B．必须是不连续的

C．必须是连续的 D．和头结点的存储地址相连续 9．空串与空格字符组成的串的区别在于( ）。 A。没有区别 B.两串的长度不相等

C。两串的长度相等 D。两串包含的字符不相同

10．栈和队列的共同特点是（ ）。

A.只允许在端点处插入和删除元素 B。都是先进后出 C.都是先进先出 D。没有共同点

11．用链接方式存储的队列，在进行插入运算时( D ）。

A。 仅修改头指针 B。 头、尾指针都要修改 C。 仅修改尾指针 D.头、尾指针可能都要修改

12． 以下数据结构中哪一个是非线性结构？（ d ）

A。 队列 B。 栈 C. 线性表 D. 二叉树

13． 二叉树的第k层的结点数最多为( D )。

A．2k-1 B.2K+1 C。2K—1 D。 2k-1

二、填空题（每空2分，共32分）

1. 一维数组的逻辑结构是__线性____，存储结构是____顺序存储____；对于二维或多维数组,分为____顺序____和_____链式______两种不同的存储方式.

2.栈是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除操作，进行操作的这一端称为 栈顶 ，与其对应的另一端称为 栈底 。

3. 在树型结构中，树根结点没有_____后继_____结点，其余每个结点的有且只有___1__个前趋驱结点；叶子结点没有_____子____结点;其余每个结点的后续结点可以____有多个结点______。

4。 线性结构中元素之间存在___一对一____关系;树型结构中元素之间存在__一对多_______关系。

5. 一棵深度为k的满二叉树的结点总数为__ (2^h）—1 ___，一棵深度为k的完全二叉树的结点总数的最小值为__（2^h）—1__,最大值为__(2^h)—1_.

6. 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEFG，则该二叉树的前序遍历序列为_ABDECFG___.

三、判断题（每题1分,共8分）

1、× 2、√ 3、√ 4、× 5、× 6、× 7、× 8、√ 1。 数组可看作基本线性表的一种推广，因此与线性表一样,可以对它进行插入、删除等操

作.（ ）

2。 对于不同的特殊矩阵应该采用不同的存储方式。( )

2

3。 采用压缩存储之后，下三角矩阵的存储空间可以节约一半。( )

4. 在一般情况下，采用压缩存储之后，对称矩阵是所有特殊矩阵中存储空间节约最多的。（ )

5。 距阵中的数据元素可以是不同的数据类型。（ ） 6. 矩阵中的行列数往往是不相等的.（ ）

7．线性表的顺序存储结构比链式存储结构更好。（ ）

8．不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（ )

四、名词解释（每题4分,共16分）

1． 数据结构

2． 线性表

3。树

4.矩阵

五、解答题（每题6分，共18分） 1.循环队列如何判断队满和队空？

第 3 页 共 4页 2.请分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

3。请写出与下列二叉树前(先）序遍历序列。

2 第 4页 共 4页