06年十月自考数据结构导论试题的答案

全国2008年10月自考数据结构导论试题答案~

深度的递归算法
int depth(BiTreeNode * T){
if(T==NULL) return 0; // 如果结点为空，高度为0
else {
int h1= depth(T->lchild); // 获得左子树的高度
int h2= depth(T->rchild); // 获得右子树的高度
return max(h1,h2)+1;
}
}

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

一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．下列描述中正确的是( )
A.数据元素是数据的最小单位
B.数据结构是具有结构的数据对象
C.数据结构是指相互之间存在一种或多种特定关系的数据元素的集合
D.算法和程序原则上没有区别，在讨论数据结构时两者是通用的
2．归并排序的时间复杂度是( )
A．O（n2）
B.O（nlog2n）
C.O（n）
D.O（log2n）
3．二分查找的时间复杂度是( )
A．O（n2）
B.O（nlog2n）
C.O（n）
D.O（log2n）
4．顺序存储的表中有90000个元素，已按关键字值升序排列，假设对每个元素进行查找的概率相同，且每个元素的关键字值皆不相同，用顺序查找法查找时，需平均比较的次数为( )
A．25000
B.30000
C.45000
D.90000
5．散列文件是一种( )
A．顺序文件
B.索引文件
C.链接文件
D.计算寻址文件
6．两个矩阵A：m×n，B：n×p相乘，其时间复杂度为( )
A．O(n)
B.O(mnp)
C.O(n2)
D.O（mp）
7.常用于函数调用的数据结构是( )
A.栈
B.队列
C.链表
D.数组
8．二维数组A［n］［m］以列优先顺序存储，数组A中每个元素占用1个字节，A［1］［1］为首元素，其地址为0，则元素A［i］［j］的地址为( )
A.（i-1）×m+(j-1)
B.(j-1)×n+(i-1)
C.(j-1)×n+i
D.j×n+i
9.图的广度优先搜索使用的数据结构是( )
A．队列
B.树
C.栈
D.集合
10．序列（21,19,37,5,2）经冒泡排序法由小到大排序，在第一次执行交换后所得结果为( )
A．(19，21，37，5，2)
B.(21，19，5，37，2)
C.(21，19，37，2，5)
D.(2，21，19，37，5)
11．数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为( )
A．索引存储方法
B.顺序存储方法
C.链式存储方法
D.散列存储方法
12．在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的( )
A．直接前趋
B.直接后继
C.开始结点
D.终端结点
13．在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为( )
A．O（1）
B.O（log2n）
C.O（n）
D.O（n2）
14．在链队列中执行入队操作，( )
A．需判别队是否空
B.需判别队是否满
C.限制在链表头p进行
D.限制在链表尾p进行
15．一整数序列26，59，77，31，51，11，19，42，以二路归并排序从小到大排序，第一阶段的归并结果为( )
A.31，51，11，42，26，77，59，19
B.26，59，31，77，11，51，19，42
C.11，19，26，31，42，59，51，77
D.26，11，19，31，51，59，77，42
二、填空题(本大题共13小题，每小题2分，共26分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16．下列程序段的时间复杂度为_______。
i=0；s=0；
while（s<n）
{i++；
s=s+i；
}
17．数据的存储结构被分为顺序存储结构、_______、散列存储结构和索引存储结构4种。
18．从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动_______个元素。
19．在单链表中，插入一个新结点需修改_______个指针。
20．在队列结构中，允许插入的一端称为_______。
21．稀疏矩阵采用的压缩存储方法是_______。
22．向一个栈顶指针为top的链栈中插入一个新结点*p时，应执行p->next=top和_______操作。
23．有m个叶结点的哈夫曼树所具有的结点数为_______。
24．在一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右地给所有结点编号。设根结点编号为1。若编号为i的结点有右孩子，那么其右孩子的编号为_______。
25．在一棵树中，_______结点没有前驱结点。
26．一个具有n个顶点的有向完全图的弧数是_______。
27．n个顶点的无向图G用邻接矩阵A［n］［n］存储，其中第i列的所有元素之和等于顶点Vi的_______。
28．选择排序的平均时间复杂度为_______。
三、应用题(本大题共5小题，每小题6分，共30分)
29．在栈的输入端元素的输入顺序为1，2，3，4，5，6，进栈过程中可以退栈，则退栈时能否排成序列3，2，5，6，4，1和1，5，4，6，2，3，若能，写出进栈、退栈过程，若不能，简述理由。（用push（x）表示x进栈，pop(x)表示x退栈）
30．已知一棵二叉树的中根遍历序列为CBEDFAGH，后根遍历序列为CEFDBHGA，画出该二叉树。
31．给定表（15，11，8，20，14，13），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树，并判断该二叉排序树是否为平衡二叉排序树，若为非平衡二叉排序树，将它调整为平衡二叉排序树。
32．如题32图所示无向图，（1）写出其邻接矩阵；（2）写出三种以顶点A为起点的深度优




先搜索顶点序列。

题32图
33．用冒泡排序法对数据序列（49，38，65，97，76，134，27，49）进行排序，写出排序过程。并说明冒泡排序是否为稳定排序。
四、算法设计题(本大题共2小题，每小题7分，共14分)
34.编写计算二叉树中叶子结点数目的算法。
35.开散列表的类型定义如下：
typedef struct tagnode
{keytype key;
struct tagnode*next;
}*pointer,node;
typedef pointer openhash［n］;
试写出开散列表上的查找算法。

全国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）；}
}
答案————————————----___
1 C 2 C 3D 4 A 5 D 6 C 7、A 8、C 9、B 10 D
1、线性 2、顺序、链式 3、健壮性 4、等于1，小于1
5、n/2 6、栈顶、先进后出、先进先出
7、(i*n+j)*5, (j*m+i)*5 8、5种 9、log2(n)+1
10、
若一个完全二叉树有1450个结点，则度为1的结点个数为 1 ，度为2

