数据结构导论2001年7月试题

二00一年下半年全国高等教育自学考试数据结构导论试卷一、单项选择题1.若给定有n个元素的向量,则建立一个有序单向链表的时间复杂性的量级是()A.O(1)B.O(n)C.O(n2)D.O(nlog2n)2.在一个具有n个结点的单链表达中查找值为m的某结点,若查找成功，则平均比较（）A．nB.n/2C.(n-1)/2D.(n+1)/23．研究数据结构就是研究（）A.数据的逻辑结构B.数据的存储结构C.数据的逻辑结构和存储结构D.数据的逻辑结构,存储结构及其数据在运算上的实现4.为了方便地对图状结构的数据进行存取操作，则其数据存储结构宜采用（）方式。A、顺序存储B、链式存储C、索引存储D、散列存储5．二维数组A[10……20，5……10]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[10，5]的存储地址是1000，则A[18，9]的地址是（）A、1208B、1212C、1368D、13646．设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有（）个结点。A、13B、12C、26D、257．下列几种结构中属于树型结构的是（）A、B、C、D、8．设无向图G=（V、E）和G’=（V’，E’），如G’为G的生成树，则下面不正确的说法是（）A、G’为G的连通分量B、G’为G的无环子图C、G’为G的子图D、G’为G的极小连通子图且V’=V9．下列说法中不正确的是（）A、无向图的极大连通子图称为连通分量B、连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C、图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D、有向图的遍历不可采用广度优先搜索方法10．对有序表（18，20，25，34，48，62，74，85）用二分查找法查找85，所需的比较次数为（）A、1次B、2次C、3次D、4次11．散列表的平均查找长度（）A、与处理冲突方法有关而与表的长度无关B、与处理冲突方法无关而与表的长度有关C、与处理冲突方法有关且与表的长度有关D、与处理冲突方法无关且与表的长度无关12．对ISAM文件的删除记录时，一般（）A、只需做删除标志B、需移动记录C、需改变指针D、一旦删除就需做整理13．顺序文件适宜于（）A、直接存取B、成批处理C、按关键字存取D、随机存取14．一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用（）方法。A、快速排序B、堆排序C、插入排序D、二路归并排序15．对下列四个序列用快速排序方法进行排序，以序列的第一个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是序列（）A、70，75，82，90，23，16，10，68B、70，75，68，23，10，16，90，82C、82，75，70，16，10，90，68，23D、23，10，16，70，82，75，68，90二、填空题1．下列程序段的时间复杂性的量级为0（m*n）for(i=0;im;i++)for(j=0;jn;j++)t=t+1;2．索引文件由索引表和主文件两部分组成。3．在一个不带有头结点的非空单链表中，其结点形式为data|next，若要在指针q所指结点之后插入一个结点，则需执行下列语句序列：p=malloc(size);p-data=x;p-next=q-next;q-next=p;4．设链栈的栈顶指针为Is，栈不空的条件为Is！=NULL或等价叙述5．遍历图的基本方法有深度优先搜索和广度优先搜索。其中，深度优先搜索是一个递归过程。6．如图所示，设输入元素的顺序为1，2，3，4，5，要在栈S的输出端得到序列43521，则应进行的操作用栈的基本运算表示应为push（S,1），push（S,2），push（S,3），push（S,4），pop(S)，pop(S)，push(S,5),pop(S),pop(S),pop(S)。7．下图为某树的静态双亲链表表示：则结点D、E的双亲结点分别为B、C8．在下列树中，结点H的祖先为A、D、G9．静态查找表的顺序查找算法中，通常采用设置岗哨的方式以确保查找不成功时循环也能终止执行，若给定值为K，表的长度为n，查找表的数据单元用R.item表示，键值用key表示，则在表尾设置岗哨的相应方法描述为R.item[n+1].key=K10．对于二叉树的查找，若根结点元素的键值大于被查找元素的键值，则应该在该二叉树的左子树上继续查找。11．采用二次探测法解决冲突问题，对于键值为K，容量为m的闭散列表，若散列地址为d0，则发生冲突后，其第三个后继散列地址d3为(d0+22)modm12．对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到已排序的有序表时，为寻找其插入位置需比较3次。13．对n个元素进行冒泡排序时，最少的比较次数是n-1三．应用题0A-11B02C03D14E212345输出端输入端栈SABCDEFGHpop(S)，pop(S)，Ipop(S)，pop(S)，1．已知序列（17，18，60，40，7，32，73，65，85），请给出采用冒泡排序法对该序列作升序排序时每一趟的过程。解：依题意：初始（17，18，60，40，7，32，73，65，85）1趟（17，18，40，7，32，60，65，73，85）2趟（17，18，7，32，40，60，65，73，85）3趟（17，7，18，32，40，60，65，73，85）4趟（7，17，18，32，40，60，65，73，85）5趟（7，17，18，32，40，60，65，73，85）第5趟元素未交换，则排序结束。2．如图所示，在栈的输入端有6个元素，顺序为A、B、C、D、E、F。能否在栈的输出端得到序列DCFEBA及EDBFCA？若能，给出栈操作的过程，若不能，简述其理由。解：（1）能得到序列DCFEBA操作过程如下：push,push,push,push,pop,pop,push,push,pop,pop,pop,pop（2）不能得到EDBFCA因为要得到E需将A，B，C，D顺序入栈，根据LIFO原则，不可能B在C之前出栈。3．分别写出下列二叉树的先根、中根、后根遍历序列。解：先根遍历序列：ABCDFGHE中根遍历序列：BADGFHCE后根遍历序列：BGHFDECA4．已知无向图G的邻接表如下，请写出其从顶点V2开始的深度优先搜索序列。解：V2V4V0V1V3ABCDEF输出端输入端栈ABCDEFGHV0V1V4V2V3104104^314223^^^^r-lchild=x;}2．已知奇偶转换排序如下所述：第一趟对所有奇数i，将a[i]和a[i+1]进行比较，第二趟对所有偶数i，将a[i]和a[i+1]进行比较，每次比较时若a[i]a[i+1]，则将两者交换，以后重复上述二趟过程交替进行，直至整个数组有序。（1）试问：排序结束的条件是什么？（2）编写一个实现上述排序过程的算法：voidoesort(inta[],intn)。解：（1）在一趟奇排序和一趟偶排序时均不发生数据交换。（2）voidoesort（inta[],intn）{inti,flag,t;do{flag=0;for(i=1;in;i++){if(a[i]a[i+1]){flag=1;t=a[i+1];a[i+1]=a[i];a[i]=t;}i++;}}while(flag!=0);}