第1章绪论练习题

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

第1章绪论练习题2013-03-2013:46简答题(选择部分习题解答)1.数据结构是一门研究什么内容的学科?2.数据元素之间的关系在计算机中有几种表示方法?各有什么特点?3.数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处,抽象数据类型的主要特点是什么?使用抽象数据类型的主要好处是什么?4.回答问题(1)在数据结构课程中,数据的逻辑结构,数据的存储结构及数据的运算之间存在着怎样的关系?(2)若逻辑结构相同但存储结构不同,则为不同的数据结构。这样的说法对吗?举例说明之。(3)在给定的逻辑结构及其存储表示上可以定义不同的运算集合,从而得到不同的数据结构。这样说法对吗?举例说明之。(4)评价各种不同数据结构的标准是什么?5.评价一个好的算法,您是从哪几方面来考虑的?6.解释和比较以下各组概念(1)抽象数据类型及数据类型(2)数据结构、逻辑结构、存储结构(3)抽象数据类型(4)算法的时间复杂性(5)算法(6)频度7.根据数据元素之间的逻辑关系,一般有哪几类基本的数据结构?8.对于一个数据结构,一般包括哪三个方面的讨论?9.当你为解决某一问题而选择数据结构时,应从哪些方面考虑?10.数据结构与数据类型有什么区别?第2章线性表练习题(一)[顺序存储结构]2009-06-1011:501.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(n)。4.设线性表存放于顺序表A中,其中有n个元素,且递增有序,请设计一算法,将元素S插入到线性表的适当位置,以保持线性表的有序性,并且给出该算法的时间复杂度。5.已知一个顺序存储的线性表的元素非递减有序排列,编写删除表中多余的值相同的元素的高效算法。6.已知一个顺序存储的线性表,编写删除表中值大于minx且小于maxy(包括minx和maxy)的所有元素的高效算法。*7.已知长度为n的线性表A采用顺序存储结构,请写一时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为item的数据元素。(O(1)表示算法的辅助空间为常量)。[提示:题目并未要求元素间的相对位置不变。]第2章线性表练习题(二)[链式存储结构]2010-04-0210:33一、简答题1.线性表有两种存储结构:一是顺序存储,二是链式存储,试问:(1)如果有n个线性表同时共存,并且在处理过程中各表的长度会动态地发生变化,线性表的总数也会自动地改变。在此情况下,应该选择那种存储结构?为什么?(2)若线性表的总数基本稳定,且很少进行插入、删除操作,但要求以最快的速度存取线性表中的元素。在此情况下,应该选择那种存储结构?为什么?2.链表所表示的元素是否是有序的?如果有序,则有序性体现在何处?链表所表示的元素是否一定要在物理上是相邻的?3.用线性表的顺序存储结构来描述一个城市的设计和规划是否合适?为什么?二、算法设计题1.StatusClearList(LinkList&L){//初始条件:线性表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,其头指针分别为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 / 3
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功