下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
数据结构导论年月真题
0214220154
1、【单选题】设某个算法的计算量是问题规模n的函数:T(n)=anc+blog2n+cn+d,则该算法
的时问复度可表示成
O(nc)
O(log2n)
A:
0(n)
B:
O(1)
C:
答D:案:A
2、【单选题】将长度为n的单链表链接在长度为m的单链表之后的算法时间复杂度为
0(n)
O(m)
A:
O(n+m)
B:
O(n×m)
C:
答D:案:B
3、【单选题】为解决计算机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲
区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓
冲区的逻辑结构应该是
栈
队列
A:
树
B:
图
C:
答D:案:B
4、【单选题】对于n(n≥0)个元素构成的线性表L,适合采用链式存储结构的操作是
需要频繁修改L中元素的值
需要频繁地对L进行随机查找
A:
需要频繁地对L进行插入和删除操作
B:
要求L存储密度高
C:
答D:案:C
5、【单选题】判断一个带有头结点的链队列为空队列Q的条件是
A:
B:
C:
答D:案:B
6、【单选题】在一个单链表中,已知指针q指向指针p所指结点的前驱结点,则删除*p结
点的操作语句是
A:
B:
C:
答D:案:D
7、【单选题】把特殊矩阵A[10][10]的下三角矩阵压缩存储到一个一维数组M中,刚A中元
素a[4][3]在M中所对应的下标位置是
8
12
A:
13
B:
55
C:
答D:案:C
8、【单选题】若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反,则该二
叉树一定是
结点均无左孩子的二叉树
结点均无右孩子的二叉树
A:
存在度为2的结点的二叉树
B:
高度为n的二叉树
C:
答D:案:D
9、【单选题】对关键字序列{0,2,4,8,16,32,64,128}进行二分查找,则第一个被查
找到的关键字是
0
8
A:
16
B:
128
C:
D:
答案:B
10、【单选题】已知一个图如题10图所示,若从顶点a出发进行广度优先遍历,则可能
得到的广度优先搜索的结果序列为
acefbd
acbdfe
A:
acbdef
B:
acdbfe
C:
答D:案:C
11、【单选题】若某二叉树按后序遍历得到的结果为c、b、a,则可以得到该结果的二叉树
有
1种
2种
A:
3种
B:
5种
C:
答D:案:D
12、【单选题】下列有关哈夫曼(Huffman)树的描述,不正确的是
哈夫曼树的树形唯一,且其WPL值最小
A:
哈夫曼树的树形不一定唯一,但其WPL值最小且相等
哈夫曼字符编码不一定唯一,但总码长最短
B:
哈夫曼树没有严格要求区别左右子树权重次序
C:
答D:案:A
13、【单选题】能够使用二分查找算法进行查找的条件是必须以
顺序方式存储,且元素按关键字有序
链式方式存储,且元素按关键字有序
A:
顺序方式存储,且元素按关键字无序
B:
链式方式存储,且元素按关键字无序
C:
答D:案:A
解析:适用二分查找法的序列要满足两个条件:一是该序列内的元素是有序排列的(这很
显然);二是该序列能够让程序直接访问它范围中间的元素,也就是需要能够随机存取。
14、【单选题】下列排序方法中不稳定的是
直接插入排序
堆排序
A:
冒泡排序
B:
二路归并排序
C:
答D:案:B
解析:冒泡排序、插入排序、归并排序属于稳定排序,选择排序、快速排序、堆排序属于
不稳定排序。
15、【单选题】对于n个元素的关键字序列{k1,k2….,kn),当且仅当满足关系k1≤k2i
且ki≤k2i+1(2i≤n,2i+1≤n)称其为最小堆,反之则为最大堆。以下序列中不符合最小堆或
最大堆定义的是
{4,10,15,72,39,23,18}
{58,27,36,12,8,23,9}
A:
{4,10,18,72,39,23,l5}
B:
{58,36,27,12,8,23,9}
C:
答D:案:C
16、【问答题】字符a.b、c、d依次通过一个栈,按出栈的先后次序组成字符串,至多可
以组成多少个不同的字符串?并分别写出它们。
答案:共14个。分别是:dcba,cbad,cbda,cdba,bacd,badc,bcad,bcda,bdca,
abcd,abdc,acbd,acbd,adcb
17、【问答题】已知某棵二叉树的先序遍历和中序遍历的结果序列分别为ABCDEFGHI和
BCAEDGHFI。试构造出该二叉树,并给出该二叉树的后序遍历结果序列。
答案:
18、【问答题】带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从
初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径,现有
一种解决该问题的方法:①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;
②选择离u最近且尚未在最短路径中的一个顶点v,加入到最短路径中,修改当前顶点u=v;
③重复步骤②,直到u是目标顶点时为止。现问上述方法能否求得最短路径?若该方法可行,
试证明之;否则,举例说明。
答案:
19、【问答题】将关键字序列{7,8,30,11,18,9,14}散列存储到一个散列表中,设该
散列表的存储空间是一个下标从0开始、大小(HashSize)为l0的一维数组,散列函数为
H(key)=(key×3)MODHashSize,处理冲突采用线性探测法。现要求:(1)画出所构造的散列
表;(2)计算出等概率情况下查找成功的平均查找长度。
答案:
20、【问答题】若采用冒泡排序方法对关键字序列{265,301,751,129,937,863,742,
694,076,438}进行升序排序,写出其每趟排序结束后的关键字序列。
答案:
21、【问答题】写出一个将线性表的顺序表存储方式(数组a、表长为n)改成单链表存储方
式(其头结点由头指针head指向)的算法。设函数头为:Node*CreateLinkedList(DataType
a[],intn)
答案:
22、【问答题】统计出一棵二叉树中结点数据域的值不小于m的所有结点个数。设二叉树
的存储结构为:
答案:
23、【填空题】数据结构研究的主要内容包括数据的逻辑结构、______、以及对数据及其关
系的操作运算。
答案:(数据的)存储结构
24、【填空题】根据数据元素之间的关系,通常有四类基本的逻辑结构:集合、线性结构、
树形结构、______.
答案:图结构
25、【填空题】在表长为n的顺序表中插入一个数据元素,平均需要移动约______个数据元
素。
答案:n/2
26、【填空题】设有二维数组A[8][10],按行序优先存储,且每个元素占用2个存储单
元,若第一个元素的存储起始位置为b,则存储位置为b+20处的元素为______。
答案:a[1][0]
27、【填空题】栈的特点是先进后出或后进先出,队列的特点是______。
答案:先进先出
28、【填空题】若一棵二叉树中度为l和度为2的结点个数均是3,则该二叉树叶子结点的
个数是_____.
答案:4
29、【填空题】高度(深度)为h的完全二叉树最少的结点个数是______。
答案:2h-1
30、【填空题】根据图的定义,图中顶点的最少数目是______。
答案:1
31、【填空题】高度为3、含有5个结点(编号l~5)的二叉树,其顺序存储结构为
,则编号为4的结点的双亲结
点的编号为______。
答案:3
32、【填空题】对如题25图所示的含有3棵树的森林进行先序遍历,得到的结果序列是
______。
答案:EBACDFHG
33、【填空题】按
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 十五五智能开关面板市场:存量房改造带来的万亿级增量空间
- 关于新能源乘用车领域用户增长分析的报告
- 十五五智能庭院伞ESG报告:全生命周期碳足迹与回收机制
- 区块链赋能新能源汽车充电基础设施:结算效率与信任机制
- 2026年新能源车充电设施行业报告及市场前景展望
- 2026年电子信息行业政策导向报告及市场前景预测
- 2026年电子商务行业创新型企业成长分析报告
- 2026年网络安全产业链安全防护与技术创新报告
- 2026年房地产行业报告:高质量发展与市场风险预警
- 2026年动漫产业报告:行业现状与市场潜力分析
- 医用高压氧舱安全管理与应用规范
- JG/T 299-2010供冷供热用蓄能设备技术条件
- 《石油化工自动化控制系统》课件
- 消防通道标线施工合同
- 绵阳市三台县乡镇地图矢量可编辑课件行政区划边界高清(四川省)
- 宅基地转让协议书
- 2024入团积极分子入团考试题库(含答案)
- 英语-简单句五种基本句型课件
- 气体绝缘金属封闭开关设备不停电扩建技术导则
- 人工智能导论智慧树知到期末考试答案2024年
- 巧克力囊肿的护理查房
评论
0/150
提交评论