数据结构期末考卷12-13级.docVIP

诚信应考 考出水平 考出风格 浙江大学城市学院 2012 — 2013 学年第 一 学期期末考试试卷 《 数据结构基础 》 开课单位： 计算分院 ；考试形式：闭卷；考试时间： 2013 年 1 月 12 日； 所需时间： 120 分钟 题序 一 二 三 四 五 六 总 分 得分 评卷人 得分 一．选择题 (本大题共 15 题，每题 1 分，共 15 分) 1. 数据结构形式地定义为（K，R），其中K是 的有限集合，R是K上的关系的有限集合。 A. 算法 B. 数据元素 C. 数据操作 D. 逻辑结构 2．数据在计算机内存中的表示是指 。 A. 数据的存储结构 B. 数据结构 C. 数据的逻辑结构 D. 数据元素之间的关系 3. 某算法的时间复杂度为f(n)= 8log2n+5n+2，若采用数量级的形式表示，应该是 。 A．O(8log2n+5n+2) B．O(log2n+n) C．O(n) D．O(log2n) 7．以下不是栈的基本运算的是 A．删除栈顶元素 B. 删除栈底元素 C．判断栈是否为空 D. 将栈置为空栈 . 向一个栈指针为HS的链式栈中插入一个s所指的结点时则执行 A. HS-NEXT=S; B. S-NEXT=HS-NEXT;HS-NEXT=S; C. S-NEXT=HS;HS=S; D. S-NEXT=HS;HS=HS-NEXT; 9. 在一个链式队列中假设f和r分别为队头和队尾指针则插入s所指的结点运算是 A. f-next=s;f=s; B. r-next=s;r=s; C. s-next=s;r=s; D. s-next=f;f=s; 10. 数组Q[0n-1]用来表示一个环形队列，f为当前头元素的前一位置，r为队尾元素的位置，假定队列中元素个数的总小于n，计算队列中元素个数的公式为 A. r-f B. n+f-r C. n+r-f D. (n+r-f)mod n 11. 递归函数调用时，为保存局部变量及返回地址，要用一种称为 的数据结构。A. 队列 B. 栈 C. 多维数组 D. 线性表 1000个结点的完全二叉树从上到下，从左到右依次进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为 。 A. 98 B. 99 C. 50 D. 没有右孩子 13．对二叉树的结点从1开始进行编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用 遍历实现编号。 A. 先序 B. 中序 C. 后序 D. 层序 14．假设一个有n个顶点和e条边的有向图用邻接表表示，则删除与某个顶点相关联的所有边的时间复杂度是___________。 A. O(n) B. O(e) C. O(n+e) D. O(n*e) 15．分析下面的无向图，从顶点A出发的深度优先有哪些信誉好的足球投注网站序列为___________。 A. ABDGEHFC B. ABCDEFGH C. ABDEGCFH D. ACEHFDBG 得分 二．填空题 (本大题共 20 个空，每个空 1 分，共 20 分) 线性结构中元素之间存在着⑴ 关系，图形结构中元素之间存在着⑵