《华南农业大学期末考试试卷》-数据结构-A卷

《《华南农业大学期末考试试卷》-数据结构-A卷》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、华南农业大学期末考试试卷(A卷)2011-2012学年第1学期考试科目：数据结构(JAVA)考试类型：(闭卷)考试考试时间：120分钟学号姓名年级专业2010级信管班答案请写到答题纸上，写在试卷上无效一、单选题(本大题共10小题，每小题2分，共20分)1.不考虑优先队列，已知入队序列为{A,B,C,D},可能的出队序列为：()A.{D,B,C,A}B.{A,B,C,D}C.{A,D,C,B}D・{A,C,D,B}2.已知结点数为1001的完全二叉树，其叶子结点个数为：()A.500B.501C.602D」3.具有8000个结点的二叉树，其高度至少为：()A.10B.llC.12D.134

2、.设一棵哈夫曼树有n个非叶子结点，该树共有()个节点A.nB.2n-1C.2n+1D.2n5.归并排序的空间复杂度是：()A.O(nlog2n)B.O(n2)C.O(Iog2n)D.O(n)6.以下程序时I'S］复杂度为：()intn=8,m=1024,count=1024;for(inti=m;i>=l;i-)count++;A.O(1)B.O(m)C.O(log2m)D.O(mlog2m)7.式n+log2n+n*n*n的时间复杂度为:()A.O(1)B.O(n3)C.O(n+log2n)D.O(log2n)8.衡量算法的标准有：()A.时间复杂度和空间复杂度B.输入和输出C.有穷性

3、和确定性D.可行性9.已知入栈顺序为{a,b,c,d,e,f,g},下列哪个是可能的出栈顺序:()A.{d,e,c,f,b,g,a}B.{f,e,g,d,a,c,b}C.{e,f,d,g,b,c,a}D.{e,f,d,g,b,a,c}10.己知一个顺序循环队列最多能容纳60个元素，当前有58个元素时，如果再插入5个元素，该队列有多少空元素：()A.-3B.63C.5D.57二、填空题(本大题共10小题，每空1分，共20分)1.软件设计是计算机学科各个领域的核心。软件设计时要考虑的首要问题是数据的表示、组织和处理方法。和是软件系统设计的核心。2.双链表的插入和删除操作：q=newDLink

4、Node(x);;q.next=p;p.prev.next=q;。3.两个顺序表相等是指它们各对应并口o4.设一棵二叉树的叶子结点数为n0,2度结点数为n2,则n0二。N个节点完全二叉树的高度是5.设嵌套广义表Z=(e,Z)=(e,(e,(e,(・・・))))，则Z的长度为,深度6.在树结构中，约定根节点的层次为,其他节点的层次是其父母节点的层次加O7.树的表示法有：图示法、和三种。8.一棵高度为k(k>=0)的完全二叉树是具有至多个结点的二叉树，一棵高度为k(k>=0)的满二叉树是具有至少个结点的二叉树。中根遍历序列和后根遍历序列相反的二叉树是,由256个权值构造一棵哈夫曼树，则该二叉

5、树共有结点。9.由n个顶点组成的无向连通图，最多可以有条边。10.10个元素的排序数据序列采用折半查找的平均查找长度是(写出算式)三、程序分析题(本题共2小题，每小题8分，共16分)1.下列该程序片段的运行结果是：〃链式栈(略)〃判断exDStr表达式屮的圆括号是//importdataStructure」ineariList・LinkedStack;publicclassExp_bracketpublicstaticStringisValid(Stringexpstr)否匹配〃返回错误信息LinkedStackstack=newLinkedStack()

6、;//创建空栈inti=0;while(i

7、

8、!stack.pop().equals(,,(H))//遇见右括号时，出栈return”期望(“；//判断出栈字符是否为左括号if(stack.isEmpty())returnreturn"期望广;publicstaticvoidmain(Stringargs[J)Stringexpstr=n((1+2)*3+4))(M;System.€?wAprintln(expstr+

9、Hn+z5W//z^(expstr));expstr=H((l+2)*3+4))n;System.pz/r.println(expstr+Hexpstr=”((l+2)*3+4)))“;System.m/Z.println(expst「+”expstr="(5*4)(";System.<；M/.println(expstr+nn+z5Va/W(expstr));H+z5Va/M(expstr));"+wVcz//J(expstr))