数据结构的选择

1．数据的物理结构包括 数据元素 的表示和 数据元素关系 的表示。

2. 对于给定的n个元素,可以构造出的逻辑结构有 集合 ， 线性结构 ， 树形结构 ，__图状结构或网状结构_四种。

3．数据的逻辑结构是指 数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系” 。

4．一个数据结构在计算机中的 表示（或称映像） 称为存储结构（又数据的物理结构）。

5．抽象数据类型的定义仅取决于它的一组__逻辑特性_，而与_在计算机内部如何表示和实现_无关，即不论其内部结构如何变化，只要它的_数学特性_不变，都不影响其外部使用。 6．数据结构中评价算法的两个重要指标是 算法的时间复杂度和空间复杂度

7. 数据结构是研讨数据的_逻辑结构_和_物理结构_，以及它们之间的相互关系，并对与这种结构定义相应的_操作（运算）_，设计出相应的_算法。

8． 一个算法具有5个特性: 有穷性 、 确定性 、 可行性 ，有零个或多个输入、有一个或多个输出 。

4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情

历届竞赛数据结构选择题

单项选择题（共10题，每题1.5分）

[10]7. 前缀表达式“+ 3 * 2 + 5 12 ” 的值是（ ）。 A. 23 B. 25 C. 37 D. 65

[10]9. 完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（ ）号位置。

A. 2k B. 2k+1 C. k/2下取整 D. (k+1)/2

[09]4. 在字长为16位的系统环境下，一个16位带符号整数的二进制补码为1111111111101101。其对应的十进制整数应该是：( )

A. 19 B. -19 C. 18 D.-18

[09]5. 一个包含n个分支结点(非叶结点)的非空满k叉树，k>=1，它的叶结点数目为：( )

A. nk+1 B. nk-1 C. (k+1)n-1 D. (k-1)n+1 [09]6. 表达式a*(b+c)-d的后缀表达式是：( )

A. abcd*+- B. abc+*d- C. abc*+d

1．数据逻辑结构包括 线性结构 、 树形结构 和 图状结构 三种类型，树形结构和图状结构合称 非线性结构 。

2．数据的逻辑结构分为 集合 、线性结构 、 树形结构 和 图状结构 4种。

3．在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有 1 个后续结点。

4．线性结构中元素之间存在 一对一 关系，树形结构中元素之间存在 一对多 关系，图形结构中元素之间存在 多对多 关系。

5．在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点可以 任意多个 。

6．数据结构的基本存储方法是 顺序 、 链式 、 索引 和 散列 存储 。

7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和 时间复杂度与 空间复杂度 。

8．评估一个算法的优劣，通常从 时间复杂度 和 空间复杂度 两个方面考察。

9．算法的5个重要特性是 有穷性 、 确定性 、

第一章 绪论

一、选择题

1.组成数据的基本单位是（C）

（A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（C ）以及它们之间的相互关系。 （A）理想结构，物理结构 （B）理想结构，抽象结构 （C）物理结构，逻辑结构 （D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（C ） （A）动态结构和静态结构 （B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构

4.数据结构是一门研究非数值计算的程序设计问题中计算机的 （①A）以及它们之间的（②B）和运算等的学科。

① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ② （A）结构 （B）关系 （C）运算 （D）算法 5.算法分析的目的是（C）。

（A） 找出数据结构的合理性 （B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性

6.计算机算法指的是（①C）,它必须具备输入、输出和（②B）等5个特性。 ① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法 ② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有

1．数据逻辑结构包括 线性结构 、 树形结构 和 图状结构 三种类型，树形结构和图状结构合称 非线性结构 。

2．数据的逻辑结构分为 集合 、线性结构 、 树形结构 和 图状结构 4种。

3．在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有 1 个后续结点。

4．线性结构中元素之间存在 一对一 关系，树形结构中元素之间存在 一对多 关系，图形结构中元素之间存在 多对多 关系。

5．在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点可以 任意多个 。

6．数据结构的基本存储方法是 顺序 、 链式 、 索引 和 散列 存储 。

7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和 时间复杂度与 空间复杂度 。

8．评估一个算法的优劣，通常从 时间复杂度 和 空间复杂度 两个方面考察。

9．算法的5个重要特性是 有穷性 、 确定性 、

1.数据结构形考选择题

2.把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（ B ）。

a)A．逻辑结构 B．物理结构

b)C．算法的具体实现 D．给相关变量分配存储单元

3.下列说法中，不正确的是（ D ）。

A．数据元素是数据的基本单位

B．数据项是数据中不可分割的最小可标识单位

C．数据可有若干个数据元素构成

D．数据项可由若干个数据元素构成

4.一个存储结点存储一个（ B ）。

a)A．数据项 B．数据元素

b)C．数据结构 D．数据类型

5.数据结构中，与所使用的计算机无关的是数据的（ C ）。

a)A．存储结构 B．物理结构

