数据结构与算法作业

数据结构习题集一、选择题１.在一个长度为n的顺序表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动B个元素。

A. n-1B. n-i+1C. n-i-1D. i２.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针，则当做退栈处理时，top变化为C。

A. top不变Ｂ. top＝-n C. top＝top-1 D. top=top+1３.向顺序栈中压入元素时，是A。

A. 先存入元素，后移动栈顶指针B.先移动栈顶指针，后存入元素４.在一个顺序存储的循环队列中，队首指针指向队首元素的A。

A. 前一个位置B. 后一个位置C. 队首元素位置D. 队尾元素位置５.若进栈序列为1,2,3,4,进栈过程中可以出栈，则C不可能是一个出栈序列。

A. 3,4,2,1B. 2,4,3,1C. 1,4,2,3D. 3,2,1,4６.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是C。

A. front= =rear+1B. front+1= =rearC. front= =rearD. front= =0７.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队满的条件是D。

A. rear % n= =frontB. (rear-1) % n= =frontC. (rear-1) % n= =rearD. (rear+1) % n= =front８.从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较D个结点。

A. nB. n/2C. (n-1)/2D. (n+1)/2９.在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点，则执行C。

A. s->next=p->next; p->next=s;B. p->next=s->next; s->next=p;C. q->next=s; s->next=p;D. p->next=s; s->next=q;10.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行C。

《数据结构与算法》作业参考答案说明：1、题号形式: 每题都以【sn，cha，sec】开头，sn表明本题的题目序号，每道题都有唯一的序号；cha表示内容所在的章；sec表示内容所在的节。

如:【17，2，1】表示序号17的题来自第2章第1节。

2、题型：1) 选择题：序号1-180题2) 是非题：序号181-220题3) 分析计算作图题：序号221-250题（选自《数据结构题集》—严蔚敏等编）3、内容取舍：根据本学期上课课件中的内容，未上课章节的练习可舍弃。

4、必做题或选做题：是非题和选择题（序号1-220）只要在上过课的章节中都是必做题，分析计算作图题（序号221-250）在每题后标出是必做题还是选做题，其中16个必做题14个选做题。

1) 选择题：序号1-180题序号参考答案1 BD2 D3 C4 A5 C6 D7 C8 D9 B10 D11 B12 D13 C14 C15 D16 A17 A18 A19 A20 A21 A22 D24 A25 B26 C27 C28 C29 B30 B31 B32 B33 B34 A35 A36 C37 D38 D39 B40 C41 B42 A43 D44 B45 D46 B47 C48 C49 B50 B51 A52 D53 D54 C55 A56 A57 C58 C59 C60 B61 A62 D64 B65 C66 B67 D68 D69 B70 A71 C72 B73 A74 D75 D76 B77 C78 C79 D80 B81 D82 C83 B84 A85 B86 C87 D88 B89 B90 B91 D92 C93 D94 A95 C96 C97 B98 A99 C 100 C 101 A 102 D 103 C105 C 106 D 107 C 108 B 109 B 110 D111 A 112 B 113 A 114 B 115 C 116 D 117 B 118 C 119 A 120 B121 A 122 A 123 C 124 C 125 B 126 B 127 B 128 C 129 C 130 B131 A 132 D 133 AB 134 D 135 C 136 C 137 B 138 A 139 B 140 B141 D 142 A 143 B145 A146 A147 C148 B149 C150 A151 B152 B153 C154 B155 A156 C157 C158 C159 A160 B161 C162 A163 A164 D165 B166 C167 D168 C169 C170 B171 B172 C173 B174 D175 C176 D177 B178 A179 A180 B2) 是非题：序号181-220题181 T182 T183 F184 T185 T186 F187 T188 T189 T190 T191 F192 T193 T194 F195 F196 T197 F198 T199 F200 T201 T202 T203 F204 T205 T206 F207 T208 T209 F210 T211 F212 T213 T214 F215 T216 T217 F218 T219 T220 F3) 分析计算作图题：序号221-250（选自《数据结构题集》—严蔚敏等编）【221，1，4】（选自《数据结构题集》1.8，选做题）设n为正整数，试确定下列各段程序中前置以记号@的语句的频度(语句的频度指的是该语句重复执行的次数)。

