数据结构是一门研究什么内容的学科

介绍数据结构

1.数据结构是一门研究什么内容的学科？

2.数据元素之间的关系在计算机中有几种表示方法？各有什么特点？

3.数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？

4.回答问题

（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？

（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。

（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。

（4）评价各种不同数据结构的标准是什么？

5．评价一个好的算法，您是从哪几方面来考虑的？

6．解释和比较以下各组概念

（1）抽象数据类型及数据类型

（2）数据结构、逻辑结构、存储结构

（3）抽象数据类型

（4）算法的时间复杂性

（5）算法

（6）频度

7.根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？

8.对于一个数据结构，一般包括哪三个方面的讨论？

9.当你为解决某一问题而选择数据结构时，应从哪些方面考虑？

10．数据结构与数据类型有什么区别？

介绍数据结构

一、简答题

1. 线性表有两种存储结构：一是顺序存储，二是链式存储，试问：

（1）如果有n个线性表同时共存，并且在处理过程中各表的长度会动态地发生变化，线性表的总数也会自动地改变。在此情况下，应该选择那种存储结构？为什么？

（2）若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的速度存取线性表中的元素。在此情况下，应该选择那种存储结构？为什么？

2. 链表所表示的元素是否是有序的？如果有序，则有序性体现在何处？链表所表示的元素是否一定要在物理上是相邻的？

3. 用线性表的顺序存储结构来描述一个城市的设计和规划是否合适？为什么？

二、算法设计题

1. Status ClearList(LinkList &L)

{ // 初始条件：线性表L已存在。操作结果：将L重置为空表

2. Status PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e) { // 初始条件: 线性表L已存在

// 操作结果: 若cur_e是L的数据元素,且不是第一个, 则用pre_e返回它的前驱,

// 返回OK;否则操作失败,pre_e无定义, 返回INFEASIBLE

介绍数据结构

3． 已知单链表的头指针为head，数据域为字符型，请编写算法，判断该链表的前n个字符是否中心对称。例如，abba、abcba都是中心对称。

4． 已知有两个单链表A和B，其头指针分别为first和second，编写一个算法，从单链表A中删除自第i个元素起的共m个元素，然后将它们插入到单链表B的第j个元素之前。

5． 设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法（要求用最少的时间和最小的空间）。

(1) 确定在序列中比正整数x大的数有几个（相同的数只计算一次，如序列{20，20，17，16，15，15，11，10，8，7，7，5，4}中比10大的数有5个）。

(2) 将单链表中比正整数x小的偶数从单链表中删除。

(3) 将比正整数x大的偶数从单链表中删除。

6． 已知指针first和second分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将表second的首元结点连在表first的最后一个结点之后，假设指针third指向连接后的链表的头结点，分析你的算法的时间复杂度。

7． 已知A和B为元素非递减排列的无头结点单链表（同一表中可能有相同元素），试编写算法，构建一个新的单链表C，保存A和B表中的公共元素。要求：C链表的元素值各不相同且递增有序。

8. 已知非空线性链表第一个结点由Head指出，请写一个算法，交换p所指的结点与其下一个结点在链表中的位置（假设p不是指向最后一个结点）。

介绍数据结构

1. Status ClearList(SqList &L)

{ // 初始条件：顺序线性表L已存在。操作结果：将L重置为空表

2. Status PriorElem(SqList L,ElemType cur_e,ElemType &pre_e)

{ // 初始条件：顺序线性表L已存在

// 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，

// 否则操作失败，pre_e无定义

3． 已知数组A[n]的元素类型为int。设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O（n）。

4． 设线性表存放于顺序表A中，其中有n个元素，且递增有序，请设计一算法，将元素S插入到线性表的适当位置，以保持线性表的有序性，并且给出该算法的时间复杂度。

5． 已知一个顺序存储的线性表的元素非递减有序排列，编写删除表中多余的值相同的元素的高效算法。

6． 已知一个顺序存储的线性表，编写删除表中值大于minx且小于maxy（包括minx和maxy）的所有元素的高效算法。

介绍数据结构

*7. 已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法

删除线性表中所有值为item的数据元素。（O（1）表示算法的辅助空间为常量）。[提示：题目并未要求元素间的相对位置不变。]