数据结构复习资料1

第一章  绪论

复习内容：

(1) 基本概念和术语

(2) 抽象数据类型的表示与实现

(3) 估算算法时间复杂度

复习题：

1.仿照三元组的抽象数据类型写出抽象数据类型有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。

ADT Rational_Num{ 

       数据对象：D={ |e1,e2∈n(n为整数集合)} 

       数据关系：R1={, e1是有理数分子，e2是有理数分母，且e2≠0 } 

       基本操作： 

       InitRational_Num (&T,v1,v2) 

       操作结果：构造了有理数T，元素e1，e2分别被赋以参数v1,v2的值。

DestroyRational_Num（&T）

       操作结果：有理数T被销毁。 

       Get（T,i,&e） 

       初始条件：有理数T已存在，    i∈{1，2}.

       操作结果：用e返回T有理数的分子和分母的值，i=1返回分子，i=2返回分母。      

Put(&T,i,e) 

       初始条件：有理数T已存在，i∈{1，2}.

       操作结果：改变有理数T的分子或分母的值为e，i=1改变分子，i=2改变分母。

       AddRational_Num (T1,T2,&T3) 

       初始条件：有理数T已存在。

       操作结果：有理数T1、T2相加，结果存入有理数T3。

SubRational_Num (T1,T2,&T3) 

       初始条件：有理数T已存在。

       操作结果：有理数T1、T2相减，结果存入有理数T3。

MulRational_Num (T1,T2,&T3) 

       初始条件：有理数T已存在。

       操作结果：有理数T1、T2相乘，结果存入有理数T3。

DivRational_Num (T1,T2,&T3) 

       初始条件：有理数T已存在。

       操作结果：有理数T1、T2相除，结果存入有理数T3。

}ADT Rational_Num

2.设n为正整数，请确定下列各程序段中前置以记号@的语句的频度：

(1) i=1;k=0;

while(i<=n-1){

  @ k+=10*i;

        i++;

}

答案：n-1

(2) for(i=2; i<=n; ++i)

for(j=2; j<=i-1; ++j)

              {++x; a[i,j]=x;}

答案：1+2+3+…+n-2=(n-1)(n-2)/2=(n2-3n+2)/2    

3. 试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值。

void Descending()

