2005级数据结构A及答案.doc

浙江工商大学2006/2007学年第一学期考试试卷 课程名称： 《数据结构》 考试方式： 闭卷 完成时限：120分钟 班级名称： 学号： 姓名： 题号 一 二 三 四 五 六 总分 分值 10 10 10 14 20 36 100 得分 阅卷人 判断题（每题1分，共10分） 数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。................................( ) 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储结构相关，是依赖于计算机的。................................( ) 线性表中的每个结点最多只有一个直接前驱和一个直接后继。..................................................( ) 线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。........................................( ) 二维数组是其数组元素为线性表的线性表。................( ) 单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。..................................( ) 由一棵二叉树的前序序列和后序序列可以唯一确定它。......( 错 ) 在数据的存放无规律而言的线性表中进行查找的最佳方法是顺序查找（线性查找）。......................................( ) 多重表文件和倒排文件都归属于多关键字文件。............( ) 不定长文件是指文件的长度不固定。..................... ( ) 填空题（每题1分，共10分） 若将数据结构形式定义为二元组(D，R)，其中D是数据元素的有限集合，则R是D上 关系的有限集合 。 在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为 。 若不带头结点的单链表的头指针为head，则该链表为空的判定条件是 。 对于顺序存储的栈，因为栈的空间是有限的，在进行 运算时，可能发生栈的上溢，在进行 运算时，可能发生栈的下溢。 树的存储结构常见的有 双亲表示法 ， 孩子链表法 ， 孩子-兄弟表示法 。 深度为k的完全二叉树至少有 个结点，至多有 个结点。 一棵有n个结点的满二叉树有 0 个度为1的结点、有 （n-1）/2 个分支 （非 终端）结点和 (n+1)/2 个叶子，该满二叉树的深度为 ?log2n? + 1 。 大多数排序算法都有两个基本的操作 和 。 线性有序表（a1，a2，a3，…，a256）是从小到大排列的，对一个给定的值k，用二分法查找表中与k相等的元素，在查找不成功的情况下，最多需要查找 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键字按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是 ；初始步长为4的希尔（shell）排序一趟的结果是 ；快速排序一趟扫描的结果是 。 选择题（每题1分，共10分） 算法指的是 ( ) A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列 线性表采用链式存储时，结点的存储地址 ( ) A．必须是不连续的 B．连续与否均可 C．必须是连续的 D．和头结点的存储地址相连续 将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为 ( ) A．O(1) B．O(n) C．O(m) D．O(m+n) 已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行操作 ( ) A. s-link = p； p-link = s； B. s-link = p-link； p-link = s； C. s-link = p-link； p = s； D. p-link = s； s-link = p； 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是 (D ) A. 2，4，3，1，5，6　　 B. 3，2，4，1，6，5