安徽大学2014数据结构期末考试试卷(A卷)
更新时间:2023-09-27 07:53:01 阅读量: 综合文库 文档下载
- 安徽大学数据结构期末试卷推荐度:
- 相关推荐
安徽大学2014-2015学年第一学期《数据结构》期末考试试卷(A卷)
(含参考答案)
一、 单项选择题(本大题共15小题,第小题2分,共30分)在每小题列出的四个选项中只有一
个符合题目要求,请将其代码填在题后的括号内。错选或未选均无分。
1. 算法必须具备输入、输出和 [ C ]
A. 计算方法 B. 排序方法 C.解决问题的有限运算步骤 D. 程序设计方法
2. 有n个节点的顺序表中,算法的时间复杂度是O(1)的操作是 [ A ]
A. 访问第i个节点(1≤i≤n)
B. 在第i个节点后插入一个新节点(1≤i≤n) C. 删除第i个节点(1≤i≤n) D. 将n个节点从小到大排序
3.单链表的存储密度 [ C ]
A.大于1 B. 等于1 C.小于1 D. 不能确定
4. 循环队列SQ的存储空间是数组d[m],队头、队尾指针分别是front和rear,则执行出队后其头指针front值是 [ D ]
A.front=front+1 B. front=(front+1)%(m-1) C. front=(front-1)%m D. front=(front+1)%m
5. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是
[ B ]
A. O(1) B. O(n) C. O(n2) D. O(nlogn)
6 设二维数组A[0..m-1][0..n-1]按行优先顺序存储,则元素A[i][j]的地址为
[ B ]
A. LOC(A[0][0])+(i*m+j) B.LOC(A[0][0])+(i*n+j) C.
LOC(A[0][0])+[(i-1)*n+j-1] D. LOC(A[0][0])+[(i-1)*m+j-1]
7.设将整数1,2,3,4,5依次进栈,最后都出栈,出栈可以在任何时刻(只要栈不空)进行,则出栈序列不可能是 [ B ]
A.23415 B. 54132 C.23145 D. 15432
1
8. 一个非空广义表的表头 [ D ]
A.一定是子表 B. 一定是原子
C.不能是子表 D. 可以是原子,也可以是子表
9.具有n个节点的完全二叉树的深度为 [ A ]
A.?log2(n+1)? -1 B. log2n+1 C. log2n D. ?log2n?
10. 若要惟一地确定一棵二叉树,只需知道该二叉树的 [ D ]
A.前序序列 B. 中序序列 C.前序和后序序列 D. 中序和后序序列
11.在一个无向图中,所有顶点的度数之和等于图的边数的 倍 [ C ]
A.1/2 B. 1 C. 2 D. 4
12. 拓扑排序运算只能用于 [ C ]
A.带权有向图 B. 连通无向图 C.有向无环图 D. 无向图
13.在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是
[ D ]
A.希尔排序 B. 冒泡排序 C.插入排序 D. 选择排序
14.下列排序算法中时间复杂度不受数据初始状态影响,恒为O(n2)的是
[ C ]
A.堆排序 B. 冒泡排序 C.直接选择排序 D. 快速排序
15.二分查找要求节点 [ A ]
A.有序、顺序存储 B. 有序、链接存储 C.无序、顺序存储 D. 无序、链接存储
二、 填空题(本大题共10小题,每小题2分,共20分)不写解答过程,将正确的答案写在每小
题的空格内。错填或不填均无分。
2
16.数据的逻辑结构分为两大类,它们是线性结构和 非线性结构 。
17.在单链表中(假设结点指针域名称为next),删除指针P所指结点的后继结点的语句是 p->next=p->next->next 。
18.已知循环队列用数组data[n]存储元素值,用front,rear分别作为头尾指针,则当前元素个数为 (rear-front+n)%n 。
19. 若n为主串长,m 为子串长,则串的朴素匹配算法最坏的情况下需要比较字符的总次数为_______(n-m+1)×m_ _。
20. 广义表((a),((b),j,(((d)))))的表尾是____(((b),j,(((d)))))___ _____。
21. 已知二叉树有61个叶子节点,且仅有一个孩子的节点数为45,则总节点数为____166 __。 22. 解决计算机与打印机之间速度不匹配问题,须要设置一个数据缓冲区,应是一个 队列 结构。 23. n 个顶点e条边的图采用邻接表存储,深度优先遍历算法的时间复杂度为_________O(n+e)___________。
24. 对于n个关键字的集合进行冒泡排序,在最坏情况下所需要的时间为_____O(n2)________。 25.在一个长度为n的顺序表中的第i个元素(1≤i≤n)之前插入一个元素时,需向后 移 n-i+1 个元素。
三、 解答题(本大题共4小题,共25分)
26. 对于下面的稀疏矩阵,画出其三元组法存储表示(假设下标从0开始)。(5分)
0 0 14 0 0 0
0 0 0 0 -6 0 7 0 0 0 0 24 0 0 0 18 0 0 0 15 0 0 0 0
答案:
3
行号 列号 值 0 1 2 3 4 5 27. 已知一棵二叉树的中序序列二叉树。(5分)
中序序列:D I G J L K B A E C H F 后序序列:I L K J G D B E H F C A
0 1 2 2 3 4 2 4 0 5 3 1 14 -6 7 24 18 15 和后序序列分别如下,请画出该
答案:
A B D G I J K L E H C F 29. 已知一个图的邻接表如下所示。(8分)
(1) 画出该图的图形;(4分)
(2) 根据邻接表分别画出从顶点a出发进行深度优先和广度优先遍历所生成的生成树。(4
分)
答案:
a b c d e f ? 1 2 5 2 5 ? ? 3 4 ? ? 5 ? 4
C
四、 算法阅读题(本大题共3小题,每小题5分,共15分)
30.设线性表的n个结点定义为(a0,a1,…,an-1),在顺序表上实现的插入和删除算法如下,请在空白处填入适当内容。(顺序表的最大可容纳项数为MaxSize)
Template
Last++;
For(int j=last;j>i;j--) data[j]= (2) ; (3) ; Return 1; } }
Template
for (int j= (4) ;j<=last;j++) data[j]= (5) ; return 1; }
return 0; } 答案:
(1) MaxSize-1 (2) data[j-1] (3) Data[i]=x
(4) i (5) data[j+1]
31.阅读下面的算法,请回答下列问题:
(1) 试说明算法的功能。
(2) 当执行该程序时,输入12345678-1,输出什么结果?
#define StackSize 200 typedef int DataType; typedef struct{
DataType data[StackSize];
5
正在阅读:
九成宫醴泉铭 - 图文03-17
计算机网络作弊版(谢希仁)复习题09-01
动漫人物生日大全05-22
除数是整数的小数除法1说课稿01-13
公关策划大赛策划书10-21
猴山观猴看图写话作文300字07-04
描写秋天的古诗08-12
2019年秋部编版三年级上册语文第六单元测试卷及答案-推荐01-08
电缆绝缘电阻测试记录表05-07
- 《江苏省环境水质(地表水)自动监测预警系统运行管理办法(试行)》
- 安乐死合法化辩论赛立论稿(浙大新生赛)
- 公共科目模拟试卷公务员考试资料
- 我国固定资产投资FAI对GDP的影响
- 大学生创新创业训练计划项目申请书大创项目申报表
- 完美版—单片机控制步进电机
- 2013资阳中考化学试题
- 18.两位数减一位数退位(397道)
- 工程量计算规则
- 二年级操行评语(下)
- 第3章 流程控制语句
- 浅基桥墩加固技术
- 课题研究的主要方法
- 5100软件说明书 - 图文
- 车间技术员年终总结
- 关于印发《中铁建工集团开展项目管理实验室活动方案》的通知
- 经典诵读结题报告
- 地下水动力学习题答案
- 2018年全国各地高考数学模拟试题平面解析几何试题汇编(含答案解
- 街道办事处主任2018年度述职述廉报告
- 安徽大学
- 数据结构
- 期末
- 试卷
- 考试
- 2014
- 2014机电年度工作总结
- 2013年高考历史 真题试题汇编 第四单元 第16课 抗日战争 新人教版必修1
- 初中函数知识点总结
- 唯识学书目
- CO-PC
- 关于进行2008-2009学年第一学期小学学生学籍审核的通知
- 2016年秋学期南开大学《文学人类学(尔雅)》满分作业
- 材力讲义2 - 图文
- 《政治经济学》资本主义部分习题及答案(7,8,9)
- 中西方古代传统教育理念对高校道德教育的启示- 副本
- 天龙八部读书笔记
- 基于plc的恒压供水系统 - 图文
- 主流文化与亚文化
- 保险原理案例及答案
- 关于印发昆明市创业投资引导基金管理暂行办法的通知
- 四辩总结大学生就业压力大弊大于利
- 聚乙烯醇用途
- 电大西方经济学试题及答案(最新已整理)
- DDR的VTT电源应用及其优化
- 国家开发银行青岛分行外聘律师投标方案