数据结构与算法实践练习题目及解答以下是一些数据结构与算法的实践练题目及其解答。

1. 数组相关题目题目一给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的索引。

def twoSum(nums, target):nums_dict = {}for i in range(len(nums)):nums_dict[nums[i]] = i题目二给定一个整数数组 nums，将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

def moveZeroes(nums):count = 0for i in range(len(nums)):if nums[i] != 0:nums[count] = nums[i]count += 1while count < len(nums):nums[count] = 0count += 12. 链表相关题目题目三反转一个单链表。

class ListNode:def __init__(self, val=0, next=None): self.val = valself.next = nextdef reverseList(head):prev = Nonecurr = headwhile curr is not None:next_node = curr.nextcurr.next = prevprev = currcurr = next_nodereturn prev题目四给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

def deleteDuplicates(head):curr = headwhile curr is not None and curr.next is not None:if curr.val == curr.next.val:curr.next = curr.next.nextelse:curr = curr.nextreturn head以上是一些数据结构与算法的实践练习题目及其解答。

《数据结构与算法》习题与答案（解答仅供参考）一、名词解释：1. 数据结构：数据结构是计算机存储、组织数据的方式，它不仅包括数据的逻辑结构（如线性结构、树形结构、图状结构等），还包括物理结构（如顺序存储、链式存储等）。

它是算法设计与分析的基础，对程序的效率和功能实现有直接影响。

2. 栈：栈是一种特殊的线性表，其操作遵循“后进先出”（Last In First Out, LIFO）原则。

在栈中，允许进行的操作主要有两种：压栈（Push），将元素添加到栈顶；弹栈（Pop），将栈顶元素移除。

3. 队列：队列是一种先进先出（First In First Out, FIFO）的数据结构，允许在其一端插入元素（称为入队），而在另一端删除元素（称为出队）。

常见的实现方式有顺序队列和循环队列。

4. 二叉排序树（又称二叉查找树）：二叉排序树是一种二叉树，其每个节点的左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。

这种特性使得能在O(log n)的时间复杂度内完成搜索、插入和删除操作。

5. 图：图是一种非线性数据结构，由顶点（Vertex）和边（Edge）组成，用于表示对象之间的多种关系。

根据边是否有方向，可分为有向图和无向图；根据是否存在环路，又可分为有环图和无环图。

二、填空题：1. 在一个长度为n的顺序表中，插入一个新元素平均需要移动______个元素。

答案：(n/2)2. 哈希表利用______函数来确定元素的存储位置，通过解决哈希冲突以达到快速查找的目的。

答案：哈希（Hash）3. ______是最小生成树的一种算法，采用贪心策略，每次都选择当前未加入生成树且连接两个未连通集合的最小权重边。

答案：Prim算法4. 在深度优先搜索（DFS）过程中，使用______数据结构来记录已经被访问过的顶点，防止重复访问。

答案：栈或标记数组5. 快速排序算法在最坏情况下的时间复杂度为______。

