全国2005年10月高等教育自学考试数据结构导论试题
课程代码：02142
一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.若要描述数据处理的变化过程，其正确的次序应为(      )
A.处理要求、基本运算和运算、算法
B.处理要求、算法、基本运算和运算
C.基本运算和运算、处理要求、算法
D.算法、处理要求、基本运算和运算

2.从运算类型角度考虑，属于引用型的运算是(      )
A.插入、删除       
B.删除、修改
C.查找、读取       
D.查找、删除

3.若在长度为n的顺序表中插入一个结点，则其结点的移动次数(      )
A.最少为0，最多为n     
B.最少为1，最多为n
C.最少为0，最多为n+1    
D.最少为1，最多为n+1

4.在一个单链表中，若p所指结点是q所指结点的前驱结点，则在结点p、q之间插入结点s的正确操作是(      )
A.s->next=q；p->next=s->next
B.p->next=q；p->next=s
C.s->next=q->next；p->next=s
D.s->next=q->next；p->next=s->next

5.若有一串数字5、6、7、8入栈，则其不可能的输出序列为(      )
A.5、6、7、8       
B.8、7、6、5
C.8、7、5、6  &n来源:91 考试网bsp;    
D.5、6、8、7

6.FORTRAN语言对数组元素的存放方式通常采用(      )
A.按行为主的存储结构     
B.按列为主的存储结构
C.按行或列为主的存储结构    
D.按行和列为主的存储结构

7.树是n个结点的有穷集合，(      )
A.树的结点个数可以为0，此时称该树为空树
B.树至少含有一个根结点，不能为空
C.树至少含有一个根结点和一个叶子结点
D.树至少含有一个根结点和两个叶子结点

8.深度为k的二叉树至多有(      )
A.2k个叶子       
B.2k-1个叶子
C.2k-1个叶子       
D.2k-1-1个叶子

9.具有10个顶点的有向完全图应具有(      )
A.20条弧       
B.50条弧
C.90条弧       
D.100条弧

10.从V1出发，对题10图按广度优先搜索遍历，则可能得到的一种顶点序列为(      )
A.V1V2V3V5V4V6
B.V1V2V3V5V6V4
C.V1V5V2V3V6V4
D.V1V3V6V4V5V2

11.适用于静态的查找方法为(      )
A.二分查找、二叉排序树查找
B.二分查找、索引顺序表查找
C.二叉排序树查找、索引顺序表查找
D.二叉排序树查找、散列法查找

12.采用二分查找法，若当前取得的中间位置MID的元素值小于被查找值，则表明待查元素可能在表的后半部分，下次查找的起始位置通常应(      )
A.从MID/2位置开始     
B.从MID位置开始
C.从MID-1位置开始     
D.从MID+1位置开始

13.磁盘是一种广泛使用的外部存储设备，对磁盘的存取操作(      )
A.只能用顺序方式      
B.只能用随机方式
C.既能用顺序方式也能用随机方式  
D.方式取决于具体的机器

14.当待排序序列中记录数较少或基本有序时，最适合的排序方法为(      )
A.直接插入排序法      
B.快速排序法
C.堆排序法       
D.归并排序法

15.若对序列（26，90，23，53，16，34，69，39，22）进行一趟排序后所得到的结果为（22，16，23，26，53，34，69，39，90），则该排序可能使用的方法是(      )
A.插入排序       
B.冒泡排序
C.快速排序       
D.选择排序

二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。错填、不填均无分。
16.算法通常可分为程序、伪语言算法和__________三种类型。

17.时间复杂性描述量级中，若某算法达到__________量级，则该算法通常是不可计算的。

18.对顺序表执行删除操作，其删除算法的平均时间复杂性为__________。

19.若head表示循环链表的头指针，t表示尾结点，则头指针head与尾结点t之间的关系可表示为__________。

20.我们通常把队列中允许删除的一端称为__________。

21.二维数组A［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则A［4］［3］的存储地址是__________。

22.树在数据结构中常采用孩子链表表示法、__________三种存储结构表示。

23.若某二叉树中度为1的结点数为4，度为2的结点数为6，则该树叶子结点数为__________。

24.对于n个顶点的生成树，其边的个数为__________ 。

25.对于具有n个元素的数据序列，若采用二分查找法，当n的值较大时其平均查找长度为__________。

26.解决散列所引起冲突的方案中，__________法是介于开散列表与闭散列表之间的一种方法。

27.多关键字文件是指同时对__________两部分都建立索引的文件组织形式。

28.排序通常可分为内部排序和外部排序，其中内部排序是指排序的整个过程中，数据全部存放在计算机的__________中。

三、应用题(本大题共5小题，每小题6分，共30分)
29.对于如题29图所示二叉树，分别写出其先根遍历、中根遍历和后根遍历的结点访问序列。

30.设散列函数为H（key）=key%11，散列表长度为11（散列地址空间为0…10），在给定表（SUN，MON，TUE，WED，THU，FRI，SAT）中，取单词的第一个字母在英语字母表中的序号为键值K，构造一散列表，并用线性探测法解决有关的地址冲突。

31.试给出题31图的邻接矩阵和邻接表表示。

32.已知一组键值序列（32，44，38，65，53，42，29，57），试采用堆排序法对该组序列作升序排序，给出建立的初始堆以及第一次输出堆元素后筛选调整的堆。

33.已知一组键值序列（13，12，16，17，15，14，11），试采用二路归并排序法对该组序列作升序排序，并给出每一趟的排序结果。