数据结构答案

数据结构答案Tag内容描述：<p>1、单元练习1一判断题（下列各题，正确的请在前面的括号内打；错误的打 ）（）（1）数据的逻辑结构与数据元素本身的内容和形式无关。（）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（）（3）数据元素是数据的最小单位。（）（4）数据的逻辑结构和数据的存储结构是相同的。（）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（）（7）数据的存储结构是数据的逻辑结构的存储映像。（）（8）数据的物理结构是指数据。</p><p>2、第1章 绪论习题1简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。3简述逻辑结构的四种基本关系并画出它们的关系图。4存储结构由哪两种基本的存储方法实现？5选择题（1）在数据结构中，从逻辑上可以把数据结构分成（ ）。A动态结构和静态结构 B紧凑结构和非紧凑结构C线性结构和非线性结构 D内部结构和外部结构（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。A存储结构 B存储实现C逻辑结。</p><p>3、数据结构试题一、单选题（每题 2 分，共20分）1. 1. 对一个算法的评价，不包括如下（ B ）方面的内容。A健壮性和可读性 B并行性 C正确性 D时空复杂度2. 2. 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( A )。A. p-next=HL-next; HL-next=p; B. p-next=HL; HL=p;C. p-next=HL; p=HL; D. HL=p; p-next=HL;3. 3. 对线性表，在下列哪种情况下应当采用链表表示？( B )A.经常需要随机地存取元素 B.经常需要进行插入和删除操作C.表中元素。</p><p>4、数据结构单元测试1一、选择题（每题2分，共40分）1数据的最小单位是（A）。(A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量2.栈和队列的共同特点是(A )。(A)只允许在端点处插入和删除元素(B)都是先进后出 (C)都是先进先出(D)没有共同点3.用链接方式存储的队列，在进行插入运算时(D )。(A)仅修改头指针 (B)头、尾指针都要修改。</p><p>5、第1章 绪论1.1 知识点分析1数据数据是信息的载体，是对客观事物的符号表示。数据是计算机化的现实世界的事物的抽象描述。凡是能被计算机识别、存取和加工处理的符号、字符、图形、图象、声音、视频信号等一切信息都可以称为数据。2数据元素数据元素是对现实世界中某独立个体的数据描述，是数据的基本单位。数据元素也称为结点，通常由若干数据元素组成。3数据项数据项是数据不可分割的、具有独立意义的最小数据单位，是对数据元素属性的描述。数据、数据元素、数据项反映了数据组织的三个层次，即数据可以由若干个数据元素组成，数据元素。</p><p>6、第10章 排序10.1 知识点分析1排序基本概念：（1）排序将数据元素的任意序列，重新排列成一个按关键字有序（递增或递减）的序列的过程称为排序。（2）排序方法的稳定和不稳定若对任意的数据元素序列，使用某个排序方法，对它按关键字进行排序，若对原先具有相同键值元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；反之，则称为不稳定的。（3）内排序整个排序过程都在内存进行的排序称为内排序，本书仅讨论内排序。（4）外排序待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排。</p><p>7、10-2 设有10000个记录对象, 通过分块划分为若干子表并建立索引, 那么为了提高搜索效率, 每一个子表的大小应设计为多大? 【解答】每个子表的大小 s = n = 10000 = 100 个记录对象。10-4 如果一个磁盘页块大小为1024 (=1K) 字节，存储的每个记录对象需要占用8字节，其中关键码占4字节，其它数据占4字节。所有记录均已按关键码有序地存储在磁盘文件中，每个页块的第1个记录用于存放线性索引。另外在内存中开辟了256K字节的空间可用于存放线性索引。试问：(1) 若将线性索引常驻内存，文件中最多可以存放多少个记录？(2) 如果使用二级索引，第。</p><p>8、3-2 试编写一个算法，在带表头结点的单链表中寻找第i个结点。若找到，则函数返回第i个结点的地址；若找不到，则函数返回0。【解答】template ListNode * List : GetANode ( int i ) /取得单链表中第i个结点地址, i从0开始计数, i * p = first; int k = 0;while ( p != NULL & k < i ) p = plink; k+; return p;3-3 设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许。</p><p>9、8-1 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n个顶点的无向完全图中，边的条数为n(n-1)/2。8-2 右边的有向图是强连通的吗？请列出所有的简单路径。8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。8-4 用邻接矩阵表示图时，若图中有1000个顶点，1000条边，则形成的邻接矩阵有多少矩阵元素？有多少非零元素？是否稀疏矩阵？【解答】一个图中有1000个顶点，其邻接矩阵中的矩阵元素有10002 = 1000000个。它有1000个非零元素（对于有向图）或2000个非零元素（对于无向图），因此是稀疏矩阵。8-5 用邻接矩阵。</p><p>10、第7章 集合与搜索7-2 试编写一个算法，打印一个有穷集合中的所有成员。要求使用集合抽象数据类型中的基本操作。如果集合中包含有子集合，各个子集合之间没有重复的元素，采用什么结构比较合适。【解答】集合抽象数据类型的部分内容Template class Set /对象: 零个或多个成员的聚集。其中所有成员的类型是一致的, 但没有一个成员是相同的。int Contains ( const Type x );/判元素x是否集合this的成员int SubSet ( Set & right );/判集合this是否集合right的子集int operator = ( Set & right );/判集合this与集合right是否相等int Elemtype。</p><p>11、5-1 已知An为整数数组，试写出实现下列运算的递归算法：(1) 求数组A中的最大整数。(2) 求n个整数的和。(3) 求n个整数的平均值。【解答】#include class RecurveArray /数组类声明private:int *Elements;/数组指针int ArraySize;/数组尺寸int CurrentSize;/当前已有数组元素个数public :RecurveArray ( int MaxSize =10 ) :ArraySize ( MaxSize ), Elements ( new intMaxSize ) RecurveArray ( ) delete Elements; void InputArray();/输入数组的内容int MaxKey ( int n );/求最大值int Sum ( int n );/求数组元素之和fl。</p><p>12、6-1 写出用广义表表示法表示的树的类声明，并给出如下成员函数的实现：(1) operator ( )接收用广义表表示的树作为输入，建立广义表的存储表示；(2) 复制构造函数用另一棵表示为广义表的树初始化一棵树；(3) operator = ( )测试用广义表表示的两棵树是否相等；(4) operator #define maxSubTreeNum 20;/最大子树(子表)个数class GenTree;/GenTree类的前视声明class GenTreeNode /广义树结点类的声明friend class GenTree;private:int utype;/结点标志：=0, 数据; =1, 子女GenTreeNode * nextSibling。</p><p>13、第6章 多维数组和广义表 6 1 知识点分析 1 多维数组概念 多维数组是向量的推广 对于二维数组A mn既可以看成m行向量组成的向量 也可以看成n行向量组成的向量 多维数组在计算机中有两种存储形式 按行优先顺序存储和按。</p><p>14、第10章 排序 10 1 知识点分析 1 排序基本概念 1 排序 将数据元素的任意序列 重新排列成一个按关键字有序 递增或递减 的序列的过程称为排序 2 排序方法的稳定和不稳定 若对任意的数据元素序列 使用某个排序方法 对它。</p><p>15、第4章 队列 4.1 知识点分析 1 队列的基本概念 （1）队列是一种特殊的、只能在表的两端进行插入或删除操作的线性表。允许插入元素的一端称为队尾，允许删除元素的一端称为队首。 （2）队列的逻辑结构和线性表相同，其最大特点是“先进先出”。 （3）队列的存储结构有顺序队列和链队列之分，要求掌握队列的C语言描述方法。 （4）重点掌握在顺序队列和链队列上实现：进队、出队、读队头元素、显示队列元素、判队空。</p><p>16、数据结构试卷（一）王彬 一、单选题（每题 2 分，共20分） 1. 栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2. 用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3. 以下数。</p>