02142自考数据结构导论今天我们的教务老师给同学来讲讲以下这些问题，如果你觉得还不错，可以收藏我们网站哦，我们专注于自学考试教材购买服务网哦，接下来一起来阅读下面的正文吧！一、什么是02142自考数据结构导论02142自考数据结构导论是一门数据结构课程，是针对自学考试（自考）考生设计的一门课程，是由中国自学考试网络中心制定的一门数据结构课程，课程编号为02142。该课程旨在帮助学生掌握数据结构的基础理论，并能够应用数据结构解决实际问题。二、02142自考数据结构导论的主要内容02142自考数据结构导论的主要内容包括：数据结构的概念与分类、线性表、栈与队列、树与二叉树、图、查找与排序、哈希表、字符串匹配算法等。三、02142自考数据结构导论的学习要求02142自考数据结构导论的学习要求主要是要求学生掌握数据结构的基本概念、基本原理和基本算法，能够熟练掌握数据结构中的常见算法，并能够运用数据结构解决实际问题。四、02142自考数据结构导论的考试形式02142自考数据结构导论的考试形式主要是采用闭卷考试的形式，考试内容主要包括理论知识和实际应用，考试时间为90分钟，满分100分。五、02142自考数据结构导论的学习方法02142自考数据结构导论的学习方法主要有以下几点：1、充分理解数据结构的基本概念、基本原理和基本算法；2、熟练掌握数据结构中的常见算法；3、多练习，熟练掌握数据结构的应用；4、注意把握考试的重点，掌握考试的规律。六、02142自考数据结构导论的重要性02142自考数据结构导论是一门重要的课程，它不仅可以帮助学生掌握数据结构的基本概念、基本原理和基本算法，而且还可以帮助学生掌握数据结构中的常见算法，并能够运用数据结构解决实际问题，这对于学生的今后学习和工作具有重要的意义。自考/成考有疑问、不知道自考/成考考点内容、不清楚当地自考/成考政策，点击底部咨询官网老师，免费领取复习资料：
《数据结构》是计算机科学与技术专业本科生的一门必修课程。本课程介绍如何组织各种数据在计算机中的存储、传递和转换。内容包括：数组、链接表、栈和队列、递归、树与森林、图、堆与优先级队列、集合与搜索结构、排序、索引与散列结构等。课程采用面向对象的观点讨论数据结构技术，并以兼有面向过程和面向对象双重特色的C++语言作为算法的描述工具，强化数据结构基本知识和面向对象程序设计基本能力的双基训练。为后续计算机专业课程的学习打下坚实的基础。社会在发展，科技在进步，人们的工作、学习、生活都离不开计算机网络。自考计算机网络专业也受到报考考生的青睐，越来越多考生选择报考自考计算机网络专业，一方面可以学习到专业的计算机网络知识，一方面能拿到这所名牌高校的毕业证书。想要报考自考计算机网络专业的考生可以通过网上报名或现场报名的形式进行报考。详情可咨询猎考网
确实比较难，我做了一套试卷（共13张试卷都附有答案详解）之后考试结果只考了49分，我又重新买了一套另一个出版社的试卷，然后认认真真的把书的每一章看几遍把重点的记录在一个本子上面，最后边做题边看下相关的章节加深理解，最后考试也才只考了65分。
五 实验及实习要求
课程设置的目的和意义数据结构是计算机专业本科学生必修的一门专业基础课 通过这门课程的学习 可以使学生掌握三类数据结构的表示与实现 并能将其应用实际问题的求解过程中 培养对问题分析 表示和实现的能力 为独立设计算法和对算法进行复杂性分析奠定坚实的理论基础 本课程在本科生阶段的计算机专业基础课处于一个打基础的地位 本课程的前导课程为计算机科学导论 离散数学 C语言程序设计 学习完本课程后 学生应当能够独立分析 表示并求解基本的问题 设计具有一些小规模程序 学生通过自己动手设计数据结构 编制程序并实现 然后形成分析结果 可以使学生充分认识到课堂上所讲授的各种方法的涵义 体会到各种方法的优缺点 并进一步掌握用高级语言编程和训练对实际问题求解的方法
应达到的基本要求学生在进行完本实验课的教学后 应该能够掌握计算机问题求解中常见的数据结构的表示与实现 对于线性结构 树状结构和网状结构三类结构有明确的认识 能够设计比较简单问题的算法 并可以根据算法编制 调试运行相应的程序 可以对算法的复杂度进行估计与证明 能够编写 组织测试数据 根据实验结果作出算法的性能分布图 并对实验结果进行评价
教学文件及教学形式教学文件:数据结构教科书 讲义 实验报告学生自拟 实验环境:本实验可选用的高级语言为C/C++ 实验用机的硬件配置 软件环境自定
实验成绩评定每次实验的成绩按照 分制评分 实验课的总成绩将按一定比例结合到课程总成绩中
实验报告基本格式实验目的:同教材实验要求:同教材上机环境:硬件配置与软件环境(包括操作系统 编译器等) 完成时间:使用多少个小时来完成本题目 程序说明:使用文字和/或框图说明程序的基本结构程序清单:测试数据与测试结果:思考题:感想与建议:
《数据结构》是计算机科学与技术专业本科生的一门必修课程。本课程介绍如何组织各种数据在计算机中的存储、传递和转换。内容包括：数组、链接表、栈和队列、递归、树与森林、图、堆与优先级队列、集合与搜索结构、排序、索引与散列结构等。课程采用面向对象的观点讨论数据结构技术，并以兼有面向过程和面向对象双重特色的C++语言作为算法的描述工具，强化数据结构基本知识和面向对象程序设计基本能力的双基训练。为后续计算机专业课程的学习打下坚实的基础。社会在发展，科技在进步，人们的工作、学习、生活都离不开计算机网络。自考计算机网络专业也受到报考考生的青睐，越来越多考生选择报考自考计算机网络专业，一方面可以学习到专业的计算机网络知识，一方面能拿到这所名牌高校的毕业证书。想要报考自考计算机网络专业的考生可以通过网上报名或现场报名的形式进行报考。详情可咨询猎考网
一 单项选择题(本大题共 小题 每小题 分 共 分 在每小题的四个备选答案中 选出一个正确答案 并将正确答案的序号填在题干的括号内)
下面程序段的时间复杂度是( )
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
一 单项选择题(本大题共 小题 每小题 分 共 分)
在每小题列出的四个备选项中只有一个是符合题目要求的 请将其代码填写在题后的括号内 错选 多选或未选均无分
在数据结构中 数据的逻辑结构可以分成()
A 内部结构和外部结构 B 线性结构和非线性结构
C 紧凑结构和非紧揍结构 D 动态结构和静态结构
在以单链表为存储结构的线性表中 数据元素之间的逻辑关系用()
A 数据元素的相邻地址表示 B 数据元素在表中的序号表示
C 指向后继元素的指针表示 D 数据元素的值表示
设 p 指向单链表中的一个结点 s 指向待插入的结点 则下述程序段的功能是()
s > next = p > next; p > next = s;
t = p > data; p > data = s > data; s >data = t;
A 结点 *p 与结点 *s 的数据域互换
B 在 p 所指结点的元素之前插入元素
C 在 p 所指结点的元素之后插入元素
D 在结点 *p 之前插入结点 *s
栈和队列都是()
A 限制存取位置的线性结构 B 顺序存储的线性结构
C 链式存储的线性结构 D 限制存取位置的非线性结构
若数组 s[ n ] 为两个栈 s 和 s 的共用存储空间 且仅当 s[ n ] 全满时 各栈才不能进行进栈操作 则为这两个栈分配空间的最佳方案是 s 和 s 的栈顶指针的初值分别为()
A 和 n+ B 和 n/
C 和 n D 和 n+
执行下列程序段后 串 X 的值为()
S= 〞 abcdefgh 〞 ; T= 〞 xyzw 〞 ;
substr (X S strlen(T));
substr (Y S stelen(T) );
strcat (X Y);
A 〞 cdefgh 〞 B 〞 cdxyzw 〞
C 〞 cdefxy 〞 D 〞 cdefef 〞
多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为()
A 数组的元素处在行和列两个关系中 B 数组的元素必须从左到右顺序排列
C 数组的元素之间存在次序关系 D 数组是多维结构 内存是一维结构
从广义表 LS =( (p q) r s )中分解出原子 q 的运算是()
A tail (head (LS)) B head (tail (head (LS)))
C head (tail (LS)) D tail (tail (head (LS)))
在具有 n 个叶子结点的严格二叉树中 结点总数为()
A n+ B n
C n D n
若 是有向图的一条边 则称()
A v i 邻接于 v j B v j 邻接于 v i
C v i 和 v j 相互邻接 D v i 与 v j 不相邻接
在一个带权连通图 G 中 权值最小的边一定包含在 G 的()
A 最小生成树中 B 深度优先生成树中
C 广度优先生成树中 D 深度优先生成森林中
当在二叉排序树中插入一个新结点时 若树中不存在与待插入结点的关键字相同的结点 且新结点的关键字小于根结点的关键字 则新结点将成为()
A 左子树的叶子结点 B 左子树的分支结点
C 右子树的叶子结点 D 右子树的分支结点
希尔排序的增量序列必须是()
A 递增的 B 随机的
C 递减的 D 非递减的
如果在排序过程中 每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置 则该排序方法称为()
A 插入排序 B 归并排序
C 冒泡排序 D 堆排序
设置溢出区的文件是()
A 索引非顺序文件 B ISAM 文件
C VSAM 文件 D 顺序文件
二 填空题(本大题共 小题 每小题 分 共 分)
请在每小题的空格中填上正确答案 错填 不填均无分
下列程序段的时间复杂度为 ________________
product = ;
for (i = n;i> ; i )
for (j = i+ ; j product *=j; 17 .已知指针 p 指向单链表中某个结点，则语句 p -> next =p -> next -> next 的作用是 ________________ 。WiNGwit. 18 .假设元素只能按 a,b,c,d 的顺序依次进栈，且得到的出栈序列中的第一个元素为 c ，则可能得到的出栈序列为 ________________ ，不可能得到的出栈序列为 ________________ 。 19 .若链串结点中的指针占 4 个字节，每个字符占 1 个字节，则结点大小为 2 的链串的存储密度为 ________________ 。 20 .右图表示的广义表为 ________________ 。 21 .若一棵满三叉树中含有 121 个结点，则该 树的深度为 ________________ 。 22 .若以邻接矩阵表示有向图，则邻接矩阵上 第 i 行中非零元素的个数即为顶点 v i 的 ________________ 。 23 .若希望只进行 8 趟排序便能在 4800 个元素中找出其中值最小的 8 个元素，并且要求排序过程中所进行的关键字比较次数尽可能少，则应该选用 ________________ 排序方法。 24 .在含 20 个关键字的 3 阶 B 树( 2 - 3 树)上查找一个关键字，至多需要访问 ___________ 次外存。 25 .文件上的两类主要操作为 ________________ 和 ________________ 。 三、解答题(本大题共 4 小题，每小题 5 分，共 20 分) 26 .设栈 S1 的入栈序列为 1 2 3 4 (每个数字为 13 个元素)，则不可能得到出栈序列 3142 。但可通过增设栈 S2 来实现。例如，按下图中的箭头指示，依次经过栈 S1 和 S2 ，便可得到序列 3 1 4 2 。 如果用 H1 和 H2 分别表示栈 S1 和 S2 的进栈操作，用 P1 和 P2 分别表示两个栈的出栈操作，则得到 3 1 4 2 的一个操作步骤为 H1 ， H1 ， H1 ， P1 ， H2 ， P2 ， P1 ， H2 ， P1 ， H2 ， P2 ， H1 ， P1 ， H2 ， P2 ， P2 请仿照上例写出利用两个栈从 1 2 3 4 得到 4 1 3 2 的操作步骤。 27 .已知树如右图所示， ( 1 )写出该树的后序序列; ( 2 )画出由该树转换得到的二叉树。 28 .为关键字( 17 ， 33 ， 31 ， 40 ， 48 )构造一个长度为 7 的散列表，设散列函数为 h(key)=key%7, 用开放定址法解决冲突的探查序列是 hi = (h(key) + i(key%5+1))%7 0 ≤ i ≤ 6 ( 1 )画出构造所得的散列表; ( 2 )求出在等概率情况下查找成功时的平均查找长度。 29 .已知 R [ 1..8 ]中的元素依次为( 12 ， 5 ， 9 ， 20 ， 6 ， 31 ， 24 ， 27 )，写出按算法 MergeSortDC 对 R 进行自顶向下的二路归并排序过程中，前 5 次调用函数 Merge(R, low, mid, high) 时参数 low, mid 和 high 的值。 void MergeSortDC (int R[], int low, int mid, int high ) { int mid; if (low { mid = (low +high)/2; MergeSortDC (R, low, mid); MergeSortDC (R, mid+1, high); Merge (R, low, mid, high); } } // MergeSortDC ( 1 )第一次调用时的参数值; ( 2 )第二次调用时的参数值; ( 3 )第三次调用时的参数值; ( 4 )第四次调用时的参数值; ( 5 )第五次调用时的参数值; 四、算法阅读题(本大题共 4 小题，每小题 5 分，共 20 分) 30 .下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表(表中不存在值相同的数据元素)进行如下操作：将所有在 Lb 表中存在而 La 表中不存在的结点插入到 La 中，其中 La 和 Lb 分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。 void union (LinkList La, LinkList Lb) { // 本算法的功能是将所有 Lb 表中存在而 La 表中不存在的结点插入到 La 表中 LinkList pre = La, q; LinkList pa = La -> next; LinkList pb = Lb -> next; free (Lb); while (pa && pd) { if (pa -> data data) { pre = pa; pa = pa -> next;} else if (pa -> data > pb ->data) { (1) ; pre = pb; pb = pb -> next; (2) ; } else { q = pb; pb = pb -> next; free (q); } } if (pb) (3) ; } (1) (2) (3) 【免费获取学历提升方案和复习资料：https://www.jxjyw.com/tg/?bdlk】自考本科计算机专业的考试科目有计算机操作系统、软件工程、操作系统、计算机应用与技术、概率论、数据库及其应用、数据库系统原理、数据结构、线性代数等。自考本科计算机考试科目有哪些1、必考科目概率论与数理统计(二)、高等数学(工本)、软件工程、计算机及应用毕业设计(实践+考核)、数据库系统原理、数据结构、操作系统、离散数学、英语(二);中国近现代史纲要、C++程序设计、计算机系统结构、计算机及应用课程实验(二)(实践+考核)、计算机网络原理、Java语言程序设计(一)、马原等。2、加考科目计算机组成原理、电子技术基础(三)(笔试+实践考核)、高级语言程序设计(一)(笔试+实践考核)、普通逻辑等。自学考试本科毕业条件是什么1、考完本专业考试计划所规定的理论课程且考试成绩合格。2、完成该专业所规定的实践性环节课程考核，并取得合格成绩。3、思想品德经鉴定符合要求。4、办理本科毕业证书者，必须具有国家承认学历的专科及以上毕业证书。自考本科计算机专业的就业方向有哪些自考本科计算机专业的毕业生们主要面向商业、贸易、金融、网络等企业，从事网络应用、硬件组装与维修、软件开发、系统维护、信息统计分析与处理、数据库系统与应用、管理学基础、网站设计与维护、电子商务等工作，这类专业毕业人员拥有广泛的选择权，能够慢慢挑选一个适合自己长远发展的行业。报考考试有疑问、不知道如何考点内容、不清楚报考考试当地政策，点击底部咨询猎考网，免费领取复习资料： 数据库管理系统常见的数据模型：1、层次模型 将数据组织成一对多关系的结构，层次结构采用关键字来访问其中每一层次的每一部分；2、网状模型 用连接指令或指针来确定数据间的显式连接关系，是具有多对多类型的数据组织方式；3、关系模型 以记录组或数据表的形式组织数据，以便于利用各种地理实体与属性之间的关系进行存储和变换，不分层也无指针，是建立空间数据和属性数据之间关系的一种非常有效的数据组织方法。 第三章 关系数据库SQL语言 本章为重点章，应熟悉和掌握SQL的数据定义、数据查询、数据更新的句法及其应用，特别是数据查询的应用。结合上机操作进行理解和掌握。 一、SQL概述。 1、SQL发展历程（ 识记 ） SQL从1970年美国IBM研究中心的E.F.Codd发表论文到1974年Boyce和Chamberlin把SQUARE语言改为SEQUEL语言，到现在还在不断完善和发展之中，SQL（结构式查询语言）虽然名为查询，但实际上具有定义、查询、更新和控制等多种功能。 2、SQL数据库的体系结构（ 领会 ） SQL数据库的体系结构也是三级结构 ，但术语与传统关系模型术语不同，在SQL中，关系模式称为“ 基本表 ”，存储模式称为“ 存储文件 ”，子模式称为“ 视图 ”，元组称“ 行 ”，属性称“ 列 ”。 SQL数据库体系的结构要点如下： （1）一个SQL数据库是表的汇集。 （2）一个SQL表由行集构成，行是列的序列，每列对应一个数据项。 （3）表或者是基本表，或者是视图。基本表是实际存储在数据库中的表，视图由是由若干基本表或其他视图构成的表的定义。 （4）一个基本表可以跨一个或多个存储文件，一个存储文件也可存放一个或多个基本表。存储文件与物理文件对应。 （5）用户可以用SQL语句对表进行操作，包括视图和基本表。 （6）SQL的用户可以是应用程序，也可以是终端用户。 3、SQL的组成（ 识记 ） SQL由四部分组成： （1）数据定义：SQL DDL.定义SQL模式，基本表、视图和索引。 （2）数据操纵：SQL DML.包括数据查询和数据更新（增、删、改）。 （3）数据控制：包括对基本表和视图的授权、完整性规则的描述，事务控制等。 （4）嵌入式SQL的使用规定。 二、SQL的数据定义（ 简单应用 ） 1、SQL模式的创建和撤消： SQL 模式的创建 可简单理解为建立一个数据库，定义一个存储空间，其句法是： CREAT SCHEMA 模式名> AUTHORIZATION 用户名> 撤消SQL模式的句法为： DROP SCHEMA 模式名> [ CASCADE | RESTRICT ] 方括号中的选项参数CASCADE表示连锁方式，执行时将模式下所有基本表、视图、索引等元素全部撤消。RESTRICT表示约束式，执行时必须在SQL模式中没有任何下属元素时方可撤消模式。 2、SQL提供的基本数据类型 数值型：包括 integer、smallint、real、double precision 、float（n），numeric（p，d） 字符串型：char（n）、varchar（n），前者是定长，后者为变长串 位串型：bit（n），bit varying（n），同上。 时间型：date、time. 3、基本表的创建、修改和撤消 基本表的创建：（可理解为建立表结构） CREAT TABLE SQL 模式名。基本表名 （列名，类型， …… 完整性约束……） 完整性约束包括主键子句（PRIMARY KEY）、检查子句（CHECK）和外键子句（Foreign KEY）。 基本表结构的修改 ALTER TABLE 基本表名 ADD/ DROP （增加/删除） 列名 类型名（增加时写出） 删除时有子句 [CASCADE|RESTRICT]，前者为连锁删除，后者为约束删除，即没有对本列的任何引用时才能删除。 基本表的撤消 DROP TABLE 基本表名 [CASCADE|RESTRICT] 4、视图的创建和撤消 创建： CREAT VIEW 视图名（列名表） AS SELECT 查询语句 撤消： DROP VIEW 视图名 5、索引的创建和撤消 创建： CREAT [UNIQUE] INDEX 索引名 ON 基本表名（列名表 [ASC|DESC]） 撤消： DROP INDEX 索引名 总结：凡创建都用 CREAT ，删除都用 DROP ，改变用 alter ，再跟类型和名字，附加子句很容易了。 三、SQL的数据查询（ 综合应用 ） 这一段是本章的重点内容，应该熟练掌握。首先了解基本句法： 1、 SELECT -FROM- WHERE 句型 SELECT 列名表（逗号隔开） FROM 基本表或视图序列 WHERE 条件表达式 在这里，重点要掌握条件表达式中各种运算符的应用，如=，>，<，>等算术比较运算符、逻辑运算符 AND、OR、NOT 、集合成员资格运算符： IN，NOT IN ，以及嵌套的 SELECT 语句的用法要特别注意理解。 针对课本的例题和课后习题进行掌握。 在查询时， SELECT 语句可以有多种写法，如 联接查询、嵌套查询和使用存在量词的嵌套查询 等。都掌握，但是起码应能写出一种正确的查询语句。 2. SELECT 语句完整的句法： SELECT 列名表（逗号隔开） FROM 基本表或视图序列 [ WHERE 条件表达式] （此为和条件子句） [GROUP BY 列名序列] （分组子句） [HAVING 组条件表达式] （组条件子句） [ORDER BY列名[ASC|DESC]……] （排序子句） 这段关于完整句法的内容能够理解也就问题不大了。 3、 SELECT 语句中的限定 这一段内容主要是对 SELECT 语句进一步使用进行的深入学习，领会下列各种限定的使用目的和方法。 要求输出表格中不出现重复元组，则在 SELECT 后加一DISTINCT SELECT 子句中允许出现加减乘除及列名，常数的算术表达式 WHERE 子句中可以用BETWEEN……AND……来限定一个值的范围 同一个基本表在 SELECT 语句中多次引用时可用AS来增加别名 WHERE 子句中字符串匹配用LIKE和两个通配符，%和下划线_. 查询结果的结构完全一致时可将两个查询进行并（UNION）交（INTERSECT）差（EXCPT）操作 查询空值操作不是用='null'，而是用 IS NULL来测试。 集合成员资格比较用 IN/NOT IN ，集合成员算术比较用元组θSOME/ALL 可以用子查询结果取名（表名（列名序列））来作为导出表使用 基本表的自然联接操作是用 NATURAL INNER JOIN来实现的。 四、SQL的数据更新（ 简单应用 ） 简单应用就是掌握基本的句型并能套用在一些简单的查询要求上。 1、数据插入： INSERT INTO 基本表名（列名表） valueS （元组值） 或 INSERT INTO 基本表名（列名表） SELECT 查询语句 其中元组值可以连续插入。用查询语句可以按要求插入所需数据。 2、数据删除： DELETE FROM 基本表名 [ WHERE 条件表达式] 3、数据修改： UPDATE 基本表名 SET 列名=值表达式，[列名=值表达式……] [ WHERE 条件表达式] 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 02142自考数据结构导论今天我们的教务老师给同学来讲讲以下这些问题，如果你觉得还不错，可以收藏我们网站哦，我们专注于自学考试教材购买服务网哦，接下来一起来阅读下面的正文吧！一、什么是02142自考数据结构导论02142自考数据结构导论是一门数据结构课程，是针对自学考试（自考）考生设计的一门课程，是由中国自学考试网络中心制定的一门数据结构课程，课程编号为02142。该课程旨在帮助学生掌握数据结构的基础理论，并能够应用数据结构解决实际问题。二、02142自考数据结构导论的主要内容02142自考数据结构导论的主要内容包括：数据结构的概念与分类、线性表、栈与队列、树与二叉树、图、查找与排序、哈希表、字符串匹配算法等。三、02142自考数据结构导论的学习要求02142自考数据结构导论的学习要求主要是要求学生掌握数据结构的基本概念、基本原理和基本算法，能够熟练掌握数据结构中的常见算法，并能够运用数据结构解决实际问题。四、02142自考数据结构导论的考试形式02142自考数据结构导论的考试形式主要是采用闭卷考试的形式，考试内容主要包括理论知识和实际应用，考试时间为90分钟，满分100分。五、02142自考数据结构导论的学习方法02142自考数据结构导论的学习方法主要有以下几点：1、充分理解数据结构的基本概念、基本原理和基本算法；2、熟练掌握数据结构中的常见算法；3、多练习，熟练掌握数据结构的应用；4、注意把握考试的重点，掌握考试的规律。六、02142自考数据结构导论的重要性02142自考数据结构导论是一门重要的课程，它不仅可以帮助学生掌握数据结构的基本概念、基本原理和基本算法，而且还可以帮助学生掌握数据结构中的常见算法，并能够运用数据结构解决实际问题，这对于学生的今后学习和工作具有重要的意义。自考/成考有疑问、不知道自考/成考考点内容、不清楚当地自考/成考政策，点击底部咨询官网老师，免费领取复习资料： 数据结构试卷(98年上半年北京市)一、 单项选择题（在每小题的四个备选答案中选出一个正确的答案，并将其号码填在题干后的号码内，每小题2分，共10分） 1.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（ ） A. 1，3，2，4 B. 2，3，4，1 C. 4，3，1，2 D. 3，4，2，1 2.下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关？（ ） A. 直接插入排序 B. 起泡排序 C. 快速排序 D. 直接选择排序 3.对n个记录的文件进行二路归并排序，总的时间代价为 A. O（nlog2n） B. O（n2） C. O（log2n） D. O（n） 4.若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（ ） A. 9 B. 11 C. 12 D. 不确定 5.下面关于B树和B+树的叙述中，不正确的是 A. B树和B+树都是平衡的多分树 B. B树和B+树都是可用于文件的索引结构 C. B树和B+树都能有效地支持顺序检索 D. B树和B+树都能有效地支持随机检索 二、 填空题（每空2分，共20分） 1.从逻辑结构看，线性表是典型的 ，树是典型的 。 2.设有二维数组A[0..9,0..19]，其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为 ，按列优顺序存储，元素A[6,6]的存储地址为 。 3.若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么当i为 且小于n时，结点I的右兄弟是结点 ，否则结点i没有右兄弟。 4.求具有最小带权外部路径长度的扩充二叉树的算法称为 算法。堆排序中建堆的方法称作 。 5.6阶B树中，每个结点至多包含 个关键码，除根和叶结点外，每个结点至少包含 个关键码。 三、 简答题（每小题6分，共18分） 1.请简述散列函数在散列法存储中的作用，并举出一个散列函数的例子。 2.请简述散列法存储中处理碰撞（冲突）的两类基本方法。 3.请简述负载因子的定义，为什么说负载因子是散列法存储的一个重要参数？ 四、 求解下列问题（每小题6分，共30分） 1.设待排序文件的关键码为（512,275,908,677,503,765,612,897,154,170）以第一元素为分界元素进行快速排序（按关键码值递增顺序），请给出一趟扫描后的结果。 2.请画出下面的树所对应的二叉树。 3.从一棵空的二叉排序树开始，将以下关键码值依次插入：25,13,15,31,7,20,37，请画出插入全部完成后的二叉排序树。 4.请画出下面带权图的一棵最小生成树。 5.对于下面的稀疏矩阵 1）画出其三元组法存储表示。 2）画出其行—列法（十字链表法）存储表示。 五、 算法题（6分） 有一个链接方式存储的线性表，表中每个结点包括两个指针，其结点用PASCAL语言描述如下： TYPE pointer=↑node; node=RECORD infdatatype; link1,link2:pointer END; 其中link1是指向结点的下一个结点的指针，link2是指向结点的前一个结点的指针,如图所示。 p和q都是pointer类型的变量，现要将q所指的新结点插入表中p所指结点的前面（说明：p所指的不是链表的第一个结点）。请用PASCAL语句写出该插入的关键步骤。（部要求写完整的算法，只要求用几个语句写出关键步骤。） 六、 算法填空和分析（共16分） 下面是用PASCAL语言编写的二分值插入排序算法，该算法对排序码为整数的线性表进行升序排序。 TYPE node=RECORD key:integer; infdatatype End; list=ARRAY[1..max] OF node; PROCEDURE binarysort (VAR R: list; n: integer); VAR temp :node ; low,m,high,I,j: integer; BEGIN nteger; BEGIN nteger; BEGIN nteger; BEGIN FOR I:=2 TO n DO BEGIN temp := R[ i ]; low :=1; high := i-1; WHILE ① DO BEGIN m :=(low+high) DIV 2; IF ② THEN high :=m-1 ELSE ③ END; FOR j := i-1 DOWNTO ④ DO R[j+1] := R[j]; ⑤ END; END; 1.请将算法的空缺处应填入的正确内容写在下面。（10分） ① ② ③ ④ ⑤ 2.设待排序的记录数n=7，当排序码的初始排列顺序分别为（15,25,35,45,55,65,75）和（75,65,55,45,35,25,15）时，请说出排序过程中对排序码所进行的总的比较次数分别是多少？（假定算法中取中项的整数除法采用小数截断的方法。）（6分）自学考试数据库结构
自学考试数据结构图