2020年电大数据结构(本科)期末复习材料

格式：doc
大小：227.50 KB
文档页数：36

下载文档原格式

/ 36

国家开放大学2020年7月《1252本科数据结构(本)》期末考试复习题及答案

数据结构（本）期末综合练习国家开放大学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 ）。

数据结构(本科)课程期末复习

temp = p→leftChild; p→leftChild = p→rightChild; p→rightChild = temp; if ( p→rightChild != NULL ) S.push ( p→rightChild ); if ( p→leftChild != NULL ) S.push ( p→leftChild ); } } } 徐孝凯：殷老师，由于时间关系，这一堂课就上到这里。同学们看了这堂课后，将对复习和考试大有帮助。希望同学们能够按照殷老师这堂课所讲的要求，认真地做好复习，真正把数据结构课程的基本知识学到手，争取在期末考试中取得较好的成绩，同时也为学习后序课程打下基础。好！同学们再见！ 1 1
空表线性表纯表共享表递归表第六章树 * 二叉树的几个性质 * 二叉树各层最大结点数2i ( i=0,1,... * 二叉树高度为 h 时的最大结点数 n * 完全二叉树有 n 个结点时的高度 h * 完全二叉树顺序存储时结点 i 的双亲结点、子女结点、兄弟结点的位置 ( i=0,1,... 或 i=1,2,... ) * * * * * * * 有 n 个结点的不同二叉树与二叉搜索树的棵数二叉树的前序、中序和后序遍历的递归算法二叉树的递归算法求二叉树高度求二叉树叶结点个数交换二叉树根结点的左右子树自左向右链接二叉树的叶结点
private: Element <Type> * Vector; int MaxSize, CurrentSize; } template <class Type> void countsort ( datalist<Type> & initList, datalist<Type> & resultList ) { //initList是待排序表，resultList是结果表 int i, j; int *c = new int[initList.CurrentSize]; // c是存放计数的临时表 for ( i = 0; i < initList.CurrentSize; i++ ) c[i] = 0; //初始化，计数值都为0 * 对于有 n 个记录的表，关键码比较次数为 n(n-1)/2。例3 阅读以下二叉树操作算法 template <calss Type> void BinTree<Type> :: unknown ( BinTreeNode<Type> * t ) { BinTreeNode<Type> *p = t, *temp; if ( p != NULL ) { temp = p→leftChild; p→leftChild = p→rightChild; p→rightChild = temp; unknown ( p→leftChild ); unknown (p→rightChild); } } * 指出该算法完成了什么功能。 * 试写一个算法，不用栈将以上算法中的第二个递归语句消去。 * 试再写一个算法，用栈将以上算法中的第一个递归语句也消去。 void BinTree<Type> :: unknown ( BinTreeNode<Type> * t ) { BinTreeNode<Type> *p = t, *temp; while ( p != NULL ) { temp = p→leftChild; p→leftChild = p→rightChild; p→rightChild = temp; unknown ( p→leftChild ); p = p→rightChild; } } * 使用栈消去递归算法中的两个递归语句：

数据结构期末重点复习必过

数据结构期末重点复习必过1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

◆ 数据：指能够被计算机识别、存储和加工处理的信息载体。

◆ 数据元素：就是数据的基本单位，在某些情况下数据项组成。

◆ 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。

◆ 数据结构：指的是数据之间的相互关系，即数据的组织形式。

一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。

◆ 逻辑结构：指各数据元素之间的逻辑关系。

◆ 存储结构：就是数据的逻辑结构用计算机语言的实现。

◆ 线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。

线性表就是一个典型的线性结构。

◆ 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。

1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。

◆例如有一张学生成绩表，记录了一个班的学生各门课的成绩。

按学生的姓名为一行记成的表。

这个表就是一个数据结构。

每个记录(有姓名，学号，成绩等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。

这几个关系就确定了这个表的逻辑结构。

那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢?是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢?这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。

(所以各位赶快学C语言吧)。

最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。

电大1252《数据结构(本)》开放大学期末考试试题2020年1月(含答案)

Ａ．Ｚｎ
Ｂ．Ｚｎ十３
Ｃ．Ｚｎ＋２
Ｄ．Ｚｎ十４
９．设根结点所在层为第一层，一棵具有５层的完全二叉树，最后一层有６个结点，则该树
总共有（）个结点。
Ａ．２２
Ｂ．２０
Ｃ．２１
Ｄ．１９
５５０
提醒：电大资源网已将该科目2010年到2020年1月的期末试题整合、汇总、去重复、按字母排版，形成题库，方便大家复习
１９．二叉排序树２０．３
２１．树形２２．ａＺ
三、综合题（每小题中每问６分，共３０分）２３．（ｌ）
６１了６
４．Ａ９．Ｃ
２０２０年１月
５．ＣＩＯ．Ｄ
２４
９１
１１
４）７１７）９２又１０
七一１２七ｌ６
４３（５
（２）４次
（３）平均查找长度一（ｌ＋２＊２＋３＊４＋４＊４）／１１一３
（１）画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示）。（２）说明不成功查找元素４５需要经过多少次比较？（３）求在等概率条件下，成功查找的平均比较次数？２４．（１）一组记录的关键字序列为（３７，６７，４３，２５，２７，３２），给出利用堆排序（堆顶元素是最小元素）的方法建立的初始堆（要求以完全二叉树描述）。（２）对关键字序列（４ｏ，７３，４９，３１，３３，７７）采用快速排序，给出以第一个关键字为分割元素，经过一次划分后的结果。
Ｄ．１４，２０，１８０，１６０
７．设有一个巧阶的对称矩阵Ａ（第一个元素为ａｌ，；），采用压缩存储的方式，将其下三角
部分以行序为主序存储到一维数组Ｂ中（数组下标从１开始），则矩阵中元素ａｓ，：在一维数组

2020年国家开放大学电大考试数据结构期末综合考题及答案

一、单项选择题1．数据的物理结构（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．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 ）。

中央电大数据结构期末考试大钢

数据结构（本）期末复习指导第一部分课程考核说明一、考核说明数据结构（本）是中央广播电视大学计算机科学与技术（本科）专业的一门统设必修、学位课程。

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

课程主要内容包括：数据结构和算法的基本概念、线性表、栈和队列、串、数组和广义表、树和图、查找和排序等。

目的是使学生通过该课程的学习，深入地理解数据的逻辑结构和物理结构以及有关算法，掌握基本的程序设计技能，学会编制高效可靠的程序，为学习后续课程奠定基础。

现将有关考核的几个问题说明如下：1．考核对象2007年秋季起入学的计算机科学与技术专业（本科）学生。

2．考核依据以数据结构（本）课程教学大纲为依据编制，考核说明是本课程形成性考核和终结性考试命题的基本依据。

3．考核方式采用形成性考核和终结性考试相结合的方式。

4．课程总成绩的记分方法课程总成绩按百分制记分，其中形成性考核所占的比例为30%，终结性考试占70％。

60分为合格，可以获得课程学分。

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

5．形成性考核的要求、形式及手段形成性考核主要考核学生形成性作业和实验的完成情况，占课程总成绩的30%。

形成性考核以作业册的形式下发，由各地电大根据学生作业和实验的完成情况进行考核。

中央电大将不定期随机抽检各地电大学生的形成性作业及课程实验报告。

6．终结性考试的要求及方式（1）考试要求考核要求分为了解、理解和掌握三个层次：了解：是指（1）学习本课程主干知识点所需要的概念、方法、预备知识和相关内容。

（2）就大部分学生目前的知识结构和基础理解和掌握有一定困难，有待今后进一步学习的内容。

（3）在主干知识点基础上拓展的内容。

这部分不属考核的主要内容。

理解：是指要求学生准确全面领会的概念、方法和思路等。

相关内容是本课程的主干知识点，要求学生能融汇贯通，并能利用所学知识分析解决相关问题。

这部分是考核的主要范围。

电大数据结构(本)期末复习指导

中央广播电视大学数据结构（本）期末复习指导第一部分课程考核说明一、考核说明数据结构（本）是中央广播电视大学计算机科学与技术（本科）专业的一门统设必修、学位课程。