搜索
清远职业技术学院2015-2016学年度第二学期《数据结构与算法(java版)》期末考试试题（A卷）院（系.部）级年制专业班学号姓名分数题号一二三总分得分评分人一、选择题（每题4分，共40分）1.对一个算法的评价，不包括如下（）方面的内容。A．健壮性和可读性B．并行性C．正确性D．时空复杂度2.在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为s,则修改链的java语句序列是（）。A.s.setNext(p);q.setNext(s);B.p.setNext(s.getNext());s.setNext(p);C.p.setNext(s);s.setNext(q);D.q.setNext(s.getNext());s.setNext(p);3.若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（）。A．1234B.1324C.4321D.14234.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串B．联接C．模式匹配D．求串长5.对一棵树进行后根遍历操作与对这棵树所对应的二叉树进行（）遍历操作相同。A．先根B.中根C.后根D.层次6.在哈夫曼树中，任何一个结点它的度都是（）。A．0或1B.1或2C.0或2D.0或1或27.若某棵二叉树的先根遍历序列为ABCDEF，中根遍历序列为CBDAEF，则这棵二叉树的后根遍历序列为（）。A．FEDCBAB.CDBFEAC.CDBEFAD.DCBEFA8.具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。A.5B.6C.7D.89.当待排序序列基本有序时，以下排序方法中，()最不利于其优势的发挥。A.直接选择排序B.快速排序C.冒泡排序D.直接插入排序10.若有一个长度为64的有序表，现用二分查找方法查找某一记录，则查找不成功，最多需要比较()次。A.9B.7C.5D.3二、填空题（每空1分，共20分）1.线性表是由n（n≥0）个数据元素所构成的有限序列，其中n为数据元素的个数，称为线性表的，n=0的线性表称为。2.顺序表中逻辑上相邻的数据元素，其物理位置相邻，而在单链表中逻辑上相邻的数据元素，其物理位置相邻。3.队列也是一种操作受限的线性表，它与栈不同的是，队列中所有的插入操作均限制在表的一端进行，而所有的删除操作都限制在表的另一端进行，允许插入的一端称为，允许删除的一端称为。4.一个串的任意连续字符组成的子序列称为串的，该串称为。5.深度为4的平衡二叉树中至少有个结点，至多有个结点。三、上机实践题（每题20分，共40分）答题要求提交如下资料：1)将代码复制到答卷中“【代码】：”处。2)运行结果中必须显示个人的名字，并截图复制到答卷中的“【运行效果图】：”处。如：3)提交完整的程序文件，并按题号分目录（如3.1、3.2）存放。1.编写一个顺序表类，实现对顺序表（顺序表长度为10，节点值为随机数字）就地逆置的操作。所谓逆置，就是把（a1,a2,…,an）变成（an,an-1,…,a1）；所谓就地，就是指逆置后的数据元素仍存储在原来顺序表的存储空间中，即不为逆置后的顺序表另外分配存储空间。2.编写一个排序方法类，实现用插入排序方法对单链表（链表长度为5，节点值为随机数字）进行排序。