数据结构考试专用附带完整答案

单元测验1一．判断题(X)(1)数据的逻辑结构和数据的存储结构是相同的。(X)(2)程序和算法原则上没有区别，所以在讨论数据结构时可以通用。(7)(3)从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。(7)(4)数据的存储结构是数据的逻辑结构的存储映像。(X)(5)数据的逻辑结构是依赖于计算机的。(7)(6)算法是对解题方法和步骤的描述。二．填空题数据有逻辑结构和存储结构两种结构。2•数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。树形结构和图形结构合称为非线性结构。数据的存储结构又叫物理结构。数据的存储结构形式包括：顺序存储和链式存储线性结构中的元素之间存在二对二的关系。树形结构中的元素之间存在二对多的关系。图形结构的元素之间存在多对多的关系。数据结构主要研究数据的逻辑结构、存储结构和二者之间的相互运算三个方面的内容。一个算法的时间复杂度是问题规模的函数。时间复杂度：O(1)vO(log2n)vO(n)vO(nlog2n)vO(n2)vO(n3)v...vO(2n)vO(n!)若一个算法中的语句频度之和为T(n)=6n+3nlog2n，贝I」算法的时间复杂度为O(nlog2n)。12.若一个算法中的语句频度之和为T(n)=3n+nlog2n+n2，贝I」算法的时间复杂度为O(n2)。三.选择题数据结构通常是研究数据的(D)及它们之间的相互联系。联系与逻辑B.存储和抽象C.联系和抽象D.存储结构和逻辑结构数据在计算机内存储时，数据元素在存储器内相对位置可以表示元素之间的逻辑关系，称为(D)存储结构B.逻辑结构C.链式存储结构D.顺序存储结构链接存储的存储结构所占存储空间(A)。分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针只有一部分，存放结点值只有一部分，存储表示结点间关系的指针分两部分，一部分存放结点值，另一部分存放结点所占单元数在数据结构中，与所使用的计算机无关的是(B)A.物理结构B.逻辑结构(不用进行计算)C•存储结构D.逻辑和存储结构5•算法能正确的实现预定功能的特性称为(A)A.正确性B.易读性C.健壮性D.高效性算法在发生非法操作时可以作出处理的特性称为(B)A.正确性B.健壮性C.易读性D.高效性下列时间复杂度中最坏的是(A)A.O(n2)B.O(log2n)C.O(n)D.O(1)8•算法分析的两个主要方面是(C)。A.可读性和文档性B.正确性和简明性C.空间复杂性和时间复杂性D.数据复杂性和程序复杂性四．分析下面各程序段的时间复杂度(1)s=0;for(i=0;i<n;i++)O(n)2for(j=0;j<n;j++)O(n2)s=s+B[i][j];(2)for(i=0;i<n;i++) O(n)for(j=0;i<n;j++)2c[i][j]=i+j; O(n2)单元测验2一．判断题(7)(1)在线性表的链式存取结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。(X)(3)顺序存储方式的优点是存储密度大，插入、删除效率高f链式存储。(x)(4)链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。(7)(5)线性表采用顺序存储，必须占用一片连续的存储单元。(x)(6)顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。二．填空题顺序表相对于链表的优点是：节省存储和随机存取。2•链表相对于顺序表的优点有插入、删除方便；缺点是存储密度小。在一个长度为n的顺序表中删除第i个元素，要移动n-i个元素。当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快速度存取线性表中的元素时，应采用顺序存储结构在线性表的链接存储中，元素之间的逻辑关系是通过指针决定的。对一个需要经常进行插入和删除操作的线性表，采用链接存储结构为宜。三.选择题1•单链表的存储密度(C)。存储密度=(结点数据本身所占的存储量)/(结点结构所占的存储总量)A.大于1 B.等于1C.小于1 D.不能确定已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为B,则第i个结点的地址为(A)。A.B+(i-1)*m B.B+i*m C.B-i*m D.B+(i+1)*m在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为(B)A.O(1) B.O(n) C.O(n2) D.O(log2n)下面关于线性表的叙述中，错误的是(B)关系。A.顺序表必须占一片地址连续的存储单元B.链表可以随机存取任一元素C.链表不必占用一片地址连续的存储单元D.顺序表可以随机存取任一元素链表不具备的特点是(C)。A.插入删除时不需移动元素 B.不必事先估计存储空间C.随机访问 D.所需空间与线性表成正比用链式存储结构存储的线性表，其优点是(B)。A.便于随机存取 B.便于插入和删除C.花费的存储空间比顺序表少 D.数据元素的物理顺序与逻辑顺序相同四．程序填空1、求带头结点的单链表长的算法：intf(linknode*head,intn){P=head;n=0;While(P->next!=NULL){P=P->next;++n;}returnn;}2、 在单链表中查找内容为x的结点的算法：Node*Lsearch(linknode*head,charx){P=head;while(P->next!=NULL&&P->data!=x)P=P->next;if(P->next==NULL)printf("没有找到!\n");elsereturnP; /*找到，返回结点指针*/}3、 在带头结点head的单链表的结点a之后插入新元素x：structNode{Chardata;Node*next;};voidListInsert(Node*head,Charx){node*p,*s;p=head->next;while(p!=NULL)&&(p->data!=a)P=P->next;if(p==NULL)printf("不存在结点a,无法插入!\n");

elseelse{s=(node*)malloc(sizeof(node));:〃让指针s指向x的地址s->data=x;s->next=p->next;p->next=s;单元测验3一．判断题(7)(1)栈是运算受限制的线性表。(7)(2)在栈空的情况下，不能作出栈操作，否则产生下溢出。(X)(3)栈一定是顺序存储的线性结构。(7)(4)栈的特点是“后进先出”。(7)(5)链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。(X)(6)一个栈的输入序列为：A,B,C,D,可以得到输出序列：C,A,B,D。二．填空题在栈结构中，允许插入、删除的一端称为」顶。在一个链栈中，若栈顶指针等于NULL,则表示栈空。已知顺序栈S,在对S进行出栈操作之前首先要判断栈是否空。从一个栈删除元素时，首先取出栈顶元素，然后再移动栈顶指针。5•顺序栈用data[n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是data[top]=x：top++：三.选择题设有编号为1,2,3,4的四辆列车,顺序进入一个栈式结构的站台,下列不可能的出站顺序为(B)A.1234B.1423C.1324D.1243顺序栈存储空间的实现使用(B)存储栈元素。A.链表B.数组C.循环链表D.变量如果以链表作为栈的存储结构,则出栈操作时(B)A.必须判别栈是否满 B.必须判别栈是否空C.必须判别栈元素类型 D.队栈可不做任何判别4•一个栈的入栈次序ABCDE,则栈的不可能的输出序列是(D)。A.A.EDCBAB.DECBA5、栈与一般线性表的区别在于A.数据元素的类型不同C.操作是否受限制C.ABCDE D.DCEAB(C)。数据元素的个数不同D.逻辑结构不同6.带头结点的链栈LS的示意图如下，栈顶元素是(A)6.带头结点的链栈LS的示意图如下，栈顶元素是(A)A．AB．BC．CD．D单元测验4一．判断题(7)(1)队列是限制在两端进行操作的线性表。(7)(2)判断顺序队列为空的标准是头指针和尾指针均指向同一个结点(x)(3)在循环链队列中无溢出现象。(X)(4)栈和队列都是顺序存储的线性结构。(x)(5)在队列中允许删除的一端称为队尾。(x)(6)顺序队列和顺序循环队列的队满和队空的判断条件是一样的。二．填空题在队列中存取数据应遵从的原则是先进先出。在队列中，允许插入的一端称为—队社。对于队列，只能在—队琵删除元素。解决顺序队列“假溢出”的方法是釆用循环队列。顺序队列的队头指针为front,队尾指针为rear,则队空的条件为front==rear。在一个链队列中，若队头指针与队尾指针的值相同，则表示该队列为空。7.区分循环队列的满与空，有三种方法，它们是设计数器 、设标志位 _和少用一个存储空间 。8.循环队列存储在数组A[m]中，则入队时的操作为rear=(rear+1)%m9.设顺序循环队列的队头指示器front指向队头元素，队尾指示器rear指向队尾元素后的一个空闲元素，队列的最大空间为M,则用牺牲一个存储单元区分队列满与空时，队列为空的标志为front=rear队满标志为front==(rear+1)%M。10.已知链队列的头尾指针分别是Q->front和Q->rear，则将值x入队的操作序列是p=(LQNode*)malloc(sizeof(LQNode))；p->data=x;p->next=NULL；Q->rear->next=p(进行连接)：Q->rear=p(指针后移)：三．选择题1．同一队列内各元素的类型(A)。A.必须一致 B.不能一致 C.不限制 D.可以不一致2．队列是一个(D)线性表结构。A.不加限制的 B.推广了的 C.非D.加了限制的四个元素按:A,B,C,D顺序连续进队Q,执行一次出队操作后，队头元素是(先进先出(C)A.D B.CC.B D.A若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0,当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为(B)。出队一个元素front+1入队一个元素rear+1D.1和5删除值最小的元素D.判断是否还有元素A.5和1B.D.1和5删除值最小的元素D.判断是否还有元素以下属于队列的操作有(D)。A.在队首插入元素 B按元素的大小排序6.设栈S和队列Q的初始状态为空，元素el,e2,e3,e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1则栈S的容量至少应该是(C)。A. A. 6 B.4C.3 D.2单元测验5一、选择题若对n阶对称矩阵A(行下标和列下标范围均为1・・・n),将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[0..(n(n+l))/2-l]中，则在B中确定ay(i<j的位置k的关系为(B)。A.i*(i-1)/2+j-1B.j*(j-1)/2+i-1C.i*(i+1)/2+jD.j*(j+1)/2+i注意：1•下标从1开始2•对称矩阵3.i<j同时满足这三个条件答案为B1•下标从1开始2.对称矩阵3・i>=j同时满足这三个条件答案为A1•下标从0开始2.对称矩阵3.i<j同时满足这三个条件答案为D1•下标从0开始2.对称矩阵3.i>=j同时满足这三个条件答案为C假设以行序为主序存储二维数组A=array[1..1OO,1..100]，设每个数据元素占2个存储单元，基地址为10,则LOC[5,5]=(B)(注意该题下标从1开始：计算10+(4*100+4)*2=818若下标从0开始则结果为1020注意列主序算法的不同)A.808 B.818 C.1010 D.1020设有数组A[i,j],数组的每个元素长度为3字节，i的值为1到8,j的值为1至到10,数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为(B)。同下题8行10列填完一列再填下一列到A[4,8]—共60个元素A.BA+141 B.BA+180 C.BA+222 D.BA+225二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,„,8,列下标j=1,2,„,10。若A按行优先存储，元素A[8,5]的起始地址与当A按列优先存储时的元素(B)的起始地址相同。设每个字符占一个字节。计算方法：该2维数组一共是9行10列即每行10个元素，每列9个元素行主序(也就是填满一行再填下一行)A[8,5]相当于第(8*10+5)=85个元素当为列主序(即填满一列再填下一列)的时候85/9=9。。。4即可以填满9列还剩4个元素即A[3,10]A.A[8,5] B.A[3,10] C.A[5,8] D.A[0,9]设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，an为第一元素，其存储下标序号为1,则a85的下标序号为(B)。85alla21a22a31a32a33……(若为列主序就是alla12...a110a21)以此类推。那么a11到a77—共有(1+7)*7/2=28个。a81到a85是5个，所以就是33。A.13 B.33 C.18 D.40有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是(B)。a(ij,k)其中i是非0元素的行，j是非0元素的列，k是值。在用三元组表示稀疏矩阵，还要三个成员来记住，矩阵的行数列数，总的元素数，所以所需的字节数是10*(1+1+1)*2+3*2=66A.60 B.66 C.18000 D.33单元测验6一．判断题(7)(1)二叉树的前序遍历中，任意一个结点均处于其孩子结点的前面。(7)(2)由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。(7)(3)在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。(7)(4)具有n个叶子结点的哈夫曼树共有2n-1个结点。二．填空题在树中，一个结点所拥有的子树数称为该结点的度。度为零的结点称为叶结点。由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。哈夫曼树是带权路径长度的二叉树。已知完全二叉树的第8层有8个结点(根结点计为第1层)，则其叶结点数是 —。(画图)三个结点可以组成二种不同形态的树。将一棵完全二叉树按层次从0开始编号，对于为5的结点，该结点左孩子的编号为：。左孩子2n+1结点最少的二叉树是空二叉树。对于二叉树来说，第5层上至多有16个结点。2k-110•深度为5的二叉树至多有31个结点。最多〜满二叉树2^-1最少〜单支树k+1具有n个结点的满二叉树层数lo%(n+1)下取整叶结点数为no,度为2的结点为巴，则有关系n0=n2+1三.选择题树最适合用来表示(B)。A.有序数据元素 B.元素之间有分支层次的关系C.元素之间无联系的数据 D.无序数据元素前序为A，B，C的二叉树共有(A)种。TOC\o"1-5"\h\zA.5 B.4 C.3 D.2根据二叉树的定义，具有3个结点的二叉树有(C)种树型。A.3 B.4 C.5 D.6将一棵有80个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为0，则编号为38的结点的右孩子编号为(C)。右孩子2n+2A.76 B.77 C.78 D.79用5个权值｛3,2,4,5,1｝构造的哈夫曼树的带权路径长度是(B)(画图)A.32 B.33 C.34 D.15WPL=4*2+5*2+3*2+2*1+1*1=336•在树结构中，若结点B有3个兄弟，A是B的父亲结点，则A的度为为(B)。\o"CurrentDocument"A.3 B.4 C.5 D.6下列陈述正确的是(C)。A.二叉树是度为2的有序树 B•二叉树中结点只有一个孩子时无左右之分C.二叉树中最多只有两棵子树，且有左右子树之分 D.二叉树中必有度为2的结点某二叉树的前序遍历序列为:DABCEFG，中序遍历序列为:BACDFGE，则层次遍历序列为(C)。A.BCAGFEDB.ABCDEFG C.DAEBCFG D.BCAEFGD

四．应用题1、某二叉树的结点数据采用顺序存储，其结构如下（其中，“/\”表示结点为空）：0123456789ABC八DEF八八G请画出该二叉树，并分别写出按前序、中序、后序、层序遍历的结点序列。解法：按照满二叉树写出编号，然后依次填充。2、已知一棵二叉树的中序遍历结点序列为BFDGAEHC,后序遍历结点序列为FGDBHECA。请画出此二叉树，并写出该树的前序遍历结点序列。ABDFGCEH3．已知一棵二叉树的后序遍历和中序遍历的序列分别为：A,C,D,B,G,I,H,F,E和A,B,C,D,E,F,G,H,I请画出该二叉树，并写出它的前序遍历的序列。答：恢复的二叉树为其前序遍历的序列为4．已知一棵二叉树的前序遍历和中序遍历的序列分别为：A，B，D，G，H，C，E，F，I和G，D，H，B，A，E，C，I，F请画出此二叉树，并写出它的后序遍历的序列。答：恢复的二叉树为其后序遍历的序列为：GHDBEIFCA5.已知一棵树的层次遍历的序列为：ABCDEFGHIJ,中序遍历的序列为：DBGEHJACIF,请画出该二叉树，并写出它的后序遍历的序列。解：

解：6、某二叉树的结点数据采用顺序存储，其结构如下：1234567891011121314151617181920EAFDHCGIB1）画出该二叉树（3分）2）写出按层次遍历的结点序列（2分）解：（解：（1）7、 某二叉树的存储如下：00237580101JHFDBACEGI000940000012346891057lchilddatarchild其中根结点的指针为6，lchild、rchild分别为结点的左、右孩子的指针域，data为数据域。（1）画出该二叉树（3分）（2）写出该树的前序遍历的结点序列（2分）1）解：（2）前序遍历的结点序列：ABCEDFHGIJ

1）哈夫曼树的构造方法：依次选择权值最小和次小的数的数分别作为二叉树的左右孩子WPL的计算以及哈弗曼编码给定一个权集W={4,5,7,8,6,12,18}，试画出相应的哈夫曼树，并计算其带权路径长度WPL。WPL=(12+18)*2+(6+7+8)*3+(4+5)*4=159给定一个权集W={3,15,17,14,6,16,9,2},试画出相应的哈夫曼树,并计算其带权路径长度WPL解WPL=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=2295•假设用于通信的电文仅由A、B、C、D、E、F、G、H8个字母组成，字母在电文中出现的频率分别为7,19,2,6,32,3,21,10。试为这8个字母设计哈夫曼编码。23字母编号对应编码出现频率A10107B0019C100002D10016E1132F100013G0121H101110解：以权值：2、323字母编号对应编码出现频率A10107B0019C100002D10016E1132F100013G0121H101110单元测验7一．判断题(X)(1)在无向图中，(VI,V2)与(V2,VI)是两条不同的边。(X)(2)邻接表只能用于有向图的存储。(7)(3)一个图的邻接矩阵表示是唯一的。(X)(4)有向图不能进行广度优先遍历。(7)(5)若一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。二．填空题图有：邻接矩阵和邻接表等常用存储方式。图的遍历有:深度优先搜索和广度优先搜索等方法。图的邻接矩阵表示法是表示顶点—之间相邻关系的矩阵。有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的 出度。有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点i的入度。6•设有一稀疏图G,则G采用邻接表 存储比较节省空间。设有一稠密图G,则G采用邻接矩阵—存储比较节省空间。n个顶点的有向完全图有n(n-1) 条边。若为无向图则有n(n-1/2条边9•对于具有n个顶点的图，其生成树有且仅有n-1条边。无向图的邻接矩阵一定是对称矩阵。三.选择题在下列表示方法中，(D)是有向图边的表示方法。A.(1，2) B.(1，2> C.<1，2) D.<1，2>在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的(B)倍。A.1/2 B.1 C.2 D.4对于一个具有n个顶点的无向图的边数最多有(B)。A.n B.n(n-1)/2 C.n(n-1) D.2n在一个具有n个顶点的无向图中，要连通全部顶点至少需要(B)条边。A.n B.n-1 C.n+1 D.n/25•有8个结点的有向完全图有(C)条边。n(n-1)A.14 B.28 C.56 D.112无向图顶点v的度是关联于该顶点(B)的数目。A.顶点 B.边 C.序号 D.下标有n个顶点的无向图的邻接矩阵是用(B)数组存储。A.—维 B.n行n列 C.任意行n列 D.n行任意列在一个具有n个顶点e条边的图中，所有顶点的度数之和等于(C)。举例得出结论即可A.e B.n C.2e D.2n四．应用题1．根据如下无向图(1)画出该图的邻接矩阵和邻接表(2)并分别给出该图邻接矩阵下的深度优先搜索遍历和广度优先搜索遍历的结点序列。邻接矩阵邻接表表示方法ABABCDEFGA0110000B1011000C1001000D0110110E0001001F0001001G0000110A—>B—>CB—>A—>DC—>A—>DD—>B—>C—>E—>FE—>D—>GF—>D—>GG—>E—>F深度优先遍历ABDCEGF广度优先遍历ABCDEFG2•分别用普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法画出构造该无向带权图最小生成树的过程。单元测验8一．判断题(X)(1)如果某种排序算法不稳定，则该排序方法就没有实际应用价值。(7)(2)对n个记录的进行快速排序，所需要的平均时间是O(nlog2n)(X)(3)堆排序所需的时间与待排序的记录个数无关。(7)(4)当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。(7)(5)对快速排序来说，初始序列为递增有序或递减有序都是最坏情况。(7)(6)采用希尔方法排序时，若关键字的排列杂乱无序，则效率较高。二．填空题大多数排序算法都有两个基本的操作:比较和移动对n个关键字进行冒泡排序，时间复杂度为O(谊)。快速排序在最坏情况下的时间复杂度是O(n2)。在排序前，关键字值相等的不同记录，排序后相对位置保持_丕变一的排序方法，称为稳定的排序方法。当增量为1时，该趟希尔排序与直接插入排序基本一致。第一趟排序后，序列中键值最大的记录交换到最后的排序算法是冒泡排序。依次将待排序的每个记录插入到一个有序已排序序列中的排序方法称为插入排序。对一组记录(54,38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较3_次。有序区［152338547296］无序区［604583］待插入元素60先和96比较再和72比较最后和54比较两个序列分别为:L1={25，57，48，37，92，86，12，33}交换15次L2={25，37，33，12，48，57，86，92}交换4次用冒泡排序法对L1和L2进行排序，交换次数较少的是序列：.L2—。对一组记录(54,35，96，21，12，72，60，44，80)进行直接选择排序时，第四次选择和交换后，未排序记录是54,72,60,96,80第一次有序区［12］无序区［3596215472604480］第二次有序区［1221］无序区［96355472604480］第三次有序区［122135］无序区［965472604480］第四次有序区［12213544］无序区［5472609680］三.选择题排序是根据(A)的大小重新安排各元素的顺序。A.关键字B.数组C.元素件D.结点排序方法中，从无序序列中选择关键字最小的记录，将其与无序区(初始为空)的第一个记录交换的排序方法，称为(B)。A.插入排序 B.选择排序 C.希尔排序 D.快速排序每次把待排序方的区间划分为左、右两个区间，其中左区间中元素的值不大于基准元素的值，右区间中元素的值不小于基准元素的值，此种排序方法叫做(D)。A.冒泡排序 B.堆排序 C.希尔排序 D.快速排序快速排序在(C)情况下最易发挥其长处。A.待排序的数据中含有多个相同的关键字B.待排序的数据已基本有序C.待排序的数据完全无序 D.待排序的数据中最大值与最小值相差悬殊直接插入排序的方法是从第(B)个元素开始，插入到前边适当位置的排序方法。A.1 B.2 C.3 D.n第一个元素初始时已经选定为a［0］堆的形状是一棵(C)。A.二叉排序树 B.满二叉树 C.完全二叉树 D.任意二叉树7．内排序是指在排序的整个过程中，全部数据都在计算机的（A）中完成的排序。A.内存B.外存C.内存和外存 D.寄存器外排序则是将数据部分导入内存依次排序下述几种排序方法中，平均时间复杂度最小的是（A）。A.希尔排序O（n1-3） B.直接插入排序 C.冒泡排序D.直接选择排序对n个数据进行快速排序，在最坏情况下，算法的时间复杂度是（B）。A.O（n） B.O（n2） C.O（nlog2n） D.O（n3）冒泡排序的方法对n个数据进行排序，第一趟排序共需要比较（C）次。A.1 B.2 C.n-1D.n用直接插入排序法对下面的四个序列进行由小到大的排序，元素比较次数最少的是（B）。A，94， 32， 40， 90， 80， 46， 21， 69 B. 21，32，46，40，80，69，90，94C.32， 40， 21， 46， 69， 94， 90， 80 D. 90，69，80，46，21，32，94，40一个数据序列的关键字为：（46，79，56，38，40，84），采用快速排序，并以第一个数为基准得到第一次划分的结果为：（C）以46（Low）为基准进行第一次快速排序（递归）〜先右后左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，79，56，84）四.应用题已知数据序列｛80，18，9，90，27，75，42，69｝，试写出采用冒泡排序（从小到大）算法排序时，每一趟排序的结果。第一次189802775426990第二次918277542698090第三次918274269758090已知数据序列｛40，63，11，84，35，93，58，39｝，试写出采用直接选择排序（从小到大）每一趟排序结果。第一次11 63408435935839第二次1135408463935839第三次1135398463935840第四次11353940 84639358第五次1135394058639384第六次113539405863 9384第七次11353940586384 93第八次1135394058638493已知数据序列｛12，2，16，30，28，10，17，20｝，写出希尔排序（从小到大）每一趟（设d=4,2,1）的排序结果。第一次122162028101730第二次122161017202830第三次212101617202830已知数据序列｛10,1,15a,18,7,15b｝（ab为了区别两个15）,试写出采用快速排序（从小到大）每一趟排序的结果。第一次17101815a15b第二次171015b15a185．已知数据序列{18，17，60，40，07，32，73趟排序结果。第一次18 17604007327365第二次1718 604007327365第三次171860 4007327365第四次17184060 07327365第五次0717184060 327365第六次071718324060 7365第七次07171832406073 65第八次0717183240606573五．程序填空1．直接选择排序VoidSelectSort(DataTypea[],intn){inti,j,small;DataTypetemp;for(i=0;i<n-1;i++){Small=i;for(j=i+1;j<n;i++)if(a[j].key<a[small].key)small=j;if(small!=i){temp=a[i];a[i]=a[small];a[small=temp;}}}

65}，试写出采用直接插入排序(从小到大)每2、直接插入排序VoidInsertSort(DataTypea[],intn){inti,j;DataTypetemp;for(i=0;ivn-1;i++){temp=a[i+1];j=i；while(j>-1&&temp.keyva[j].key){aj+1]=a[i];j--；}a[j+1]=temp;}}3、冒泡排序VoidBubbleSort(DataTypea[],intn){intij,flag=1;DataTypetemp;for(i=0;ivn-1&&flag==1;i++){flag=0;for(j=0;jvn-1-i;j++){if(a[j].key >a[j+1].key){flag=1;temp=a[j];a[j]=aj+1];a[j+1]=temp;}}}}单元测验9一．判断题(7)(1)二分査找法要求待査表的关键字值必须有序。(X)(2)对有序表而言采用二分查找总比采用顺序查找法速度快。 慢(X)(3)在二叉排序树中，根结点的值都小于孩子结点的值。 小于右孩子结点的值(7)(4)哈希表是一种将关键字转换为存储地址的存储方法。(7)(5)哈希法的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。(X)(6)在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点的相应的指针域置空即可。二．填空题1•在分块查找方法中，首先查找索引表，然后再查找相应的块。2•顺序查找、二分查找、分块查找都属于静态查找。对于长度为n的线性表，若进行顺序查找，则时间复杂度为O(n)。4•对于长度为n的线性表，若采用二分査找，则时间复杂度为：O(log2n)_。在关键字序列(7,10，12，18，28，36,45，92)中，用二分查找法查找关键字92,要比较4次才找到。第一次mid=(low+high)/2=3查找a[3]=18,low=mid+1=4第二次mid=(low+high)/2=5查找a[5]=36,low=mid+1=6第三次mid=(low+high)/2=6查找a[6]=45,low=mid+1=7第四次mid=(low+high)/2=7查找a[7]=92・对二叉排序树进行查找的方法是用待查的值与根结点的键值进行比较，若比根结点小，则继续在，左子树中杳找。7•二叉排序树是一种动态查找表。哈希法既是一种存储方法，又是一种至找方法。设哈希函数H(k)和键值匕，k2，若k子k2，且H(k1)=H(k2),则称这种现象为哈希冲突。处理冲突的两类主要方法是开放定址法和链表法。在哈希函数H(key)=key%P中，P一般应取质数。 为了最大情况避免哈希冲突在査找过程中有插入元素或删除元素操作的，称为_动基査找。三.选择题对线性表进行二分查找时，要求线性表必须(B)。A.以顺序方式存储 B.以顺序方式存储，且结点按关键字有序排序C.以链接方式存储 D.以