2002年下半年全国高等教育自学考试

数据结构导论

（课程代号：2142）

一、单项选择题（在下列每小题四个备选答案中选出一个正确答案，并将其字母标号填入题干的括号内。每小题2分，共30分）

1.下列数据组织形式中，( )的结点按逻辑关系依次排列形成一个"锁链"。
A.集合     B.树形结构     C.线性结构     D.图状结构

2.数据结构可以形式化地定义为(S，△)，其中S指某种逻辑结构，△是指( )
A. S上的算法     B. S的存储结构
C. 在S上的一个基本运算集     D. 在S上的所有数据元素

3.下列说法正确的是( )
A.线性表的逻辑顺序与存储顺序总是一致的
B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续
C.线性表的线性存储结构优于链式存储结构
D.每种数据结构都具有插入、删除和查找三种基本运算

4.设非空单链表的数据域为data，指针域为next，指针p指向单链表中第i个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为第i个结点，下列算法段能正确完成上述要求的是( )
A. s－＞next=p－＞next; p－＞next=s;
B. p－＞next=s; s－＞next=p－＞next;
C. s－＞next=p－＞next; p－＞next=s; 交换p－＞data和s－＞data;
D. p=s; s－＞next=p;

5.稀疏矩阵一般采用( )方法压缩存储。
A.三维数组     B.单链表     C.三元组表     D.散列表

6.树若用双亲链表表示，则( )
A.可容易地实现求双亲及子孙的运算
B.求双亲及子孙的运算均较困难
C.可容易地实现求双亲运算，但求子孙运算较困难
D.可容易地实现求子孙运算，但求双亲运算较困难

7.将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点( )
A.无左、右孩子     B.有左孩子，无右孩子
C.有右孩子，无左孩子     D.有左、右孩子

8.用邻接表作为有向图G的存储结构。设有n个顶点、e条弧，则拓扑排序的时间复杂度为( )
A. O(n)     B. O(n+e)     C. O(e)     D. O(n*e)

9.如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是( )
A.完全图     B.连通图     C.有回路     D.一棵树

10.采用线性探测法解决冲突问题，所产生的一系列后继散列地址( )
A.必须大于等于原散列地址
B.必须小于等于原散列地址
C.可以大于或小于但不能等于原散列地址
D.地址大小没有具体限制

11.在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于( )
A.静态查找表     B.动态查找表
C.静态查找表与动态查找表     D.两种表都不适合

12.由索引集、顺序集和数据集三部分组成的文件称为( )
A. VSAM文件     B.散列文件     C.顺序文件     D.索引文件

13.下列有关散列文件的说法中不正确的是( )
A.散列文件具有随机存放的优点
B.散列文件只能按关键字存取
C.散列文件需要索引区
D.散列文件的记录不需要进行排序

14.一组记录的键值为(12，38，35，25，74，50，63，90)，按2路归并排序方法对该序列进行一趟归并后的结果为( )
A. 12，38，25，35，50，74，63，90    B. 12，38，35，25，74，50，63，90
C. 12，25，35，38，50，74，63，90    D. 12，35，38，25，63，50，74，90

15.用快速排序方法对包含有n个关键的序列进行排序，最坏情况下执行的时间杂度为( )
A. O(n) B. O(log₂n)     C. O(nlog₂n)     D. O(n²)

二、填空题(每空2分，共26分)

1.定义在线性表上的初始化、查找、插入和删除运算中，          是引用型运算。

2.线性表(a₀,a₁,a₂,…,a_n) (n≥1)中，每个元素占c个存储单元，m为a₀的首地址，则按顺序存储方式存储线性表，a_n的存储地址是          。

3.在栈的顺序实现中，设栈顶指针为top，栈空的条件为          。

4.队列中允许进行插入的一端称为          。

5.深度为90的满二叉树上，第11层有          个结点。

6.给定n个值构造哈夫曼树。根据哈夫曼算法，初始森林中共有n棵二叉树，经过          次合并后才能使森林中的二叉树的数目由n棵减少到只剩下一棵最终的哈夫曼树。

7.设无向图G的顶点数为n，则G最少有          条边。

8.通常采用拉链法、线性探测法、多重散列法、二次探测法、公共溢出区法等解决散列地址冲突问题，若要避免"堆积"现象发生应采用          法。

9.对有序表(25，30，32，38，47，54，62，68，90，95)用二分查找法查找32，则所需的比较次数为          。

10.树型结构结点间通过"父子"关系相互关联，这种相互关联构成了数据间的          关系。

11.文件的检索有顺序存取、直接存取和          三种方式。

12.第i趟在n-i+l (i=1，2，…，n-l)个记录中选取键值最小的记录作为有序序列的第i个记录。这样的排序方法称为          。

13.在堆排序和快速排序中，若原始记录已基本有序，则较适合选用          。

三、应用题（共30分）

1.设有字符串为 3 * - y - a / y ∧ 2 ，试利用栈写出将其转换为 3 y - * a y 2 ∧ / - 的操作步骤。假定用 X 代表扫描该字符串过程中顺序取一个字符进栈的操作，用 S 代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC 变为 BCA 的操作步骤为 XXSXSS 。（5分）

2.现有某二叉树，按先根遍历的序列为ABDEFCGH，按中根遍历的序列为DEFBGHCA，试画出此二叉树。(6分)

3.给定表（19，22，18，15，30，20，42，35，16），按数据元素在表中的次序构造一棵二叉排序树。（6分）

4.已知序列（70，83，100，65，10，32，7，9），请给出采用直接插入排序法对该序列作升序排序时的每一趟的结果。（7分）

5.已知无向图G的邻接表如下，请画出其所有的连通分量。（6分）

四、设计题（共14分）

1.设字符串仅由圆括号“（”和“）”，方括号“[”和“]”，花括号“{”和“}”组成，利用链栈的操作编写一个检查括号是否正确配对的算法：int Matcher(LStackTP *ls)。例如，[{{（）}[]}（）{[]}]是正确的，而{（{（）[]}）}]）}则不正确。设链栈定义如下：（6分）

typedef struct node
{   char data;
    struct node *next;
} LStackTp;

2.利用一维数组a可以对n个整数进行排序，其中一种排序算法的处理思想是：将n个整数分别作为数组a的n个元素值，每次（即第i次）从元素a[i]到a[n]中挑出最小的一个元素a[k](i≤k≤n)，然后将a[k]与a[i]换位。这样反复n-1次完成排序。编写实现上述算法的函数：void sort(int a[],int n)。（8分）