资源描述:
《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