1、在二叉搜索树（BST）中，以下哪个遍历顺序会按从小到大的顺序访问所有节点？A. 前序遍历B. 中序遍历C. 后序遍历D. 层次遍历（答案：B）2、对于一个给定的无向图，以下哪种算法最适合找到从起点到终点的最短路径（假设所有边的权重都相等）？A. Dijkstra算法B. Bellman-Ford算法C. Floyd-Warshall算法D. 广度优先搜索（BFS）（答案：D）3、在哈希表中处理冲突的一种方法是链地址法（也称为拉链法），以下关于链地址法的说法错误的是：A. 每个哈希表槽位连接一个链表B. 当发生冲突时，新元素添加到对应槽位的链表末尾C. 链地址法不需要处理哈希函数的设计，因为冲突总是通过链表解决D. 查找、插入和删除操作的时间复杂度与链表的长度有关（答案：C）4、以下哪种数据结构最适合实现优先队列，且支持高效的插入和删除最小（或最大）元素操作？A. 数组B. 链表C. 二叉堆D. 平衡二叉搜索树（如AVL树）（答案：C）5、在快速排序算法中，选择哪个元素作为基准（pivot）对算法的效率有重要影响，以下哪种策略通常不是一个好的选择？A. 数组的第一个元素B. 数组的最后一个元素C. 数组中间的元素D. 随机选择一个元素（答案：视具体情况而定，但通常A、B在特定情况下可能不是最佳，如当数组已近排序时；然而，此题要求选一个“通常不是好选择”的，若必须选一个，可以认为A或B在未知数据分布时风险较高，答案可倾向A或B，这里选A作为示例）6、以下哪个不是图的遍历算法？A. 深度优先搜索（DFS）B. 广度优先搜索（BFS）C. A*搜索算法D. 拓扑排序（答案：D）7、在平衡二叉搜索树（如红黑树）中，以下哪个操作的时间复杂度不是O(log n)？A. 查找B. 插入C. 删除D. 计算树中所有节点的和（答案：D，因为计算所有节点和需要遍历整个树，时间复杂度为O(n)）8、以下哪种情况最适合使用动态规划算法来解决？A. 查找无序数组中的最大值B. 对一组数进行排序C. 计算斐波那契数列的第n项D. 在已排序的数组中查找特定元素（答案：C）。

北理工《数据结构与算法》在线作业试卷总分：100 测试时间：-- 试卷得分：99.5一、单选题（共40 道试题，共99.5 分。

）得分：99.51. 图的存储结构不包括()A. 数组表示B. 邻接表C. 邻接多重表D. 孩子兄弟表示正确答案：D 满分：2.5 分得分：2.52. 当两个元素比较出现反序时就相互交换位置的排序方法称为()。

A. 归并排序B. 选择排序C. 交换排序D. 插入排序正确答案：C 满分：2.5 分得分：2.53. 快速排序属于那种排序类型()。

A. 选择排序B. 插入排序C. 交换排序D. 基数排序正确答案：C 满分：2.5 分得分：2.54. 中序遍历一棵二叉排序树所得到的结点序列是键值的()序列。

A. 递增或递减B. 递减C. 递增D. 无序正确答案：C 满分：2.5 分得分：2.55. 关键路径是指AOE(Activity On Edge)网中()。

A. 最长的回路B. 最短的回路C. 从源点到汇点(结束顶点)的最长路径D. 从源点到汇点(结束顶点)的最短路径正确答案：C 满分：2.5 分得分：2.56. 设有一个二维数A[m][n]，以行序为主序存储。

假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，则A[4][5]在()位置，(10)表明用10进数表示。

A. 692(10)B. 626(10)C. 709(10)D. 724(10)正确答案：C 满分：2.5 分得分：2.57. 当待排序列基本有序时，下列排序方法中()最好。

A. 直接插入排序B. 快速排序C. 堆排序。

