发布时间 : 星期日 文章数据结构课后答案 - 北邮更新完毕开始阅读44bf282258fb770bf78a55fd
习题1
1. 填空题
（1）（___________）是指数据之间的相互关系，即数据的组织形式。通常人们认为它包含三个方面的内容，分别为数据的（___________）、（___________）及其运算。
答案：数据结构 逻辑结构 存储结构 （2）（___________）是数据的基本单位，在计算机程序中通常作为一个整体进行处理。 答案：数据元素 （3）数据元素之间的不同逻辑关系代表不同的逻辑结构，常见的逻辑结构有（___________）、（___________）、（___________）和（___________）。
答案：集合 线形结构 树结构 图结构
（4）数据的存储结构考虑的是如何在计算机中存储各个数据元素，并且同时兼顾数据元素间的逻辑关系。基本的存储结构通常有两大类：（___________）和（___________）。 答案：顺序存储结构 链式存储结构
（5）通常一个问题可以有多种不同的算法，但每个算法必须满足5个准则：输入、输出、（___________）、（___________）和（___________）。 答案：有穷性 确定性 可行性
（6）通常通过衡量算法的（___________）复杂度和（___________）复杂度来判定一个算法的好坏。
答案：时间 空间
（7）常见时间复杂性的量级有：常数阶O（___________）、对数阶O（___________）、线性阶O（___________）、线性对数阶O（___________）、平方阶O（___________）、和指数阶O（___________）。通常认为，当问题规模较大时，具有（___________）量级的算法是不可计算的。
答案：1 logn n nlogn n2 2n 指数
（8）STL提供的标准容器有顺序容器、（___________）和（___________）。 答案：排序容器 哈希容器
（9）算法可认为是STL的精髓，所有算法都是采用（___________）的形式提供的。 答案：函数模版
（10）通常认为STL由空间管理器、迭代器、泛函、适配器、（___________）和（___________）等六部分构成，其中前面四部分服务于后面两部分。 答案：容器 算法
2. 选择题
（1）以下结构中，（ ）属于线性结构。 A. 树 B. 图 C. 串 D. 集合 （2）算法描述的方法有很多种，常常将（ ）称为算法语言。 A. 自然语言 B. 流程图 C. 伪代码 D. 程序设计语言 （3）现实生活中的家族谱，可认为是一种（ ）结构。
A. 树 B. 图 C. 集合 D. 线性表 （4）手机中存储的电话号码簿，可认为是一种（ ）结构。 A. 树 B. 图 C. 集合 D. 线性表 （5）NP问题是（ ）。
A. 非多项式时间问题，即非P问题 B. 非确定性多项式时间问题
C. P问题的子集 D. 与P问题不相交的 （6）以下（ ）不属于STL的顺序容器。 A. 向量（vector） B. 列表（list） C. 队列（queue） D.双端队列（deque） （7）下面带有@标记的语句的频度(n>10)是（ ）。
for(int i=0;i for(int j=i+1;j @cout< A. n*(n-1)/2 B. n*n/2 n?2n?1n?2分析：??1??n?1?i?(n?1)n?0j?i?1i?02 i3. 分析以下程序段的时间复杂度。 （1）for (i=l; i<=n; i++) { k++; for (j=1; j<=n; j++) m += k; } （3）i=1; while (i<=n) i *= 2; （5）k=100,i=10; do { if (i i++; }while (i while (y*y*y <= n) y++; （8）int i=0; while(i C. n*(n+1)/2 D. 不确定 （2）for (i=l; i<=n; i++) k++; for (j=1; j<=n; j++) m += k; （4）i=1; while (i<=n) i += 2; （6）for (i=0; i<100; i++) for (j=0; j sum += j; 答案： (1) (2) (3) (4) O(n) O(n) O(logn) O(n) 2 (5) O(1) (6) O(1) (7) O(n1/3) (8) O(n) 4. 将整数设计为一个类，将整数相关的常见数学运算设计为类的接口并进行实现，如求与 给定值的最大公约数、最小公倍数、枚举所有因子等。 解： #include \#include %using std::vector; //定义自然数类 class NaturalNumber{ public: }; //返回欧几里德算法求解最大公约数 unsigned long int NaturalNumber :: EUCLID(NaturalNumber & nn) { } //返回最大公约数 unsigned long int NaturalNumber :: GreatestCommonDivisor(NaturalNumber & nn) unsigned long int m = (num > nn.num) ? num : nn.num; //较大的自然数赋值给m unsigned long int n = (num < nn.num) ? num : nn.num; //较小的自然数赋值给n unsigned long int r = m % n; while (r != 0){ } return n; m = n; n = r; r = m % n; //……其它外部接口 unsigned long int EUCLID(NaturalNumber & n); //欧几里德算法求解最大公约数 unsigned long int num; //存储真正的自然数 NaturalNumber(unsigned long int n=0):num(n){} unsigned long int GreatestCommonDivisor(NaturalNumber & nn);//求解最大公约数 unsigned long int LeaseCommonMultiple(NaturalNumber & nn);//求解最小公约数 int GetFactors(vector //求所有因子，存储在factors 中，函数返回因子个数 private: { } //返回最小公倍数 unsigned long int NaturalNumber :: LeaseCommonMultiple(NaturalNumber & nn) { } int NaturalNumber :: GetFactors( vector void main() { } NaturalNumber p(1); int xx = p.GreatestCommonDivisor(NaturalNumber(120)); int yy = p.LeaseCommonMultiple(NaturalNumber(120)); vector int m = sqrt((double)num); vector if ( m*m == num ) { t++; factors.push_back(m);} vector it--; factors.push_back(*it); if ( 0 == num%i ) {t+=2; factors.push_back(i);bigfactors.push_back(num/i);} unsigned long int temp = EUCLID(nn); return num * nn.GetNumber() / temp; return EUCLID(nn); }while (it!=bigfactors.begin()); return t; 习题2 1. 填空题 （1）在一个单链表中，已知每个结点包含data和next两个域，q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（___________）和（___________）操作。