试卷代号：3323
中央广播电视大学2000一2001学年度第二学期期末补考
计算机、数教九九级第四学期数据结构试题
2001年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，则它的最小深度为 ，最大深度为 。
1
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），请写出在堆排序阶段进行前三次对换和筛运算后数据的排列情况。
2
数据排列情况： 。 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；
3
ElemType x=A[s]； d0｛
do i十十； while（ ）；／／填写一个循环条件 do j一 一； while（A [ j ] ．stn＞x．stn）； if（I { 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 中央广播电视大学2000一2001学年度第二学期期末补考 计算机、数教九九级第四学期数据结构 试题答案及评分标准 （供参考） 2001年9月 一、单选题（每小题2分，共8分） 评分标准：选对者得2分，否则不得分。 1．B 2．D 3．A 4．B 二、填空题（每空1分，共32分） 评分标准：每空得2分，否则不得分。 1．集合结构线性结构树结构图结构（次序元先后） 2． O（n）O（1） 4 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） 5
中央广播电视大学2000一2001学年度第二学期期末补考数据结构试题及参考答案
