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

第一章知识点

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个元素的存储地址＋(5－1)×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=”a1a2…an”哟可以表示为s=（a1,a2,…,an）,即线性表的形式。因此，串也是一种线性表，是一种数据类型受到限制（只能为字符型）的线性表。

·空串 不含任何字符的串称为空串，它的长度n=0,记为s=””

·空白串 含有一个空格的串称为空白串，它的长度n=1,记为s=“ “或s=”φ”.

·子串、主串 若一个串是另一个串中连续的一段，则这个串称为另一个串的子串 P62 ·串的运算 （8）求子串位置index(S,T), 在S中找T P69 ·串的模式匹配 模式匹配如下：

int seqstring::INDEX( seqstring S,seqstring T) {

int i=0,j=0;

while ((i

i++; j++; } else {

i=i-j+1; //将i指针回溯 j=0; }

if (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个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（ ）。 【解答】1140

【分析】数组A中每行共有n=6个元素，元素A[15][10]的前面共存储了(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、设HEAD[p]为求广义表p的表头函数，TAIL[p]为求广义表p的表尾函数，

其中[]是函数的符号，给出下列广义表的运算结果： HEAD[(a, b, c)]的结果是_________。 TAIL[(a, b, c)]的结果是_________。 HEAD[((a), (b))]的结果是_________。 TAIL[((a), (b))]的结果是_________。

HEAD[TAIL[(a, b, c)]]的结果是_________。 TAIL[HEAD((a, b), (c, d))]的结果是_________。 HEAD[HEAD[(a, b), (c, d)]]的结果是_________。 TAIL[TAIL[(a, (c, d))]]的结果是_________。

答：1、（1）（（a）） (2) ( )

2、(1)(a) (2) (((b),c),(((d)))) 3、(1)3 (2) 4 4、(1)5 (2) 3

5、(1) a (2) (b,c) (3) (a) (4) ((b)) (5) b (6) (b) (7) a (8) ( )

重点题目： P97 5-11

本文来源：https://www.bwwdw.com/article/ziu6.html