数据结构复习提要

结论（10） 线性表（10） 栈队列（18） 串（4） 数组（4） 树与二叉树（17） 图（6） 查找（16） 排序（15） 算法题（26） * * * 简答题（40） * * * * * * * 综合题（24） * * * 论述题（10） * 注：

算法题： 程序填空；添加注释；写运行结果；画图；描述算法思想。 综合题： 画图；根据图表回答问题。

数据结构考试重点（答案仅供参考）

绪论

1．谈谈你对“数据结构”概念的理解。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合，在任何问题中，数据元素都不是孤立存在的。而是他们之间存在着某种关系，这种数据元素相互之间的关系称为结构，这也是我们要讨论的数据结构的主要内容。一般来说，数据结构包括以下三方面的内容： （1）数据元素之间的逻辑关系，也称数据的逻辑结构。数据的逻辑结构是抽象的，它不依赖计算机的实现，只依赖人们对事物的理解和描述。

（2）数据元素及其关系，在计算机内部（内存）中的表示，称其为数据的物理结构或数据的存储结构。

（3）数据的运算及实现，即对数据元素可以施加的操作及这些操作在相应的存储结构上的具体实现。

2．谈谈你对“抽象数据类型（ADT）”的理解。

抽象数据类型(Abstract Data Type 简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。

线性表

3． 顺序表的动态内存分配的好处是什么？

（1）长度能动态增长；根据实际需要分配所需内存大小，合理利用资源 （2）不需要预先分配存储空间；

（3）存储效率高，紧凑结构；

4． 单链表中引入“头结点”的好处是什么？ 什么情况下单链表需要使用“尾指针”？ （1）由于开始结点的位置存放在头结点的指针域中，所以对链表第一个位置的操作同其他位置一样，无须特殊处理。

(2) 只有“头指针”时，访问“头”方便，而访问“尾”不方便。有时候，根据需要，一个单向循环链表只设置尾指针，而不设置头指针。此时访问“头”和“尾”都很方便。

5． 在主调函数中构建了一个“不带头结点”的单链表L1（即该链表已完成初始化，甚至链

表已不空），在子函数中对该单链表进行 插入/删除 操作。说明 在参数传递时，使用“引用”与不使用“引用”的区别。

6． 在主调函数中 声明了 一个单链表L1，在子函数 InitLink( )中对该单链表 初始化 为一

个“带头结点”的单链表。在 “不使用引用型参数”的情况下， 1） 写出初始化函数。 typedef int data;

typedef struct LNode{ data d;

Struct LNode *next; }LNode ,*LinkList; LinkList initialize (void) { LinkList L;

L=(LinkList)malloc (sizeof(LNode);L->next=NULL;return L; }

2）写出调用该函数的语句。 Void main () { LinkList L1; L1=initialize(); . . .

return 0; }

栈队列

7． 对“链栈”， 哪一端是“栈顶”？为什么？ 链头作为栈顶

原因：链栈是运算受限的单链表，其插入和删除操作仅限制在表头位置上操作，因此将链头作为栈顶方便操作。

8． 链栈中还要不要“头结点”？为什么？

不要。原因：链栈是运算受限的单链表，其插入和删除的操作仅在链表头位置上进行。如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂。

9． 顺序栈采用动态内存分配，数据结构定义如下：

typedef struct sStack{

DataType *base; DataType *top; int stacksize; //最大容量 } SqStack;

1）如何求栈高？

Int stackHeight (SqStack sq) { return sq.top-sq.base; }

2）能否将 top 定义成 int 类型？

可以

10． 链队列的“队头”与其它链式结构（如 链栈 或者 单链表）有什么不同？

11． 为什么引入“循环队列”？ 写出循环队列 判队满，判队空 以及 求队长的表达式。 原因：为充分利用向量空间，克服\假溢出\现象 方法：

1）设置一个队长变量 2）牺牲一个元素空间

队空：Q.front= Q.rear;

队满：(Q.rear+1)%maxsize= Q.front

队长(Q.rear-Q.front+MAXSIZE)%MAXSIZE

知识：

12.对于一般的顺序存储结构，若采用“动态内存分配”，当插入元素而空间不足时，可以动态增加内存分配。而对于循环队列，能否这样做？为什么？ 不能

（1）循环队列是将顺序队列臆造成一个环状空间，当插入元素而空间不足时，动态增长内存分配会破坏循环队列的结构。

（2）循环队列队满的标志为（Q.rear+1)%maxsize==Q.front。要插入元素，只能让对头元素出队。

能力：

13.定义一个长度为k的循环队列，有一个字符串 S（长度>k ），编写程序完成 进队出队。 调试完毕后，将完整代码写在实验报告册上。

特别强调：将关键代码加注释，注释行数不少于总代码行的 2/3 。

#include \#include \

#define MAXSIZE 10; //最大队列长度

typedef char DataType;

typedef struct{

DataType *base; //初始化的动态分配存储空间

int front ,rear; //头，尾指针，若队列不空，指队头元素、队列尾元素的下一个位置 } SqQueue;

//-------------------实现-----------

void InitQueue (SqQueue &Q) //初始化队列 { }

bool isQEmpty( SqQueue Q) //判队空 { }

bool isQFull( SqQueue Q) //判队满 { }

void EnQueue(SqQueue &Q, DataType &e) //向队列中添加元素 { }

void OutQueue(SqQueue &Q, DataType &e) //出队 { }

//-------------------实现完毕-----------

void main() //调用函数 {

SqQueue Q1; InitQueue (Q1); char c1, c2;

cout<<\请读入符号串，以 # 号结束:\cin>>c1;

e=Q.base[Q.front];

Q.front=(Q.front+1)% MAXSIZE;

Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)% MAXSIZE;

if ((Q.rear+1) % MAXSIZE ==Q.front) else

return false; return true;

if (Q.front==Q.rear) else

return false; return true;

Q.base=(DataType *)malloc( MAXSIZE* sizeof( DataType) ); Q.front=Q.rear=0;