没有合适的资源?快使用搜索试试~ 我知道了~
计算机数据结构今年考研真题及答案(供参考).docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 201 浏览量
2023-03-22
20:00:10
上传
评论
收藏 932KB DOCX 举报
温馨提示
试读
23页
。。。
资源推荐
资源详情
资源评论
2009
1.为解决心算机与打印机之间速度不般配的
问题,
往常设置一个打印数
据缓
冲区,主机将要输出的数据挨次写入该缓冲区, 而打印机则挨次从该缓
冲区中取
出数据。该缓冲区的逻辑结构应当是
A.栈 B.行列 C.树
D.图
2.设栈 S 和行列 Q 的初始状态均为空,元素 abcdefg 挨次进入栈 S
。若每个
元素出栈后立刻进入行列 Q,且 7 个元素出队的次序是 bdcfeag ,则栈
S 的容量
起码是 A. 1 B.2 C.3 D.4
3.给定二叉树图所示。设 N 代表二叉树的根, L 代表根结点的左子树
, R 代
表根结点的右子树。若遍历后的结点序列为 3,1,7,5,6,2,4,则
其遍历方
式是 A. LRN B.NRL C.RLN D.RNL
4.以下二叉排序树中,知足均衡二叉树定
义的是
5.已知一棵完好二叉树的第 6 层(设根为第 1 层)有 8 个叶结点,
则完好二
叉树的结点个数最多是
A.39 B.52 C.111
D.119
6.将丛林变换为对应的二叉树,若在二叉树中,
结点
父结点,则在本来的丛林中, u 和 v 可能拥有的
关系是
系 III.u 的父结点与 v 的父结点是兄弟关系
u 是结点 v
I.父子关系 II. 兄
弟关
的父结点的
I.所有极点的度之和为偶数 II. 边数大于极点个数减 1 III. 起码有一
个极点的
度为 1
A.只有 I B.只有 II C.I 和 II D.I
和 III
8.以下表达中,不切合 m 阶 B 树定义要
求的是
A.根节点最多有 m 棵子树 B.所有叶结点都在同一层上 C.各结点内
重
点字均升序或降序摆列 D.叶结点之间经过指针链接
9.已知重点序列 5,8,12, 19,28,20, 15,22 是小根堆(最小堆
),插
入重点字 3,调整后获得的小根堆是
A.3,5,12, 8, 28,20,15, 22
,19
B.3,5,12, 19,20,15, 22,8
,28
C.3,8,12, 5, 20,15,22, 28
,19
D.3,12, 5, 8, 28,20,15, 22
,19
10.若数据元素序列 11, 12,13,7,8, 9, 23,4,5 是采纳以下
排序方
法之一获得的第二趟排序后的结果,则该排序算法只好是
A.起泡排
序
B.插入排序 C.选择排序 D.
二路合
并排序
①设最短路径初始时仅包含初始极点,令目前极点 u 为初始极点;②
选择离 u
近来且还没有在最短路径中的一个极点 v,加入到最短路径中,修
改目前极点 u=v;
③重复步骤②,直到 u 是目标极点时
为止。
请问上述方法可否求得最短路径?若该方法可行, 请证明之;不然,
请举例说
明。
42.(15 分)已知一个带有表头结点的单链表,结点
结构为
data
link
假定该链表只给出了头指针 list 。在不改变链表的前提下,请设计一
个尽可能
高效的算法,查找链表中倒数第 k 个地点上的结点( k 为正整数)。若查
找成功,
算法输出该结点的 data 值,并返回 1;不然,只返回 0。要求:
(1)描绘算法的基本设计思想
(2)描绘算法的详尽实现
步骤
2010
1、若元素 a,b,c,d,e,f
许连续三次进行退栈工作,则不行能获得的出栈序列是(
)
A:dcebfa B : cbdaef C : dbcaef D
挨次进栈,同意进栈、退栈操作交替进行。
但不允
: afedcb
2、某行列同意在其两头进行入队操作,但仅同意在一端进行出队
操作,
则不行能获得的次序是( )
A:bacde B :dbace C :dbcae D :
ecbad
3、以下线索二叉树中(用虚线表示线索),切合后序线索树定
义的是(
)
4、在以下所示的均衡二叉树中插入重点字 48 后获得一棵新均衡二叉树
, 在新
均衡二叉树中,重点字 37 所在结点的左、右子结点中保存的重点字分别是
( )
A:13,48 B :24,48 C :24,53 D :24
,90
5、在一棵度为 4 的树 T 中,如有 20 个度为 4 的结点, 10 个度为 3
的结点,
1 个度为 2 的结点, 10 个度为 1 的结点,则树 T 的叶节点个数是(
)
A:41 B :82 C :113 D :122
A:该树必定是一棵完好二
叉树
B:树中必定没有度为
1
的结点
C:树中两个权值最小的结点必定是兄
弟结点
D:树中任一非叶结点的权值必定不小于下一任一结点
的权值
7、若无向图 G-(V.E)中含 7 个极点,则保证图 G 在任何状况下都是
连通的,
则需要的边数最少是( )
A:6 B :15 C :16 D
:21
8、对以下图进行拓补排序,能够获得不一样的拓补序列的个数
是( )
e
d
a
c
b
A:4 B :3 C :2 D
:1
9、已知一个长度为 16 的次序表 L,其元素按重点字有序摆列,若
采纳折半
查找法查找一个不存在的元素,则比较次数最多是( )
A:4 B:5 C:6 D:7
10、采纳递归方式对次序表进行迅速排序, 以下对于递归次数的表达
中, 正
确的选项是( )
A:递归次数与初始数据的摆列序次
没关
B:每次区分后,先办理较长的分区能够减少递
归次数
C:每次区分后,先办理较短的分区能够减少递
归次数
D:递归次数与每次区分后获得的分区办理次序
没关
11、对一组数据( 2,12, 16,88,5,10)进行排序,若前三趟排
序结果
以下( )
第一趟: 2,12, 16,5,10
,88
第二趟: 2,12, 5, 10,16
,88
第三趟: 2,5,10, 12,16
,88
41. (10 分)将重点字序列( 7、8、11、18、9、14)散列储存到散列
列表中,
散列表的储存空间是一个下标从 0 开始的一个一维数组散列函数维: H(key
)=
(key×3)MODT,办理矛盾采纳线性探测再散列法,要求装填(载)因子为
0.7
问题:( 1)请画出所结构的散列表;
(2)分别计算等概率状况下, 查找成功和查找不行功的均匀查
找长度。
42. (13 分)设将 n(n,1) 个整数寄存到一维数组 R 中,试设计一个在时间
和空
间双方面尽可能有效的算法, 将 R 中保有的序列循环左移 P(0﹤ P﹤n)个
地点,
马上 R 中的数据由( X0X1 Xn-1 )变换为( XpXp+1 Xn-1X0X1 Xp-1 )要
求:( 1 )
给出算法的基本设计思想。
(2)依据设计思想,采纳 C 或 C++ 或 JAVA 语言表述算法重点之处给
出说明。
(3)说明你所设计算法的时间复杂度和空间复杂度
2011
1. 设 n 是描绘问题规模的非负整数,下边程序片段的时间复
杂度是
x = 2;
while ( x < n/2
)
x = 2*x;
A.O(log2n) B.O(n) C.O(n log2n)
D.O(n2)
2. 元素 a, b, c, d, e 挨次进入初始为空的栈中,若元素进栈后可逗留、
可出栈,
直到所有元素都出栈, 则在所有可能的出栈序列中, 以元素 d 开头的序
列
个数是 A.3 B.4 C.5 D.6
3. 已知循环行列储存在一维数组 A[0..n-1] 中,且行列非空时 front 和
rear 分别
指向队头元素和队尾元素。 若初始时行列为空, 且要求第 1 个进入行列
的元素储
存在 A[0] 处,则初始时 front 和 rear 的值分别是
A.0, 0 B.0, n-1 C.n-1, 0 D.n-1,
n-1
4. 若一棵完好二叉树有 768 个结点,则该二叉树中叶结点
的个数是
A.257 B.258 C.384
D.385
5. 若一棵二叉树的前序遍历序列和后序遍历序列分别为 1, 2, 3, 4
和 4, 3,
2, 1 ,则该二叉树的中序遍历序列不会是
A.1, 2, 3, 4 B.2, 3, 4, 1 C.3, 2, 4, 1 D.4,
3, 2, 1
6. 已知一棵有 2011 个结点的树,其叶结点个数为 116 ,该树对应的
二叉树中
无右孩子的结点个数是
A.115 B.116 C.1895
D.1896
7. 对于以下重点字序列, 不行能组成某二叉排序树中一条查找路径
的序列是
A.95, 22, 91, 24, 94, 71 B.92, 20, 91, 34, 88, 35
C.21, 89, 77, 29, 36, 38 D.12, 25, 71, 68,
33, 34
8. 以下对于图的表达中,正确的选
项是
I. 回路是简单路径
II. 储存稀少图,用毗邻矩阵比毗邻表更省
空间
III. 如有向图中存在拓扑序列,则该图不存
在回路
9. 为提升散列 (Hash) 表的查找效率,能够采纳的正确
举措是
I. 增大装填 ( 载) 因子
II. 设计矛盾 ( 碰撞 ) 少的散列
函数
III. 办理矛盾 ( 碰撞 ) 时防止产生齐集 ( 聚积
) 现象
10. 为实现迅速排序算法,待排序序列宜采纳的储存
方式是
A. 次序储存 B. 散列储存 C. 链式储存 D. 索引储存
41.(8 分) 已知有 6 个极点 ( 极点编号为 0 ~ 5) 的有向带权图 G,其
毗邻矩阵
A 为上三角矩阵,按行为主序( 行优先) 保存在以下的一维数组中。
要求: (1) 写出图 G 的毗邻矩阵
A。
(2) 画出有向带权图
G。
(3) 求图 G 的重点路径,并计算该重点路径的长度。
42.(15 分) 一个长度为 L(L ≥1) 的升序序列 S,处在第 éL/2 ù 个地点
的数称为
S 的中位数。比如,若序列 S1=(11, 13, 15, 17, 19)
两个序列的中位数是含它们所有元素的升序序列的中位数。
比如,若
6, 8, 20)
15。
,则 S1 的中位数
是
S2=(2, 4,
,则 S1 和 S2 的中位数是 11。现有两个等长升序序列 A 和 B
,试设计
一个在时间和空间双方面都尽可能高效的算法,找出两
个序列
A 和 B 的中位数
。
要求 :(1) 给出算法的基本设计思
想。
(2) 依据设计思想,采纳 C 或 C++或 JAVA 语言描绘算法,重点之处给
出说明。
(3) 说明你所设计算法的时间复杂度和空间复杂度。
2012
1、求整数 n(n≥0)阶乘的算法以下,其时间复杂度
是 ()
intfact(intn)
{if(n<=1)return
1;
returnn*fact(n-
1);
}
A.O(log2n) B.O(n)
C.(nlog2n)
D.O(n2)
A.5 B.7 C.8
D.11
3、若一颗二叉树的前序遍历序列为 a,e,b,d,c ,后续遍历
序列为
b,c,d,e,a ,
则
()
根节点的孩子节
点
A.只有 e
B. 有 e、b C.有 e、c D. 没法
确立
4、若均衡二叉树的高度为 6,且所有非叶节点的均衡因子均为 1,
则该均衡
()
二叉树的节点总数
为
A.10
B.20 C.32
D.33
5、对有 n 个节点、 e 条边且使用毗邻表储存的有向图进行广度优
先遍历,
其算法时间复杂度 ()
剩余22页未读,继续阅读
资源评论
คิดถึง643
- 粉丝: 3921
- 资源: 1万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功