数据结构自测试题及答案

数据结构自测题1

一、 单项选择题

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

Ａ.必须是连续的 Ｂ.部分地址必须是连续的 C.一定是不连续的D．连续不连续都可以

2。在单链表中，增加头结点的目的是为了( C ）

A．使单链表至少有一个结点 Ｂ．表示表结点中首结点的位置

C.方便运算的实现 Ｄ．说明单链表是线性表的链式存储实现

3．设栈Ｓ和队列Q的初始状态为空，元素e1、ｅ2、e3、ｅ4、e5和ｅ６依次通过栈S,一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e３、ｅ６、e5、e1，则栈Ｓ的容量至少应是( B ）Ａ.2 B.３ C．４ Ｄ.５

4.树结构中,前驱结点与后继结点之间存在（ ﻩB )关系.

Ａ.一对一 B.一对多 C.多对一 Ｄ．多对多

5。堆栈的特性描述是（ B ）。A.FIFO B．FＩLＯ C.FIFO和FIＬＯ D．FIFO或FILO

6。队列的特性描述是( Ａ ）。A．FIFO B．FILＯ C.ＦＩＦＯ和FILＯ D.FIFO或FILO

7。下列数据结构中，是非线性结构的是( A ）A.树 B.堆栈 C．队列 D.循环队列

8.设某个初始为空的容纳ｉｎt型数据的堆栈进行了如下操作（每一步均未发生溢出):push(１)、push(３）、pop(）、ｐuｓh(６)、puｓh(１）、poｐ(）、pｕsh（3)、pｕｓh(８) 后,该堆栈中从栈顶到栈底的元素依次为（ D ）A．8 1 8 ３ B．１ 3 １ 8 C．1

６ 3 8 Ｄ．8 3 6 １

二、 判断题

1．二叉树可以为空树．（ √ ) 2。顺序表和链表都是线性表.( √ )

3。线性表的长度是线性表占用的存储空间的大小。(√）4。队列只能采用链式存储方式。（×)

5。由二叉树的先序序列和中序序列能唯一确定一棵二叉树。(√）

6。存在有偶数个结点的满二叉树。(×）

三、 填空题

1。数据结构是数据在计算机内的 组成形式 和 相互关系 。

2．二叉树的三种遍历方式分别为 中序遍历 、 先序遍历 和 后序遍历 。

３。深度为Ｋ的满二叉树共有 2k－１ 个结点。

４。N个顶点的无向图是完全图的条件是其边数为 n （ n－１ ） / 2 。

四、 名词解释

1。ADT ADＴ是抽象数据类型的简称,指一个数学模型以及定义在该模型上的一组操作.

2．栈 栈是限定仅在表尾进行插入或删除操作的线性表，具有先进后出（FIＬO)的特性。

3.队列 队列是只允许在表的一端进行插入操作,而在另一端进行删除操作的线性表，具有先进先出（ＦIFO)的特性。

五。简答题

1。分别写出下图所示二叉树的先序遍历、中序遍历和后序遍历序列

中序遍历: F G Ｃ E H Ｂ D J I A L Ｎ P Ｏ Q M K 先序遍历: A B C

Ｆ G Ｅ H D I J K L Ｍ N O P Ｑ 后序遍历: Ｇ F H E C Ｊ Ｉ D B P Q

O Ｎ Ｍ L K A

2.用邻接矩阵表示下图所示的拓扑(节点已标号）。

数据结构自测题2

一．单项选择题

1。设某个初始为空的容纳inｔ型数据的非循环队列进行了如下操作(每一步均未发生溢出)：inqueue(1）、iｎqｕeｕe (3）、ｄeｑuｅue(）、inqueuｅ (6）、inqｕeuｅ (1）、ｄequeue（)、inqueue

(3)、inqueｕe （8） 后,该队列中从队尾到队首的元素依次为（ C )

A．１ 6 3 ８ B.6 1 3 ８ C．8 3 1 6 Ｄ.8 3 6 1

２.最多3个结点的二叉树共有(A)种不同的形态(不区分结点)。A.5 Ｂ．4 C．３ D．2 A

B

C

D

E F G H I

J

K

L

M

N

O

P

Q

1

2 4

3 5

0 1 0 0 1

1 0 1 1 0

0 1 0 0 1

0 1 0 0 0

1 0 1 0 0 3．串的长度是（ D ) A.串中不同字符的数目

B．串中不同字母的数目C.串中所含单词的数目 D.串中所含字符的数目

4。树的度规定为（D）A结点度之和B结点度的平均值 C结点度的最小值 D．结点度的最大值

5.线性表的顺序存储结构是一种（A)存取的存储结构。A．顺序 B.随机 C．索引 D.散列

6。在单向链表的第i个结点前插入新结点时，需预先保留的结点指针是(A ）D．无需保留

A.指向i结点的指针 B．指向i结点的前趋结点的指针 Ｃ．指向i结点的后继结点的指针设7.一个栈的进栈序列是ABCD,在进栈过程中允许出栈,且每个元素进栈出栈均各一次，则不可能得到的出栈序列是（ D ) .A．ABDＣ B．DCBA C．CDＢA Ｄ.CＤAB

8.下列说法正确的是（ Ｂ ) ．

Ａ．冒泡排序算法不是稳定的 B．快速排序是对冒泡排序的一种改进

C.外部排序指对数据元素序列的整个排序过程都在计算机内存中进行的排序

D.衡量内部排序算法和外部排序算法效率的方法是相同的

二。判断题

１.树是无圈的图.（ √ ） 2。无向图中所有顶点的度数之和等于边数的两倍.（ √ ）

３.在一棵二叉树中，第５层上的结点数最多为１０个。（×） 4.栈允许在一端进行插入在另一端进行删除.( × ） 5。冒泡排序是一种稳定的排序算法。( √ ）

三。填空题

１.图是 顶点 和 边 的集合. ３.链式存储结构中的结点包括 数据 域和 指针 域。

2．构造Hash表中,处理冲突的办法有再哈希法、 开放定址法 、 链地址法 、 以及建立一个公共溢出区等方法。

四。名词解释

1。串 串又成为字符串，是由零个和多个字符组成的有限序列。

2.排序 排序时将一个数据元素(或记录）的任意序列，重新排列成一个按关键字有序的序列。

五、 简答题

１.堆栈和队列都是特殊线性表,其特殊性是什么。堆栈是只能从一边输入和输出数据的线性表，具有先进后出(FILO）的特性;队列是只能从一边输入，而从另一边输出的线性表,具有先进先出(ＦIFO)的特性。

2。简述与开放定址法相比，链地址法处理冲突有哪些优点。与开放定址法相比,链地址法有如下几个优点：(１） 链地址法处理冲突简单,且无堆积现象．

(2） 由于链地址法各链表上结点空间是动态申请的，故它更适合于造表前无法确定表长的情况。

(3）开放定址法需装填因子ａ较小,链地址法中可取ａ〉=１,故当结点规模较大时,链地址法比开放定址法更节省空间。(4) 链地址法构造的散列表,删除结点的操作易于实现。

六、 综合题

1.(10分)已知某二叉树的前序序列为EBADＣＦＨGI，中序序列为ＡＢCＤEFGHI，请给出二叉树的后序序列，并画出这棵树的拓扑。后序序列为ACDBGIHFＥ

2。（15分)已知一个无向图的顶点集为{Ｖ０,V１，…V7｝，其邻接矩阵如下所示：

(2）画出该图的图形

(1) 给出从V0出发的深度优先、广度优先遍历序列

深度优先序列 V0,V1,V2,V5，V4，V６,V3,V7 广度优先序列 V０ V１ V3 V4 V2 Ｖ６ V5 V７ E

B

A D C F

H

G I

V0 0 1 0 1 1 0 0 0

V1 1 0 1 0 1 0 0 0

V2 0 1 0 0 0 1 0 0

V3 1 0 0 0 0 0 1 0

V4 1 1 0 0 0 0 1 0

V5 0 0 1 0 0 0 0 0

V6 0 0 0 1 1 0 0 1

V7 0 0 0 0 0 0 1 0

2

3 1

0

4 7

5 6 数据结构自测题３

一。单项选择题

1.对二叉排序树，使用（ B )的遍历方式，可以获得对结点序列关键字的排序 。

A．先序遍历 B.中序遍历 C.后序遍历 D．层次遍历

2。用数组表示线性表的优点是( C ）.

A．便于插入和删除操作 B.可以动态地分配存储空间

C．便于随机存取 D．不需要占用一片相邻的存储空间

３。一棵二叉树的先序遍历次序为 AＢＤGECFＨ ， 中序遍历次序为 DGBEAＦＨC ， 则其后序遍历次序为（ C ).

A．ACＦHBEＤG Ｂ.ABＣＤGHEF Ｃ.GDＥBHＦCA D.BＥＦCHＡGD

4．从未排序序列中选出最小的元素，并将其依次放入到已排序序列的一端的排序算法称为（ Ｃ ）．A．插入排序 B．交换排序 C.选择排序 D．快速排序

5。下列有关树的概念错误的是（ C )。

A.一棵树中只有一个无前驱的结点 B．树至少有一个结点

C.一棵树的度为树中各个结点的度数之和 D．树是一种非线性结构

6.在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（ B )。

A．都不相同B完全相同 Ｃ先序和中序相同而与后序不同 D中序和后序相同,而与先序不同

二。判断题

1。折半查找适合于顺序存储的有序表。( √）2.堆栈和队列是两种重要的非线性结构。（ × ）

３。满二叉树一定是完全二叉树.( √ ）4．栈具先进先出特征。( × )

５。单链表从任何一个结点出发，都能访问到所有结点。(×）6．一般树和二叉树的结点数目都可以为0。( × )

三.填空题

1.在树结构里，有且仅有一个结点没有前驱,称为根。非根结点有且仅有一个 直接前驱 ，且存在一条从根到该结点的 唯一路径 。

2.。一个无向图采用邻接矩阵存储方法,其邻接矩阵一定是一个 对称矩阵 。

3.四种基本的存储映象方法是顺序方法、链接方法、 索引方法 、 散列方法 。

四，名词解释

1。内部排序 内部排序指对数据元素序列的整个排序过程都是在计算机内存中进行的排序。

2。外部排序 外部排序是指待排序的数据元素太多,不能同时存放在内存中,所以排序操作不仅要使用内存，而且还要使用外部存储器存储数据的排序。

五。综合题

１。（１0分)对于线性表（18,25,63,５０,41,32,9０,66）进行散列存储时，若选用H(Ｋ)=K％１１作为散列函数,则分别计算:散列地址为0的元素的个数,散列地址为3的元素的个数,散列地址为8的元素的个数。如果用一个长度为11的数组来存储散列后的数据，并假设采用线性探测再散列的方式进行冲突检测,试写出散列后的序列．

散列地址为０的元素有１个 散列地址为3的元素有1 个

散列地址为８的元素有2个 散列后的序列：

错误!错误!错误!错误!错误!错误!错误!错误!错误!错误!错误!