数据结构导论年月试题.docVIP

二00年下半年全国高等教育自学考试 数据结构导论试卷 一、单项选择题 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’=V 9．下列说法中不正确的是（ ） 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，68 B、70，75，68，23，10，16，90，82 C、82，75，70，16，10，90，68，23 D、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．下图为某树的静态双亲链表表示： 0 A -1 1 B 0 2 C 0 3 D 1 4 E 2 则结点D、E的双亲结点分别为 B、C 8．在下列树中，结点H的祖先为 A、D、G 9．静态查找表的顺序查找算法中，通常采用设置岗哨的方式以确保查找不成功时循环也能终止执行，若给定值为K，表的长度为n，查找表的数据单元用R.item表示，键值用key表示，则在表尾设置岗哨的相应方法描述为 R.item[n+1].key=K 10．对于二叉树的查找，若根结点元素的键值大于被查找元素的键值，则应该在该二叉树的 左子树 上继续查找。 11．采用二次探测法解决冲突问题，对于键值为K，容量为m的闭散列表，若散列地址为d0，则发生冲突后，其第三个后继散列地址d3为 (d0+22) mod m 12．对一组记录（54，38，96，23