全国2008年10月高等教育自学考试数据结构导论试题
课程代码:02142

一、单项选择题(本大题共15小题,每小题2分,共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内.错选、多选或未选均无分.
1.从逻辑上可以把数据结构分为（　　）
A.动态结构、静态结构
B.顺序结构、链式结构
C.线性结构、非线性结构
D.初等结构、构造型结构

2.关于算法的描述,不正确的是（　　）
A.算法最终必须由计算机程序实现
B.所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界
C.健壮的算法不会因非法的输入数据而出现莫名其妙的状态
D.算法的优劣与算法描述语言无关

3.在单链表中,存储每个结点需要有两个域,一个是数据域,另一个是指针域,指针域指向该结点的（　　）
A.直接前趋
B.直接后继
C.开始结点
D.终端结点

4.将两个各有n个元素的有序表合并成一个有序表,其最少的比较次数为（　　）
A.n
B.2n-1
C.2n
D.n2

5.栈和队列共同具有的特点是（　　）
A.都是先进后出
B.都是先进先出
C.只允许在端点进行操作运算
D.既能先进先出,也能先进后出

6.若用一个有6个单元的数组来实现循环队列,rear和front的初值分别为0和3.则从队列中删除一个元素,再添加两个元素后,rear和front的值分别为（　　）
A.1和5
B.2和4
C.4和2
D.5和1

7.数组A[0..5][0..5]的每个元素占5个字节,将其以列为主序存储在起始地址为1000的内存单元中,则元素A［5］［5］的地址是（　　）
A.1175
B.1180
C.1205
D.1210

8.含有n个结点的二叉树采用二叉链表存储时,空指针域的个数为（　　）
A.n-1
B.n
C.n+1
D.n+2

9.在一棵深度为H的完全二叉树中,所含结点的个数不少于（　　）
A.2H-1-1
B.2H-1
C.2H-1
D.2H

10.一个具有n个顶点的无向连通图,它所包含的连通分量数为（　　）
A.0
B.1
C.n
D.不确定

11.下列说法中不正确的是（　　）
A.无向图的极大连通子图称为连通分量
B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
C.连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
D.有向图的遍历不可采用广度优先搜索算法

12.对一棵二叉排序树采用中根遍历进行输出的数据一定是（　　）
A.递增或递减序列
B.递减序列
C.无序序列
D.递增序列

13.一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时,查找成功时的比较次数为（　　）
A.1
B.2
C.4
D.8

14.一组记录的关键字为{45,80,55,40,42,85},则利用堆排序的方法建立的初始堆为（　　）
A.80,45,55,40,42,85
B.85,80,55,40,42,45
C.85,80,55,45,42,40
D.85,55,80,42,45,40

15.关于VSAM文件存取操作的说法,正确的是（　　）
A.不能顺序存取,只能按关键字随机存取
B.不能顺序存取,不能按关键字随机存取
C.只能顺序存取,不能按关键字随机存取
D.既能顺序存取,也能按关键字随机存取

二、填空题(本大题共13小题,每小题2分,共26分)
请在每小题的空格中填上正确答案.错填、不填均无分.
16.在任何问题中,数据元素都不是孤立的,它们之间总存在某种关系,通常称这种关系为________.
17.存储结点之间通常有四种基本存储方式,即顺序存储方式、索引存储方式、________和散列存储方式.
18.在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时,需向后移动________个元素.
19.对一棵深度为10的满二叉树按层编号,则编号为51的结点,它的双亲结点编号为________.
20.用S表示入栈操作,X表示出栈操作,若元素入栈顺序为1234,为了得到1342的出栈顺序,相应的S和X操作串为________.
21.具有n个叶子结点的哈夫曼树,其结点总数为________.
22.一棵具有n个结点的树,所有非终端结点的度均为k,则该树中叶子结点个数为________.
23.在无向图G的邻接矩阵A中,若A[i][j]等于0,则A[j][i]等于________.
24.两个串是相等的,当且仅当两个串的长度相等且________的字符都相同.
25.某二叉树的后根遍历序列为abd,中根遍历序列为adb,则它的先根遍历序列为________.
26.先在所有的记录中选出键值最小的记录,将它与第一个记录交换；然后在其余的记录中再选出最小的记录与第二个记录交换,依此类推,直至所有记录排序完成.这种排序方法称为________.
27.对含有n个结点e条边的无向连通图,利用prim算法生成最小生成树的时间复杂度为________.
28.对n个元素进行冒泡排序时,最少的比较次数为________.

三、应用题(本大题共5小题,每小题6分,共30分)
29.设有编码为A,B,C,D的4列火车,依次进入一个栈式结构的站台,试写出这4列火车开出站台的所有可能的顺序.
30.画出题30图所示的二叉树的二叉链表存储结构.

题30图
31.对于题31图,试给出:
 
（1）邻接矩阵；
（2）邻接表.

题31图
32.给定表（39,14,22,8,65,28,88,29,67,13,10）,试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树,画出插入完成后的二叉排序树.
33.用插入排序算法对数据序列（47,33,61,82,72,11,25,57）进行排序,写出整个插入排序的每一趟过程.

四、算法设计题(本大题共2小题,每小题7分,共14分)
34.设两个数据元素均为整型数据的线性表A=(a1,a2,…,an)和B=(b1,b2,…,bm).若n=m且ai=bi（i=1,2,…,n）则认为A=B；若ai=bi（i=1,2,…,j）且aj+1B.试编写一个比较A和B的算法,当AB时,输出1.要求线性表的存储结构使用链接存储.
35.设二叉树的结点类型定义如下:
typedef struct node{
　　　　datatype data;
　　　　struct node*lchild,*rchild;
　　　　}Bitree;
Bitree*t;
试编写一个计算二叉树深度的递归算法(int Depth(Bitree*t)).