郑大远程-数据结构.doc

数据结构第01章在线测试数据结构第01章在线测试剩余时间：59:41窗体顶端答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。第一题、单项选择题（每题1分，5道题共5分）1、算法分析的目的是A、找出数据结构的合理性B、分析算法的效率以求改进C、研究算法中输入和输出的关系D、分析算法的可读性和可行性2、设n为正整数。确定下面程序段的时间复杂度： k0; for(i1;in;i+) for(ji;jn;j+) k+; A DA、nB、lognC、nlognD、n23、设n为正整数。确定下面程序段的时间复杂度： i1; k0; while(in-1) k+10*i; i+; A、1B、nC、nlognD、n24、下列函数中，时间复杂度最小的是。A、nlogn+5000nB、n2-8000nC、nlogn-6000nD、10nlogn-7000n5、n为正整数，下列程序段的时间复杂度是。 for(i1,x0; in; i+,x+);A、O(1)B、O(n)C、O(n2)D、第二题、多项选择题（每题2分，5道题共10分）1、计算机算法必须具备输入、输出和等特性。ACDA、确定性B、稳定性C、可行性D、有穷性E、易读性F、可扩充性2、根据元素之间关系的不同特性，通常可有下列基本结构。ABCDA、集合B、线性结构C、树结构D、图结构3、下列说法中，不正确的是。ABDA、数据是数据元素的基本单位B、数据元素是数据中不可分割的最小标识单位C、数据元素可由若干个数据项组成D、数据项可由若干个数据元素组成4、数据结构的三要素是指。ABCA、数据元素B、逻辑结构C、物理结构D、顺序结构E、链式结构5、数据结构被形式化的定义为(D,S), 其中D、S分别是的有限集合。ADA、数据元素B、数据操作C、数据存储D、数据关系第三题、判断题（每题1分，5道题共5分）1、数据元素是数据的不可分割的最小单位。正确错误2、数据的物理结构是指数据和关系在计算机内的实际存储形式。正确错误3、在数据结构中，从逻辑上可以把数据结构分为动态结构和静态结构两大类。正确错误4、数据对象是一组数据元素的集合。正确错误5、算法是解决某一问题的有限运算序列。正确错误窗体底端数据结构第02章在线测试数据结构第02章在线测试剩余时间：59:55窗体顶端答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。第一题、单项选择题（每题1分，5道题共5分）1、线性表的顺序存储结构是一种的存储结构。BA、顺序存取B、随机存取C、索引存取D、散列存取2、顺序表中第一个元素的起始存储地址为100，每个元素的长度为4，则第五个元素的起始地址是。A、105B、116C、120D、1243、单链表是一种的存储结构。AA、顺序存取B、随机存取C、索引存取D、散列存取4、有头结点的单链表（head为头指针）是空表的条件是A、head-nextNULL;B、headNULL;C、head-nexthead;D、head-next-next NULL;5、顺序表是线性表的一种的存储结构。A、顺序存取B、随机存取C、索引存取D、第二题、多项选择题（每题2分，5道题共10分）1、单链表是用一组任意的存储单元来存储线性表的元素，这些存储单元之间A、可以是连续的B、可以是不连续的C、必须是连续的D、必须是不连续的2、单链表的特点是。A、随机存取B、顺序存取C、元素间的逻辑关系由指针指示D、插入删除元素时需要移动表中元素E、插入删除元素时不必移动元素，只须修改指针F、数据元素在存储器内的物理位置顺序与它们的逻辑顺序不一定相同3、顺序表的特点是。ADFGA、随机存取B、顺序存取C、元素间的逻辑关系由指针指示D、插入删除元素时需要移动表中元素E、插入删除元素时不必移动元素，只须修改指针F、数据元素在存储器内的物理位置顺序与它们的逻辑顺序一定相同G、元素间的逻辑关系隐含在存储位置中4、顺序表具备的特点有。ACDA、随机存取B、顺序存取C、插入删除需要移动元素D、事先估计存储空间的大小E、插入删除只需要修改指针5、在双向循环链表（L为头指针）中，指针p所指结点为尾结点的条件是。A、p=LB、p-nextLC、L-priorpD、L-nextp第三题、判断题（每题1分，5道题共5分）1、整个单链表的存取必须从头指针开始沿链表进行，因此单链表中的元素是可以进行随机存取的。正确错误2、线性表的顺序存储结构优于链式存储结构。 （ ）正确错误3、单链表的头结点表示的是线性表中的第一个元素。正确错误4、顺序表中插入或删除元素时是以元素的移动来反映逻辑关系的变化的。正确错误5、在双向循环链表中插入或删除元素时仅需要修改结点的指针，不需要移动元素，因此算法的时间复杂度为O(1)。正确错误数据结构第03章在线测试数据结构第03章在线测试剩余时间：59:28窗体顶端答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。第一题、单项选择题（每题1分，5道题共5分）1、在进行递归函数调用时，处理参数和返回地址需要使用一种称为的数据结构。A、线性表B、栈C、队列D、树2、在顺序栈中，base、top分别为栈底、栈顶指针，则时表明栈空。A、baseNULLB、top NULLC、basetopD、3、已知一个栈的入栈序列是1，2，3，n，其输出序列为p1,p2,p3,pn,若p1n,则pi为。A、iB、n-iC、n-i+1D、不确定4、栈是限定在进行插入或删除的线性表。A、栈底B、栈顶C、任意位置D、5、在循环队列中，设队列元素依次存放在Q0.m中，f、r分别指示队头元素位置和队尾元素的下一个位置，Q中存放m个元素时认为队列满，则队列满的判定方法是 。CA、f=rB、(f+1) (m+1)rC、(r+1) (m+1)fD、(r+1) mf第二题、多项选择题（每题2分，5道题共10分）1、一个栈的入栈序列是1,2,3,4,5,在各种出栈序列中，以3，4开头的输出序列可能是。A、3,4,5,1,2B、3,4,1,2,5C、3,4,5,2,1D、3,4,2,1,5E、3,4,1,5,2F、3,4,2,5,1 2、队列入、出操作的特点是。A、只能在队尾插入B、只能在队头插入C、只能在队尾删除D、只能在队头删除E、可以在任意位置插入F、可以在任意位置删除3、下列数据结构中，是线性结构。A、线性表B、栈C、队列D、树E、图4、队列操作的原则是。ACDA、先进先出B、后进先出C、可以进行插入D、可以进行删除5、非空链栈（ls为栈顶指针）的出栈操作可表示为: pls; ; free(p);ACA、lsls-nextB、ls=pC、lsp-nextD、p ls-next第三题、判断题（每题1分，5道题共5分）1、队列是先进先出的线性表。正确错误2、一个队列的入队序列是1,2,3,4,则队列的输出序列只能是1,2,3,4。正确错误3、在链队列上删除队头元素时，只需修改头结点中的指针，不必修改尾指针。正确错误4、循环队列也可以用动态分配的一维数组来实现。正确错误5、队列只能有一种输出序列，即队列中的元素只能按照进入队列的顺序依次出队。正确错误窗体底端窗体底端数据结构第04章在线测试数据结构第04章在线测试剩余时间：59:53窗体顶端答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。第一题、单项选择题（每题1分，5道题共5分）1、若串Sabcdef，则其非空子串数目为。DA、6B、12C、21D、222、字符串是一种特殊的线性表，其特殊性在于它的数据元素只能是。A、字符B、字符串C、数字D、字母3、设有三个串，s1How, s2 are, s3 you,则这三个串连接后得到的结果串是。A、HowareyouB、How are youC、How are you.D、 How are you4、串是。DA、不少于一个字母的序列B、任意个字母的序列C、不少于一个字符的序列D、有限个字符的序列5、空格串的长度为。A、0B、1C、串中空格的个数D、第二题、多项选择题（每题2分，5道题共10分）1、以下说法正确的是。A、串长相等的两个串相等B、串值的引号不被计算在串长之内C、空串的长度为0D、空格串的长度为02、以下关于堆分配存储表示的串的说法正确的是。A、它是以地址连续的存储单元存放串值的字符序列B、它的存储空间是预先分配的一个比较大的连续空间C、它的存储空间是在程序执行过程中动态分配的D、它是按实际串长来分配存储区的大小E、它也是一种顺序存储结构3、两个串相等的充分必要条件是。A、串长相等且各对应位置字符相等B、所含字符集合相同C、所含字符个数相同D、串值相等4、串的机内表示方法有。A、定长顺序存储表示B、堆分配存储表示C、块链存储表示D、散列表示5、以下关于块链结构的说法正确的是。A、结点大小小，则存储密度小B、结点大小小，则存储密度大C、结点大小小，则占用存储空间多D、结点大小小，则占用存储空间少第三题、判断题（每题1分，5道题共5分）1、如果两个串含有相同的字符，则它们相等。正确错误2、使用定长顺序结构表示串时，超出预定义长度的串值被“截断”。正确错误3、串的基本操作和线性表的一样，都是以“单个元素”作为操作对象的。正确错误4、串是元素类型受限制的线性表。正确错误5、在串的链式存储结构中，结点大小与存储密度之间没有关系。正确错误窗体底端数据结构第05章在线测试数据结构第05章在线测试剩余时间：56:05窗体顶端答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。第一题、单项选择题（每题1分，5道题共5分）1、二叉树的第i（i1）层上至多有个结点。A、2iB、2(i-1)C、i+1D、2i-12、树最适合表示。A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据3、具有100个结点的完全二叉树的深度为。A、6B、7C、8D、94、的同种顺序的遍历仍需要栈的支持。A、先序线索树B、中序线索树C、后序线索树D、5、已知二叉树的后序遍历序列是dabec,中序遍历序列是debac,则它的先序遍历序列是。A、acbedB、decabC、deabcD、cedba第二题、多项选择题（每题2分，5道题共10分）1、下列关于树和二叉树的叙述中，正确的有。A、森林和二叉树之间可以相互转换B、树和二叉树之间可以相互转换C、二叉树的子树有左右之分，而树的子树没有左右之分D、二叉树结点的最大度数为2，而树的结点的最大度数没有限制2、森林的遍历方式有A、先序遍历B、中序遍历C、后序遍历D、层序遍历3、树型结构的特点是：任意一个结点。A、可以有多个前驱B、可以有多个后继C、只有一个前驱D、只有一个后继4、将一个有50个结点的完全二叉树按层序编号（根编号为1），则编号为 25的结点。A、有左孩子B、有右孩子C、无左孩子D、无右孩子5、树可采用的存储结构有。A、顺序结构B、多重链表C、二叉链表D、孩子链表第三题、判断题（每题1分，5道题共5分）1、n个叶子的Huffman树共有2n-1个结点。正确错误2、用树的先序遍历和中序遍历序列可以导出树的后序遍历。正确错误3、中序遍历中序线索二叉树时不必使用栈。正确错误4、在一棵非空二叉树的中序遍历序列中，根结点的右边只有其右子树上的所有结点。正确错误5、一棵树中的叶子结点数目等于与其对应的二叉树中的叶子结点数目。正确错误窗体底端数据结构第06章在线测试数据结构第06章在线测试剩余时间：59:57窗体顶端答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。第一题、单项选择题（每题1分，5道题共5分）1、一个有n个顶点的无向图若是连通图，则至少有条边。A、n-1B、nC、n+1D、(n+1)/22、图的广度优先遍历算法类似于二叉树的。A、先序遍历B、中序遍历C、后序遍历D、层序遍历3、一个无向连通图的生成树是含有该连通图所有顶点的。A、极大连通子图B、极大子图C、极小连通子图D、极小子图4、对，用克鲁斯卡尔算法求最小生成树较为合适。A、非连通图B、连通图C、稀疏图D、稠密图5、图的深度优先遍历算法类似于二叉树的。A、先序遍历B、中序遍历C、后序遍历D、层序遍历第二题、多项选择题（每题2分，5道题共10分）1、在拓扑排序中，拓扑序列的第一个顶点一定是的顶点。A、入度为0B、没有前驱C、出度为0D、没有后继2、对图分别进行深度优先遍历和广度优先遍历，得到的顶点访问序列。A、一定相同B、一定不同C、不一定相同D、可能相同3、下列说法中不正确的有。A、n个顶点的无向连通图的边数为n(n-1)B、图的广度优先遍历过程是一个递归过程C、n个顶点的有向完全图的弧数为n(n-1)D、有向图的强连通分量是有向图的极大强连通子图4、下列关于最短路径的说法中，正确的有。A、Dijkstra算法是按路径长度递增的顺序依次产生从某一固定源点到其他各顶点之间的最短路径。B、若仅求单一源点到某一特定顶点之间的最短路径，则其算法的时间复杂度可以达到O(n)。C、求图中每一对顶点间最短路径的Floyd算法的时间复杂度为O(n3)。D、求图中每一对顶点间的最短路径也可用Dijkstra算法实现。5、已知一个无向图的邻接矩阵表示，计算第i个顶点的度的方法是。A、计算邻接矩阵中第i行的元素之和B、计算邻接矩阵中第i列的元素之和C、计算邻接矩阵中第i行的非零元个数D、计算邻接矩阵中第i列的非零元个数第三题、判断题（每题1分，5道题共5分）1、任何有向图的顶点都可以排成拓扑有序序列，而且拓扑序列不唯一。正确错误2、在n个顶点的无向图中，若边数大于n-1，则该图一定是连通图。正确错误3、图的深度优先遍历算法类似于二叉树的先序遍历正确错误4、利用拓扑排序，可检测一个有向图中是否存在环正确错误5、若从无向图的一个顶点出发进行深度优先遍历可访问到图中的所有顶点，则 该图一定是连通图。正确错误窗体底端数据结构第07章在线测试数据结构第07章在线测试剩余时间：59:55窗体顶端答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。第一题、单项选择题（每题1分，5道题共5分）1、对线性表进行折半查找时，要求线性表必须。A、以顺序方式存储B、以链式方式存储C、以顺序方式存储且表中元素按关键字有序排列D、以链式方式存储且表中元素按关键字有序排列2、用链地址法处理冲突构造的散列表中，每个地址单元所链接的同义词表的相同。A、关键字B、元素值C、散列地址D、含义3、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用查找方法。DA、折半B、顺序C、分块D、散列4、有一个有序表1，3，9，12，32，41，45，62，75，77，82，95，100中折半查找值为82的结点时，次比较后查找成功。A、1B、2C、4D、85、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用查找方法。DA、折半B、顺序C、分块D、散列第二题、多项选择题（每题2分，5道题共10分）1、构造散列函数时通常考虑的因素有。A、计算函数的工作量B、关键字的长度C、散列表长D、关键字的分布情况2、下列关于n个结点的m阶B树的说法中，正确的是。BCDEA、树中每个结点最多有m个关键字B、树中叶子结点的个数为n+1C、在B树上进行查找的过程是顺指针找结点和在结点内找关键字交叉进行的过程。D、树中所有叶子结点都在同一层，并且不带任何信息E、树中每个结点最多有m-1个关键字F、树中每个结点最多有m+1个关键字3、在顺序表的顺序查找算法中，监视哨的位置。A、只能在表头B、只能在表尾C、可以在表头D、可以在表尾4、对序列50，72，43，85，75，20，35，45，30按顺序建二叉排序树，则在树中须比较3次方可查找成功的元素有。A、50 CDE F 还是不对B、43C、85D、75E、20F、35G、45H、305、在下列各种查找方法中，平均查找长度与表长有关的查找方法是。A、散列表查找B、顺序查找C、折半查找D、排序树查找第三题、判断题（每题1分，5道题共5分）1、散列表的装填因子越小，发生冲突的可能性越大。正确错误2、平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉树。正确错误3、二叉树为二叉排序树的充要条件是，其任意结点的值均大于其左孩子的值且小于其右孩子的值。正确错误4、9阶B树中，除根以外的任意非终端结点中的关键字个数不少于4。正确错误5、若散列表的装填因子小于1，则可避免冲突的产生正确错误窗体底端数据结构第08章在线测试数据结构第08章在线测试剩余时间：59:36窗体顶端答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。第一题、单项选择题（每题1分，5道题共5分）1、下列方法中，算法的时间复杂度为O(n2)。A、直接插入排序B、希尔排序C、快速排序D、堆排序2、对于关键字序