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

《数据结构是一门研究什么内容的学科.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.数据结构是一门研究什么内容的学科？2.数据元素之间的关系在计算机中有几种表示方法？各有什么特点？3.数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？4.回答问题（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。（4）评价各

2、种不同数据结构的标准是什么？5．评价一个好的算法，您是从哪几方面来考虑的？6．解释和比较以下各组概念（1）抽象数据类型及数据类型（2）数据结构、逻辑结构、存储结构（3）抽象数据类型（4）算法的时间复杂性（5）算法（6）频度7.根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？8.对于一个数据结构，一般包括哪三个方面的讨论？9.当你为解决某一问题而选择数据结构时，应从哪些方面考虑？10．数据结构与数据类型有什么区别？一、简答题1.线性表有两种存储结构：一是顺序存储，二是链式存储，试问：   （1）如果有n个线性表同时共存，并

3、且在处理过程中各表的长度会动态地发生变化，线性表的总数也会自动地改变。在此情况下，应该选择那种存储结构？为什么？   （2）若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的速度存取线性表中的元素。在此情况下，应该选择那种存储结构？为什么？    2.链表所表示的元素是否是有序的？如果有序，则有序性体现在何处？链表所表示的元素是否一定要在物理上是相邻的？3.用线性表的顺序存储结构来描述一个城市的设计和规划是否合适？为什么？ 二、算法设计题1. StatusClearList(LinkList &L)  {//初始条

4、件：线性表L已存在。操作结果：将L重置为空表2. StatusPriorElem(LinkListL,ElemTypecur_e,ElemType&pre_e) {//初始条件:线性表L已存在  //操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,  //返回OK;否则操作失败,pre_e无定义,返回INFEASIBLE3．已知单链表的头指针为head，数据域为字符型，请编写算法，判断该链表的前n个字符是否中心对称。例如，abba、abcba都是中心对称。4．已知有两个单链表A和B，其头指针分别为

5、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．已知指针

6、first和second分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将表second的首元结点连在表first的最后一个结点之后，假设指针third指向连接后的链表的头结点，分析你的算法的时间复杂度。7．已知A和B为元素非递减排列的无头结点单链表（同一表中可能有相同元素），试编写算法，构建一个新的单链表C，保存A和B表中的公共元素。要求：C链表的元素值各不相同且递增有序。8.已知非空线性链表第一个结点由Head指出，请写一个算法，交换p所指的结点与其下一个结点在链表中的位置（假设p不是指向最后一个结

7、点）。1. StatusClearList(SqList&L) {//初始条件：顺序线性表L已存在。操作结果：将L重置为空表2. StatusPriorElem(SqListL,ElemTypecur_e,ElemType&pre_e) {//初始条件：顺序线性表L已存在  //操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，  //否则操作失败，pre_e无定义3．已知数组A[n]的元素类型为int。设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O

8、（n）。4．设线性表存放于顺序表A中，其中有n个元素，且递增有序，请设计一算法，将元素S插入到线性表的适当位置，以保持线性表的有序性，并且给出该算法的时间复杂度。5．已知一个顺序存储的线性表的元素非递减有序排列，编写删除表中多余的值相同的元素的高效算法。6．已知