全国自考（数据结构）模拟试卷4
一、1.单项选择题
0. 对文件进行直接存取的是根据( )
A．逻辑记录号去存取某个记录
B．逻辑记录的关键字去存取某个记录
C．逻辑记录的结构去存取某个记录
D．逻辑记录的具体内容去存取某个记录
1. 一个栈的人栈序列是a,b,c,d,e，则栈的不可能的输出序列是( )
A．e d c b a
B．d e c b a
C．d c e a b
D．a b c d e
2. 带头结点的单链表head为空的判断条件是( )
A．head=NULL
B．head—＞next=NULL
C．head—＞next=head
D．head!=NULL
3. 非空的单循环链表L的尾结点P↑，满足( )
A．P↑.next=NULL;
B．P=NULL;
C．P↑.next=L;
D．P=L
4. 在下面的排序方法中，不需要通过比较关键字就能进行排序的是( )
A．箱排序
B．快速排序
C．插入排序
D．希尔排序
5. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着( )
A．数据元素具有同一特点
B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C．每个数据元素都一样
D．数据元素所包含的数据项的个数要相等
6. 从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较( )个结点。
A．n
B．n/2
C．(n-1)/2
D．(n+1)/2
7. 在一个链队列中，若f，r分别为队首、队尾指针，则插入s所指结点的操作为( )
A．f—＞next=c;f=s;
B．r—＞next=s;r=s;
C．s—＞next=r;r= s
D．s—＞next=f,f=s;
8. 设散列函数为H(k)=k mod7，一组关键码为23,14,9,6,30,12和18，散列表T的地址空间为0.6，用线性探测法解决冲突，依次将这组关键码插入T中，得到的散列表为( )
9. 邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的( )
A．先序遍历
B．中序遍历
C．后序遍历
D．按层遍历
10. 线索二叉树是一种( )结构。
A．物理
B．逻辑
C．存储
D．线性
11. 排序的重要目的是为了以后对已排序的数据元素进行( )
A．打印输出
B．分类
C．查找
D．合并
12. 在一非空二叉树的中序遍历序列中，根结点的右边( )
A．只有右子树上的所有结点
B．只有右子树上的部分结点
C．只有左子树上的所有结点
D．只有左子树上的部分结点
13. 设图G采用邻接表存储，则拓扑排序算法的时间复杂度为( )
A．O(n)
B．O(n+e)
C．O(n2)
D．O(n×e)
14. 在下面的排序方法中，属于不稳定的排序方法的是( )
A．直接插入排序
B．冒泡法排序
C．堆排序
D．归并排序
二、2.填空题
0. 对于一个具有n个结点的单链表，在已知p结点后插入一个新结点的事件的时间复杂性为______，在给定值为x的结点后插入一个新结点的时间复杂性为______。
1. 设有两个串p和q，求q在p中首次出现的位置的运算叫______。
2. 对于一个长度为n的线性表，假设表中各结点的查找概率相同，则在查找成功的情况下，平均查找长度为______，如果k不在表中，则需要进行______次比较后才能确定查找失败。
3. 在二叉排序树中，其左子树中任何一个结点的关键字一定______其右子树的各结点的关键字。
4. 数组0[1……n]表示一个环形队列，设f的值为队列中第一个元素的位置，r的值为队列中实际队尾元素的位置加1，并假定队列中至多只有n-1个元素，则计算队列中元素个数的公式为______。
5. 一般来说，数组中的元素具有______的数据类型，并且数组元素的下标的上界和下界都是______的。
6. 一个n×n的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为______。
7. 性表的顺序存储中，假设每个结点所占用的存储空间为c，且第一个单元的存储地址则是该结点的存储地址，设开始结点a1的存储地址是LOC(a1)，则结点a1存储地址LOC(a1)可以通过下式得到______。
8. 在具有n个单元的循环队列中，队满时共有______个元素。
9. 查找表按其所包括的运算的不同分为______查找表和______查找表。
三、3.解答题
0. 请根据下面所给出的邻接矩阵画出相应的有向图或者是无向图(顶点vi表示)。
1. 对于如下一个有序的关键字序列{5,9,12,18,23,31,37,46,59,66,71,78,85)，现在要求用二分法进行查找值为18的关键字，则经过几次比较之后能查找成功?
2. 已知有一关键字序列为{505,94,512,61,908,170,897,275,653,463)，如果我们采用快速法对此序列进行排序(按照升序排序)，请给出每一趟排序的结果。
3. 已知数据序列为{12,5,9,20,6,31,24)，对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果。
四、4.算法阅读题
0. INITIATE()的功能是建立一个空表。请在______处填上正确的语句。
lklist initiate_lklist() /*建立一空表*/
{______;
______;
return(t);
}
1. 以下运算实现在顺序栈上的退栈，请在______处用适当的语句予以填充。
int Pop(SqStackTp*sq,DataType*x)
{ if(sq—＞top==0){error("下溢");return(0);)
else{*x=______;
______;
return(1);
}
}
2. 以下算法在开散列表HP中查找键值等于K的结点，成功时返回指向该点的指针，不成功时返回空指针。请分析程序，并在______上填充合适的语句。
pointer research_openhash(keytype K,openhash HP)
{ i=H(K); /*计算K的散列地址*/
p=HP[i]; /*i的同义词子表表头指针传给P*/
while(______)p=p—＞next; /*未达到表尾且未找到时，继续扫描*/
______;
}
3. 基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的列序来进行转置，请在______处用适当的语句予以填充。
Trans_Sparmat(SpMatrixTp a,SpMatrixTp*b)
{ (*b).mum=a.nu;(*b).nu=a.mu;(*b).tu=a.tu
if(a.tu)
{ q=1;
for(col=1;______;col++)
for(p=1;p＜=a.tu;p++)
if(______)==col)
{ (*b).data[q].i=a.data[p].j;
(*b).data[q].j=a.data[p].i;
(*b).data[q].v=a.data[p].v;
______;
}
}
}
五、5.算法设计题
0. 采用单链表作为存储结构，试编写一个函数来实现用选择排序方法进行升序排列。
