自考数据结构2008-10-1.doc

全天24小时服务咨询电话 [phone]　免费热线 4008135555

□ 自考名师全程视频授课，图像、声音、文字同步传输，享受身临其境的教学效果；
□ 权威专家在线答疑，提交到答疑板的问题在24小时内即可得到满意答复；
□ 课件自报名之日起可反复观看，不限时间、地点、次数，直到当期考试结束后一周关闭；
□ 付费学员赠送1G超大容量电子信箱；及时、全面、权威的自考资讯全天24小时滚动更新；
□ 一次性付费满300元，即可享受九折优惠；累计实际交费金额500元或支付80元会员费，可
成为银卡会员，购课享受八折优惠；累计实际交费金额1000元或支付200元会员费，可成为金
卡会员，购课享受七折优惠（以上须在同一学员代码下）；
英语/高等数学预备班：英语从英文字母发音、国际音标、基本语法、常用词汇、阅读、写作等角度开展教学；数学针对有高中入学水平的数学基础的同学开设。通过知识点精讲、经典例题详解、在线模拟测验，有针对性而快速的提高考生数学水平。立即报名！
基础学习班：依据全新考试教材和大纲，由辅导老师对教材及考试中所涉及的知识进行全面、系统讲解，使考生从整体上把握该学科的体系，准确把握考试的重点、难点、考点所在，为顺利通过考试做好知识上、技巧上的准备。立即报名！
真题串讲班：教育部考试中心已经启动了自考的国家题库建设，熟练掌握自考历年真题成为顺利通过考试的保障之一。自考365网校与权威自考辅导专家合作，推出真题串讲班网上辅导课程。通过对课程的整体情况分析及近3次考试的真题讲解，全面梳理考试中经常出现的知识点，并对重点难点问题配合典型例题扩展讲解。串讲班课程在考前一个月左右开通。立即报名！
习题班：自考365网校与北大燕园合作推出，每门课程均涵盖该课程全部考点、难点，在线测试系统按照考试难度要求自动组卷、全程在线测试、提交后自动判定成绩。我们相信经过反复练习定能使您迅速提升应试能力，使您考试梦想成真！立即报名！
自考实验班：针对高难科目开设，签协议，不及格返还学费。全国限量招生，报名咨询 010-82335555 立即报名！

全国2008年10月高等教育自学考试
数据结构导论试题
课程代码：02142

一、单项选择题（本大题共15小题，每小题2分，共30分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.从逻辑上可以把数据结构分为（　　　）
A.动态结构、静态结构 B.顺序结构、链式结构
C.线性结构、非线性结构 D.初等结构、构造型结构
2.关于算法的描述，不正确的是（　　　）
A.算法最终必须由计算机程序实现
B.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
C.健壮的算法不会因非法的输入数据而出现莫名其妙的状态
D.算法的优劣与算法描述语言无关
3.在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指向该结点的（　　　）
A.直接前趋 B.直接后继
C.开始结点 D.终端结点
4.将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（　　　）
A.n B.2n-1
C.2n D.n2
5.栈和队列共同具有的特点是（　　　）
A.都是先进后出 B.都是先进先出
C.只允许在端点进行操作运算 D.既能先进先出，也能先进后出
6.若用一个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3。则从队列中删除一个元素，再添加两个元素后，rear和front的值分别为（　　　）
A.1和5 B.2和4
C.4和2 D.5和1
7.数组A［0..5］［0..5］的每个元素占5个字节，将其以列为主序存储在起始地址为1000的内存单元中，则元素A［5］［5］的地址是（　　　）
A.1175 B.1180
C.1205 D.1210
8.含有n个结点的二叉树采用二叉链表存储时，空指针域的个数为（　　　）
A.n-1 B.n
C.n+1 D.n+2
9.在一棵深度为H的完全二叉树中，所含结点的个数不少于（　　　）
A.2H-1-1 B.2H-1
C.2H-1 D.2H
10.一个具有n个顶点的无向连通图，它所包含的连通分量数为（　　　）
A.0 B.1
C.n D.不确定
11.下列说法中不正确的是（　　　）
A.无向图的极大连通子图称为连通分量
B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
C.连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
D.有向图的遍历不可采用广度优先搜索算法
12.对一棵二叉排序树采用中根遍历进行输出的数据一定是（　　　）
A.递增或递减序列 B.递减序列
C.无序序列 D.递增序列
13.一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，查找成功时的比较次数为（　　　）
A.1 B.2
C.4 D.8
14.一组记录的关键字为{45，80，55，40，42，85}，则利用堆排序的方法建立的初始堆为（　　　）
A.80，45，55，40，42，85 B.85，80，55，40，42，45
C.85，80，55，45，42，40 D.85，55，80，42，45，40
15.关于VSAM文件存取操作的说法，正确的是（　　　）
A.不能顺序存取，只能按关键字随机存取 B.不能顺序存取，不能按关键字随机存取
C.只能顺序存取，不能按关键字随机存取 D.既能顺序存取，也能按关键字随机存取

