全国2008年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是最符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ）A. 栈 B. 队列C. 树 D. 图2.下面程序段的时间复杂度为（ ）for (i=0; i
链式存储结构的特点是借助_指示数据元素地址的指针______来表示数据元素之间的逻辑关系。数据的存储结构是其逻辑结构在计算机中的___存放形式________。
自考题库及答案可以登录查找。作为专门的在线教育平台，的备考指导栏目就专门收录有自考的历年真题和模拟练习题，还有备考的知识点指导。点击底部咨询官网。 自考怎么复习？ 1、根据自考大纲泛读教材，找好考试重点 了解了自考的考试大纲以后，需要分清知识点的主次，可以让自己较大程度的提高自己学习的效率。 2、依次熟悉题型 对自考教材的知识有了一定把握以后，就可以开始完成刷题做题。在第一次开始完成自考题型的时候，可以先翻开自考资料，将自考科目的每个题型都依次熟悉一遍。了解每个学科对应的是哪些题型，再对每个题型进行多次练习。 3、分析标准答案 在做完一套自考练习之后，可以在校对答案的时候，要学会自己分析自考的参考答案。 有些考生在完成问题后，很少分析答案是如何得到的，这样的学习效果不好。 分析自考的标准答案可以增强对知识点的记忆，避免盲目陷入问题的海洋。 4、做历年真题，了解分值 每个考生都尽量完成一套历年的试题，了解分数的分布，这有利于我们合理分配好自考学习的时间。自考/成考有疑问、不知道如何总结自考/成考考点内容、不清楚自考/成考报名当地政策，点击底部咨询官网，免费领取复习资料：
一 单项选择题(本大题共 小题 每小题 分 共 分 在每小题的四个备选答案中 选出一个正确答案 并将正确答案的序号填在题干的括号内)
下面程序段的时间复杂度是( )
for(i= ;i
for(j=1;j
A[i][j]=0;
A.O(n) B.O(m+n+1) C.O(m+n) D.O(m*n)
2.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是( )
A.p=p->next; B.p->next=p->next->next;
C.p->next=p; D.p=p->next->next;
3.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=
head,则( )
A.p指向头结点 B.p指向尾结点
C.*p的直接后继是头结点 D.*P的直接后继是尾结点
4.判定“带头结点的链队列为空”的条件是( )
A.Q.front==NULL B.Q.rear==NULL
C.Q.front==Q.rear D.Q.front!=Q.rear
5.设有两个串T和P，求P在T中首次出现的位置的串运算称作( )
A.联接 B.求子串 C.字符定位 D.子串定位
6.广义表A=(a,(b),(),(c,d,e))的长度为( )
A.4 B.5 C.6 D.7
7.一棵含18个结点的二叉树的高度至少为( )
A.3 B.4 C.5 D.6
8.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( )
A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA
9.无向图中一个顶点的度是指图中( )
A.通过该顶点的简单路径数 B.与该顶点相邻接的顶点数
C.通过该顶点的回路数 D.与该顶点连通的顶点数
10.已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为( )
A.a c e f b d
B.a c b d f e
C.a c b d e f
D.a c d b f e
11.在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是( )
A.快速排序 B.堆排序 C.归并排序 D.基数排序
12.已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。.WingwIT.CoM对这些子序列进行一趟两两归并的结果是( )
A.{25,36,48,72,23,40,79,82,16,35}
B.{25,36,48,72,16,23,40,79,82,35}
C.{25,36,48,72,16,23,35,40,79,82}
D.{16,23,25,35,36,40,48,72,79,82}
13.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( )
A.21 B.23 C.41 D.62
14.索引非顺序文件的特点是( )
A.主文件无序，索引表有序 B.主文件有序，索引表无序
C.主文件有序，索引表有序 D.主文件无序，索引表无序
15.倒排文件的主要优点是( )
A.便于进行插入和删除运算 B.便于进行文件的恢复
C.便于进行多关键字查询 D.节省存储空间
二、填空题 (本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分)
16.抽象数据类型的特点是将____________和____________封装在一起，从而现实信息隐藏。
17.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需____________一个位置。
18.在队列中，允许进行插入操作的一端称为____________，允许进行删除操作的一端称为____________。
19.如图两个栈共享一个向量空间，top1和top分别为指向两个栈顶元素的指针，则“栈满”的判定条件是____________。
20.设S1="good",S2=" ",S3="book"，则S1，S2和S3依次联接后的结果是____________。
21.假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A[9][8][7]的存储地址是____________。
22.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为____________。
23.能够成功完全拓扑排序的图一定是一个____________。
24.如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用____________较为适当。
25.假设哈希表的表长为m，哈希函数为H(key)，若用线性探查法解决冲突，则探查地址序列的形式表达为____________。
三、解答题 (本大题共4小题，每小题5分，共20分)
26.假设通信电文使用的字符集为{a,b,c,d,e,f}，名字符在电文中出现的频度分别为：34，5，12，23，8，18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值)，然后分别写出每个字符对应的编码。
27.已知一个图如下所示，其顶点按a、b、c、d、e、f顺序存放在邻接表的顶点表中，请画出该图的邻接表，使得按此邻接表进行深度优先遍历时得到的顶点序列为acbefd，进行广度优先遍历时得到的顶点序列为acbdfe。
28.已知两个4×5的稀疏矩阵的三元组表分别如下：
0 1 4 16 0 1 1 32
1 2 2 18 1 2 2 - 22
2 3 4 - 25 2 2 5 69
3 4 2 28 3 3 4 25
4 4 2 51
请画出这两个稀疏矩阵之和的三元组表。
29.从空树起，依次插入关键字40，8，90，15，62，95，12，23，56，32，构造一棵二叉排序树。
(1)画出该二叉排序树
(2)画出删去该树中元素值为90的结点之后的二叉排序树。
四、算法阅读题 (本大题共4小题，每小题5分，共20分)
30.如图所示，利用同一循环向量空间实现两个队列，其类型Queue2定义如下：
typedef struct {
DataType data[MaxSize];
int front[2],length[2];
} Queue2;
对于 i=0或1,front[i]和length[i]分别为第i个队列的头指针和长度域。请在空缺处填入合适的内容，实现第i个循环队列的入队操作。
int EnQueue(Queue2*Q,int i,DataType x)
{//若第i个队列不满，则元素x入队列，并返回1，否则返回0
if(i<0||i>1)return 0;
if( (1) )
return 0;
Q->data[ (2) ]=x;
Q->length[ (3) ]++;
return 1;
}
(1)
(2)
(3)
31.某二叉树的线索链表存储结构如图(b)所示，其中p为指向根结点的指针，图(a)为结点结构。阅读下列算法，并回答问题：
(1)写出执行函数调用f(p)的输出结果;
(2)简述函数f的功能。
{
while(t)
{
printf(t->data);
if(t->lchild)
t=t->lchild;
else
t=t->rchild;
}
}
(1)
(2)
32.下列函数FindCycle(G,i)的功能是，对一个采用邻接表作存储结构的有向图G，利用深度优先搜索策略寻找一条经过顶点v i 的简单回路。数组cycle_path用于保存搜索过程中形成的回路，cycle_path[k]=j(j≥0)表示在回路中顶点v k 的下一个顶点是v j 。请在空缺处填入合适的内容，使其成为一个完整的算法。
vertex firstedge
已知邻接表的顶点表结点结构为：
adjvex next
边表结点 EdgeNode结构为：
int cycle_path[MaxNum];
int FindCycle(ALGraph*G,int i)
{//若回路存在，则返回1，否则返回0
int j;
for(j=0;j n;j++)cycle_path[j]=-1;
return DFSPath(G,i,i);
}
int DFSPath(ALGraph*G,int j,int i)
{
EdgeNode *p;
int cycled=0;
for(p=G->adjlist[j].firstedge;p&&!cycled;p=p->next)
{
cycle_path[j]=p->adjvex;
if( (1 ) )cycled=1;//已找到回路
else
if(cycle_path[p->adjvex]==-1)cycled= (2) ;
}
return (3)
}
(1)
(2)
(3)
33.阅读下列函数algo,并回答问题。
(1)假设整型数组A[1..8]中的元素依次为(3，8，9，1，7，4，2，6)。执行函数调用algo(A,8)时，外层while的循环体执行多少次?函数的返回值是多少?
(2)简述函数algo(L,n)的功能。
int algo(int L[],intn)
{
int i=0,j,s=1,t=n;
while (i!=(n+1)/2)
{
int x=L[s];
i=s;j=t;
while(i
自考题库及答案可以登录查找。作为专门的在线教育平台，的备考指导栏目就专门收录有自考的历年真题和模拟练习题，还有备考的知识点指导。点击底部咨询官网。 自考怎么复习？ 1、根据自考大纲泛读教材，找好考试重点 了解了自考的考试大纲以后，需要分清知识点的主次，可以让自己较大程度的提高自己学习的效率。 2、依次熟悉题型 对自考教材的知识有了一定把握以后，就可以开始完成刷题做题。在第一次开始完成自考题型的时候，可以先翻开自考资料，将自考科目的每个题型都依次熟悉一遍。了解每个学科对应的是哪些题型，再对每个题型进行多次练习。 3、分析标准答案 在做完一套自考练习之后，可以在校对答案的时候，要学会自己分析自考的参考答案。 有些考生在完成问题后，很少分析答案是如何得到的，这样的学习效果不好。 分析自考的标准答案可以增强对知识点的记忆，避免盲目陷入问题的海洋。 4、做历年真题，了解分值 每个考生都尽量完成一套历年的试题，了解分数的分布，这有利于我们合理分配好自考学习的时间。自考/成考有疑问、不知道如何总结自考/成考考点内容、不清楚自考/成考报名当地政策，点击底部咨询官网，免费领取复习资料：
自考数据库系统原理历年真题如下：
（1）试为该图书借阅系统设计一个ER模型，要求标注联系类型，可省略实体属性。
（2）根据转换规则，将ER模型转换成关系模型，要求标注每个关系模式的主键和外键（如
果存在）。
关于数据库的介绍如下：
数据库是存放数据的仓库。它的存储空间很大，可以存放百万条、千万条、上亿条数据。但是数据库并不是随意地将数据进行存放，是有一定的规则的，否则查询的效率会很低。当今世界是一个充满着数据的互联网世界，充斥着大量的数据。
即这个互联网世界就是数据世界。数据的来源有很多，比如出行记录、消费记录、浏览的网页、发送的消息等等。除了文本类型的数据，图像、音乐、声音都是数据。
数据库是“按照数据结构来组织、存储和管理数据的仓库”。是一个长期存储在计算机内的、有组织的、可共享的、统一管理的大量数据的集合。
在数据库的发展历史上，数据库先后经历了层次数据库、网状数据库和关系数据库等各个阶段的发展，数据库技术在各个方面的快速的发展。
【免费定制个人学历提升方案和复习资料： 】自考本科论文查重形式通常是以抽查为主，但也不排除部分学校会进行覆盖式的查重方式，自考本科论文虽然要进行查重，但相对并不是非常严格，查重标准有所放宽。据了解，基本上每个学校都会组织论文查重检测的。只不过有的学校会采用抽样检测的方法。一般学校是不允许超过20%的相似度，也有部分学校是30%。其实毕业论文还是比较难写的，一般本科毕业论文都是在知网查重的。但是也有考生，整篇论文都是自己写的，但是在查重过程中却超过了学校设定的查重率要求，其实论文查重率会受论文检测系统的影响，每个学校使用的检测系统可能都是不同的，一般来说，毕业论文里面要写参考文献，但有时候学校使用的检测系统如果没收录你参考文献那篇论文的话，你的论文就很好通过了。毕业论文通过与否主要是靠个人，要保证论文的查重过关，毕业论文最好还是要原创的，如果引用他人的文章，那么需用同义词语替换才行。自考本科论文答辩自考论文查重自考毕业论文需不需要查重自考毕业论文查重自考毕业设计查重自考本科论文下方免费学历提升方案介绍： 2020年10月自考02331数据结构真题试卷 格式：PDF大小：378.68KB 201704自考00182公共关系学真题试卷 格式：PDF大小：289.28KB自考/成考考试有疑问、不知道自考/成考考点内容、不清楚自考/成考考试当地政策，点击底部咨询猎考网，免费获取个人学历提升方案：
【免费定制个人学历提升方案和复习资料： 】成人自考大专有什么要求？成人自考大专是成人获取学历的方式，入学门槛较低，凡是中华人民共和国公民，包括港澳台同胞，不受性别、年龄、学历、种族、民族、居住地、身体健康状况等条件限制，均可报考自考。申请成人自考大专毕业的条件如下：1、考完本专业考试计划所规定的理论课程且考试成绩合格。2、完成该专业所规定的实践性环节课程考核，并取得合格成绩。3、思想品德经鉴定符合要求。4、办理本科毕业证书者，必须具有国家承认学历的专科及以上毕业证书。自考大专毕业证书的效力《中华人民共和国高等教育法》明确规定：国家实行高等教育自学考试制度，经考试合格的，发给相应的学历证书。国务院颁布的《高等教育自学考试暂行条例》中明确规定“高等教育自学考试毕业证书获得者的待遇与普通高校同类毕业生相同”，可以考研，出国留学等。其中澳大利亚、英国的高等学府都承认，世界上有20多个国家承认自考学历。成人自考大专成人自考大专报名成人自考大专报考成人自考大专报名要求成人自考大专报名条件成人自考大专报考要求下方免费学历提升方案介绍： 2020年10月自考02331数据结构真题试卷 格式：PDF大小：378.68KB 201510自考00183消费经济学真题试卷 格式：PDF大小：337.15KB自考/成考考试有疑问、不知道自考/成考考点内容、不清楚自考/成考考试当地政策，点击底部咨询猎考网，免费获取个人学历提升方案：
数据 ：是描述客观事物属性的数、字符及所有能输入到计算机中并能被计算机程序识别和处理的符号的集合。
数据元素 ：是数据的基本单元，可由多项数据项组成。
数据项 ：是构成数据元素的不可分割的最小单元。
数据对象 ：是具有相同性质的数据元素的集合，是数据的一个子集。
数据结构 ：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
数据类型 ：是一个值的集合和定义在此集合上的一组操作的总称。
抽象数据类型（ADT） ：描述了数据的逻辑结构和抽象运算，通常用（数据对象，数据关系，基本操作集）这样的三元组来表示
数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算，缺一不可。
逻辑结构 ：是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。
存储结构 ：是指数据结构在计算机中的表示（又称 映像 ），也称 物理结构 。
数据的运算 ：施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。
【免费定制个人学历提升方案和复习资料： 】自考本科论文查重形式通常是以抽查为主，但也不排除部分学校会进行覆盖式的查重方式，自考本科论文虽然要进行查重，但相对并不是非常严格，查重标准有所放宽。据了解，基本上每个学校都会组织论文查重检测的。只不过有的学校会采用抽样检测的方法。一般学校是不允许超过20%的相似度，也有部分学校是30%。其实毕业论文还是比较难写的，一般本科毕业论文都是在知网查重的。但是也有考生，整篇论文都是自己写的，但是在查重过程中却超过了学校设定的查重率要求，其实论文查重率会受论文检测系统的影响，每个学校使用的检测系统可能都是不同的，一般来说，毕业论文里面要写参考文献，但有时候学校使用的检测系统如果没收录你参考文献那篇论文的话，你的论文就很好通过了。毕业论文通过与否主要是靠个人，要保证论文的查重过关，毕业论文最好还是要原创的，如果引用他人的文章，那么需用同义词语替换才行。自考本科论文答辩自考论文查重自考毕业论文需不需要查重自考毕业论文查重自考毕业设计查重自考本科论文下方免费学历提升方案介绍： 2020年10月自考02331数据结构真题试卷 格式：PDF大小：378.68KB 201704自考00182公共关系学真题试卷 格式：PDF大小：289.28KB自考/成考考试有疑问、不知道自考/成考考点内容、不清楚自考/成考考试当地政策，点击底部咨询猎考网，免费获取个人学历提升方案：
全国2008年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是最符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ）A. 栈 B. 队列C. 树 D. 图2.下面程序段的时间复杂度为（ ）for (i=0; i
全国2009年1月高等教育自学考试数据结构试题课程代码02331答案急求。。谢谢。。最好答案和题都有。。尤其是答案。。谢谢啦。。
【免费定制个人学历提升方案和复习资料： 】成人自考大专的考试内容分为公共课程考试科目和专业课程考试科目，其中同一层次同一类型的自学考试的公共课程考试科目是差不多的，而专业课程的考试科目是根据专业学习的需要而开设的考试科目，每个专业都不一样。成人自考大专指的是高等教育自学考试专科层次的考试，考生完成所选专业的全部课程考试，并修满学分即可申请毕业。自考专科的招生专业众多，每一个专业的科目设置，会根据专业知识、技能的不同培养要求而有不同。所以，成人自考大专具体有哪些科目，要根据考生选择的专业而定。成人自考大专成人自考大专报名成人自考大专报考成人自考大专报名要求成人自考大专报名条件成人自考大专报考要求下方免费学历提升方案介绍： 2016年10月自考02331数据结构真题试卷 格式：PDF大小：377.58KB 2015年04月自考03410工程造价真题试卷 格式：PDF大小：224.42KB自考/成考考试有疑问、不知道自考/成考考点内容、不清楚自考/成考考试当地政策，点击底部咨询猎考网，免费获取个人学历提升方案：