好文档 - 专业文书写作范文服务资料分享网站

《华南农业大学期末考试试卷》-数据结构-A卷

天下 分享 时间: 加入收藏 我要投稿 点赞

装订线

华南农业大学期末考试试卷(A卷)

2011-2012学年第 1 学期 考试科目: 数据结构(JAVA) 考试类型:(闭卷)考试 考试时间: 120 分钟

学号 姓名 年级专业 2010级信管 班

答案请写到答题纸上,写在试卷上无效

一、单选题(本大题共10小题,每小题2分,共20分)

1. 不考虑优先队列,已知入队序列为{A,B,C,D},可能的出队序列为:()

A. {D,B,C,A} B. {A,B,C,D} C. {A,D,C,B} D. {A,C,D,B}

2. 已知结点数为1001的完全二叉树,其叶子结点个数为:()

A.500 B.501 C.602 D.1

3. 具有8000个结点的二叉树,其高度至少为:()

A.10 B.11 C. 12 D.13

4. 设一棵哈夫曼树有n个非叶子结点,该树共有()个节点

A.n B.2n-1 C.2n+1 D. 2n 5. 归并排序的空间复杂度是:()

A. O(nlog2n) B. O(n2) C. O(log2n) D. O(n) 6. 以下程序时间复杂度为:()

int n=8,m=1024,count=1024; for (int i=m; i>=1; i--) count++;

A.O(1) B. O(m) C. O(log2m) D. O(mlog2m) 7. 式n+log2n+n*n*n的时间复杂度为:()

A.O(1) B. O(n3) C. O(n+log2n) D. O(log2n) 8. 衡量算法的标准有:()

A.时间复杂度和空间复杂度 B.输入和输出 C.有穷性和确定性 D.可行性 9. 已知入栈顺序为{a,b,c,d,e,f,g},下列哪个是可能的出栈顺序:()

A. {d,e,c,f,b,g,a} B. {f,e,g,d,a,c,b} C. {e,f,d,g,b,c,a} D. { e,f,d,g,b,a,c } 10. 已知一个顺序循环队列最多能容纳60个元素,当前有58个元素时,如果再

插入5个元素,该队列有多少空元素:() A.-3 B.63 C.5 D.57 二、填空题(本大题共10小题,每空1分,共20分)

1. 软件设计是计算机学科各个领域的核心。软件设计时要考虑的首要问题是数

据的表示、组织和处理方法。______和______是软件系统设计的核心。 2. 双链表的插入和删除操作:q = new DLinkNode(x); ______;q.next =

p;p.prev.next = q; ______。

3. 两个顺序表相等是指它们各对应______并且______。

4. 设一棵二叉树的叶子结点数为n0,2度结点数为n2,则n0=______。N个节

点完全二叉树的高度是______

第 1 页 共 6 页

5. 设嵌套广义表Z=(e, Z)=(e, (e, (e, (…)))),则Z的长度为______,深度______。

6. 在树结构中,约定根节点的层次为______,其他节点的层次是其父母节点的层次加______。

7. 树的表示法有:图示法、______和______三种。

8. 一棵高度为k(k>=0)的完全二叉树是具有至多______个结点的二叉树,一棵高度为k(k>=0)的满二叉树是具有至少______个结点的二叉树。中根遍历序列和后根遍历序列相反的二叉树是______,由256个权值构造一棵哈夫曼树,则该二叉树共有______结点。

9. 由n个顶点组成的无向连通图,最多可以有______条边。

10. 10个元素的排序数据序列采用折半查找的平均查找长度是(写出算式)______。 三、程序分析题 (本题共2小题,每小题8分,共16分) 1. 下列该程序片段的运行结果是:____________________。

//import dataStructure.linearList.LinkedStack; //链式栈(略) public class Exp_bracket {

public static String isValid(String expstr) //判断expstr表达式中的圆括号是否匹配

