2020年国家开放大学电大数据结构题库

数据结构课程平时作业1一．单项选择题1．数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科。①A．操作对象B．计算方法C．逻辑存储D．数据映象②A．结构B．关系C．运算D．算法2．数据结构被形式地定义为（K，R），其中K是①的有限集合，R是K上的②的有限集合。①A．算法B．数据元素C．数据操作D．逻辑结构②A．操作B．映象C．存储D．关系在数据结构中，从逻辑上可以把数据结构分成()。动态结构和静态结构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)}部分参考答案单选题AB2.BD3.C4.D5.C填空题无，1，无，1前驱，1个，后继，多个多个一对一，一对多，多对多逻辑结构、物理结构、数据运算6.O(n*m)7.O(n*n)三、简答题1.略见课件2.略3．d1d2d3d4线性结构数据结构课程平时作业2一．单项选择题1.线性表L=（a,a,…,a）,下列说法正确的是（）。A．每个元素都有一个直接前驱和一个直接后继。B．线性表中至少要有一个元素。C．表中诸元素的排列顺序必须是由小到大或由大到小。D．除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继。在线性表的下列运算中，不改变数据元素之间结构关系的运算是（）。

A．插入B．删除

C．排序D．定位在一个长度为n的顺序表中，在第i个元素（1<=i<=n+1）之前插入一个新元素时需向后移动（）个元素．A．n-1 B．n-i+1 C．n-i-1 D．I4.一个数组第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）A．110B．108C．100D．1205.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以6.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行语句（）。A．s->next=p->next;p->next=s;B．p->next=s->next;s->next=p;C．q->next=s;s->next=p;D．p->next=s;s->next=q;7．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为()。A可能是2B一定是2C可能是1D一定是18.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）A.543612B.453126C.346521D.2341569.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是()A.2B.3C.5D.610.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]二.填空题（将正确的答案填在相应的空中）1.向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动_______个元素。2.带头结点的单链表head为空的判定条件是。3.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为。4.线性表（a,a,…,a）以链接方式存储时，访问第i位置元素的时间复杂性为。5.栈是的线性表，其运算遵循的原则。6.一个栈的输入序列是：1，2，3则不可能的栈输出序列是。7.用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为。8.队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是。部分参考答案单选题D2.D3.B4.B5.D6.C7.A8.C9.B10.B填空题n-i2.head->next==NULL3.O(n)4.O(1)5.访问受限，后进先出6.3,1,27.SXSSXSXX8.先进先出数据结构课程平时作业3一．单项选择题1．下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．串是一种特殊的线性表，其特殊性体现在（）。A．可以顺序存储B．数据元素是一个字符C．可以链接存储D．数据元素可以是多个字符3．串的长度是指（）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数4．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串B．联接C．匹配D．求串长5．若串S=“software”,其子串的个数是（）。A．8B．37C．36D．96.广义表（（a,b,c,d））的表头是（），表尾是（）。A.aB.（）C.（a,b,c,d）D.（b,c,d）7.设广义表L=（（a,b,c）），则L的长度和深度分别为（）。A.1和1B.1和3C.1和2D.2和38.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。A.13B.33C.18D.409.设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为()。A.BA+141B.BA+180C.BA+222D.BA+22510.假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。A.808B.818C.1010D.1020二.填空题（将正确的答案填在相应的空中）1．含零个字符的串称为()串。任何串中所含()的个数称为该串的长度。2．当且仅当两个串的()相等并且各个对应位置上的字符都()时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的()串。3．INDEX（‘DATASTRUCTURE’，‘STR’）=（）。4.数组的存储结构采用（）存储方式。5.设二维数组A[-20..30,-30..20],每个元素占有4个存储单元,存储起始地址为200。如按行优先顺序存储,则元素A[25,18]的存储地址为（）；如按列优先顺序存储,则元素A[-18,-25]的存储地址为（）。6.将整型数组A[1..8，1..8]按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[7，3]的地址是（）。7.设广义表L=((),()),则head(L)是（）；tail(L)是（）；L的长度是（）；深度是（）。8.广义表(a,(a,b),d,e,((i,j),k))的长度是（），深度是（）。部分参考答案单选题B2.B3.B4.C5.B6.C.B7.C8.B9.B10.B填空题空，字符2.长度，串值，子串3.54.顺序存储5.9392，12086.12007.（），（），2,28.5,3数据结构课程平时作业4一．单项选择题1.按照二叉树的定义，具有3个结点的二叉树有（）种。A．3B.4C.５D.62.有关二叉树下列说法正确的是（）A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为23．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定4.深度为５的二叉树至多有（）个结点。A.16B.32C.31D.105．在一棵高度为k的满二叉树中，结点总数为（）A．2k-1B．2kC．2k-1D．log2k+11.设有无向图6.G=（V，E）和G’=（V’,E’）,如G’为G的生成树，则下面不正确的说法是（）A．G’为G的子图B．G’为G的连通分量C．G’为G的极小连通子图且V’=VD．G’是G的无环子图7.任何一个带权的无向连通图的最小生成树（）A．只有一棵B．有一棵或多棵C．一定有多棵D．可能不存在8．以下说法正确的是（）A．连通分量是无向图中的极小连通子图。B．强连通分量是有向图中的极大强连通子图。C．在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧<a,b>。D．对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。9．图中有关路径的定义是（）。A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是10．设无向图的顶点个数为n，则该图最多有（）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n2二.填空题（将正确的答案填在相应的空中）１．树是n个结点的有限集合，当n=0时称为（）。2．具有256个结点的完全二叉树的深度为（）。3.如果结点A有3个兄弟，而且B是A的双亲，则B的度是()。4.设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有()个结点，右子树中有()个结点。5.具有N个结点的二叉树，采用二叉链表存储，共有（）个空链域。6．具有10个顶点的无向图，边的总数最多为()。7．对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为（），邻接表的边结点个数为（）。8.在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要（）条弧。9．下图中的强连通分量的个数为（）个。10．N个顶点的连通图用邻接矩阵表示时,该矩阵至少有（）个非零元素。三.简答题1.已知某二叉树的前序遍历序列为：ABCDEFG和中序遍历序列为：CBEDAFG，求后续遍历。（1）每个顶点的入度、出度；（2）邻接矩阵；（（1）每个顶点的入度、出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表；（5）强连通分量。部分参考答案一、单选题C2.B3.B4.C5.A6.B7.B8.B9.A10.B二、填空题空树2.93.44.n1,n2+n35.N+16.457.n,2e8.n9.310.2(N-1)简答题1.CEDBAGF2.（1）顶点入度出度130222312413521623（2）

