数据结构 - 图文

习题一

1. 简要回答术语：数据，数据元素，数据结构，数据类型。

数据(data)：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素（data element）：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象（data object）:是性质相同的数据元素的集合，是数据的一个子集。

数据结构（data structure）:是相互之间存在一种或多种特定关系的数据元素的集合，有集合、线性结构和树形结构。

数据类型（data type）：是一个值的集合和定义在这个值集上的一组操作的总称。

2. 数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是？

数据的逻辑结构：是数据元素间的逻辑关系。

数据的物理结构：是数据结构在计算机中的表示（或映像）。 区别：逻辑结构是指数据之间的联系，而物理结构是指数据的存放位置。

联系：任何一个算法设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。 3. 数据结构的主要运算包括哪些？

答：数据结构的主要运算包括： ⑴ 建立(Create)一个数据结构； ⑵ 消除(Destroy)一个数据结构；

⑶ 从一个数据结构中删除(Delete)一个数据元素； ⑷ 把一个数据元素插入(Insert)到一个数据结构中； ⑸ 对一个数据结构进行访问(Access)；

⑹ 对一个数据结构(中的数据元素)进行修改(Modify)； ⑺ 对一个数据结构进行排序(Sort)； ⑻ 对一个数据结构进行查找(Search)。 4. 算法分析的目的是什么？算法分析的主要方面是什么？ 算法分析的目的是：分析算法的效率以求改进。

算法分析的主要方面：算法的空间复杂度和时间复杂度、算法的正确

性和简单性。

5. 分析一下程序段的时间复杂度，请说明分析的理由或原因。 （1）基本操作的语句频度为：2n，其时间复杂度为：O(n)。 （2）基本操作的语句频度为：1+2+3+?+n=n(n-1)/2，其时间复杂度为：O(n2) 。

（3） 基本操作的语句频度为：n，其时间复杂度为：O(n)。 （1） Sum1 (int n)

{ int p=1,sum=0,m; for(m=1; m<=n; m++) {p*=m; sum+=p;} Return (sum); } （2）

Sum2 (int n) { int sum=0,m,t; For(m=1; m<=n; m++) { p=1;

For(t=1; t<=m; t++) p*=t; Sum+=p;

}

Return (sum); } (3) Fact(int n)

{ if (n<=1) return 1; Else return (n*fact(n-1));

}

习题二

1. 简述下列术语：线性表，顺序表，链表

答：线性表：最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。

顺序表：是指用一组连续的存储单元一次存储线性表中的数据元素。物理结构和逻辑结构都相邻。

链表：逻辑结构相邻的数据元素物理结构不一定相邻。采用指针的形式连接起来。

2 何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么?

不需要经常大量的修改表或需要随机存取的情况下可以选用顺序表； 相反需要经常大量的修改表，但不是频繁的随机存取的情况下可选用链式表。

3 在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个因素?

答：平均需要移动n/2个结点。表的长度，和要插入的位置。 4 链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解?

答：有序。有序性体现在通过指针数据元素有序的相连。物理上不一定要相邻。

5 设顺序表L是递增有序表，试写一算法，将x插入到L中并使L仍是递增有序表。

Status ListInsert(SqList &L,int i,ElemType e) {

if((i>L.length+1)||i<1) {

newbase=(ElemType return ERROR; if(L.length>=L.listsize)

*)realloc((L.listsize+LISTINCREMENT)*sizeof(ElemType));

}

if(!newbase) exit(-1);

L.elem=newbase;

L.listsize+=LISTINCREMENT; }

ElemType *q,*p; q=&L.elem[i-1];

for(p=&L.elem[L.length-1];p>=q;p--)

*(p+1)=*p; *q=e; L.length++; return OK;

6 写一求单链表的结点数目ListLength(L)的算法。 int ListLength(L) {

int i=0; ElemType *p; p=&L; if(!p) }

exit(-1); if(p.next==NULL) return 0;

