数据结构,,华工数据结构试卷资料,电信学院,

1.1选择题 1、数据结构是一门研究计算机解决实际问题中（  A  ）以及它们之间的（  B  ）和运算等的学科。 (1)A、数据元素        B、计算方法      C、逻辑存储        D、数据映像 (2)A、结构            B、关系          C、运算            D、算法 2、数据结构可以用二元组来示，它包括（  A ）集合K和K上的（  C  ）集合R。 A、数据元素          B、存储结构        C、元素之间的关系    D、逻辑结构 3、数据结构在计算机内存中的表示是指（   A  ）。 A、数据的存储结构                        B、数据结构            C、数据的逻辑结构                        D、数据元素之间的关系 4、在数据结构中，与所使用的计算机无关的是数据的（    A   ）结构。 A、逻辑              B、存储            C、逻辑和存储        D、物理 5、以下说法中正确的是（  D    ）。 A、数据元素是数据的最小单位              B、数据项是数据的基本单位 C、数据结构是带结构的各数据项的集合      D、一些表面上很不相同的数据可以有相同的逻辑结构 1.2 填空题 1、线性结构中元素之间存在（一对一）关系，树型结构中元素之间存在（一对多 ）关系，图型结构中元素之间存在（多对多）关系。 2、数据结构是研究数据的（逻辑结构）和（存储结构）以及它们之间的相互关系，并对这种结构定义相应的操作，设计出相应的（算法），而确保经过这些运算后所得到的新结构是原来的结构类型。 3、一个算法的时间复杂度是该算法包含的（简单操作次数）的多少，它是一个算法运行时间的（相对量度），一个算法的空间复杂度是指该算法在运行过程中临时占用的（存储空间）的大小。 4、一个算法的时间复杂度通常用问题规模的（最高数量级）形式表示，当一个算法的时间复杂度与问题的n大小无关时，则表示为（O（1））；成正比时，表示为（O（n）），成平方时，则表示为（O（n2））。 5、数据结构、数据元素和数据项在计算机中的映射（或表示）分别称为存储结构、结点和数据域。这句话是（正确）。（填写正确或错误） 2.1选择题 1、线性表的顺序存储结构是一种（  A  ）的存储结构，线性表的链式存储结构是一种（  B  ）的存储结构。 A、随机存取    B、顺序存取    C、索引存取      D、散列存取 2、对于一个线性，既能够进行较快的插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该选择（  B  ）。 A、顺序存储方式                  B、链式存储方式 C、散列存储方式                  D、索引存储方式 3、已知，L是一个不带头结点的单链表，p指向其中的一个结点，选择合适的语句实现在p结点的后面插入s结点的操作（  B  ）。 A、p->next=s ;  s->next=p->next ;    B、s->next=p->next ;  p->next=s ; C、p->next=s ;  s->next=p ;        D、s->next=p ;  p->next=s ; 4、单链表中各结点之间的地址（  C D  ）。 A、必须连续                      B、部分地址必须连续 C、不一定连续                    D、连续与否都可以 5、在一个长度为n的顺序表中向第i个元素（0next= =L）。 3.1 选择题 1、栈的插入和删除操作在（  A  ）进行。 A、栈顶          B、栈底            C、任意位置      D、指定位置 2、利用大小为N的数组顺序存储一个队列时，该队列最大长度为（  B  ）。 A、N－2          B、N－1            C、N              D、N＋1 3、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn, 那么p1=n；pi为（ C  ）。 Ａ、i             Ｂ、n-i             Ｃ、n－i＋1           Ｄ、不确定 4、假设以I和O分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列。下列序列（  A  ）是合法的。 Ａ、IOIIOIOO  Ｂ、IOOIOIIO        C、IIIOIOIO      D、OIIOIOIO 5、递归函数可以调用自身（  B  ）次。 Ａ、只多1次    Ｂ、任意次数          Ｃ、0 次            Ｄ、至多2次 3.2 填空题 1、线性表、栈和队列都是（线性）结构，可以在线性表的（任意）位置插入和删除元素；对于栈只能在（栈顶）插入和删除元素；对于队列只能在（队尾）插入元素和在（队首）删除元素。 2、对于一个顺序栈作进栈运算时，应先判别栈是否为（满），作退栈运算时，应先判别栈是否为（空），当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为（m）。 3、设有一个空栈，现有输入序列1，2，3，4，5，经过push，push，pop，push，pop，push，push后，输出序列是（2，3）。 4、无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除操作的时间复杂度均相同为（o(1)）。 5、有一个循环队列，分配到的存储空间大小为n，则其队满条件是（(rear+1)%QueueMaxSize= =front），队列为空的条件是（rear= =front）。 4.1选择题 1、空串与空格串是（  B  ）。 A、相同        B、不相同      Ｃ、不能确定 2、串是一种特殊的线性表，其特殊性体现在（    B  ）。 A、可以顺序存储                  B、数据元素是一个字符 C、可以链式存储                  D、数据元素可以是多个字符 3、设有两个串p和q，求q在p中首次出现的位置的操作是（  B    ）。 A、连接        B、模式匹配        C、求子串          D、求串长 4、设串s1=“ABCDEFG”，s2=“PQRST”函数strconcat（s，t）返回s和t串的连接串，strsub（s，i，j）返回串s中从第i个字符开始的、由连续j个字符组成的子串。strlength(s)返回串s的长度。则strconcat（strsub（s1，2，strlength（s2）），strsub（s1，strlength（s2），2））的结果串是（    D    ）。 A、BCDEF      B、BCDEFG      C、BCPQRST      D、BCDEFEF 5、若串s=“software”，其子串个数是（    B    ）。 A、8          B、37            C、36              D、9 4.2简答题 1、简述空串与空格串、主串与子串、串名与串值每对术语的区别？ 答：空串是指长度为0的串，即没有任何字符的串。 空格串是指由一个或多个空格组成的串，长度不为0。 子串是指由串中任意个连续字符组成的子序列，包含子串的串称为主串。 串名是串的一个名称，不指组成串的字符序列。 串值是指组成串的若干个字符序列，即双引号中的