数据结构与算法设计试卷（答案见尾页）一、选择题1. 数据结构中，下列哪种数据结构的插入和删除操作时间复杂度最低？A. 栈B. 队列C. 数组D. 链表2. 在二叉树的遍历方法中，哪种方法可以访问所有节点且时间复杂度为O(n)？A. 前序遍历B. 中序遍历C. 后序遍历D. 层次遍历3. 常用的排序算法中，哪种算法是基于比较的排序算法，并且时间复杂度为O(n log n)？A. 冒泡排序B. 选择排序C. 插入排序D. 归并排序4. 在图的存储结构中，邻接矩阵适合表示哪种类型的图？A. 稀疏图B. 密集图C. 有向无环图D. 无向无环图5. 动态规划算法用于解决哪种类型的问题？A. 数值计算问题B. 字符串匹配问题C. 图论问题D. 机器学习问题6. 在最短路径问题中，Dijkstra算法和Floyd算法分别适用于哪种类型的图？A. 有权图和无权图B. 无权图和有权图C. 有向图和无向图D. 无向图和有权图7. 快速排序算法中，基准元素的选择对算法性能有何影响？A. 基准元素的选择不影响算法性能B. 基准元素选择不当会导致算法性能下降C. 基准元素选择得当可以提高算法性能D. 基准元素的选择与算法性能无关8. 在链表中，单向链表的每个节点包含哪些部分？A. 数据域和指针域B. 数据域和指针头C. 数据域和指针尾D. 数据域和指针尾9. 在栈的实现中，后进先出（LIFO）原则是如何体现的？A. 先进入栈的元素总是最先被移除B. 先进入栈的元素总是最后被移除C. 后进入栈的元素总是最先被移除D. 后进入栈的元素总是最后被移除10. 哈希表（Hash Table）的主要优点是什么？A. 查找速度快，插入和删除操作较慢B. 查找速度较慢，插入和删除操作较快C. 查找速度较快，插入和删除操作也较快D. 查找速度较慢，插入和删除操作也较慢11. 在最坏情况下，下列哪种排序算法的时间复杂度为O(n^)？A. 冒泡排序B. 选择排序C. 插入排序D. 归并排序12. 在二叉树的遍历方法中，先序遍历的特点是？A. 先访问根节点，然后遍历左子树，最后遍历右子树B. 先访问左子树，然后访问根节点，最后遍历右子树C. 先访问左子树，然后访问右子树，最后访问根节点D. 先访问右子树，然后访问左子树，最后访问根节点13. 常用的查找算法中，哈希表的查找效率最高，其平均查找时间复杂度为？A. O(1)B. O(log n)C. O(n)D. O(n log n)14. 下列哪种数据结构适用于表示稀疏线性表？A. 数组B. 链表C. 栈D. 队列15. 最短路径问题在图论中的研究内容是？A. 路径长度B. 路径上的节点序列C. 最短路径的长度及路径上的节点序列D. 最短路径的权重16. 快速排序算法是基于什么思想进行递归划分的？A. 分治法B. 动态规划C. 贪心算法D. 回溯算法17. 在图的遍历算法中，普里姆算法用于寻找？A. 所有顶点的最短路径B. 两个顶点之间的最短路径C. 一棵树的中序遍历D. 一棵树的前序遍历18. 下列哪种数据结构可以实现队列的先进先出（FIFO）特性？A. 栈B. 队列C. 数组D. 链表19. 在深度优先搜索算法中，哪种策略用于访问所有可能的路径？A. 沿着边遍历B. 沿着对角线遍历C. 沿着某一特定方向遍历D. 沿着任意方向遍历20. 在图的遍历算法中，普里姆算法用于求解什么问题？A. 最小生成树B. 最短路径C. 连通性D. 网络流21. 哈希表的冲突解决策略中，链地址法适用于哪种情况？A. 哈希函数值分布均匀B. 哈希函数值分布不均匀C. 存储的元素数量较大D. 存储的元素数量较小22. 在快速排序算法中，基准元素的选择对算法性能有何影响？A. 基准元素选择不合适会导致排序效率降低B. 基准元素选择不合适会导致排序效率提高C. 基准元素选择对算法性能没有影响D. 基准元素选择与算法性能无关23. 在二叉树的遍历算法中，先序遍历、中序遍历和后序遍历分别适用于哪些类型的树？A. 充分不平衡的二叉树B. 充分平衡的二叉树C. 不充分平衡的二叉树D. 完全不平衡的二叉树24. 在贪心算法中，贪心选择性质如何帮助求解问题？A. 贪心选择性质使得每次选择都能立即带来全局最优解B. 贪心选择性质使得每次选择都能减少后续问题的规模C. 贪心选择性质使得每次选择都能增加后续问题的规模D. 贪心选择性质使得每次选择都能保持问题的原有规模25. 在动态规划算法中，状态转移方程如何描述问题的解决过程？A. 状态转移方程描述了问题状态之间的转移过程B. 状态转移方程描述了问题状态之间的变换过程C. 状态转移方程描述了问题状态之间的依赖关系D. 状态转移方程描述了问题状态之间的组合关系26. 在下列哪种数据结构中，元素之间的逻辑关系可以通过指针直接访问？A. 数组B. 链表C. 栈D. 队列27. 下列哪种排序算法的平均时间复杂度为O(n^)？A. 快速排序B. 归并排序C. 堆排序D. 插入排序28. 在图论中，表示图中节点间有向边的图形是？A. 无向图B. 有向图C. 网络图D. 树29. 在树的遍历算法中，先序遍历、中序遍历和后序遍历分别指的是什么？A. 先访问根节点，再遍历左子树，最后遍历右子树B. 先访问左子树，再访问根节点，最后遍历右子树C. 先访问左子树，再遍历右子树，最后访问根节点D. 先访问根节点，再遍历右子树，最后遍历左子树30. 在图的存储结构中，邻接矩阵和邻接表分别适用于哪种情况？A. 小型图和大中型图B. 大中型图和小型图C. 都适用于大型图D. 都适用于小型图31. 在动态规划算法中，解决最短路径问题常用的算法是？A. 贝尔曼-福特算法B. 弗洛伊德-沃沙尔算法C. 克鲁斯卡尔算法D. 普里姆算法32. 在贪心算法中，贪心选择性质是指什么？A. 每一步都选择局部最优解，整个问题就最优B. 每一步都选择全局最优解，整个问题就最优C. 每一步都选择当前最优解，整个问题就最优D. 每一步都选择历史最优解，整个问题就最优33. 在搜索算法中，广度优先搜索（BFS）和深度优先搜索（DFS）有何不同？A. BFS从根节点开始，逐层扩展；DFS从任意节点开始，深入探索B. BFS从任意节点开始，逐层扩展；DFS从根节点开始，深入探索C. BFS只搜索浅层节点，DFS可能搜索深层的叶子节点D. BFS只搜索浅层节点，DFS可能搜索深层的叶子节点34. 在图论中，强连通分量是指什么？A. 图中任意两个顶点之间都有路径相连B. 图中任意三个顶点之间都有路径相连C. 图中存在一个顶点集合，使得每个顶点都与另一个顶点直接相连D. 图中存在一个顶点集合，使得每个顶点都与另一个顶点循环相连35. 在下列哪种数据结构中，元素之间的关系可以通过指针直接访问？A. 数组B. 链表C. 栈D. 队列36. 在排序算法中，稳定性意味着什么？A. 相同值的元素在排序后相对顺序不变B. 不相邻的元素在排序后相对顺序不变C. 相邻的元素在排序后相对顺序不变D. 所有元素的相对顺序都不变37. 下列哪种排序算法是递归的？A. 冒泡排序B. 选择排序C. 插入排序D. 归并排序38. 在图的存储结构中，邻接矩阵更适合表示哪种类型的图？A. 小型图B. 大型图C. 稀疏图D. 密集图二、问答题1. 什么是递归？请举例说明递归在计算机科学中的应用。

