顺序结构部分带答案及例题版.pdfVIP

《数据结构》课程复习资料

选择题15分

填空题30分

简答题30分

综合体30分

主观题10分

第一章：数据结构概述（15分）

1、掌握数据结构的定义:是指互相之间存在着一种或多种关系的数据

元素的集合。

即数据结构三要素：数据的逻辑结构、存储结构、数据元素。

2、数据结构包括：逻辑结构和存储结构；

3、数据之间的关系：表（一对一之间的关系）、树（一对多之间的关

系）、图（多对多之间的关系）；

4、算法的定义：是对特定问题求解步骤的一种描述，使指令的有限序

列。

算法衡量的标准：时间复杂度和空间复杂度；

5、算法时间复杂度的求法：给定一段程序，求其时间复杂度；

时间复杂度的比较：O(1)O(log2n)O(n)O(nlog2^n)O(n^2)

O(n^3)O(2^n)

6、为什么学习“数据结构”？

之所以要学习数据结构的原因如下：

(1)计算机处理的数据量越来越大；

（2）数据的类型越来越多；

（3）数据的结构越来越复杂。

“数据结构”课程主要学了哪些知识？

第二章：线性表(10分)

1、线性表按照存储结构不同分为顺序表、链式表；

顺序表的特点：逻辑上相邻的两个元素在物理上也相邻；链式表的特

点：逻辑上相邻的两个元素在物理上未必相邻；（“未必”的含义是可

相邻也可以不相邻）

2、比较线性表顺序存储和链式存储的优缺点。

顺序存储有以下三个优点:

(1)方法简单，各种高级语言中都有数组，容易实现

（2）不用为表示结点间的逻辑关系而增加额外的存储开销

（3）顺序表具有按元素序号随机访问的特点

缺点：

（1）在顺序表中做插入、删除操作时，移动大量元素，效率低

（2）需要预先分配足够大的存储空间，过大过小都不好。

链表的优缺点恰好与顺序表相反。

第三章：栈和队列（20分）

1、栈和队列的特点：栈：后进先出，队列：先进先出

2、熟悉栈和队列的基本操作：初始化栈、入栈操作、出栈操作、判断

栈是否为空、取栈顶元素等。

如：经过InitQueue（Q）；EnQueue（Q,a）；EnQueue（Q,b）；DeLQueue（Q,?）

队头元素值是（）

如：ABC顺序进栈，则出栈的可能性有多少种？

3、根据实例，能够容易的判断出是栈的应用还是队列的应用？

栈的典型应用包括：进制转换，递归，表达式求值。

4、重点掌握栈的应用：进制转换算法的思想或程序。

思想：（1）若N0,则将（N%R）压入栈S中，执行（2）,；若N=0，

则将栈S的内容依次出栈，算法结束。

（2）N/R代替N，转向（1）。

程序：P(49)

第四章：数组（10分）

1、牢记对称矩阵、三角矩阵、对角矩阵的特点：

对称矩阵：关于主对角线对称；

三角矩阵：上三角或下三角矩阵主对角线以下或以上均为同一个常数；

对角矩阵：以主对角线为中心的带状区域中，即除了主对角线和主对

角线相邻两侧的若干条对角线上的元素之外，其余元素均为0。

如：设n阶对称矩阵A采用下三角储存。A在储存时所对应的一维数组SA和k

ij

的关系（）。

掌握矩阵中的元素A与一维数组SA[K]的对应关系。

ij

对称矩阵：K=I*(I+1)/2+J

三角矩阵:上三角：k=i*(2n-i+1)/2+j-i当i=j

K=n*(n+1)/2当ij

下三角：k=i*(i+1)/2+j当i=j

K=n*(n+1)/2当ij

对角矩阵：k=2*i+j

2、掌握稀疏矩阵的三元组表示法。P（69）

第五章：串（5分）

1、掌握上课介绍的9种函数名称:求串长，串拷贝，连接操作，串比

较，求字串，字串定位，串插入，删除，串替换。

及其实现结果P（81）；

如：设字符串s=“I_am_a_student！”，那么字符串s的长度为_____。

如：设字符串s1=“I_am”，s2=“