北邮数据结构课后答案.pdf-资料库

《数据结构与 STL》教师手册 ver 0.1 肖波徐雅静莫骁肖晶 2010 年 9 月

目录习题 1........................................................................................................................................3 习题 2........................................................................................................................................7 习题 3......................................................................................................................................12 习题 4......................................................................................................................................16 习题 5......................................................................................................................................19 习题 6......................................................................................................................................26 习题 7......................................................................................................................................29 习题 8......................................................................................................................................32

习题 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. 树（2）算法描述的方法有很多种，常常将（）称为算法语言。 A. 自然语言（3）现实生活中的家族谱，可认为是一种（）结构。 A. 树（4）手机中存储的电话号码簿，可认为是一种（）结构。 A. 树 D. 程序设计语言 D. 线性表 D. 线性表 C. 伪代码 B. 流程图 C. 集合 C. 集合 D. 集合 C. 串 B. 图 B. 图 B. 图

B. 非确定性多项式时间问题 D. 与 P 问题不相交的（5）NP 问题是（）。 A. 非多项式时间问题，即非 P 问题 C. P 问题的子集（6）以下（）不属于 STL 的顺序容器。 A. 向量（vector）（7）下面带有@标记的语句的频度(n>10)是（）。 @cout<

答案： (1) O(n2) (2) O(n) (3) O(logn) (4) O(n) (5) O(1) (6) O(1) (7) O(n1/3) (8) O(n) 4. 将整数设计为一个类，将整数相关的常见数学运算设计为类的接口并进行实现，如求与给定值的最大公约数、最小公倍数、枚举所有因子等。解： #include "math.h" #include "vector" using std::vector; //定义自然数类 class NaturalNumber{ public: NaturalNumber(unsigned long int n=0):num(n){} unsigned long int GreatestCommonDivisor(NaturalNumber & nn);//求解最大公约数 unsigned long int LeaseCommonMultiple(NaturalNumber & nn);//求解最小公约数 int GetFactors(vector & factors); //求所有因子，存储在factors 中，函数返回因子个数 unsigned long int GetNumber(){return num;} //……其它外部接口 private: unsigned long int EUCLID(NaturalNumber & n); //欧几里德算法求解最大公约数 unsigned long int num; //存储真正的自然数 }; //返回欧几里德算法求解最大公约数 unsigned long int NaturalNumber :: EUCLID(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){ m = n; n = r; r = m % n; } return n; //返回最大公约数 unsigned long int NaturalNumber :: GreatestCommonDivisor(NaturalNumber & nn) 5

{ } return EUCLID(nn); //返回最小公倍数 unsigned long int NaturalNumber :: LeaseCommonMultiple(NaturalNumber & nn) { } unsigned long int temp = EUCLID(nn); return num * nn.GetNumber() / temp; int NaturalNumber :: GetFactors( vector & factors ) { int t=0; int m = sqrt((double)num); vector bigfactors; for (unsigned long int i=1;i ::iterator it=bigfactors.end(); if (bigfactors.size()) do { it--; factors.push_back(*it); }while (it!=bigfactors.begin()); return t; } void main() NaturalNumber p(1); int xx = p.GreatestCommonDivisor(NaturalNumber(120)); int yy = p.LeaseCommonMultiple(NaturalNumber(120)); vector f; int t = p.GetFactors(f); { } 6

