数据结构知识点及相应题目

1、第一章知识点P3 数据结构从 逻辑上划分为：（1）线性结构 （2）非线性结构：树型结构和图型结构P4 从存储结构（物理结构）上划分：（ 1 ）顺序结构 ：所有元素存放在一片连续的存储单元中，逻辑上相邻的元素存放到计算 机内存中仍然相邻（ 2）链式结构：所有元素存放在可以不连续的存储单元中，但元素之间的关系可以通过地 址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。P5 算法的五大特性：（1）输入（2）输出（3）有穷性（4）确定性（5）可行性（可执行）P6 算法分析的任务/方面：（1）时间复杂度 （重点是计算时间复杂度 P9 1-5 P101-12）（2）空间复杂度（性） ：一个算法在

2、执行时所占有的内存开销，称为空间频度课后部分习题解释：1-2 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结 构、非线性结构。数据：指能够被计算机识别、存储和加工处理的信息载体。数据元素：就是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 数据结构： 指的是数据之间的相互关系， 即数据的组织形式。 一般包括三个方面的内容 ： 数据的逻辑结构、存储结构和数据的运算。 逻辑结构：指各数据元素之间的逻辑关系。 存储结构：就是数据的逻辑结构用计算机语言的实现。 线性结构：数据逻辑结构中的一类，它的

3、特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点， 并且所有结点都最多只有一个直接前趋和一个直接后继。 线性 表就是一个典型的线性结构。 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前 驱和直接后继。补充习题9（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树型结构，图型结构 算法指的是（ ）。A 对特定问题求解步骤的一种描述，是指令的有限序列。B 计算机程序 C 解决问题的计算方法 D 数据处理【解答】 A【分析】计算

4、机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是 通过算法完成的。所以，只有 A 是算法的准确定义。 下面（ ）不是算法所必须具备的特性。A 有穷性 B 确切性 C 高效性 D 可行性【解答】C【分析】高效性是好算法应具备的特性。 算法分析的目的是(),算法分析的两个主要方面是()。A找出数据结构的合理性B研究算法中输入和输出的关系C分析算法的效率以求改进D分析算法的易读性和文档性E空间性能和时间性能F正确性和简明性G可读性和文档性H数据复杂性和程序复杂性【解答】C, E6.对下列用二元组表示的数据结构，试分别画出对应的逻辑结构图，并指出属于何种结构。 A=(D，R)， 其

5、中 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)所示；(3)属于树结构，其逻辑结构图如图1-4(c)所示；(4)属于图结构，其逻辑结构图如图1-4(d)所示。第二章知识点P16 利用线性表来存储线性表，表中

6、相邻的元素存储在计算机内的位置也相邻P21 线性表的链式存储结构，也称为链表。其存储方式是：在内存中利用存储单元(可以不连续)来存放元素值及它在内存中的地址，各个元素的存放顺序及位置都可以以任意 顺序进行P25 单链表上的插入运算(1) s->n ext=p->n ext;(2) p->n ext=s;P26 单链表上的删除运算1)q->next=p->next;2)delete(p);补充习题：(1)顺序表中第一个元素的存储地址是100，每个元素的长度为 2，则第 5 个元素的存储地址是( )。【解答】 108【分析】第5个元素的存储地址=第1个元素的存储地址+

7、 (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【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素， 这 组存储单元可

8、以连续，也可以不连续，甚至可以零散分布在内存中任意位置。(11) 在一个单链表中，已知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 之间插入新结点，所以，不用考虑修改指针的顺序。(12) 在循环双链表的p所指结点后插入s所指结点的操作是()

9、。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-&g

10、t;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种

11、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 seqs

12、tring:INDEX( seqstring S,seqstring T)int i=0,j=0;while (i<S.cuele n )&&(j<T.curle n) if (S.chi=T.chj)i+； j+； else i=i-j+1;将i指针回溯j=0; if (j>=T.curle n) retue n (i-T.curle n);else return (-1);/ 匹配失败第五章知识点P75 多维数组的存储结构LOC(a00) 是 a00 的内存地址， d 是每个元素占的字节， i 是每行， i*n+j 是表示 aij 前面有多少个元素。地址计

13、算(1 行优先:LOC (aij) =LOC(aOO)+(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) X 6+5个元素，每个元素占4个存储单元，所以，其存 储地址是 1000+ (15- 10) X 6+5) *4=1140。 广义表(a), (b),c),(d)

14、的长度是()，深度是()，表头是()，表尾是()。【解答】 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,