数据结构2007试题(A)-答案
更新时间:2023-08-11 08:24: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)-答案08-11
2014春外研版8年级下册课时作业 Module 3 Journey to space Unit 110-16
2016届河北省石家庄市高三复习教学质量检测一文科数学试卷(带解析)03-14
英美国家常用人名04-23
2014年江苏省学业水平测试化学考试说明(最新) - 图文05-20
机械手维护保养说明03-18
各国公共邮箱后缀07-22
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 数据结构
- 试题
- 答案
- 2007
- 3、《鸟的天堂》达标练习题(精品文档)
- 班级管理中如何处理好师生关系
- 餐饮服务与管理期中考试试题 陈奋霞
- 个人中英文简历模板3
- 3.1理解和宽容第一课时
- 制造企业车间主任车间管理和现场改善
- 汽车空调系统电路
- 07601;中文规格书,Datasheet资料
- Office的高级使用
- 组装收音机课程设计的总结【免费】
- 21 古老帝国的悲剧
- (keil设置)第一个keilMDK工程
- 教师资格证:普通话学习技巧之朗读训练技巧
- word2003和word2007所有的常用快捷键大全
- 鸡蛋果的功效百香果的养颜功效
- 14心理剧本征集
- 应用ASP.NET开发Web程序中的安全策略
- 扶溪镇中心幼儿园大班教师个人工作计划A
- 沪科版14.1 电阻和滑动变阻器(第一课时 电阻)
- 个人月工作总结报告模板范文