川大计算机学院数据结构与算法分析期末
试题
中考模拟试题doc幼小衔接 数学试题 下载云南高中历年会考数学试题下载N4真题下载党史题库下载
(2007级B)_无答案
四川大学 期末考试试题
(2008-2009学年第1学期)
课程号: 课程名称: 数据结构与算法分析,B卷, 任课教师: 适用专业年级: 学号: 姓名:
考试须知
四川大学学生参加由学校组织或由学校承办的各级各类考试,必须严格执行《四川大学考试工作
管理办法
关于高温津贴发放的管理办法稽核管理办法下载并购贷款管理办法下载商业信用卡管理办法下载处方管理办法word下载
》和《四川大学考场规则》。
有考试违纪作弊行为的,一律按照《四川大学学生考试违纪作弊处罚
条例
事业单位人事管理条例.pdf信访条例下载信访条例下载问刑条例下载新准则、条例下载
》进行处理。
四川大学各级各类考试的监考人员,必须严格执行《四川大学考试工作管理办法》、《四川大学考场规则》和《四川大学监考人员职
责》。有违反学校有关规定的,严格按照《四川大学教学事故认定及处理办法》进行处理。
题 号 1 2 3 4 5 6 7 8 9 卷面成绩
20 10 10 10 10 10 10 10 10 得 分
阅卷教师
阅卷时间
一、单项选择题(每小题 2 分,共20分)
1(数据类型为( )。
A)数据项的集合 B)值的集合及定义在其上的一组操作的总称
C)数据元素的集合 D)关键字的集合
2(链表不具有的特点是( )。
A)可随机直接访问任一元素 B)插入删除不需要移动元素
C)不必事先估计元素个数 D)所需空间与线性表长度成正比 3(设一个栈的入栈序列是ABCD,则借助于一个栈所得到的出栈序列不可能是( )。
A)ABCD B)DCBA C)ABCD D)DABC 4(将对称矩阵A压缩存储在一维数组B[m]中,则m的值至少为( )。 nxn2A)n(n+1)/2 B)n(n-1)/2 C)n(n+1) D)n
5(设二叉树中有n个度为2的结点,n个度为1的结点,n个叶子结点,则此二叉树中空指针域个数为( )。 210
A)n+n+nB)n+n+2nC)2n+n D)2n+n 012 210 2101
6(对于具有n个顶点的强连图,其弧条数的最小值为( )。
A)n+1 B)n C)n-1 D)n-2
7(一棵深度为k的平衡二叉树,其每个非终端结点的平衡因子均为0,则该树共有( )个结点。 k-1k-1k-1kA)2-1 B)2 C)2+1 D)2-1 8(归并排序的时间复杂度是( )。 2A)O(1) B)O(n) C)O(n) D)O(nlogn) 9(每一趟都能选出一个元素放在其最终位置上,并且不稳定的排序算法是( )。
A)冒泡排序 B)简单选择排序 C)希尔排序 D)直接插入排序 10(按照二叉树的定义,具有3个结点的不同形态(相似)的二叉树有( )种。
A)3 B)4 C)5 D)6
二、(本题10分)
利用两个栈S1、S2模拟一个队列(如客户队列)时,如何用栈的运算实现队列的插入、删除运算,请简述算
法思想。
三、(本题10分)
已知一棵二叉树的先序序列与中序序列分别如下,试画出此二叉树。
先序序列:ABCDEFGHIJ
中序序列:CBEDAGHFJI
注:试题字迹务必清晰,
书
关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf
写工整。 本题2页,本页为第1页
教务处试题编号:
课程名称:数据结构与算法分析 任课教师: 学号: 姓名: 四、(本题10分)
对于权值序列w={7,5,2,4},试画出它对应的哈夫曼树。
五、(本题10分)
对于下图,用Kruskal算法构造出一棵最小生成树,要求图示出构造过程中每一步的变化情况。
六、(本题10分)
已知序列{4,1,7,1,3,8,2,},试构造二叉排序树。
七、(本题10分)
已知一组关键字为(19,14,23,1,68,20,84,27,55,11,10,79),哈希函数为H(key)=key MOD 13,
哈希地址空间为0~12,请构造用链地址法处理冲突的哈希表,并求平均查找长度。
八、(本题10分)
使用堆排序所使用的调整
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
把存放在数组中的10个数据元素45,25,15,80,50,75,60,40,35,70调整成一个堆。
九、(本题10分)
试写出按层次遍历二叉树的算法。
本题2页,本页为第2页
教务处试题编号: