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

一、单项选择题(本大题共15小题,每小题2分,共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内.错选、多选或未选均无分.
1.下列描述中正确的是( )
A.数据元素是数据的最小单位
B.数据结构是具有结构的数据对象
C.数据结构是指相互之间存在一种或多种特定关系的数据元素的集合
D.算法和程序原则上没有区别,在讨论数据结构时两者是通用的
2.归并排序的时间复杂度是( )
A.O（n2）
B.O（nlog2n）
C.O（n）
D.O（log2n）
3.二分查找的时间复杂度是( )
A.O（n2）
B.O（nlog2n）
C.O（n）
D.O（log2n）
4.顺序存储的表中有90000个元素,已按关键字值升序排列,假设对每个元素进行查找的概率相同,且每个元素的关键字值皆不相同,用顺序查找法查找时,需平均比较的次数为( )
A.25000
B.30000
C.45000
D.90000
5.散列文件是一种( )
A.顺序文件
B.索引文件
C.链接文件
D.计算寻址文件
6.两个矩阵A:m×n,B:n×p相乘,其时间复杂度为( )
A.O(n)
B.O(mnp)
C.O(n2)
D.O（mp）
7.常用于函数调用的数据结构是( )
A.栈
B.队列
C.链表
D.数组
8.二维数组A［n］［m］以列优先顺序存储,数组A中每个元素占用1个字节,A［1］［1］为首元素,其地址为0,则元素A［i］［j］的地址为( )
A.（i-1）×m+(j-1)
B.(j-1)×n+(i-1)
C.(j-1)×n+i
D.j×n+i
9.图的广度优先搜索使用的数据结构是( )
A.队列
B.树
C.栈
D.集合
10.序列（21,19,37,5,2）经冒泡排序法由小到大排序,在第一次执行交换后所得结果为( )
A.(19,21,37,5,2)
B.(21,19,5,37,2)
C.(21,19,37,2,5)
D.(2,21,19,37,5)
11.数据在计算机存储器内表示时,根据结点的关键字直接计算出该结点的存储地址,这种方法称为( )
A.索引存储方法
B.顺序存储方法
C.链式存储方法
D.散列存储方法
12.在单链表中,存储每个结点有两个域,一个是数据域,另一个是指针域,指针域指向该结点的( )
A.直接前趋
B.直接后继
C.开始结点
D.终端结点
13.在已知头指针的单链表中,要在其尾部插入一新结点,其算法所需的时间复杂度为( )
A.O（1）
B.O（log2n）
C.O（n）
D.O（n2）
14.在链队列中执行入队操作,( )
A.需判别队是否空
B.需判别队是否满
C.限制在链表头p进行
D.限制在链表尾p进行
15.一整数序列26,59,77,31,51,11,19,42,以二路归并排序从小到大排序,第一阶段的归并结果为( )
A.31,51,11,42,26,77,59,19
B.26,59,31,77,11,51,19,42
C.11,19,26,31,42,59,51,77
D.26,11,19,31,51,59,77,42
二、填空题(本大题共13小题,每小题2分,共26分)
请在每小题的空格中填上正确答案.错填、不填均无分.
16.下列程序段的时间复杂度为_______.
i=0；s=0；
while（s<n）
{i++；
s=s+i；
}
17.数据的存储结构被分为顺序存储结构、_______、散列存储结构和索引存储结构4种.
18.从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时,需向前移动_______个元素.
19.在单链表中,插入一个新结点需修改_______个指针.
20.在队列结构中,允许插入的一端称为_______.
21.稀疏矩阵采用的压缩存储方法是_______.
22.向一个栈顶指针为top的链栈中插入一个新结点*p时,应执行p->next=top和_______操作.
23.有m个叶结点的哈夫曼树所具有的结点数为_______.
24.在一棵具有n个结点的完全二叉树中,从树根起,自上而下、自左至右地给所有结点编号.设根结点编号为1.若编号为i的结点有右孩子,那么其右孩子的编号为_______.
25.在一棵树中,_______结点没有前驱结点.
26.一个具有n个顶点的有向完全图的弧数是_______.
27.n个顶点的无向图G用邻接矩阵A［n］［n］存储,其中第i列的所有元素之和等于顶点Vi的_______.
28.选择排序的平均时间复杂度为_______.
三、应用题(本大题共5小题,每小题6分,共30分)
29.在栈的输入端元素的输入顺序为1,2,3,4,5,6,进栈过程中可以退栈,则退栈时能否排成序列3,2,5,6,4,1和1,5,4,6,2,3,若能,写出进栈、退栈过程,若不能,简述理由.（用push（x）表示x进栈,pop(x)表示x退栈）
30.已知一棵二叉树的中根遍历序列为CBEDFAGH,后根遍历序列为CEFDBHGA,画出该二叉树.
31.给定表（15,11,8,20,14,13）,试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树,画出插入完成后的二叉排序树,并判断该二叉排序树是否为平衡二叉排序树,若为非平衡二叉排序树,将它调整为平衡二叉排序树.
32.如题32图所示无向图,（1）写出其邻接矩阵；（2）写出三种以顶点A为起点的深度优

题32图
33.用冒泡排序法对数据序列（49,38,65,97,76,134,27,49）进行排序,写出排序过程.并说明冒泡排序是否为稳定排序.
四、算法设计题(本大题共2小题,每小题7分,共14分)
34.编写计算二叉树中叶子结点数目的算法.
35.开散列表的类型定义如下:
typedef struct tagnode
{keytype key;
struct tagnode*next;
}*pointer,node;
typedef pointer openhash［n］;
试写出开散列表上的查找算法.