单选题1.从原理上讲，折半查找法要求查找表中各元素的键值必须是____• A 递增或递减• B 递增• C 递减• D 无序单选题2.关于判定树，下列说法不正确的是____• A 判定树是对有序序列进行二分查找得到的树• B n个结点的判定树的深度为[log2n]+1• C 判定树的叶子结点都在同一层• D 判定树除去最后一层结点以后是满二叉树或空二叉树单选题3.在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做____次关键码比较• A 2• B 3• C 4• D 5单选题4.对线性表进行二分查找时，要求线性表必须____• A 以顺序方式存储• B 以顺序方式存储且元素有序• C 以链式方式存储• D 以链式方式存储且元素有序单选题5.折半查找算法的时间复杂度是____• A O(n2)• B O(n)• C O(log2n)• D O(nlog2n)单选题6.若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至____• A 该中间位置• B 该中间位置－1• C 该中间位置＋1• D 该中间位置／2单选题7.对包含N个元素的散列表进行查找，平均查找长度____• A 为O(log2N)• B 为O(N)• C 不直接依赖于N• D 上述三者都不是单选题8.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过____• A n/2• B n• C (n+1)/2• D n+1单选题9.分别以下列序列构造二叉排序树，则与其它几个序列构造的结果不同的是____• A （80，70，60，75，90，85，100，10）• B （80，90，85，70，60，10，75，100）• C （80，90，70，85，10，60，75，100）• D （80，90，100，70，85，60，10，75）单选题10.如果某二叉树的左右子树的高度差的绝对值不大于1，则一定是平衡二叉树• A 正确• B 不正确单选题11.AVL树的任何子树都是AVL树。

