数据结构复习提要

结论（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;

} */

while( c1!='#') { }

while( ! isQEmpty(Q1) ) { }

OutQueue(Q1,c2); cout<

if( ! isQFull(Q1) ) { } else { }

OutQueue(Q1,c2); cout<>c1;

cout<

串

14.能力：

在第1章 绪论中，曾经写了一个描述“串”的ADT，并给出了其表示与实现，以及一个完整的程序。

要求：给该程序关键代码加注释，注释行数不少于总代码行的 2/3 。

#include \#include \

typedef struct str{ char *ch; int length; }HString;

//----------------基本操作算法描述---------------

bool StrAssign(HString &T, char *chars) //将chars串赋给T {

int i; char *c; if( T.ch)

free( T.ch); //这行代码有问题，思考？ for( i=0, c=chars; *c ; i++, c++) //求chars串的长度

做的 }

int StrLength( HString S) //求串长 {

return S.length; }

int StrCompare( HString S, HString T) //串大小的比较 { }

bool SubString(HString &Sub, HString S, int pos, int len) //求子串 {

if( pos<1 || pos>S.length || len<0 || len>S.length-pos+1) return false; if( Sub.ch)

free(Sub.ch); //这行代码有问题，思考？

if( !len) { Sub.ch=NULL; Sub.length=0; } else{

Sub.ch=( char*) malloc( len * sizeof( char) );//注意：这里没有检测是否内存分配成功，其实是

应该做的

for( int j=0, k=pos-1; j

Sub.ch[j] =S.ch[k];

int i;

for( i=0; i

if( S.ch[i] != T.ch[i] )

return S.ch[i] - T.ch[i];

}

return true; //赋值成功

for( int j=0; j

T.ch[j]=chars[j]; //注意：T串的末尾没有添加'\\0' T.length=i;

;

T.ch=NULL; T.length=0; } //建立一个空串

T.ch=( char *) malloc( i* sizeof( char) );//注意：这里没有检测是否内存分配成功，其实是应该

if( !i) { else {

return S.length - T.length; //请理解这一行的意思

Sub.length=len; } return true; }

int Index( HString S, HString T, int pos) //子串定位 {

if( pos>0){

n=StrLength(S); m=StrLength(T); i=pos; while( i<= n-m+1) { SubString( sub,S,i,m);

if( StrCompare( sub, T)!=0 ) i++;

else return i; //返回子串的位置 } }

return 0; //不存在子串 }

void main() { }

cin>>pos;

cout<

StrAssign( S, \ //注意：strS1.ch的末尾没有 '\\0' StrAssign( T, \ //注意：strS1.ch的末尾没有 '\\0' T.ch=NULL; T.length=0;

//初始化。其实最好将初始化过程做成一个基本操作

S.ch=NULL; S.length=0;

//初始化。其实最好将初始化过程做成一个基本操作

HString S, T, sub; int pos; int m,n,i; sub.ch=NULL; sub.length=0; int n,m,i; HString sub;

数组

知识：

15.二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址是多少？

A[4][7]和A[2][3]相差22个元素[(4×9+7)-(2×9+3)=22]

1153-1087=66 即一个数组元素占3个字节

A[6][7]和A[4][7]相差18个元素 [(6×9+7)-(4×9+7)]=18 则A[6][7]存储地址为1153+18×3=1207

16、三角矩阵和对称矩阵在进行压缩存储时有什么不同？

三角矩阵是指上（下）三角矩阵的下（上）三角（不包括对角线）中的元素均为常数C或0，所以在压缩存储时只存储上（下）三角中的元素，并加一个存储常数C的存储空间。

对称矩阵进行压缩存储时是每一对称无分配一个存储空间，将n的平方个元压缩存储在n(n+1)/2个元的空间中。

树和二叉树：

知识：

17、对于二叉树，什么情况下选用“顺序存储”较好？ 稠密的树

18、先序序列为：ABCDEFG，中序序列为：CBAEFGD，画出该二叉树，及二叉链表。

19、实现二叉链表的层序遍历，需要借助于什么数据结构？为什么？

层序遍历需要借助于“队列”完成，对二叉树遍历，除了按 先序、中序、后序遍历外，还可以按“层序”遍历。先一层的遍历完须保存下来。

20、结点权值分别是：0.05,0.29,0.07,0.08,0.14,0.23,0.03, 0.11，构造最优二叉树。

例如：1,2,3,4,5,6,7,8,9,10

1、先在序列里找权值两个最小的根结点。选1，2组成一棵二叉数。 然后，把1，2去掉。用根结点的权值3加入原序列。3，3，4,5,6,7,8,9,10 2、在新的序列中找权值两个最小的根结点.选3，3组成一棵二叉数。 然后，把3.3去掉。用根结点的权值6加入原序列，升序排列。 4,5,6，6,7,8,9,10

3、在新的序列中找权值两个最小的根结点.选4，5组成一棵二叉数。

然后，把4，5去掉。用根结点的权值9加入原序列。升序排列。6，6,7,8,9,9,10 4、在新的序列中找权值两个最小的根结点.选6，6组成一棵二叉数。 然后，把6，6去掉。用根结点的权值12加入原序列。升序排列。

7,8,9,9,10，12

5、在新的序列中找权值两个最小的根结点.选7，8组成一棵二叉数。 然后，把7，8去掉。用根结点的权值15加入原序列。升序排列。 9,9,10，12，15

6、在新的序列中找权值两个最小的根结点.选9，9组成一棵二叉数。 然后，把9，9去掉。用根结点的权值18加入原序列。升序排列。 10，12，15，18

7、在新的序列中找权值两个最小的根结点.选10，12组成一棵二叉数。 然后，把10，12去掉。用根结点的权值22加入原序列。升序排列。 15，18，22

8、在新的序列中找权值两个最小的根结点.选15，18组成一棵二叉数。 然后，把15，18去掉。用根结点的权值33加入原序列。升序排列。 22，33

9、在新的序列中找权值两个最小的根结点.选22，33组成一棵二叉数。 然后，把22，33去掉。用根结点的权值55加入原序列。55

21、能力：

1）按右图所示的二叉树建立二叉链表，然后：2）按“中序”遍历二叉链表；3）求树高度； 调试完毕后，将完整代码写在实验报告册上。

要求：将关键代码加注释，注释行数不少于总代码行的 2/3 。 1 #include

3 #include 2 typedef char elemtype;

6 4 5 typedef struct BiNTree{ /*定义二叉树结点类型*/ elemtype data;

7 struct BiNTree *lchild; struct BiNTree *rchild; 9 }BiNTree,*BiTree; /创建一棵二叉树

void CreateBiTree(BiTree &T) { if( T) free(T); cin>>ch;

if (ch=='#') T= NULL; else

{ T=(BiTNode*)malloc(sizeof(BiTNode)); T->data = ch;

CreateBiTree(T->lchild);

CreateBiTree(T->rchild); /递归创建一棵二叉树 }

return OK; }

void InOrderTraverse(BiTree T) 中序遍历 { if (T) { InOrderTraverse(T->lchild); 访问左子树 printf(\ InOrderTraverse(T->rchild); 访问右子树 } }

int Depth(BiTree T){ 求树高 int depl, depr; 左右子树的高度 if (T){ depl=Depth(T->lchild); depr=Depth(T->rchild); if (depl>=depr) return (depl+1); else return (depr+1); 返回子树高度加上根节点高度 } return 0; }

int main(void) 调用函数 { BiTree t; /*定义二叉数*/ CreateBiTree(t); printf(\中序输出\ InOrder(t); 访问二叉树 Depth(t); return 0; }

22、带“空指针域标记”的中序序列能否确定二叉树的形态？为什么？ 不能

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