数据结构2007试题(A)-答案
更新时间:2023-05-17 08:15:01 阅读量: 实用文档 文档下载
数据结构2007试题(A)-答案
武汉大学计算机学院
2006年-2007学年第二学期“数据结构”考试试题(A)
姓名
学号(序号)_ 班号
要求:所有的题目的解答均写在答题纸上(每张答题纸上要写清楚姓名、班号和学号),需写清楚题目的序号。每张答题纸都要写上姓名和序号。
一、单项选择题(每小题2分,共20分)
1. 在存储数据时,通常不仅要存储各数据元素的值,而且还要存储 。 A. 数据的处理方法
B. 数据元素的类型
C. 数据元素之间的关系 D. 数据的存储方法 2. 下述函数中渐进时间复杂度最小是 。 A.T1(n)=nlog2n+5000n
2
B.T2(n)=n2-8000n
C.T3(n)= nlogn-6000n D.T4(n)=1000nlog2n+7000log2n
3. 设线性表有n高。
A.输出第i(1≤i≤n)个元素值
B.交换第1个元素与第2个元素的值 C.顺序输出这n个元素的值
D.输出与给定值x相等的元素在线性表中的序号
4. 设n个元素进栈序列是p1,p2,p3,…,pn,其输出序列是1,2,3,…,n,若p3=3,则p1的值 。
A.可能是2 B.一定是2
C.不可能是1
D.一定是1
5. 以下各种存储结构中,最适合用作链队的链表是 。
A.带队首指针和队尾指针的循环单链表 B.带队首指针和队尾指针的非循环单链表 C.只带队首指针的非循环单链表 D.只带队首指针的循环单链表 6. 对于链串s(长度为n,每个结点存储一个字符),查找元素值为ch的算法的时间复杂度为 。
A.O(1)
B.O(n)
C.O(n2) D.以上都不对
7. 设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素a[3][5]的存储地址为1000,则a[0][0]的存储地址是 。
A.872 B.860
C.868
D.864
8. 一个具有1025个结点的二叉树的高h为 。 A.11 B.10 C.11~1025
D.12~1024
数据结构2007试题(A)-答案
9. 一棵二叉树的后序遍历序列为DABEC,中序遍历序列为DEBAC,则先序遍历序列为 。
A.ACBED C.DEABC
B.DECAB D.CEDBA B.1 2 4 3 5 6 7 10. 对图1所示的无向图,从顶点1开始进行深度优先遍历;。 A.1 2 4 3 5 7 6 C.1 2 4 5 6 3 7
图1 一个无向图
二、填空题(每题2分,共10分)
1. 的不同。
2. 在有n个顶点的有向图中,每个顶点的度最大可达 。
3. 对有18个元素的有序表R[1..18]进行二分查找,则查找R[3]的比较序列的下标为 。
4. 对含有n元素的关键字序列进行直接选择排序时,所需进行的关键字之间的比较次数为 。
5. 已知关键字序列为{2,7,4,3,1,9,10,5,6,8},采用堆排序法对该序列作升序排序时,构造的初始堆(大根堆)是 。(不用画出堆,只需写出初始堆的序列)
三、问答题(共40分)
1. 一棵完全二叉树上有1001个结点,其中叶结点的个数是多少?(需写出推导过程,8分)
2. 对n个顶点的无向图和有向图,采用邻接矩阵和邻接表表示时,如何求任意一个顶点的度是多少?(8分)
3. 将整数序列{4,5,7,2,1,3,6}中的数依次插入到一棵空的平衡二叉树中,试构造相应的平衡二叉树。(要求画出每个元素插入过程,若需调整,还需给出调整后的结果,并指出是什么类型的调整,12分)
4. 当实现插入直接排序过程中,假设R[0..i-1]为有序区,R[i..n-1]为无序区,现要将R[i]插入到有序区中,可以用二分查找来确定R[i]在有序区中的可能插入位置,这样做能否改善直接插入排序算法的时间复杂度?为什么?(8分)
5. 简述外排序的两个阶段。(4分)
四、算法设计题(共30分)
1. 设计一个在带头结点的单链表L中删除一个最小值结点的算法。
2.假设二叉树采用二叉链存储结构存储,设计一个算法,由二叉树b复制成另一棵二叉树t。(15分)
数据结构2007试题(A)-答案
参 考 答 案
一、单项选择题(每小题2分,共20分)
1. C 6. B
2. D 7. B
3. A 8. C
4. A 9. A
5. B 10. A
二、填空题(每题2分,共10分)
1. 存储方法或存储结构。 2. 2(n-1)。 3. 9、4、2、3 4. n(n-1)/2。
5. 10,8,9,6,7,2,4,5,3,1。(序列不全对不给分)
三、问答题(共40分)
1. 答:二叉树中度为1的结点个数只能是1或0。设n1=1,n=n0+n1+n2=n0+n2+1=1001,由性质1可知n0=n2+1,由两式可求n0=500.5,不成立;设n1=0,n=n0+n1+n2=n0+n2=1001,由性质1可知n0=n2+1,由两式可求n0=501。本题答案为:501。
评分标准:只给出结果给3分,推导过程占5分。
2. 答:对于邻接矩阵表示的无向图,顶点i的度等于第i行中元素等于1的个;对于邻接矩阵表示的有向图,顶点i的出度等于第i行中元素等于1的个数;入度等于第i列中元素等于1的个数;度数等于它们之和。
对于邻接矩阵表示的无向图,顶点i的出度等于g->adjlist[i]为头结点的单链表中结点的个数;入度需要遍历各顶点的边表,若g->adjlist[k]为头结点的单链表中存在顶点编号为i的结点,则顶点i的入度增1;度数等于它们之和。
评分标准:有向图、无向图两种存储方式各占4分。
3. 建立平衡二叉树过程如图2所示(图中加阴影的结点表示要调整的结点)。
数据结构2007试题(A)-答案
图2 构造平衡二叉树过程
评分标准:除第一步外,每插入一个元素占1分,每次调整占2分。
4. 答:不能。因为在这里,二分查找只减少了关键字间的比较次数,而记录的移动次数不变,时间的复杂度仍为O(n)。
评分标准:答对“不能”占3分,说明理由占5分。
5. 答:生成初始归并段(或顺串),采用多路平衡归并方法进行归并。
2
四、算法设计题(共30分)
1. 设计一个在带头结点的单链表L中删除一个最小值结点的算法。
解:用p从头至尾扫描单链表,pre指向*p结点的前驱,用minp保存值最小的结点指针,minpre指向*minp结点的前驱。一面扫描,一面比较,将最小值的结点放到*minp中。算法如下:
void delminnode(LinkList *&L) {
LinkList *pre=L,*p=pre->next,*minp=p,*minpre=pre; while (p!=NULL) {
if (p->data<minp->data) { minp=p;
//查找最小值结点*minp及其前驱结点*minpre
数据结构2007试题(A)-答案
}
}
} pre=p; p=p->next;
minpre=pre;
minpre->next=minp->next; //删除*minp结点 free(minp);
评分标准:根据算法的正确性评分,不考虑算法的时间复杂度。
2.假设二叉树采用二叉链存储结构存储,设计一个算法,由二叉树b复制成另一棵二叉树t。(15分)
解:递归算法如下:
void copy(BTNode *b,BTNode *&t) { }
BTNode *l,*r;
if (b==NULL) t=NULL; else { }
t=(BTNode *)malloc(sizeof(BTNode)); copy(b->lchild,l); copy(b->rchild,r); t->lchild=l; t->rchild=r;
评分标准:根据算法的正确性评分,不考虑算法的时间复杂度。
正在阅读:
数据结构2007试题(A)-答案05-17
2018-2023年中国床上用品行业市场深度调研分析与投资机会研究报告08-28
2018-2019年开心版英语小学六年级下册Unit 1 A Parade Day 优质课教案07-25
网络协议分析课设09-28
2019年考研英语二考前模拟题11-12
《学前心理学》复习要点07-06
不干胶标签印刷的质量控制续03-19
2014年一轮复习:9.4电磁感应规律的综合应用(二)05-22
争创省级和谐示范社区汇报材料(修改稿)03-09
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 数据结构
- 试题
- 答案
- 2007
- 电脑维修服务合同示范文本
- 电子商务概论习题集
- 文学院教育实习报告
- 2011年重庆巴蜀中学初二(上)第一次月考-英语试题
- 2014年度民警述职述廉报告
- 大垭口石灰石矿区地质灾害危险性评估报告
- hypermesh几何清理常见问题及解答
- 第一部分 茶文化知识
- 药物化学CJ-05 中枢兴奋药及利尿药
- 个人中英文简历模板3
- 制造企业车间主任车间管理和现场改善
- 组装收音机课程设计的总结【免费】
- 餐饮服务与管理期中考试试题 陈奋霞
- 长沙四大名校2021年生物会考模拟试题及答案
- 3、《鸟的天堂》达标练习题(精品文档)
- 3.1理解和宽容第一课时
- 茶叶氟研究现状及降氟措施研究进展_罗学平
- 能源资源的开发学案
- HELLO甜品店策划书
- 论矿山地质环保新规