数据结构(C++版)知识点及相应题目.doc

第一章知识点P3 数据结构从逻辑上划分为：（1）线性结构 （2）非线性结构: 树型结构和图型结构 P4 从存储结构（物理结构）上划分：（1）顺序结构 ：所有元素存放在一片连续的存储单元中，逻辑上相邻的元素存放到计算机内存中仍然相邻 （2）链式结构：所有元素存放在可以不连续的存储单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。 P5 算法的五大特性：（1）输入（2）输出 （3）有穷性 （4）确定性（5）可行性（可执行）P6 算法分析的任务/方面：（1）时间复杂度 （重点是计算时间复杂度P9 1-5 P10 1-12）（2）空间复杂度（性）：一个算法在执行时所占有的内存开销，称为空间频度课后部分习题解释：1-2简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 数据：指能够被计算机识别、存储和加工处理的信息载体。 数据元素：就是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。 逻辑结构：指各数据元素之间的逻辑关系。 存储结构：就是数据的逻辑结构用计算机语言的实现。 线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前驱和直接后继。补充习题（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。【解答】数据元素 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。【解答】集合，线性结构，树型结构，图型结构 算法指的是（ ）。A 对特定问题求解步骤的一种描述，是指令的有限序列。B 计算机程序 C 解决问题的计算方法 D 数据处理【解答】A【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。 下面（ ）不是算法所必须具备的特性。A 有穷性 B 确切性 C 高效性 D 可行性【解答】C 【分析】高效性是好算法应具备的特性。 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。A 找出数据结构的合理性 B 研究算法中输入和输出的关系C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性【解答】C，E 6. 对下列用二元组表示的数据结构,试分别画出对应的逻辑结构图，并指出属于何种结构。 A=(D，R)， 其中D=a1, a2, a3, a4，R= B=(D，R)， 其中D=a, b, c, d, e, f，R=, C=( D，R)，其中D=a，b，c，d，e，f，R=, D=(D，R)， 其中D=1, 2, 3, 4, 5, 6，R=(1, 2)，(1, 4)，(2, 3)，(2, 4)，(3, 4)，(3, 5)，(3, 6)，(4, 6) 【解答】 属于集合，其逻辑结构图如图1-4(a)所示； 属于线性结构，其逻辑结构图如图1-4(b)所示； 属于树结构，其逻辑结构图如图1-4(c)所示； 属于图结构，其逻辑结构图如图1-4(d)所示。 第二章知识点P16 利用线性表来存储线性表，表中相邻的元素存储在计算机内的位置也相邻P21 线性表的链式存储结构，也称为链表。其存储方式是：在内存中利用存储单元（可以不连续）来存放元素值及它在内存中的地址，各个元素的存放顺序及位置都可以以任意顺序进行P25 单链表上的插入运算 (1)s-next=p-next; (2)p-next=s;P26 单链表上的删除运算 （1）q-next=p-next; （2）delete(p);补充习题：（1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（ ）。【解答】108【分析】第5个元素的存储地址=第1个元素的存储地址(51)2=108（2） 设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（ ）。【解答】p-next=(p-next)-next（3）线性表的顺序存储结构是一种（ ）的存储结构，线性表的链接存储结构是一种（ ）的存储结构。 A 随机存取 B 顺序存取 C 索引存取 D 散列存取【解答】A，B（4） 线性表采用链接存储时，其地址（ ）。A 必须是连续的 B 部分地址必须是连续的C 一定是不连续的 D 连续与否均可以【解答】D【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。 在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（ ）操作。A s-next=p-next; p-next=s; B q-next=s; s-next=p; C p-next=s-next; s-next=p; D p-next=s; s-next=q;【解答】B【分析】注意此题是在q和p之间插入新结点，所以，不用考虑修改指针的顺序。 在循环双链表的p所指结点后插入s所指结点的操作是（ ）。A p-next=s; s-prior=p; p-next-prior=s; s-next=p-next; B p-next=s; p-next-prior=s; s-prior=p; s-next=p-next;C s-prior=p; s-next=p-next; p-next=s; p-next-prior=s;D s-prior=p; s-next=p-next; p-next-prior=s; p-next=s【解答】D【分析】在链表中，对指针的修改必须保持线性表的逻辑关系，否则，将违背线性表的逻辑特征，图2-10给出备选答案C和D的图解。第三章知识点P40 栈 栈是一种后进先出的线性表，简称LIFO表。P52 队列 先进先出，FIFO表重点习题：课本P58-59:3-1: 进一个出一个，ABCD先进两个，AB进，进C出C,进D出D，出B出A，CDBA进A进B，进C进D，出D出C出B出A，DCBA下面的不解释了，不明白你再问BCDA,BDCA,BCAD,BADC,BACD,前三个一起进CBAD,CBDA,CDBA第一个进去就出来ADCB,ACDB,ACBD一共14种3-2; 3-3第四章知识点P61 串 是由零个或多个 字符 组成的有限序列串s=”a1a2an”哟可以表示为s=（a1,a2,an）,即线性表的形式。因此，串也是一种线性表，是一种数据类型受到限制（只能为字符型）的线性表。空串 不含任何字符的串称为空串，它的长度n=0,记为s=”空白串 含有一个空格的串称为空白串，它的长度n=1,记为s=“ “或s=”.子串、主串 若一个串是另一个串中连续的一段，则这个串称为另一个串的子串P62 串的运算 （8）求子串位置index(S,T), 在S中找TP69 串的模式匹配 模式匹配如下： int seqstring:INDEX( seqstring S,seqstring T) int i=0,j=0; while (iS.cuelen )&(j=T.curlen) retuen (i-T.curlen); else return (-1); /匹配失败 第五章知识点P75 多维数组的存储结构LOC(a00)是a00的内存地址，d是每个元素占的字节，i是每行，i*n+j是表示aij前面有多少个元素。地址计算 （1）行优先：LOC（aij）=LOC(a00)+(i*n+j)*d （2）列优先：LOC（aij）= LOC(a00)+(j*m+i)*d例题： 二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A105的存储地址是1000，则元素A1510的存储地址是（ ）。【解答】1140【分析】数组A中每行共有n=6个元素，元素A1510的前面共存储了(15-10)6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+（(15-10)6+5）*4=1140。 广义表(a), (b),c),(d)的长度是（），深度是（），表头是（），表尾是（）。【解答】3，4，(a)，(b),c),(d)加深习题：1 广义表(a)的表头是_，表尾是_。2、广义表（a）,(b), c), (d)）的表头是_，表尾是_。3、广义表(a), (b), c), (d)的长度是_，深度是_。4、广义表(a, (a, b), d, e, (i, j), k)的长度是_，深度是_。5、设HEADp为求广义表p的表头函数，TAILp为求广义表p的表尾函数，其中是函数的符号，给出下列广义表的运算结果：HEAD(a, b, c)的结果是_。TAIL(a, b, c)的结果是_。HEAD(a), (b)的结果是_。TAIL(a), (b)的结果是_。HEADTAIL(a, b, c)的结果是_。TAILHEAD(a, b),