浙江大学远程教育学院《数据结构与算法》课程离线作业姓名：学号：年级：学习中心：—————————————————————————————一、填空题：（【序号，章，节】。

）【1，1，2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。

【2，1，2】为了最快地存取数据元素，物理结构宜采用结构。

【3，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为__，___。

【4，1，3】度量算法效率可通过__来进行。

【5，1，3】设n 为正整数，下面程序段中前置以记号@的语句的频度是1。

for (i=0; i<n; i++){for (j=0; j<n; j++)if (i+j==n-1)@ a[i][j]=0;}【6，1，3】设n 为正整数，试确定下列各程序段中前置以记号@的语句的频度:(1) i=1; k=0;while (i<=n-1){i++;@ k+=10 * i; // 语句的频度是______________________。

}(2) k=0;for (i=1; i<=n; i++){for (j=i; j<=n; j++)@ k++; // 语句的频度是______________________。

}2【7，3，2】线性表(a1，a2，…，a n)有两种存储结构：顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充：___ 存储密度较大；____存储利用率较高；____可以随机存取；_____不可以随机存取；____插入和删除操作比较方便。

【8，3，2】从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动个元素。

【9，3，2】带头结点的单链表Head为空的条件是____ ______。

【10，3，2】在一个单链表中p所指结点(p所指不是最后结点)之后插入一个由指针s所指结点，应执行s->next=__ ___;和p->next=___ _____的操作。

数据结构与算法在线作业答案55283,单选题655121.邻接表是图的一种____。

A 顺序存储结构B 链式存储结构C 索引存储结构D 散列存储结构6550255281,单选题655022.具有5个顶点的有向完全图有____条弧。

A 10B 16C 20D 256547555245,单选题654753.链表不具有的特点是_____。

A 可随机访问任一元素B 插入和删除不需要移动元素C 不必事先估计存储空间D 所需空间和线性表长度成正比6548555256,单选题654854.作进栈操作时，应先判断栈是否为_____。

A 空B 满C 上溢D 下溢6551555287,单选题655155.下面关于图的存储的叙述中，哪一个是正确的？A 用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关B 用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关C 用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D 用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关6548655261,单选题654866.当字符序列 x5y 作为字符堆栈的输入时，输出长度为3的且可以作为C语言标识符的个数是____。

A 3个B 4个C 5个D 6个6547755253,单选题654777.树最适合用来表示_____。

A 有序数据元素B 无序数据元素C元素之间具有分支层次关系的数据D 元素之间无联系的数据6546055240,单选题654608.线性表按链式方式存储时，每个结点的存储包括_____两部分。

A 数据值与符号B 数据与指针C 数据与表名D 数据项与符号6549855268,单选题654989.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。

这里我们把由树转化得到的二叉树叫做这棵树对应的二叉树。

那么以下结论中_____是正确的。

习 题 11． 简述下列术语：数据 数据元素 数据结构 存储结构 数据类型 抽象数据类型2．在下面两列中，左侧是算法的执行时间，右侧是一些时间复杂度。

请用连线的方式表示每个算法的时间复杂度。

100n 3 (1) (a) O (1) 6n 2-12n +1 (2) (b) O (2n ) 1024 (3) (c) O (n ) n +2log 2n (4) (d) O (n 2) n (n +1)(n +2)/6 (5) (e) O (log 2n ) 2n +1+100n (6)(f) O (n 3)3. 试编写算法，求一元多项式P n (x )=∑=ni ii xa 0的值P n (x 0)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。

注意选择你认为较好的输入和输出方法，本题输入为a i (i=0,1,…,n )，x 0和n ，输出为P n (x 0)。

习 题 21． 填空题：a) 在顺序表中插入和删除一个元素，需要平均移动 表中一半 元素，具体移动的元素个数与 插入或删除元素的位置 有关。

