数据结构历年真题

C．（2，1，4，3，5，7，8，6） D．（8，7，6，5，4，3，2，1）

12．下列二叉树中，不平衡的二叉树是（ ） ．

13．下列序列中，不构成堆的是（ ） ．

A．（1，2，5，3，4，6，7，8，9，10）B．（10，5，8，4，2，6，7，1，3） C．（10，9，8，7，3，5，4，6，2）D．（1，2，3，4，10，9，8，7，6，5） 14．主关键字能唯一标识（ ） A．一个记录

B．一组记录C．一个类型 D．一个文件

15．稀疏索引是指在文件的索引表中（ ） A．为每个字段设一个索引项 C．为每组字段设一个索引项

B．为每个记录设一个索引项 D．为每组记录设一个索引项

二、填空题（本大题共10小题，每小题2分，共20分）

请在每小题的空格中填上正确答案。错填、不填均无分。

16．链式存储结构的特点是借助_______来表示数据元素之间的逻辑关系。

17．假设带头结点的非空单循环链表中仅设尾指针L，则在第1个结点之前插入指针s所指结点的语句依次是_______；_______。

18．无表头结点的链队列Q为空的条件是_______。 19．不含任何字符的串称为_______。 ．

20．假设按行优先顺序将一个20阶的三对角矩阵A压缩存储在一维数组Q中，其中Q[0]存放矩阵的第1个元素a1,1，那么矩阵元素a3,4在Q中的存储位置k=_______。

21．前序序列和中序序列不相同的二叉树的特征是_______。 ．

22．在含有n个顶点的连通图中，任意两个不同顶点之间的简单路径的最大长度为_______。

23．用_______排序方法对关键字序列（20，25，12，47，15，83，30，76）进行排序时，前三趟排序的结果为： 20，12，25，15，47，30，76，83 12，20，15，25，30，47，76，83 12，15，20，25，30，47，76，83

24．哈希表常用的两类解决冲突的方法是_______和_______。 25．倒排文件和多重表文件的主要区别在于_______的结构不同。 三、解答题（本大题共4小题，每小题5分，共20分）

26．已知主串为″ccgcgccgcgcbcb″，模式串为″cgcgcb″。下表所列为按照朴素的串匹配算法进行的前两趟匹配。请

全国2001年10月自考数据结构试题

37

继续完成余下各趟匹配，直至结束。

27．已知带权图G如图所示，画出图G的一棵最小生成树。

28．对于直接插入排序，希尔排序，冒泡排序，快速排序，直接选择排序，堆排序和归并排序等排序方法，分别写出： （1）平均时间复杂度低于O（n2）的排序方法； （2）所需辅助空间最多的排序方法；

（3）最好情况和最坏情况下的时间复杂度相同的排序方法。 29．已知一棵线索化的二叉排序树如图所示。 （1）说明该树的线索化是基于何种遍历次序的；

全国2001年10月自考数据结构试题

38

（2）在该树中插入元素值为53的结点并修改相应线索，画出修改之后的树。 （1） （2）

四、算法阅读题（本大题共4小题，每小题5分，共20分）

30．假设线性表采用顺序存储结构，表中元素值为整型。阅读算法f 30，并回答下列问题：（1）设顺序表L=(3,7,3,2,1,1,8,7,3),写出执行算法f 30后的L; （2）简述算法f 30的功能。 void f 30(SeqList *L) { int i,j,k;

k=0;

for(i=0;ilength;i++)

{ for(j=0;jdata[i]!=L->data[j];j++); if(j==k)

{ if(k!=i)L->data[k]=L->data[i]; k++; } }

L->length=k; }

31．阅读算法f 31,并回答下列问题：

（1）设队列Q=（1，3，5，2，4，6）。写出执行算法f 31后的队列Q; （2）简述算法f 31的功能。

void f 31(Queue *Q){ DataType e; if (!QueueEmpty(Q)){ e=DeQueue(Q); f 31(Q); EnQueue(Q,e);

全国2001年10月自考数据结构试题

39

} }

32．已知树的存储结构为孩子兄弟链表，其类型定义如下： typedef struct CSTNode { char data;

struct CSTNode leftmostchild,*rightsibling; } CSTNode, *CSTree;

阅读函数f 32,并回答下列问题：

（1）对于如图所示树，写出函数调用f 32(T)的返回值； （2）简述树T非空时函数f 32返回值的含义。

int f32(CSTree T){ int c; CSTree p;

if (!T->leftmostchild) return 1; else { c=0;

for(p=T->leftmostchild;p;p=p->rightsibling) c+=f32(p); return c; } } (1) (2)

33．已知数组R[1..p-1]中的元素序列为一个大根堆，函数Adjust(R,p)将R[1..p]重新调整为一个大根堆。（1）在函数Adjust的空缺处填入适当内容，使其成为一个完整的函数； （2）简述函数f33(R,n)的功能。

void Adjust(SeqList R,int p) { int i,j;

RecType temp=R[p]; i=p; j=i/2;

while(j>=1&& R[j].key

① ;

全国2001年10月自考数据结构试题

40