的结点个数为 724 ，叶子结点的个数为 725 ，有 725 个结

点有左孩子，有 724 个结点有右孩子；该树的高度为 11 。(性质

3、性质4以及完全二叉树的特征)

应用题1：typedef struct node
{
elementype data;
struct node *pri,*next;
}lnode,*linklist;

应用题2：
q->next=p->next;
p->next->pri=q;
p->next=q;
q->pri=p;

34、ABCDEFGH
35、WPl= (3+6+7+9)*3+(10+11)*2=117
10:01 11:10
3:000 6:001 7:110 9:111

数据结构导论试题和答案已经发到你邮箱里去了,你会给我分数吗?我相信你,你一定会给我的.

---

依安县13873055062： 自考数据结构答案 - ？
祢星血府： 全国2003年上半年自考数据结构答案及标准评分 http://www.xpbook.com/soft/14519.shtml2006年10月自学考试＂数据结构＂试题参考答案 http://edu.qq.com/a/20061129/000168.htm 很多数据结构试题 http://www.bkzyk.com/test/search.asp?act=...

依安县13873055062： 数据结构导论中的填空题,出自＂自考2007年10月＂ - ？
祢星血府： 引用型运算 ① 加工型运算 其操作改变了原逻辑结构的“值”,如结点个数、某些结点的内容等;如:初始化、插入、删除、更新等操作. ② 引用型运算 其操作不改变原逻辑结构的“值”,只从中提取某些信息作为运算的结果.如:查找、读取等操作.

依安县13873055062： 数据结构导论试题答案解一下 - ？
祢星血府： 第六题选B,因为完全二叉树的深度h满足:2^i-1=100;可以算出i=7时为128;

依安县13873055062： 全国2006年10月高等教育自学考试 自动控制理论(二)试题 答案 课程代码:02306 - ？
祢星血府： 全国2006年10月高等教育自学考试 自动控制理论(二)试题 课程代码:02306 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内.错选、多选...

依安县13873055062： 求教数据结构导论的题目,麻烦给做一下.一个10阶对称矩阵A,采用行优先顺序压缩存储上三角元素,a00为第一个元素,其存储地址为0,每个元素占有1个... - ？
祢星血府：[答案] 对称矩阵,A85=A58 只需要存上半三角 A58=10+9+8+7+4-1=37 首地址为0所以需减1

依安县13873055062： 男龙.正月十三,女马4月初一,今年什么时候结婚最好 - ？
祢星血府： 吉祥温馨提示---您的生肖类别:那年的龙马?男龙.正月十三,女马4月初一,2011年5月份恭候您二位结婚的黄道吉日是: (避开您二位新人生肖的冲日后可任选)2011年05月03日 农历04月 01日 星期二 冲鼠(壬子) 2011年05月06日 农...

依安县13873055062： 数据结构概论 试题求解 - ？
祢星血府： 1.c 2.c. 3.c 4.c 5.a 6.a 7.b 8.b 9.b 10.b 11.a 12.b 13.b 14.b 15.b 16.a 17.c 18. d 19.c 20.d 21.b 22.c 23.b