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

1试卷代号：3323中央广播电视大学2000一2001学年度第二学期期末补考计算机、数教九九级第四学期数据结构试题2001年9月一、单选题（每小题2分，共8分）1．若需要利用形参直接访问实参，则应把形参变量说明为参数。A指针B引用C值2．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行。Aq一next=p一next；p一next=q；Bp一next=q一next；q=p；C9一next=p一next；p一next=q；Dp一next=q一next；q一next=p；3．在一个顺序队列中，队首指针指向队首元素的位置。A前一个B后一个C当前4．向二叉搜索树中插入一个元素时，其时间复杂度大致力。AO（1）BO（1og2n）CO（n）DO（nlog2n）二、填空题（每空1分，共32分）1．数据的逻辑结构被分为、、和四种。2．对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为，在表尾插入元素的时间复杂度为。3．在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的、和三项。4．在广义表的存储结构中，每个结点均包含有个域。5．当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件为。6．假定一棵三叉树的结点个数为50，则它的最小深度为，最大深度为。27．在一棵二叉树中，第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），请写出在堆排序阶段进行前三次对换和筛运算后数据的排列情况。3数据排列情况：。4．假定一组记录的徘序码为（46，79，56，38，40，80，36，40，75，66，84，24），对其进行归并排序的过程中，第三趟归并后的结果为：。四、阅读算法，回答问题（每小题8分，共16分）1．voidAA（List＆L）{InitList（L）；InsertRear（L，30）；InsertFront（L，50）；inta[4]={5，8，12，15}for（inti=0；1＜4；i＋＋＝InsertRear（L，a[i]）；}该算法被调用执行后，得到的线性表L为：。2．voidAF（Queue＆Q）{InitQueue（Q）：inta[4]={5，8，12，15}for（inti一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]上进行快速排序的递归算法。voidQuickSort（ElemTypeA[]，ints，intt）{inti=sj=t十1；4ElemTypex=A[s]；d0｛doi十十；while（）；／／填写一个循环条件doj一一；while（A[j]．stn＞x．stn）；if（Ij）{ElemTypetemp=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为树根指针的二叉树中的叶子结点的个数。intCount（BTreeNode*BT）试卷代号：3323中央广播电视大学2000一2001学年度第二学期期末补考计算机、数教九九级第四学期数据结构试题答案及评分标准（供参考）2001年9月一、单选题（每小题2分，共8分）评分标准：选对者得2分，否则不得分。1．B2．D3．A4．B二、填空题（每空1分，共32分）评分标准：每空得2分，否则不得分。1．集合结构线性结构树结构图结构（次序元先后）2．O（n）O（1）53．行号列号元素值（次序无先后）4．35．top==06．5507．168．2h一12h一19．最小值最大值10．n一111．O（n2）O（n十e）O（e）12．顺序有序13．稠密稀疏14．开放定址法链接法（次序无先后）15．1116．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）203．（50，42，46，38，40，56，79，84）4．［3638404046567980］［25667584」四、阅读算法，回答问题（每小题8分，共16分）评分标准：每小题正确得8分，出现一处错误扣4分，两处及以上错误不得分。1．（50，30，5，8，12，15）2．121553018五、算法填空，在画有横线的地方填写合适的内容（10分）。评分标准：对一空得3分，全对得10分。A[i]stn＜x．stnQuickSort（A，s，j一1）QuickSort（A，j十1，t）；六、编写算法（10分）评分标准：请根据编程情况酌情给分。intcount（RtreeNOde*BT）6／／统计出二叉树中所有叶子结点数{if（BT==NULL）return0：elseif（BT一left==NULL&&BT一right==NULL）returnelsereturnCount（BT一left）十Count（BT一right）；}