二、填空题（本大题共13小题，每小题2分，共26分）
请在每小题的空格中填上正确答案。错填、不填均无分。
16.在任何问题中，数据元素都不是孤立的，它们之间总存在某种关系，通常称这种关系为
________。
17.存储结点之间通常有四种基本存储方式，即顺序存储方式、索引存储方式、________和散列存储方式。
18.在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动________个元素。
19.对一棵深度为10的满二叉树按层编号，则编号为51的结点，它的双亲结点编号为________。
20.用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342的出栈顺序，相应的S和X操作串为________。
21.具有n个叶子结点的哈夫曼树，其结点总数为________。
22.一棵具有n个结点的树，所有非终端结点的度均为k，则该树中叶子结点个数为________。
23.在无向图G的邻接矩阵A中，若A［i］［j］等于0，则A［j］［i］等于________。
24.两个串是相等的，当且仅当两个串的长度相等且________的字符都相同。
25.某二叉树的后根遍历序列为abd，中根遍历序列为adb，则它的先根遍历序列为________。
26.先在所有的记录中选出键值最小的记录，将它与第一个记录交换；然后在其余的记录中再选出最小的记录与第二个记录交换，依此类推，直至所有记录排序完成。这种排序方法称为________。
27.对含有n个结点e条边的无向连通图，利用prim算法生成最小生成树的时间复杂度为________。
28.对n个元素进行冒泡排序时，最少的比较次数为________。

三、应用题（本大题共5小题，每小题6分，共30分）
29.设有编码为A，B，C，D的4列火车，依次进入一个栈式结构的站台，试写出这4列火车开出站台的所有可能的顺序。
30.画出题30图所示的二叉树的二叉链表存储结构。

题30图
31.对于题31图，试给出：
（1）邻接矩阵；
（2）邻接表。

题31图
32.给定表（39，14，22，8，65，28，88，29，67，13，10），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。
33.用插入排序算法对数据序列（47，33，61，82，72，11，25，57）进行排序，写出整个插入排序的每一趟过程。

四、算法设计题（本大题共2小题，每小题7分，共14分）
34.设两个数据元素均为整型数据的线性表A=（a1，a2，…，an）和B=（b1，b2，…，bm）。若n=m且ai=bi（i=1，2,…，n）则认为A=B；若ai=bi（i=1，2,…，j）且aj+1<bj+1，（j<n≤m）,则认为A<B；在其它情况下均认为A>B。试编写一个比较A和B的算法，当A<B时，输出-1；当A=B时，输出0；当A>B时，输出1。要求线性表的存储结构使用链接存储。
35.设二叉树的结点类型定义如下：
typedef struct node{
datatype data;
struct node*lchild,*rchild;
}Bitree;
Bitree*t;
试编写一个计算二叉树深度的递归算法（int Depth（Bitree*t））。

════════════════════════════════════════════════════════════════════
自考365（--）领先的专注于自学考试的网络媒体与服务平台 - 本套试题共分4页，当前页是第4页-