习题 2 1. 填空题（1）在一个单链表中，已知每个结点包含 data 和 next 两个域，q 所指结点是 p 所指结点的直接前驱，若在 q 和 p 之间插入 s 所指结点，则执行（___________）和（___________）操作。答案：q->next = s; s->next = p; 或 s->next=q->next; q->next = s; （2）表长为 n 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（___________），删除一个元素需要移动元素的平均个数为（___________）。答案：n/2 (n-1)/2 （3）表长为 0 的线性表称为（___________）。答案：空表（4 ）动态内存管理是操作系统的基本功能之一，其作用是响应用户程序对内存的（___________）和（___________）请求。答案：申请释放（5）顺序表多采用（___________）实现的，是一种随机存取结构，对表中任意结点存取操作的时间复杂度为（___________）。而查找链表中的结节，需要从头指针起顺着链扫描才能得到，平均时间复杂度为（___________）。因此，若线性表的操作主要是进行查找，很少进行插入或删除操作时，采用（___________）表比较合适。答案：数组 O(1) O(n) 顺序（6）在链表某个位置上进行插入和删除操作，只需要修改（___________）即可，而无须移动大量元素，操作的时间复杂度为（___________）。而在顺序表中进行插入和删除操作，往往要移动大量元素，平均移动元素的数目为（___________），平均时间复杂度为（___________）。因此，若对线性表进行频繁的插入和删除操作时，采用（___________）表相对合适。若插入和删除主要发生在表头和表尾，则采用（___________）表更为合适。答案：指针 O(1) 表长的一半 O(n) 链循环链（7）静态链表一般采用（___________）存储的链表结构。答案：数组（8）对于 32 位计算机环境，若单链表中的数据类型为整性，则其存储密度为（___________），而若为双链表，则存储密度为（___________）。若采用顺序表存储数据，则其存储密度为（___________）。答案：50% 33% 1 （9 ）向量是最常用的容器， STL 中向量使用（___________ ）实现，因此向量具有（___________）表的所有特点，可以快速随机存取任意元素。答案：数组顺序（10）操作系统在运行之初，有一块很大的连续内存块供用户程序申请，通常称之为内存池或（___________）。答案：堆（11）循环链表与单链表的区别仅仅在于其尾结点的链域值不是（___________），而是一个指向（___________）的指针。答案：NULL(或空指针) 头结点 2. 选择题 7

D. 动态 B. 双向 B. list 单链表 D. vector 单链表 B. 顺序表链表 D. 静态链表动态链表 B. 顺序存取随机存取 D. 索引存取散列存取（1）线性表的顺序存储结构是一种（）的存储结构，线性表的链式存储结构是一种（）的存储结构。 A. 随机存取索引存取 C. 随机存取顺序存取（2）在双向链表 p 所指结点之前插入 s 所指结点的操作是（）。 A. p->left=s; s->right=p; p->left->right =s; s->left=p->left; B. p->right=s; p->right->left=s; s->left=p; s->right=p->right; C. s->right=p; s->left=p->left; p->left=s; p->left->right =s; D. s->right=p; s->left=p->left; p->left->right =s; p->left=s; （3）若链表是利用 C++指针来存储结点的地址，结点空间的分配和收回都是由操作符 new 和 delete 动态执行的，则称该链表为（）链表 A. 单向 C. 静态（4）将线性表存储到计算机中可以采用多种不同的方法，按顺序存储方法存储的线性表称为（），按链式存储方法存储的线性表称为（）。 A. 数组单链表 C. 向量静态链表（5）（）是 STL 中线性表的链式存储形式，STL 标准库中一般采用（）实现。 A. vector 数组 C. list 双向循环链表（6）顺序表的类型定义可经编译转换为机器级。假定每个结点变量占用 k(k>=1)个字节，b 是顺序表的第一个存储结点的第一个单元的内存地址，那么，第 i 个结点 ai 的存储地址为（）。 A. b+ki （7）在循环链表中，若不使用头指针而改设为尾指针（rear），则头结点和尾结点的存储位置分别是（）。 A. real 和 rear->next->next C. rear->next->next 和 rear （8）有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是（）。 A. 将“指针型变量”简称为“指针” B. 将“头指针变量”简称为“头指针” C. 将“修改某指针型变量的值” 简称为“修改某指针” D. 将“p 中指针所指结点” 简称为“P 值” （9）以下说法错误的是（）。 A. 对循环链表来说，从表中任一结点出发都能通过向前或向后操作而扫描整个循环链表。 B. 对单链表来说，只有从头结点开始才能扫描表中全部结点。 C. 双链表的特点是找结点的前趋和后继都很容易。 D. 对双链表来说，结点*P 的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。（10）以下说法正确的是（）。 A. 顺序存储方式的优点是存储密度大、且插入、删除运算效率高。 B. 链表的每个结点中都恰好包含一个指针。 C. 线性表的顺序存储结构优于链式存储结构。 D. 顺序存储结构属于静态结构，链式结构属于动态结构。 B. rear->next 和 rear D. rear 和 rear->next C. b+k(i+1) B. b+k(i-1) D. b-1+ki 8

资料库

北邮数据结构课后答案.pdf

相关推荐

课程资源

热门标签

最新资料