六、写算法（共20分） 1．参考答案：
template
void LinkList
if(la->next){
q=la->next->next;
la->next->next=NULL; while(q){
pre=la;p=la->next;x=q->data; while(p && x>=p->data){ pre=p; p=p->next; }//while t=q;
q=q->next; pre->next=t; t->next=p; }//while }//if
}//StraitInsertSort 2．参考答案：
template
void BiTree
visit(T->data);
PreOrder(T->lchild,Visit); T=T->rchild; }//while
}//PreOrder
模拟试卷八
一、 单项选择题(在下列每小题四个备选答案中选出一个正确答案，并将其字母标号填入题干的括号内。每小题2分，共30分)
1．若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是( )
A．O(1) B．O(n)
C．O(n2) D．O(nlog2n)
2．在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则平均比较( )个结点。
36
A．n B．n／2 C．(n-1)／2 D．(n+1)／2 3．研究数据结构就是研究( ) A．数据的逻辑结构 B．数据的存储结构
C．数据的逻辑结构和存储结构
D．数据的逻辑结构、存储结构及其数据在运算上的实现
4．为了方便地对图状结构的数据进行存取操作，则其数据存储结构宜采用( )方式。
A．顺序存储 B．链式存储 C．索引存储 D．散列存储
5．二维数组A[10．．20，5．．10]采用行序为主序方式存储，每个数据元素占4个存储单元，且[A10，5]的存储地址是1000，则A[18，9]的地址是( )
A．1208 B．1212 C．1368 D．1364
6．设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有( )个结点。
A．13 B．12 C．26 D．25
8.设无向图G=(V，E)和C’=(V’,E’)，如C’为G的生成树，则下面不正确的说法是( )
A. C’为C的连通分量 B．C’为C的无环子图 C．C’为C的子图
D. C’为C的极小连通子图且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．与处理冲突方法无关而与表的长度有关
37
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 二、填空题(每空2分，共26分)
1．下列程序段的时间复杂性的量级为__________。 for(i=0；i 2．索引文件由_________和主文件两部分组成。 3．在一个不带有头结点的非空单链表中，其结点形式为data next,若要在指针q所指结点之后插入一个结点，则需执行下列语句序列： p=malloc(size)；p->data=x；______________;q->next=p; 4．设链栈的栈顶指针为ls，栈不空的条件为___________5．遍历图的基本方法有深度优先搜索和广度优先搜索。其中，____________是一个递归过程。 7．下图为某树的静态双亲链表表示： 则结点D、E的双亲结点分别为_________。 38 0 A -1 1 B 0 2 C 0 3 D 1 4 E 2 9．静态查找表的顺序查找算法中，通常采用设置岗哨的方式以确保查找不成功时循环也能终止执行，若给定值为K，表的长度为n，查找表的数据单元用R.item表示，键值用key表示，则在表尾设置岗哨的相应方法描述为_________。 10．对于二叉排序树的查找，若根结点元素的键值大于被查找元素的键值，则应该在该二叉树的_________上继续查找。 11．采用二次探测法解决冲突问题，对于键值为K、容量为m的闭散列表，若散列地址为d0，则发生冲突后，其第三个后继散列地址d3为___________。 12．对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到已排序的有序表时，为寻找其插入位置需比较________次。 13.对n个元素进行冒泡排序时，最少的比较次数是___________。 三.应用题（共30分） 1．已知序列(17，18，60，40，7，32，73，65，85)，请给出采用冒泡排序 法对该序列作升序排序时每一趟的过程。(6分) 2．如图所示，在栈的输入端有6个元素，顺序为A，B，C，D，E，F能否在 栈的输出端得到序列DCFKBA及EDDFCA?若能，给出栈操作的过程，若不能，简述其理由。(8分) 39 5．设散列函数为H(K)=K mod 11，散列表长度为11(散列地址空间0．．10)，给定表(SUN，MON，TUE，WED，THU，FRI，SAT)中，取单词的第一个字母在英语字母表中的序号为键值K，构造一开散列表，并用拉链法解决有关地址冲突。(7分) 四、设计题（共14分） 1.设以二叉链表为二叉树的存储结构,结点的结构如下: lchild data rchild 求二叉树中叶子结点的数目 2.已知奇偶转换排序如下所述:第一趟对所有奇数i,a[i]和 a[i+1]进行比较,第二趟对所有偶数i,将a[i]和a[i+1]进行比较,每次比较时若a[i]>a[i+1],则将两者交换,以后重复上述二趟过程交替进行,直至整个数组有序。 （1） 试问：排序结束的条件是什么？（2分） 40