数据结构课后答案_北邮.pdfVIP

习题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 ）下面带有@标记的语句的频度(n10)是 （ ）。 for(int i=0;in-1;i++) for(int j=i+1;jn;j++)