数据结构的逻辑结构有哪些

数据结构

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依次进入初

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

数据结构的程序实现

一、 实验目的和要求

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 四、 实验习

福建师范大学数学与计算机科学学院 2009--2010学年度上学期08电信

《数据结构》期中试题

试卷类别：闭卷 考试时间：90分钟

专业： 学号： 姓名： ZhengKen 题号 一 得分 得分 评卷人 一、选择题（每小题1分， 共6分） 1、关于线性表的说法,下面选项正确的是（B ） A 线性表的特点是每个元素都有一个前驱和一个后继（除头、尾元素，直接的） B 线性表是具有n(n>=0)个元素的一个有限序列 C 线性表就是顺序存储的表 （可以是链式存储结构） D 线性表只能用顺序存储结构实现 （可以是链式存储结构） 2、表长为n的顺序存储的线性表，当在任何一个位置上插入或者删除一个元素的概率相等时，删除一个元素需要移动元素的平均个数为（ A） A (n-1)/2 B n/2 C n D n-1 3、设双向循环链表中节点的结构为(data,LLink,RLink)，且不带头节点。若想在指针p所指节点之后插入指针s所指节点，则应执行下列哪一个操作？（ D ） A p->RLink=s

数据结构

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

4.1 栈

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

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

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

数据结构习题

一、 单选题

1. 研究数据结构就是研究 D

A) 数据的逻辑结构

B) 数据的逻辑结构和存储结构 C) 数据的存储结构

D) 数据的逻辑结构、存储结构及其数据在运算上的实现 2. 下面关于算法的说法，错误的是 D 。

A) 算法最终必须由计算机程序实现

B) 为解决某问题的算法与为该问题编写的程序含义是相同的 C) 算法的可行性是指指令不能有二义性 D) 以上几个都是错误的

3. 计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备

5个特性输入、输出 、 B 。 A) 可执行性、可移植性和可扩充性 B) 可执行性、有穷性和确定性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和确定性

4. 以下属于逻辑结构的概念是 C 。

A) 顺序表 B) 哈希表 C) 有序表 D) 单链表

5. 具有线性结构的数据结构是 D 。

A) 图 B) 树 C) 广义表 D) 栈

6. 数据的存储结构包括顺序、链接、散列和 D 种基本类型。

A) 向量 B) 数组 C) 集

数据结构复习201406

第一章绪论

基本知识点：数据结构与算法的概念。

重点：数据结构的逻辑结构、存储结构、数据运算三方面的概念及相互关系；算法时间复杂度分析。

难点：分析算法的时间复杂度。 知识要点：

数据：在计算机科学中数据是指所有能输入到计算机中并被计算机处理的符号的总称。 数据元素：数据的基本单位，是数据的一个元素。

数据对象：性质相同的数据元素的集合，是数据的一个子集。

数据结构：相互之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。

数据类型：一个值的集合和定义在这个值集上的一组运算的总称。

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间关系和操作（运算）的学科。

数据的逻辑结构是指数据元素之间逻辑关系的整体。 数据的存储结构是指数据结构在计算机内的表示。

四种基本数据结构：集合、线性结构、树形结构、图结构。

算法具有的五个基本特性是：有穷性、可行性、确定性、输入和输出。 算法执行的时间是问题规模的函数。 算法的时间复杂度是指，随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同时，则称该算法的时间复杂度为O(f(n))。

完全二叉树的顺序存储：

A2B1C34DE56FG7HIJKL89101112

ABCDEFGHIJKL

0 1 2 3 4 5 6 7 8 9 10 11 12

一般二叉树的顺序存储：

把一般的二叉树先补成完全二叉树，然后按照完全二叉树的顺序存储方式进行存储，而新补上去的结点只占位置，不存放结点数据。

ABCD(a) 右偏斜二叉树AABCD(b) 补全后的完全二叉树 DBC (c) 右偏斜二叉树的顺序存储示意图

二叉树的链式存储结构： 二叉链表：

二叉树的遍历：

顺着某一条搜索路径巡访二叉树中的节点，使得每个节点均被访问一次，而且仅被访问一次。

常见的遍历方式有：

递归遍历，层次遍历，非递归遍历 树的遍历常用方法：

先序遍历：先访问树的根节点，然后先序访问左子树，最后先序访问右子树 中序遍历：先中序遍历左子树，然后访问根节点，最后中序访问右子树 后序遍历：先后序遍历左子树，然后后序遍历右子树，最后访问根节点 按层次遍历：先访问第一次上的节点，然后依次遍历第二层。。。。。

先序遍历的递归算法： void

数 据 结 构 习 题

一、基本概念

1. 为了描述n个人之间的同学关系，可用 结构表示。 C A.线性表 B.树 C.图 D.队列 2.数据结构主要研究数据的______。 D

A.逻辑结构 B.存储结构

C.逻辑结构和存储结构 D.逻辑结构和存储结构及起运算的实现 二、线性表

1.链表不具备的特点是 。 A

A．可随机访问任何一个元素 B．插入、删除操作不需要移动元素 C．无需事先估计存储空间大小 D．所需存储空间与线性表长度成正比 2. 若线性表采用链式存储结构，则适用的查找方法为____。 D

A. 随机查找 B. 散列查找 C. 二分查找 D. 顺序查找

3.已知 N 个数已存入数组 A[1..M]的前 N 个元素中（N

4．设指针p指向单链表中的结点A，结点A的后继结点是结点B，则删除结点B的操作为（ ）。 D

A． p->next=p

B． p=p->next

D． p->next=p->next->next

C．p=p->next

数据结构3

总分：100 考试时间：100分钟

一、单项选择题

1、数组的存储结构采用（）存储方式(正确答案：A)

A、顺序

B、链式C、链表D、线性表

2、设二维数组A[-20..30,-30..20], 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素A[25,18]的存储地址为( )(正确答案：C)

A、4568

B、9536 C、9572 D、4672

3、二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（）的起始地址一致。(正确答案：B)

A、A[8,5]

B、A[3,10] C、A[5,8] D、A[0,9]

4、已知二维数组A[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是（）(正确答案：D)

A、1086

B、1096 C、1186 D、1196

5、二维数组a[4][5][6]（下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]的地址是( )。(设a[0][0][0]的地

1． 已知长度为n的线性表L采用顺序存储结构，编写一个时间复杂度为O(n)，空间复杂度

为O(1)的算法，该算法删除线性表中所有值为item的数据元素。

2． 用顺序表A和B表示的两个线性表，元素的个数分别为m和n，若表中数据都是由小

到大顺序排列的，且这(m+n)个数据中没有相重的。设计一个算法将些两个线性表合并成一个，仍是数据由小到大排列的线性表，存储到另一个顺序表C中。

3． 已知线性表{a0,a1,……,an-1}按顺序存储，且每个元素都是不相等的整数。设计把所有

的奇数移到所有的偶数前边的算法（要求时间最少，辅助空间最少）。 4． 输入一组整型元素序列，建立单链表。

5． 写出在带头结点的单向链表l中删除第i个结点的算法。

6． 编写算法,将带头结点的单链表拆分成一个奇数链表和一个偶数链表。

7． 设C={a1,b1,a2,b2,……,an,bn}为一线性表，采用带头结点的Hc单链表存放，编写一个

就地算法，将其拆分成两个线性表，使得：A={a1,a2,…..,an} C={b1,b2,….,bn} 8． 编写出判断带头结点的双向循环链表L是否对称相等的算法。 9． 设计一算法，将一带头结点的数据域依次为a1,a2,…,an(n>=3)的单