数据结构习题集包含全部答案
- 格式：doc
- 大小：1.12 MB
- 文档页数：52
下载文档原格式
合集下载
数据结构试题集(包含答案-完整版)
数据结构试题集(包含答案-完整版)数据结构试题集（包含答案-完整版）1. 单选题1) 数据结构是一种（）。
a) 存储结构b) 算法c) 数据模型d) 网络答案：c) 数据模型解析：数据结构是一种用于组织和存储数据的方式，描述了数据之间的关系以及对数据的操作。
2) 以下哪种数据结构可以通过索引直接访问元素？a) 链表b) 队列c) 栈d) 数组答案：d) 数组解析：数组是一种线性数据结构，可以通过索引直接访问指定位置的元素。
2. 多选题1) 哪些数据结构属于非线性结构？（）a) 队列b) 树c) 栈d) 图答案：b) 树d) 图解析：线性结构中的元素存在一对一的关系，非线性结构中的元素存在一对多或多对多的关系，树和图属于非线性结构。
2) 下列哪些操作可以在栈上进行？（）a) 入栈b) 出栈c) 查找d) 删除答案：a) 入栈b) 出栈解析：栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。
3. 简答题1) 请简要介绍线性表和非线性表。
答案：线性表是数据元素的一个有限序列，元素之间存在一对一的关系。
非线性表是指元素之间存在一对多或多对多的关系，如树和图。
2) 请解释什么是时间复杂度和空间复杂度。
答案：时间复杂度是衡量算法执行效率的度量，表示算法的运行时间随输入规模增长的速度。
空间复杂度是指算法执行过程中所需的存储空间随输入规模增长的速度。
4. 编程题题目：实现一个栈，包含push、pop和getMin三个操作，要求时间复杂度为O(1)。
答案：class MinStack:def __init__(self):self.stack = []self.min_stack = []def push(self, x):self.stack.append(x)if not self.min_stack or x <= self.min_stack[-1]:self.min_stack.append(x)def pop(self):if self.stack.pop() == self.min_stack[-1]:self.min_stack.pop()def getMin(self):return self.min_stack[-1]解析：在栈的基础上，使用一个辅助栈min_stack来记录当前栈中的最小值。
数据结构考试题库含答案
数据结构考试题库含答案数据结构习题集含答案⽬录⽬录 (1)选择题 (2)第⼀章绪论 (2)第⼆章线性表 (4)第三章栈和队列 (5)第四章串 (6)第五章数组和⼴义表 (7)第六章树和⼆叉树 (7)第七章图 (9)第⼋章查找 (11)第九章排序 (12)简答题 (15)第⼀章绪论 (15)第⼆章线性表 (20)第三章栈和队列 (22)第四章串 (24)第五章数组和⼴义表 (24)第六章树和⼆叉树 (26)第七章图 (31)第⼋章查找 (33)第九章排序 (34)编程题 (36)第⼀章绪论 (36)第⼆章线性表 (36)第三章栈和队列 (46)第四章串 (46)第五章数组和⼴义表 (46)第六章树和⼆叉树 (46)第七章图 (46)第⼋章查找 (46)第九章排序 (52)选择题第⼀章绪论1. 数据结构这门学科是针对什么问题⽽产⽣的？（A ）A、针对⾮数值计算的程序设计问题B、针对数值计算的程序设计问题C、数值计算与⾮数值计算的问题都针对D、两者都不针对2. 数据结构这门学科的研究内容下⾯选项最准确的是（D ）A、研究数据对象和数据之间的关系B、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3. 某班级的学⽣成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下⾯关于数据对象、数据元素、数据项描述正确的是（C ）A、某班级的学⽣成绩表是数据元素，90分是数据项B、某班级的学⽣成绩表是数据对象，90分是数据元素C、某班级的学⽣成绩表是数据对象，90分是数据项D、某班级的学⽣成绩表是数据元素，90分是数据元素4. *数据结构是指（A ）。
A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义5. 数据在计算机存储器内表⽰时，物理地址与逻辑地址不相同，称之为（C ）。
A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6. 算法分析的⽬的是（C ）A、找出数据的合理性B、研究算法中的输⼊和输出关系C、分析算法效率以求改进D、分析算法的易懂性和⽂档型性7. 算法分析的主要⽅法（A ）。
数据结构习题集和答案
第1章绪论1、填空题1.常见的数据结构有_线性__结构，__树形___结构，__图形__结构等三种。
2.常见的存储结构有__顺序存储_______结构，__链式存储____结构等两种。
3.数据的基本单位是_数据元素___，它在计算机中是作为一个整体来处理的。
4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，__线性结构____和__非线性结构___。
2、应用题1、给出以下算法的时间复杂度.void fun(int n){int i=1,k=100;while(i<n){k=k+1;i=i+2;}}时间复杂度为____O（n）_____。
2、给出以下算法的时间复杂度.void fun2(int n){int i=1,k=100;while(i<n){i=i*10;k=k+1;}}时间复杂度为____O（log n）___________。
第2章线性表1、填空题1. 线性表按照存储结构不同主要有两种实现方式，一种是__顺序_表，另一种是___链___表。
2.顺序表采用__随机___访问机制对数据元素进行访问。
3.若在单链表结点p的后面插入一个新的结点s，则其操作序列为:①____s->next=p->next_____________；②____p->next=s___________________；4.在单向链表中，若要删除某个结点p，一般要找到__p的前趋__结点，才能实现该操作。
2、选择题1.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是A。
(A)n (B)2n－1 (C)2n (D)n-12.在单链表中，如果在结点p之后插入一个新结点s，其操作为 A 。
（A）s->next=p->next; p->next=s;（B）p->next=s; s->next=p->next;（C）s->next=p; p->next=s->next;（D）p->next=s; s->next=p;3.若长度为n的线性表采用顺序存储结构，在其第i个位置删除一个元素的算法的平均时间复杂度为( C )。
(完整word版)数据结构题集答案
数据结构题集第一章绪论一、单选题1.在数据结构中,从逻辑上可以把数据结构分成【C 】。
A.动态结构和静态结构B.紧凑结构和非紧凑结构C。
线性结构和非线性结构D。
内部结构和外部结构2.数据结构在计算机内存中的表示是指【A 】.A。
数据的存储结构 B.数据结构C。
数据结构的逻辑结构 D.数据元素之间的关系3. 【A 】是数据的最小单位，【B 】是数据的基本单位。
A。
数据项 B.数据元素C。
信息项D。
表元素4。
计算机所处理数据一般具有某种内在联系，这是指【B 】。
A。
数据与数据之间存在某种关系B。
数据元素与数据元素之间存在某种关系C。
元素内部存在某种结构 D.数据项与数据项之间存在某种关系5.算法分析的目的是【C 】.A.找出数据结构的合理性B。
研究输入和输出的关系C.分析算法的效率以求改进D。
分析算法的易懂性6。
在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储【C 】。
A。
数据处理的方法 B.数据元素的类型C。
数据元素之间的关系D。
数据的存储方法7。
算法分析的主要任务是分析【D 】。
A。
算法是否具有较好的可读性B.算法中是否存储语法错误和逻辑错误C。
算法的功能是否符合设计要求D.算法的执行时间与问题规模之间的关系.8.数据的运算【A 】.A。
效率与采用何种存储结构有关B.是根据存储结构来定义的C.有算术运算和关系运算两大类D.必须用程序设计语言来描述9。
算法的计算量的大小称为算法的【B 】.A。
效率B。
时间复杂度C。
现实性 D.难度10.连续存储分配时,存储单元的地址【A 】。
A.一定连续B.一定不连续C.不一定连续D。
部分连续，部分不连续二、判断题1.数据元素是数据结构的最小单位【。
×】。
2。
数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的存储结构【×.】。
3。
数据的逻辑结构指数据元素的各数据项之间的逻辑关系【×.】.4。
算法的优劣与算法的描述语言无关，但与使用的计算机有关【.×】。
数据结构题库及答案详解
数据结构题库及答案详解一、选择题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. 给定一个整数数组，请实现一个函数来找到数组中的最长连续子序列的长度。
数据结构试题库及答案
数据结构试题库及答案一、选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构通常使用（）来存储。
A. 链表B. 栈C. 队列D. 数组答案：D2. 以下哪个算法不是排序算法？A. 快速排序B. 归并排序C. 深度优先搜索D. 堆排序答案：C3. 在二叉树的遍历算法中，先访问根节点，然后遍历左子树，最后遍历右子树的遍历方式是（）。
A. 先序遍历B. 中序遍历C. 后序遍历D. 层序遍历答案：A4. 哈希表的冲突解决方法不包括以下哪种？A. 链地址法B. 线性探测法C. 二分查找法D. 再散列法答案：C5. 在图的遍历算法中，广度优先搜索（BFS）使用的辅助数据结构是（）。
A. 栈B. 队列C. 堆D. 链表答案：B6. 下列关于堆的描述中，错误的是（）。
A. 堆是一种特殊的完全二叉树B. 堆中的每个节点的值都大于其子节点的值C. 堆可以用于实现优先队列D. 堆的插入操作的时间复杂度为O(log n)答案：B7. 在一个长度为n的数组中，使用二分查找算法查找一个元素的最坏情况下的时间复杂度是（）。
A. O(1)B. O(n)C. O(n^2)D. O(log n)答案：D8. 以下哪个数据结构不是线性结构？A. 链表B. 栈C. 队列D. 二叉树答案：D9. 以下哪个算法是动态查找表？A. 直接索引B. 顺序查找C. 二分查找D. 哈希表答案：D10. 在图的表示方法中，邻接矩阵表示法的缺点是（）。
A. 占用空间大B. 占用空间小C. 插入和删除操作复杂D. 遍历操作复杂答案：A二、填空题（每题2分，共20分）1. 在一个长度为n的数组中，使用顺序查找算法查找一个元素的时间复杂度为________。
答案：O(n)2. 一个具有n个节点的完全二叉树的高度为________。
答案：log2(n) + 1（向上取整）3. 一个长度为n的链表，删除一个节点的时间复杂度为________。
答案：O(1)4. 在图的表示方法中，邻接表表示法的缺点是________。
数据结构练习题(含答案)
数据结构练习题习题1 绪论1.1 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。
① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。
① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象② A．操作Ｂ．映象Ｃ．存储Ｄ．关系3. 在数据结构中，从逻辑上可以把数据结构分成。
A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4. 算法分析的目的是①，算法分析的两个主要方面是②。
① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性② A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。
① A. 计算方法 B. 排序方法C. 解决问题的有限运算序列D. 调度方法② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性1.2 填空题（将正确的答案填在相应的空中）1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。
2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。
3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。
4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。
5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。
数据结构习题集答案
数据结构》习题集答案第一章绪论（1-1）一、选择题：1、B、D 2 、A、B 3 、4 4 、C、A 5 、C 6 、D7、A 8 、A 9 、D 10 、1 11 、2 12 、A、D 13 、3 二、填空题1、数据元素数据元素间关系2、集合线性结构树形结构图状结构或网状结构。
3、数据的组织形式，即数据元素之间逻辑关系的总体。
而逻辑关系是指数据元素之间的关联方式或称“邻接关系” 。
4、表示（又称映像）。
5、（1）逻辑特性（2）在计算机内部如何表示和实现（3）数学特性。
6、算法的时间复杂度和空间复杂度。
7、（1）逻辑结构（2）物理结构（3）操作（运算）（4）算法。
绪论（1-2）一、选择题：1、B 2 、C 3 、C，B 4 、B 5 、C6、D 7 、B 8 、O(sqrt(n))二、填空题1、（1）有穷性( 2)确定性（3）可行性。
2、( 1 ) n+12) n ( 3) n(n+3)/2 (4) n(n+1)/2 。
3、1+ (1+2++ (1+2+3) + …+ (1+2+…+n) =n(n+1)( n+2)/6 O(n 3)4、O(n)5、n(n-1)/2第二章线性表（1-1 ）、选择题：1、B 2 、B 3 、A 4 、B 5 、C6、A 7 、D 8 、D 9 、D 10 、B，C11、C 12 、C二、填空题1 、顺序2、（ n-1 ）/23、n-i+1第二章 线性表( 1-2 )一、选择题：1、C 2 、 B 3、B 4、C5 、A6 、C7、B8 、A 9 、D10 、 B 11、C 12 、 B 13 、A二、填空题1、 py->next=px->next; px->next=py2、主要是使插入和删除等操作统一，在第一个元素之前插入 元素 和删除第一个结点不必另作判断。
另外，不论链表是否为空，链表指针不变。
3、O(1) ，O(n)4、单链表，多重链表， (动态)链表，静态链表5、 f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;6、指针7、物理上相邻 指针8、 4 29、从任一结点出发都可访问到链表中每一个元素。
数据结构试题库及答案
数据结构试题库及答案一、选择题1. 在数据结构中，线性结构的特点是：A. 元素之间存在一对一关系B. 元素之间存在一对多关系C. 元素之间存在多对多关系D. 元素之间存在一对一或多对多关系答案：A2. 栈（Stack）是一种特殊的线性表，其特点是：A. 只能在一端进行插入和删除操作B. 可以在两端进行插入和删除操作C. 只能在一端进行插入操作，另一端进行删除操作D. 可以在任意位置进行插入和删除操作答案：A3. 在二叉树中，度为1的节点数目为2，度为0的节点数目也为2，该二叉树的节点总数是：A. 5B. 6C. 7D. 8答案：B二、简答题1. 请简述什么是哈希表，并说明其主要优点。
答案：哈希表是一种通过哈希函数将键映射到表中一个位置来访问记录的数据结构。
其主要优点包括：平均情况下，查找、插入和删除操作的时间复杂度为O(1)，即常数时间内完成操作；空间效率高，能够存储大量数据。
2. 描述图的深度优先搜索（DFS）算法的基本思想。
答案：深度优先搜索算法的基本思想是从一个顶点开始，尽可能深地搜索图的分支。
搜索过程中使用一个栈来保存路径上的顶点。
当搜索到一个顶点时，先访问该顶点，然后依次搜索其所有未被访问过的邻接顶点。
如果当前顶点的所有邻接顶点都被访问过，则回溯到上一个顶点，继续搜索其他邻接顶点。
三、应用题1. 给定一个无向图，使用邻接表表示，请编写一个算法找出图中的所有连通分量。
答案：首先，创建一个访问过的顶点集合。
然后，从图中任意一个未被访问的顶点开始，执行深度优先搜索（DFS）。
每次DFS完成后，就找到了一个连通分量。
重复这个过程，直到所有顶点都被访问过，即可找到图中的所有连通分量。
2. 假设有一个数组，需要频繁地进行查找、插入和删除操作，请设计一个适合这种场景的数据结构，并说明其优势。
答案：对于这种场景，可以使用平衡二叉搜索树（如AVL树或红黑树）。
这些数据结构可以保证在最坏情况下，查找、插入和删除操作的时间复杂度为O(log n)。
数据结构习题(包含全部答案解析)
数据结构习题(包含全部答案解析)数据结构习题（包含全部答案解析）1. 塔的问题题目描述：有三个塔，分别是A、B和C，A塔上有n个盘子，按照从小到大的顺序叠放。
现在要将这些盘子从A塔移动到C塔，并且每次只能移动一个盘子，并且在移动过程中保持大盘子在下，小盘子在上的顺序。
求移动的步骤。
解析：这道题可以使用递归来解决。
将问题分解为两个子问题：将n-1个盘子从A塔移动到B塔，然后将最后一个盘子从A塔移动到C 塔，最后再将n-1个盘子从B塔移动到C塔。
步骤如下：1）如果n等于1，直接将盘子从A塔移动到C塔；2）否则，执行以下步骤：a) 将n-1个盘子从A塔移动到B塔，使用C塔作为中转塔；b) 将最后一个盘子从A塔移动到C塔；c) 将n-1个盘子从B塔移动到C塔，使用A塔作为中转塔。
2. 链表问题题目描述：给定一个链表，判断链表是否存在环。
解析：这道题可以使用快慢指针的思想来解决。
定义两个指针fast和slow，初始时都指向链表的头节点。
fast指针每次向后移动两个节点，slow指针每次向后移动一个节点。
如果链表中存在环，则fast指针一定会在某个时刻追上slow指针。
步骤如下：1）定义两个指针fast和slow，初始时都指向链表的头节点；2）使用一个while循环，判断条件是fast指针不为空且其下一个节点也不为空；3）在循环中，fast指针每次向后移动两个节点，slow指针每次向后移动一个节点；4）如果fast指针和slow指针相遇，则链表存在环，返回true；5）如果fast指针和slow指针永远不相遇，则链表不存在环，返回false。
3. 栈的应用题目描述：给定一个只包含'('和')'的字符串，判断该字符串是否是有效的括号序列。
解析：这道题可以使用栈来解决。
遍历字符串的每一个字符，如果是左括号，将其压入栈中；如果是右括号，判断栈顶的字符是否与该右括号匹配，若匹配则出栈，若不匹配则该字符串不是有效的括号序列。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
数据结构习题集(自编)第一章绪论一、选择题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与B6.一个算法应该就是( )。
A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A与C、7、下面关于算法说法错误的就是( )A.算法最终必须由计算机程序实现B、为解决某问题的算法与为该问题编写的程序含义就是相同的C、算法的可行性就是指指令不能有二义性D、以上几个都就是错误的8.以下与数据的存储结构无关的术语就是( )。
A.循环队列 B、链表 C、哈希表D、栈9.在下面的程序段中,对x的赋值语句的频度为( )for(i=0;i<n;i++)for(j=0;j<n;j++)x=x+1;nA. 2nB.nC.n2D.log210.以下数据结构中,( )就是非线性数据结构A.树B.字符串C.队列D.栈11、下列数据中,( )就是线性数据结构。
A.哈夫曼树 B、有向无环图 C、二叉排序树 D、栈12.以下属于逻辑结构的就是( )。
A.顺序表 B、哈希表C、有序表 D、单链表二、填空题1、_______就是信息的载体,就是对客观事物的符号表示,它能够被计算机识别、存储、加工与处理,________就是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。
(数据、数据)2、数据元素就是数据的______,有些情况下也称为元素、结点、顶点、记录等。
(基本单位)3、________就是数据不可分割的最小单元,就是具有独立含义的最小标识单位。
例如构成一个数据元素的字段、域、属性等都可称之为________。
(数据项、数据项)4、数据的逻辑结构就是指数据之间的________。
逻辑结构就是从________上描述数据,它与具体存储无关,就是独立于计算机的。
因此逻辑结构可以瞧作就是从具体问题抽象出来的______________。
(逻辑关系、逻辑关系、数学模型)5、数据的________指数据元素及其关系在计算机存储器内的表示。
_________就是逻辑结构在计算机里的实现,也称之为映像。
(存储结构、存储结构)6、数据逻辑结构可以分为四种基本的类型,_______结构中的元素除了仅仅只就是同属于一个_________________,不存在什么关系。
(集合、集合)7、数据逻辑结构的四种基本类型中,________中的元素就是一种一对一的关系,这种结构的特征就是:若结构就是非空集,则有且只有一个开始结点与一个终端结点,并且所有结点最多只能有一个直接前驱与一个直接后继。
(线性结构)8、数据逻辑结构的四种基本类型中,____________中的元素就是一种一对多的关系。
(树形结构)9、图型结构或图状结构就是一种________的关系。
在这种逻辑结构中,所有结点均可以有多个前驱与多个后继。
(多对多)10、有时也可将树型结构、集合与图型结构称为__________,这样数据的逻辑结构就可以分为__________与________两大类。
(非线性结构、线性结构、非线性机构)11、____________方式就是指逻辑上相邻的结点被存储到物理上也相邻的存储单元中。
这种存储结构只存储结点的数值,不存储结点之间的关系,结点之间的关系就是通过存储单元的相邻关系隐含的表示出来的。
(顺序存储)12、_______方式就是种存储方法,不要求逻辑上相邻的结点在物理上也相邻,即数据元素可以存储在任意的位置上。
(链式存储)13、_________方式就是利用结点关键字的值直接计算出该结点存储单元地址,然后将结点按某种方式存人该地址的一种方法。
(散列存储或哈希存储)14、所谓算法(Algorithm)就是对特定问题求解步骤的一种描述,它就是指令的其中每个指令表示一个或多个操作。
算法的五个重要特性就是__________、__________、__________、__________与__________。
(有限序列、有穷性、确定性、可行性、输入、输出)15、算法的_______性就是指算法必须能够在执行有限个步骤之后结束,并且每个步骤都必须在有穷的时间内完成。
(有穷性)16、算法的________性就是指算法中的每一个步骤必须就是有明确定义的,不允许有模棱两可的解释,也不允许有多义性。
并且,在任何条件下,算法只能有惟一的一条执行路径,即只要输人就是相同的就只能得到____________的输出结果。
(确定性、相同)17、算法的____________性又称为算法的能行性,就是指算法中描述的操作就是可以通过已经实现的基本运算执行有限次来实现。
(可行性)18、判断一个算法的好坏主要以下几个标准:________、________、________、_________。
(正确性、可读性、健壮性、时间效率与空间效率)19、算法分析就是对一种算法所消耗的计算机资源的估算,其中包括计算机_________的长短与___________________的大小。
(运行时间、所占据空间)20、空间复杂度(SPace ComPlexity)也就是度量一个算法好坏的标准,它所描述的就是算法在运行过程中所占用_____________的大小。
(存储空间)三、判断题1.顺序存储方式只能用于存储线性结构。
(×)2.数据元素就是数据的最小单位。
(×)3.算法的优劣与算法描述语言无关,但与所用计算机有关。
(×)4.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。
()5.数据的逻辑结构就是指各元素之间的逻辑关系,就是根据用户需要而建立的。
6.数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。
()7.数据的物理结构就是指数据在计算机中实际的存储形式。
()8.具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。
9.算法实际上就就是程序,程序也一定就是算法。
(×)10、在顺序存储结构中,有时也存储数据结构中元素之间的关系。
(×)11、顺序存储方式的优点就是存储密度大,且插入、删除运算效率高。
(×)12、数据结构的基本操作的设置的最重要的准则就是,实现应用程序与存储结构的独立。
()13、数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。
(×)14、判断一个算法的好坏主要以下几个标准:正确性、有穷性、健壮性与可行性。
(×)15.算法的时间复杂度T(n)=O(f(n))表示随问题规模n的增大,算法执行时间的增长率与函数f(n)的增长率相同。
()四、综合题1.用大O形式表示下面算法的时间复杂度:for(i=0;i＜m;i十十)for(j=0;j＜n;j＋＋)A[i][j]=i*j;2.写出下面算法的时间复杂度:i＝0;s=0;while(s＜n)｛ i++;s+=i;｝3.写出以下算法的时间复杂度:for(i＝0; i＜m; i＋＋)for(j＝0 ; j＜t; j＋＋)c[i][j]=0;for(i=0;i＜m;i＋＋)for(j=o; j<t; j++)for(k=0;k＜n;k＋＋)c［i］［j］＋＝a［i］［k］*b[k][j];4.写出下面算法的时间复杂度:i=1;while(i＜＝n)i=i*3;5.求下面函数中各条语句的频度与算法的时间复杂度:prime(int n)｛int i＝2;while ((n％i)！=0＆＆i＜sqrt(n) )i++;if(i＞sqrt(n) )printf(”％d is a prime number、＼n”,n);elseprintf(”％d is not a prime number、＼n”,n);｝1、该算法的时间复杂度为:O(m×n)。
2、该算法的时间复杂度为3、该算法的时间复杂度为:O(m×n×t)。
(n)。
4、该算法的时间复杂度为:log3。
5、该算法的时间复杂度为6.将下列函数,按它们在n→∝时的无穷大阶数,从小到大排序。
n, n-n3+7n5, nlogn, 2n/2, n3, logn, n1/2+logn, (3/2)n, ,n!, n2+logn 从小到大排列为:logn, n1/2+logn, n, nlogn, n2+logn,n3, n-n3+7n5, 2n/2, (3/2)n, n!,第二章线性表一、选择题1.在一个长度为n的顺序表中删除第i个元素(0<i<=n)时,需要向前移动( )个元素。
A.n-iB.n-i+1C.n-i-1D.i+12.从一个具有n个元素的线性表中查找其值等于x的结点时,在查找成功的情况下,需平均比较( )个元素结点。
A.n/2B.nC.(n-1)/2D.(n +1)/23.对一个具有n个元素的线性表,建立其单链表的时间复杂度为( )。
A.O(n)B.O(1)C.O(n2)D.O(long2n)4.线性表采用链式存储时,其地址( )。
A. 必须就是连续的B.一定就是不连续的C.部分地址必须连续D.连续与否均可以5.在一个具有n个结点的有序单链表中插人一个新的结点,使得链表仍然有序,该算法的时间复杂度就是( )。
A.O(long2n) B.O(l) C.O(n2) D.O(n)6.线性表就是( )。
A.一个有限序列,可以为空B.一个有限序列,不可以为空C.一个无限序列,可以为空D.一个无限序列,不可以为空7.在一个长度为n的顺序表中,向第i个位置(0一1＜n＋1)插入一个新元素时,需要向后移动( )个元素。
A.n-iB.n-i＋1C.n－i－1D.i＋18.如果某链表中最常用的操作就是取第i个结点及其前驱,则采用( )存储方式最节省时间。
A.单链表B.双向链表C.单循环链表D.顺序表9.一个顺序存储线性表的第一个元素的存储地址就是90,每个元素的长度就是2,则第6个元素的存储地址就是()。
A.98B.100C.102D.10610.在顺序存储的线性表(a1……an)中,删除任意一个结点所需移动结点的平均移动次数为( )A.nB.n／2C.(n-1)/2D.(n＋l)/211.在线性表的下列存储结构中,读取第i个元素花费的时间最少的就是()。