2015年第二十一届全国青少年信息学奥林匹克联赛提高组初赛试题(C ).doc

2015年第二十一届全国青少年信息学
奥林匹克竞赛初赛提高组
一、选择题(共15题,)
1、在计算机内部用来传送、存贮、加工处理的数据或指令都是以()形式进行的。
A. 二进制码 B. 八进制码 C. 十进制码 D. 智能拼音码
2、下列说法正确的是()
A. CPU的主要任务是执行数据运算和程序控制
B. 存储器具有记忆能力,其中信息任何时候都不会丢失
C. 两个显示器屏幕尺寸相同,则它们的分辨率必定相同
D.
3、()
A. B. C. D.
4、下面有四个数据组,每个组各有三个数据,其中第一个数据为八进制数,第二个数据为十进制数,第三个数据为十六进制数。这四个数据组中三个数据相同的是()
A. 120 82 50 B. 144 100 68 C. 300 200 C8 D. 1762 1010 3F2
5、线性表若采用链表存储结构,要求内存中可用存储单元地址()
A. 必须连续 B. 部分地址必须连续 C. 一定不连续 D. 连续不连续均可
6、今有一空栈S,对下列待进栈的数据元素序列a,b,c,d,e,f依次进行进栈,进栈,出栈,进栈,进栈,出栈的操作,则此操作完成后,栈S的栈顶元素为()
A. f B. c C. a D. b
7、前序遍历序列与后序遍历序列相同的二叉树为()
A. 非叶子结点只有左子树的二叉树 B. 只有根结点的二叉树
C. 根结点无右子树的二叉树 D. 非叶子结点只有右子树的二叉树
8、如果根的高度是1,具有61个结点的完全二叉树的高度是()
A. 5 B. 6 C. 7 D. 8
9、6个顶点的连通图的最小生成树,其边数为()
A. 6 B. 5 C. 7 D. 4
10、设某算法的计算时间表示为递推关系式T(n)=T(n-1)+n (n为正整数)及T(0)=1,则该算法的时间复杂度为()
A. O(logn) B. O(nlogn) C. O(n) D. O(n2)
11、具有n个顶点,e条边的图采用邻接表存储结构,进行深度优先遍历和广度优先遍历运算的时间复杂度均为()
A. O(n2) B. O(e2) C. O(ne) (n+e)
12、在数据压缩编码的应用中,哈夫曼(Huffman)算法是一种采用了()思想的算法。
A. 贪心 B. 分治 C. 递推 D. 回溯
13、双向链表中有两个指针域,llink和rlink,分别指向前戏及后继,设p指向链表中的一个结点,q指向一待插入结点,现要求在p前插入q,则正确的插入为()
A. p->llink=q; q->rlink=p; p->llink->rlink=q;q->llink=p->llink;
B. q->llink=p->llink; p->llink->rlink=q; q->rlink=p; p->llink-q->rlink;
C. q->rlink=p; p->rlink=q; p->llink->rlink=q;q->rlink=p;
->llink->rlink=q; q->rlink=p; q->llink=p->llink; p->link=q;
14、对图G中各个结点分别指点一