邻接矩阵

（3）邻接表（4）逆邻接表（5）强连通分量数据结构课程平时作业5一．单项选择题1.若在线性表中采用二分查找法查找元素，该线性表应该(

)。A．元素按值有序

B．采用顺序存储结构C．元素按值有序，且采用顺序存储结构D．元素按值有序，且采用链式存储结构2.利用逐点插入法建立序列(51，71，43，81，74，20，34，45，64，30)对应的二叉排序树以后，查找元素34要进行(

)元素间的比较。A．4次

B．5次

C.7次

D．103.散列函数有一个共同性质，即函数值应按(

)取其值域的每一个值。A.最大概率

B.最小概率

C.同等概率

D.平均概率4.一个哈希函数被认为是“好的”，如果它满足条件()。A．哈希地址分布均匀B.保证不产生冲突C.所有哈希地址在表长范围内D.满足B和C5.平均查找长度最短的查找方法是()。A.折半查找B.顺序查找C.哈希查找D.其他6.若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j]，则需要移动元素的次数为（）。A.j-iB.i-j-1C.i-jD.i-j+17.若对n个元素进行直接插入排序，则进行任一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（）。A.O(1)B.O(n)C.O(n2)D.O(log2n)8.在对n个元素进行冒泡排序的过程中，第一趟排序至多需要进行（）对相邻元素之间的交换。A.nB.n-1C.n+1D.n/29.在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（）。A.O(1)B.O(log2n)C.O(n2)D.O(n)10.在对n个元素进行快速排序的过程中，第一次划分最多需要移动（）次元素，包括开始把支点元素移动到临时变量的一次在内。A.n/2B.n-1C.nD.n+1二.填空题（将正确的答案填在相应的空中）1.()法构造的哈希函数肯定不会发生冲突。2.线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索()次。设有100个结点，用二分法查找时，最大比较次数是()。3.对n个关键字进行冒泡排序，时间复杂度为（）。4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素()比较大小。5.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是()。6.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是（）的，否则称为（）的。7.按照排序过程涉及的存储设备的不同，排序可分为（）排序和（）排序。8.直接插入排序用监视哨的作用是（）。9.对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为（）。10.在插入排序和选择排序中，若初始数据基本正序，则选用（）较好。三.简答题1．对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15，分别画出应用直接插入排序、直接选择排序、快速排序、归并排序对上述序列进行排序中各趟的结果。部分参考答案一、单选题C2.A3.C4.D5.C6.D7.C8.B9.D10.B二、填空题直接定址法2.9，73.O(n2)4.28,12,205.哈希表6.稳定的，非稳定的7.内部排序，外部排序8.防止数组越界9.n(n-1)/210.插入排序简答题①直接插入排序序号123456789101112关键字834063138435965739796115i=24083[63138435965739796115]i=3406383[138435965739796115]i=413406383[8435965739796115]i=51340638384[35965739796115]i=6133540638384[965739796115]i=713354063838496[5739796115]i=81335405763838496[39796115]i=9133539405763838496[796115]i=1013353940576379838496[6115]i=111335394057616379838496[15]i=12131535394057616379838496②直接选择排序序号123456789101112关键字834063138435965739796115i=113[4063838435965739796115]i=21315[63838435965739796140]i=3131535[838463965739796140]i=413153539[8463965783796140]i=51315353940[63965783796184]i=6131535394057[966383796184]i=713153539405761[6383799684]i=81315353940576163[83799684]i=9131535394057616379[839684]i=1013153539405761637983[9684]i=111315353940576163798384[96]③快速排序关键字834063138435965739796115第一趟排序后[154063136135795739]83[9684]第二趟排序后[13]15[63406135795739]8384[96]第三趟排序后1315[3940613557]63[79]838496第四趟排序后1315[35]39[614057]6379838496第五趟排序后13153539[5740]616379838496第六趟排序后1315353940[57]616379838496第七趟排序后131535394057616379838496④归并排序关键字834063138435965739796115第一趟排序后[4083][1363][3584][5796][3979][1561]第二趟排序后[13406383][35578496][15396179]第三趟排序后[1335405763838496][15396179]第四趟排序后131535394057616379838496国家开放大学(中央广播电视大学)《国家开放大学学习指南》课程教学大纲第一部分大纲说明一、课程性质与任务《国家开放大学学习指南》是国家开放大学（中央广播电视大学）在本、专、一村一所有专业的一年级第一学期开设的、起到基础导学作用的一门统设必修课。课程任务是：以完成学习任务的过程为导向，从学习者如何完成国家开放大学规定的专业学习任务的角度，让学习者学会如何完成一门课程的学习、一个专业的学习，同时描述国家开放大学基本的学习方式，说明国家开放大学的学习环境，解释国家开放大学学习平台上基本术语的涵义，使学生能使用学习平台的基本工具辅助完成学习活动，并且了解国家开放大学学生相关事务与管理规定。使学生初步具备利用现代远程技术在国家开放大学进行学习的能力。二、先修课要求无三、课程的教学要求理解国家开放大学课程、专业平台，熟练基本的远程技术学习操作技能，掌握远程学习的学习方法，较好利用国家开放大学资源和学习支持服务。四、课程的教学方法和教学形式建议1.本课程的特点是：网络课程完善、课程内容新、课程形式丰富、实践性强、涉及面广，因此建议通过网络，在计算机教室（或计算机多媒体教室）进行授课、答疑和讨论。讲授与实践统一考虑。2.为加强和落实动手能力的培养，应保证上机机时不少于本教学大纲规定的学时。3.对于重要概念、关键技能和方法等问题可辅以网上答疑讨论的形式。五、教学要求的层次课程的教学要求大体上分为三个层次：了解、理解和掌握。了解：能正确判别有关概念和方法。理解：能正确表达有关概念和方法的含义。掌握：在理解的基础上加以灵活应用。第二部分教学媒体与教学过程建议一、课程教学总学时数、学分数课程教学总学时数为18学时，1学分。其中网络课程为13学时，课堂练习和实验为5学时。二、课程呈现方式课程以网络课程为主，这是学生学习的主要媒体形式，因此课程呈现方式以视频、动画为主，配以必要的文字说明，每段视频、动画不超过8分钟。视频以学习发生的场景为主，也可以是学生访谈，体现一定交互性。课程内容可以在手机、PAD、计算机、电视等多种终端上呈现。根据课程呈现方式，课程要做到只选取完成国家开放大学学习的必备知识，摈弃过多的理论知识，尽可能简捷。实用、方便、模块化设计，基于问题、案例形式呈现。概念清晰、条理分明、深入浅出、便于自学。在内容上要紧密围绕培养目标，突出重点、兼顾一般，反映当代最新技术及应用。三、主要教学媒体的使用与学时分配章节序号教学内容网络课程学时课堂练习和实验学时1认识国家开放大学312完成专业学习313完成课程学习314网上学习操作技能215学生事务服务21合计135四、考核本课程采用上机操作的考核方式，100%国家开放大学考核。开放教育的学生应严格执行该课程的有关考核文件。第三部分教学内容和教学要求1、学习活动一：认识国家开放大学（3学时）【教学内容】：任务一走进国家开放大学（一）基本介绍介绍国开的历史，办学模式，提供的学科门类等。（二）案例导入由国家开放大学的学生讲述参加国家开放大学学习的体会与收获（由学生讲，把国家开放大学学习的特点和优势讲出来，包括学习时间、学习方式等等。）（三）国家开放大学的学习环境1.在线学习平台；2.教师（教师群体与角色）；3.学习者（个人角色与学习小组创建）；4.学习资源（文字教材、录像、网络课程、流媒体资源、全媒体数字教材、小课件等）；5.学习活动（网上教学活动、论坛讨论）；6.支持服务（获得途径：面对面的服务、电话、短信、电子邮件、网上论坛、在线即时答疑系统）；（四）拓展内容报名渠道，获得学习资源，买书，有困难时候如何寻求帮助。任务二如何有效学习（一）学习策略1.纸质学习和电子学习的认知策略；2.制定计划、自我监控与调节；3.学习时间管理、学习资源与环境利用、互动空间与手段（QQ群、课程论坛、学习空间）、学业求助策略。（二）学习方式1.自学（自己阅读学习资源，做测试与练习）；2.听讲（听看讲课视频或音频、面授）；3.体验；4.探究；5.问题解决；任务三学前准备了解并完成一些学前准备工作，从学习方法、知识储备、计算机技能、学习环境等多方面了解自身的情况，为日后学习奠定基础。【教学要求】：了解：国家开放大学的基本介绍，教学环境；掌握：国家开放大学的学习策略与方式；掌握：在国家开放大学进行学习的学前准备；2、学习活动二：完成专业学习（3学时）【教学内容】：任务一走进专业1．专业概况、专业培养方案及实施细则，专业学习的知识、能力要求。2．本专业师资队伍、学生概况、毕业生风采。任务二专业学习过程和评价1.本专业的学习过程及主要环节2.该专业与社会证书或社会考试的接轨，学分互换等问题。任务三学位授予及其他1.申请学位相关要求。2.了解转专业、转学等相关政策。【教学要求】：了解：国家开放大学的专业概况及师生概况；掌握：国家开放大学专业学习过程及主要环节了解：国家开放大学的学位授予资格、转学与转专业相关要求3、学习活动三：完成课程学习（3学时）【教学内容】：任务一选择课程通过学习风格测试、咨询学业顾问、体验课程学习，进一步明确个人的学习要求，找