习题11．解释以下概念：逻辑结构，存储结构，操作，数据结构，数据结构的表示，数据结构的实现，抽象数据类型，算法，算法的时间代价，算法的空间代价，大O 表示法。

2．理解以下关系：算法与数据结构的关系；数据结构与抽象数据类型的关系；算法和数据结构与问题求解的关系。

3. 写出下列程序段的平均情况下的时间代价O表示式。

(1) a=b+c;d=a+e(2) sum=0;for (i=0;i<3;i++)for (j=0;j<n;j++)sum++;(3) x=n;y=0;while (x>=(y+1)*(y+1))y++;(4) s=0;if(even(n))for (i=0;i<n;i++)sum++;elses=s+n;(5) x=66;n=200;while (n>0){if(x>lO0){ x=x-10;n=n-1;}elsex=x+1;}4．对于给定的n个元素，可以构造出的逻辑结构有，，，四种。

5.按增长率由小到大的顺序排列下列各函数：2100, (32)n, (23)n, (43)n, n n, n32, n!, n, log2n, n/log2n习题22.1已知L是无头结点的单链表，且p结点既不是第一个结点，也不是最后一个结点，试从下列提供的语句中选出合适的语句序列：(1)在p结点之后插入s结点：(2)在p结点之前插入s结点：(3)在单链表L首插入s结点：(4)在单链表L后插入s结点：提供的语句：①p->next＝s；②p->next＝p->next->next；③p->next=s->next；④s->next=p->next；⑤s->next＝L；⑥s->next=p；⑦s->next=NULL；⑧q＝p；⑨while(p->next!=q)p=p->next；⑩while(p->next!=NULL)p=p->next；⑾p=q；⑿p=L；⒀L＝s；⒁L＝p；2.2已知p结点是某双向链表的中间结点，试从下列提供的语句中选出合适的语句序列。

(1)在p结点之后插入s结点：(2)在p结点之前插入s结点：(3)删除p结点的直接后继结点：(4)删除p结点的直接前驱结点：提供的语句：①p->next＝p->next->next；②p->prior=p->prior->prior；③p->next=s；④p->prior=s；⑤s->next=p；⑥s->prior＝p；⑦s->next=p->next；⑧s->prior=p->prior；⑨p->prior->next=p->next；⑩p->prior->next＝p；⑾p->next->prior＝p；⑿p->next->prior＝s；⒀p->prior->next=s；⒁p->next->prior=p->prior；⒂q=p->next；⒃q=p->prior；⒄free(p)；⒅free(q)；2.3试编写一个计算头结点指针为L的单链表长度的算法。

2.4试编写一个将单循环链表逆置的算法。

2.5已知一顺序表A，其元素值非递减有序排列，编写一个算法，删除顺序表中多余的值相同的元素。

习题33.1 简述栈和线性表的区别。

简述栈和队列的相同点和不同点。

3.2 如果进栈的数据元素序列为1、2、3、4、5、6，能否得到4、3、5、6、1、2和1、3、5、4、2、6的出栈序列?并说明为什么得不到或如何得到。

3.3 利用两个栈模拟一个队列的入队、出队和判断队列空的运算。

3.4 写一算法，将一个顺序栈中的元素依次取出，并打印元素值。

3.5 写一算法，将一个非负十进制整数转换成二进制。

3.6 写一算法，将一个链式队列中的元素依次取出，并打印元素值。

3.7 设有编号为1、2、3、4的4辆车，顺序进入一个栈式结构的站台，试写出这4辆车开出站台的所有可能的顺序。

3.8 写一个算法，借助于栈将一个单链表逆置。

习题44.1 空串和空格串有什么区别?4.2 两个字符串相等的充要条件是什么?4.3 串的三种机内表示方法是什么?4.4 设S＝'I am a student'，T＝'good'，Q＝'worker'。

求：(1)StrLength(S)(2)SubString(&Sub，S，8，7)(3)SubString(&Sub，T，2，1)(4)Index(S，'a'，1)(5)Index(S，T，1)(6)Replace(&S，'Student'，Q)(7)Concat(&N，SubString(&V，S，6，2)，Concat(&P，T，SubString(&W,S,7,8)))4.5 设A＝'This'，F＝'a sample'，C＝'good'，D＝'ne'，B＝' '，G＝'is'。

