数据结构与算法分析课后习题答案
【篇一：《数据结构与算法》课后习题答案】
>2.3.2 判断题
2．顺序存储的线性表可以按序号随机存取。（√）
4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√）
6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√）
8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√）
9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√）
2.3.3 算法设计题
1．设线性表存放在向量a[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。
【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x ，最后修改表示表长的变量。
int insert (datatype a[],int *elenum,datatype x) /*设elenum为表的最大下标*/ {if (*elenum==arrsize-1) return 0; /*表已满，无法插入*/
else {i=*elenum;
while (i=0 a[i]x)/*边找位置边移动*/
{a[i+1]=a[i];
i--;
}
a[i+1]=x;/*找到的位置是插入位的下一位*/ (*elenum)++;
return 1;/*插入成功*/
}
}
时间复杂度为o(n)。
2．已知一顺序表a，其元素值非递减有序排列，编写一个算法删除顺序表中多余的值相同的元素。
【提示】对顺序表a，从第一个元素开始，查找其后与之值相同的所有元素，将它们删除；再对第二个元素做同样处理，依此类推。 void delete(seqlist *a)
{i=0;
while(ia-last)/*将第i个元素以后与其值相同的元素删除*/
{k=i+1;
while(k=a-lasta-data[i]==a-data[k])
k++;/*使k指向第一个与a[i]不同的元素*/ n=k-i-1;/*n表示要删除元素的个数*/
for(j=k;j=a-last;j++)
a-data[j-n]=a-data[j]; /*删除多余元素*/
a-last= a-last -n;
i++;
}
}
3．写一个算法，从一个给定的顺序表a中删除值在x~y(x=y)之间的所有元素，要求以较高的效率来实现。
【提示】对顺序表a，从前向后依次判断当前元素a-data[i]是否介于x和y之间，若是，并不立即删除，而是用n记录删除时应前移元素的位移量；若不是，则将a-data[i]向前移动n位。n用来记录当前已删除元素的个数。
void delete(seqlist *a,int x,int y)
{i=0;
n=0;
while (ia-last)
{if (a-data[i]=x a-data[i]=y)n++; /*若a-data[i] 介于x和y之间，n 自增*/ else a-data[i-n]=a-data[i];/*否则向前移动a-data[i]*/
i++;
}
a-last-=n;
}
4．线性表中有n个元素，每个元素是一个字符，现存于向量r[n]中，试写一算法，使r中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。
【提示】对线性表进行两次扫描，第一次将所有的字母放在前面，
第二次将所有的数字放在字母之后，其它字符之前。
int fch(char c) /*判断c是否字母*/
{if(c=ac=z||c=ac=z) return (1);
elsereturn (0);
}
int fnum(char c) /*判断c是否数字*/
{if(c=0c=9)return (1);
elsereturn (0);
}
void process(char r[n])
{low=0;
high=n-1;
while(lowhigh) /*将字母放在前面*/
{while(lowhighfch(r[low])) low++;
while(lowhigh!fch(r[high])) high--;
if(lowhigh)
{k=r[low];
r[low]=r[high];
r[high]=k;
}
}
low=low+1;
high=n-1;
while(lowhigh) /*将数字放在字母后面，其它字符前面
*/{while(lowhighfnum(r[low])) low++;
while(lowhigh!fnum(r[high])) high--;
if(lowhigh)
{k=r[low];
r[low]=r[high];
r[high]=k;
}
}
}
5．线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间
将顺序表中前m个元素和后n个元素进行整体互换。即将线性表：
（a1, a2, … , am, b1, b2, … , bn）改变为：
（b1, b2, … , bn , a1, a2, … , am）。
【提示】比较m和n的大小，若mn，则将表中元素依次前移m次；否则,将表中元素依次后移n次。
void process(seqlist *l,int m,int n)
{if(m=n)
for(i=1;i=m;i++)
{x=l-data[0];
for(k=1;k=l-last;k++)
l-data[k-1]=l-data[k];
l-data[l-last]=x;
}
else for(i=1;i=n;i++)
{x=l-data[l-last];
for(k=l-last-1;k=0;k- -)
l-data[k+1]=l-data[k];
l-data[0]=x; }
}
6．已知带头结点的单链表l中的结点是按整数值递增排列的，试写
一算法，将值为x 的结点插入到表l中，使得l仍然递增有序，并且
分析算法的时间复杂度。
linklist insert(linklist l, int x)
{p=l;
while(p-next xp-next-data)
p=p-next;/*寻找插入位置*/ s=(lnode *)malloc(sizeof(lnode)); /*
申请结点空间*/ s-data=x;/*填装结点*/
s-next=p-next;
p-next=s; /*将结点插入到链表中*/ return(l);
}
7．假设有两个已排序（递增）的单链表a和b，编写算法将它们合
并成一个链表c而不改变其排序性。
linklist combine(linklist a, linklist b)
{c=a;
rc=c;
pa=a-next; /*pa指向表a的第一个结点*/
pb=b-next; /*pb指向表b的第一个结点*/
free(b); /*释放b的头结点*/
while (pa pb) /*将pa、pb所指向结点中，值较小的一个插入到链表c的表尾*/if(pa-datapb-data)
{rc-next=pa;
rc=pa;
pa=pa-next;
}
else
{rc-next=pb;
rc=pb;
pb=pb-next;
}
if(pa) rc-next=pa;
else rc-next=pb;/*将链表a或b中剩余的部分链接到链表c的表尾*/
return(c);
}
8．假设长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点的指针，编写算法删除该结点的前驱结点。【提示】利用循环单链表的特点，通过s指针可循环找到其前驱结点p及p的前驱结点q，然后可删除结点*p。
viod delepre(lnode *s)
{lnode *p, *q;
p=s;
while (p-next!=s)
{q=p;
p=p-next;
}
q-next=s;
free(p);
}
9．已知两个单链表a和b分别表示两个集合，其元素递增排列，编写算法求出a和b的交集c，要求c同样以元素递增的单链表形式存储。
【提示】交集指的是两个单链表的元素值相同的结点的集合，为了操作方便，先让单链表c带有一个头结点，最后将其删除掉。算法中指针p用来指向a中的当前结点，指针q用来指向b中的当前结点，将其值进行比较，两者相等时，属于交集中的一个元素，两者不等时，将其较小者跳过，继续后面的比较。
linklist intersect(linklist a, linklist b)
{lnode *q, *p, *r, *s;
linklist c;
c= (lnode *)malloc(sizeof(lnode));
c-next=null;
r=c;
p=a;
q=b;
while (p q )
if (p-dataq-data) p=p-next;
else if (p-data==q-data)
{s=(lnode *)malloc(sizeof(lnode));
s-data=p-data;
r-next=s;
r=s;
p=p-next;
q=q-next;
}
else q=q-next;
r-next=null;
c=c-next;
return c;
}
10．设有一个双向链表，每个结点中除有prior、data和next域外，还有一个访问频度freq域，在链表被起用之前，该域的值初始化为零。每当在链表进行一次locata(l,x)运算后，令值为x的结点中的freq域增1，并调整表中结点的次序，使其按访问频度的非递增序列排列，以便使频繁访问的结点总是靠近表头。试写一个满足上述要
求的locata(l,x)算法。
【提示】在定位操作的同时，需要调整链表中结点的次序：每次进
行定位操作后，要查看所查找结点的freq域，将其同前面结点的
freq域进行比较，同时进行结点次序的调整。 typedef struct
dnode
【篇二：数据结构课后习题答案】
lass=txt>高等学校精品资源共享课程
绪论
第 1 章
1.1 什么是数据结构？
【答】：数据结构是指按一定的逻辑结构组成的一批数据，使用某
种存储结构将这批数据存储于计算机中，并在这些数据上定义了一
个运算集合。 1.2 数据结构涉及哪几个方面？
【答】：数据结构涉及三个方面的内容，即数据的逻辑结构、数据
的存储结构和数据的运算集合。
1.3 两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不一样，它们是否可以认作是同一个数据结构？为什么？
【答】：不能，运算集合是数据结构的重要组成部分，不同的运算
集合所确定的数据结构是不一样的，例如，栈与队列它们的逻辑结
构与存储结构可以相同，但由于它们的运算集合不一样，所以它们
是两种不同的数据结构。
1.4 线性结构的特点是什么？非线性结构的特点是什么？
【答】：线性结构元素之间的关系是一对一的，在线性结构中只有
一个开始结点和一个终端结点，其他的每一个结点有且仅有一个前
驱和一个后继结点。而非线性结构则没有这个特点，元素之间的关
系可以是一对多的或多对多的。 1.5 数据结构的存储方式有哪几种？【答】：数据结构的存储方式有顺序存储、链式存储、散列存储和
索引存储等四种方式。 1.6 算法有哪些特点？它和程序的主要区别是什么？
【答】：算法具有（1）有穷性（2）确定性（3）0 个或多个输入（4）1 个或多个输出（5）可行性等特征。程序是算法的一种描述
方式，通过程序可以在计算机上实现算法。 1.7 抽象数据类型的是什么？它有什么特点？
【答】：抽象数据类型是数据类型的进一步抽象，是大家熟知的基
本数据类型的延伸和发展。抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类
型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具
体实现，程序设计中就可以像使用基本数据类型那样，十分方便地
使用抽象数据类型。抽象数据类型的设计者根据这些描述给出操作
的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。 1.8 算法的时间复杂度指的是什么？如何表示？
【答】：算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在同一台计算机上执行的时间也不一样，另外，算法执行的时间还与输入数据的状态有关，所以对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。算法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为 n 的数据处理问题，用 t(n)表示算法基本操作的执行次数。为了评价算法的执行效率，通常采用大写 o 符号表示算法的时间复杂度，大写 o 符号给出了函数f 的一个上限。其它义如下：
3
十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
定义：f (n)=o (g (n)) 当且仅当存在正的常数 c 和 n0，使得对于所有的n≥n0，有f (n) ≤c g(n)。上述定义表明，函数 f 顶多是函数 g 的 c 倍，除非 n 小于 n0。因此对于足够大的 n (如n≥n0)， g 是 f 的一个上限（不考虑常数因子 c）。在为函数 f 提供一个上限函数 g 时，通常使用比较简单的函数形式。比较典型的形式是含有 n 的单个项（带一个常数系数）。表 1-1 列出了一些常用的 g 函数及其名称。对于表 1-1 中的对数函数 logn，没有给出对数基，原因是对于任何大于 1 的常数 a 和 b 都有 logan =logbn/logba,所以 logan 和logbn 都有一个相对的乘法系数 1/logba，其中 a 是一个常量。
表 1-1 常用的渐进函数
1.9 【答】：算法的空间复杂度是指算法在执行过程中占用的额外的辅助空间的个数。可以将它表
示为问题规模的函数，并通过大写o符号表示空间复杂度。
1.10 对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度 t(n)。
（1） i++ ;
（2） for(i=0;in;i++)
if (a[i]x) x=a[i];
（3）for(i=0;in;i++)
for(j=0;jn;j++)
;
（4）for (i=1;i=n-1;i++)
{ k=i;
for(j=i+1;j=n;j++)
if(a[j]a[j+1]) k=j; t=a[k]; a[k]=a[i]; a[i]=t; }
（5）for(i=0;in;i++)
for(j=0;jn;j++)
{++x;s=s+x;}
【答】：（1）o（1）；（2）o（n）；（3）o（n2）；（4）o
（n2）；（5）o（n2）
4
第 2 章线性表及其顺序存储
2.1 选择题
（1）表长为 n 的顺序存储的线性表，当在任何位置上插入或删除
一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（为（ a ）。
a．（n?1）/2 e．n/2
b．n f．(n+1)/2
c．n+1
d．n?1
g．(n?2)/2
（2）设栈 s 和队列 q 的初始状态为空，元素 e1、e2、e3、e4、e5 和 e6 依次通过栈 s，一个元素出栈后即进入队列 q，若 6 个元素出队的序列为 e2、e4、e3、e6、e5 和 e1，则栈 s 的容量至少应该为（ c ）。
a．6
（ b ）。
a．不确定
b．n?i+1
c．i
d．n?i
（4）在一个长度为 n 的顺序表中删除第 i 个元素（1=i=n）时，需向前移动（ a ）个元素。
a．n?i
间复杂度为（ a ）。
a．o(n)
b．o(1)
c．o(n2)
）。
d．?+*abcd d．o(n3)
（6）表达式 a*(b+c)?d 的后缀表达式是（ b
b．n?i+1
c．n?i?1
d．i
（5）若长度为 n 的线性表采用顺序存储结构存储，在第 i 个位置上插入一个新元素的时
b．4
c．3
d．2
（3）设栈的输入序列为 1、2、3… n，若输出序列的第一个元素为n，则第 i 个输出的元素为
e ），删除一个元素所需移动元素的平均个数
a．abcd*+? b．abc+*d? c．abc*+d? （7）队列是一种特殊的线性表，其特殊性在于（ c ）。
a．插入和删除在表的不同位置执行 b．插入和删除在表的两端位置执行 c．插入和删除分别在表的两端执行 d．插入和删除都在表的某一端执行（8）栈是一种特殊的线性表，具有（ b ）性质。
a．先进先出
b．先进后出
c．后进后出
d．顺序进出
（9）顺序循环队列中（数组的大小为 n），队头指示 front 指向队列的第 1 个元素，队尾指示 rear 指向队列最后元素的后 1 个位置，则循环队列中存放了 n??? 1 个元素，即循环队列满
）。的条件为（ b
a．(rear+1)%n=front?1 c．(rear)%n=front
b．(rear+1)%n=front d．rear+1=front
（10）顺序循环队列中（数组的大小为 6），队头指示 front 和队尾指示 rear 的值分别为 3 和 0，当从队列中删除 1 个元素，再插入2 个元素后，front 和 rear 的值分别为（ d ）。
a．5 和 1
b．2 和 4
c．1 和 5
d．4 和 2
2.2 什么是顺序表？什么是栈？什么是队列？
5
【答】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特
殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入
与删除操作只能在这种线性表的同一端进行（即栈顶），因此，栈
具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它
的特殊性表现在约定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因此队列具有先进先出，后进后出
的特点。
2.3 设计一个算法，求顺序表中值为 x 的结点的个数。【答】：顺
序表的存储结构定义如下（文件名 seqlist.h）： #include stdio.h
#define n 100 typedef int datatype; typedef struct {
datatype data[n]; int length; } seqlist;
/*预定义最大的数据域空间*/ /*假设数据类型为整型*/
/*此处假设数据元素只包含一个整型的关键字域*/ /*线性表长度*/
/*预定义的顺序表类型*/
算法 countx（l,x）用于求顺序表 l 中值为 x 的结点的个数。 int countx(seqlist *l,datatype x) {
int c=0; int i;
for (i=0;il-length;i++)
if (l-data[i]==x) c++; return c; }
2.4 设计一个算法，将一个顺序表倒置。即，如果顺序表各个结点值存储在一维数组 a 中，倒置的结果是使得数组 a 中的 a[0]等于原来
的最后一个元素，a[1] 等于原来的倒数第 2 个元素，…，a 的最后
一个元素等于原来的第一个元素。
【答】：顺序表的存储结构定义同题 2.3，实现顺序表倒置的算法程序如下： void verge(seqlist *l) {int t,i,j; i=0;
j=l-length-1; while (ij)
{ t=l-data[i];
l-data[i++]=l-data[j]; l-data[j--]=t; } }
2.5 已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为 x 的结点，使顺序表中的结点仍然是从小到大有序。【答】：顺序表的定义同题 2.3，实现本题要求的算法程序如下：
6
void insertx(seqlist *l,datatype x) {int j;
if (l-lengthn) { j=l-length-1;
while (j=0 l-data[j]x)
{ l-data[j+1]=l-data[j];
j--; } l-data[j+1]=x; l-length++; } }
2.6 将下列中缀表达式转换为等价的后缀表达式。
(1) 5+6*7 (2) (5-6)/7 (3) 5-6*7*8 (4) 5*7-8 (5) 5*(7-6)+8/9 (6) 7*(5-
6*8)-9 【答】：
(7) 5+6*7 (8) (5-6)/7 (9) 5-6*7*8 (10)5*7-8 (11)5*(7-6)+8/9 (12)7*(5-6*8)-9
后缀表达式：5 6 7*+ 后缀表达式：5 6-7/ 后缀表达式：5 6 7*8*- 后
缀表达式：5 7* 8- 后缀表达式：5 7 6-*8 9/+ 后缀表达式：7 5 6 8*-
*9-
2.7 循环队列存储在一个数组中，数组大小为 n，队首指针和队尾
指针分别为 front 和 rear，请写出求循环队列中当前结点个数的表
达式。
【答】：循环队列中当前结点个数的计算公式是：(n+rear-
front)%n
2.8 编号为 1,2,3,4 的四列火车通过一个栈式的列车调度站，可能得
到的调度结果有哪些？如果有 n 列火车通过调度站，请设计一个算法，输出所有可能的调度结果。【答】：
方法一：
算法思想：逐次输出所有可能，用回溯法。即：
总体：对原始序列中的每一个元素，总是先入栈，后出栈
1．入栈后的操作：a.该元素出栈；b.下一个元素入栈；
2．出栈后的操作：a.（栈中其他元素）继续出栈；b. （原始序列中）下一个数入栈；注意：回溯法，关键在于回溯，即在某分支结点x：处理 x 的一个子分支，再退回分支 x，接着处理 x 的下一个子分支,
若所有 x 的子分支处理完，再退回上一层分支节点。所谓“退回”，
7
【篇三：数据结构课后习题答案】
下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑
结构、存储结构、抽象数据类型。
答案：
数据：是客观事物的符号表示，指所有能输入到计算机中并被计算
机程序处理的符号的总称。如数学计算中用到的整数和实数，文本
编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画
等通过特殊编码定义后的数据。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指
数据元素之间存在的关系。
逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立
于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出
来的数学模型。
存储结构：数据对象在计算机中的存储表示，也称为物理结构。
抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定
义在这个模型上的一组操作的总称。具体包括三部分：数据对象、
数据对象上关系的集合和对数据对象的基本操作的集合。
2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的
含义和相互关系。答案：
例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺
序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生
记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。
这些学生记录在计算机中的存储表示就是存储结构。如果用连续的
存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如
果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。
即相同的逻辑结构，可以对应不同的存储结构。
3．简述逻辑结构的四种基本关系并画出它们的关系图。
答案：
（1）集合结构
数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。
（2）线性结构
数据元素之间存在一对一的关系。例如，将学生信息数据按照其入
学报到的时间先后顺序进行排列，将组成一个线性结构。
（3）树结构
数据元素之间存在一对多的关系。例如，在班级的管理体系中，班
长管理多个组长，每位组长管理多名组员，从而构成树形结构。
（4）图结构或网状结构
数据元素之间存在多对多的关系。例如，多位同学之间的朋友关系，任何两位同学都可以是朋友，从而构成图形结构或网状结构。
其中树结构和图结构都属于非线性结构。
四类基本逻辑结构关系图
4．存储结构由哪两种基本的存储方法实现？
答案：
（1）顺序存储结构
顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之
间的逻辑关系，通常借助程序设计语言的数组类型来描述。
（2）链式存储结构
顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，
而链式存储结构，无需占用一整块存储空间。但为了表示结点之间
的关系，需要给每个结点附加指针字段，用于存放后继元素的存储
地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。
5．选择题
（1）在数据结构中，从逻辑上可以把数据结构分成（）。
a．动态结构和静态结构 b．紧凑结构和非紧凑结构
c．线性结构和非线性结构d．内部结构和外部结构
答案：c
（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。
a．存储结构b．存储实现
c．逻辑结构d．运算实现
答案：c
（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。
a．数据具有同一特点
b．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
c．每个数据元素都一样
d．数据元素所包含的数据项的个数要相等
答案：b
（4）以下说法正确的是（）。
a．数据元素是数据的最小单位
b．数据项是数据的基本单位
c．数据结构是带有结构的各数据项的集合
d．一些表面上很不相同的数据可以有相同的逻辑结构
答案：d
解释：数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构的各数据元素的集合。
（5）算法的时间复杂度取决于（）。
a．问题的规模
答案：d
解释：算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。如某些排序的算法，其执行时间与待排序记录的初始状态有关。为此，有时会对算法有最好、最坏以及平均时间复杂度的评价。
（6）以下数据结构中，（）是非线性数据结构
a．树 b．字符串 c．队列 d．栈
答案：a
6．试分析下面各程序段的时间复杂度。
（1）x=90; y=100;
while(y0)
if(x100)
{x=x-10;y--;}
else x++;
答案：o(1)
解释：程序的执行次数为常数阶。
b．待处理数据的初态 d．a和b c．计算机的配置
（2）for (i=0; in; i++)
for (j=0; jm; j++)
a[i][j]=0;
答案：o(m*n)
解释：语句a[i][j]=0;的执行次数为m*n。
（3）s=0;
for i=0; in; i++)
for(j=0; jn; j++)
s+=b[i][j];
sum=s;
2答案：o(n)
解释：语句s+=b[i][j];的执行次数为n。
（4）i=1;
while(i=n)
i=i*3;
答案：o(log3n)
解释：语句i=i*3;的执行次数为 ?log3n?。
（5）x=0;
for(i=1; in; i++)
for (j=1; j=n-i; j++)
x++;
2答案：o(n)
解释：语句x++;的执行次数为n-1+n-2+??＋1= n(n-1)/2。
（6）x=n; //n1
y=0;
while(x≥(y+1)* (y+1))
y++;
答案：o()
解释：语句y++;的执行次数为 ?n?。 2
第2章线性表
1．选择题
（1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
a．110b．108 c．100 d．120
答案：b
解释：顺序表中的数据连续存储，所以第5个元素的地址为：
100+2*4=108。
（2）在n个结点的顺序表中，算法的时间复杂度是o(1)的操作是（）。
a．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
b．在第i个结点后插入一个新结点（1≤i≤n）
c．删除第i个结点（1≤i≤n）
d．将n个结点从小到大排序
答案：a
解释：在顺序表中插入一个结点的时间复杂度都是o(n2)，排序的时间复杂度为o(n2)或o(nlog2n)。顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是o(1)。
（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。
a．8 b．63.5 c．63d．7
答案：b
解释：平均要移动的元素个数为：n/2。
（4）链接存储的存储结构所占存储空间（）。
a．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
b．只有一部分，存放结点值
c．只有一部分，存储表示结点间关系的指针
d．分两部分，一部分存放结点值，另一部分存放结点所占单元数答案：a
（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。
a．必须是连续的 b．部分地址必须是连续的
c．一定是不连续的 d．连续或不连续都可以
答案：d
（6）线性表Ｌ在（）情况下适用于使用链式结构实现。
a．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入
c．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂
答案：b
中南大学网络教育课程考试复习题及参考答案 算法分析与设计 一、名词解释： 1.算法 2.程序 3.递归函数 4.子问题的重叠性质 5.队列式分支限界法 6.多机调度问题 7.最小生成树 二、简答题： 1.备忘录方法和动态规划算法相比有何异同？简述之。 2.简述回溯法解题的主要步骤。 3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 6.简要分析分支限界法与回溯法的异同。 7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？ 8.贪心算法求解的问题主要具有哪些性质？简述之。 9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。 10.简述分析贪心算法与动态规划算法的异同。 三、算法编写及算法应用分析题： 1.已知有3个物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。 2.按要求完成以下关于排序和查找的问题。 ①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。 ②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。 ③给出上述算法的递归算法。 ④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。 3.已知1() *() i i k k ij r r A a +=，k =1，2，3，4，5，6，r 1=5，r 2=10，r 3=3，r 4=12，r 5=5，r 6=50，r 7=6，求矩阵链积A 1×A 2×A 3×A 4×A 5×A 6的最佳求积顺序（要求给出计算步骤）。 4.根据分枝限界算法基本过程,求解0-1背包问题。 已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。 5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n 公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。 6.试用动态规划算法实现下列问题：设A 和B 是两个字符串。我们要用最少的字符操作，将字符串A 转换为字符串B ，这里所说的字符操作包括： ①删除一个字符。 ②插入一个字符。 ③将一个字符改为另一个字符。 请写出该算法。 7.对于下图使用Dijkstra 算法求由顶点a 到顶点h 的最短路径。
泛函分析答案： 1、 所有元素均为0的n ×n 矩阵 2、 设E 为一线性空间，L 是E 中的一个子集，若对任意的x,y ∈L ，以及变数λ和μ均有λx ＋μy ∈L ，则L 称为线性空间E 的一个子空间。子空间心室包含零元素，因为当λ和μ均为0时，λx ＋μy ＝0∈L ，则L 必定含零元素。 3、 设L 是线性空间E 的子空间，x 0∈E\L,则集合x 0+L={x 0+l,l ∈L}称为E 中一个线性流形。 4、 设M 是线性空间E 中一个集合，如果对任何x,y ∈M ，以及λ＋μ＝1，λ≥0，μ≥0的 λ和μ，都有λx ＋μy ∈M ，则称M 为E 中的凸集。 5、 设x,y 是线性空间E 中的两个元素，d(x,y)为其之间的距离，它必须满足以下条件： （1） 非负性：d(x,y)＞0，且d(x,y)＝0＜―――＞x=y （2） d(x,y)=d(y,x) （3） 三角不等式：d(x,y)≤d(x,z)+d(y,z) for every x,y,z ∈E n 维欧几里德空间常用距离定义： 】 设x={x 1,x 2,…x n }T ,y={y 1y 2,…y n }T d 2(x,y)=( 21 ||n i i i x y =-∑)1/2 d 1(x,y)=1 ||n i i i x y =-∑ d p (x,y) = ( 1 ||n p i i i x y =-∑ )1/p d ∞(x,y)=1max ||i i i n x y ≤≤- 6、距离空间(x,d)中的点列{x n }收敛到x 0是指d(x n ,x 0)0(n ∞)，这时记作 0lim n n x x -->∞ =，或 简单地记作x n x 0 7、设||x||是线性空间E 中的任何一个元素x 的范数，其须满足以下条件： （1）||x||≥0,且||x||＝0 iff x=0 （2）||λx||=λ||x||,λ为常数 （3）||x+y||≤||x||+||y||,for every x,y ∈E 8、设E 为线性赋范空间，｛x n ｝∞ n=1是其中的一个无穷列，如果对于任何ε>0,总存在自然数N ，使得当n>N,m>N 时，均有|x m -x n |<ε,则称序列{x n }是E 中的基本列。若E 的基本列的收敛元仍属于E ，则称E 为完备的线性赋范空间，即为Banach 空间。线性赋范空间中的基本列不一定收敛。 9、有限维的线性赋范空间必然完备，所以它必定是Banach 空间。 $ 10、如果内积空间能在由内积诱导的赋范空间完备，则此内积空间称为Hilbert 空间。 11、L 2（a,b ）为定义在(a,b)上平方可积函数空间，即设f(t)∈L 2（a,b ）, 2|()|b a f t dt ? ＜∞。 当 L 2（a,b ）中内积的定义为（f,g ）= _____ ()()b a f t g t dt ? (其中f(t),g(t)∈L 2（a,b ）)时其为Hilbert 空间。 ★ 12、算子表示一种作用，一种映射。设X 和Y 是给定的两个线性赋范空间，集合D ?X ， 若对D 中的每一个x ，均有Y 中的一个确定的变量y 与其对应，则说这种对应关系确定
第一章习题（1-1,1-2,1-3,1-6） 1-1 求下列函数的渐进表达式 3n2+10n = O(n2) n2/10+2n = O(2n) 21+1/n = O(1) logn3 = O(logn) 10log3n = O(n) 知识点： 如果存在正的常数C和自然数N0，使得： 当N>=N0时有f(N)<=Cg(N)，则称f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)). 这时，可以说f(N)的阶不高于g(N)的阶。 1-2 论O(1)和O(2)的区别 O(1)和O(2)差别仅在于其中的常数因子，根据渐进上界记号O的定义可知，O(1)=O(2)。
1-3 从低到高排列以下表达式（按渐进阶排列以下表达式） 结果：2 logn n2/320n 4n23n n! 分析： 当n>=1时，有logn< n2/3 当n>=7时，有3n< n! 补充： 当n>=4时，有logn> n1/3 1-6 对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=Θ(g(n))。 知识点： f(n)的阶不高于g(n)的阶：f(n)=O(g(n))；f(n)的阶不低于g(n)的阶：f(n)=Ω(g(n))；f(n)与g(n)同阶：f(n)=Θ(g(n)) (1)f(n)= logn2。g(n)= logn+5 f(n)与g(n)同阶，故f(n)=Θ(g(n)) (2) f(n)= logn2。g(n)= n1/2 当n>=8时，f(n)<=g(n)，故f(n)=O(g(n))
分析：此类题目不易直接看出阶的高低，可用几个数字代入观察结果。 如依次用n=1,21,22,23,26,28,210 (3) f(n)= n 。g(n)= log2n f(n)=Ω(g(n)) (4) f(n)= nlogn+n。g(n)= logn f(n)=Ω(g(n)) (5) f(n)= 10 。g(n)= log10 f(n)=Θ(g(n)) (6) f(n)= log2n。g(n)= logn f(n)=Ω(g(n)) (7) f(n)= 2n。g(n)= 100 n2 f(n)=Ω(g(n)) (8) f(n)= 2n。g(n)= 3n f(n)=O(g(n))
泛函分析答案： 1、所有元素均为0的n ×n 矩阵 2、设E 为一线性空间，L 是E 中的一个子集，若对任意的x,y ∈L ，以及变数λ和μ均有λx ＋μy ∈L ，则L 称为线性空间E 的一个子空间。子空间心室包含零元素，因为当λ和μ均为0时，λx ＋μy ＝0∈L ，则L 必定含零元素。 3、设L 是线性空间E 的子空间，x 0∈E\L,则集合x 0+L={x 0+l,l ∈L}称为E 中一个线性流形。 4、设M 是线性空间E 中一个集合，如果对任何x,y ∈M ，以及λ＋μ＝1，λ≥0，μ≥0的λ和μ，都有λx ＋μy ∈M ，则称M 为E 中的凸集。 5、设x,y 是线性空间E 中的两个元素，d(x,y)为其之间的距离，它必须满足以下条件： （1） 非负性：d(x,y)＞0，且d(x,y)＝0＜―――＞x=y （2） d(x,y)=d(y,x) （3） 三角不等式：d(x,y)≤d(x,z)+d(y,z)foreveryx,y,z ∈E n 维欧几里德空间常用距离定义： 设x={x 1,x 2,…x n }T ,y={y 1y 2,…y n }T d 2(x,y)=(21 ||n i i i x y =-∑)1/2 d 1(x,y)=1 ||n i i i x y =-∑ d p (x,y)=(1 ||n p i i i x y =-∑)1/p d ∞(x,y)=1max ||i i i n x y ≤≤- 6、距离空间(x,d)中的点列{x n }收敛到x 0是指d(x n ,x 0)?0(n ?∞)，这时记作 0lim n n x x -->∞ =，或简单地记作x n ?x 0 7、设||x||是线性空间E 中的任何一个元素x 的范数，其须满足以下条件： （1）||x||≥0,且||x||＝0 iffx=0 （2）||λx||=λ||x||,λ为常数 （3）||x+y||≤||x||+||y||,foreveryx,y ∈E 8、设E 为线性赋范空间，｛x n ｝∞n=1是其中的一个无穷列，如果对于任何ε>0,总存在自然数N ，使得当n>N,m>N 时，均有|x m -x n |<ε,则称序列{x n }是E 中的基本列。若E 的基本列的收敛元仍属于E ，则称E 为完备的线性赋范空间，即为Banach 空间。线性赋范空间中的基本列不一定收敛。 9、有限维的线性赋范空间必然完备，所以它必定是Banach 空间。 10、如果内积空间能在由内积诱导的赋范空间完备，则此内积空间称为Hilbert 空间。 11、L 2 （a,b ）为定义在(a,b)上平方可积函数空间，即设f(t)∈L 2 （a,b ）,2|()|b a f t dt ?＜∞。
Chapter11:Amortized Analysis 11.1When the number of trees after the insertions is more than the number before. 11.2Although each insertion takes roughly log N ,and each DeleteMin takes2log N actual time,our accounting system is charging these particular operations as2for the insertion and3log N ?2for the DeleteMin. The total time is still the same;this is an accounting gimmick.If the number of insertions and DeleteMins are roughly equivalent,then it really is just a gimmick and not very meaningful;the bound has more signi?cance if,for instance,there are N insertions and O (N / log N )DeleteMins (in which case,the total time is linear). 11.3Insert the sequence N ,N +1,N ?1,N +2,N ?2,N +3,...,1,2N into an initially empty skew heap.The right path has N nodes,so any operation could take?(N )time. 11.5We implement DecreaseKey(X,H)as follows:If lowering the value of X creates a heap order violation,then cut X from its parent,which creates a new skew heap H 1with the new value of X as a root,and also makes the old skew heap H smaller.This operation might also increase the potential of H ,but only by at most log N .We now merge H and H 1.The total amortized time of the Merge is O (log N ),so the total time of the DecreaseKey operation is O (log N ). 11.8For the zig ?zig case,the actual cost is2,and the potential change is R f ( X )+ R f ( P )+ R f ( G )? R i ( X )? R i ( P )? R i ( G ).This gives an amortized time bound of AT zig ?zig =2+ R f ( X )+ R f ( P )+ R f ( G )? R i ( X )? R i ( P )? R i ( G ) Since R f ( X )= R i ( G ),this reduces to =2+ R f ( P )+ R f ( G )? R i ( X )? R i ( P ) Also,R f ( X )> R f ( P )and R i ( X )< R i ( P ),so AT zig ?zig <2+ R f ( X )+ R f ( G )?2R i ( X ) Since S i ( X )+ S f ( G )< S f ( X ),it follows that R i ( X )+ R f ( G )<2R f ( X )?2. Thus AT zig ?zig <3R f ( X )?3R i ( X ) 11.9(a)Choose W (i )=1/ N for each item.Then for any access of node X ,R f ( X )=0,and R i ( X )≥?log N ,so the amortized access for each item is at most3log N +1,and the net potential drop over the sequence is at most N log N ,giving a bound of O (M log N + M + N log N ),as claimed. (b)Assign a weight of q i /M to items i .Then R f ( X )=0,R i ( X )≥log(q i /M ),so the amortized cost of accessing item i is at most3log(M /q i )+1,and the theorem follows immediately. 11.10(a)To merge two splay trees T 1and T 2,we access each node in the smaller tree and insert it into the larger tree.Each time a node is accessed,it joins a tree that is at least
第十章 曲线积分 一、证明题 1.证明:若函数f 在光滑曲线L:x=x(t),y=y(t)(β≤≤αt )上连续，则存在点()L y ,x 00∈，使得，()?L ds y ,x f =()L y ,x f 00? 其中L ?为L 的长。 二、计算题 1.计算下列第一型曲线积分: (1) ()?+L ds y x ,其中L 是以0(0,0),A(1,0)B(0,1)为顶点的三角形; (2) ()?+L 2122ds y x ,其中L 是以原点为中心,R 为半径的右半圆周; (3) ?L xyds ,其中L 为椭圆22a x +22 b y =1在第一象限中的部分; (4) ?L ds y ,其中L 为单位圆22y x +=1; (5) () ?++L 222ds z y x ,其中L 为螺旋线x=acost,y=asinr, z=bt(π≤≤2t 0)的一段; (6) ?L xyzds ,其中L 是曲线x=t,y=3t 232,z=2t 2 1 ()1t 0≤≤的一段; (7) ?+L 22ds z y 2,其中L 是222z y x ++=2a 与x=y 相交的圆周. 2.求曲线x=a,y=at,z=2at 21(0a ,1t 0>≤≤)的质量,设其线密度为a z 2=ρ, 3.求摆线x=a(t －sint),y=a(1－cost)(π≤≤t 0)的重心,设其质量分布是均匀的. 4.若曲线以极坐()θρ=ρ()21θ≤θ≤θ表示,试给出计算 ()?L ds y ,x f 的公式.并用此公式计算下列曲线积分.
(1)? +L y x ds e 22,其中L 为曲线ρ=a ??? ??π≤θ≤40的一段; (2)?L xds ,其中L 为对数螺线θ=ρx ae (x>0)在圆r=a 内的部分. 5.设有一质量分布不均匀的半圆弧,x=rcos θ,y=rsin θ(π≤θ≤0),其线密度θ=ρa (a 为常数),求它对原点(θ,0)处质量为m 的质点的引力. 6.计算第二型曲线积分: (1) ?-L ydx xdy ,其中L 为本节例2的三种情形; (2) ()?+-L dy dx y a 2,其中L 为摞线x=a(t-sint),y=a(1-cost)(π≤≤2t 0)沿t 增加方向的 一段; (3) ?++-L 22y x ydy xdx ,其中L 为圆周222a y x =+,依逆时针方向; (4)?+L xdy sin ydx ,其中L 为y=sinx(π≤≤x 0) 与x 轴所围的闭曲线,依顺时针方向; (5)?++L zdz ydy xdx ,其中L 为从(1,1,1)到(2,3,4)的直线段. 7.质点受力的作用,力的反方向指向原点,大小与质点离原点的距离成正比,若质点由(a,0)沿椭圆移动到(0,b),求力所作的功. 8.设质点受力的作用,力的方向指向原点,大小与质点到xy 平面的距离成反比,若质点沿直线x=at,y=bt,z=ct(0c ≠) 从M(a,b,c)到N(2a,2b,2c),求力所作的功. 9.计算沿空间曲线的第二型曲线积分: (1) ?L xyzddz ,其中L 为x 2+y 2+z 2=1与y=z 相交的圆,其方向按曲线依次经过1,2,7,8卦限; (2) ()()() ?-+-+-L 222222dz y x dy x z dx z y ,其中L 为球面x 2+y 2+z 2=1在第一卦限部分的边界线,其方向按曲线依次经过xy 平面部分,yz 平面部分和zx 平面部分 .
第二章 度量空间 作业题答案提示 1、 试问在R 上，()()2,x y x y ρ=- 能定义度量吗？ 答：不能，因为三角不等式不成立。如取 则有(),4x y ρ=,而(),1x z ρ=，(),1z x ρ= 2、 试证明：（1）()1 2 ,x y x y ρ= -;(2)(),1x y x y x y ρ-= +-在R 上都定 义了度量。 证：（1）仅证明三角不等式。注意到 2 11 22x y x z z y x z z y ?? -≤-+-≤-+- ? ?? 故有1 112 22 x y x z z y -≤-+- （2）仅证明三角不等式 易证函数()1x x x ?=+在R +上是单调增加的， 所 以 有 ()() a b a b ??+≤+,从而有 1111a b a b a b a b a b a b ++≤≤+ ++++++ 令,,x y z R ?∈,令,a z x b y z =-=- 即111y x z x y z y x z x y z ---≤+ +-+-+-
4.试证明在[]b a C ,1 上，)12.3.2()()(),(?-=b a dt t y t x y x ρ 定义了度量。 证：（1）0)()(0),(≡-?=t y t x y x ρ（因为x,y 是连续函数） 0),(≥y x ρ及),(),(x y y x ρρ=显然成立。 []) ,(),()()()()()()()()()()(),()2(y z z x dt t y t z dt t z t x dt t y t z dt t z t x dt t y t x y x b a b a b a b a ρρρ+≤-+-≤-+-≤-=???? 5.试由Cauchy-Schwarz 不等式证明 ∑∑==≤?? ? ??n i i n i i x n x 12 2 1 证：∑∑∑∑=====?≤?? ? ??n i i n i n i i n i i x n x x 12 12 122 11 8.试证明下列各式都在度量空间()11,ρR 和()21,R R 的Descartes 积 21R R R ?=上定义了度量 {}2 12/1222121,max ~~)3(;)(~)2(;)1(ρρρρρρρρρ=+=+= 证：仅证三角不等式。（1）略。 (2) 设12(,)x x x =，12(,)y y y =12R R ∈?，则
第七章 习题解答 1．设（X ，d ）为一度量空间，令 }),(,|{),(},),(,|{),(0000εεεε≤∈=<∈=x x d X x x x S x x d X x x x U 问),(0εx U 的闭包是否等于),(0εx S ？ 解 不一定。例如离散空间（X ，d ）。)1,(0x U ={0x }，而)1,(0x S =X 。 因此当X 多于两点时，)1,(0x U 的闭包不等于)1,(0x S 。 2. 设 ],[b a C ∞是区间],[b a 上无限次可微函数的全体，定义 证明],[b a C ∞按),(g f d 成度量空间。 证明 （1）若),(g f d =0，则) ()(1)()(max ) () ()()(t g t f t g t f r r r r b t a -+-≤≤=0，即f=g （2）)()(1)()(max 2 1 ),()()()()(0t g t f t g t f g f d r r r r b t a r r -+-=≤≤∞ =∑ =d （f ，g ）+d （g ，h ） 因此],[b a C ∞按),(g f d 成度量空间。 3． 设B 是度量空间X 中的闭集，证明必有一列开集ΛΛn o o o 21,包含B ，而且B o n n =?∞ =1 。 证明 令n n n o n n B x d Bo o .2,1},1 ),({K =<==是开集：设n o x ∈0，则存在B x ∈1，使 n x x d 1),(10<。设,0),(1 10>-=x x d n δ则易验证n o x U ?),(0δ，这就证明了n o 是 开集 显然B o n n ??∞=1 。若n n o x ∞ =?∈1 则对每一个n ，有B x n ∈使n x x d 1 ),(1< ，因此
习题1 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C++描述。 //采用分治法 //对数组先进行快速排序 //在依次比较相邻的差 #include qsort(l,1,n); //第一个作为枢轴，从第一个排到第n个 } int main() { int a[11]={0,2,32,43,23,45,36,57,14,27,39}; int value=0;//将最小差的值赋值给value for (int b=1;b<11;b++) cout< 第一章绪论 一、选择题 1.组成数据的基本单位是（） （A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ①（A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ②（A）结构（B）关系（C）运算（D）算法 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。 ①（A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法 ②（A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 习题 1．验证下列等式 （1） C x f dx x f +='?)()( （2）?+=C x f x df )()( 证明 （1）因为)(x f 是)(x f '的一个原函数，所以?+='C x f dx x f )()(. （2）因为C u du +=?, 所以? +=C x f x df )()(. 2．求一曲线)(x f y =, 使得在曲线上每一点),(y x 处的切线斜率为x 2, 且通过点 )5,2(. 解 由导数的几何意义, 知x x f 2)(=', 所以C x xdx dx x f x f +=='= ??22)()(. 于是知曲线为C x y +=2 , 再由条件“曲线通过点)5,2(”知，当2=x 时，5=y , 所以 有 C +=2 25, 解得1=C , 从而所求曲线为12 +=x y 3．验证x x y sgn 2 2 =是||x 在),(∞+-∞上的一个原函数. 证明 当0>x 时, 22x y =, x y ='; 当0 第一章 1. 算法分析题 算法分析题1－1 求下列函数的渐进表达式 (1). 3n^2 + 10n < 3n^2 + 10n^2 = 13n^2 = O(n^2) (2). n^2 / 10 + 2^n 当n>5是，n^2 < 2 ^n 所以，当n >= 1时，n^2/10 < 2 ^n 故: n^2/10 + 2^n < 2 ^n + 2^n = 2*2^n = O(2^n) (3). 21 + 1/n < 21 + 1 = 22 = O(1) (4). log(n^3)=3log(n)=O(log(n)) (5). 10log(3^n) = (10log3)n = O(n) 算法分析题1-6 (1)因为：f(n)=log(n^2) = 2log(n); g(n) = log(n) + 5 所以：f(n)=Θ(log(n)+5) =Θ(g(n)) (2)因为：log(n) < √n; f(n) = 2log(n); g(n)= √n 所以：f(n) = O(g(n)) (3)因为：log(n) < n; f(n) = n; g(n) = log(n^2) = 2log(n) 所以；f(n) = Ω(g(n)) (4)因为：f(n) = nlogn +n; g(n) = logn 所以：f(n) =Ω(g(n)) (5)因为: f(n) = 10; g(n) = log(10) 所以:f(n) =Θ(g(n)) (6)因为: f(n)=log^2(n); g(n) = log(n) 所以: f(n) ==Ω(g(n)) (7)因为: f(n) = 2^n < 100*2^n; g(n)=100n^2; 2^n > n ^2 所以: f(n) = Ω(g(n)) (8)因为：f(n) = 2^n; g(n) = 3 ^n; 2 ^n < 3 ^n 所以: f(n) = O(g(n)) 习题1－9 证明：如果一个算法在平均情况下的计算时间复杂性为Θ(f(n)),该算法在最坏情况下所需的计算时间为Ω(f(n)). 分析与解答： 因此，Tmax(N) = Ω(Tavg(N)) = Ω(Θ(f(n)))=Ω(f(n)). 第二章 算法分析题 泛函分析复习题2012 1．在实数轴R 上，令p y x y x d ||),(-=，当p 为何值时，R 是度量 空间，p 为何值时，R 是赋范空间。 解：若R 是度量空间，所以R z y x ∈?,,，必须有： ),(),(),(z y d y x d z x d +≤成立 即p p p z y y x z x ||||||-+-≤-，取1,0,1-===z y x ， 有2112=+≤p p p ，所以，1≤p 若R 是赋范空间，p x x x d ||||||)0,(==，所以R k x ∈?,， 必须有：||||||||||x k kx ?=成立，即p p x k kx ||||||=，1=p ， 当1≤p 时，若R 是度量空间，1=p 时，若R 是赋范空间。 2．若),(d X 是度量空间，则)1,m in(1d d =，d d d +=12也是使X 成为度量空间。 解：由于),(d X 是度量空间，所以X z y x ∈?,,有： 1）0),(≥y x d ，因此0)1),,(m in(),(1≥=y x d y x d 和0) ,(1) ,(),(2≥+= y x d y x d y x d 且当y x =时0),(=y x d ， 于是0)1),,(m in(),(1==y x d y x d 和0) ,(1) ,(),(2=+=y x d y x d y x d 以及若 0)1),,(m in(),(1==y x d y x d 或0) ,(1) ,(),(2=+= y x d y x d y x d 均有0),(=y x d 成立，于是y x =成立 2）),(),(y x d x y d =， 因此),()1),,(m in()1),,(m in(),(11y x d y x d x y d x y d === 和),() ,(1) ,(),(1),(),(22y x d y x d y x d x y d x y d x y d =+=+= 3）),(),(),(z y d y x d z x d +≤，因此 }1),,(),(m in{)1),,(m in(),(1z y d y x d z x d z x d +≤= ),(),()1),,(m in()1),,(m in(11z y d y x d z y d y x d +=+≤ 以及设x x x f += 1)(，0)1(1)(2 >+='x x f ，所以)(x f 单增， 所以) ,(),(1),(),(),(1),(),(2z y d y x d z y d y x d z x d z x d z x d +++≤+= ),(),(1) ,(),(),(1),(z y d y x d z y d z y d y x d y x d +++++= ),(),() ,(1) ,(),(1),(22z y d y x d z y d z y d y x d y x d +=+++≤ 综上所述)1,m in(1d d =和d d d += 12均满足度量空间的三条件， 故),(1y x d 和),(2y x d 均使X 成为度量空间。 题目描述：设计蛮力算法求解小规模的线性规划问题，假设约束条件为： （1）x+y<=4;(2)x+3y<=6;(3)x>+0;y>=0，使目标函数3x+5y取得最大值 */ /* 思路：用两个for遍历用一个if比较找出最大的。 */ #include 算法分析与设计教程 习题解答 第1章 算法引论 1. 解：算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列计算方法。 频率计数是指计算机执行程序中的某一条语句的执行次数。 多项式时间算法是指可用多项式函数对某算法进行计算时间限界的算法。 指数时间算法是指某算法的计算时间只能使用指数函数限界的算法。 2. 解：算法分析的目的是使算法设计者知道为完成一项任务所设计的算法的优劣，进而促 使人们想方设法地设计出一些效率更高效的算法，以便达到少花钱、多办事、办好事的经济效果。 3. 解：事前分析是指求出某个算法的一个时间限界函数（它是一些有关参数的函数）；事 后测试指收集计算机对于某个算法的执行时间和占用空间的统计资料。 4. 解：评价一个算法应从事前分析和事后测试这两个阶段进行，事前分析主要应从时间复 杂度和空间复杂度这两个维度进行分析；事后测试主要应对所评价的算法作时空性能分布图。 5. 解：①n=11； ②n=12； ③n=982； ④n=39。 第2章 递归算法与分治算法 1． 解：递归算法是将归纳法的思想应用于算法设计之中，递归算法充分地利用了计算机系统内部机能，自动实现调用过程中对于相关且必要的信息的保存与恢复；分治算法是把一个问题划分为一个或多个子问题，每个子问题与原问题具有完全相同的解决思路，进而可以按照递归的思路进行求解。 2． 解：通过分治算法的一般设计步骤进行说明。 3． 解：int fibonacci(int n) { if(n<=1) return 1; return fibonacci(n-1)+fibonacci(n-2); } 4. 解：void hanoi(int n,int a,int b,int c) { if(n>0) { hanoi(n-1,a,c,b); move(a,b); hanoi(n-1,c,b,a); } } 5. 解：① 22*2)(--=n n f n ② )log *()(n n n f O = 泛函分析题1_3列紧集p19 1.3.1 在完备的度量空间中，求证：为了子集A是列紧的，其充分必要条件是对?ε > 0，存在A的列紧的ε网． 证明：(1) 若子集A是列紧的，由Hausdorff定理， ?ε > 0，存在A的有限ε网N． 而有限集是列紧的，故存在A的列紧的ε网N． (2) 若?ε > 0，存在A的列紧的ε/2网B． 因B列紧，由Hausdorff定理，存在B的有限ε/2网C． 因C ?B ?A，故C为A的有限ε网． 因空间是完备的，再用Hausdorff定理，知A是列紧的． 1.3.2 在度量空间中，求证：紧集上的连续函数必是有界的，并且能达到它的上、下确界． 证明：设(X, ρ)是度量空间，D是紧子集，f : D→ 是连续函数． (1) 若f无上界，则?n∈ +，存在x n∈D，使得f (x n) > 1/n． 因D是紧集，故D是自列紧的． 所以{x n}存在收敛子列x n(k) →x0∈D (k→∞)． 由f的连续性，f (x n(k))→f (x0) (k→∞)． 但由f (x n) > 1/n知f (x n)→ +∞(n→∞)， 所以 f (x n(k))→ +∞ (k→∞)，矛盾． 故f有上界．同理，故f有下界． (2) 设M = sup x∈D f(x)，则?n∈ +，存在y n∈D，使得f (y n) > M- 1/n． {y n}存在子列y n(k) →y0∈D (k→∞)． 因此f ( y0 ) ≥M． 而根据M的定义，又有f ( y0 ) ≤M． 所以f ( y0 ) = M．因此f能达到它的上确界． 同理，f能达到它的下确界． 1.3.3 在度量空间中，求证：完全有界的集合是有界的，并通过考虑l 2的子集E = {e k }k≥ 1，其中e k = { 0, 0, ..., 1, 0, ... } (只是第k个坐标为1，其余都是0 )，来说明一个集合可以是有界的但不完全有界的． 证明：(1) 若A是度量空间(X, ρ)中的完全有界集． 则存在A的有限1-网N = { x0, x1, x2, ..., x n }． 令R = ∑1 ≤j≤nρ(x0, x j) + 1． 则?x∈A，存在某个j使得0 ≤j≤n，且ρ(x, x j) < 1． 因此，ρ(x, x0) ≤ρ(x, x j) + ρ(x j, x0) ≤ 1 + ∑1 ≤j≤nρ(x0, x j) = R． 所以A是度量空间(X, ρ)中的有界集． (2) 注意到ρ(e k , e j) = 21/2 ( ?k ≠ j )， 故E中任意点列都不是Cauchy列． 所以，E中任意点列都没有收敛子列(否则，该收敛子列就是Cauchy列，矛盾)．严蔚敏 数据结构课后习题及答案解析
数学分析课后习题答案(华东师范大学版)
算法设计与分析课后习题
最新泛函分析考试题集与答案
算法分析与设计第三章课后练习题
算法分析与设计教程习题解答_秦明
泛函分析答案
相关主题
文本预览