南京晓庄学院大一第二学期计算机数据结构期末考试试卷及答案,南京晓庄学院数据结构题库参考标准答案...

南京晓庄学院数据结构题库参考标准答案

数据结构与算法 习题册 (课后部分参考答案) 《数据结构与算法》课程组 目录 课后习题部分 第一章 绪论1 第二章 线性表3 第三章 栈和队列5 第四章 串8 第五章 数组和广义表10 第六章 树和二叉树13 第七章 图16 第九章 查找20 第十章 排序23 第一章 绪论 一. 填空题 1. 从逻辑关系上讲，数据结构的类型主要分为 集合 、线性结构、树结构和 图结构。 2. 数据的存储结构主要有 顺序存储和 链式存储 两种基本方法，不论哪种存储结构，都要存储两方面的内容：数据元素 和 数据元素之间的关系 。 3. 算法具有五个特性，分别是 有穷性 、 确定性、可行性、 输入 、 输出 。 4. 算法设计要求中的健壮性指的是 算法在发生非法操作时可以作出处理的特性。 二. 选择题 1. 顺序存储结构中数据元素之间的逻辑关系是由 C 表示的，链接存储结构中的数据元素之间的逻辑关系是由 D 表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 2. 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是 B 。 A 树 B 图 C 线性表 D 集合 3. 算法指的是 A 。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 三. 简答题 1. 分析以下各程序段，并用大O记号表示其执行时间。 (1) (2) i=1;k=0;i=1;k=0; While(inext; rear->next =s; rear =s;；删除开始结点的操作顺序为q=rear->next->next; rear->next->next=q->next; delete q; 。 二. 选择题 1.数据在计算机存储器内表示时物理地址与逻辑地址相同并且是连续的，称之为： C A存储结构 B逻辑结构 C顺序存储结构 D链式存储结构 2. 在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是： A A 访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n) B 在第i个结点后插入一个新结点(1≤i≤n) C 删除第i个结点(1≤i≤n) D 将n个结点从小到大排序 3. 线性表L在 B 情况下适用于使用链式结构实现。 A 需经常修改L中的结点值 B 需不断对L进行删除插入 C L中含有大量的结点 D L中结点结构复杂 4. 单链表的存储密度 C A大于1 B等于1 C小于1 D不能确定 三. 判断题 1. 线性表的逻辑顺序和存储顺序总是一致的。 F 2. 线性表的顺序存储结构优于链接存储结构。 F 3. 设p，q是指针，若p=q，则*p=*q。 F 4. 线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。 F 四. 简答题 1. 分析下列情况下，采用何种存储结构更好些。 (1)若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。 (2)如果n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。 (3)描述一个城市的设计和规划。 ⑴ 应选用顺序存储结构。很少进行插入和删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储结构。 ⑵ 应选用链式存储结构。链表容易实现表容量的扩充，适合表的长度动态发生变化。 ⑶ 应选用链式存储结构。因为一个城市的设计和规划涉及活动很多，需要经常修改、扩充和删除各种信息，才能适应不断发展的需要。而顺序表的插入、删除的效率低，故不合适。 五. 算法设计 1. 已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O(n)。 2. 线性表存放在整型数组A[arrsize]的前elenum 个单元中，且递增有序。编写算法，将元素x插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。 int insert (datatype A[],int *elenum,datatype x) /*设elenum为表的最大下标*/ {if (*elenum==arrsize-1) return 0; /*表已满，无法插入*/ else {i=*elenum; while (i>=0 i--; } A

总结

以上是生活随笔为你收集整理的南京晓庄学院大一第二学期计算机数据结构期末考试试卷及答案,南京晓庄学院数据结构题库参考标准答案...的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。