数据结构07B参考答案.doc

《数据结构07B参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、试卷编号命题人：　金旺春　　试卷分类（A卷或B卷）B五邑大学试卷学期：2008至2009学年度第二学期课程：　数据结构　　　专业：　　　班级：AP0　　　　　　　姓名：　　　　学号：　题号一二三四五总分得分得分一、　　　　　　　单项选择题(10小题，每小题1分，共10分)1．下列数据中，（C）是非线性数据结构。A．栈B.队列C.完全二叉树D.堆2.假设某个带头结点的单链表的头指针为head，则判定该表为空表的条件是(B)A.head==NULL；B.head->next==NULL；C.head!=NULL；D.head->next==head；3.栈是一种操作受限的线性结构，

2、其操作的主要特征是(B)A.先进先出B.后进先出C.进优于出D.出优于进4.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为(D)A.(rear-front-1)％nB.(rear-front)％nC.(front-rear+1)％nD.(rear-front+n)％n5.判断两个串大小的基本准则是(D)A.两个串长度的大小B.两个串中首字符的大小C.两个串中大写字母的多少D.对应的第一个不等字符的大小6.二维数组A[4][5]按行优先顺序存储，若每

3、个元素占2个存储单元，且第一个元素A[0][0]的存储地址为1000，则数组元素A[3][2]的存储地址为(C)A.1012B.1017C.1034D.10367.高度为5的完全二叉树中含有的结点数至少为(C)A.16B.17C.31D.328.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为(C)A.5B.8C.11D.189.如图所示有向图的一个拓扑序列是(B)A.ABCDEFB.FCBEADC.FEDCBAD.DAEBCF图1题一、9图10.对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关

4、键字比较次数的平均值为(B)A.B.C.D.得分二、判断题(10小题，每小题1分，共10分)（）1．数据的逻辑结构是指数据的各数据项之间的逻辑关系；V（）2．设有5000个元素，希望用最快的速度挑选出前10个最大的，采用快速排序方法比采用堆排序更好。X（）3．顺序存储结构的主要缺点是不利于插入或删除操作。V（）4．对任何数据结构链式存储结构一定优于顺序存储结构。X（）5．两个栈共用静态存储空间，对头使用也存在空间溢出问题。V（）6．数组不适合作为任何二叉树的存储结构。X（）7．非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子。V（）8．在n个结点的无向图中，若

5、边数大于n-1,则该图必是连通图。X（）9．完全二叉树肯定是平衡二叉树。V（）10．在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n)。X得分三、　　　　　　　填空题(10小题，每空1分，共10分)1.估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的__元素个数_______。2.在双向循环链表中插入一个新的结点时，应修改___4______个指针域的值。3.若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现___5______个不同的出栈序列。4..广义表(a，(d，(c)))的深度为___3______。5.在含有3个结点a，b，c的二叉

6、树中，前序序列为abc且后序序列为cba的二叉树有___4______棵。6.若用邻接矩阵表示有向图，则顶点i的入度等于矩阵中___第i列非零元素个数______。7．.对关键字序列(15，18，11，13，19，16，12，17，10，8)进行增量为5的一趟希尔排序的结果为__15,12,11,10,8.16,18,17.13,19_。8．第一个顶点和最后一个顶点相同的路径称为回路或者环，除第一个顶点和最后一个顶点外，其余顶点都不重复的回路，称为_简单回路或简单环______。9．一个具有10个顶点的完全无向图中有__45_____条边。10．一棵平衡二叉树中任一结点的平衡因

7、子只可能是__+1,0，-1_____。得分四、　　　　　　　应用题(共有7小题，共计56分)1．某二叉树的先根遍历序列为ABIJCDFGHE，中根遍历序列为IJBADGFHCE，试画出该二叉树，并写出它的后序遍历序列。(8分)解答：该二叉树如图所示(5分)对应的后序遍历为：JIBGHFDECA（3分）2．证明：对于一棵非空的完全二叉树，若结点总数为n，则该二叉树的深度k=+1（8分）证明：假设二叉树的深度为k,根据完全二叉树的定义知，在1~k-1层上具有最大结点数，在k层上具有1~2k-1