2014-2015-1福建师范大学软件学院数据结构试卷A卷.doc

2014-2015-1福建师范大学软件学院数据结构试卷A卷.doc

ID:56271093

大小:549.50 KB

页数:7页

时间:2020-06-05

2014-2015-1福建师范大学软件学院数据结构试卷A卷.doc_第1页
2014-2015-1福建师范大学软件学院数据结构试卷A卷.doc_第2页
2014-2015-1福建师范大学软件学院数据结构试卷A卷.doc_第3页
2014-2015-1福建师范大学软件学院数据结构试卷A卷.doc_第4页
2014-2015-1福建师范大学软件学院数据结构试卷A卷.doc_第5页
资源描述:

《2014-2015-1福建师范大学软件学院数据结构试卷A卷.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、福建师范大学软件学院2014—2015学年第1学期考试A卷考      生      信      息      栏______学院______系______专业______年级    姓名______学号___装订线专业:年级:课程名称:数据结构任课教师:试卷类别:开卷()闭卷(√)考试用时:120分钟考试时间:年月日午点分题号一二三四五总得分评卷人得分题号六七八九十得分一、单项选择题(每小题2分,共30分)1.用来表达一对多关系的数据结构是()。A.树B.图C.栈D.线性表2.在具有n个结点的有序单链表中插入一个新结点,并使链

2、表仍然有序,该操作的时间复杂度是()A.O(1)B.O(n)C.O(nlogn)D.O(n2)3.队和栈的主要区别是()A.逻辑结构不同B.存储结构不同C.所包含的运算个数不同D.限定插入和删除的位置不同4.链栈与顺序栈相比,比较明显的优点是()A.插入操作时间复杂度更低B.删除操作时间复杂度更低C.无需多次申请和释放空间D.不会出现上溢的情况5.下列编码中属前缀码的是()A.{1,01,000,001}B.{1,01,011,010}C.{0,10,110,11}D.{0,1,00,11}6.二叉树中第5层上的结点个数最多为()

3、A.8B.15C.16D.327.如果求一个连通图中以某个顶点为根的高度最小的生成树,应采用(   )A.深度优先搜索算法B.广度优先搜索算法C.求最小生成树的prim算法D.拓扑排序算法8.对n个关键字的序列进行快速排序,平均情况下的时间复杂度为()A.O(1)B.O(logn)C.O(n)D.O(nlogn)9.对表长为n的顺序表进行顺序查找,在查找概率相等的情况下,查找成功的平均查找长度为()A.(n-1)/2B.(n/2)C.(n+1)/2D.n10.对于哈希函数H(key)=key%13,被称为同义词的关键字是()A.3

4、5和41B.23和39C.15和44D.25和5111.在最好和最坏情况下的时间复杂度均为O(n*logn)且稳定的排序方法是:()A.快速排序B.堆排序C.归并排序D.基数排序12.非空循环链表head的尾结点p满足下列()条件。A.head->next==pB.head==pC.p->next==headD.p->next==nil13.如下函数中,当n趋近于无穷时,增长率最快的是()A.n2B.109n1.9C.nlogn9D.lognn14.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是()A.

5、9B.11C.15D.不确定15.从下列有关树的叙述中,选出正确的叙述()A.二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。B.叶子节点权值确定后,从这些节点构造的带权路径最短的树是唯一的。C.对一个带权图而言,其最小生成树不唯一。D.在二叉树中插入结点,该二叉树便不再是二叉树。考      生      信      息      栏______学院______系______专业______年级    姓名______学号_____装订线二、填空题(每空2分,共20分)1.对一组数据(84,47,25,1

6、5,21)排序,数据的排列次序在排序的过程中的变化为(1)8447251521(2)1547258421(3)1521258447(4)1521254784,则采用的排序是________。2.下面程序段中s=s+j运行次数为______________。(请准确计算)FORi:=1TOnDOFORj:=iTOnDOs=s+j;3.已知链栈的结点结构为(data,next),栈顶指针为top,则实现将指针p所指结点插入栈顶的语句依次为________和________。4.假设S和X分别表示进栈和出栈操作,由输入序列“ABC”得到

7、输出序列“BCA”的操作序列为SSXSXX,则由“a*b+c”得到“ab*c+”的操作序列为___________。5.在一棵度为3的树中,度为2的结点个数是1,度为0的结点个数是6,则度为3的结点个数是________。6.如图所示的有向无环图可以排出________种不同的拓扑序列。7.若一个栈的输入序列是1,2,3……,n,其输出序列为p1,p2,……pn,若p1=n,则pi为_____________。8.对长度为20的有序表进行二分查找,查找成功的情况下,最多进行__次关键字比较。9.在具有n个结点的k(k>=2)叉树的

8、k叉链表表示中,共有__个空指针域。三、解答题(每小题10分,共40分)1.对于单链表、单循环链表和双向链表,如果仅仅知道一个指向链表中某结点的指针p,能否将p所指结点的数据元素与其确实存在的直接前驱交换?请对三种链表的每一种链表作出判断,若可以,

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。