内容

财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容

。 2、两个字符串相等的充要条件是什么？ 答：条件一是两个串的长度必须相等 条件二是串中各个对应位置上的字符都相等。 3、串有哪几种存储结构？ 答：有三种存储结构，分别为：顺序存储、链式存储和索引存储。 4、已知两个串：s1=”fg cdb cabcadr”, s2=”abc”, 试求两个串的长度，判断串s2是否是串s1的子串，并指出串s2在串s1中的位置。 答：（1）串s1的长度为14，串s2的长度为3。 （2）串s2是串s1的子串，在串s2中的位置为9。 5、已知：s1=〃I’m a student〃，s2=〃student〃，s3=〃teacher〃，试求下列各操作的结果： strlength(s1)；        答：13 strconcat(s2,s3)；      答：”studentteachar” strdelsub(s1,4,10)；    答：I’m 6、设s1=”AB”，s2=”ABCD”，s3=”EFGHIJK，试画出它们在各种存储结构下的结构图。 答： 顺序存储方式下： ‘A’       ‘B’       ‘\0’               S1 ‘A’       ‘B’       ‘C’       ‘D’       ‘\0’               S2 ‘E’       ‘F’       ‘G’       ‘H’       ‘I’       ‘J’       ‘K’       ‘\0’               S3 链式存储方式： 5.1 选择题 1、一维数组和线性表的区别是（  A   ）。 A、前者长度固定，后者长度可变    B、后者长度固定，前者长度可变 C、两者长度均固定                D、两者长度均可变 2、设W为一个二维数组，其每个数据元素Wij 占用6个字节，行下标i从0到8，列下标j从2到5，则二维数组W的数据元素共占用（    C  ）个字节。 A、480          Ｂ、192          Ｃ、216           Ｄ、144 3、在稀疏矩阵的行逻辑链式存储中，每个行单链表中的结点都具有相同的（  A   ）。 A、行号          B、列号        Ｃ、元素值        D、地址 4、二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行序存储时元素M[3][5]的起始地址与M按列序存储时的元素（      ）的起始地址相同。 A 、M[2][4]      B、 M[3][4]    C、 M[3][5]        D、M[4][4] 5、稀疏矩阵一般的压缩存储方法有两种，即（  C    ）。 A、二维数组和三维数组            B、三元组和散列  C、三元组和十字链表              D、散列和十字链表 5.2 填空题 1、一维数组的逻辑结构是（线性表），存储结构是（顺序存储）；对于二维或多维数组，分为按（行序）和（列序）两种不同的方式存储。 2、对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址为（A+(i*m+j)*每个元素所占字节数）。 3、已知广义表A=((a,b,c),(d,e,f))，则运算head(tail(tail(A)))=（e）。 4、三维数组R[c1‥d1,c2‥d2,c3‥d3]共含有（（d1-c1+1）*(d2-c2+1)*(d3-c3+1)）个元素。（c1≤d1,c2≤d2,c3≤d3） 5、二维数组A[10‥20][5‥10]以行序为主序存储，每个元素占4个存储单元，且A[10][5]的存储地址是1000，则A[18][9]的地址是（1368）。 5.3 应用题 1、按行优先存储方式，写出三维数组A[3][2][4]在内存中的排列顺序及地址计算公式（假设每个数组元素占用L个字节的内存单元，a[0][0][0]的内存地址为Loc(a[0][0][0])）。 答：内存中的排列顺序为： A[0][0][0],A[0][0][1],A[0][0][2],A[0][0][3], A[0][1][0],A[0][1][1],A[0][1][2],A[0][1][3], A[1][0][0],A[1][0][1],A[1][0][2],A[1][0][3], A[1][1][0],A[1][1][1],A[1][1][2],A[1][1][3], A[2][0][0],A[2][0][1],A[2][0][2],A[2][0][3], A[2][1][0],A[2][1][1],A[2][1][2],A[2][1][3] 地址计算公式为： Loc(a[i][j][k])= Loc(a[0][0][0])+（i*2*4+j*4+k）*L 2、给定矩阵A如下，写出它的三元组表示、行逻辑链式存储和十字链表存储。 答：三元组表示法：m=5,n=5,t=6,data数组为： 行    列    值    下标 1 1 1 2 3 2 2 4 3 3 2 4 3 5 5 5 5 6                   1 2 3 4 5 6 ┇ MaxTerms 行逻辑链式存储方式： 十字链表存储方式： 3、求下列广义表的运算的结果 （1）head((p,h,w))                结果为：(p,h,w) （2）tail ((b,k,p,h))                结果为：( ) （3）head(((a,b),(c,d)))              结果为：((a,b),(c,d) ) （4）tail (((b),(c,d)))                结果为：( ) （5）head (tail (head(( (a,d),(c,d)))))  结果为：c （6）tail (head (tail (((a,b),(c,d)))))    结果为：( ) 4、求出下列广义表的长度和深度。 （1）A=（（））                      结果为：1  2 （2）B=（a，（b，（c）））            结果为：2  3 （3）C=（a，（b，（c，d）），（e））    结果为：3  3 （4）F=（（a，（b，（），c），（（d）,e）） 结果为：3  3 5、画出下列广义表的图形表示 （1）A(b,(A,a,C(A)),C(A)) （2）D(A( ),B(e),C(a,L(b,c,d))) 答：       ( 1 )                                ( 2 ) 6、画出第5题的广义表的单链表表示。 答： （ 1 ） （ 2 ） 6.1选择题 1、假定在一棵二叉树中，度为2的分支结点个数为15，度为1的分支结点个数为30个，则叶子结点数为（  B   ）。 A、15              B、16            C、17          D、47 2、设n，m为一棵树上的两个结点，在中根遍历时，n在m前的条件是（    C  ）。 A、n在m右方      B、n是m祖先    C、n在m左方  D、n是m子孙 3、由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带树路径长度为（ D ）。 A、23              B、37            C、46            D、44 4、如果F是由树T转换而来的二叉树，则T中结点的前根就是F中结点的（    B   ）。 A、中根遍历        B、先根遍历      C、后根遍历      D、按层遍历 5、某二叉树的先根遍历结点序列和后根遍历结点序列刚好相反，则该二叉树一定是（  D  ）。 A、空树或只有一个根结点              B、完全二叉树        C、二叉排序树                        D、高度等于其结点数 6.2填空题 1、在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有（一）个前驱结点；叶子结点没有（后继）结点，其余结点的后继结点可以（任意多个）。 2、在具有n个结点的二叉树中，有（n+1）个空指针。 3、深度为k的完全二叉树至少有（2k-1）个结点，至多有（2k-1）个结点，若按自上而下，从左到右次序给结点从1开始编号，则编号最小的叶子结点的编号是（  n/2+1   ）。 4、由a，b，c三个结点构成的二叉树，共有（5）种不同形态。 5、树所对应的二叉树其根结点的（右）子树一定为空。 6.3应用题 1、给定的树如图6-24（a）所示，回答以下问题： （1）哪个是根结点，哪些是叶子结点？ 答：根结点是A，叶子结点是B，K，L，M，G，D，H，I，J。 （2）哪个是结点F的双亲结点，哪些是结点F 的祖先结点，哪些是结点F的孩子结点？ 答：结点F的双亲结点是C，祖先结点是A，C，孩子结点是K，L，M。 （3）哪些是结点C的子孙结点，哪些是结点C的兄弟结点？ 答：结点C的子孙结点是F，G，K，L，M，结点C的兄弟结点是B，D，E。 （4）给定树的层数是多少，结点I所在的层数是多少？ 答：树的层数为4，结点I在第三屋。 （5）写出先根遍历、后根遍历和按层遍历的结点序列。 答：先根：ABCFKLMGDEHIJ。后根：BKLMFGCDHIJEA。按层：ABCDEFGHIJKLM。 2、给定的二叉树如图6-25所示： （1）写出先根遍历、后根遍历、中根遍历和按层遍历的结点序列。 答：先根：ABDIKECFGN。中根：DIKBEAFCNG。后根：KIDEBFNGCA。按层：ABCDEFGTNK。 （2）画出先根遍历和中根遍历的线索二叉树。 答： 先根遍历的线索二叉树                    中根遍历的线索二叉树 （a）将图中给定的树转换成二叉树          （b）将图中给定的二叉树转换成树 （c）将图中给定的森林转换成二叉树 图6-24  题6.3.5 图6-25  题6.3.2 3、图6-24中的树、森林与二叉树之间进行转换： （1）将图（a）中给定的树转换成二叉树 （2）将图（b）中给定的二叉树转换成树 答： （1）                                  （2） （3）将图（c）中给定的森林转换成二叉树 （4）将图6-24中给定的二叉树转换成森林 答： （3）                                          （4） 4、出所有满足以下条件的二叉树： （1） 先根遍历和中根遍历时，得到的结点序列相同 答：空树、只有根结点的二叉树或所有的结点都没有左分支的二叉树。 （2） 后根遍历和中根遍历时，得到的结点序列相同 答：空树、只有根结点的二叉树或所有的结点都没有右分支的二叉树。 （3） 先根遍历和后根遍历时，得到的结点序列相同 答：空树或只有根结点的二叉树。 5、已知，一棵二叉树中根遍历的结点序列为DCBGEAHFIJK，先根遍历的结点序列为ABCDEGFHJIK，画出对应的二叉树，并写出后根遍历的结点序列。 答：解题依据：对先根遍历得到的结点序列来讲，第一个访问的结点肯定是二叉树的根结点，根据根结点可以将中根遍历的结点序列分为左子树、根结点和右子树三部分。根据分到的左、右子树包含的结点将先根遍历结点序列分出根结点、左子树和右子树。对左、右子树也是按先根遍历，所以可重复使用上述规则，就可以分出所有结点在二叉树中的位置。得到的二叉树如图所示： 6、一个度为2的树与一棵二叉树有什么区别？ 答：一个度为2的树是一棵无序树，它的两个分支不分顺序；二叉树是一棵有序树，它的两个分支是有顺序的，分别称为左右子树。 7、已知如下所示长度为12的表（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）,按表中元素的顺序构造一棵二叉排序树，插入时按字典序大小进行比较。 答： 8、有7个带权结点，其权值分别为：4，7，8，2，5，16，30，试以它们为叶子结点构造一棵哈夫曼树（要求按每个结点的左子树根结点的权值小于等于右子树根结点的权值的次序构造）。 答：构造的哈夫曼树为： 9、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用另一种编码方式是采用二进数的等长编码，给出每个字母的编码，并比较两种编码

