全国2005年10月自考（课程代码：02142）数据结构导论试题

 
 全国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                                                 D.5、6、8、7
6.FORTRAN语言对数组元素的存放方式通常采用(      )
A.按行为主的存储结构                                   B.按列为主的存储结构
C.按行或列为主的存储结构                            D.按行和列为主的存储结构
7.树是n个结点的有穷集合，(      )
A.树的结点个数可以为0，此时称该树为空树
B.树至少含有一个根结点，不能为空
C.树至少含有一个根结点和一个叶子结点
D.树至少含有一个根结点和两个叶子结点
8.深度为k的二叉树至多有(      )
A.2^k个叶子                                              B.2^k-1个叶子
C.2^k-1个叶子                                           D.2^k-1-1个叶子
9.具有10个顶点的有向完全图应具有(      )
A.20条弧                                                 B.50条弧
C.90条弧                                                 D.100条弧

10.从V₁出发，对题10图按广度优先搜索遍历，则可能得到的一种顶点序列为(      )
A.V₁V₂V₃V₅V₄V₆
B.V₁V₂V₃V₅V₆V₄
C.V₁V₅V₂V₃V₆V₄
D.V₁V₃V₆V₄V₅V₂
 
 
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），试采用二路归并排序法对该组序列作升序排序，并给出每一趟的排序结果。
四、设计题(本大题共2小题，每小题7分，共14分)
34.若循环单链表长度大于1，p为指向链表中某结点的指针，试编写一算法删除p结点的前驱结点。
35.若二叉树用二叉链表表示，试编写一算法计算一棵二叉树的叶子总数（可采用递归算法描述）。

试题word文档下载：

全国2005年10月自考（课程代码：02142）数据结构导论试题.doc