while(p.next!=NULL) { } p++; i++; else

return i;

7 写一算法将单链表中值重复的结点删除，使所得的结果链表中所有结点的值均不相同。 void DeletElem(SqList L) { }

8 写一算法从一给定的向量A删除值在x到y(x≤y)之间的所有元素(注意：x和y是给定的参数，可以和表中的元素相同，也可以不同)。 void DeletElem(SqList L,int x,int y) {

ElemType *p,*q; int i=0;

ElemType *p,*q,*s; int i=1; int j;

p=&L.next.next; for(i;i

q=&L.next; for(j=1;j<=i;j++) { } p++;

if(q->data==p->data) {

p.next=(p-1).next; s=p; free(s);

p++;

}

if(j>i)

图解：

8. 假设Q[0,5]是一个循环列队，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。 d，e，b，g，h入队 d，e出队

i，j，k，l，m入队 b出队

n，o，p，q，r入队 图解：

习题四

1. 解释下列术语的区别：空串和空白串：主串和字串；目标串和模式串 解：空串和空白串的区别：空串不含任何字符，它的长度为0，而空白串含有一个空格，它的长度为1.

主串和子串的区别：主串是相对于子串而言的，子串是主串中连续的一段，是主串的一个子集。

目标串和模式串的区别：目标串是在模式匹配中的主串，是相对于模式串运算的母串，而模式串是子串，是在主串中运算的子串。 2. 若X和Y是两个采用顺序结果存储的串，写一算法比较这两个字符串是否相等。 解：

int streql(Hstring x, Hstring y) if(x[0]!=y[0]) return (0); else i=1;

while(x[i]==y[i]&&i

3. 写一算法void StrRelace(char *T,char *P,char *S)，将T中第一次出现的与P相等的子串替换为S，串S和P的长度不一定相等，并分析时间复杂度。

size_t lenT, lenP, lenS; char *e;

if ( !T || !P || !S ) return; e = strstr( T, P ); if ( !e ) return; lenT = strlen( T ); lenP = strlen( P ); lenS = strlen( S );

memmove( e+lenS, e+lenP, lenT+1-(e-T)-lenP );

memcpy( e, s, lenS ); 假定三个长度 t、p、s 。 strstr: O(t*p) strlen*3: O(t+p+s)

memmove: O(t-p) memcpy:O(s) 最终复杂度 O(t*p+2(t+s)) -> O(n^2)。 可以看出热点在 strstr 函数。

如果将其通过 kmp 或类似的匹配算法优化成 O(n) 的，那么复杂度可以直接降为 O(n) 。

习题五

1. 什么事广义表？请简述广义表与线性表的区别。

广义表是零至多个元素的有限序列，广义表中的元素可以是原子，也可以是子表。从“元素的有限序列”角度看，广义表满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于扩充的线性结构（只不过元素并不具有同一类型：可以是原子，也可以是广义表）。当广义表中的元素都是原子时，广义表就蜕变为线性表。

广义表是线性表的推广，线性表是广义表的特例。当广义表中的元素都是原子时，即为线性表。

2. 一个广义表是（a,(a,b),d,e,(a,(I,j),k)），请画出该广义表的链式存储结构。 图解：

10a110a10b∧10d10e11∧10a10i10j∧10k∧

3. 设有二维数组a[6][8]，每个元素占相邻的4个字节，存储器按字节编址，已知a的起始地址是1000，试计算： （1） 数组a的最后一个元素a[5][7]起始地址； （2） 按行序优先时，元素a[4][6]的起始地址； （3） 按列序优先时，元素a[4][6]的起始地址；

LOC(a[5][7])=LOC(a[0][0])+47*4=1188 LOC(a[4][6])=LOC(a[0][0])+(4?8+6)?4=1152 LOC(a[4][6])=LOC(a[0][0])+（6*6+4）?4=1160

4. 设A和B是稀疏矩阵，都是以三元组作为存储结构，请写出矩阵相加的算法，其结果存放在三元组表C中，并分析时间复杂度。 5. 设有稀疏矩阵B如下图所示，请画出该稀疏矩阵的三元组表和十字

链表存储结构。

图解：

12331-3384432462521865467573-3

图中未标记空指针，作业中请注意标记

习题六

1．假设在树中，结点X是结点y的双亲时，用（x,y）来表示树边。

已知一棵树的树边集合为{（e,i）,（b,e）, (b,d)，(a,b)，(g，j)，(c,g)，(c,f)，(h,l)，(c,h)，(a,c)}，用树型表示发表示该树，并回到下列问题： （1）哪个是根节点？哪些是子叶结点？哪些是g的双亲？哪些是g的祖先？哪些g的孩子？哪些是e的子孙？哪些是e的兄弟？哪些是f的兄弟？ g a c b hfdeilj如图：a为根节点 j 、l（是爱乐） 、f 、d 以及i为叶子节点 ； C为g的双亲节点； a 和c为g的祖先；g的孩子为j节点；e的子孙只有i节点。

e的兄弟节点为d； f节点的兄弟有g和h节点。

（2）b和n的层次格式多少？输的深度是多少？以结点c为根的子树的深度是多少？

B的层次格式为2，h的深度为3；树的深度为4 以节点c为根的子树的深度为3.

2. 一颗深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都是k棵非空子树，如果按照层次顺序（同层自左至右）从1开始对全部结点编号，问： （1）各层的结点数是多少？

i层的节点数目为k^(i-1)

（2）编号为i的结点的双亲结点（若存在）的编号是多少？

编号为i的节点的双亲节点（若存在）的标号为：?（i-2）/k?+1; （3）编号为i的节点的第j个孩子结点（若存在）编号是多少？ 编号为i的节点的第j个孩子节点存在（若存在）编号为 pij=（i-1）*k+2+j-1=(i-1)*k+j+1;

（4） 编号为i的结点的有右兄弟的条件是什么？其右兄弟的编号是多少？

有兄弟的条件为： i%k!=1; 3.设有如6-27图示的二叉树，

（1）分别用顺序存储方法和链接存储方法画出这个二叉树的存储结构。（2）写出该二叉树的先序、中序、后序遍历序列。

a b d e f c g h k m n 顺序存储方法

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 a b c d e f g h k m n 链式存储方法

NULL NULL h NULL NULL e NULL NULL m NULL NULL n NULL a b c d NULL e NULL f NULL g

先序遍历：a b d e h k c f g m n; 中序遍历：d b h e k a f c m g n; 后序遍历：d h k e b f m n g c a;

4. 一直一颗二叉树先序遍历序列和中序遍历序列分别为ABDGHCEFI

和GDHBAECIF，请画出这课二叉树，然后给出该树的后序遍历序列。

A B C D E F GH I 后序遍历：G H D B E I F C A

5. 设一棵二叉树的中序遍历序列和后序遍历序列分别为BDCEAFHG

和DECBHGFA，请画出这课二叉树，然后给出该树的的先序序列。

A B F C G D E H 先序遍历：A B C D E F G H

6.已知一颗二叉树的中序遍历序列和后序遍历序列分别为dgbaekchif

和gdbkeihfca，请画出这课二叉树对应的中序线索树和后序线索树。 中序遍历的线索树

a 前驱 g c 后继

后继 前驱 前驱 b e d 后继 f 后继 后继 k h 前 i 后序遍历的线索树

a g c d b efk h i 7.以二叉链表为存储结构，请分别写出求二叉树的结点总数及叶子结点总数的算法。

#include #include

struct inform /*建立输入信息结构体inform*/ { char data;

int l; int r;

int signl; /*作为标记的signl,signr*/ int signr; };

struct leafnode /*建立叶子节点结构体*/ {

char leaf; leafnode* lchild; leafnode* rchild; };

void print(inform* ps, int n); void judge ( inform* ps );

leafnode* creatree(); /*声明二叉树的建立函数*/ void preorder (leafnode* T); /*声明先序遍历函数*/ void inorder (leafnode* T); /*声明中序遍历函数*/ void postorder (leafnode* T); /*声明后序遍历函数*/ char a[100]; int k=1; int s=0; inform *p;

void main() {

/*-------------------------------按格式输入信息-----------------------------------*/ int n;

cout<<\请输入二叉树内容：第一行为节点总数n ，后面的n行是节点的具体形式：\ cout<<\ cin>>n;

p=(inform* )malloc( n*sizeof(inform) ); /*开辟的一个叶子结构

体型的指针数组*/ inform *p1; p1=p;

for(int i=0; i

cin>>(p+i)->data>>(p+i)->l>>(p+i)->r;

if((p+i)->l != -1) (p+i)->signl=1; /*用signl signr 的0，1标示输入的信息中是否有左或右孩子*/ else (p+i)->signl= 0;

if((p+i)->r !=-1) (p+i)->signr=1; else (p+i)->signr= 0; }

/*--------------------------------------------------------------------------------------------*/

a[0]= p->data;

judge ( p1 ); /*用递归算法将输入数据信息转为线性字符串*/

cout</*------------------------------------------遍历-----------------------------------*/ leafnode* T; T= creatree(); /*先续遍历二叉树*/

cout<<\先序遍历二叉树： \ preorder( T );

cout<

cout<

/*------------------------------------------函数定义

-------------------------------*/

void judge( inform* ps ) /*用函数的递归来将输入的信息转化为线性的数组*/ {

inform* b; if (ps->signl==0) { a[k]='@'; k++; } else {

b = p+(ps->l); a[k] = b->data; k++; judge(b); }

if ((ps->signr) == 0) {

a[k]='@'; k++; } else {

b = p+(ps->r ); a[k] = b->data; k++; judge(b); } }

leafnode* creatree() /*建立二叉树函数*/

{ char ch; leafnode *t; ch= a[s]; s++; if(ch=='@') {

t=NULL; } else {

t=(leafnode* )malloc(sizeof(leafnode)); t->leaf=ch; t->lchild=creatree(); t->rchild=creatree(); }

return t; }

/*先序遍历的递归函数*/ void preorder (leafnode* T) { if(T) {

cout<leaf; preorder(T->lchild); preorder(T->rchild); } }

/*中序遍历的递归函数*/ void inorder (leafnode* T) {

if(T) {

inorder(T->lchild); cout<leaf; inorder(T->rchild); } }

/*后序遍历的递归函数*/ void postorder (leafnode* T) { if(T) {

postorder(T->lchild); postorder(T->rchild); cout<leaf; } }

8.设图6-27的二叉树是森林F所对应的二叉树，请画出森林F。

d a b d e f c g h k m n 转换为森林

a c g n b e k f m h

01234abcde21213101403??2?3?1? 逆邻接链表

01234abcde231211040342?4??2? ?⑶ 对图7-27所示的带权无向图。

① 写出相应的邻接矩阵表示。 ② 写出相应的边表表示。 ③ 求出各顶点的度。 邻接矩阵：

∞ 9 6 3 ∞ ∞ 9 ∞ ∞ 5 8 ∞ 6 ∞ ∞ 2 9 5 3 5 2 ∞ ∞ 7 ∞ 8 9 ∞ ∞ 4 ∞ ∞ 5 7 4 ∞

边表表示：

顶点表012345123456边表0 1 90 2 60 3 31 3 51 4 82 3 22 4 92 5 53 5 74 5 4

各顶点的度：

顶点1的度：3 顶点2的度：3 顶点3的度：4

顶点4的度：4 顶点5的度：3 顶点6的度：3

⑷ 已知有向图的逆邻接链表如图7-28所示。

① 画出该有向图。

② 写出相应的邻接矩阵表示。

③ 写出从顶点V1开始的深度优先和广度优先遍历序列。 ④ 画出从顶点V1开始的深度优先和广度优先生成树。 有向图：

V2V3V1V5V4邻接矩阵表示：

0 1 0 1 0 1 0 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 1 1 0

深度优先遍历序列：V1 V4 V3 广度优先遍历序列：V1 V2 V4 V3 V5

深度优先生成树

V1V4V3V5V2

广度优先生成树

V5 V2

V3 V5或V1 V4 V2 V1V4V2V3V5

5.一个带权连通图的最小生成树是否唯一？在什么情况下可能不唯一？

一个带权联通图的最小生成树不一定唯一。若是途中同时存在若干个全职相同的彼岸，选择不同点起点，可得到不同的最小生成树，但这些最小生成树边上权值之和均为定值。

6.对于图7-27所示的带权无向图

（1）按照Prime算法给出从顶点2开始构造最小生成树的过程 （2）按照Kruskal算法给出开始构造最小生成树的过程

（1）Prime

例题

(2) Kruskal

12.设计一个算法利用图的遍历方法输出一个无向图G中从顶点Vi到Vj的长度为S的简单路径，设图采用邻接链表作为存储结构。

#include \#define MAX 5 typedef struct ArcNode { /*单链表中的结点的类型*/ int adjvex; /*该边指向的顶点在顺序表中的位置*/ struct ArcNode *next; /*下一条边*/ }ArcNode;

typedef struct VNode { /*顶点类型*/

int data; /*顶点中的数据信息*/

ArcNode *firstarc; /*指向单链表，即指向第一条边*/ }VNode;

int visited[5]={0,0,0,0,0}; //标记数组 //先创建顶点，再创建指向 CreatGraph(int n , VNode G[] ) {

int i,e; ArcNode *p , *q;

printf(\ for(i=0;i

scanf(\

G[i].firstarc = NULL; /*初始化第一条边为空*/ }

for(i=0;i

printf(\ scanf(\

while(e!=-1) //为每一个顶点循环创建指向

{ p = (ArcNode *)malloc(sizeof(ArcNode)); /*创建一条边*/ p->next = NULL; p->adjvex = e;

if(G[i].firstarc == NULL) G[i].firstarc = p; /*i结点的第一条边*/

else

q->next = p; /*下一条边*/ q = p; scanf(\ } } }

int FirstAdj(VNode G[],int v) {

if(G[v].firstarc != NULL)

return (G[v].firstarc)->adjvex; return -1; int NextAdj(VNode G[],int v) {

ArcNode *p; p = G[v].firstarc; while( p!= NULL) {

if(visited[p->adjvex]) //如果访问过了就继续找下一个结点 p = p->next; else

return p->adjvex; //如果找到未访问过的就返回 } return -1; }

void DFS(VNode G[],int v)

{ int w; printf(\访问当前顶点,打印出该顶点中的数据信息*/

visited[v] = 1; /*将顶点v对应的访问标记置1*/

w = FirstAdj(G,v); /*找到顶点v的第一个邻接点，如果无邻接点，返回-1*/ while(w != -1) {

//退出递归条件有二：一是直到某节点无指向，二是该深度没有可以访问的顶点

if(visited[w] == 0) /*该顶点未被访问*/ DFS(G,w); /*递归地进行深度优先搜索*/ w = NextAdj(G,v); /*找到顶点v的下一个邻接点，如果无邻接点，返回-1*/ } }

int main(void) { int i = 0,n;

VNode G[5]; //顶点容器 printf(\

scanf(\ {

if(visited[i] == 0) DFS(G,i); }

printf(\}

13.假设一个工程的进度计划用AOE网表示，如图7-33所示 （1）求出每个事件的最早发生时间和最晚发生时间 （2）该工程完工至少需要多少时间？ （3）求出所有关键路径和关键活动。 关键路径的算法思想：

1>从ve[0]=0开始利用递推公式求出其余顶点的最早发生时间ve[j] ve[j]=Max{ve[i]+dut}

(i=0,1,2,….n-1 j=1,2,…n-1 ∈E ) 即从源点开始按拓扑有序求各顶点的最早发生时间

2>从vl[n-1]=ve[n-1]开始利用递推公式求出其余顶点的最迟发生时间vl[j]； vl[j]=Min{vl[k]-dut}

3>求出每条弧(即活动)的最早开始时间e[i]与最迟开始时间l[i] e[i]=ve[j]; l[i]=vl[k]-dut

若 e[i]=l[i]即为关键活动。由关键活动组成的路径即关键路径 v1最早发生时间:ve[1]=ve[0]+a1=0+5=5; v2最早发生时间:ve[2]=ve[0]+a2=0+6=6;

v3最早发生时间:有两条路v0->v1->v3,路径长度为5+3=8；v0->v2->3, 路径长度为6+12=18；取最大的即公式中的Max{ve[i]+dut}的含义ve[3]=18

ve[4]=18+3=21;ve[5]=21;ve[6]=23;ve[7]=25;ve[8]=28;ve[9]=30; 假定vl[l]=ve[9]=30反向递推其余顶点的最迟发生时间 vl[8]=vl[9]-a14=30-2=28; vl[7]=vl[8]-a13=28-2=26; vl[6]=vl[8]-a12=28-5=23; vl[5]=26;

vl[4]有两路：vl[6]-a9=22;vl[7]-a10=26-10=16取最小的16 其他依次类推：然后是

3>求出每条弧(即活动)的最早开始时间e[i]与最迟开始时间l[i] e[i]=ve[j]; l[i]=vl[k]-dut

找到 e[i]=l[i]的活动即关键活动。由关键活动组成的路径即关键路径

习题九

1. 对于一个有n个元素的线性表，若采用顺序查找方法时的平均查找长度是什么？若结点是有序的，则采用折半查找法时的平均查找长度是什么？ 答：217页 221页

2. 设查找表采用单链表存储，请分别写出对该表进行顺序查找的静态查找的算法和动态查找的算法。 静态查找算法

动态查找算法：

3. 设二叉排序树中的关键字互不相同：则

（1） 最小元素无左孩子，最大元素无右孩子，此命题是否正确？ 答：此命题正确。

（2） 最大和最小元素一定是叶子结点吗？ 答:最小值结点和最大值结点不一定是叶子结点 （3） 一个新结点总是插入在叶子结点上吗？

答：一个新结点不一定总是插在二叉排序树的某叶子上。 4. 试比较哈希表构造时几种冲突处理方法的优点和缺点 答：开放定址法

线性探测再散列,，冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表

二次探测再散列，这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。

伪随机探测再散列，线性探测再散列容易产生“二次聚集”，即在处理同义词的冲突时又导致非同义词的冲突。线性探测再散列的优点是：只要哈希表不满，就一定能找到一个不冲突的哈希地址，而二次

探测再散列和伪随机探测再散列则不一定。

再哈希法这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。 建立公共溢出区

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

5. 将关键字序列（10,2,26,4,18,24,21,15,8,23,5,12,14）一次插入到初态为空的二叉排序树中，请画出所得到的树T:然后画出删除10之后的二叉排序树T1：若再将10插入到T1中得到的二叉排序树T2是否

与T1相同？请给出T2的先序、中序、后序序列。 6．

设有关键字序列为i:

（Dec,Feb,Nov,Oct,June,Sept,Aug,Apr,May,July,Jan,Mar），请手工构造一棵二叉排序树。该树是平衡二叉排序树？若不是，请为其构造一棵平衡二叉排序树。

7设关键字序列是（19,14,23,01,68,84,27,55,11,34,79），散列表长度

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