2012数据结构b卷

《2012数据结构b卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、院/系年级专业姓名学号答题勿超装订线------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------安徽大学2011—2012学年第2学期《数据结构》考试试卷（B卷）（闭卷时间120分钟）考场登记表序号题号一二三四五六总分得分阅卷人得分一、填空题（每空2分

2、，共30分）1．向量、栈和队列都是结构；对于栈只能在插入和删除元素；对于队列只能在插入元素和删除元素。2．向栈中压入元素的入栈函数是。3．由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为。4．在双链表中，每个结点有两个指针域，一个指向，另一个指向。5．二维数组A[0‥5][0‥5]以行序为主序存储，每个元素占4个存储单元，且A[0][0]的存储地址是1000，则A[3][4]的地址是。6．若串s=，则其子串个数是。7.在顺序存储结构的线性表中，插入或删除一个数据元素平均需移动表

3、中元素。8．下列程序段的时间复杂度是。for(i=0;i

4、结点的单链表，p指向其中的一个结点，选择合适的语句实现在p结点的后面插入一个结点s的操作（）。A、p->next=s;s->next=p->next;B、s->next=p->next;p->next=s;C、p->next=s;s->next=p;D、s->next=p;p->next=s;3.一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是（）。A.edcbaB.decbaC.dceabD.abcde4、树最适合用来表示（）。A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的

5、数据D、元素之间无联系的数据5、栈结构通常采用的两种存储结构是（）。A、顺序存储结构和链式存储结构B、散列方式和索引方式C、链表存储结构和数组D、线性存储结构和非线性存储结构6、假设在一棵二叉树中，度为2的分支结点个数为15，度为1的分支结点个数为30，则该二叉树的结点总数为（）。A、45B、60C、46D、617.对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为（）。A、O(n2)B、O(e)C、O(n)D、O(n+e)8.栈和队列的共同点是（）。A.都是先进后出B.都是先进先出C.只允许在端点处

6、插入和删除元素D.没有共同点9、已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是()A:head(tail(LS))                     B:tail(head(LS))C:head(tail(head(tail(LS)))          D:head(tail(tail(head(LS))))10.下面序列中哪个是堆？（）A、79，46，56，38，40，80B、84，79，56，38，40，46C、84，79，56，86，

7、40，38D、84，56，19，40，46，38三、判断题（在正确的题后括号内打P，错的则打×，每小题1分，共10分）得分1.链表不一定要设置一个头结点。（）第4页共4页2.队列在数据中的存储原则是后进先出。（）3.二叉树中任何一个结点的度都是2。（）4.循环队列是指用链表存储的队列。（）5.若入栈序列为abcd，则出栈序列不可能为cdab。（）答题勿超装订线------------------------------装------------------------------------------

8、---订----------------------------------------线----------------------------------------6.在拓扑排序过程中，如果图中已不存在无前驱的顶点了，而此时还有顶点没有输出，则说明图中存在环。（）7．平衡二叉树是指这样的二叉树：树中任一结点的左右子树深度都相同。（）8．在任何情况下，快速排序都是最快的。（）9.一个有向图的邻接矩阵一定是一个非对称矩阵。（）10.栈和队