2012_2013年上学期期末考试——数据结构——A卷新区.docVIP

安阳师范学院计算机与信息工程学院 11级计科、软工 专业 《数据结构》课程 2012—2013学年上学期期末考试试卷A 题号 一 二 三 四 五 合计 总分人 复核人 分数 分数 评卷人 一、填空题（每空1分，共10分） 1．数据元素之间的关系在计算机中有两种不同的表示方法，由此得到两种不同的存储结构： ______________和链式结构。 2．在有n个元素的顺序表中删除一个元素，所需要移动元素的平均个数是____________，具体移动元素的个数与元素位置有关。 3．1，2，3，…，n按照先后顺序入栈，则可能的出栈序列有__________________个。 4．假设有三维数组A[3][4][5]，每个元素长度为3个字节，假设从首地址SA＝0开始以行为主序存放在存储器中，则元素a[2][3][4]的存储位置为____________________。 5．设树T 的度为4，其中度为1，2，3 和4 的结点个数分别为4，2，1，1 则T 中的叶子结点个数为 个。 6．在一个图中，所有顶点的度数之和是图中边数之和的 倍。 7．一个有n个顶点、e条边的无向图的邻接表中有 个边结点。 8．假设G是一个具有21条边的非连通无向图（不含自回路和多重边），则图G至少有___________个顶点。 9．有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当折半查找到值为82的元素时,经过比较的关键字的序列为： 。 10．就平均时间性能而言， 排序被认为是目前最好的内部排序方法。 分数 评卷人 二、判断题 ( 本大题共 10小题，每小题 1 分，共10 分 ) （ ）1. 数据元素是数据的最小单位。 （ ）2. 一个“好”算法的标准是正确性，可行性，可读性和健壮性。 （ ）3. 存取单链表中第i个元素时花费的时间同i的大小有关。 （ ）4. 栈和队列都是限制了存取点的线性结构。 （ ）5．数组不适合作为任何二叉树的存储结构。 （ ）6．树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。 （ ）7．在n 个结点的无向图中，若边数大于n-1,则该图必是连通图。 （ ）8．一个网（带权图）都有唯一的最小生成树。。 （ ）9．顺序查找法适用于存储结构为顺序或链接存储的线性表。。 （ ）10．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大顶堆”。 分数 评卷人 三、选择题：（每小题2分，共40分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将其代码填在相应表格内。错选或未选均无分。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 （ ）1. 以下哪一个术语与数据的存储结构无关？ A．栈 B．双向链表 C．线索二叉树 D．哈希表 （ ）2. 链表不具有的特点是（ ） A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 （ ）3. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。。 A． 顺序表 B．单循环链表 C． 双链表 D．带头结点的双循环链表 （ ）4. 在循环双链表的p所指节点之后插入s所指节点的操作是( )。 A.p-right=s；s-left=p；p-right-left=s；s-right=p-right；s-left=p；s-right=p-right；p-right-left=s；p-right=s；s-left=p；s-right=p-right；p-right=s；p-right-left=s； p-right=s；p-right-left=s；s-left=p；s-right=p-right； （ ）7. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为 第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。 A. 13 B. 33 C. 18 D. 40 （ ）8. 在下述结论中，正确的是（ ）。 ①只有一