2020年电大考试《数据结构》形成性考核

一、单项选择题（每小题2分，共40分）题目1答案已保存满分2.00标记题目题干对线性表进行二分查找时，要求线性表必须（）。

选择一项：A. 以链接存储方式B. 以顺序存储方式，且数据元素有序C. 以链接存储方式，且数据元素有序D. 以顺序存储方式题目2答案已保存满分2.00标记题目题干采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。

选择一项：A. (n-1)/2B. (n+1)/2C. nD. n/2题目3答案已保存满分2.00标记题目题干有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。

选择一项：A. 29/10B. 26/10C. 31/10D. 29/9题目4答案已保存满分2.00标记题目题干已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较（）次。

选择一项：A. 3B. 5C. 6D. 4题目5答案已保存满分2.00标记题目题干有数据{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（）。

选择一项：A. 37,24,12,30,53,45,96B. 45,24,53,12,37,96,30C. 12,24,30,37,45,53,96D. 30,24,12,37,45,96,53题目6答案已保存。

数据结构（本）形成性考核作业册使用说明本作业册是电视大学计算机科与技术专业（本科）数据结构（本）课程形成性考核的依据，与《数据结构（本科）》教材配套使用。

数据结构（本）课程是电视大学计算机科学技术专业的一门统设必修、学位课程，4学分，共72学时。

其中实验24学时，开设一学期。

本课程的特点是综合性、实践性强，内容抽象，在专业中具有承上启下的作用。

因此，在学习本课程时，要注意理论联系实际，结合教学内容进行上机实践，认真完成作业和实验内容。

本课程的总成绩按百分制记分，其中形成性考核所占的比例为30%，终结性考试占70％（闭卷，答题时限为90分钟）。

课程总成绩达到60分及以上者为合格，可以获得该课程的学分。

本课程的学位课程学分为70分，即课程总成绩达到70分及以上者有资格申请专业学位。

本课程共设计了4次形考作业，每次形考作业均包括实验内容，由各地电大根据学生对作业中各种题型练习和实验的完成情况进行考核。

对于实验内容要求按实验要求认真完成，并提交实验报告。

数据结构（本）课程作业作业1（本部分作业覆盖教材第1-2章的内容）一、单项选择题1．在数据结构中，从逻辑上可以把数据结构分为（）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部机构2．下列说法中，不正确的是（）。

A．数据元素是数据的基本单位B．数据项是数据中不可分割的最小可标识单位C．数据可有若干个数据元素构成D．数据项可由若干个数据元素构成3．一个存储结点存储一个（）。

A．数据项B．数据元素C．数据结构D．数据类型4．数据结构中，与所使用的计算机无关的是数据的（）。

A．存储结构B．物理结构C．逻辑结构D．物理和存储结构5．下列的叙述中，不属于算法特性的是（）。

A．有穷性B．输入性C．可行性D．可读性6．算法分析的目的是（）。

A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和文档性7．数据结构是一门研究计算机中（）对象及其关系的科学。

国家开放大学电大《数据结构》网络课形考任务3作业及答案形考任务3一、单项选择题（每小题2分，共38分）题目1假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）。

选择一项：B. 16题目2二叉树第k层上最多有（）个结点。

选择一项：A. 2k-1题目3将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（）。

选择一项：C. 34题目4如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）。

选择一项：B. 哈夫曼树题目5在一棵度具有5层的满二叉树中结点总数为（）。

选择一项：C. 31题目6一棵完全二叉树共有6层，且第6层上有6个结点，该树共有（）个结点。

选择一项：B. 37题目7利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子结点中的最长带权路径长度为（）。

选择一项：A. 18在一棵树中，（）没有前驱结点。

选择一项：A. 树根结点题目9设一棵采用链式存储的二叉树，除叶结点外每个结点度数都为2，该树结点中共有20个指针域为空,则该树有（）个叶结点。

选择一项：B. 10题目10在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。

选择一项：A. 2题目11邻接表是图的一种（）。

选择一项：A. 链式存储结构题目12图的深度优先遍历算法类似于二叉树的（）遍历。

选择一项：A. 先序题目13已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。

选择一项：D. V1V2V4V8V5V3V6V7题目14已知如下图所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。

选择一项：D. aecbdf题目15图状结构中数据元素的位置之间存在（）的关系。

选择一项：B. 多对多在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（）。

数据结构（本）期末综合练习国家开放大学2020年7月《1252本科数据结构（本）》期末考试复习题及答案一、单项选择题1．数据的物理结构（ D）。

A．与数据的逻辑结构无关 B．仅仅包括数据元素的表示C．只包括数据元素间关系的表示 D．包括数据元素的表示和关系的表示2．数据元素是数据的基本单位，它（C ）。

A．只能有一个数据项组成B．至少有二个数据项组成C．可以是一个数据项也可以由若干个数据项组成D．至少有一个数据项为指针类型3．从n个数中选取最大元素，（ C ）。

A．基本操作是数据元素间的交换B．算法的时间复杂度是O(n2)C．算法的时间复杂度是O(n) D．需要进行(n+1)次数据元素间的比较4．线性表的顺序结构中，（ C ）。

A．逻辑上相邻的元素在物理位置上不一定相邻B．数据元素是不能随机访问的C．逻辑上相邻的元素在物理位置上也相邻D．进行数据元素的插入、删除效率较高5．以下表中可以随机访问的是（ D ）。

A．单向链表 B．双向链表C．单向循环链表D．顺序表6．带头结点的单向链表为空的判断条件是（ B ）（设头指针为head）。

A．head = =NULL B．head->next= =NULLC．head->next= =head D．head!=NULL7 .设顺序存储的线性表长度为n，对于删除操作，设删除位置是等概率的，则删除一个元素平均移动元素的次数为（ A ）。

A．(n+1)/2 B．n C．2n D．n-i8．线性结构中数据元素的位置之间存在（A ）的关系。

A．一对一B．一对多C．多对多D．每一个元素都有一个直接前驱和一个直接后继9．设top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成，设用x接收栈顶元素，则出栈操作为（A ）。

A．x=top->data;top=top->next; B．top=top->next;x=top->data;C．x=top-> next;top=top-> data; D．top->next =top; x=top->data;10．设顺序存储的线性表长度为n，要删除第i个元素，按课本的算法，当i=（ C ）时，移动元素的次数为3 A．3 B．n/2 C．n-3 D．411．以下说法正确的是（ C ）。

数据结构课程平时作业1一. 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科。

①A. 操作对象 B. 计算方法 C. 逻辑存储 D. 数据映象②A. 结构 B. 关系 C. 运算 D. 算法2．数据结构被形式地定义为（K, R）, 其中K是①的有限集合, R是K上的②的有限集合。

①A. 算法 B. 数据元素 C. 数据操作 D. 逻辑结构3．②A. 操作 B. 映象 C. 存储 D. 关系A．在数据结构中, 从逻辑上可以把数据结构分成( )。

动态结构和静态结构 B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构D. 内部结构和外部结构4.线性结构是数据元素之间存在一种：A）一对多关系B）多对多关系C）多对一关系D）一对一关系5.数据结构中, 与所使用的计算机无关的是数据的结构；A) 存储B) 物理C) 逻辑D) 物理和存储二.填空题（将正确的答案填在相应的空中）1. 在线性结构中, 第一个结点①前驱结点, 其余每个结点有且只有②个前驱结点；最后一个结点③后续结点, 其余每个结点有且只有④个后续结点。

