2014考研计算机数据结构专项精讲课程讲义第二部分

(C/C++语言版(C/C++语言版Data基础与理论环节——第一章第三章栈第六章图及应用第七章查找基础基础与理论环节——概念和算法思路解第一章绪基本概念和抽象数据类算法和算法A.效率B.复杂性C.现实性D问题的规 B.待处理数据的初3.计算机算法指的是(1),它必须具备（2）A.计算方 B.排序方C.解决问题的步骤序列DA.A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A和从逻辑上可 分为() C.线性结构非线性结构D.初等结构、构造型结构 结构无关的术语是()。 B.链表C.哈希 ()。FORi:=1TOnDOFORj:=1TOnDO8.FORi:=n-1DOWNTO1DOFORj:=1TOiDO8.FORi:=n-1DOWNTO1DOFORj:=1TOiDOIFTHENA[j]与A[j+1]n为正整数，则最后一行的语句频度在情况下是()。 系。()有关。()健壮的算法不会 的输入数据而出现莫名其妙的状态(66算法可以用不同语言描述，如果用C言等高级语言来描述，则算法实际上就是程序。()7.程序一定是算法。8.数据的物理结构是指数据在计算机内的实 形式。( 的抽象操作的定义与具体实现有关。10.在顺序 关系。()中 间储 效率高。() 结构的独立。() 结构。()三、填 包 的表示 的表示对于给定的n个元素,可以构造出的逻辑结构有.（3）,（4）四种数据的逻辑结构是 .个.个4.在计算机4.在计算机 称5.抽象数据类型的定义仅取决于它的一组 ,而 6中评价算法的两个重要指标 ,而与(2),无关，即不论其内部结构如何变化，只要它的(3),不变，都不影响其外部使用。7．在7．在下面的程序段中，对ｘ的赋值语句的频度 （表示为n的函数 i：＝１TOnDO j：＝１TOiDOFORk：＝1TOj8.计算机执行下面的语句时，语句s的执行次数 8.8.计算机执行下面的语句时，语句s的执行次数 答案：(n+3)(n-9.n,n-n3+7n5,nlogn,2n/2,n3,logn,n1/2+logn,(3/2)n,,n!,n2+logn9.n,9.n,n-n3+7n5,nlogn,2n/2,n3,logn,n1/2+logn,(3/2)n,,n!,n2+lognlogn,n1/2+logn,n,nlogn,n2+logn，n3,n-n3+7n5,2n/2,(3/2)n,n!,基础与理论环节——第二章第三章栈第六章图及应用第七章查找—选择—选择3．线性表是具有n个A．表元 B．字）的有限序列（n>0）C．数据元 D．数 E．信息4若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）省时间。A.顺序结点的双循环链 C．双链D．仅有尾指针的单循环链6．设—个链表最常用的操作是入结点和删除尾点，则选用 )最节省时间A.单链 B.单循环链C.带尾指针的单循环链 结点的双循环链7．7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ ）方式最节省运算时间。A．单链 B．双链C．单循环链 结点的双循环链8.静态链表中指针表示的是 A．内存地 下面的叙述不正确的是 线性表在链 时，查找第i个元素的时间同i的值成正线性表在链式时，查找第i个元素的时间同i的值无线性表在顺序时，查找第i个元素的时间同i的值成正线性表在顺序时，查找第i个元素的时间同i的值无voidreverse(pointer{pointerp=h->next;h->next=NULL; {q=p;p=p->next;q->next=h->next; }}voidreverse(pointer{pointerp=h->next;h->next=NULL; {q=p;p=p->next;q->next=h->next; }}p!=null 31.下面是用c31.下面是用c语言编写的对不 voidreverse（linklist{{ q->next=p；p=q；(2)} }voidreverse（linklist{p=null；q=L；{ >next=p；p=q；(2)} }L=L->next 3636typedefstruct{intdata;structnodevoidInsertsort(link {r=L;q=L- &&q->data<=p-{r=q;q=q-u=p->next; ; ;}}voidInsertsort(link {r=L;q=L- &&q->data<=p-{r=q;q=q-u=p->next; ; ;}}(1)L->next=null(2)p!=null(3)q!=null(4)p->next=r->next(5)r->next=p基础与理论环节——基础与理论环节——第六章图及应用第七章查找—选择题一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第 B.n- C. D.n-4.若一个栈的输入序列为1,2,3,,n，输出序列的第一个元素是i，则A.i-j- B.i-）Cj-i+1D若已知一个栈的入栈序列是1,2,3,若已知一个栈的入栈序列是1,2,3,,n，其输出序列为p1,p2,p3，，pN,若pN是n，则pi是( A. B.n- Cn- D有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法 A.54361 B.45312C.34652 D.234157.设栈的输入序列是1，2，3，4,则（）A.1，2，4，3，B.C.1，4，3，2，D.4，3，1，2，E.8.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序 A.2341C.2314B.5413D.15439.设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法 A.5123C.4312B.4513D.321510.10.某堆栈的输入序列为a,b，c，d,下面的四个序列中，不可能是它 A. B.b,C.c,d，b, D.d,11.设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则 A．fedcbaB.bcafedC.dcefbaD.1 表达式exp的一个单词 表达式exp的一个单词③x是运算符。若x‘）’，‘（’为止。。835+562/-*基础基础与理论环节——基本概念和算法思路第一章第三章栈第四章第五章树与二叉第六章及应用第七章查找第八章序第九章1用不 指针指向队尾结点，则在进行删除操作时()。A．仅修改队头指 B仅修改队尾指C队头、队尾指针都要修 D队头,队尾指针都可能要修2递归过程或函数调用时，处理参数及返回地址，要用一种称为（。A． 数 C． D线性3假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A．(rear-D．(rear-循环队循环队 在数组A[0m]中，则入队时的操作为（）A Brear=(rear+1)mod(m-Crear=(rear+1)mod D若用一个大小为6的数组来实现循环队列，且当前rr和font的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，ar和on的值分别为多少？A1和 B2和 C4和 D5和已知输入序列为abcd（）AdacbBcadbC DbdacE得到，也不能由输出受限的双端队列得到的输出序列是()。A B C D件是（）。A(rear+1)MOD B D(rear-l)MOD9栈和队列的共同点是（）A都是先进先 B都是先进后C只允许在端点处插入和删除元 D没有共同栈的特点是（）栈的特点是（）,队列的特点是（）,栈和队列都是（）。若进栈序列为1,2,3,4则（④）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4则（⑤）是一个出①,②:A先进先 B后进先 C进优于出D出优于③:A顺序的线性结构B链式的线性结C限制存取点的线性结构D④,⑤:A3,2,1,4B3,2,4,1C4,2,3,1D4,3,2,1F1,2,3,4G栈和队都是（A．顺序的线性结 B链 的非线性结C限制存取点的线性结构D设栈S和队列Q的初始状态为空，元素1，2，3，45和6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，4，3651则栈S的容量至少应该是。 B C D用单链表表示的链式队列的队头在链表的（）链 B．链 C．链进后出型结构。（）通常使用队列来处理函数或过程的调用。（队列逻辑上是一个下端和上端既能增加又能减少的线性表。（循环队列通常用指针来实现队列的头尾相接。（循环队列也存在空间溢出问题。（队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（栈和队列都是线性表，只是在插入和删除时受到了一些限制。（栈和队列 方式，既可以是顺序方式，又可以是链式方式。（三填空题循环队列的引入，目的是为了克 队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是 。已知链队列的头尾指针分别是f和r，则将值x 区分循环队列的满与空，只有两种方法，它们 6．设循环队列用数组6．设循环队列用数组A[1M]表示，队首、队尾指针分别是FRONT和 7设循环队列存放在向量sqdata[0:M]中，则队头指针sqfront在循环意义 队满和队空（设队尾指针sqrear）,则队满的条件为 表达式求值 应用的一个典型例子循环队列用数组A[0m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是 设Q[0N-1]为循环队列，其头、尾指针分别为P和R，则队Q中当前 基础与理论环节——基本概念和算法思路解第一章第三章栈第四章树与二叉树第六章图及应用第七章查找第八章序第九章2已知一棵二叉树的前序遍历为ABECDFGHIJ33(1)对此二叉树进行后序后继线索化；(2)将此二叉树变换为森林(3)用后根序遍历该森林，；写出遍历后的结点序5、以数据集{3,4,5,8,12,18,20,30}5、以数据集{3,4,5,8,12,18,20,30}基础与理论环节——第三章栈第六章图及应用第七章查找11．图中有关路径的定义是）2．设无向图的顶点个数为n，则该图最多有（）A．n- B．n(n- C． 3．—个n个顶点的连通无向图，其边的个数至少为（） B．n C．n+1 4．要连通具有n个顶点的有向图，至少需要（）条边。 5．n个结点的完全有向图含有边的数目 Ｂ．n（n＋１））6．—个有n个结点的图，最少有（）个连通分量，最多有（）个连 C．n- 7．在—个无向图中，所有顶点的度数之和等于所有边数（7．在—个无向图中，所有顶点的度数之和等于所有边数（） 点，则输出的顶点序列是()。A．逆拓扑有 B．拓扑有 C．无序9．下列哪—种图的邻接矩阵是对称矩阵？（A．有向 B．无向 C．AOV D．AOE1．给出图画出G的邻接表表示图（2（2）以顶点①为根，画出G的广度优先生成 2．已知一个无向图如下图所示，要求分别用Pi和Kuskl算法生成最小树（假设以①为起点，试画出构造过程）假设开始顶点就选为顶点1，故首先有假设开始顶点就选为顶点1，故首先有66 15125 1255(d)u={1,3,6}134264(c)u={1,3}要求要求分别用Prim算法生成最小树（假设以①为起点要求分别用Kruskal算法生成最小树（假设以①为起点3．用最短路径算法，求如下图中3．用最短路径算法，求如下图中a到z4．请写出应填入下列叙述中（4．请写出应填入下列叙述中（） 完成此工程的关键路径是（1）求出所有的最早开始时间ve[j]=若j=0（即vj为源点Maxve[idur(i,j|vviVe[0]=0(表示0最早发生时间是0)Ve[1]=Max{Ve[0]+dur(<0,1>)}=6(表示1最早发生时间是6)Ve[2]=Max{Ve[0]+dur(<0,2>)}=4(表示2最早发生时间是4)(表示（2（2）求出所 的最迟开始时vl[j]=ve(n-Min{vl[k]-dur(j,k)|<v,v>为网中jVl[8]=18(表示 Vl[7]=Min{Vl[8]-dur(<7,8>)}=18-4=14(表示 Vl[6]=Min{Vl[8]-dur(<6,8>)}=18-2=16(表示 Vl[5]=Min{Vl[7]-dur(<5,7>)}=14-4=10(表示 Vl[2]=Min{Vl[4]-dur(<2,4>)}=7-Vl[1]=Min{Vl[4]-dur(<1,4>)}=7-Vl[0]=Min{Vl[1]-dur(<0,1>),Vl[2]-dur(<0,1>,Vl[3]-dur(<0,3)}=Min{6-6,6-a<0,1>e[1]=Ve[0]=0a<0,2>e[2]=Ve[0]=0i=0a<0,3>e[3]=Ve[0]=0a<1,4>e[4]=Ve[1]=6i=1a<2,4>e[5]=Ve[2]=4i=2a<3,5>e[6]=Ve[3]=5i=3a<4,6>e[7]=Ve[4]=7i=4a<4,7>e[8]=Ve[4]=7i=4a<5,7>e[9]=Ve[5]=7a<6,8>e[10]=Ve[6]=16i=6a<7,8>e[11]=Ve[7]=14l[k]=Vl[j]-dur(<i,j>)a是活动a<0,1>l[1]=Vl[1]-dur(<0,1>)=6-a<0,2>l[2]=Vl[2]-dur(<0,2>)=6-a<0,3>l[3]=Vl[3]-dur(<0,3>)=8-5=3a<1,4>l[4]=Vl[4]-dur(<1,4>)=7-=a<2,4>l[5]=Vl[4]-dur(<2,4>)=7-1=6a<3,5>l[6]=Vl[5]-dur(<3,5>)=10-a<4,6>l[7]=Vl[6]-dur(<4,6>)=16-a<4,7>l[8]=Vl[7]-dur(<4,7>)=14-a<5,7>l[9]=Vl[7]-dur(<5,7>)=14-l[1]-e[1]=0- l[4]-e[4]=6- l[7]-e[7]=7- l[11]-e[11]=14- （4（4）所以a1,a4,a7,a8,a10,a11是关键活动，他们组成关键第i 最早开始时间活动活动ak的最早开始时间第i个 允许最迟开始时间松弛时间l[k]-基础基础与理论环节——基本概念和算法思路第一章第三章栈第四章第六章图及应用第七章查找第八章第九章—选择题1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。A．(n- B. C. D.2N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为() B.N/2 C.N D.[（1+N）*N]/2 数为（（1））,二分法查找只适用于查找顺 的有序表，平比较次数为（（2））N为线性表中结点数，且每次查44下面关于二分查找的叙述正确的是()A表必须有序，表可以顺序方式 C表必须B表必须有序且表中数据必须是整型，实型或字符型 D表必须有序，5对线性表进行二分查找时，要求线性表必须（A以顺序方C 方B以顺序方 D 方适用于折半查找的表 方式及元素排列要求为(方 ，元素无序 方 ，元素有C．顺序方 ，元素无序D．顺序方 ，元素有设哈希表长为14，哈希函数是Hkyky%1表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决，则放入的位置是() 列表中，至少要进行多少次探测？()A．k-1次Bk次Ck+1次Dk（k+1）/2哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k次探测。A． Bk+1Ck(k+1)/2D10散列函数有一个共同的性质，即函数值应当以10散列函数有一个共同的性质，即函数值应当以()A最大概率B最小概率C平均概率D11散列表的地址区间为0-17,散列函数为H(K)=Kmod17。采用线性探测法处理，并将关键字序列26，25，72，38，8，18，59依次存储（1）元素59存放在散列表中的地址是（）A． B C D（2）存放元素59需要搜索的次数是（）A． B C D12将个元素散列 个单元的哈希表中，则（）产生A一定会B一定不会C Hash表的平均查找长度与处理的方法无关(装填因子)是散列表的一个重要参数，它反映散列表的装满7散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载若散列表的负载因子若散列表的负载因子α<1在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。顺序查找法适用 结构为顺序或的线性表就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为 次；当使用监视哨时，若查找失败，则比较关键字的次数为_。 在顺序表（81159252630332850）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为3．在有序表A[112]中，采用二分查找算法查等于A[12]的元素，所比较 4在有序表A[120]中，按二分查找方法进行查找，查找长度为5的元素 给定关键字序列给定关键字序列11，78，10，1，3，2，4，21，试分别用顺序查找、二分查找、二叉排序树查找、平衡二叉树查找、散列查找(用线性探查法和拉链法)来实现查找，试画出它们的对应形式(顺序查找的顺序表，二分查找的判定树，二叉排序树查找的二叉排序树及平衡二叉树查找的平衡二叉树，两种散列查找的散列表)，并求出每一种查找的成功平均查找长度。散列函数H()=%1。01234567891324图7-顺序的顺序表二分查找的判定树（中序序列为从小到大排列的有序序列）7-20二分查找的判定树（中序序列为从小到大排列的有序序列）7-20从图7-20ASL=(1+2*2+3*4+4)/8=2二叉排序树（关键字顺序已确定，该二叉排序树应唯一）如图7-21()所示，平衡二叉树（关键字顺序已确定，该平衡二叉树也应该是唯一的），如图7-21(b)所示，ASL=(1+2*2+3*2+4+5*2)=3ASL=(1+2*2+3*3+4*2)/8=20101234567891324图7-22线性探查的散列拉链法解决的散列表ASL=(1*6+2*2)/8=1.25基础基础与理论环节——基本概念和算法思路第一章第三章栈第四章第六章图及应用第七章查找第八章第九章—选择题 C．平均时间为0（nlogn）2下面给出的四种排序法中 A.插 B.冒泡C.二路归并 A.堆排序，冒泡排 B.快速排序，堆排C.直接选择排序，归并排 D.归并排序，冒泡排4．稳定的排序方法是 4．稳定的排序方法是 C．简单选择排序和四路归并排序D．树形选择排序和 排AB）B．归并排序C．冒泡排序）。 则可选择的排序方法是 ）AC A.起泡排序B.折半插入排序C.简单选择排序D.排序E.基数排序A．快速排序B.直接插入排序C.二路归并排序D.简单选择排序EF（1）其比较次数与序列初态无关的算法是 在初始序列已基本有序（除去n个元素中的k个元素后即呈有序k<n）的情下，排序效率最的算法是（ ） A．插 B.选 C.冒 D.快 B.插入排序法 C.快速排序法 D.堆积排序法 B.二分法插入 C.快速排序 D.归并排序在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（）A．直接插入排序B.气泡排 C.快速排 D.直接选择排1616BCD B.C. ABC对一组数据（84，47，25，1521）排序，数据的排列次序在排序的过程中的变化为（1）8447251521（2）1547258421（3）1521258447（4）212547则采用的排序是 )A.选 B.冒 C.快 D.插 ）排序。A.选 B.快 D A．选 B. C.直接插 D.冒A.快速排序B.s排序C.堆排序D下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位上。A.选 B.冒 C.归 D.下列序列中 A.[68，11，18，69] B.[68，11，69，23]C.[93，73][68，11，69，23，18] D.[68，11，69，23，18][93， ） B. D. )排 B.堆排 C.选择排 D.归并排 冒泡 C.快速D.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ ）。A.直接插入排序B.快速排序C.直接选择排 30.对初始状态为递增序列的表按递增顺序排序，最省时间的是（ A.堆排 B.快速排 C.插入排 D.归并排31A.冒泡B.希尔插入C.交换D A．起泡排 B．快速排列排序D．堆排序E33法是 A．直接插入排序B．冒泡排序C34．下列排序算法中34．下列排序算法中）A.堆排序 B.冒泡排序 C.快速排序 D.插入排下列排序算法中，占用辅助空间最多的是： )A.归并排B.快速排 排 D.堆排从未排序序列中依次取出一个元素与已排序序列中的元素依次进行AB37.在排序算法中，每次从未排序的记录中挑出最小（或最大）字的记录，加入到已排序记录的末尾，该排序方法是 ）A.选 B.冒 C.插 D.38．用直接插入排序方法对下面四个序列进行排序（由小到大），比较次数最少的是 ） CB．．D．39．直接插入排序在最好情况下的时间复杂度为A．D．B．）C．4010,14,26,29,41,524010,14,26,29,41,52进行A.B.C.D. 41.采用简单选择排序，比较次数与移动次数分别为 )A.D.B.C.42.对序列{15，9，7，8，20，-1，4，} A. B. C. D. ）A．{21,25,5,17,9,23,30}C．{21,9,17,30,25,23,5}Ｄ．44．对关键码序列28，16，3212，60，2，572快速排序，从小到大一次划分结果为（ ）。A.(2,5,12,16)26(60,32,72)B.C.(2,16,12,5)28(60,32,72)D. AB．每次分区后，先处理较长的部分C．与算法每次分区后的处理顺序无关D．以上三者都不对46．当n个整型数据是有序时，对这n46．当n个整型数据是有序时，对这n间复杂度是(6)，当用递归算法求n76)-(7)=（）A D. B.A．O(NlogN)B．O(N2)C．O(N3)D．堆排序E．冒泡排序F48.快速排序方法在 ）情况下最不利于发挥其长处A.要排序的数据量太 B.要排序的数据中含有多个相同C.要排序的数据个数为奇数D在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能 在（）位置上。 B．n/2- D．n/2 B.D.51．下列四个序列中，哪一个是堆 ）A. B.C. D.52.堆排序是52.堆排序是）加 空间复杂度分别是A.插入 B.交换F.O（n2）和HO（nlogn）和CD.基 G.O（nlogn）和O（n2）和 ）A.O(logn)B.O(1)C.O(n)D.对n个记录的文件进行堆排序 情况下的执行时间是多少 A．O（logn）B．O（n）C．O（nlogn）法建立的初始堆为 A．-1，4，8，9，20，7，15，7B．-1，7，15，7，4，8，20，9C．-1，4，7，8，20，15，7，9D．A，B，C均不对。归并排序中，归并的趟数是 )A．O（nB．C． A．插入排序B．枚举排序C．选择排序D．交换排序就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（ ）ABD已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端；交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二（1）--B．快速排 C．插入排排序G当待排序的元当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（ ）内排序要求数据一定要以顺序方 。 排序算法中的比较次数与初始元素序列的排列无关。排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ）在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（）直接选择排序算法在最好情况下的时间复杂度为O（N）。（8．在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog8．在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlogn ）10序的执行时间最省。 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 和记录的 。外排序的基本操作过程 属于不稳定排序的 属于不稳定排序的 分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是 算法，最费时间的是 算法。 用链表表示的数据的简单选择排序，结点的域为数据域data，指针域next；链表首指针为head，链表无头结点。while {q=p; ){if )q=r; ;}tmp=q->data;q->data=p->data;p->data=tmp;p= ;}9．下面的9．下面的c函数实现对链表hed大#includetypedefstructnode{chardata;structnode*link;}node;node*select(node*head){node*p,*q,*r,*s;p=(node*)malloc(sizeof(node));p->link=head;head=p;{q=p->link;r=p;while((1){if(q->link->data<r->link->data)r=q;q=q->link;}if((2)){s=r->link;r->link=s->link;s->link=((3) );((4) ((5));}p=head;head=head->link;(p);}给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：归并排 每归并一次书写一个次序快速排 每划分一次书写一个次序堆排序 先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次基础基础与理论环节——基本概念和算法思路第一章第三章栈第四章第六章图及应用第七章查找第八章第九章—选择题散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关，则选择好（ ）方法是散列文的关键。A.散列函数B.除余法中的质数C.处理D.散列函数和处顺序文件采用顺序结构实现文件的，对大型的顺序文件的少量修改，要求重整个文件，价很高，采（ ）的方法可降低需的代价。A.附加文件B.按关键字大小排序C.按记录输入先后排序D 4．下述文件中适合于磁带的是4．下述文件中适合于磁带的是 ）A.顺序文件B.索引文件C.散列文件D ）顺序文 B.索引文6.ISAM文件和VASM文件属于 ）A.索引非顺序文件B.索引顺序文件C.顺序文 D.散列文 ）文件系统中 B. 文件 两种文件 文件 两种文件单关键字文 多关键字文3.从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如dBASE中数据库文件那样的文件组织结构，称为(1文件；另一种是诸如用各种文字处理软件编辑成的文本文件，称为_2文件。从文件在器上的存放方式来看，文件的物理结构往往可区分为三类，即(3)_，_(4和5)_。B适用于组织(6)_的索引结构，mB_(7)_个儿子，除根结点外每个结点至少有(8(9个儿子，有k个儿子的结点必有(10)个关键码。3.从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如dBASE3.从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如dBASE中数据库文件那样的文件组织结构，称为(1)文件；另一种是诸如用各种文字处理软件编辑成的文本文件，称为_2文件。从文件在器上的存放方式来看，文件的物理结构往往可区分为三类，即(3)_，_(4和5)_。B适用于组织(6)_的索引结构，m阶B+树每个结点至多有_(7)_个儿子，除根结点外每个结点至少有(8(9个儿子，有k个儿子的结点必有(10)个关键码。（1）数据库（2）文本（3）顺序组织（4）随机组织（5）链组织（6）随机组织（7）m （8）m/2（9）2（10）k文件 组成；记录 组成 个记录 存取 文件 文件 组成；记录 组成记 数据 个记录 存取 索引顺序文件是最常用的文件组织之一，通常用 检，也可以 检索； 检索又可以 检索 检索索引顺序文件是最常用的文件组织之一，通常用索引顺序文件是最常用的文件组织之一，通常用树 检 和 构成的VSAM(虚拟存取方法)文件的优点是：动态地 和 构成的VSAM(虚拟存取方法)文件的优点是：动态地 和 构造散列函数解决的方 构成的索引集顺序集数据集VSAM(虚拟存取方法)文件的优点是：动态 ，不需要文件进 ，分配和释放空 重 顺序结构，相应文件为顺序文件，其记录按存入文件的先后次序顺序存放。顺序文件本质上就是顺序表。若逻辑上相邻的两个记录在位置上相邻，则为连续文件；若记录之间以指针相，则称为串联文件。顺序文件只能顺序存取，更新某个记录，必须带索引的结构，相应文件为索引文件。索引文件包括索引表和数据表，索引表中的索引项包括数据表中数据的关键字和相应地址，索引表有序，其物理顺序体现了文件的逻辑次序，实现了文件的线性结构。索引文件只能是磁盘文件，既能顺序存取，又能隋机存取。散列结构，也称计算寻址结构，相应文件称为散列文件，其记录是根据关键字值经散列函数计算确定地址，