《数据结构(Java语言版)》试卷1.pdf

《《数据结构(Java语言版)》试卷1.pdf》由会员分享，可在线阅读，更多相关《《数据结构(Java语言版)》试卷1.pdf（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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.一个无序序列

2、，不能为空 5、用链表表示线性表的优点是（）。A.便于随机存取 B.花费的存储空间较顺序存储少 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、若依次输入数

3、据元素序列a，b，c，d，e，f，g进栈，出栈操作可以和入栈操作间隔进行，则下列哪个元素序列可以由出栈序列得到()A c，d，b，e，g，a，f B f，e，g，d，a，c，b Ce，f，d，g，b，c，a Dd，e，c，f，b，g，a 10、一个栈的入栈序列是 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,2 11、判断一个循环队列(m0为最大队列长度（以元素为单位），front 和 rear 分别为队列的队头指针和队尾指针)为空队列的条件是()。A front=rear B front!=rea

4、r C front=(rear+1)%m0 D front!=(rear+1)%m0 12、判断一个循环队列(m0为最大队列长度(以元素为单位)，front 和 rear 分别为队列的队头指针和队尾指针)为满队列的条件是()。A front=rear Bfront!=rear C front=(rear+1)%m0 D front!=(rear+1)%m0 13、串是一种特殊的线性表，其特殊性体现在（）。A可以顺序存储 B数据元素是一个字符 C可以链式存储 D数据元素可以是多个字符 14、假设 S=“abcaabcaaabca”，T=“bca”，(T,3)（其中 3 为索引号，索引号从 0 开

5、始编号）的结果是（）A1 B5 C10 D0 谋事在人，成事在天！增广贤文谋事在人，成事在天！增广贤文15、二叉树的数据结构描述了数据之间的（）关系。A链接关系 B层次关系 C网状关系 D随机关系 16、（）遍历方法在遍历它的左子树和右子树后再遍历它自身。A先序遍历 B.后序遍历 C.中序遍历 D.层次遍历 17、在构造哈夫曼树的过程中说法正确的是（）。A.使权值越大的叶结点越远离根结点，而权值越小的叶结点越靠近根结点 B.使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点 C.最终是带权路径长度最大的二叉树 D.构造的过程是一次到位 18、55 为最第一趟快速排序的基准值，执行一

6、趟快速排序能够得到的序列是（A）。A.12，27，45，41 55 34，63，72 B.45，34，12，41 55 72，63，27 C.63，12，34，45，27 55 41，72 D.41，12，34，45，27 55 72，63 19、对线性表进行二分查找时，要求线性表必须()。A以顺序方式存储 B以链接方式存储 C以链接方式存储，且结点按关键字有序排序 D以顺序方式存储，且结点按关键字有序排序 20、在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的键值（）。A一定都是同义词 B.一定都不是同义词.不一定都是同义词 D都

7、相同 二、判断题（共 10 题，每题 2 分,共 20 分，正确打，错误的打）三、1-5 6-10 1、数据元素是组成数据的基本单位，数据项是组成数据元素的基本单位。（）2、数据的逻辑结构是从逻辑的角度来观察数据，分析数据，与数据的存储位置无关。（）3、链式存储结构是把数据元素存放在地址连续的存储单元里，借助元素在存储器中的相对位置来表示数据元素之间逻辑关系。（）4、单链接表可以按双向遍历线性表中的每一个数据元素。（）5、链表中删除和插入操作比顺序表快，但是元素的访问速度比顺序表要慢。（）6、栈的主要特点是“先进先出”，队列的主要特点是“后进先出”。（）7、StringBuilder 是非线程

8、安全，StringBuffer 是线程安全的。（）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、 9 10 11 12 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 38 61 84 49 2、请分别给出下图中先序遍历、中序遍历、后序遍历和层次遍历的结果。人人好公，则天下太平；人人营私，则天下大乱。刘鹗其身正，不令而行；其身不正，虽令不从。论语 先序遍历（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 分）给定一组数据：70304010802090100756045初始关键字012345678910 1、编写冒泡排序算法 public int bubbleSort(int data),实现对该组数据的排序。2、编写二分查找算法 public int binSearch(int data,int key)，实现对关键字 key 的查找。3、用给定的初始关键字编写测试程序，对两个算法进行测试。