2. 在树形结构中, 树根结点没有①结点, 其余每个结点有且只有②个前驱结点；叶子结点没有③结点, 其余每个结点的后续结点可以④。

3. 在图形结构中, 每个结点的前驱结点数和后续结点数可以①。

4．线性结构中元素之间存在①关系, 树形结构中元素之间存在②关系, 图形结构中元素之间存在③关系。

5.数据结构包括数据的、数据的和数据的这三个方面的内容。

6. 下面程序段的时间复杂度是①。

for（i=0；i＜n；i++）for（j=0；j＜m；j++）A[i][j]=0；7. 下面程序段的时间复杂度是①。

S＝0；for（i=0；i<n；i++）for（j=0; j<n; j++）s+=b[i][j]；sum=s;三、简答题1.数据结构是一门研究什么内容的学科？2.数据元素之间的关系在计算机中有几种表示方法？各有什么特点？3.设有数据逻辑结构S=（D,R）, 试按题所给条件画出这些逻辑结构的图示, 并确定相对于关系R, 哪些结点是开始结点, 哪些结点是终端结点？D={d1,d2,d3,d4}R={(d1,d2),(d2,d3),(d3,d4) }部分参考答案一、单选题二、A B 2. B D 3. C 4. D 5. C三、填空题1.无, 1, 无, 12.前驱, 1个, 后继, 多个3.多个4.一对一, 一对多, 多对多5.逻辑结构、物理结构、数据运算6. O(n*m)7. O(n*n)三、简答题1.略见课件2.略3. d1( d2(d3(d4 线性结构数据结构课程平时作业2一. 单项选择题1.线性表L=（a1, a2,…,a n）,下列说法正确的是（）。

数据结构形考3_0001
四大形成性测评系统课程代码：5110025 答案资料
、单项选择题（共 15 道试题，共 60 分。

）
1. 二叉树第k层上最多有（）个结点。

A. 2k
B. 2k-1
C. 2k-1
D. 2k-1
-正确答案-：B
2. 二叉树的深度为k,则二叉树最多有（）个结点。

A. 2k
B. 2k-1
C. 2k-1
D. 2k-1
-正确答案-：D
3. 在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（）邻接点。

A. 入边
B. 出边
C. 入边和出边
D. 不是入边也不是出边
-正确答案-：B
4. 假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）。

A. 15
B. 16
C. 17
D. 47
-正确答案-：B
5. 设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（）个结点。

A. 2n
B. 2n-1
C.
2n+1
D. 2n+2
-正确答案-：B
6. 将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（）。

A. 33
B. 34
C. 35
D. 36
-正确答案-：B
7. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（）。

国开02272《数据结构》形成性考核(1-4)试题及解答1. 选择题问题 1.1:在数据结构中，以下哪种结构是最基本的数据结构？- A. 栈- B. 队列- C. 树- D. 图解答 1.1:正确答案是 A. 栈。

栈是一种后进先出（LIFO）的数据结构，它是通过在一端进行插入和删除操作来实现的。

问题 1.2:在二叉树中，一个节点的最大孩子数目是？- A. 1- B. 2- C. 3- D. 无穷大解答 1.2:正确答案是 B. 2。

在二叉树中，每个节点最多有两个子节点，即左子节点和右子节点。

2. 填空题问题 2.1:在线性表中，如果一个元素在表中的位置是 i，那么它之前有 i - 1 个元素。

_____解答 2.1:正确答案是 "正确"。

在线性表中，如果一个元素在表中的位置是 i，那么它之前有 i - 1 个元素，因为它是从位置 1 开始计数的。

问题2.2:在_____结构中，删除操作的平均时间复杂度是O(n)。

_____解答 2.2:正确答案是 "链表" 和 "O(n)"。

在链表结构中，删除操作的平均时间复杂度是 O(n)，因为需要找到要删除的元素的前一个元素来进行删除操作。

3. 简答题问题 3.1:请解释什么是深度优先搜索（DFS）算法，并给出一个应用场景。

解答 3.1:深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。

它从根节点开始，沿着树的深度遍历树的节点，尽可能深地搜索树的分支。

当节点v的所有边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。

它适用于解决迷宫问题、求解最大子矩阵问题等。

问题 3.2:请解释什么是堆，并给出两种类型的堆。

解答 3.2:堆是一种特殊的完全二叉树，用于实现优先队列。

堆分为两种类型：最大堆和最小堆。

- 最大堆：在一个最大堆中，每个节点的值都大于或等于其子节点的值。

最大堆的根节点具有最大值。

电大数据结构形成性考核册（DOC 34页）数据结构（本）形成性考核作业册使用说明本作业册是中央广播电视大学计算机科与技术专业（本科）数据结构（本）课程形成性考核的依据，与《数据结构（本科）》教材（李伟生主编，中央电大出版社出版）配套使用。

数据结构（本）课程是中央广播电视大学计算机科学技术专业的一门统设必修、学位课程，4学分，共72学时。

其中实验24学时，开设一学期。

本课程的特点是综合性、实践性强，内容抽象，在专业中具有承上启下的作用。

因此，在学习本课程时，要注意理论联系实际，结合教学内容进行上机实践，认真完成作业和实验内容。

本课程的总成绩按百分制记分，其中形成性考核所占的比例为30%，终结性考试占70％（闭卷，答题时限为90分钟）。

课程总成绩达到60分及以上者为合格，可以获得该课程的学分。

本课程的学位课程学分为70分，即课程总成绩达到70分及以上者有资格申请专业学位。

本课程共设计了4次形考作业，每次形考作1．在数据结构中，从逻辑上可以把数据结构分为（）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部机构2．下列说法中，不正确的是（）。

A．数据元素是数据的基本单位B．数据项是数据中不可分割的最小可标识单位C．数据可有若干个数据元素构成D．数据项可由若干个数据元素构成3．一个存储结点存储一个（）。

A．数据项B．数据元素C．数据结构D．数据类型4．数据结构中，与所使用的计算机无关的是数据的（）。

A．存储结构B．物理结构C．逻辑结构D．物理和存储结构5．下列的叙述中，不属于算法特性的是（）。

A．有穷性B．输入性C．可行性D．可读性6．算法分析的目的是（）。

A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和文档性7．数据结构是一门研究计算机中（）对象及其关系的科学。

A．数值运算B．非数值运算C．集合D．非集合8．算法的时间复杂度与（）有关。

一、单项选择题（每小题2分，共40分）题目1答案已保存满分2.00标记题目题干对线性表进行二分查找时，要求线性表必须（）。

选择一项：A. 以链接存储方式B. 以顺序存储方式，且数据元素有序C. 以链接存储方式，且数据元素有序D. 以顺序存储方式题目2答案已保存满分2.00标记题目题干采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。

选择一项：A. (n-1)/2B. (n+1)/2C. nD. n/2题目3答案已保存满分2.00标记题目题干有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。

选择一项：A. 29/10B. 26/10C. 31/10D. 29/9题目4答案已保存满分2.00标记题目题干已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较（）次。

选择一项：A. 3B. 5C. 6D. 4题目5答案已保存满分2.00标记题目题干有数据{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（）。

选择一项：A. 37,24,12,30,53,45,96B. 45,24,53,12,37,96,30C. 12,24,30,37,45,53,96D. 30,24,12,37,45,96,53题目6答案已保存满分2.00标记题目题干对于顺序存储的有序表{5,12,20,26,37,42,46,50,64}，若采用折半查找，则查找元素26的比较次数是（）。

选择一项：A. 3B. 4C. 5D. 6题目7答案已保存满分2.00标记题目题干在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（）。

选择一项：A. 希尔排序B. 直接选择排序C. 直接插入排序题目8答案已保存满分2.00标记题目题干从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。

一、单项选择题1．数据的物理结构（D ）。

A．与数据的逻辑结构无关 B．仅仅包括数据元素的表示C．只包括数据元素间关系的表示 D．包括数据元素的表示和关系的表示2．数据元素是数据的基本单位，它（C ）。

A．只能有一个数据项组成B．至少有二个数据项组成C．可以是一个数据项也可以由若干个数据项组成D．至少有一个数据项为指针类型3．从n个数中选取最大元素，（C ）。

A．基本操作是数据元素间的交换B．算法的时间复杂度是O(n2)C．算法的时间复杂度是O(n) D．需要进行(n+1)次数据元素间的比较4．线性表的顺序结构中，（C ）。

A．逻辑上相邻的元素在物理位置上不一定相邻B．数据元素是不能随机访问的C．逻辑上相邻的元素在物理位置上也相邻D．进行数据元素的插入、删除效率较高5．以下表中可以随机访问的是（D ）。

A．单向链表 B．双向链表C．单向循环链表D．顺序表6．带头结点的单向链表为空的判断条件是（B ）（设头指针为head）。

A．head = =NULL B．head->next= =NULL C．head->next= =head D．head!=NULL 7 .设顺序存储的线性表长度为n，对于删除操作，设删除位置是等概率的，则删除一个元素平均移动元素的次数为（ A ）。

A．(n+1)/2 B．n C．2n D．n-i8．线性结构中数据元素的位置之间存在（A）的关系。

A．一对一B．一对多C．多对多D．每一个元素都有一个直接前驱和一个直接后继9．设top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成，设用x接收栈顶元素，则出栈操作为（A ）。

A．x=top->data;top=top->next; B．top=top->next;x=top->data;C．x=top-> next;top=top-> data; D．top->next =top; x=top->data;10．设顺序存储的线性表长度为n，要删除第i个元素，按课本的算法，当i=（C）时，移动元素的次数为3A．3 B．n/2 C．n-3 D．411．以下说法正确的是（C ）。

中央电大本科数据结构形成性考核册实验报告实验名称：实验一线性表线性表的链式存储结构【问题描述】某项比赛中，评委们给某参赛者的评分信息存储在一个带头结点的单向链表中，编写程序：（1）显示在评分中给出最高分和最低分的评委的有关信息（、年龄、所给分数等）。

（2）在链表中删除一个最高分和一个最低分的结点。

（3）计算该参赛者去掉一个最高分和一个最低分后的平均成绩。

【基本要求】（1）建立一个评委打分的单向链表；（2）显示删除相关结点后的链表信息。

（3）显示要求的结果。

【实验步骤】（1）运行PC中的Microsoft Visual C++ 6.0 程序，（2）点击“文件”→“新建” →对话窗口中“文件” →“c++ Source File ” →在“文件名”中输入“X1.cpp ” →在“位置”中选择储存路径为“桌面” →“确定”，（3）输入程序代码，程序代码如下:#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <iostream.h>#include <conio.h>#define NULL 0#define PWRS 5 // 定义评委人数struct pw // 定义评委信息{ char name[6];float score;int age;};typedef struct pw PW;struct node // 定义链表结点{struct pw data;struct node * next;};typedef struct node NODE;NODE *create（int m）; // 创建单链表int calc（NODE *h）; // 计算、数据处理head=create(PWRS);printf(" 所有评委打分信息如下 :\n");print(head);// 显示当前评委打分calc(head);// 计算成绩printf(" 该选手去掉 1 最高分和 1 最低分后的有效评委成绩 :\n"); print(head);// 显示去掉极限分后的评委打分 }void input(NODE *s){printf(" 请输入评委的 : "); scanf("%S",&s->);printf(" 年龄 : ");scanf("%d",&s->data.age); printf("打分 : "); scanf("%f",&s->data.score);printf("\n");}void output(NODE *s){printf(" 评委 : %8s , 年龄 : %d, 打分 : %2.2f\n",s->,s->data.age,s->data.score); } NODE *create(int m){NODE *head,*p,*q;int i;p=(NODE*)malloc(sizeof(NODE));head=p;q=p;p->next=NULL;for(i=1;i<=m;i++){ p=(NODE*)malloc(sizeof(NODE)); input(p);p->next=NULL;q->next=p;q=p;}return (head);}void print(NODE *h){ for(int i=1;((i<=PWRS)&&(h->next!=NULL));i++){h=h->next;output(h); }printf("\n");void print(NODE *h); //void input(NODE *s);//void output(NODE *s);//void main(){ NODE *head;float ave=0;float sum=0;输出所有评委打分数据 输入评委打分数据}int calc(NODE *h){NODE *q,*p,*pmin,*pmax;float sum=0;float ave=0;p=h->next; // 指向首元结点pmin=pmax=p; // 设置初始值sum+=p->data.score;p=p->next;for(;p!=NULL;p=p->next){ if(p->data.score>pmax->data.score) pmax=p; if(p->data.score<pmin->data.score) pmin=p;sum+=p->data.score;}cout<<" 给出最高分的评委："<<pmax-><<" 年龄："<<pmax->data.age<<" 分值："<<pmax->data.score<<endl;cout<<" 给出最低分的评委："<<pmin-><<" 年龄："<<pmin->data.age<<" 分值："<<pmin->data.score<<endl;printf("\n");sum-=pmin->data.score;sum-=pmax->data.score;for (q=h,p=h->next;p!=NULL;q=p,p=p->next){if(p==pmin){q->next=p->next; p=q;}// 删除最低分结点if(p==pmax) {q->next=p->next; p=q;}// 删除最高分结点}ave=sum/(PWRS-2);cout<<" 该选手的最后得分是："<<ave<<endl;return 1;}程序运行结果如下:线性表的顺序存储结构问题描述】用顺序表 A 记录学生的信息，编写程序：（1）将A表分解成两个顺序表 B 和C，使C表中含原A表中性别为男性的学生， B 表中含原表中性别为女性的学生，要求学生的次序与原 A 表中相同。

电大数据结构形成性考核册1.知识点总结：学员需要对所学的数据结构课程内容进行总结，包括数据结构的基本概念、常见数据结构的特点和应用、数据结构与算法的关系等。

学员可以参考课本、笔记、课程讲义等资料，用自己的话进行概括和总结。

2.算法分析：学员需要选择一个或多个常见的算法，并分析其时间复杂度和空间复杂度。

学员可以选择一些简单的算法，如线性查找、二分查找、选择排序等，或者稍微复杂一些的算法，如快速排序、堆排序等。

对于每个算法，学员需要深入理解其原理，并计算出相应的时间复杂度和空间复杂度。

3. 代码实现：学员需要选择一个或多个数据结构，并使用编程语言（如C/C++、Java等）实现该数据结构的基本操作。

学员可以选择栈、队列、链表、二叉树等常见的数据结构，这些数据结构的实现可以包括插入、删除、查找、遍历等基本操作。

4.综合应用：学员需要选择一个实际问题，并结合所学的数据结构知识，设计并实现一个解决方案。

例如，可以选择一个图论问题，通过使用图的数据结构和相关算法，解决一些实际场景中的路径规划或最短路径等问题。

或者选择一个字符串处理问题，通过使用字符串的相关数据结构和算法，解决一些实际场景中的文本处理或模式匹配等问题。

5.思考题和实验总结：学员需要回答一些与数据结构相关的思考题，并进行实验总结。

思考题可以包括理论问题、算法问题或应用问题，要求学员深入分析和思考，并给出合理的解答。

实验总结要求学员描述自己在实际操作中的体会和心得，从中总结出学习到的经验和教训。

总之，在电大数据结构形成性考核册中，学员需要综合运用所学的数据结构知识，展示自己的理解和应用能力。

这不仅是对学员学习成果的一种检验，也是对学员解决实际问题能力的一种培养和锻炼。

通过完成这份考核作业，学员可以更深入地理解和掌握数据结构知识，为日后的学习和工作打下坚实的基础。

准答案1：物理结构
标准答案2：数据项可由若干个数据元素构成
标准答案3：数据元素
标准答案4：逻辑结构
标准答案5：逻辑上相邻的元素在物理位置上也相邻
标准答案6：不能随机访问任一结点
标准答案7：可读性
标准答案8：算法本身
标准答案9：n-i+1
标准答案10：n-i
标准答案11：p->next=q->next
标准答案12：s->next=p->next; p->next=s;
标准答案13：p->next==head
标准答案14：可随机访问任一元素
标准答案15：head->next==NULL
标准答案16：20
标准答案17：除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继
标准答案18：63.5
标准答案19：100
标准答案20：q->next=p
标准答案21：对
标准答案22：错
标准答案23：错
标准答案24：错
标准答案25：错
标准答案26：错
标准答案27：错
标准答案28：对
标准答案29：对
标准答案30：对
标准答案31：错
标准答案32：对
标准答案33：对
标准答案34：对
标准答案35：{p->data} {p=p->next} {p!=NULL}
标准答案36：{q->next!=NULL} {p=p->next} {q->next=s}。

数据结构形考2_0004四大形成性测评系统课程代码：5110025 答案资料、单项选择题（共 15 道试题，共 60 分。

）1. 如果以链表作为栈的存储结构，则退栈操作时（）。

A. 必须判断栈是否满B. 判断栈元素类型C. 必须判断栈是否空D. 对栈不作任何判断-正确答案-：C2. 对一个栈顶指针为top的链栈进行进栈操作，设P指向待进栈的结点，则执行（）。

A. p=top->next; top=topànext;B. p->next=top; p=top;C. p->next=top;top=p;D. top=p;-正确答案-：C3.设有一个15阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a7,3在一维数组B中的下标是（）。

(矩阵中的第1个元素是a1,1 ）A. 33B. 24C. 25D. 26-正确答案-：B4. 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为( )。

A. n-2B. n-1C. nD. n+1-正确答案-：B5. 串的长度是指（）。

A. 串中所含不同字母的个数B. 串中所含字符的个数C. 串中所含不同字符的个数D. 串中所含非空格字符的个数-正确答案-：B6. 在一个顺序存储的循环队列中，队头指针指向队头元素的( )位置。

A. 前一个B. 后一个C. 当前D. 后面-正确答案-：A7. 判断一个顺序队列sq（最多元素为m0）为空的条件是（）。

A. sq->rear-sq->front== m0。

数据结构（本）形成性考核作业答案作业1一、单项选择题1．C 2．D 3．B 4．C 5．D 6．C 7．B 8．C 9．A 10．B11．C 12．D 13．C 14．A 15．B 16．C 17．C 18．B 19．B 20．D二、填空题1．n-i+12．n-i3．集合线性结构树形结构图状结构4．物理结构存储结构5．线性结构非线性结构6．有穷性确定性可形性有零个或多个输入有零个或多个输出7．图状结构8．树形结构9．线性结构10． n-1 O(n)11．s->next=p->next;12．head13．q->next=p->next;14．p->next=head;15．单链表16．顺序存储链式存储17．存储结构18．两个直接后继直接前驱尾结点头结点19．头结点的指针指向第一个结点的指针20．链式链表三、问答题1．简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。

数据在计算机中的存储表示称为数据的存储结构。

可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。

尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。

采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。

2．解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。

答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。

优点：一般情况下，存储密度大，存储空间利用率高。

缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。

国家开放大学电大数据结构(试题50道含答案)栈是限定在表的一端进行插入和删除操作的线性表，又称为先进后出表。

()A.正确B.错误正确答案：A在有序顺序存储的线性表中查找一个元素，用折半查找速度一定比顺序查找快。

()A.正确B.错误正确答案：B在一维数组的定义语句中，数组名后带有一对花括号。

()A.正确B.错误C. n~iD. n-i+1正确答案：c设有一个长度为10的顺序表，要在第3个元素之后插入一个元素，则需移动元素的个数为()。

A.36B.78正确答案：C设有一个单向链表，结点的指针域为next,头指针为head, p 指向尾结点，为了使该单向链表改为单向循环链表，可用语句p->next=head o()A.正确B.错误若要在程序文件中使用标准输入和输出函数，则需要引入的系统头文件为stdio. h。

()A.正确B.错误正确答案：A每次只能向文本文件中写入一个字符，不能一次写入一个字符串。

()A.正确B.错误正确答案：B链表所具备的特点之一是()。

A.可以随机访问任一结点B.需要占用连续的存储空间C.插入元素的操作不需要移动元素D.删除元素的操作需要移动元素假定一组记录的排序码为(46, 79, 56, 38, 40, 80),对其进行归并排序的过程中，第二趟归并后的结果为()。

A.46,79,56,38,40,80B.46979,38,56,40,80C.38,46,56,79,40,80D.38,40,46,56,79,80正确答案：C假定要访问一个结构变量x中的由指针成员a所指向的对象，则表示方法为()。

A.x->aX. aB.*(a. x)*(X. a)正确答案：D 假定p是一个指向数据对象的指针，则通过P表示该数据对象为A. pxB.p&C.&pD.*p正确答案：D假定a是一个一维数组，则a+i的值与a[i]的值相等。

（）A.正确B.错误正确答案：B二叉树只能采用二叉链表来存储。

）。
A. f —>next=p; f=p
B. r->next=p;r=p
C. p->next=r;r=p
D. p->next=f;f=p
4. 在一个头指针为 head 的带头结点的单向循环链表中， p 指向尾结点，要使该链表成为
不带头结点的单向链表，可执行（
）。
— A. head= head >next;p=NULL
种顶点序列为（
）。
A. abecdfg C. aebcfdg
546
图1
B. aecbdfg D. aedfcbg
10. 设一棵哈夫曼树共有 31 个结点，则该树共有（
A. C 1 41 6
B. 15
）个非叶子结点。
.
D. 17
得分 1 评卷人
二、填空题（每小题 2 分，共 24 分）
11.
结构中，数据元素的位置之间存在多对多的关系。
: : I 218 I :51630 174517591860 I :61980 I :51 : :
(3) 以 1,2,3 ,6,7,8 作为叶结点的权，构造一棵哈夫曼树。
得分 1 评卷人
四、程序填空题（每空 2 分，共 16 分）
25. 设线性表以不带头结点的单向链表存储，链表头指针为 head, 以下程序的功能是： (1)
B. head= head-> next; P- >next= head
— — C. head >next=p >next
D. head= head->next;p->next=NULL 545
5. 元素 212,214,216,218 按顺序依次进栈，则该栈的不可能输出序列是（