b)C．逻辑结构 D．物理和存储结构

6.下列的叙述中，不属于算法特性的是（D ）。

a)A．有穷性 B．输入性

b)C．可行性 D．可读性

7.算法分析的目的是（C ）。

a)A．找出数据结构的合理性 B．研究算法中的输入和输出的关系

b)C．分析算法的效率以求改进 D．分析算法的易懂性和文档性

8.

福建农林大学计算机与信息学院实验报告

数据结构的程序实现

一、 实验目的和要求

1) 进一步了解数据结构的实现策略。 2) 掌握动态结构的静态实现方法。 3) 了解大批量数据的组织策略。 4) 掌握数据结构在问题建模中的应用。 二、 实验内容和原理 实验内容：

编程实现Josephus问题。 实验原理：

【问题描述】设有n个人围坐一圈并由1~n编号。从某个人（例如编号为k的人）开始报数，数到m的人出列；接着从出列的下一个人开始重新1~m报数，数到m的人又出列；如此反复地报数和出列，知道最后一个人出列为止。试设计确定这n个人出列序列的程序。

【解题思路】有问题描述可以很自然地联想到循环列表，用循环列表对Josephus问题建模，可以做到程序世界和问题世界的完全一致性，符合面向对象的设计思想。考虑到反复报数的过程，可选用不带头结点的单循环链表，以避免报数过程中识别头结点的麻烦。由此，程序中可以先构建一个具有n个结点的单循环链表，然后从约定的结点开始1到m计数，计到m时从链表中删除对应结点；接着从被删除结点的下一个结点起计数，知道最后一个结点从链表中删除后结

束。

三、 实验环境 Windows XP系统 visual c++6.0 四、 实验习

数据结构

1

1.为解决计算机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。（全国统考2009） A．栈 B．队列 C．树 D．图

2.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后入队Q，若出队序列为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（ ）。（全国统考2009）

A．1 B．2 C．3 D．4

3.若元素abcdef依次进栈，允许进栈、出栈交替进行，不允许连续三次进行出栈操作，则不可能得到的出栈序列是（ ）。（全国统考2010）

A．dcebfa B．cbdaef C．dbcaef D．afedcb 4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（ ）。（全国统考2010） A．bacde B．dbace C．dbcae D．ecbad

5.元素abcde依次进入初

数据结构

为了编写一个“好”的程序，必须分析待处理的对象特性以及各处理对象之间存在的关系.这就需要学习“数据结构”。因此，简单地说来，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。在信息学奥赛中需要学习线性表、树、图三种数据结构，在后面我们将一一介绍.

4.1 栈

线性表是最常用且比较简单的一种数据结构，它是由有限个数据元素组成的有序集合，每个数据元素有一个数据项或者含多个数据项.例如我们前面所学过的数组是线性的数据结构.

下面介绍的栈是一种线性表，但是对它的插人和删除等操作都限制在表的同一端进行，即栈顶，而另一端则称为是栈底.打个形象地比喻，用桶堆积物品，先堆进来的压在底下，随后一件一件往上堆.取走时，只能从上面一件一件取.堆和取都在顶部进行，底部一般是不动的.所以，栈也称为后进先出表(LIFO表).

通常栈可以用顺序的方式存储，分配一块连续的存储区域来存放栈中的数据项，即用定长为N的数组S来表示，并用一个变量TOP指向当前栈顶(如图4-1-1).若TOP=0，表示栈空，T0P=N时栈满.我们一般把插人操作称为进栈(PUSH)，此时TOP加1，删除操作则称为出栈

标题：简单数据结构与拓补数据结构的比较

关键词：简单数据结构、拓补数据结构

（一） 摘要

简单数据结构具有结构简单、直观、易实现以实体为单位的运算和显示的优点

在简单数据结构中，空间数据按照以基本的空间对象(点、线或多边形)为单元进行单独组织，不含有拓扑关系数据，最典型的是面条(Spaghetti)结构。

拓补：即形状的研究。拓扑数据结构的构建实际上大大增加了数据编辑的难度和复杂性。

（二）介绍：

矢量数据结构： 基于矢量模型的数据结构简称为矢量数据结构。矢量也叫向量，数学上称“具有大小和方向的量”为向量。在计算机图形中，相邻两结点间的弧段长度表示大小，弧段两端点的顺序表示方向，因此弧段也是一个直观的矢量。

矢量数据结构是通过记录坐标的方式来表示点、线、面等地理实体空间分布的一种数据组织方式。这种数据组织方式定位明显，属性隐含，能最好地逼近地理实体的空间分布特征，数据精度高，数据存储的冗余度低，便于进行地理实体的网络分析，但对于多层空间数据的叠合分析比较困难。

适量数据结构师一种最常见的图形数据结构，主要用于表示地图图形元素集合数据之间及其与属性数据之间的相互关系。通过记录坐标方式，尽可能的将点、线、面地理实体表现得精确无误。

矢量数据结构的