求：(1)Coneat(&S，A，Concat(&Z，SubString(&Y，F，2，7)，Concat(&X，B，SubString(A，3，2))))(2)Concat(&U，SubString(&X，C，3，1)，D)(3) Replace(&F，SubString(&X，F，3，6)，C)(4)StrLength(S)(5)Index(V，G，1)(6)Index(U，G，1)(7) Concat(&V，S，Concat(&Z，B，Concat(&Y，F，Concat(&X，B，U))))4.6 利用C的库函数strlen、strcpy(或strcat)写一个算法voidStrDelete(char *S,int i,int m)，删除串S中从位置i开始连续的m个字符。

若i≥strlen(S)，则没有字符被删除；若i+m≥strlen(S)，则S中从位置i开始直至末尾的字符均被删去.。

4.7 采用顺序结构存储串，编写一个函数，求串s和串t的一个最长的公共子串。

提示: 需要采用三重循环来实现。

习题51.假设按行优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是100，每个整数占4个字节。

问下列元素的存储地址是什么?(1) a0000 (2) a1111 (3) a3125 (4) a82472.假设一个准对角矩阵按以下方式存储于一维数组B[4m]中：写出由一对下标(i,j) 求k的转换公式。

3.现有如下的稀疏矩阵A，要求画出三元组表示法。

习题610. 假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。

试为这8个字母设计赫夫曼编码。

使用0～7的二进制表示形式是另一种编码方案。

对于上述实例，比较两种方案的优缺点。

11．一棵度为2的树与一棵二叉树有何区别?树与二叉树之间有何区别?12．对于如图所示的树，试给出：(1)双亲数组表示法示意图；(2)孩子链表表示法示意图；(3)孩子兄弟链表表示法示意图。

13．画出下图所示的森林经转换后所对应的二叉树，并指出在二叉链表中某结点所对应的森林中结点为叶子结点的条件。

14．将如图所示的二叉树转换成相应的森林。

15．在具有n(n>1)个结点的各棵树中，其中深度最小的那棵树的深度是多少?它共有多少叶子和非叶子结点?其中深度最大的那棵树的深度是多少?它共有多少叶子和非叶子结点?16．画出和下列已知序列对应的树T：树的先根访问序列为：GFKDAIEBCHJ；树的后根访问序列为：DIAEKFCJHBG。

17．画出和下列已知序列对应的森林F：森林的先序访问序列为：ABCDEFGHIJKL；森林的中序访问序列为：CBEFDGAJIKLH。

18．对以孩子－兄弟链表表示的树编写计算树的深度的算法。

习题71 对于右图所示的有向图，试给出：(1)每个顶点的入度和出度。

(2)邻接矩阵。

(3)邻接表。

(4)逆邻接表。

(5)强连通分量。

2 设无向图G如右图所示，试给出：(1)该图的邻接矩阵。

(2)该图的邻接表。

(3)该图的多重邻接表。

(4)从v0出发的“深度优先”遍历序列。

(5)从v0出发的“广度优先”遍历序列。

3请对下边的无向带权图，(1)写出它的邻接矩阵，并按普里姆算法求其最小生成树；(2)写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。

4 对下图所示的带权有向图G，试回答以下问题：(1)求出G中从结点v1出发按深度优先搜索遍历G所得到结点序列；(2)求出G中从结点v1出发按广度优先搜索遍历G所得的结点序列；5 对于下图所示的带权图(1)按照普里姆算法，从顶点v1出发生成最小生成树，按生成次序写出各条边；(2)按照克鲁斯卡尔算法，生成最小生成树，按生成次序写出各条边；(3)画出其最小生成树，并求出它的权值。

6 写出下图所示的AOV网的全部可能的拓扑有序序列。

7 对下图所示的带权有向图G，试回答以下问题：(1)写出其带权邻接矩阵arcs；(2)求出从顶点v1到其他各顶点之间的最短路径。