自考数据结构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<n）
{ i++；
s=s+i；
}
A.O（） B.O（）
C.O（n） D.O（n2）
3.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（　　　）
A.单链表 B.仅有头指针的单循环链表
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］<R［j-1］
{temp=R［j-1］；
R［j-1］=R［j］；
R［j］=temp；
exchang= （2）________；
}
（3）________；
}
while（exchang= （4）________）；
}
35.下列函数是在无向图的邻接表中删除一条边的算法，请在（1）～（4）处填入适当内容加以完善。
Void deledge（ALGraph *G，int i，int 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页-