中央广播电视大学2005-2006学年度第一学期"开放本科"期末考试
计算机专业 数据结构 试题
2006年1月
一、单项选择题，在括号内填写所选择的标号(9小题，每小题2分，共18分)
1．一种抽象数据类型包括数据和( )两个部分。
A．数据类型 B．操作
C数据抽象 D．类型说明
2．在一个长度为n的顺序表的表尾插入一个新元素的时间复杂度为( )。
A．O(1) B．O(n)
C.O(n2) D．O(log2n)
3．已知L是带表头附加结点的单链表，删除第一个结点的语句是( )。
A．L＝L一>link； D．L一>1ink=L一>link一>link；
C L＝L； D． L一>1ink=L；
4．下列广义表中的线性表是( )。
A．E(a，(b，c)) B．E(a，E)
C． E(a，b) D． E(a，())
5．在一棵树的左子女一右兄弟表示法中，一个结点的右子女是该结点的( )结点。
A兄弟 B．父子
C祖先 D子孙
6．向一棵AVL树插入元素时，可能引起对最小不平衡子树的双向旋转的调整过程，此时
需要修改相关( )个指针域的值。
A．2 B．3
C 4 D．5
7．在一个有向图的邻接矩阵表示中，删除一条边
A．O(1) B．O(i)
C O(i) D·O(i+j)
8．在一棵高度为h的B树中，插入一个新关键码时，为搜索插入位置需读取( )个结点。
A．h一1 B．h
C h+1 D．h+2
9．对存储有n个元素的长度为m的散列表进行搜索，平均搜索长度与( )有关。
A．n B．m
C．n／m D．n*m
二、填空题，在横线处填写合适内容(12小题，每小题1分，共12分)
1.抽象数据类型的特点是 、信息隐蔽、使用与实现分离。
2．利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对应一个非零元素的行号、列号和 。
3．在单链表中逻辑上相邻的结点而在物理位置上， 相邻。
4．向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给 。
5．迷宫问题是一个回溯控制的问题，最好使用 的方法来解决。
6．在一棵高度为3的四叉树中，最多含有 个结点，假定树根结点的高度为0。
7．在一个堆的顺序存储中，若一个元素的下标为i(0≤i≤n一1)，则它的右子女元素的下标为 。
8．根据一组记录(56，42，73，50，48，22)依次插入结点生成一棵AVL树时，当插入到值为 的结点时才出现不平衡，需要进行旋转调整。
9．在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个 上，才会被加入到生成树中。
10．在堆排序中，对n个记录建立初始堆需要调用 次调整算法。
11．在对n个数据对象的二路归并排序中，每趟归并的时间复杂度为 。
12．在一棵m阶B树上，每个非根结点的关键码数最少为 个。
三、判断题，在每小题前面打对号表示正确或打叉号表示错误(10小题，每小题1分，共10分)
( )1．多维数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。
( )2．若每次从队列中取出的是具有最高优先权的元素，则称这种队列为优先级队列。
( )3．递归定义的数据结构通常不需要用递归的算法来实现对它的操作。
( )4．当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。
( )5．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。
( )6．对于同一组记录，生成--X搜索树的形态与插入记录的次序无关。
( )7．在每个AOE网络中只有一条关键路径。
( )8．图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。
( )9．装载因子是散列表的一个重要参数，它反映了散列表的装满程度。
( )10．在一棵B树中，所有叶结点都处在同一层上，所有n十结点中空指针数等于所有关键码的总数加1。
四、运算题(5小题，每小题6分，共30分)
1．假定一棵二叉树广义表表示为a(b(c)，d(e，f))，分别写出对它进行中序、后序、按层遍历的结果。
中序：
后序：
按层：
2．-个-维数组a[10]中存储着有序表(15，26，34，39，45，56，58，63，74，76)，根据折半搜索所对应的判定树，写出该判定树中度为1的结点个数，并求出在等概率情况下进行成功搜索时的平均搜索长度。
度为1的结点个数：
平均搜索长度：
3．假定-个线性序歹U为(38，42，55，15，23，44，30，74，48，26)，根据此线性序歹U中元素的排列次序生成一棵-X搜索树，求出该二叉搜索树中左子树为空的所有单支结点、右子树为空的所有单支结点和所有叶子结点，请按照结点值从小到大的次序写出。
左子树为空的所有单支结点：
右子树为空的所有单支结点：
所有叶子结点：
4．已知一个图的顶点集V和边集G分别为：
V：{l，2，3，4，5，6}；
E＝{<1，2>，El，3>，<2，4>，<2，52>，<3，4>，<4，5>，<4，6>，<5，l>，<5，3
>，<6，5>}；
假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号(即数值域的
值)从小到大的次序链接的，试写出：
(1)从顶点1出发进行深度优先搜索所得到的顶点序列；
(2)从顶点1出发进行广度优先搜索所得到的顶点序列。
(1)：
(2)：
5．已知一个数据序列为{6，45，27，23，41，5，56，64}，把它调整为最大堆并给出进行两趟交换和堆排序后的结果(即尾部得到2个最大数)。
最大堆：
两趟排序后结果：
五、算法分析题(3小题，每小题6分，共18分)
1．该算法功能为：从表头指针为1a的、按值从小到大排列的有序链表中删除所有值相同的多余元素，并释放被删结点的动态存储空间。阅读算法，按标号填写空缺的内容，要求统一填写在算法后面的标记处。
void purge_linkst(ListNode*&1a)
{
ListNode*p，*q；
if(1a==NULL)return；
q=1a；p=1a一>link；
while(p){
if( (1) ){q=p；p＝p一>link；}
else{
q->link= (2) ；
delete(p)；
p= (3) ；
}
}
}
(1)
(2)
(3)
2．请写出下面算法的功能，其中Stack表示栈类，Queue表示队列类。
void unknown(Queue&Q)
{
StackS；int d；
S．InitStack()；
while(!Q．IsEmpty()){
Q．DeQueue(d)； ／／出队列元素值由变量d带回
S．Push(d)；
}
while(!S．IsEmpty()){
S．Pop(d)； ／／出栈元素值由变量d带回
Q．EnQueue(d)；
}
}
算法功能：
3．已知二叉树中的结点类型BinTreeNode定义为：
struct BinTreeNode{ElemTypedata；BinTreeNode*left，*right；}；
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下面函数的功能是从二叉树BT中查找值为X的结点，若查找成功则返回结点地址，否则返回空。按标号填写空缺的内容，要求统一填写在算法后面的标记处。
BinTreeNode*BTF(BinTreeNode* BT，ElemType x)
{
if(BT＝＝NULL) (1) ；
else{
if(BT一>data＝＝x) (2) ；
else{
BinTreeNode't；
if(t=BTF(BT一>left，x))returnt;
(3) ；
return NULL；
}
}
}
(1)
(2)
(3)
六、算法设计题(2小题，每小题6分，共12分)
1．在一个带表头附加结点的单链表L中，假定所有结点的值按递增顺序排列，试编写一个while循环补充下面函数，功能是删除表L中所有其值大于等刁：min，同时小于等于max的结点。
void rangeDelete(ListNode*&L，ElemTyperain，ElemTypemax)
{
ListNode*q=L，*p=L一>link；
／／添加的while循环位置
}
／／请把while循环内容写在此行下面
2．已知二叉搜索树中的结点类型BinTreeNode定义为：
structBinTreeNode{ElemTypedata；BinTreeNode'left，*right；}；
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数BST指向一棵二叉搜索树的根结点。试根据下面的函数声明编写一个非递归算法，从BST树中搜索出具有item参数值的结点，若搜索成功则返回该结点的地址，否则返回NULL。
BinTreeNodei*Find(BinTreeNode*BST，const ElemType&item)；
／／请把函数定义写在此行下面
试卷代号：1010
中央广播电视大学2005-2006学年度第一学期"开放本科"期末考试
计算机专业 数据结构 试题答案及评分标准
(供参考)
2006年1月
一、单项选择题，在括号内填写所选择的标号(9小题，每小题2分，共18分)
1．B 2．A 3．B 4．C 5．A 6．D
7。 A 8．B 9．C
二、填空题，在横线处填写合适内容(12小题，每小题1分，共12分)
1．数据封装
2．值
3．不一定
4．栈顶指针
5．递归
6．85
7．2i+2
8． 48
9．连通分量
10．n／2
11．O(n)
12． [m／2]-1
三、判断题，在每小题前面打对号表示正确或打叉号表示错误(10小题，每小题1分，共10分)
1．对 2．对 3．错 4．对 5．对
6．错 7．错 8．对 9．对 10．对
四、运算题(5小题，每小题6分，共30分)
1．中序：c，b，a，e，d，f ／／2分
后序：c，b，e，f，d，a ／／2分
按层：a，b，d，c，e，f ／／2分
2．度为1的结点个数：3 ／／3分
平均搜索长度：29／10 ／／3分
3．左子树为空的所有单支结点：15，23，42，44 ／／2分
右子树为空的所有单支结点：30 ／／2分
所有。十子结点：26，48，74 ／／2分
4．(1)1，2，4，5，3，6 ／／3分
(2)1，2，3，4，5，6 ／／3分
5．最大堆：{64，45，56，23，41，5，27，6} ／／3分
两趟排序结果：{45，41，27，23，6，5，56，64} ／／3分
五、算法分析题(3小题，每小题6分，共18分)
1．(1)p一>data>q一data(或p-> data!＝q一>data) ／／2分
(2)p->link ／／2分
(3)q->link ／／2分
2．利用"栈"作为辅助数据结构，将队列Q中的元素逆置(即按相反次序放置)。
3．(1)refurn NULl。 ／／2分
(2)return BT ／／2分
(3)if(t＝BTF(BT一>right，x))return t ／／2分
六、算法设计题(2小题，每小题6分，共12分)
评分标准：根据编写正确程度酌情给分。
1．while(p!=NULL){
if(p->data>-=min&&p->(tata<=max){
q一>link=p一>link;delete p；p=q一>link；
}
else{q=p；p=p一>link；}
}
2． BinTreeNOde*Find(BinTteeNOde*BST，const E1emType&item)
{
while(BST!；NULL)
{
if(item==BST->data)returnBST，
elseif(item
elseBST：BST一>right;
}
return NUll;
}
来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
相关文章：
在实际教学中，任课教师不能经常搞突袭，像突然来的考试、04-27
作为教师，往往“身教重于言传”。体现了教师04-27
人们希望得到较稳定的职位，有相对稳定的社会福利，积极参04-27
以下德育途径，属于基本途径的是(04-27
阅读诗句“蒹葭苍苍，白露为霜。”想象着诗中04-27
斯金纳认为“凡是使反应概率增加，或维持某种反应水平的04-27
下列选项中不属于资源管理策略的是04-27