资源描述：
《2012《数据结构》期末试卷(a卷)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2012A卷【字号：大中小】2011－2012年春季学期计算机科学与技术、软件工程、网络工程专业《数据结构》期末试卷（A卷）卷面总分：100分 答题时间：120分钟 专业 年级 班级 姓名 学号 题号一二三四五六七八九十总分得分 一、 单项选择题（本大题共15小题，每小题1分，共15分 答案写在答题卡上）答题卡 题号123456789101112131415 答案 1. 设n是描述问题规模的非负整数，下面程
2、序片段的时间复杂度是( )。 x=2; while(x0）。 A．表元素 B．数据元素 C．字符 D．数据项 3. 对于顺序存储的线性表
3、，访问结点和增加、删除结点的时间复杂度为( )。 A.O(n) O(n) B.O(n) O(1) C.O(1) O(n) D.O(1)O(1)4. 设栈的输入序列是1，2，3，4,则( )不可能是其出栈序列。A.1，2，4，3 B.2，1，3，4 C.1，4，3，2 D.4，3，1，2 5. 设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至
4、少是( )。A.4 B.3 C.2 D.16.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。A.栈 B.队列 C.树 D.串7. 串是一种特殊的线性表，下面哪个叙述体现了这种特殊性( )。A.可以顺序存储
5、 B.数据元素是一个字符 C.数据元素可以是多个字符 D.可以链接存储8.已知一棵完全二叉树的第6层（设根是第1层）有8个叶结点，则该完全二叉树的结点个数最多是( )。A.119 B.111 C.52 D.399.一个具有1025个结点的二叉树的高h为( )。A．10至1024之间 B．11至1025之间 C.10 D.1110. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点
6、的右子树上的结点个数是( )。A．M1+M2 B．M2+M3 CM3 D.M1 11. 设无向图的顶点个数为n，则该图最多有( )条边。 A．n-1 B．n2 C．n(n+1)/2 D．n(n-1)/212.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。A.(n-1)/2 B.n/2 C.n D.
7、(n+1)/213.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。A.(100,80,90,60,120,110,130) B.(100,120,110,130,80,60,90) C.(100,60,80,90,120,110,130) D.(100,80,60,90,120,130,110) 14.一组记录的关键字为{46、79、56、38、40、84},则利用快速排序的方法,以第一个记录为枢轴得到的一次划分结果是( )A.38、40、46、56、79、84 B.4
8、0、38、46、79、56、84 C.40、38、46、56、79、84
