Netease
首页 - 短信 - 游戏 - 泡泡 - 邮箱 - 同学录 - 相册 - V交友 - 同城约会
新闻 体育 财经 科技 商业 游戏 娱乐 女性 生活 房产 招聘 旅游 健康 文化 教育 出国 汽车 手机 导购 广东 上海
箐箐论坛 
民办高校 
心理驿站 
试题中心 
精彩专题 
教育首页 | 多彩校园 | 高考 | 考研 | 中考 | 自考 | 打工求职 | 时尚外语 | 职业培训 | 留学海外    
  您现在的位置∶网易首页 >> 教育首页 >> 自考站 >> 文考高职-试题汇编
99年北京文凭考试“数据结构”试题
2004年04月22日17:57:27 北京自考热线 

课程代码:21049
适用专业:计算机应用、计算机网络

一、判断题 (每小题1分,共10分)
1.一个完整算法可以没有输入,但是必须有输出。( )
2.算法与程序没有区别。( )
3.用循环链表作为存储结构的队列称为循环队列。( )
4.满二叉树一定是完全二叉树,而完全二叉树不一定是满二叉树。( )
5.除了插入和删除以外,数组的操作还有存取、修改、检索和排序。( )
6.任意图都是其自身的子图。( )
7.一个图具有生成树的必要条件是该图必须是连通图。( )
8.折半查找方法也可以用于按值大小链接的线性链表的查找。( )
9.在B树中查找与在B+树中查找的过程完全相同。( )
10.对具有n个元素的序列采用泡排序法进行排序,排序趟数为n-1。( )
二、单项选择题 (每小题2分,共10分)
1.正常情况下,删除非空的顺序存储结构的堆栈的栈顶元素,栈顶指针top的变化是( )。
A.top不变 B.top←0
C.top←top+1 D.top←top-1
2.中缀表达式(A-B*C)/D+E的后缀形式是( )。
A.A-BC*D/E+ B.ABC*-D/E+
C.ABC*-DE/+ D.ABC*-D/+E
3.对二叉树进行_______遍历可以得到结点的排序序列。( )
A.前序 B.中序
C.后序 D.按层次
4.一个具有n个顶点的连通图的生成树中有_______条边。( )
A.n-1 B.n
C.┗n/2┛  D.n+1
5.对具有八个元素的序列(49,38,65,97,76,13,27,50)按从小到大排序,_______是选择排序法第一趟的结果。( )
A.13,65,38,97,76,49,27,50
B.13,27,38,49,50,65,76,97
C.97,76,65,50,49.38,27,13
D.13,38,65,97,76,49,27,50
三、填空题 (每空2分,共20分)
1.一般情况下,将一个递归算法变换成等价的非递归算法主要设置_______机制。
2.循环单链表与循环非循环单链表的主要不同是___________________________________。
3.若具有n个结点的非空二叉树采用二叉链表存储结构,该链表一共有____个指针域,其中_____个指针域存放非空指针,有_____个指针域存放空指针(nil)。
4.具有n个顶点的无向图的边数最多为_______________________,具有n个顶点的有向图的边数最多为_____________________。
5.在散列文件(Hash文件)中,处理冲突的方法通常有__________、___________、___________三种。
四、简答题 (共20分)
1.一个完整的算法应该具有哪几个基本性质?分别简要说明每一性质的含意。(5分)
2.有人说一个m×n阶的矩阵是一个广义表结构,你认为如何?请拘役说明你的结论。(5分)
3.插入排序法的时间花费主要取决于元素之间的比较次数。若具有n个元素的序列初始时为递增序列,采用插入排序法排序一共要进行多少次元素的比较?若序列初始为递减序列,一共要进行多少次元素的比较?(10分)
五、问题求解题 (每小题10分,共20分)
1.给定一带权连通图如下,先写出其邻接矩阵,然后根据Prim算法求出其所有可能的最小生成树。
9
6
7 8
V1--------V2--------V3--------V4--------V5
4
4
2.若一棵树有n1个度为1的结点,n2个度为2的结点,…,nm个度为m的结点,求该树中叶结点的个数。(要求写出推导过程)
六、算法题 (共20分)
1.已知具有n个记录的排序连续顺序文件,其关键字序列满足key[1]≤key[2]≤...≤key[n],下面是在该文件中查找关键字为k的记录的算法,若查找成功,算法返回被查到记录在文件中的位置,若查找失败,返回信息0。请在算法的空缺处填入适当内容,使之能够正常工作。(8分)
function BINSRCH(key,n,k)
low←1
high←n
while ┏━━━━━━━━━┓do
┗━━━━━━━━━┛
mid←┗(low+high)/2 ┛
if key [mid]=k then
return (mid)
if key [mid] ┏━━━━━━━━━┓
┗━━━━━━━━━┛
else
┏━━━━━━━━━┓
┗━━━━━━━━━┛
end
return (0)
end
2.已知二叉树采用二叉链表存储结构,链接点的构造为lchild | data | rchild 根结点的指针为T,下面给出的是交换该二叉树中所有结点的左、右子树相对位置的算法,算法中设置了一个空间足够大的书许存储结构的队列Q,队头指针与队尾指针分别用front和rear表示,队列中保存的是链接点的地址。请在算法的空缺处填入适当内容,使之能够正常工作。(12分)
procedure EXCHANGE(T)
if T=nil the
return
Q[1]←T
rear←1
front←0
while┏━━━━━━━━━┓do
┗━━━━━━━━━┛
┏━━━━━━━━━━━━┓
┗━━━━━━━━━━━━┛
p←Q[front] // 从队列中退出一个元素 //
┏━━━━━━━━━━━┓
┃ ┃
┃ ┃
┃ ┃ // 交换左右子树位置 //
┃ ┃
┃ ┃
┃ ┃
┗━━━━━━━━━━━┛
if lchild(p)≠nil then
[┏━━━━━━━━━┓
┗━━━━━━━━━┛
Q[rear]←lchild(p) // 进队 // ]
if rchild(p)≠nil then
[┏━━━━━━━━━┓
┗━━━━━━━━━┛
Q[rear]←lchild(p) // 进队 // ]
end
end


  上一篇: 04年1月汇编语言试题   下一篇: 03年数据库原理及应用题

相关文章

  · 98年北京文凭考试“数据结构”试题  (04-22 17:55)
· 2003年北京文考“汇编语言”试题  (04-21 16:59)
· 2002年北京文考“汇编语言”试题  (04-21 16:54)
· 2001年北京文考“汇编语言”试题  (04-21 16:52)
· 2000年北京文考“汇编语言”试题  (04-21 16:50)


手机短信,推荐新闻给好友 我要发表评论】  【关闭窗口

校园连线
 
海报
60%谈恋爱为找伴侣

4 60%谈恋爱为找伴侣
卧谈
我把青春献给了你,我的阿姨

4 我把青春献给了你,我的阿姨
交锋
黑中介瞄上学生

4 黑中介瞄上学生


逼死人的择校费 北京中招择校1分值3万 女大学生口述:如果可以重来 我要珍惜自己


  恋情测试
4 面对爱情,你是否执迷不悔?
4 你属于哪种类型的美眉?
4 你的魅力到底有多少?
  休闲搞笑
4 如此广告
4 男人的为什么
4 智力测验
  求职故事
4 女学生求职受骚扰
4 代人事经理招聘的烦恼
4 用人单位出尔反尔
  影视娱乐
4 《爱是妥协》精彩对白
4 We Are The World
4 Beatles经典回顾

  论坛热贴
  我也评两句
网易通行证: 密码:

您的发表的评论将在5分钟内被审核,请耐心等待

·打工不如当老板!

·今年开什么店好赚钱!

·美式幼教,火爆中国!

·开家咖啡店赚个几百万

·开家面馆挤破门的好生意

·学生狂爱,钱狂赚!

·赚有车人的钱,真容易!

·开特色店,年赚100万!

·少奋斗20年的赚钱机会

·05年哪些项目赚钱快!

·废旧塑料,轮胎变黄金!

·老公投资,我赚钱!

·开个粥铺,稳赚不赔!

·1.2万办厂:年利百万

·怎样成为中国富豪!

易趣竞拍
· 珠宝首饰/手表/眼镜
· 礼品/烟具/优惠券
· 运动/户外/球星纪念品
· 玩具/卡通产品/游戏机
多彩校园
· 谁革了传统教材的命?
· 当校园民谣即将离我们远去
· 聘周星驰 招贤?炒作?
· 研究生戴着手铐答辩
· 12/07 高校BBS热贴榜

精彩专题
· 网易教育周刊TOP10(第十一期)
· 世界政治与经济课程免费视频
· 考研政治经济学课程免费视频
· 梦在重点 路在脚下
· 中国MBA备考网名师辅导专栏

时尚外语
· 8分考生谈雅思
· 雅思阅读的一点个人经验
· 进跨国公司需参加哪些英语考试
· 3个月听力口语纯正化
· 美文赏析:The Perfect Dog

试题中心
高考历年试题 高考模拟试题
考研历年试题 考研模拟试题
高考作文 MBA考试 GRE CET
TOFEL IELTS 财会类 司法类
IT类   公务员    高教自考
文考高职    中考试题

频道精选
 
· 毕业剧场:校园绝恋
· 恐怖!亲历灵异事件
· 新玄幻名作:魔旅

  
·小贝夫妇贴身热吻
·赵薇见老同学自曝糗事
·谢霆锋自嘲无性生活

 
- 男友劈腿,赵薇遭遇"第三者"
- 老公的初恋女友竟然跑到我家来了!!
- 老公竟然当着我的面召妓

  
· 实录:中国吧女和三个外国男人的恩怨
· 迷失在阿姆斯特丹的红灯区(组图)
· 宿舍里7个室友的7件怪事
手机短信 推荐新闻
闪烁短信 动感短信
自写短信 精品图片
时事新闻 铃声传情
都市情缘 暗恋表白
天气预报 移动股市
邮件通知 短信富翁

About NetEase - 公司简介 - 联系方法 - 招聘信息 - 客户服务 - 相关法律 - 网络营销
网易公司版权所有
© 1997-2005