实用数据结构基础参考答案
- 格式:doc
- 大小:925.00 KB
- 文档页数:83
单元练习1一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳)(√)(1)数据的逻辑结构与数据元素本身的内容和形式无关。
(√)(2)一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。
(ㄨ)(3)数据元素是数据的最小单位。
(ㄨ)(4)数据的逻辑结构和数据的存储结构是相同的。
(ㄨ)(5)程序和算法原则上没有区别,所以在讨论数据结构时可以通用。
(√)(6)从逻辑关系上讲,数据结构主要分为线性结构和非线性结构两类。
(√)(7)数据的存储结构是数据的逻辑结构的存储映像。
(√)(8)数据的物理结构是指数据在计算机内实际的存储形式。
(ㄨ)(9)数据的逻辑结构是依赖于计算机的。
(√)(10)算法是对解题方法和步骤的描述。
二.填空题(1)数据有逻辑结构和存储结构两种结构。
(2)数据逻辑结构除了集合以外,还包括:线性结构、树形结构和图形结构。
(3)数据结构按逻辑结构可分为两大类,它们是线性结构和非线性结构。
(4)树形结构和图形结构合称为非线性结构。
(5)在树形结构中,除了树根结点以外,其余每个结点只有 1 个前趋结点。
(6)在图形结构中,每个结点的前趋结点数和后续结点数可以任意多个。
(7)数据的存储结构又叫物理结构。
(8)数据的存储结构形式包括:顺序存储、链式存储、索引存储和散列存储。
(9)线性结构中的元素之间存在一对一的关系。
(10)树形结构结构中的元素之间存在一对多的关系,(11)图形结构的元素之间存在多对多的关系。
(12)数据结构主要研究数据的逻辑结构、存储结构和算法(或运算)三个方面的内容。
(13)数据结构被定义为(D,R),其中D是数据的有限集合,R是D上的关系的有限集合。
(14)算法是一个有穷指令的集合。
(15)算法效率的度量可以分为事先估算法和事后统计法。
(16)一个算法的时间复杂性是算法输入规模的函数。
(17)算法的空间复杂度是指该算法所耗费的存储空间,它是该算法求解问题规模n 的函数。
《数据结构基础教程》习题及解答数据结构基础教程习题及解答第一章:数据结构简介1.1 什么是数据结构?数据结构是指相互之间存在一种或多种特定关系的数据元素的集合,包括数据的逻辑结构、物理结构和数据元素之间的运算。
1.2 数据的逻辑结构有哪些?数据的逻辑结构包括线性结构、树形结构和图状结构。
1.3 数据的物理结构有哪些?数据的物理结构包括顺序存储结构和链式存储结构。
1.4 数据结构的主要目标是什么?数据结构的主要目标是提高数据的存储效率和运算效率。
第二章:线性表2.1 线性表的定义线性表是由n(≥0)个数据元素组成的有限序列。
线性表是一种常见的数据结构,常用的实现方式包括数组和链表。
2.2 线性表的顺序存储结构线性表的顺序存储结构是将线性表中的元素存储在连续的存储空间中,通过元素在内存中的物理位置来表示元素之间的关系。
2.3 线性表的链式存储结构线性表的链式存储结构是通过指针将线性表中的元素连接在一起,每个元素包括数据域和指针域。
2.4 线性表的基本操作包括初始化线性表、插入元素、删除元素、查找元素等。
第三章:栈与队列3.1 栈的定义与特性栈是一种具有后进先出特性的线性表,只允许在一端进行插入和删除操作,被称为栈顶。
3.2 栈的顺序存储结构和链式存储结构栈的顺序存储结构和链式存储结构与线性表的存储结构类似,不同之处在于栈只允许在一端进行插入和删除操作。
3.3 栈的应用栈在表达式求值、函数调用和递归等场景中有广泛应用。
3.4 队列的定义与特性队列是一种具有先进先出特性的线性表,允许在一端插入元素,在另一端删除元素。
3.5 队列的顺序存储结构和链式存储结构队列的顺序存储结构和链式存储结构与线性表的存储结构类似,不同之处在于队列允许在一端插入元素,在另一端删除元素。
3.6 队列的应用队列在模拟排队系统、操作系统进程调度等场景中有广泛应用。
第四章:树与二叉树4.1 树的基本概念树是由n(≥0)个节点组成的有限集合,其中有一个称为根节点,除了根节点之外的其余节点被分为m(m≥0)个互不相交的集合,每个集合本身又是一棵树。
第1 章绪论1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案:数据:是客观事物的符号表示,指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数,文本编辑所用到的字符串,多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素:是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。
在有些情况下,数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象,如一个学生记录,树中棋盘的一个格局(状态)、图中的一个顶点等。
数据项:是组成数据元素的、有独立含义的、不可分割的最小单位。
例如,学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象:是性质相同的数据元素的集合,是数据的一个子集。
例如:整数数据对象是集合N={0,±1,±2,… },字母字符数据对象是集合C={‘A’,‘B’,… ,‘Z’,‘a’,‘b’,…,‘z’},学生基本信息表也可是一个数据对象。
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说,数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。
逻辑结构:从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。
因此,数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构:数据对象在计算机中的存储表示,也称为物理结构。
抽象数据类型:由用户定义的,表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称。
具体包括三部分:数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
2.试举一个数据结构的例子,叙述其逻辑结构和存储结构两方面的含义和相互关系。
答案:例如有一张学生基本信息表,包括学生的学号、姓名、性别、籍贯、专业等。
每个学生基本信息记录对应一个数据元素,学生记录按顺序号排列,形成了学生基本信息记录的线性序列。
数据结构习题参考答案一、栈和队列1. 栈是一种具有后进先出(Last In First Out)特性的线性数据结构。
常用方法:- push(x): 将元素x压入栈顶;- pop(): 弹出栈顶元素;- top(): 返回栈顶元素;- isEmpty(): 判断栈是否为空;例题解答:(1)题目描述:使用栈实现队列的功能。
解答:使用两个栈,一个用于入队操作,一个用于出队操作。
入队操作:直接将元素压入入队栈中;出队操作:如果出队栈为空,则将入队栈的元素逐个弹出并压入出队栈,此时出队栈的栈顶元素即为要弹出的元素。
复杂度分析:入队操作的时间复杂度为O(1),出队操作的平均时间复杂度为O(1)。
(2)题目描述:判断括号序列是否合法,即括号是否完全匹配。
解答:使用栈来处理括号序列,遇到左括号则入栈,遇到右括号则与栈顶元素进行匹配,如果匹配成功则继续处理剩余字符,如果不匹配则判定为非法序列。
算法步骤:- 初始化一个空栈;- 从左到右遍历括号序列,对于每个字符执行以下操作:- 如果是左括号,则将其入栈;- 如果是右括号,则将其与栈顶元素进行匹配:- 如果栈为空,则判定为非法序列;- 如果栈顶元素与当前字符匹配,则将栈顶元素出栈,继续处理剩余字符;- 如果栈顶元素与当前字符不匹配,则判定为非法序列。
- 遍历结束后,如果栈为空,则括号序列合法;否则,括号序列非法。
复杂度分析:时间复杂度为O(n),其中n为括号序列的长度。
2. 队列是一种具有先进先出(First In First Out)特性的线性数据结构。
常用方法:- enqueue(x): 将元素x入队;- dequeue(): 出队并返回队首元素;- getFront(): 返回队首元素;- isEmpty(): 判断队列是否为空;例题解答:(1)题目描述:使用队列实现栈的功能。
解答:使用两个队列,一个用于入栈操作,一个用于出栈操作。
入栈操作:直接将元素入队入栈队列中;出栈操作:如果出栈队列为空,则将入栈队列的元素逐个出队并入队出栈队列,此时出栈队列的队首元素即为要出栈的元素。
数据结构(含答案)数据结构数据结构是计算机科学的基础知识之一,它在计算机领域中有着重要的地位。
本文将介绍数据结构的概念、常见的数据结构类型以及其应用。
同时,还会对一些常见的数据结构问题进行解答。
一、概念简介在计算机科学中,数据结构是指存储和组织数据的方式。
它关注数据元素之间的关系,以及如何对数据进行插入、删除和查询等操作。
数据结构可以分为线性结构和非线性结构两大类。
1.1 线性结构线性结构是最简单的一种数据结构,它的特点是数据元素之间存在一对一的关系。
常见的线性结构包括数组、链表、栈和队列。
- 数组是一种连续存储数据元素的结构,可以通过下标快速访问元素。
但是数组的大小固定,插入和删除操作比较耗时。
- 链表是一种通过指针连接数据元素的结构,可以动态地进行插入和删除操作。
但是链表的随机访问效率较低。
- 栈是一种先进后出(LIFO)的数据结构,只能在栈顶进行插入和删除操作。
常见的应用场景包括函数调用、表达式求值等。
- 队列是一种先进先出(FIFO)的数据结构,插入操作在队尾进行,删除操作在队头进行。
常见的应用场景包括任务调度、消息传递等。
1.2 非线性结构非线性结构中,数据元素之间的关系不是一对一的,包括树和图等结构。
- 树是一种层次结构,由节点和边组成。
树的常见应用包括文件系统、数据库索引等。
- 图是由节点和边组成的网络结构,节点之间的关系可以是任意的。
图的应用非常广泛,包括社交网络、路由算法等。
二、数据结构问题解答2.1 如何判断一个链表中是否存在环?使用快慢指针可以判断一个链表中是否存在环。
假设有两个指针,一个每次移动一步,另一个每次移动两步。
如果链表中存在环,那么快指针迟早会追上慢指针。
如果快指针到达链表尾部时都没有追上慢指针,那么链表中不存在环。
2.2 如何判断一个二叉树是否是平衡二叉树?平衡二叉树是一种左子树和右子树高度差不超过1的二叉树。
判断一个二叉树是否是平衡二叉树可以使用递归的方法。
数据结构题库及答案详解一、选择题1. 在数据结构中,线性结构的特点是什么?A. 结构中存在唯一的开始结点和终端结点B. 结构中所有结点的前驱和后继都存在C. 结构中所有结点都只有一个直接前驱和一个直接后继D. 结构中存在多个开始结点和终端结点答案:C2. 栈是一种特殊的线性表,其特点是:A. 先进先出B. 先进后出C. 可以同时在两端进行插入和删除操作D. 只能在一端进行插入和删除操作答案:D3. 在二叉树的遍历算法中,先序遍历的顺序是:A. 先访问根结点,然后遍历左子树,最后遍历右子树B. 先遍历左子树,然后访问根结点,最后遍历右子树C. 先遍历右子树,然后访问根结点,最后遍历左子树D. 先遍历左右子树,最后访问根结点答案:A二、填空题4. 在图的遍历中,______算法可以避免重复访问同一顶点。
5. 哈希表的冲突可以通过______方法来解决。
答案:4. 深度优先搜索(DFS)5. 链地址法或开放地址法三、简答题6. 简述排序算法中的快速排序算法的基本原理。
答案:快速排序算法是一种分治算法,它通过选择一个元素作为“基准”,然后将数组分为两个子数组,一个包含小于基准的元素,另一个包含大于基准的元素。
然后对这两个子数组递归地应用快速排序算法。
7. 解释什么是递归,并给出一个递归函数的例子。
答案:递归是一种在函数中调用自身的编程技术。
递归函数必须有一个明确的终止条件,以避免无限递归。
例如,计算阶乘的递归函数如下:```int factorial(int n) {if (n == 0) return 1; // 终止条件return n * factorial(n - 1); // 递归调用}```四、编程题8. 编写一个函数,实现单链表的反转。
答案:```c// 假设ListNode是链表节点的定义ListNode* reverseList(ListNode* head) {ListNode* prev = NULL;ListNode* curr = head;ListNode* next = NULL;while (curr != NULL) {next = curr->next; // 保存下一个节点curr->next = prev; // 反转指针prev = curr; // 移动prevcurr = next; // 移动curr}return prev; // 新的头节点}```9. 给定一个整数数组,请实现一个函数来找到数组中的最长连续子序列的长度。
实用数据结构基础第四版答案一、判断题〔第一章绪论〕1、数据元素是数据的最小单元。
答案:错误2、一个数据结构是由一个逻辑结构和这个逻辑结构上的根本运算集构成的整体。
答案:错误3、数据的存储结构是数据元素之间的逻辑关系和逻辑结构在计算机存储器内的映像。
答案:正确4、数据的逻辑结构是描述元素之间的逻辑关系,它是依赖于计算机的。
答案:错误5、用语句频度来表示算法的时间复杂度的最大好处是可以独立于计算机的软硬件,分析算法的时间答案:正确〔第二章6。
取顺序存储线性表的第i个元素的时间同i的大小有关。
答案:错误7。
线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。
答案:正确8。
线性链表的每一个节点都恰好包含一个指针域。
答案:错误9。
顺序存储方式的优点的存储密度大,插入和删除效率不如练市存储方式好。
答案:正确10。
插入和删除操作是数据结构中最根本的两种操作,所以这两种操作在数组中也经常使用。
答案:错误〔第三章栈〕11、栈是一种对进栈和出栈作了限制的线性表。
答案:错误12、在C〔或C++〕语言中设顺序栈的长度为MALEN,那么top=MALEN 表示栈满。
13、链栈与顺序栈相比,其特点之一是通常不会出现满栈的情况。
答案:正确14、空栈就是所有元素都为0上的栈。
答案:错误15、将十进制数转换为二进制数是栈的典型应用之一、答案:正确〔第四章队列〕16。
队列式限制在两端进行操作的线性表。
答案:正确17。
判断顺序队列为空的标准是头指针和尾指针都指向同一结点。
答案:错误18。
在循环链列队中无溢出现像。
答案:错误19。
在循环队列中,假设尾指针rear大于头指针front,那么元素个数为rear-front。
答案:正确20。
顺序队列和循环队列关于队满和队空的判断条件是一样的。
〔第五章串〕21、串是n个字母的有限序列。
答案:错误22、串的堆分配存储是一种动态存储结构。
答案:正确23、串的长度是指串中不同字符的个数。
第一章概论自测题答案一、填空题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。
2. 数据结构被形式地定义为(D, R),其中D是数据元素的有限集合,R是D上的关系有限集合。
3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。
4. 数据结构按逻辑结构可分为两大类,它们分别是线性结构和非线性结构。
5. 线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。
6.在线性结构中,第一个结点没有前驱结点,其余每个结点有且只有 1个前驱结点;最后一个结点没有后续结点,其余每个结点有且只有1个后续结点。
7. 在树形结构中,树根结点没有前驱结点,其余每个结点有且只有1个前驱结点;叶子结点没有后续结点,其余每个结点的后续结点数可以任意多个。
8. 在图形结构中,每个结点的前驱结点数和后续结点数可以任意多个。
9.数据的存储结构可用四种基本的存储方法表示,它们分别是顺序、链式、索引和散列。
10. 数据的运算最常用的有5种,它们分别是插入、删除、修改、查找、排序。
11. 一个算法的效率可分为时间效率和空间效率。
二、单项选择题(B)1. 非线性结构是数据元素之间存在一种:A)一对多关系 B)多对多关系C)多对一关系 D)一对一关系( C )2. 数据结构中,与所使用的计算机无关的是数据的结构;A) 存储 B) 物理C) 逻辑 D) 物理和存储(C)3. 算法分析的目的是:A) 找出数据结构的合理性B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性(A)4. 算法分析的两个主要方面是:A) 空间复杂性和时间复杂性B) 正确性和简明性C) 可读性和文档性D) 数据复杂性和程序复杂性(C )5. 计算机算法指的是:A) 计算方法B) 排序方法C) 解决问题的有限运算序列D) 调度方法(B)6. 计算机算法必须具备输入、输出和等5个特性。
数据结构习题及参考答案部门: xxx时间: xxx整理范文,仅供参考,可下载自行编辑数据结构习题及参考答案一、判断下列叙述的对错。
<1)线性表的逻辑顺序与物理顺序总是一致的。
<2)线性表的顺序存储表示优于链式存储表示。
<3)线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。
<4)二维数组是其数组元素为线性表的线性表。
<5)每种数据结构都应具备三种基本运算:插入、删除和搜索。
二、设单链表中结点的结构为typedef struct node { file://链表结点定义ElemType data; file://数据struct node * Link; file://结点后继指针} ListNode;<1)已知指针p所指结点不是尾结点,若在*p之后插入结点* s,则应执行下列哪一个操作?A. s->link = p; p->link = s;B. s->link = p->link; p->link = s;C. s->link = p->link; p = s;D. p->link = s; s->link = p;<2)非空的循环单链表first的尾结点<由p所指向)满足:A. p->link == NULL;B. p == NULL;C. p->link == first;D. p == first;三、设有一个顺序栈S,元素s1, s2, s3, s4, s5, s6依次进栈,如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1,则顺序栈的容量至少应为多少?b5E2RGbCAP四、一棵具有n个结点的理想平衡二叉树<即除离根最远的最底层外其他各层都是满的,最底层有若干结点)有多少层?若设根结点在第0层,则树的高度h如何用n来表示<注意n可能为0)?p1 EanqFDPw五、从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句,将其编号填入相应的括号内。
单元练习1一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳ )(√)(1)数据的逻辑结构与数据元素本身的内容与形式无关。
(√)(2)一个数据结构就是由一个逻辑结构与这个逻辑结构上的一个基本运算集构成的整体。
(ㄨ)(3)数据元素就是数据的最小单位。
(ㄨ)(4)数据的逻辑结构与数据的存储结构就是相同的。
(ㄨ)(5)程序与算法原则上没有区别,所以在讨论数据结构时可以通用。
(√)(6)从逻辑关系上讲,数据结构主要分为线性结构与非线性结构两类。
(√)(7)数据的存储结构就是数据的逻辑结构的存储映像。
(√)(8)数据的物理结构就是指数据在计算机内实际的存储形式。
(ㄨ)(9)数据的逻辑结构就是依赖于计算机的。
(√)(10)算法就是对解题方法与步骤的描述。
二.填空题(1)数据有逻辑结构与存储结构两种结构。
(2)数据逻辑结构除了集合以外,还包括:线性结构、树形结构与图形结构。
(3)数据结构按逻辑结构可分为两大类,它们就是线性结构与非线性结构。
(4)树形结构与图形结构合称为非线性结构。
(5)在树形结构中,除了树根结点以外,其余每个结点只有 1 个前趋结点。
(6)在图形结构中,每个结点的前趋结点数与后续结点数可以任意多个。
(7)数据的存储结构又叫物理结构。
(8)数据的存储结构形式包括:顺序存储、链式存储、索引存储与散列存储。
(9)线性结构中的元素之间存在一对一的关系。
(10)树形结构结构中的元素之间存在一对多的关系,(11)图形结构的元素之间存在多对多的关系。
(12)数据结构主要研究数据的逻辑结构、存储结构与算法(或运算) 三个方面的内容。
(13)数据结构被定义为(D,R),其中D就是数据的有限集合,R就是D上的关系的有限集合。
(14)算法就是一个有穷指令的集合。
(15)算法效率的度量可以分为事先估算法与事后统计法。
(16)一个算法的时间复杂性就是算法输入规模的函数。
(17)算法的空间复杂度就是指该算法所耗费的存储空间 ,它就是该算法求解问题规模n的函数。
(18)若一个算法中的语句频度之与为T(n)=6n+3nlog2n,则算法的时间复杂度为O(nlog2n) 。
(19)若一个算法中的语句频度之与为T(n)=3n+nlog2n+n2,则算法的时间复杂度为O(n2) 。
(20) 数据结构就是一门研究非数值计算的程序设计问题中计算机的操作对象 ,以及它们之间的关系与运算的学科。
三.选择题(1)数据结构通常就是研究数据的( A )及它们之间的相互联系。
A、存储结构与逻辑结构B、存储与抽象C、联系与抽象D、联系与逻辑(2)在逻辑上可以把数据结构分成:( C )。
A、动态结构与静态结构B、紧凑结构与非紧凑结构C、线性结构与非线性结构D、内部结构与外部结构(3)数据在计算机存储器内表示时,物理地址与逻辑地址相同并且就是连续的,称之为( C )。
A、存储结构B、逻辑结构C、顺序存储结构D、链式存储结构(4)非线性结构中的每个结点( D )。
A.无直接前趋结点B.无直接后继结点C.只有一个直接前趋结点与一个直接后继结点D.可能有多个直接前趋结点与多个直接后继结点(5)链式存储的存储结构所占存储空间( A )。
A. 分两部分,一部分存放结点的值,另一部分存放表示结点间关系的指针B. 只有一部分,存放结点的值C. 只有一部分,存储表示结点间关系的指针D. 分两部分,一部分存放结点的值,另一部分存放结点所占单元素(6)算法的计算量大小称为算法的( C )。
A、现实性B、难度C、时间复杂性D、效率(7)数据的基本单位就是( B )。
A、数据结构B、数据元素C、数据项D、文件(8)每个结点只含有一个数据元素,所有存储结点相继存放在一个连续的存储区里,这种存储结构称为( A )结构。
A、顺序存储B、链式存储C、索引存储D、散列存储(9)每一个存储结点不仅含有一个数据元素,还包含一组指针,该存储方式就是( B )存储方式。
A、顺序B、链式C、索引D、散列(10)以下任何两个结点之间都没有逻辑关系的就是( D )。
A、图形结构B、线性结构C、树形结构D、集合(11)在数据结构中,与所使用的计算机无关的就是( C )。
A、物理结构B、存储结构C、逻辑结构D、逻辑与存储结构(12)下列四种基本逻辑结构中,数据元素之间关系最弱的就是( A )。
A、集合B、线性结构C、树形结构D、图形结构(13)与数据元素本身的形式、内容、相对位置、个数无关的就是数据的( A )。
A、逻辑结构B、存储结构C、逻辑实现D、存储实现(14)每一个存储结点只含有一个数据元素,存储结点存放在连续的存储空间,另外有一组指明结点存储位置的表,该存储方式就是( C )存储方式。
A、顺序B、链式C、索引D、散列(15)算法能正确的实现预定功能的特性称为算法的( A )。
A、正确性B、易读性C、健壮性D、高效性(16)算法在发生非法操作时可以作出处理的特性称为算法的( C )。
A、正确性B、易读性C、健壮性D、高效性(17)下列时间复杂度中最坏的就是( D )。
A、O(1)B、O( n)C、O(log2n)D、O(n2)(18)下列算法的时间复杂度就是( D )。
for (i=0;i<n;i++)for (j=0;i<n;j++)c[i][j]=i+j;A、O(1)B、O( n)C、O(log2n)D、O(n2)(19)算法分析的两个主要方面就是( A )。
A、空间复杂性与时间复杂性B、正确性与简明性C、可读性与文档性D、数据复杂性与程序复杂性(20)计算机算法必须具备输入、输出与( C )。
A、计算方法B、排序方法C、解决问题的有限运算步骤D、程序设计方法四.分析下面各程序段的时间复杂度(1)for (i=0;i<n;i++)for (j=0;j<m;j++)A[i][j]解: O(n*m)(2) s=0;for (i=0;i<n;i++)for (j=0;j<n;j++)s+=B[i][j];sum=s;解: O(n2)(3) T=A;A=B;B=T;解:O(1)(4) s1(int n){ int p=1,s=0;for (i=1;i<=n;i++){ p*=i;s+=p; }return(s);}O(n)(5) s2(int n)x=0;y=0;for (k=1;k<=n;k++)x++;for (i=1;i<=n;i++)for (j=1;j<=n;j++)y++;解:O(n2)五. 根据二元组关系,画出对应逻辑图形的草图,指出它们属于何种数据结构。
(1)A=(D,R),其中:D={a,b,c,d,e},R={ }解: a属于集合(2)B=(D,R),其中:D={a,b,c,d,e,f},R={r}R={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>} (尖括号表示结点之间关系就是有向的) 解:属于线性结构。
(3)F=(D,R),其中:D={50,25,64,57,82,36,75,55},R={r}R={<50,25>,<50,64>,<25,36>,<64,57>,<64,82>,<57,55>,<57,75>}解:属于树结构(4)C=(D,R),其中:D={1,2,3,4,5,6},R={r}R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}(园括号表示结点之间关系就是有向的) 解:属于图结构(5)E=(D,R),其中:D={a,b,c,d,e,f,g,h},R={r}R={<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>} 解:属于树结构。
单元练习2一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳)(×)(1)线性表的链式存储结构优于顺序存储。
(×)(2)链表的每个结点都恰好包含一个指针域。
(√)(3)在线性表的链式存储结构中,逻辑上相邻的两个元素在物理位置上并不一定紧邻。
(×)(4)顺序存储方式的优点就是存储密度大,插入、删除效率高。
(×)(5)线性链表的删除算法简单,因为当删除链中某个结点后,计算机会自动地将后续的各个单元向前移动。
(×)(6)顺序表的每个结点只能就是一个简单类型,而链表的每个结点可以就是一个复杂类型。
(√)(7)线性表链式存储的特点就是可以用一组任意的存储单元存储表中的数据元素。
(√)(8)线性表采用顺序存储,必须占用一片连续的存储单元。
(×)(9)顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。
(ㄨ)(10)插入与删除操作就是数据结构中最基本的两种操作,所以这两种操作在数组中也经常使用。
二.填空题(1)顺序表中逻辑上相邻的元素在物理位置上必须相连。
(2)线性表中结点的集合就是有限的,结点间的关系就是一对一关系。
(3)顺序表相对于链表的优点就是: 节省存储与随机存取。
(4)链表相对于顺序表的优点就是: 插入、删除方便。
(5) 采用顺序存储结构的线性表叫顺序表。
(6) 顺序表中访问任意一个结点的时间复杂度均为O(1)。
(7) 链表相对于顺序表的优点就是插入、删除方便;缺点就是存储密度小。
(8) 在双链表中要删除已知结点*P,其时间复杂度为O(1)。
(9) 在单链表中要在已知结点*P之前插入一个新结点,需找到*P的直接前趋结点的地址,其查找的时间复杂度为 O(n) 。
(10)单链表中需知道头指针才能遍历整个链表。
(11)性表中第一个结点没有直接前趋,称为开始结点。
(12)在一个长度为n的顺序表中删除第i个元素,要移动n-i 个元素。
(13)在一个长度为n的顺序表中,如果要在第i个元素前插入一个元素,要后移n- i +1 个元素。
(14)在无头结点的单链表中,第一个结点的地址存放在头指针中,而其它结点的存储地址存放在前趋结点的指针域中。
(15)当线性表的元素总数基本稳定,且很少进行插入与删除操作,但要求以最快速度存取线性表中的元素时,应采用顺序存储结构。
(16)在线性表的链式存储中,元素之间的逻辑关系就是通过指针决定的。
(17)在双向链表中,每个结点都有两个指针域,它们一个指向其前趋结点,另一个指向其后继结点。
(18)对一个需要经常进行插入与删除操作的线性表,采用链式存储结构为宜。
(19)双链表中,设p就是指向其中待删除的结点,则需要执行的操作为: p->prior->next=p->next 。