{ //返回错误信息 LinkedStack stack = new LinkedStack(); //创建空栈 int i=0;

while(i

char ch=expstr.charAt(i); i++; switch(ch) {

case '(': stack.push(ch+\ //左括号入栈 break;

case ')': if (stack.isEmpty() || !stack.pop().equals(\遇见右括号时,出栈 return \期望(\ //判断出栈字符是否为左括号 } }

if(stack.isEmpty())

return \ //返回空串表示没有错误

else

return \期望)\ }

public static void main(String args[]) {

String expstr=\

System.out.println(expstr+\ \isValid(expstr));

2

装 expstr=\

System.out.println(expstr+\ \isValid(expstr)); expstr=\

System.out.println(expstr+\ \isValid(expstr)); expstr=\

System.out.println(expstr+\ \isValid(expstr)); }

}

2.

//package dataStructure.tree;

//import dataStructure.tree.BinaryNode; //二叉树的二叉链表结点类(略) //import dataStructure.linearList.LinkedQueue; //链式队列(略) //import dataStructure.linearList.LinkedStack; //链式栈(略) //构造并遍历二叉树。 public class BinaryTree_make {

订线 public static BinaryTree make() //构造给定的一棵二叉树 {

BinaryTree bitree=new BinaryTree(); //创建空二叉树 BinaryNode child_f, child_d, child_b, child_c;

child_d = new BinaryNode(\ child_b = new BinaryNode(\

child_f = new BinaryNode(\ child_c = new BinaryNode(\ bitree.root = new BinaryNode(\ return bitree; }

public static void main(String args[]) {

BinaryTree bitree = make();

bitree.preOrder(); //先根次序遍历二叉树 bitree.inOrder(); //先根次序遍历二叉树 bitree.postOrder(); //后根次序遍历二叉树

第 3 页 共 6 页

bitree.levelOrder(); //层次遍历二叉树 } }

则程序运行结果如下:

先根次序遍历二叉树(写出字母顺序):______ 中根次序遍历二叉树(写出字母顺序):______ 后根次序遍历二叉树(写出字母顺序):______ 层次遍历二叉树(写出字母顺序): ______

四、简答题 (本题共6小题,每小题6分,共36分)

1. 什么是栈和队列?两者有何异同?什么情况下需要使用栈或队列?采用顺序存储结构的栈和队列,在进行插入、删除操作时需要移动数据元素吗?为什么?什么是队列的假溢出?为什么顺序存储结构队列会出现假溢出?怎样解决队列的假溢出问题?链式存储结构队列会出现假溢出吗?顺序存储结构的栈会出现假溢出吗?为什么?

2. 已知一棵二叉树的中根次序遍历序列为CBDFEGAMLNKJOPRQIHS,后根次序遍历序列为CFGEDBMNLKRQPOJISHA,画出这棵二叉树(3分)并进行中序线索化(3分)。

3. 设一段正文由字符集{A,B,C,D,E,F,G,H}组成,其中每个字符在正文中的出现次数依次为{23,5,17,4,9,31,29,18},采用Huffman编码对这段正文进行压缩存储,画出所构造的Huffman树,并写出每个字符的Huffman编码(4分)。说明Huffman编码的特点和作用(2分)。

4. 利用Prim算法构造以下从A节点出发的带权无向图的最小生成树,给出该最小生成树的代价。

A7B12419C56G13151620DF10E11B12C4A6GF10E11DB12C4A6GEB4FA6GF10E (c)Prim算法不断扩充T,(d)Kruskal5. 什么是二叉排序树?画出由关键字序列{25,27,30,12,11,18,14,20,15,22}构造算法不断合并树,依次(a)带权无向图(b)最小生成树,代价为45T顶点扩充次序为AGBC……选择边(B,G),(A,G),(C,D),(E,F)……的一棵二叉排序树,计算ASL成功。画出删除节点12,然后再插入节点12后的二叉排序树。

6. 下列removeAll()方法欲删除target串中所有与pattern匹配的子串。 public static StringBuffer removeAll(StringBuffer target, String pattern) {

int m=target.length(), n=pattern.length(); int i=target.indexOf(pattern), k=i; while (k!=-1) { int j=k+n;

55DC5D 4

装 k=target.indexOf(pattern, j);

while (k>0 && j

target.setCharAt(i++, target.charAt(j++)); }

return target; }

① 对于以下调用语句,运行结果是什么?正确的运行结果是什么? StringBuffer target = new StringBuffer(\ System.out.println(removeAll(target, \

五、程序设计题 (本题共1小题,共8分)

//使用顺序表类SeqList求解约瑟夫环问题。 public class Josephus {

//创建约瑟夫环并求解,参数指定环长度、起始位置、计数 public Josephus(int number, int start, int distance) {

SeqList list = new SeqList(number);

//采用顺序表存储约瑟夫环的元素,元素类型是字符串,构造方法参数指定顺序表容量

for (int i=0; ① ______; i++)

②______; //添加字符串对象

System.out.print(\约瑟夫环(\,\ ③______; //输出顺序表的描述字符串

int i = start; //计数起始位置

while (list.length()>1) //多于一个对象时循环 {

④______;

System.out.print(\删除\,\ //删除指定位置对象

System.out.println(list.toString()); }

System.out.println(\被赦免者是\ }

public static void main(String args[]) {

new Josephus(5,0,2); } } /*

程序运行结果如下:

约瑟夫环(5,0,2),(A, B, C, D, E)

订线 第 5 页 共 6 页

《华南农业大学期末考试试卷》-数据结构-A卷

装订线华南农业大学期末考试试卷(A卷)2011-2012学年第1学期考试科目:数据结构(JAVA)考试类型:(闭卷)考试考试时间:120分钟学号姓名年级专业2010级信管班答案请写到答题纸上,写在试卷上
推荐度:
点击下载文档文档为doc格式
2u2ki69app1j03v4hzfz
领取福利

微信扫码领取福利

微信扫码分享