数据结构形考任务2答案

1.数据结构形考选择题

2.把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（ B ）。

a)A．逻辑结构 B．物理结构

b)C．算法的具体实现 D．给相关变量分配存储单元

3.下列说法中，不正确的是（ D ）。

A．数据元素是数据的基本单位

B．数据项是数据中不可分割的最小可标识单位

C．数据可有若干个数据元素构成

D．数据项可由若干个数据元素构成

4.一个存储结点存储一个（ B ）。

a)A．数据项 B．数据元素

b)C．数据结构 D．数据类型

5.数据结构中，与所使用的计算机无关的是数据的（ C ）。

a)A．存储结构 B．物理结构

b)C．逻辑结构 D．物理和存储结构

6.下列的叙述中，不属于算法特性的是（D ）。

a)A．有穷性 B．输入性

b)C．可行性 D．可读性

7.算法分析的目的是（C ）。

a)A．找出数据结构的合理性 B．研究算法中的输入和输出的关系

b)C．分析算法的效率以求改进 D．分析算法的易懂性和文档性

8.

第二学期“数据结构”考试试题（A）

姓名

学号(序号)_ 班号

要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。

一、单项选择题（每小题2分，共20分）

1．数据的运算a 。

A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 2. 链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 3. 在顺序表中删除一个元素的时间复杂度为 c 。

A.O(1) B.O(log2n) C.O(n) D.O(n2)

4．以下线性表的存储结构中具有随机存取功能的是 d 。 A. 不带头结点的单链表 B. 带头结点的单链表 C. 循环双链表 D. 顺序表 。

5. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。 A.edcba

第二学期“数据结构”考试试题（A）

姓名

学号(序号)_ 班号

要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。

一、单项选择题（每小题2分，共20分）

1．数据的运算a 。

A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 2. 链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 3. 在顺序表中删除一个元素的时间复杂度为 c 。

A.O(1) B.O(log2n) C.O(n) D.O(n2)

4．以下线性表的存储结构中具有随机存取功能的是 d 。 A. 不带头结点的单链表 B. 带头结点的单链表 C. 循环双链表 D. 顺序表 。

5. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。 A.edcba

一、绪论

a) 何谓程序设计？

程序=算法+数据结构 b) 数据结构的定义

是相互之间存在一种或多种特定关系的数据元素的集合 c) 数据、数据元素、数据对象的概念

数据：是对客观事物的符号表示 数据元素：是数据的基本单位

数据对象：是性质相同的数据元素的集合 d) 四种基本的数据结构类型

集合结构、线性结构、树型结构、图形结构 e) 两种存储结构（计算机中的实现方式）

顺序存储结构

特点：随机访问

优缺点：存取快，但插入元素复杂 适用情况：插入元素操作较多的情况 链式存储结构

特点：顺序访问

优缺点：访问元素麻烦，但是插入元素方便

适用情况：插入元素为主要操作而访问元素的操作较少

f) 数据类型、抽象数据类型

数据类型：用以刻画（程序）操作对象的特性

抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作 g) 抽象数据类型的意义

ADT（abstract data type）着重数据结构的操作接口，不关心具体实现，主要是面向用户

ADT是数据结构设计所追求的目标 h) 何谓算法

算法是解决特定问题求解步骤的描述 i) 算法特征

①有穷性 ②确定性 ③可行性 ④输入 ⑤输出 j) 算法设计的要求

①正确性 ②可读性 ③健壮性 ④效率与低

数据结构练习（二）答案

一、填空题：

1．若一棵树的括号表示为A（B（E，F），C（G（H,I,J,K）,L）,D（M（N））），则该树的度为 （1）4 ，树的深度为 （2）4 ，树中叶子结点的个数为（3）8。 2．一棵满二叉树中有m个叶子，n个结点，深度为h，请写出m、n、h之间

hh-1

关系的表达式 （4）n=2-1,m=n+1-2 n=2m-1 。

3．一棵二叉树中如果有n个叶子结点，则这棵树上最少有（5）2n-1 个结点。

k-1k

一棵深度为k的完全二叉树中最少有 2（6） 个结点，最多有（7）2-1 个结点。

4．具有n个结点的二叉树，当它是一棵 (8)完全 二叉树时具有最小高度 （9）?log2n」+1 ，当它为一棵单支树时具有高度 (10) n 。 5．对具有n个结点的完全二叉树按照层次从上到下，每一层从左到右的次序对

所有结点进行编号，编号为i的结点的双亲结点的编号为_(11)__[i/2]__，左孩子的编号为___2i____，右孩子的编号为__2i+1______。

