《郑州大学远程教育数据结构考试》由会员分享，可在线阅读，更多相关《郑州大学远程教育数据结构考试（14页珍藏版）》请在金锄头文库上搜索。
1、数据结构第04章在线测试数据结构第04章在线测试剩余时间：43:12A、定长顺序表示和堆分配表示都是串的顺序存储表示B、定长顺序表示的串的存储空间是编译时预先分配的一个比较大的连续空间G堆分配表示的串的存储空间是在程序执行过程中动态分配的“D堆分配存储表示时的空串不占用连续的存储区3、两个串相等的充分必要条件是。MA串长相等且各对应位置字符相等厂B、所含字符集合相同厂G所含字符个数相同“D串值相等4、串的机内表小方法有。旷A定长顺序存储表示B、堆分配存储表示乒G块链存储表示DD散列表不5、以下关于块链结构的说法正确的是。mA结点大小小，则存储密度小厂B、结点大小小，则存储密度大乒G结点大小小，
2、则占用存储空间多厂D结点大小小，则占用存储空间少第三题、判断题（每题1分，5道题共5分）1、如果一个串中的所有字符均在另一串中出现，则前者是后者的子串。正确错误2、串也有两种存储结构：顺序结构和链式结构。正确错误3、串是n个字母的有限序列（n0）o正确万错误4、串是元素类型受限制的线性表。1*正确错误5、在C语言中，用动态分配函数进行管理的自由存储区称为“堆”。G正确错误父卷数据结构第05章在线测试剩余时间：35:15答题须知：1、本卷满分20分。2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。第一题、单项
3、选择题（每题1分，5道题共5分）1、按照二叉树的定义，具有3个结点的二叉树有种形态。A3B、4CC5D、62、树最适合表示。A有序数据元素B、无序数据元素臂G元素之间具有分支层次关系的数据D、元素之间无联系的数据3、的同种顺序的遍历仍需要栈的支持。厂A先序线索树B、中序线索树G后序线索树D、B、 decab4、已知二叉树的后序遍历序列是dabec,中序遍历序列是debac,则它的先序遍历序列是rD、cedbaB、a-b+c*d/e+fA、acbedGdeabc5、对于表达式（a-b+c）*d/（e+f）,其前缀表达式为A/*+-abcd+efG /*-a+bcd+efD、ab-c+d*ef+/
4、第二题、多项选择题（每题2分，5道题共10分）1,下列关于完全二叉树的叙述中，正确的有。厂A完全二叉树一定是满二叉树厂B、满二叉树一定是完全二叉树厂G完全二叉树中要么没有结点的度为1,要么只可能有一个结点的度为1厂D只有一个结点的度为1的二叉树一定是完全二叉树2,下列关于树和二叉树的叙述中，正确的有。乒A森林和二叉树之间可以相互转换旧B、树和二叉树之间可以相互转换bG二叉树的子树有左右之分，而树的子树没有左右之分乒D二叉树结点的最大度数为2,而树的结点的最大度数没有限制3、森林的遍历方式有A先序遍历B、中序遍历G后序遍历口D层序遍历4、先序序列和中序序列相同的二叉树有。A空二叉树IB、左单支树
5、UG右单支树7D根树5、将一个有50个结点的完全二叉树按层序编号（根编号为1）,则编号为25的结点RA、有左孩子B、有右孩子乒D无右孩子第三题、判断题（每题1分，5道题共5分）1、n个叶子的Huffman树共有2n-1个结点。,正确错误2、二叉树的先、中、后序遍历序列中，叶子结点的相对顺序不会发生改变。正确错误3、将一棵树转换成相应的二叉树后，二叉树的根结点肯定没有左子树。正确错误4、二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。,正确错误5、给定二叉树的先序和后序遍历序列，可以唯一的确定这棵二叉树。正确*错误数据结木J第06章在线测试剩余时间：47:27a非连通图b、连通图臂g
6、稀疏图0D、稠密图5、对,用Prim算法求最小生成树较为合适。厂A非连通图0B、连通图厂g稀疏图aD、稠密图第二题、多项选择题(每题2分，5道题共10分)1、如果对无向图G必须进行二次广度优先遍历才能访问到图中所有顶点，则下列说法中正确的是。厂AG肯定不是完全图厂B、G肯定不是连通图厂CG中一定有回路厂DG有两个连通分量2列下列说法中正确的是。厂A、无向图中的极大连通子图称为连通分量。厂B、图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点。厂G图的深度优先搜索中一般要采用队列来暂存刚访问过的顶点。厂D有向图的遍历不能采用广度优先搜索方法。3、下列说法中不正确的有。AAn个顶点的无向连通图的
7、边数为n(n-1)乒B、图的广度优先遍历过程是一个递归过程Cn个顶点的有向完全图的弧数为n(n-1)厂D有向图的强连通分量是有向图的极大强连通子图4,下列关于最短路径的说法中，正确的有oADijkstra算法是按路径长度递增的顺序依次产生从某一固定源点到其他各顶点之间的最短路径。O(n)B、若仅求单一源点到某一特定顶点之间的最短路径，则其算法的时间复杂度可以达到G求图中每一对顶点间最短路径的Floyd算法的时间复杂度为O（nA3）厂D求图中每一对顶点间的最短路径也可用Dijkstra算法实现。5、有向图中顶点之间关系的特征是：每个顶点可以有。!_JA一个前驱OB、一个后继二G多个前驱D多个后继
8、第三题、判断题（每题1分，5道题共5分）1、连通网的最小生成树是唯一的。正确错误2、Dijkstra算法是按路径长度递增的顺序依次产生从某一固定源点到其他各顶点之间的最短路径。正确错误3、图的深度优先遍历算法类似于二叉树的先序遍历正确,错误4、对稀疏图，用Prim算法求最小生成树较为合适正确”错误5、若从无向图的一个顶点出发进行深度优先遍历可访问到图中的所有顶点，则该图一定是连通图正确错误数据结构第07章在线测试数据结构第07章在线测试剩余时间：42:32答题须知：1、本卷满分20分。2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。3、在交卷之前，不要刷新本网页，否
9、则你的答题结果将会被清空。第一题、单项选择题（每题1分，5道题共5分）1、对线性表进行折半查找时，要求线性表必须。A以顺序方式存储B、以链式方式存储6G以顺序方式存储且表中元素按关键字有序排列厂D、以链式方式存储且表中元素按关键字有序排列2、用折半查找对长度为12的有序表进行查找，则等概率下查找成功时的平均查找长度为。A35/12*B、37/12rrG39/12D、43/123、用链地址法处理冲突构造的散列表中，每个地址单元所链接的同义词表的相同。厂A、关键字0B、元素值夕G散列地址0D、含义4、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用查找方法。A、折半B、顺序臂G分
10、块D、散列5、哈希函数有一个性质：函数值应按取其值域的每一个值。AA最小概率rB、最大概率厂G平均概率臂D、同等概率第二题、多项选择题（每题2分，5道题共10分）1、构造散列函数时通常考虑的因素有。乒A计算函数的工作量口B、关键字的长度G散列表长bD关键字的分布情况2、下列关于n个结点的m阶B树的说法中，正确的是。厂A树中每个结点最多有m个关键字厂B、树中叶子结点的个数为n+1“G在B树上进行查找的过程是顺指针找结点和在结点内找关键字交叉进行的过程。bD树中所有叶子结点都在同一层，并且不带任何信息8E、树中每个结点最多有m-1个关键字厂F、树中每个结点最多有m+1个关键字3、影响散列表的平均查
11、找长度的因素有。*A散列函数-B、散列表长MG装填因子=JD处理冲突的方法4、在顺序表的顺序查找算法中，监视哨的位置。1A只能在表头B、只能在表尾G可以在表头D可以在表尾5、对序列50,72,43,85,75,20,35,45,30按顺序建二叉排序树，则在树中须比较3次方可查找成功的元素有A50B、43LG85LD75E、20F、35G45H30第三题、判断题（每题1分，5道题共5分）1、散列表的装填因子越小，发生冲突的可能性越大。正确”错误2、折半查找和二叉排序树查找的时间性能相同。正确错误3、给出不同的输入序列构造二叉排序树，一定得到不同的二叉排序树。正确昔误4、9阶B树中，除根以外的任意
12、非终端结点中的关键字个数不少于4。正确昔误5、在分块查找中，对索引表的查找既可用顺序查找法，也可用折半查找法。正确错误数据结构第08章在线测试剩余时间：37:27口A简单选择排序以R起泡排序C快速排序R直接插入排序L3E、折半插入排序2、在下列排序方法中，每一趟排序结束后都能选出一个元素放在其最终位置上的是dA简单选择排序.R起泡排序C快速排序R直接插入排序E、堆排序3、下列排序方法中，空间复杂度为0(1)的排序方法有。A堆排序口R快速排序口C直接插入排序R冒泡排序4、下列排序方法中，在最坏情况下算法的时间复杂度为0(nA2)的有。A堆排序jR快速排序yc希尔排序R冒泡排序5、下列排序方法中，不稳定的排序方法有。A希尔排序R快速排序犷C堆排序厂R直接插入排序第三题、判断题(每题1分，5道题共5分)1、快速排序的速度在所有排序方法中是最快的，而且所需的附加空间也最少。正确”错误2、在一个大顶堆中，最小元素不一定在最后。正确错误3、在数据表基本有序时，冒泡排序方法的时间复杂度一定接近O(n)。正确错误4、由于希尔排序的最后一趟与直接插入排序过程相同，所以前者一定比后者花费的时间多正确II错误5、在初始数据表为逆序时，冒泡排序所执行的比较次数最多。正确错误
