《《数据结构(Java语言版)》试卷12页》由会员分享，可在线阅读，更多相关《《数据结构(Java语言版)》试卷12页（2页珍藏版）》请在金锄头文库上搜索。
1、长沙民政学院2015年 上 学期期末考试卷（A卷）考试科目： 数据结构 考试形式：闭卷适应班级：软开 1431-1439一、 单项选择（共20题，每题2分, 共40分）1、以下数据结构中哪一个是非线性结构？（ ）A. 队列 B. 栈 C. 二叉树 D. 线性表 2、（ ）不是算法的主要特性。A输入性 B输出性 C有穷性 D高效性3、（ ）不是线性表的存储结构。A叉链表 B单链表 C双向链表 D循环链表4、线性表是：A. 一个有限序列，可以为空； B. 一个有限序列，不能为空； C. 一个无限序列，可以为空； D. 一个无序序列，不能为空5、用链表表示线性表的优点是 （ ）。A.便于随机存取B.
2、花费的存储空间较顺序存储少C.便于插入和删除D.数据元素的物理顺序与逻辑顺序相同6、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。A. 单链表 B. 仅有头指针的单循环链表 C. 双链表 D. 仅有尾指针的单循环链表7、栈中元素的进出原则是（ ）A. 先进先出 B. 后进先出 C. 栈空则进 D. 栈满则出8、若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为( ) Ai Bn=i Cn-i+1 D不确定9、若依次输入数据元素序列a，b，c，d，e，f，g进栈，出栈操作可以和入栈操作间
3、隔进行，则下列哪个元素序列可以由出栈序列得到？( )A c，d，b，e，g，a，f B f，e，g，d，a，c，bCe，f，d，g，b，c，a Dd，e，c，f，b，g，a10、一个栈的入栈序列是1,2,3,4,5，则下列序列中不可能的出栈序列是( )A 2,3,4,1,5 B 2,3,1,4,5 C5,4,1,3,2 D1,5,4,3,211、判断一个循环队列( m0为最大队列长度（以元素为单位），front和rear分别为队列的队头指针和队尾指针 ) 为空队列的条件是( )。A front = rear B front != rearC front = (rear+1) % m0 D fr
4、ont != (rear+1) % m012、判断一个循环队列( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 )为满队列的条件是( )。A front= rear Bfront!= rearC front=( rear+1) % m0 D front!=( rear+1) % m013、串是一种特殊的线性表，其特殊性体现在（ ）。A可以顺序存储 B数据元素是一个字符 C可以链式存储 D数据元素可以是多个字符14、假设S=“abcaabcaaabca”，T=“bca”，S.indexOf (T,3) （其中3为索引号，索引号从0开始编号） 的结果是（
5、）A1 B5 C10 D015、二叉树的数据结构描述了数据之间的（ ）关系。A链接关系 B层次关系C网状关系 D随机关系16、（ ）遍历方法在遍历它的左子树和右子树后再遍历它自身。A先序遍历 B. 后序遍历C. 中序遍历 D. 层次遍历17、 在构造哈夫曼树的过程中说法正确的是（ ）。A. 使权值越大的叶结点越远离根结点，而权值越小的叶结点越靠近根结点B. 使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点C. 最终是带权路径长度最大的二叉树D. 构造的过程是一次到位18、55为最第一趟快速排序的基准值，执行一趟快速排序能够得到的序列是（A ）。A. 12，27，45，41 55
6、34，63，72B. 45，34，12，41 55 72，63，27C. 63，12，34，45，27 55 41，72D. 41，12，34，45，27 55 72，63 19、对线性表进行二分查找时，要求线性表必须( )。A以顺序方式存储 B以链接方式存储C以链接方式存储，且结点按关键字有序排序D以顺序方式存储，且结点按关键字有序排序 20、在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的键值（ ）。A一定都是同义词 B. 一定都不是同义词. 不一定都是同义词 D都相同 二、 判断题（共10题，每题2分, 共20分，正确打，错误
7、的打）三、 1-5 6-10 1、数据元素是组成数据的基本单位，数据项是组成数据元素的基本单位。 （ ）2、数据的逻辑结构是从逻辑的角度来观察数据，分析数据，与数据的存储位置无关。 （ ）3、链式存储结构是把数据元素存放在地址连续的存储单元里，借助元素在存储器中的相对位置来表示数据元素之间逻辑关系。 （ ）4、单链接表可以按双向遍历线性表中的每一个数据元素。 （）5、链表中删除和插入操作比顺序表快，但是元素的访问速度比顺序表要慢。 （）6、栈的主要特点是“先进先出”，队列的主要特点是 “后进先出”。 （）7、StringBuilder是非线程安全，StringBuffer是线程安全的。 （ ）
8、8、前序遍历是首先遍历根结点的左子树，再遍历根结点的右子树，最后访问根结点。（ ）9、插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。 （ ）10、二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。（ ）三、简答题（共题，每题10分，共20分）1、 设哈希表长m=14，哈希函数为H(k) = k MOD 11。如果用二次探测再散列处理冲突，请将关键字为15、38、49、61、84的记录填写在相应的存储单元中。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 0 1 2 3 4
9、5 6 7 8 9 10 11 12 1315386184492、 请分别给出下图中先序遍历、中序遍历、后序遍历和层次遍历的结果。先序遍历（A B D G C E F）、中序遍历（D G B A E C F）、后序遍历（G D B E F C A）和层次遍历（A B C D E F G）。四、 编程题（共20分，第1和第2小题各8分，第3小题4分）给定一组数据：1、编写冒泡排序算法public int bubbleSort(int data),实现对该组数据的排序。2、编写二分查找算法 public int binSearch(int data,int key)，实现对关键字key的查找。3、用给定的初始关键字编写测试程序，对两个算法进行测试。第 2 页 共 2 页
