《数据结构》期末试卷(A卷).docVIP

2012 A卷 【 字号： 大 中 小 】 2011－2012年 春 季学期计算机科学与技术、软件工程、网络工程专业 《数据结构》期末试卷（A卷） 卷面总分：100分??????? 答题时间：120分钟 ? 专业??????? 年级??? ?班级???? ?姓名????????? 学号????? ???? 题号 一 二 三 四 五 六 七 八 九 十 总分 得分 ? ? ? ? ? ? ? ? ? ? ? 一、???????????? 单项选择题（本大题共15小题，每小题1分，共15分?答案写在答题卡上） 答题卡?题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ??? 答案 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1. ?? 设n是描述问题规模的非负整数，下面程序片段的时间复杂度是(??? )。 ????????????? x=2; ????????????? while(xn/2) ???????????????????? x=2*x; A. O(log2n)???????????? ?????? B. O(n)????????? ?????? C. O(nlog2n)????????? ?????? D. O(n2) 2.??? 线性表是具有n个(??? )的有限序列（n0）。?????????? A．表元素???????? ???? ?B．数据元素??? ?C．字符??? ???????????? D．数据项???????? 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的容量至少是(??? )。 A. 4??????????? ????????? B.3?????????? ??? ?C.2????????????? ??? ?D. 1 6. 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是(??? )。 A. 栈???????????? ????? B. 队列????????? C. 树??? ????????????? D. 串 7.??? 串是一种特殊的线性表，下面哪个叙述体现了这种特殊性(??? )。 A. 可以顺序存储???????????????????????? B.数据元素是一个字符? C. 数据元素可以是多个字符??????? D. 可以链接存储 8.已知一棵完全二叉树的第6层（设根是第1层）有8个叶结点，则该完全二叉树的结点个数最多是(??? )。 A. 119????????? ?? B. 111????????? C. 52????????D. 39 9. 一个具有1025个结点的二叉树的高h为(??? )。 A．10至1024之间??? B．11至1025之间??????????? C. 10??????? D. 11 10.?? 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是(??? )。 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)/2 12. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为(??? )。 A. (n-1)/2????? ???? B. n/2?????? C. n????? ??????????? D. (n+1)/2 13. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(??? )。 A.(100,80,90,60,120,110,130)???B.(100,120,110,130,80