2023年中央广播电视大学一度第二学期期末补考数据结构试题及参考答案.doc

试卷代号：3323
中央广播电视大学2023一2023学年度第二学期期末补考
计算机、数教九九级第四学期数据结构试题
2023年9月
一、单选题（每小题2分，共8分）
1．若需要运用形参直接访问实参，则应把形参变量说明为 参数。
A指针 B引用 C值
2．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行 。
A q一>next=p一>next；p一>next=q；
B p一>next=q一>next；q=p；
C 9一>next=p一>next；p一>next=q；
D p一>next=q一>next；q一>next=p；
3．在一个顺序队列中，队首指针指向队首元素的 位置。
A前一个 B后一个 C当前
4．向二叉搜索树中插入一个元素时，其时间复杂度大体力 。
A O（1） B O（1og2n）
C O（n） D O（nlog2n）
二、填空题（每空1分，共32分）
1．数据的逻辑结构被分为 、 、 和
四种。
2．对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为 。
3．在一个稀疏矩阵中，每个非零元素所相应的三元组涉及该元素的 、
和 三项。
4．在广义表的存储结构中，每个结点均包具有 个域。
5．当用长度为N的数组顺序存储一个栈时，假定用top = =N表达栈空，则表达栈满的条件为 。
6．假定一棵三叉树的结点个数为50，则它的最小深度为 ，最大深度为 。
7．在一棵二叉树中，第5层上的结点数最多为 。
8．在一棵高度为6的抱负平衡树中，最少具有 个结点，最多具有 个结点。
9．在一个小根堆中，堆顶结点的值是所有结点中的 ，在一个大根堆中，堆顶结点的值是所有结点中的 。
10．在一个具有n个顶点的无向圄中，要连通所有顶点则至少需要 条
边。
11．假定一个图具有n个顶点和e条边，贝采用邻接矩阵、邻接表和边集数组表达时，其相应的空间复杂度分别为 、 和 。
12．以二分查找方法查找一个线性表时，此线性表必须是 存储的 表。
13．在索引表中，若一个索引项相应主表中的一条记录，则称此索引为
表。
14．在线性表的散列存储中，解决冲突有 和 两种方法。
15．向一棵B—树插入元素的过程中，若最终引起树根结点的分裂，则新树的高度比原树增 ；从一棵B—树删除元素的过程中，若最终引起树根结点的合并，则新树的高度比原树减 。
16．快速排序在平均情况下的空间复杂度为 ，在最坏情况下的空间复杂度为 。
三、运算题（每6分，共24分）
1．假定一个大很堆为（56，38，42，30，25，40，35，20），则依次从中删除两个元素后得到的堆为 。
2．已知一个图的顶点集V和边集6分别为：
V={0，1，2，3，4，5，6，7}；
E={（04）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；
按照克鲁斯卡尔算法得到最小生成材，拭写出在最小生成树中依次得到的各条边。
， ， ， ， ， ， 。
3．假定一组数据的初始堆为（84，79，56，42，40，46，50，38），请写出在堆排序阶段进行前三次对换和筛运算后数据的排列情况。
数据排列情况： 。
4．假定一组记录的徘序码为（46，79，56，38，40，80，36，40，75，66，84，24），对其进行归并排序的过程中，第三趟归并后的结果为：
。
四、阅读算法，回答问题（每小题8分，共16分）
1．        void AA （List＆L）
{
InitList（L）；
InsertRear （L，30）；
InsertFront（L，50）；
int a [4]={5，8，12，15}
for（int i=0；1＜4；i＋＋＝ InsertRear（L，a [i]）；
}
该算法被调用执行后，得到的线性表L为： 。
2．        void AF（Queue＆Q）
{
InitQueue（Q）：
int a [4]={5，8，12，15}
for（int i一0；i＜4；i斗＋＝ Qlnsert（Q，迁6）；
QInsert（Q，QDelete（Q））；
QInsert（Q，30）；
QInsert（Q，QDelete（Q）＋10）；
whi1e（！QueueEmpty（Q）） cout＜＜QDeleie（Q）＜＜”；
}
该算法被调用后得到的输出结果为： 。
五、算法填空，在画有横线的地方填写合适的内容（10分）
从一维数组A[n]上进行快速排序的递归算法。
void QuickSort（ElemType A [ ]， int s， int t）
{
int i=s j=t十1；
ElemType x=A[s]；
d0｛
do i十十； while（ ）；／／填写一个循环条件
do j一 一； while（A [ j ] ．stn＞x．stn）；
if（I<j）
{ ElemType temp = A［i］；A［i］= A［j］；A［j］＝temp；}
} while（i＜j）；
A[s]=A[j]；A[j]=x；
if（s＜i一1） ；
if（j十1＜t） ；
}
六、编写算法（10分）
编写一个递归算法，记录并返回以BT为树根指针的二叉树中的叶子结点的个数。
int Count（BTreeNode*BT）

试卷代号：3323
中央广播电视大学2023一2023学年度第二学期期末补考
计算机、数教九九级第四学期数据结构
试题答案及评分标准
（供参考）
2023年9月
一、单选题（每小题2分，共8分）
评分标准：选对者得2分，否则不得分。
1．B 2．D 3．A 4．B
二、填空题（每空1分，共32分）
评分标准：每空得2分，否则不得分。
1．集合结构线性结构树结构图结构（顺序元先后）
2． O（n）O（1）
3．行号列号元素值（顺序无先后）
4．3
5．top= =0
6．550
7．16
8．2h一1 2h一1
9．最小值最大值
10．n一1
11．O（n2） O（n十e）O（e）
12．顺序有序
13．稠密稀疏
14．开放定址法链接法（顺序无先后）
15．1 1
16．O（1og2n） O（n）
三、运算题（每小题6分，共24分）
评分标准：每小题对的得6分，出现一处错误扣3分，两处及以上错误不得分。
1．（40，38．35，30，25，20）
2．（0，3）2，（4，6）4，（0，2）5，（1，5）6，（0，1）8，（3，6）10，（5，7）20
3．（50，42，46，38，40，56 ，79，84）
4．［36 38 40 40 46 56 79 80］［25 66 75 84」
四、阅读算法，回答问题（每小题8分，共16分）
评分标准：每小题对的得8分，出现一处错误扣4分，两处及以上错误不得分。
1．（50，30，5，8，12，15）
2．12 15 5 30 18
五、算法填空，在画有横线的地方填写合适的内容（10分）。
评分标准：对一空得3分，全对得10分。
A[i] stn＜x．stn QuickSort（A，s，j一1） QuickSort（A，j十1，t）；
六、编写算法（10分）
评分标准：请根据编程情况酌情给分。
int count（RtreeNOde*BT）
／／记录出二叉树中所有叶子结点数
{
if（BT= =NULL）return 0：
else if（BT一>left= =NULL&&BT一>right= =NULL）return
else return Count（BT一>left）十Count（BT一>right）；
}