试题(张艳玲)-6.docVIP

学院领导 审批并签名 A B卷 广州大学 学年第 学期考试卷 课程 数据结构与算法 考试形式（闭卷，考试） 信息学院 系 专业 级 班 学号： 姓名： 题次 一 二 三 四 五 六 总分 评卷人 分数 20 10 10 30 20 10 100 评分 填空题：（每空2分，共20分） 抽象数据类型的特点是________、________、使用与实现分离。 算法的一个特性是________，即算法必须执行有限步就结束。 3、一维数组所占用的空间是连续的。但数组元素不一定顺序存放，而是按元素的_________存放的。 4、将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则一维数组需要存储_________个矩阵元素。 5、在单链表中设置表头结点的作用是在插入和删除表中第一个元素时不必对________进行特殊处理。 6、中缀表达式3*(x+2)-5所对应的后缀表达式为________。 7、广义表A ( (a, b, c), (d, e, f ) ) 的表尾为________。 8、假定一棵三叉树（即度为3的树）的结点个数为50，则它的最小高度为______。假定根结点的高度为0。 9、 101个顶点的连通网络N有100条边，其中权值为1, 2, 3, 4, 5, 6, 7, 8, 9, 10的边各10条，则网络N的最小生成树各边的权值之和为_________。 单项选择题（每空1分，共10分） 一个数组元素a[i] 与（ ）的表示等价。 A. *(a+i) B. a+i C. *a+i D. a+i 一种抽象数据类型包括数据和（ ）两个部分。 A. 数据类型 B. 操作 C. 数据抽象 D. 类型说明 以下说法错误的是（ ）。 A. 抽象数据类型具有封装性。 B. 抽象数据类型具有信息隐蔽性。 C. 抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作。 D. 抽象数据类型的一个特点是使用与实现分离。 4、在一个长度为n的顺序表中顺序有哪些信誉好的足球投注网站一个值为x的元素时，在等概率的情况下，有哪些信誉好的足球投注网站成功的数据平均比较次数为（ ）。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 5、在一个长度为n的顺序表中向第i个元素（0≤i≤n）位置插入一个新元素时，需要从后向前依次后移（ ）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 6、不带头结点的单链表first为空的判定条件是： A. first == NULL; B. first-link == NULL; C. first-link == first; D. first != NULL; 7、栈的插入和删除操作在（ ）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 8、在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（ ），在被调用程序中可直接操纵实际参数。 A. 空间 B. 地址 C. 返回地址 D. 副本 9、在一棵树中，（ ）没有前驱结点。 A. 分支结点 B. 叶结点 C. 根结点 D. 空结点 10、在一个带权连通图G中，权值最小的边一定包含在G的（ ）生成树中。 A. 某个最小 B. 任何最小 C. 广度优先 D.深度优先 三、判断题（在括号内填上“√”或“╳”，每题1分，共10分，做错不倒扣） （ ）数据结构是具有结构的数据对象。 2、（ ）数据结构是指相互之间存在一种或多种关系的数据元素的全体。 3、（ ）数组是一种静态的存储空间配置，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行配置。 4、（ ）n阶三对角矩阵总共n2个矩阵元素中最多只有3n-2个非零元素，因此它是稀疏矩阵。 5、（ ）链式存储在插入和删除时需要保持数据元素原来的物理顺序，不需要保持原来的逻辑顺序。 6、（ ）若让元素1, 2, 3依次进栈，则出栈次序3, 1, 2是不可能出现的情况。 7、（ ）递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要分配额外的空间和传递数据和控制，所以时间