吉林大学珠海学院数据结构期末卷.docVIP

2008年 A卷 【 字号： 大 中 小 】 春 季学期计算机科学与技术、软件工程专业 《数据结构》 期末试卷（A卷） 卷面总分：100分 答题时间：120分钟 ? 专业 年级 班级 姓名 学号 题号 一 二 三 四 五 六 七 八 九 十 总分 得分 ? ? ? ? ? ? ? ? ? ? ? 一、???????????? 单项选择题（本大题共15小题，每小题1分，共15分 答案写在答题卡上） 答题卡 题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 答案 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1、算法分析的目的是（ ） A、找出数据结构的合理性 B、研究算法中的输入和输出的关系 C、分析算法的效率以求改进 D、分析算法的易懂性和文档特点 2．下面关于线性表的叙述中，错误的是哪一个？（ ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 4、选择题：循环队列存储在数组A[0..m]中，则入队时的操作为( )。 A. rear=rear+1 B. rear=(rear+1) % (m-1) C. rear=(rear+1) % m D. rear=(rear+1) % (m+1) 5、下面关于串的的叙述中，哪一个是不正确的？（ ） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 6、对矩阵压缩存储是为了（ ）。 A.方便运算 B.方便存储 C.提高运算速度 D.减少存储空间 7、有关二叉树下列说法正确的是（ ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 8、二叉树的第I层上最多含有结点数为（ ） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 9、设无向图的顶点个数为n，则该图最多有（ ）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 10、图的BFS生成树的树高比DFS生成树的树高（ ） A.小或相等 B.小 C.大或相等 D.大 11、下列说法不正确的是（ ）。 A．图的遍历是从给定的源点出发每个顶点仅被访问一次 B．遍历的基本方法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程 12、对线性表进行二分查找时，要求线性表必须（ ） A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序 13、下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）。 A．选择排序法 B. 插入排序法 C. 快速排序法 D. 堆排序法 14、一个排序算法的时间复杂度与以下哪项有关。（ ） A．排序算法的稳定性 B. 所需比较关键字的次数 C. 所采用的存诸结构 D. 所需辅助存诸空间的大小 15、下述文件中适合于磁带存储的是（ ） A. 顺序文件 B. 索引文件 C. 散列文件 D. 多关键字文件 二、判断题（本大题共 5小题，每小题 1 分，共 5 分正确的打“√”，错误打“×”）， 1、 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。（ ） 2、 在单链表中，要取得某元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（ ） 3