6．若具有n个结点的二叉树采用二叉链表存储结构，则该链表中有__2n_个指

针域，其中有_n-1_个指针域用于链接孩子结点，__n+1_个指针域

第1章 绪论

习题

1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现？ 5．选择题

（1）在数据结构中，从逻辑上可以把数据结构分成（ ）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构

（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。 A．存储结构 B．存储实现 C．逻辑结构 D．运算实现

（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。 A．数据具有同一特点

B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样

D．数据元素所包含的数据项的个数要相等 （4）以下说法正确的是（ ）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位

C．数据结构是带有结构的各数据项的集合

D．一些表面上很

数据结构试卷（二）

一、选择题(24分)

1．下面关于线性表的叙述错误的是（ ）。

(A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现

2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。 (A) 2m-1 (B)2m (C)2m+1 (D)4m

3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）。 (A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M

4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ ）。 (A) BADC (B)BCDA (C) CDAB (D) CBDA 5．设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边。 (A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1

邵阳学院课程设计（论文）任务书

年级专业 题目名称 课程名称 数据结构课程设计 2010级网络工程 课程编号 131301302 学生姓名 学 号 设计时间 设计地点 2011.12.12-12.25 新实验楼四楼机房 一、课程设计（论文）目的 学生在教师指导下运用所学课程的知识来研究、解决一些具有一定综合性问题的专业课题。通过课程设计（论文），提高学生综合运用所学知识来解决实际问题、使用文献资料、及进行科学实验或技术设计的初步能力，为毕业设计（论文）打基础。 二、已知技术参数和条件 三、任务和要求 注：1．此表由指导教师填写，经系、教研室审批，指导教师、学生签字后生效； 2．此表1式3份，学生、指导教师、教研室各1份。

四、参考资料和现有基础条件（包括实验室、主要仪器设备等） 五、进度安排 2011.12.5—2011.12.6：课程设计选题 2011.12.7—2011.12.8：下发任务书 2011.12.9—2011.12.12：搜集相关参考资料 2011.12.13—2011.12.19：编程 2011.12.20—2011.12.25：撰写课程设计报告 六、教研室审批意见 教研室主任（签字）：

邵阳学院课程设计（论文）任务书

年级专业 题目名称 课程名称 数据结构课程设计 2010级网络工程 课程编号 131301302 学生姓名 学 号 设计时间 设计地点 2011.12.12-12.25 新实验楼四楼机房 一、课程设计（论文）目的 学生在教师指导下运用所学课程的知识来研究、解决一些具有一定综合性问题的专业课题。通过课程设计（论文），提高学生综合运用所学知识来解决实际问题、使用文献资料、及进行科学实验或技术设计的初步能力，为毕业设计（论文）打基础。 二、已知技术参数和条件 三、任务和要求 注：1．此表由指导教师填写，经系、教研室审批，指导教师、学生签字后生效； 2．此表1式3份，学生、指导教师、教研室各1份。

四、参考资料和现有基础条件（包括实验室、主要仪器设备等） 五、进度安排 2011.12.5—2011.12.6：课程设计选题 2011.12.7—2011.12.8：下发任务书 2011.12.9—2011.12.12：搜集相关参考资料 2011.12.13—2011.12.19：编程 2011.12.20—2011.12.25：撰写课程设计报告 六、教研室审批意见 教研室主任（签字）：

数据结构综合实验任务书

本次课程设计安排在第19周，教师提供了26道选题，按照题目的难易程序度分为一类、二类及三类，一类选题9个，难度稍高，二类选题5个，难度中等，三类选题12个，难度较低。根据自身情况选题，必须保证自己完成。自选题必须事先由教师看过并同意才可以做。选题原则上一人一组形式进行。

课程设计按照软件工程的步骤进行，先写出需求分析，再进行概要设计和详细。基本要求是给出题中所涉及的数据的逻辑结构、存储结构、算法核心设计流程、输入输出、源程序、测试数据及结果，并在总结部分给出设计及实现过程中出现的问题及解决思路，探讨算法的改进方法。系统实现在Visual C++控制台环境下实现，要求有简单界面的设计，课程设计最后以设计报告及软件形式提交，设计报告按照指导书的要求编写。

课程设计从学习态度、程序运行及答辩情况、文档写作情况分项打分，学习态度包括考勤及投入情况，程序运行考查编码的独立完成情况、程序的执行情况及工作量大小，文档的写作包括需求分析文档的写作，概要设计和详细设计情况以及数据结构的定义情况等等。

课程设计第一天，必须写出需求分析和概要设计。

课程设计任务书

一类题（9个）： NO. 1

１、题目：工程求解 ２、设计内容及要求： 内容：一个工