全国计算机等级考试二级教程---公共基础知算法与数据结构试题.doc

全国计算机等级考试二级教程-公共基础知识第一章 数据结构与算法 考点题型总结 3.算法的有穷性是指 A）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的 D）算法只能被有限的用户使用4.下列叙述中正确的是A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间复杂度必定小D）上述三种说法都不对6.下列叙述中正确的是A）算法的效率只与问题的规模有关，而与数据的存储结构无关B）算法的时间复杂度是指执行算法所需要的计算工作量C）数据的逻辑结构与存储结构是一一对应的D）算法的时间复杂度与空间复杂度一定相关1.(08年4月填空题第3题)设某循环对列的容量为50，头指针front=5（指向对头元素的前一位置），尾指针rear=29（指向队尾元素），则该循环队列中共有 个元素。2.设某循环对列的容量为50，头指针front=45（指向对头元素的前一位置），尾指针rear=10（指向队尾元素），则该循环队列中共有 个元素。5. （1）顺序存储结构:它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。 （2）链式存储结构：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。 （3）索引：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。 7.下列叙述中正确的是A）数据的逻辑结构与存储结构必定是一一对应的B）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C）程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构D）以上三种说法都不对8.按“先进后出”原则组织数据的数据结构是 。9.数据结构分为线性结构和非线性结构，带链的队列属于 。10.下面对队列的叙述正确的是A) 队列属于非线性表 B) 队列按“先进后出”原则组织数据C) 队列在队尾删除数据 D) 队列按“先进先出”原则组织数据11.数据的逻辑结构反映数据元素之间的逻辑关系，数据的存储结构（也称数据的物理结构）是数据的逻辑结构在计算机存储空间中的存放形式。同一种逻辑结构的数据可以采用不同的存储结构，但影响数据处理效率。12.线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的 存储结构。13.某二叉树中有n个度为2的结点,则该二叉树中的叶子结点数为 A)n+1 B)n-1 C)2n D)n/214.某完全二叉树中有n（n=2k时，n=2k+1时）的结点,则该二叉树中的叶子结点数为 15. 在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。一颗二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为 A）219 B）221 C）229 D）23116.深度为5的满二叉树有 个叶子结点。17. 对下列二叉树进行前序遍历的结果为 A)DYBEAFCZX B)YDEBFZXCA C)ABDYECFXZ D)ABCDEFXYZ ABCDEFXYZ18.下列对于线性链表的描述中正确的是 。（2005年4月）A. 存储空间不一定是连续，且各元素的存储顺序是任意的B. 存储空间不一定是连续，且前件元素一定存储在后件元素的前面C. 存储空间必须连续，且前件元素一定存储在后件元素的前面D. 存储空间必须连续，且各元素的存储顺序是任意的答案 A19. 下列叙述中正确的是 （2010年9月）A. 线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B. 线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C. 线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D. 上述三种说法都不对20.下列叙述中正确的是 （2009年3月）A.栈是“先进先出”的线性表B.队列是“先进后出”的线性表C.循环队列是非线性结构D.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构21. 下列描述的不是链表的优点的是_。A. 逻辑上相邻的结点物理上不必相邻B. 插入、删除运算操作方便，不必移动结点C. 所需存储空间比线性表节省D. 无需事先估计存储空间的大小22用链表表示线性表的优点是_。A. 便于插入和删除操作B. 数据元素的物理顺序与逻辑顺序相同C. 花费的存储空间较顺序存储少D. 便于随机存取23.下列叙述中，错误的是_。A. 线性表是由n个数据元素组成的一个有限序列B. 线性表是一种线性结构C. 线性表的所有结点有且只有一个前件和一个后件D. 线性表可以是空表24. 线性表采用链式存储时，结点的存储地址 A. 必须是不连续的B. 连续与否均可C. 必须是连续的D. 和头节点的存储地址相连续25. 在循环链表中，增加头结点的目的是_。A. 方便运算的实现B. 使单链表至少有一个结点C. 标识表结点中首结点的位置D. 说明单链表是线性表的链式存储实现26.对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是 A）快速排序 B）冒泡排序