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

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

□ 自考名师全程视频授课，图像、声音、文字同步传输，享受身临其境的教学效果；
□ 权威专家在线答疑，提交到答疑板的问题在24小时内即可得到满意答复；
□ 课件自报名之日起可反复观看不限时间、次数，直到当期考试结束后一周关闭；
□ 付费学员赠送1G超大容量电子信箱；及时、全面、权威的自考资讯全天24小时滚动更新；
□ 一次性付费满300元，即可享受九折优惠；累计实际交费金额500元或支付80元会员费，可成为银卡会员，购课享受八折优惠；累计实际交费金额1000元或支付200元会员费，可成为金卡会员，购课享受七折优惠（以上须在同一学员代码下）；
英语/高等数学预备班：英语从英文字母发音、国际音标、基本语法、常用词汇、阅读、写作等角度开展教学；数学针对有仅有高中入学水平的数学基础的同学开设。通过知识点精讲、经典例题详解、在线模拟测验，有针对性而快速的提高考生数学水平。立即报名！
基础学习班：依据全新考试教材和大纲，由辅导老师对教材及考试中所涉及的知识进行全面、系统讲解，使考生从整体上把握该学科的体系，准确把握考试的重点、难点、考点所在，为顺利通过考试做好知识上、技巧上的准备。立即报名！
冲刺串讲班：结合历年试题特点及命题趋势，规划考试重点内容，讲解答题思路，传授胜战技巧，为考生指出题眼，提供押题参考。配合高质量全真模拟试题，让学员体验实战，准确地把握考试方向、将已掌握的应试知识融会贯通，并做到举一反三。立即报名！
真题测试班：通过真题的在线模拟测试，由自考365网校的专家名师指明未来考试中可能出现的“陷阱”、“雷区”、“误区”，帮助学员减少答题失误，提高学员驾驭和应用所学知识的能力，迅速提高应试技巧和强化所学知识，顺利通过考试！立即报名！
自考实验班：针对高难科目开设，签协议，不及格返还学费。全国限量招生，报名咨询 010-82335555 立即报名！

全国2006年10月高等教育自学考试
数据结构导论试题
课程代码：02142
一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.数据的基本单位是（　　　）
A.数据项 B.数据类型
C.数据元素 D.数据变量
2.下列程序的时间复杂度为（　　　）
i=0；s=0；
while（s针的单循环链表
C.双链表 D.仅有尾指针的单循环链表
4.从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（　　　）
A.n-i B.n-i+1
C.n-i-1 D.i
5.顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（　　　）
A.s.elem［top］=e； B.s.elem［top+1］=e；
s.top=s.top+1； s.top=s.top+1；
C.s.top=s.top+1； D.s.top=s.top+1；

s.elem［top+1］=e； s.elem［top］=e；
6.循环队列sq中，用数组elem［0··25］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（　　　）
A.8 B.16
C.17 D.18
7.设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为（　　　）
A.13 B.35
C.17 D.36
8.含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（　　　）
A.3 B.4
C.5 D.6
9.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为（　　　）
A.24 B.25
C.98 D.99
10.可以惟一地转化成一棵一般树的二叉树的特点是（　　　）
A.根结点无左孩子 B.根结点无右孩子
C.根结点有两个孩子 D.根结点没有孩子
11.有n个结点的有向完全图的弧数是（　　　）
A.n2 B.2n
C.n(n-1) D.2n(n+1)
12.设图的邻接链表如题12图所示，则该图的边的数目是（　　　）

题12图
A.4 B.5
C.10 D.20
13.已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素时，检索成功需比较的次数是（　　　）
A.1 B.2
C.3 D.4
14.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（　　　）
A.选择排序 B.快速排序
C.冒泡排序 D.插入排序
15.排序算法中，不稳定的排序是（　　　）
A.直接插入排序 B.冒泡排序
C.堆排序 D.归并排序
二、填空题(本大题共13小题，每小题2分，共26分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16.在数据结构中，数据的逻辑结构分为集合、________、树形结构和图状结构等四类。
17.通常从正确性、易读性、________和高效率等4个方面评价算法（包括程序）的质量。
18.顺序表的存储密度为________，而链表的存储密度为________。
19.对于栈只能在________插入和删除元素。
20.在循环队列中，存储空间为0～n-1,设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么队满标志为front=(rear+1)%n，队空标志为________。
21.三个结点可构成________种不同形态的二叉树。
22.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中________个用于链接孩子结点。
23.有向图G用邻接矩阵A［1··n，1··n］存储，其第i列的所有元素之和等于顶点Vi的________。
24.对二叉排序树进行________遍历，可得到排好序的递增结点序列。
25.采用折半查找方法进行查找的数据序列应为________且________。
26.索引文件只能是________，因为索引文件的组织方式是为随机存取而设计的。
27.在插入和选择排序中，若初始数据基本正序，则选用________；若初始数据基本反序，则选用________。
28.快速排序最好情况下的时间复杂度为________，最坏情况下的时间复杂度为________。

三、应用题(本大题共5小题，每小题6分，共30分)
29.已知一棵二叉树的中根序列和后根序列分别为B、D、C、E、A、F、H、G和D、E、C、B、H、G、F、A，试画出这棵二叉树，并给出其先根序列。
30.已知如题30图所示，用普里姆（prim）算法从顶点A开始求最小生成树。在算法执行之初，顶点的集合U={A，B}，边的集合TE={（A，B）}。试按照最小生成树的生成过程，分步给出加入顶点和边以后的集合U和TE的值。

31.设散列函数H（key）=key mod 11，给定键值序列为13、41、15、44、6、68、17、26、39、46，试画出相应的开散列表，并计算在等概率情况下查找成功时的平均查找长度。
32.从一个空的二叉排序树开始，依次插入关键字25、13、15、34、7、20、37，试分别画出每次插入关键字后的二叉排序树。
33.画出对应于序列{10，20，7，75，41，67，3，9，30，45}的初始堆（堆顶元素取最小值）。
四、算法设计题(本大题共2小题，每小题7分，共14分)
34.在下面冒泡排序算法中（1）～（4）处填入适当内容，以使该算法在发现有序时能及时停止。
bubble（R）
Rectype R［n］；
{int i，j，exchang；
Rectype temp；
i=1；
do
{exchang=False；
for（j=n；j>= （1）________；j--）
if（R［j］
{ EdgeNode *p，*q；
p=G→adjlist［i］.firstedge；
if（p→adjvex==j）{G→adjlist［i］.firstedge=p→next；free（p）；}
else{while（p→next→adjvex!=j&&p→next）
（1）________；
if（p→next!=NULL）{q=p→next；（2）________；free（q）；}
}
p=G→adjlist［j］.firstedge；
if（p→adjvex==i）{G→adlist［j］.firstedge=p→next；free（q）；}
else{while（p→next→adjvex!=i&&p→next）
（3）________；
if（p→next!=NULL）{q=p→next；（4）________；free（q）；}
}
}
════════════════════════════════════════════════════════════════════
自考365（--）领先的专注于自学考试的网络媒体与服务平台 - 本套试题共分6页，当前页是第6页-