第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。
I Single Choice(10 points) 1. ( a )For the following program fragment the running time(Big-Oh) is . i = 0; s = 0; while(s <( 5*n*n + 2)) { i++; s = s + i; } a. O(n) b. O(n2) c. O(n1/2) d. O(n3) 2. ( c )Which is non-linear data structure_____. a. queue c. tree d. sequence list 3.( b )The worst-time for removing an element from a sequence list (Big-Oh) is . a. O(1) b. O(n) c. O(n2) d. O(n3) 4.( d )In a circular queue we can distinguish(区分) empty queues from full queues by .
a. using a gap in the array b. incrementing queue positions by 2 instead of 1 a count of the number of elements d. a and c 5.( b )A recursive function can cause an infinite sequence of function calls if . a.the problem size is halved at each step b.the termination condition is missing c.no useful incremental computation is done in each step d.the problem size is positive 6．( c )The full binary tree with height 4 has nodes. a. 15 b. 16 7. ( b )Searching in an unsorted list can be made faster by using . a.binary search
第 1 章 绪 论 (2005-07-14) - 第 1 章 绪 论 课后习题讲解 1. 填空 ⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模 ⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为 n*log25n，则表示成数量级的形式为（ ）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。
2. 选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 ⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶ 算法指的是（ ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。 ⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。 ⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性
第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={
一．是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示（D，S，P）。其中：D是数据对象，S 是D上的关系，P是对 D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表（头指针为L）中指针p所指结点是最后一个元素结点 的条件是：p->next==L。(t) 4 线性表的链式存储结构具有可直接存取?表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是： P->next= S ; S-> next = P->next;。(顺序弄反了)(f) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。栈和队列是操作上受限制的线性表(f) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。对列不是(f) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的 特殊情形。(f) 15 二叉树是一棵结点的度最大为二的树二叉树和树相互独立。(f) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) 18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历后根遍历相当于中序遍历。(f) 19. 通常，二叉树的第i层上有2i-1个结点。应该为1~2i-1个(f) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。 (t) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。只能表示无向图，有向图用十字链表(f) 24 可从任意有向图中得到关于所有顶点的拓扑次序带环图没有。(f) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t) 26 关键路径是AOE网中源点到汇点的最短路径。(f) 27 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。(f) 28 一个无向图的连通分量是其极大的连通子图。(t) 29 十字链表可以表示无向图，也可用以表示有向图。(f) 30 邻接表可以表示有向图，也可以表示无向图。（t ） 31. 二叉排序树的平均查找长度为O(logｎ)。(t) 32. 二叉排序树的最大查找长度与（LOG2N）同阶。(f) 33 选用好的HASH函数可避免冲突。哈希函数有几种处理冲突的方法(f) 34 折半查找不适用于有序链表的查找。(t) 35. 对于目前所知的排序方法，快速排序具有最好的平均性能。(t) 36 对于任何待排序序列来说，快速排序均快于冒泡排序。(f)
数据结构（C语言篇）―习题与解析（修订版） 清华大学出版社 一、绪论 选择题 1.数据结构是一门研究非数值计算的程序设计问题计算机的以及它们之间的和运算等的学科。 1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为 (K, R)，其中K是的有限集，R是K 上的有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种 A 的存储结构，线性表的链式存储结构是一种 B 的存储结构。 A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是 C ，算法分析的两个主要方面是AB 。 1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系
C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.正确性和简单性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是 C ，它必须具备输入、输出和 B 等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法 B 。 A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址D 。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D 连续不连续都可以 9.以下的叙述中，正确的是 B 。 A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表 C.栈的操作方式是先进后出 D.队列的操作方式是
第1章绪论 一、 判断题 1. 数据的逻辑结构与数据元素本身的内容和形式无关。 （V ） 2. 一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。 （V ） 3. 数据元素是数据的最小单位。 （X ） 4. 数据的逻辑结构和数据的存储结构是相同的。 （X ） 5. 程序和算法原则上没有区别， 所以在讨论数据结构时可以通用。 （X ） 6. 从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 （V ） 7. 数据的存储结构是数据的逻辑结构的存储映象。 （V ） 8. 数据的物理结构是指数据在计算机内实际的存储形式。 （V ） 9. 数据的逻辑结构是依赖于计算机的。 （X ） 10. 算法是对解题方法和步骤的描述。 （V ） 二、填空题 1. 数据有逻辑结构和 存储结构 两种结构。 ----------------- 2. 数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构 。 _________ 3. 数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构 。 --------- 4. 树形结构 和图形结构 合称为非线性结构。 --------------------------------- 5. 在树形结构中，除了树根结点以外，其余每个结点只有 1个前驱结点。_ 6. 在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个 。 ___________ 7. 数据的存储结构又叫物理结构 。 ________________ 8. 数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储 ------- 9. 线性结构中的元素之间存在一对一 的关系。 ------------- 10. 树形结构中的元素之间存在一对多 的关系。 _____________ 11. 图形结构的元素之间存在多对多 的关系。 -------------- 12. 数据结构主要研究数据的逻辑结构、存储结构和算法（或运算） 3个方面的内容。 13. 数据结构被定义为（D, R ）,其中D 是数据的有限集合，R 是 D 上的关系 14. 算法是一个有穷指令 ------ 的集合。 15. 算法效率的度量可以分为事先估算法和事后统计法 16. 一个算法的时间复杂度是算法 输入规模 的函数。 ---------------- 句频度之和为+n --------------------- 数据结构是一门研究非数值计算的程序问题中计算机的操作对象, 以及它们之间的关系和运算的学 20. ------------------ 科。三、选择题1 1. 数据结构通常是研究数据的（ A ）及它们之间的相互关系。 A. 存储结构和逻辑结构 B ?存储和抽象 C ?联系和抽象 D ?联系 与逻辑 有限集合。 17.算法的空间复杂度是指该算法所耗费的存储空间 ，它是该算法求解问题规模的 n 的函数 18.若一个算法中的语句频度之和为 T( n)=6 n+3n log n. 则算法的时间复杂度为 O ( n log n ) 222 0 则算法的时间复杂度为（ n ）。，T （n ）=3n+nlog 19.若一个算法的语
1-1什么是数据? 它与信息是什么关系? 【解答】 什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。 什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。 1-2什么是数据结构? 有关数据结构的讨论涉及哪三个方面? 【解答】 数据结构是指数据以及相互之间的关系。记为：数据结构= { D, R }。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。 有关数据结构的讨论一般涉及以下三方面的内容： ①数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构； ②数据成员极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构； ③施加于该数据结构上的操作。 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。 1-3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、 队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？ 【解答】 线性结构的特点是：在结构中所有数据成员都处于一个序列中，有且仅有一个开始成员和一个终端成员，并且所有数据成员都最多有一个直接前驱和一个直接后继。例如，一维数组、线性表等就是典型的线性结构 非线性结构的特点是：一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如，树、图或网络等都是典型的非线性结构。 1-4．什么是抽象数据类型？试用C++的类声明定义“复数”的抽象数据类型。要求 (1) 在复数内部用浮点数定义它的实部和虚部。 (2) 实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。 (3) 定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。
第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现？ 5．选择题 （1）在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．部结构和外部结构 （2）与数据元素本身的形式、容、相对位置、个数无关的是数据的（）。 A．存储结构 B．存储实现 C．逻辑结构 D．运算实现 （3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。 A．数据具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 （4）以下说确的是（）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 （5）以下与数据的存储结构无关的术语是（）。 A．顺序队列 B. 链表 C.有序表 D. 链栈（6）以下数据结构中，（）是非线性数据结构 A．树 B．字符串 C．队 D．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90; y=100; while(y>0) if(x>100) {x=x-10;y--;} else x++; （2）for (i=0; i 一、绪论 选择题 1.数据结构是一门研究非数值计算的程序设计问题计算机的以及它们之间的和运算等的学科。 1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是的有限集，R是K上的有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种的存储结构，线性表的链式存储结构是一种的存储结构。 A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是，算法分析的两个主要方面是。 1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.正确性和简单性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是，它必须具备输入、输出和等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。 A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。 A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表 C.栈的操作方式是先进先出 D.队列的操作方式是先进后出 10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。 A.正确 B.不正确 填空题 1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。 2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3.在树形结构中，树根结点没有结点，其余每个结点有且只有个前驱结点；叶子结点没有结点，其余每个结点的后续可以。 4.在图形结构中，每个结点的前驱结点数和后续结点数可以。 5.线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结 数据结构（C语言篇）―习题与解析（修订版）清华大学出版社 一、绪论 选择题 1.数据结构是一门研究非数值计算的程序设计问题计算机的以 及它们之间的和运算等的学科。 1A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是的有限集，R是K 上的有限集。 1A.算法 B.数据元素 C.数据操作 D.逻辑结构 2A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种A的存储结构，线性表的链式 存储结构是一种B的存储结构。 A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是C，算法分析的两个主要方面是AB。 1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.正确性和简单性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是C，它必须具备输入、输出和B等5个 特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法B。 A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址D。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是B。 A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表 第 1 章绪论 (1) 1.1 本章导学 (1) 1.2 习题解析 (2) 第 2 章线性表 (8) 2.1 本章导学 (8) 2.2 习题解析 (9) 第 3 章栈和队列 (17) 3.1 本章导学 (17) 3.2 习题解析 (18) 第 4 章字符串和多维数组 (24) 4.1 本章导学 (24) 4.2 习题解析 (25) 第 5 章树和二叉树 (30) 5.1 本章导学 (30) 5.2 习题解析 (31) 第 6 章图 (40) 6.1 本章导学 (40) 6.2 习题解析 (41) 第7 章查找技术 (53) 7.1 本章导学 (53) 7.2 习题解析 (54) 第8 章排序技术 (63) 8.1 本章导学 (63) 8.2 习题解析 (64) 第9 章索引技术 (74) 9.1 本章导学 (74) 9.2 习题解析 (74) 第 1 章绪论 1.1 本章导学 1. 知识结构图 本章的知识结构如图1-1所示，其中第二层的椭圆代表本章的学习主线。 图1-1 知识结构图 2. 学习要点 对本章的学习要从两条主线出发，一条主线是数据结构，包括数据结构的相关概念及含义，另一条主线是算法，包括算法的相关概念、描述方法以及时间复杂度的分析方法。 在学习数据结构时要抓住两个方面：逻辑结构和存储结构，并注意把握二者之间的关系。在学习算法时，要以算法的概念和特性为基本点，并在以后的学习中注意提高算法设计的能力。对于算法时间性能的分析，要将注意力集中在增长率上，即基本语句执行次数的数量级，在设计算法时，养成分析算法时间性能的习惯，进而有效地改进算法 1.2 习题解析 1. 填空 （1）（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。【解答】数据元素 （2）（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 （3）从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。【解答】集合，线性结构，树结构、图结构 （4）数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 （5）算法具有五个特性，分别是（）、（）、（）、（）、（）。【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 （6）算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 （7）在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 （8）设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为2n*log25n + 8n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 （1）顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 （2）假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承遗产。则表示该遗产继承关系的最合适的数据结构应该是（）。 A 树 B 图 C 线性表 D 集合 【解答】B 本资料由理硕教育整理，理硕教育是全国唯一专注于北理工考研辅导的学校，相对于其它机构理硕教育有得天独厚的优势。丰富的理工内部资料资源与人力资源确保每个学员都受益匪浅，确保理硕教育的学员初试通过率89%以上，复试通过率接近100%，理硕教育现开设初试专业课VIP一对一，初试专业课网络小班，假期集训营，复试VIP一对一辅导，复试网络小班，考前专业课网络小班，满足学员不同的需求。因为专一所以专业，理硕教育助您圆北理之梦。详情请查阅理硕教育官网 第 9 章索引技术 课后习题讲解 1. 填空题 ⑴在索引表中，每个索引项至少包含（）和（）等信息 【解答】关键码，关键码对应的记录在存储器中的位置 ⑵在线性索引中，（）称为稠密索引 【解答】若文件中的每个记录对应一个索引项 ⑶分块有序是指将文件划分为若干块，（）无序，（）有序。 【解答】块内，块间 ⑷在分块查找方法中，首先查找（），然后查找相应的（）。 【解答】索引表，块 ⑸在10阶B—树中根结点所包含的关键码个数最多为（），最少为（）。 【解答】9，1 【分析】m阶的B－树中每个结点至多有m棵子树，若根结点不是终端结点，则至少有两棵子树，每个结点中关键码的个数为子树的个数减1。 ⑹一棵5阶B—树中，除根结点外，每个结点的子树树目最少为（），最多为（）。【解答】3，5 【分析】m阶的B－树中每个结点至多有m棵子树，除根结点之外的所有非终端结点至少有?m/2? 棵子树。 ⑺对于包含n个关键码的m阶B—树，其最小高度是（），最大高度是（）。 【解答】[logm(n+1)]， [logm/2(n+1)/2] ⑻在一棵B—树中删除关键码，若最终引起树根结点的合并，则新树比原树的高度（）。【解答】减少1层 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 图 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。 数据结构习题集（自编） 第一章绪论 一、选择题 1．数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（）和运算的学科。 A．结构B．关系 C．运算 D．算法 2．在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．逻辑结构和存储结构 3．线性表的逻辑顺序和存储顺序总是一致的，这种说法（）。 A．正确B．不正确 C．无法确定 D．以上答案都不对4．算法分析的目的是（）。 A．找出算法的合理性 B．研究算法的输人与输出关系 C．分析算法的有效性以求改进 D．分析算法的易懂性 5. 算法的时间复杂度取决于（） A．问题的规模B待处理数据的初态 C. A和B 6．一个算法应该是（）。 A．程序B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 7. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法与为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 8．以下与数据的存储结构无关的术语是（）。 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．在下面的程序段中，对x的赋值语句的频度为（） for（i=0;i (1)对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是______。 A）冒泡排序为n/2 B）冒泡排序为n C）快速排序为n D）快速排序为n(n-1)/2 【答案】D 【解析】在全国二级考试中涉及的排序算法（冒泡排序法、快速排序法、简单插入排序法、希尔排序法、简单选择排序、堆排序法），只有“堆”排序和“希尔”排序不是n(n-1)/2，其它都是n(n-1)/2。堆排序是O(nlog2n)，希尔排序是O(n1.5)。 (2)对于长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为_______。 A）log2n B） n/2 C） n D） n+1 【答案】C 【解析】最坏的情况是要找的元素在最后一个或不在序列中，所以要把n个元都比较一下。 (3)下列叙述中正确的是______。 A）对长度为n的有序链表进行查找，最坏的情况需要比较次数为n。 B）对长度为n的有序链序表进行对分查找，最坏的情况需要比较次数为（n/2）。 C）对长度为n的有序链序表进行对分查找，最坏的情况需要比较次数为（log2n）。 D）对长度为n的有序链序表进行对分查找，最坏的情况需要比较次数为（nlog2n）。 【答案】A 【解析】二分查找（对分查找）只能用于顺序存储的有序表，所以只有A是对的。 （4）对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为。 【答案】45 【解析】n(n-1)/2=10*9/2=45 (1)数据的存储结构是指_______。 A）存储在外存中的数据 B）数据所占的存储空间量 C）数据在计算机中的顺序存储方式 D）数据的逻辑结构在计算机中的表示 【答案】D 【解析】数据的存储结构是数据的逻辑结构在计算机中的表示，根据数据的逻辑关系和运算特点可以采取顺序存储或链式存储的方式，这些数据一般都是存储在内存中的。 (2)下列关于栈的描述中错误的是_______。 A）栈是先进后出的线性表 B）栈只能顺序存储 C）栈具有记忆作用 D）对栈的插入与删除操作中，不需要改变栈底指针【答案】B 【解析】栈是一种特殊的线性表，可以顺序存储，也可以用链式存储，所以B是错的；栈具有记忆作用，在过程的调用中就是利用这个功能，保存现场；对栈的操作都在栈顶上进行，不需要改变栈底的指针。 (3)下列对于线性链表的描述中正确的是_______。 A）存储空间不一定是连续，且各元素的存储顺序是任意的 B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C）存储空间必须连续，且前件元素一定存储在后件元素的前面 D）存储空间必须连续，且各元素的存储顺序是任意的 【答案】A 【解析】线性链表是线性表的链式存储结构，即数据在逻辑上是线性关系，在存储结构上是链式存储，存储空间不一定连续，且各元素的存储顺序是任意的，所以A是正确的。 （5）下列叙述中正确的是_______。李春葆数据结构习题与解析
数据结构李春葆习题与解析
数据结构c++版课后习题解析
北京理工大学数据结构考研例题解析9
数据结构习题和答案及解析
数据结构_第六章_图_练习题与答案详细解析(精华版)
数据结构习题(包含全部答案解析)
数据结构例题讲解
相关主题
文本预览