中央广播电视大学2008-2009学年度第一学期"开放本科"期末考试
数据结构 试题
2009年1月
一、单项选择题(在括号内填写所选择的标号。每小题2分，共18 分)
2．在一个长度为n的线性表中顺序查找一个值为x的元素时，在等概率的情况下，查找成功时的平均查找长度为( )。
A． n B． n／2
C. (n+1)／2 D. (n一1)／2
5。在一棵完全二叉树中，若编号为i的结点存在左子女，则左子女结点的编号为( )，假定树根结点的编号为0。
A．2i B．2i一1
C. 2i+1 D. 2i+2
6．对长度为lo的线性有序表ALlo]进行折半查找，若查找到元素A[2)6寸成功，则查找长度为( )。
A．1 B. 2
C． 3 D． 4
7．向一棵AVL树插入元素时，可能引起对最小不平衡子树的调整过程，此调整过程共具有( )种旋转类型。
A．1 B．2
C． 3 D． 4
8．设一个有向图具有n个顶点和e条边，若采用邻接表作为其存储结构，则空间复杂度为( )。
9．在一棵m阶B树中，树根结点所包含的关键码个数至少为( )。
A．1 B．2
C．m／2 D．m-1
二、填空题(在横线处填写合适的内容。每小题2分，共14分)
10．利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对应一个非零元素的行号、列号和 。
11．在单链表中逻辑上相邻的结点而在物理位置上 相邻。
12．在一棵高度为2的四叉树中，最多含有--个结点，假定树根结点的高度为0。
13．在一个堆的顺序存储中，若一个元素的下标为i(i≥0)，则它的右子女元素的下标为 。
14．根据一组记录(56，42，?3，50，48，22)依次插入结点生成一棵AVL树时，当插入到值为--的结点时首次出现不平衡，需要进行旋转凋整。
15．当利用Kruskal算法求解...·个连通网的最小生成树时，只有当--条候选边的两个端点不在同一个--一一分量时，才会被加入到最小生成树中。
16．在堆排序中，对n个记录建立初始堆需要调用--一一---一-次筛运算的算法。
三、判断题(在每小题后面括号内打对号表示叙述正确或打叉号表示叙述错误。每小题2分，共14分)
17．线性表若采用链式存储表示．时，其存储结点的地址可连续也可不连续。 ( )
20．在一棵二叉树中，假定每个结点只有左子女，没有右子女，若对它分别进行中序
遍历和后序遍历，则具有相同的遍历结果。 ( )
21．折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树。 ( )
22．对一个用顶点表示活动的网络(AOV网)进行拓扑排序的结果是唯一的。 ( )
23．堆排序是一种稳定的排序方法。 ( )
四、计算题(每小题6分，共30分)
先根：
后根：
按层：
26．已知一个数据集合为{28，12，16，49，34，30}，试把它调整为-个最大堆。
最大堆：
27．已知一个图的顶点集V和边集G分别为：
V＝{1，2，3，4，5}；
E＝{<1，2>，<1，3>，<2，4>，<2，5>，<3，4>，<4，5>，<5，1>，<5，3
>}；
假定此图采用邻接矩阵表表示，根据图的遍历算法分别写出从顶点l出发进行
深度优先搜索和广度优先搜索所得到的顶点序列。
深度优先搜索序列：
广度优先搜索序列：．
28．设散列表的长度m＝7；散列函数为H(K)＝K mod m，若采用线性探查法解决
冲突，待依次插入的关键码序列为{19，14，23，68，20}，分别求出查找23、68、20
时的搜索长度。
查找23、68、20的搜索长度：
五、计算分析题(每小题6分，共12分)
29．设rear是以循环链表表示的队列的队尾指针，EnL Queue 函数实现把x插入到
队尾的操作。阅读算法，在划有横线的上面填写合适的内容。
试卷代号：1010
中央广播电视大学2008-2009学年度第一学期"开放本科"期末考试
数据结构 试题答案及评分标准
(供参考)
2009年1月
一、单项选择题(在括号内填写所选择的标号。每小题2分，共18分)
1．B 2．C 3．C 4．D 5．C
6．C 7．D 8．B 9．A
二、填空题(在横线处填写合适的内容。每小题2分，共14分)
10．值
11．不一定
12． 2l
13．2i+2
14， 48
15．连通
16． n／2
三、判断题(在每小题后面括号内打对号表示叙述正确或打叉号表示叙述错误。每小题2分，
共14分)
17．√ 18．X 19．√ 20．√ 21．√
22．X 23．X
四、计算题(每小题6分，共30分)
24．先根：a，b，e，c，f，h，i，j，g ／／2分
后根：e，b，h，i,j，f，g，c，a ／／2分
按层：a，b，c，c，f，g，h，i，j ／／2分
25．评分标准：每个数值对得2分，全对给6分
26． {49，34，30，12，28，16}
27．深度搜索序列：1，2，4，5，3 ／／3分
广度搜索序列：1，2，3，4，5 ／／3分
28．查找23、68、20的搜索长度：1、2、3 ／／每个数据占2分
五、计算分析题(每小题6分，共12分)
29．rear->link、rear＝p ／／每空3分
30．从HL单链表中顺序查找出值为K的结点，若查找成功则返回该结点的地址，否则返回空。
六、编写题(每小题6分，共12分)
31．请根据编程的完整程度酌情给分。
32．请根据编程的完整程度酌情给分
来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
相关文章：
材料：你市海事局进行例行的航前安全检查，在登船检查时发04-27
你作为卫生防疫部门的工作人员，当前新型冠状肺炎的防治04-27
小王是一名下沉社区支援基层防疫的工作人员。社区领导04-27
你是刘处长，分管单位的办公室，小王是办公室新进员工，上班04-27
材料：近日，某海事局对一违法运输船舶处以21.8万元罚款，刷04-27
单位要组织大型会议，准备时间非常紧，领导便安排你和其他04-27
2019年5月5日凌晨，被告人彭某与朋友吃宵夜、喝啤酒，并在04-27
疫情防控期间，单位要求50%的人员到岗，你作为科室负责人04-27