南京晓庄学院数据构造题库参考答案 - 数据构造与算法 习题册 〔课后局部参考答案〕 《数据构造与算法》课程组目录 目录 课后习题局部 第一章绪论 ......................................................................................................... 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. 分析^p 以下各程序段，并用大O记号表示其执行时间 (1)(2) i=1;k=0; do i=1;k=0; {{ k=k+10*i; k=k+10*i; i++; i++; } ⑴根本语句是k=k+10*i，共执行了n-2次，所以T(n)=O(n)。
⑵根本语句是k=k+10*i，共执行了n次，所以T(n)=O(n) While(inext =rear->next; 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进展删除插入 CL中含有大量的结点D L中结点构造复杂 4.单链表的存储密度C A大于1 B等于1 C小于1 D不能确定 三. 判断题 1. 线性表的逻辑顺序和存储顺序总是一致的。
F 2. 线性表的顺序存储构造优于链接存储构造F 3. 设p，q是指针，假设p=q，那么*p=*qF 4. 线性构造的根本特征是：每个元素有且仅有一个直接前驱和一个直接后继F 四. 简答题 1. 分析^p 以下情况下，采用何种存储构造更好些 (1)假设线性表的总长度根本稳定，且很少进展插入和删除操作，但要求以最快的速度存取线性表中的元素 (2)假如n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化 (3)描绘一个城市的设计和规划 3 第 6 页 共 6 页。