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

一、判断题 (每小题1分,共15分)
1.算法一定要有输入和输出。( )
2.算法分析的目的旨在分析算法的效率以求改进算法。( )
3.非空线性表中任意一个数据元素都有且仅有一个直接后继元素。( )
4.数据的存储结构不仅有顺序存储结构和链式存储结构,还有索引结构与散列结构。( )
5.线性链表中各个链结点之间的地址不一定要连续。( )
6.若频繁地对线性表进行插入和删除操作,该线性表采用顺序存储结构更合适。( )
7.若线性表采用顺序存储结构,每个数据元素占用4个存储单元,第12个数据元素的存储地址为144,则第1个数据元素的存储地址是101。( )
8.若长度为n的线性表采用顺序存储结构,删除表的第i个元素之前需要移动表中n-i+1个元素。( )
9.符号link(p)出现在表达式中表示p所指的那个结点的内容。( )
10.要将指针p移到它所指的结点的下一个结点是执行语句p←link(p)。( )
11.在非空线性链表中由p所指的结点后面插入一个由q所指的结点的过程是依次执行语句:link(q)←link(p);link(p)←q。( )
12.在非空双向循环链表中由q所指的结点后面插入一个由p指的结点的动作依次为:llink(p)←q,rlink(p)←rlink(q),rlink(q)←p,llink(rlink(q))←p。( )
13.若某堆栈的输入序列为1,2,3,4,则4,3,1,2不可能是堆栈的输出序列之一。( )
14.删除非空链式存储结构的堆栈(设栈顶指针为top)的一个元素的过程是依次执行:p←top,top←link(p),call RET(p)。( )
15.若队列采用链式存储结构,队头指针与指针分别为front和rear,向队列中插入一个数据信息为item的新元素的过程是依次执行:call GETNODE(p),data(P)←item,rear←p,front←p。( )
二、单项选择题 (每小题2分,共20分)
16.广义表中元素分为 ( )
A.原子元素
B.表元素
C.原子元素和表元素
D.任意元素
17.求字符串T在字符串S中首次出现的位置的操作称为 ( )
A.串的模式匹配
B.求子串
C.求串的长度
D.串的连接
18.树型结构最适合用来描述 ( )
A.有序的数据元素
B.无序的数据元素
C.数据元素之间的具有层次关系的数据
D.数据元素之间没有关系的数据
19.若二叉树中度为2的结点有15个,度为1的结点有10个_______个叶结点。 ( )
A.25
B.30
C.31
D.41
20.若深度为6的完全二叉树的第6层有3个叶结点,则该二叉树一共有______个结点。 ( )
A.15
B.16
C.17
D.18
21.若某完全二叉树的深度为h,则该完全二叉树中至少有______个结点。 ( )
A.2h
B.2h-1
C.2h-1-1
D.2h-1+1
22.在非空二叉树的中序遍历序列中,二叉树的根结点的左边应该 ( )
A.只有左子树上的所有结点
B.只有左子树上的部分结点
C.只有右子树上的所有结点
D.只有右子树上的部分结点
23.对于任意非空二叉树,要设计出其后序遍历的非递归算法而不使用堆栈结构,最适合的方法是对该二叉树采用_______存储结构。 ( )
A.三叉链表
B.二叉链表
C.顺序
D.索引
24.对于一个数据序列,按照“逐点插入方法”建立一个二叉排序树,该二叉排序树的形状取决于 ( )
A.该序列的存储结构
B.序列中的数据元素的取值范围
C.数据元素的输入次序
D.使用的计算机的软、硬件条件
25.下面关于哈夫曼树的说法,不正确的是 ( )
A.对应于一组权值构造出的哈夫曼树一般不是唯一的
B.哈夫曼树具有最小带权路径长度
C.哈夫曼树中没有度为1的结点
D.哈夫曼树中除了度为1的结点外,还有度为2的结点和叶结点
三、填空题 (每小题2分,共20分)
26.在一个图中,所有顶点的度数之和等于所有边的数目的_________倍。
27.图的深度优先搜索方法类似于二叉树的_________遍历。
28.带权连通图G=,其它V={v1,v2,v3,v4,v5},E={(v1,v2)7, 29.数据文件最重要的操作除了插入、删除、修改和查找外,还有_________。
30.将数据元素2,4,6,8,10,12,14,16,18,20依次存放于一个一维数组中,然后采用折半查找方法查找元素12,被比较过的数组元素的下标依次为_________。
31.在索引表,若一个索引项对应基本数据中一条记录,则称此索引为稠密索引;若索引表中一个索引对应基本数据中的若干记录,则称此索引为_________索引。
32.每趟排序从未排序的子序列中依次取出元素与已经排好序的序列中元素进行比较,然后将其放在已经排好序的序列的合适位置。这种排序法称为_________排序法。
33.从未排序序列中选择一个元素,该元素将当前参加排序的那些元素分成前后两个部分,前一部分中所有元素都小于等于所选元素,后一部分中所有元素都大于或等于所选元素,而此时所选元素处在排序的最终位置。这种排序法称为_________排序法。
34.谢尔排序法、快速排序法、堆积排序法和二路归并排序法四种排序法中,要求辅助空间最多的是_________。
35.对序列(49,38,65,97,76,27,13,50)采用快速排序法进行排序,以序列的第一个元素为基准元素得到的划分结果是__________________。
四、问题求解题 (每小题10分,共20分)
36.已知某非空二叉排序树采用顺序存储结构依次将所有结点的数据信息存放于一维数组
ABDIC*EF**C***H
请分别写出该二叉树的前序遍历序列与中序遍历序列。
37.已某个不带权的无向图采用邻接矩阵存储方法依次将顶点的数据信息存放于一维数组ABCDEFGH中,边的信息存放于邻接矩阵中,邻接矩阵为
0 1 1 0 0 0 0 0
1 0 0 0 1 0 1 1
1 0 0 1 0 1 0 0
0 0 1 0 0 1 0 0
0 1 0 0 0 0 0 1
0 0 1 1 0 0 0 0
0 1 0 0 0 0 0 0
0 1 0 0 1 0 0 0
请写出从顶点A出发对该图进行深度有限搜索后得到的顶点序列。
五、算法填空题 (本大题共2小题,共25分)
38.已知长度为n的线性表A=(a1,a2,...,an-1,an)采用顺序存储结构,请写出一算法,将线性表转换为A"=(an,an-1,...,a2,a1),要求转换过程中尽可能少的辅助空间。
procedure REVERSE(A,n)
for i←1 to _____ do
temp←A[i]
___________________
___________________ // 这三条语句是交换A中两个元素的位置 //
end
end
39.设非空二叉树采用二叉链表储存结构,根结点的指针为T,下面是利用前序遍历的非递归方法删除该二叉树该二叉树中数据域内容为item的那个叶结点的算法。这里,假设算法中用到的堆栈采用顺序存储结构,并且空间足够大。
请在算法的空白处填入适当内容,使之能够正常工作。
procedure DELLEAF(T)
top←0 // 堆栈初始置空 //
p←T
repeat
while (p≠nil) do
if __________________________________ then
// 找到了满足条件的结点(叶结点)//
[if _______________ then // 若满足条件的结点是根结点 //
T←nil
else // 若满足条件的结点不是根结点 //
if ______________ then
lchild(q)←nil // 被删除结点的双亲结点的左指针域置空 //
else
rchild(q)←nil // 被删除结点的双亲结点的右指针域置空 //
call RET(p) // 释放被删除结点的存储空间 //
return]
top←top+1
STACK[top]←p // p 所指结点的地址进栈 //
q←p // 记录p 所指结点的双亲结点的地址 //
p←lchild(p) // p 向下指向其左孩子结点 //
end
p←STACK[top] // 栈顶元素(结点的地址)退栈送p //
top←top-1
q←p // 记录p 所指结点的双亲结点的地址 //
p←rchild(p)
until ________________________ // p 向下指向其右孩子结点 //
end
相关文章
· 02年北京市文凭考试"解剖生理学"试题  (07-03 10:15)
· 文凭考试与国立大学考试的区别  (07-01 10:25)
· 文凭考试学校的性质和办学体制  (07-01 10:23)
· 文凭考试“数据库原理”考试题型  (06-17 17:44)
· (北京)2003年10月文凭考试时间表  (06-06 10:08)

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

   论坛热贴




   热力推荐

  • 2004网易"名校行"活动
  • 中大华工考研不必先选导师
  • 金领之路--追踪十五位归国MBA
  • 小鱼轻声请问:谁是汉语系的?
  • 动什么也别动感情


  • ·彻底根治牛皮癣,鱼鳞病!
    ·不孕不育新希望
    ·中医药治愈肿瘤创奇迹
    ·海军中医攻克牛皮癣
    ·权威专家专业治疗肿瘤
    ·脑萎缩痴呆不容忽视
    ·告别脑萎缩、帕金森病
    多彩校园
    · 谁革了传统教材的命?
    · 当校园民谣即将离我们远去
    · 聘周星驰 招贤?炒作?
    · 研究生戴着手铐答辩
    · 12/07 高校BBS热贴榜

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

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

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

    手机短信 推荐新闻
    闪烁短信 动感短信
    自写短信 精品图片
    时事新闻 铃声传情
    都市情缘 暗恋表白
    天气预报 移动股市
    邮件通知 短信富翁

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