{

    scanf(x,y,z);

if(x    {temp=x;x=y;y=temp;}//使x>=y

if(y    {

        temp=z;z=y;  //使temp>z

        if(x>=temp)y=temp;

        else {y=x;x=temp;}

    }

    printf(x,y,z);

}//Descending

第二章  线性表

复习内容：

(1)   线性表的类型和定义

(2)   线性表的顺序表示和实现

(3)   线性表的链式存储和实现

(4)   一元多项式的表示及相加

线性表----顺序存储结构----顺序表

线性表----链式存储结构----链表

线性表在顺序存储结构上实现查找、插入和删除的算法

区分线性表的逻辑结构和存储结构

复习题：

1.(1) 在顺序表中插入或删除一个元素，需要平均移动【表中一半】元素，具体移动的元素个数与【表长和该元素在表中的位置】有关。

(2) 顺序表中逻辑上相邻的元素的物理位置【必定】紧邻。单链表中逻辑上相邻的元素的物理位置【不一定】紧邻。

2.例2-1   假设:有两个集合A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。  现要求一个新的集合A＝A∪B。

3.简述顺序表和单链表的优缺点。

顺序表--优点：①逻辑相邻，物理相邻②可随机存取任一元素③存储空间使用紧凑。缺点：①插入、删除操作需要移动大量的元素②预先分配空间需按最大空间分配，利用不充分③表容量难以扩充。

单链表--优点①它是一种动态结构，整个存储空间为多个链表共用②不需预先分配空间③插入、删除操作方便。①单链表的缺点②指针占用额外存储空间③不能随机存取，查找速度慢。

4. 写出按正位序建立一个单链表的算法。

void CreateList_L(LinkList &L, int n)

 {

    // 正序输入 n 个数据元素，建立带头结点的单链表

    L = (LinkList) malloc (sizeof (LNode));

    L->next = NULL;    // 先建立一个带头结点的单链表

for (i = 1; i       {

          p = (LinkList) malloc (sizeof (LNode));

          scanf(&p->data);    // 输入元素值

p->next = L->next;

          L->next = p;  // 插入

      }

} // CreateList_L 

5.已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

（1）删除P结点的语句序列是【JLGCN】。

（2）删除尾元结点的语句序列是【IKCN】。

(A)  P=P->next;

(B)  P->next = P;

(C)  P->next= P->next ->next;

(D) P= P->next ->next;

(E)  while(P!=NULL) P= P->next;

(F)  while(Q->next!=NULL) {P=Q;Q= Q->next;}

(G) while(P->next !=Q) P= P->next;

(H)  while(P->next ->next!=Q) P= P->next;

(I) while(P->next ->next!= NULL) P= P->next;

(J)   Q=P;

(K) Q=P->next;

(L)  P=L;

(M) L=L->next;

(N)  free(Q);

6. 指出以下算法中的错误和低效（即费时）之处，并将它改写为一个既正确又高效的算法。

Status DeletK(SqList &La, int I, int k)

{//本过程从顺序存储结构的线性表La中删除第i个元素起

 //的k个元素

If (i<1||k<0||i+k> La.length) return ERROR；

   //参数不合法

else { for (count=1;count for (j= La.length;j>=i+1;j--)

                   La.elem[j-1]=La.elem[j];

              La.length--;  }

   return ok;

}//DeleteK

第二个for语句中，元素前移的次序错误；

低效之处是每次删除一个元素的策略。

改正后的算法：

Status DeletK(SqList &La, int I, int k)

{//本过程从顺序存储结构的线性表La中删除第i个元素起

 //的k个元素

If (（0{ 

             for (j=i+k;j<=La.length;j++) 

                   La.elem[i++]=La.elem[j];

            La.length= La.length-k;

              return ok;

}

 else  return ERROR；

}//DeleteK

第三章  栈和队列

复习内容：

(1)   栈的定义及实现

(2)   栈的应用

(3)   队列的定义及实现

(4)   队列的应用 

复习题：

1. 栈和队列的共同特点是(   A   )。 

A.只允许在端点处插入和删除元素 

B.都是先进后出     

C.都是先进先出 

D.没有共同点

2. 利用栈的结构对列车车厢进行调度则如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？【123,132,213,231,321】②如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到（即写出以‘S’表示进栈和以‘X’表示出栈的栈操作序列）。【可以得到135426，不可能得到435612，因为‘4356’出栈说明12已在栈中，则1不可能在2之前出栈。】

3.写出检验括号匹配的算法。（见作业）

4. 假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件。head=((q.rear+MAXLEN)-q.length+1)%MAXLEN  

其中MAXLEN为队列可用的最大空间。

5. 设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ C ）。(A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M

第四章  串

复习内容：

（1）串类型的定义；

（2）串的三种存储表示，定长顺序结构。块链存储结构和堆分配存储结构；

（3）串的各种基本操作的实现及其应用。

复习题：

1. 设计在顺序存储结构上实现求子串算法。

Status SubString(SString&Sub, SString S, int pos,int len) {

// 用Sub返回串S的第pos个字符起长度为len的子串。

//其中1≤pos ≤StrLength(S) 且 0≤len≤StrLength(S)-pos+1

   if (pos<1 ||pos>S[0] || len<0 || len>S[0]-pos+1)

         return ERROR;

   Sub[1……len]=S[pos…pos+len-1]；

   Sub[0]=len；

   return OK;

} // SubString

2.已知下列字符串

a=‘THIS’,f=‘A SAMPLE’,c=‘GOOD’,d=‘NE’,b=‘’,

s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2)))),

t=Replace(f,SubString(f,3,6),c),

u=Concat(SubString(c,3,1),d),  g=‘IS’

v=Concat(s,Concat(b,Concat(t,Concat(b,u)))),

请问：s，t，v,StrLength(s),Index(v,g),Index(u,g)各是什么？

答：s='THIS SAMPLE IS’；t=‘A GOOD’；v=‘THIS SAMPLE IS A GOOD ONE’； StrLength(s)=14； Index(v,g)=3；Index(u,g)=0。

3.

第五章  数组和广义表

复习内容：

(1)   数组的类型定义

(2)   数组的顺序表示和实现

(3）  矩阵的压缩存储

(4）  广义表的定义

(5）  广义表的存储结构

复习题：

1. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。

2. 稀疏矩阵的压缩存储方法：【三元组顺序表，行逻辑链接的顺序表，十字链表】

3. 设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（ B ）。(A) 10 (B) 19 (C) 28 (D) 554. 

Loc( aij)=？

答案：Loc( aij)=Loc(a11)+[ i*(i-1)/2 +(j-1)]*L

第六章  树和二叉树

复习要求：掌握树和二叉树的概念、存储结构，基本运算及其遍历，掌握哈夫曼树的概念和构造方法。

复习内容：

(1)   树的定义和基本术语

(2)   二叉树

(3)   遍历二叉树和线索二叉树

(4)   树和森林

(5)   哈夫曼树及其应用 

复习题：

1. 画出和下列已知序列对应的树T

    树的先根次序访问序列为GFKDAIEBCHJ

树的后根次序访问序列为DIAEKFCJHBG

2. 画出和下列已知序列对应的森林F

    森林的先序访问序列为ABCDEFGHIJKL

森林的中序访问序列为CBEFDGAJIKLH

3.假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10试为这8个字母设计哈夫曼编码。使用0-7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。

WPL1=2.61      WPL2=3        方案1优于方案2

5. 一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序从1开始对全部结点编号，问：

(1)各层结点数目是多少？

(2)编号为p的结点的父结点（若存在）的编号是多少？

(3)编号为p的结点的第i个儿子结点（若存在）的编号是多少？

(4)编号为p的结点有有右兄弟的条件是什么？其右兄弟的编号是多少？

答案：

(1)第i层有ki-1个结点；

(2)p=1时，该结点为根，无父结点；否则其父结点编号为（k>=2）

(3)其第k-1个儿子的编号为p·k。所以，如果他有儿子，则其第i个儿子的编号为

p·k+（i-（k-1））；

(4)(p-1)%k≠0时，该结点有右兄弟，其右兄弟的编号为p+1。

第七章  图

复习要求：掌握图的有关概念、存储结构、遍历算法、生成树的求法以及拓扑排序的概念及求法。

复习内容：

(1)   图的定义和术语

(2)   图的存储结构

(3)   图的遍历

(4)   图的连通性问题

(5)   有向无回图及其应用

(6)   最短路径 

复习题：

1.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有___e___个和___2e__个。

2. 设有6个结点的无向图，该图至少应有(  A  )条边才能确保是一个连通图。     A.5       B.6         C.7      D.8 

3. 已知如右图所示的有向图，请给出该图的

(1) 每个顶点的入/出度；

(2) 邻接矩阵

(3) 邻接表

(4) 逆邻接表

(5) 强连通分量

答案：

(1) 每个顶点的入/出度；

(4) 逆邻接表

(5) 有3个强连通分量

4.简述图的各种存储结构的适用类型？

答：

邻接矩阵：有向图和无向图

邻接表（逆邻接表）：有向图和无向图

十字链表：有向图

邻接多重表：无向图

5. 已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。答：用克鲁斯卡尔算法得到的最小生成树为：(1,2)3,  (4,6)4,  (1,3)5,  (1,4)8,  (2,5)10,  (4,7)20

6. AOV网是一种___有向无回路_的图。7.请对下面的无向带权图，

(1) 写出它的邻接矩阵，并按普里姆算法求其最小生成树；

(2) 写出它的邻接表，并按克鲁斯卡算法求其最小生成树。