b) 顺序表中逻辑上相邻的元素的物理位置 要求 紧邻。

单链表中逻辑上相邻的元素的物理位置 不要求 紧邻。

c) 在单链表中，除了首结点外，任一结点的存储位置由 前一结点的指针 指示。

d) 在单链表中设置头结点的作用是 储存指向第一个结点的指针 。

2． 已知顺序线性表A 和B 中各存放一个英语单词，字母均为小写。

试编写一个判定那个单词在字典中排在前面的算法。

3．试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1，a2，…, a n）逆置为（a n，a n-1，…，a1）。

4．已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m 和n。

试写一算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。

作业布置作业一第一章1.1 什么是数据对象、数据元素、数据结构？1.2 什么是数据类型？什么是抽象数据类型？1.3 什么是算法？它有哪些特性？它与程序有何区别？1.4 试判定下列计算过程是否为一个算法？1)开始2)n<=03)n=n+14)重复3)5)结束1.5 用图形表示下列数据结构：1) S=(D, R) , D={a,b,c,d,e,f,g} , R={<a,e>, <b,c>, <c,a>, <e,f>, <f,g>}2) S=(D, R) , D={48,25,64,57,82,36,75} , R={R1, R2}R1={<25,36>,<36,48>,<48,57>,<57,64>,<64,75>,<75,82>}R2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<82,75>}1.6 将O(1)、O(n)、O(n2)、O(n3)、O(nlog2n)、O(log2n)、O(2n)按增长率递增排列。

1.7 计算下列算法的时间复杂度：1)x=100; y=0;while(x>=y*y)y=y+2;2)sum(int n){int sum=0,x, j,k;for(j=1; j<=n; j++){x=1;for(k=1; k<=j; k++)p=p*k;sum=sum+p;}return sum;}>> 查看/完成作业：作业一作业二2.1 试编写一个算法，将一个顺序表逆置，并使用最少的辅助存储空间实现。

2.2 试编写一个算法，将两个元素值递减排列的顺序表合并为一个非递增的顺序表。

2.3 试编写一个算法，计算带头结点的循环单链表的长度。

北理工《数据结构与算法》在线作业一、单选题：1.（单选题）设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为() (满分AabedfcBacfebdCaebdfcDaedfcb正确:C2.（单选题）栈的插入和删除操作在()进行。

(满分A栈顶B栈底C任意位置D指定位置正确:A3.（单选题）某二叉树的前序和后序序列正好相同，则该二叉树一定是()的二叉树。

(满分A空或只有一个结点B高度等于其结点数C任一结点无左孩子D任一结点无右孩子正确:A4.（单选题）下列排序算法中，其中()是稳定的。

(满分A堆排序，冒泡排序B快速排序，堆排序C直接选择排序，希尔排序D归并排序，冒泡排序正确:5.（单选题）对于经常要存取线性表任意指定位置元素的应用，线性表应采用()存储结构。

(满分 A顺序存储结构B链式存储结构C线性链表D栈正确:6.（单选题）快速排序属于那种排序类型()。

(满分:)A选择排序B插入排序C交换排序D基数排序正确:7.（单选题）线性链表是通过()方式表示元素之间的关系 (满分:)A后继元素地址B元素的存储顺序C左、右孩子地址D元素的相对存储位置正确:8.（单选题）关键路径是指AOE(ActivityOnEdge)网中()。

(满分:)A最长的回路B最短的回路C从源点到汇点(结束顶点)的最长路径D从源点到汇点(结束顶点)的最短路径正确:A2B3C4D5正确:10.（单选题）下列排序方法中效率最高的排序方法是()。

(满分:)A起泡排序B堆排序C快速排序D直接插入排序正确:11.（单选题）已知A=(a,b),B=(A,A),那么GetHead(GetHead(GetTail(B)))=()。

(满分:)A(a)BACaD(A)正确:12.（单选题）图的存储结构不包括() (满分:)A数组表示B邻接表C邻接多重表D孩子兄弟表示正确:13.（单选题）()是HASH查找的冲突处理方法。