方案

气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载

的优缺点。 答： 第一种方法：哈夫曼编码。为了简简化求哈夫曼树的过程，将每个字母的出现频率看成整数，即将0.07看到是7，依次类推。则构造的哈夫曼树如下所示： 按左分支是0，右分支是1的规则编码，则8个字母的编码依次为：1010，00，10000，1001，11，10001，01，1011（如图所示）。 第二种方法：等长编码。电文由8个字母组成，所以共有八种情况，可以用三位二进制数来表示。则8个字母的编码依次为：000，001，010，011，100，101，110，111。 比较：哈夫曼编码采用了高频率字母的编码较短的特点，所以同等个数的电文发送时翻译后所得的电文总长会比采用等长编码要短。假设发送的电文是85，以数字代表八个字母，即数字1代表第一个字母，依次类推。通过计算可得，蛤夫曼编码的总长为48，等长编码的总长为51。若发送的电文越长这个优点体现的越明显。 7.1 选择题 1、在一个图中，所有顶点的度数之和等于所有边数的（    B    ）倍。 A、1            B、2          C、3            D、4 2、对于有n个顶点和e条边的有向图和无向图，若采用边集数组表示，则存于数组的边数为（    D    ）条。 A、n ，n        B、n，e        C、2n，2e      D、e，e 3、对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为（    A    ）。 A、O（n2）      B、O（e）      C、O（n）      D、O（n+e） 4、n个顶点的强连通图至少有（    A     ）边。 A、n            B、n-1          C、n+1        D、n (n-1) 5、在一个无向图中，所有顶点的度数之和等于所有边数的（    B  ）倍；在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（    C    ）倍。 A、1/2          B、2          C、1            D、4 7.2 填空题 1、设无向图G的顶点数为n，图G最少有（0）边；最多有（n(n-1)/2）条边。若G为有向图，则图G最少有（0）边，最多有（n(n-1)）边。具有n个顶点的无向完全图，边的总数为（n(n-1)/2）；而具有n个项点的有向完全图，边的总数为（n(n-1)）。 2、在一个图G的邻接表表示中，每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的（出度）；而对于无向图而言等于该顶点的（度）。 3、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（先根）遍历；广度优先遍历算法类似于二叉树的（按层）遍历。 4、一个具有n个顶点的无向图中，要连通全部顶点至少需要（n-1）条边；若是有向图，至少需要（n）条边。 5、在无向图G的邻接矩阵A中，若A[i][j]=1，则A[j][i]=（1）。 7.3 应用题 1、 对于下面所示的图（a）和（b），求出： （a）                        （b） 图7-20 （1） 每一个图的二元组表示，对于带权图，可将边的权写在该边的后面； 答：（a）图  Ga=(V,E) V={0,1,2,3,4} E={(0,1),(0,2),(0,3),(0,4),(2,1),(2,3),(3,4)} （b）图  Gb=(V,E) V={0,1,2,3,4} E={<0,1>,<0,3>,<1,0>,<2,0>,<2,1>,<2,3>,<2,4>,<3,4>} （2）在（a）中的每个顶点的度，以及每个顶点的所有邻接点和所有边； 答： 0：度为4；邻接点1，2，3，4；边(0,1),(0,2),(0,3),(0,4) 1：度为2；邻接点0，2；边(0,1),(1,2) 2：度为3；邻接点0，1，3；边(0,2),(1,2) ,(3,2) 3：度为3；邻接点0，2，4；边(0,3),(3,2) ,(3,4) 4：度为2；邻接点0，3；边(0,4),(3,4) （3）在（b）中的每个顶点的入度、出度和度，以及每个顶点的所有入边和出边； 答： 0：入度2；出度2；度4；入边<1,0>,<2,0>；出边<0,1>,<0,3> 1：入度2；出度1；度3；入边<0,1>,<2,1>；出边<1,0> 2：入度0；出度4；度4；入边无；出边<2,0>,<2,1>,<2,3>,<2,4> 3：入度2；出度1；度3；入边<0,3>,<2,3>；出边<3,4> 4：入度2；出度0；度2；入边<2,4>,<3,4>；出边无 （4）在（a）中从0到4的所有简单路径及相应路径长度； 答：（04）1，（034）2，（0234）3，（01234）4 （5）在（b）中从0到4的所有简单路径及相应的带权路径长度； 答：（034）2 2、如图所示有向图，采用dijkstra算法求出从顶点0到其它顶点的最短路径，并说明整个计算过程。 图7-21 解： （1）选<0,1>4                              （2）选<1,2>1 （3）选<2,5>4                              （4）选<0,3>6 （5）选<1,4>7                              （6）选<5,6>8或选<4,6>6 3、写出上图的一种拓扑序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出惟一一种拓扑序列。 解：任意的拓扑序列为：0312456    惟一拓扑序列为：0132456 4、对图7-22中所示图分别写出深度优先遍历和广度优先遍历的项点序列。如果确定图以邻接矩阵存储，则得到的遍历顶点序列是什么？ 解：深度优先遍历：（a）01234    02341  （b）01342    03412 广度优先遍历：（a）01234    04321  （b）01342    03142 邻接矩阵存储时： 深度优先遍历：（a）01234  （b）01342 广度优先遍历：（a）01234  （b）01342 5、对图7-21中所示图分别用克鲁斯卡尔算法和普里姆算法（从顶点2开始）求出其最小生成树。 解：用克鲁斯卡尔算法 √    √  √  √  √  ╳  ╳  ╳    ╳  √ 1 4 2 0 2 3 0 0 2 4 1 5 2 5 3 1 5 5 3 2 4 6 4 6 1 1 2 4 4 5 6 6 6 6 7 8                         用普里姆算法 初始状态                        （1）选(1,2)1，进行修改 （2）选(2,3)2，无需修改              （3）选(1,0)4，无需修改 （4）选(2,5)4，进行修改              （5）选(4,5)1，进行修改 （6）选(4,6)6，结束 9．1一、选择题 1、一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为(  B )。 A、79，46，56，38，40，80                  B、84，79，56，38，40，46 C、84，79，56，46，40，38                  D、84，56，79，40，46，38 2、排序趟数与序列原始状态(原始排列)有关的排序方法是（ ACD ）方法。 A、插入排序        B、选择排序             C、冒泡排序       D、快速排序 3 、下列排序方法中，（  B ）是稳定的排序方法。 A、直接选择排序    B、二分法插入排序      C、希尔排序      D、快速排序 4、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中(  C  )的两趟排序后的结果。 A、选择排序        B、冒泡排序              C、插入排序      D、堆排序 5、对序列(15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据的排列变为（4，9，-1，8，20，7，15），则采用的是（ C ）排序。 A、选择          B、快速                  C、希尔          D、冒泡 6 、一组待排序记录的关键字为（46，79，56，38，40，84），则利用快速排序，以第一个记录为基准元素得到的一次划分结果为（ C ）。 A、(38,40,46,56,79,84)                      B、(40,38,46,79,56,84) C、(40,38,46,56,79,84)                      D、(40,38,46,84,56,79) 7、用直接插入排序对下面四个序列进行排序（由小到大），元素比较次数最少的是（  C ）。 A、94,32,40,90,80,46,21,69                  B、32,40,21,46,69,94,90,80 C、21,32,46,40,80,69,90,94                  D、90,69,80,46,21,32,94,40 8、若用冒泡排序对关键字序列（18,16,14,12,10,8）进行从小到大的排序，所需进行的关键字比较总次数是（ B ）。 A、10                B、15                  C、21            D、34 9、就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系（  A ）。 A、堆排序<快速排序<归并排序  　            B、堆排序<归并排序<快速排序 C、堆排序>归并排序>快速排序  　            D、堆排序>快速排序>归并排序 E、以上

答案

八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案

都不对 10、采用败者树进行k路平衡归并的外部排序算法，其总的归并效率与k（        ）。 A、有关                                    B、无关 9.2 填空题 1、在直接插入排序和直接选择排序中，若初始数据基本有序，则选用（直接插入排序），若初始数据基本反序，则选用（直接选择排序）。 2、在归并排序中，若待排序记录的个数为20，则共需要进行（5）趟归并，在第三趟归并中，是把长度为（4）的有序表归并为长度为（8）的有序表。 3、在内排序中，平均比较次数最多的是（快速排序），要求附加的内存空间最大的是（归并排序），排序时不稳定的有（希尔排序）、（选择排序）、（快速排序）和（堆排序）等几种方法。 4、对n个元素的序列进行冒泡排序，最少的比较次数是（n-1），此时元素的排列情况（从小到大排列），在（从大到小排列）情况下比较次数最多，其比较次数为（n(n-1)/2）。 5、对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7条记录60插入到有序表中时，为寻找插入位置需比较（3）次。 9.3 应用题 1、在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。 答：稳定的排序算法有直接插入排序、折半插入排序、冒泡排序、归并排序和基数排序。 不稳定的排序算法有希尔排序、直接选择排序、堆排序、快速排序。 例子：讲课是的例子。 2、设待排序的关键码分别为28，13，72，85，39，41，6，20。按折半插入排序已使前七个记录有序，中间结果如下： 6    13    28    39    41  72  85    20 i=1                m=4            r=7 试在此基础上，沿用上述表达方式，给出继续采用折半插入第八条记录的比较过程，并回答以下问题： (1) 使用折半插入排序所要进行的比较次数，是否与待排序的记录的初始状态有关？ (2) 在一些特殊情况下，二分法插入排序比直接插入排序要执行更多的比较。这句话对吗？ 答： 插入20的过程： 1 39>20：r=m-1=3;i<=r;m=(i+r)/2=4/2=2 2 13<20: i=m+1=3;i>r;查找过程结束，插入位置为i。 最终结果为：6  13  20  28  39  41  72  85 （1）插入排序所要进行的比较次数与待排序的记录的初始状态有关。若初始状态基本有序，每次查找时都会搜索到有序表的最后一个元素才找到插入位置。若每次插入的元素在有序表中的插入位置靠中间，则查找次数最少。 （2）在一些特殊情况下，二分法插入排序比直接插入排序要执行更多的比较。这句话是对的。若初始状态基本有序，则折半插入排序，每次查找时都会搜索到有序表的最后一个元素才找到插入位置。直接插入排序则每次只比较一次就找到合适位置。 3、已知一关键码序列为：3，87，12，61，70，97，26，45。试根据堆排序原理，填写完整下示各步骤结果。 建立初始堆：_97  87  26  61  70  12  3  45 堆排序过程： （1）87 70 26 61 45 12 3 97;（2） 70  61  26  3  45  12  87  97; （3）61 45 26 3 12 70 87 97;（4） 45  12  26  3  61  70  87  97; （5）26 12 3 45 61 70 87 97;（6） 12  3  26  45  61  70  87  97; （7）3 12 26 45 61 70 87 97; 4、全国有10000人参加物理竞赛，只录取成绩优异的前10名，并将他们从高分到低分输出。而对落选的其他考生，不需排出名次，问此种情况下，用何种排序方法速度最快？为什么？ 答：因排序的元素个数很大，所以需要采用排序速度较快的排序方法。排序速度比较快的排序方法有快速排序、堆排序、归并排序和基数排序等。其中快速排序、归并排序和基数排序都是在排序结束后才能确定数据元素的全部序列，而排序过程中无法知道部分连续位置上的最终元素。但堆排序则每次输出一个堆顶元素（即最大或最小元素），然后对堆进行再调整，保证堆顶元素总是剩下元素的最大或最小的，从而可知，若在大量数据的文件中，只选取排序后的前几名，采用堆排序最合适。 5、判断下列序列是否为堆，若不是堆，则把它们调整为堆。 （1）100，85，95，75，80，60，82，40，20，10，65; （2）100，95，85，82，80，75，65，60，40，20，10; （3）100，85，40，75，80，60，65，95，82，10，20; （4）10，20，40，60，65，75，80，82，85，95，100; 答：（1）100，85，95，75，80，60，82，40，20，10，65; 是堆。 （2）100，95，85，82，80，75，65，60，40，20，10; 是堆。 （3）100，85，40，75，80，60，65，95，82，10，20; 不是堆 调整以后的堆为： 100，95，65，85，80，60，40，75，82，10，20 （4）10，20，40，60，65，75，80，82，85，95，100; 是堆。