数据结构
数据结构试题
数据结构
一、单项选择题
1. 数据的最小单位是_A___。
A.数据元素 B.记录 C.数据对象 D.数据项
2. 对于一个具有n个结点和e条边的无向图,若采用邻接表表
示,所有边链表中边结点的总数为__C__。
A. e/2 B.e C.2e D.n+e
3. 数组a[1..6,1..5] (无0行0列)以列序为主序顺序存储,a[1][1]的地址为1000,每个元素占2个存储单元,则a[3][4]的地址是___A_。
A.1026 B.1040 C.1042 D.1046
4. 某线性表常发生的操作为删除第一个数据元素和在最后一个元素后添加新元素,采用__D__的存储结构,能使其存储效率和时间效率最高。
A.单链表 B.仅用头指针的循环链表
C.双向循环链表 D.仅用尾指针的循环链表
5. 在一个单链表中,已知q所指向的结点是p指向的结点的直接前驱结点,若在q所指向的结点和p指向的结点间插入s所指向的结点, 则执行 C ___ 。
A. s->next=p->next; p->next=s;
B. p->next=s->next; s->next=p;
C. q->next=s; s->next=p;
D. p->next=s; s->next=q;
6. 若循环队列使用C数组A[m]存放其数据元素,已知头指针front指向队首元素,尾指针rear指向尾元素后的空单元,则当前队列中的元素个数为___A_。
A.(rear-front+m)%m B. rear-front+1
C. rear-front D. rear-front-1
7. 栈和队列的共同点是___C_。
A.先进先出 B. 后进先出
C.只允许在端点处插入和删除元素 D. 运算受限的线性表
数据结构试题
8. 一棵深度为5的完全二叉树,叶结点数最大值和最小值分别为_B___。
A. 10,5 B. 16,8 C. 8,4 D. 32,16
9. 折半查找有序表(5,15,25,35,40,65,70,75,80,85,88,90),若查找元素75,需依次与表中元素__A__进行比较,。
A.65,80,70,75 B.65,85,75 C.65,80,75 D.70,85,75
10. 算法suanfa的时间复杂度为_A___。
int suanfa(int n)
{ int i=1;
while(pow(2,i)<=n) /* pow(2,i)表示2i*/
i=i+1;
return i;
}
内容需要下载文档才能查看2) D.O(n)
二、简答题
1. 简叙深度优先遍历算法与广度优先遍历算法的区别,当采用广度优先遍历时,如何记录已被访问的顶点?
答:
区别:可以看到两种方法最大的区别在于前者从顶点的第一个邻接点一直访问下去再访问顶点的第二个邻接点;后者从顶点开始访问该顶点的所有邻接点再依次向下,一层一层的访问。
可以用队列来储存那些没有访问或者刚访问过的结点,对每个结点设置一个访问标志位。
2.设文件R共有1500条记录,磁盘的读、写单位为250条记录,内存可提供750条记录的空间,试简要说明对文件R的排序过程。 答:
第一步,每次将三个记录块即750个记录有外存读到内存,进行内部排序,整个文件被分成2个有序子序列,然后分别把它们写到外存上去。
第二步,两两归并有序子文件,进行了一趟,最终成为了一个有序文件。
数据结构试题
三、画图题
1. 已知一链式队列中,队列元素依次为A,B,C,D, 完成删除操作3次,试画出每次删除之后的链式队列存储结构。
初始队列:front
内容需要下载文档才能查看 内容需要下载文档才能查看 内容需要下载文档才能查看 内容需要下载文档才能查看rear
内容需要下载文档才能查看
第一次:front rear
第二次:front rear
第三次:front rear
2. 已知一棵二叉树的先序遍历结果为ABCDEFG,中序遍历结果为CBEDAFG,试画出这棵二叉树。
四、计算题
1.设对18个记录的表作折半查找, (1)画出折半查找过程的判定(
(2)ASL(成功)=(1*1+2*2+4*3+8*4+3*5)/18=32/9
ASL(不成功)=(13*5+6*6)/13=101/13
2. 试用权值集合 { 12,4,5,6,1,2}构造赫夫曼(Huffman)树,(1)列出构造过程,(2)计算该哈夫曼树的带权路径长度。 初始集合:{ 12,4,5,6,1,2}
第一次:选取1、2 集合:{ 12,4,5,6,3}
第二次:选取3、4 集合:{ 12,7,5,6}
第三次:选取5、6 集合:{ 12,7,11}
第四次:选取7、11 集合:{ 12,18}
数据结构试题
第五次:选取12、18 集合:{30} 构造完成
WPL=2*4+3*3+1*1=18
3.试用关键字序列(39,25,24,50,12,14,20,19,37,6),构造哈希(Hash)表,设哈希函数为:H(key)=key % 13,其中key为关键字,%为求余运算符;用开放定址法处理冲突, 用线性探测再散列法查找空位,用数组A[15]表示哈希表。 (1)画出该哈希表的存储结构图;(2)假定每个元素的查找概率相等, 计算查找成功及查找失败
内容需要下载文档才能查看ASL(不成功)=(5+4+3+2+1+1+5+4+3+2)/10=3.0
五、算法设计题
1. 设a[ ] 的初值为(119,527,9,768,22,549)
a[0]为临时工作单元。分析如下程序段:
for (i=0,d=1;i<3; i++,d*=10)
{
for ( j=0; j<10; j++) count[j]=0;
for( j=0; j<6; j++) count[ a[j] / d % 10]++;
for ( j=1; j<10; j++) count[j]=count[j-1]+count[j]; for( j=5; j>=0; j- -) b[- -count[a[j] / d % 10]]=a[j]; for( j=0; j<6; j++) a[j]=b[j];
}
(1)当i=1时,给出循环体执行完后a[ ] 的值。
(2)说明该程序段的功能。
(1) a[ ]={22,527,768,119,9,549}
(2) 基数排序
2.试写出算法,就地逆转以herd 为头指针的无表头结点的单链表。
Status ListOppose_L(LinkList &L)
{
LinkList p,q;
p=L;
p=p->next;
数据结构试题
} L->next=NULL; while(p){ q=p; p=p->next; q->next=L->next; L->next=q; } return OK;
下载文档
热门试卷
- 2016年四川省内江市中考化学试卷
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
- 山东省滨州市三校2017届第一学期阶段测试初三英语试题
- 四川省成都七中2017届高三一诊模拟考试文科综合试卷
- 2017届普通高等学校招生全国统一考试模拟试题(附答案)
- 重庆市永川中学高2017级上期12月月考语文试题
- 江西宜春三中2017届高三第一学期第二次月考文科综合试题
- 内蒙古赤峰二中2017届高三上学期第三次月考英语试题
- 2017年六年级(上)数学期末考试卷
- 2017人教版小学英语三年级上期末笔试题
- 江苏省常州西藏民族中学2016-2017学年九年级思想品德第一学期第二次阶段测试试卷
- 重庆市九龙坡区七校2016-2017学年上期八年级素质测查(二)语文学科试题卷
- 江苏省无锡市钱桥中学2016年12月八年级语文阶段性测试卷
- 江苏省无锡市钱桥中学2016-2017学年七年级英语12月阶段检测试卷
- 山东省邹城市第八中学2016-2017学年八年级12月物理第4章试题(无答案)
- 【人教版】河北省2015-2016学年度九年级上期末语文试题卷(附答案)
- 四川省简阳市阳安中学2016年12月高二月考英语试卷
- 四川省成都龙泉中学高三上学期2016年12月月考试题文科综合能力测试
- 安徽省滁州中学2016—2017学年度第一学期12月月考高三英语试卷
- 山东省武城县第二中学2016.12高一年级上学期第二次月考历史试题(必修一第四、五单元)
- 福建省四地六校联考2016-2017学年上学期第三次月考高三化学试卷
- 甘肃省武威第二十三中学2016—2017学年度八年级第一学期12月月考生物试卷
网友关注
- 会计从业资格考试《财经法规》学习笔记精装整理
- 2014考研经典案例答疑解说 跨考教育为您撑起考研一片天
- 中兴通讯移动网络管理产品发展策略探析-new
- 教科版小学科学六年级上册教案[精品]
- 2011考研英语必考200个句型
- 第四讲 无形资产评估准则
- 人教版四年级英语下(词汇,句型和练习)
- 广东外语外贸大学全国硕士研究生入学考试试题册
- 公共课程题库
- 天津经济概况
- 《学生心理辅导》高等院校小学教育专业教材
- 考研英语历年真题词汇手册
- 中国石油大学(华东)2011年学术型硕士研究生专业目录doc
- 人教版小学数学六年级上电子版教科书
- 小学语文必做阅读训练
- 【精品】VoIP发展新方向IP85
- LTE系统及关键技术
- 辽宁省出台新的资产评估收费标准
- 2010_年全国硕士研究生入学统一考试数学三试题及解析
- 小学教育专业本科课程设置研究
- 北邮通信概论课件-信令系统
- 4G资费过高可搭配免费wifi使用
- MIMO技术在3G演进中的应用进展1
- 2015年东北农业大学mba招生简章-中公管理人
- MPA联考《公共管理基础》完成教案
- 凯撒股份:2013年年度报告
- 【精品】附录3汉字区位码表7
- 苏教版二年级数学上册教案(2013新版)
- 27松鼠的尾巴
- 四年级语文上册教案
网友关注视频
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 12
- 苏教版二年级下册数学《认识东、南、西、北》
- 外研版英语七年级下册module3 unit2第二课时
- 沪教版牛津小学英语(深圳用) 五年级下册 Unit 10
- 19 爱护鸟类_第一课时(二等奖)(桂美版二年级下册)_T3763925
- 【部编】人教版语文七年级下册《老山界》优质课教学视频+PPT课件+教案,安徽省
- 冀教版小学数学二年级下册第二单元《租船问题》
- 二年级下册数学第一课
- 外研版英语三起6年级下册(14版)Module3 Unit2
- 【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案,辽宁省
- 精品·同步课程 历史 八年级 上册 第15集 近代科学技术与思想文化
- 冀教版英语五年级下册第二课课程解读
- 冀教版小学数学二年级下册第二周第2课时《我们的测量》宝丰街小学庞志荣.mp4
- 第4章 幂函数、指数函数和对数函数(下)_六 指数方程和对数方程_4.7 简单的指数方程_第一课时(沪教版高一下册)_T1566237
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 2
- 【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,辽宁省
- 外研版英语三起6年级下册(14版)Module3 Unit1
- 北师大版八年级物理下册 第六章 常见的光学仪器(二)探究凸透镜成像的规律
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 8
- 3.2 数学二年级下册第二单元 表内除法(一)整理和复习 李菲菲
- 【部编】人教版语文七年级下册《老山界》优质课教学视频+PPT课件+教案,安徽省
- 【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案,安徽省
- 三年级英语单词记忆下册(沪教版)第一二单元复习
- 冀教版小学英语四年级下册Lesson2授课视频
- 【部编】人教版语文七年级下册《过松源晨炊漆公店(其五)》优质课教学视频+PPT课件+教案,江苏省
- 19 爱护鸟类_第一课时(二等奖)(桂美版二年级下册)_T502436
- 《空中课堂》二年级下册 数学第一单元第1课时
- 苏科版数学七年级下册7.2《探索平行线的性质》
- 冀教版小学数学二年级下册第二单元《余数和除数的关系》
- 外研版英语七年级下册module1unit3名词性物主代词讲解
精品推荐
- 2016-2017学年高一语文人教版必修一+模块学业水平检测试题(含答案)
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
分类导航
- 互联网
- 电脑基础知识
- 计算机软件及应用
- 计算机硬件及网络
- 计算机应用/办公自动化
- .NET
- 数据结构与算法
- Java
- SEO
- C/C++资料
- linux/Unix相关
- 手机开发
- UML理论/建模
- 并行计算/云计算
- 嵌入式开发
- windows相关
- 软件工程
- 管理信息系统
- 开发文档
- 图形图像
- 网络与通信
- 网络信息安全
- 电子支付
- Labview
- matlab
- 网络资源
- Python
- Delphi/Perl
- 评测
- Flash/Flex
- CSS/Script
- 计算机原理
- PHP资料
- 数据挖掘与模式识别
- Web服务
- 数据库
- Visual Basic
- 电子商务
- 服务器
- 搜索引擎优化
- 存储
- 架构
- 行业软件
- 人工智能
- 计算机辅助设计
- 多媒体
- 软件测试
- 计算机硬件与维护
- 网站策划/UE
- 网页设计/UI
- 网吧管理