《数据结构》填空作业题答案
第1章绪论（已校对无误）1．数据结构包括数据的逻辑结构、数据的
存储结构和数据的运算三方面的内容。
2．程序包括两个内容：数据结构和算法。
3. 数据结构的形式定义为：数据结构是一个二元组：Data Structure =（D，S）。
4. 数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。
5. 数据的逻辑结构可以分类为线性结构和非线性结构两大类。
6. 在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。
7. 在树形结构中，数据元素之间存在一对多的关系。
8. 数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。
9. 数据的逻辑结构包括线性结构、树形结构和图形结构3种类型，树型结构和有向图结构合称为非线性结构。
10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。
11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。
12. 数据的存储结构可用4种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的
逻辑关系是一对多或多对多。
14. 数据结构在物理上可分为顺序存储结构和链式存储结构。
15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。
16. 数据元素可由若干个数据项组成。
17. 算法分析的两个主要方面是时间复杂度和空间复杂度。
18. 一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的
存储空间的大小来度量的。
19. 算法具有如下特点：有穷性、确定性、可行性、输入、输出。
20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切
的定义，并在有穷时间内计算出结果。
21. 下面程序段的时间复杂度为㏒n 。3
i=1；
while(i<=n)
i= i﹡3；
第2章线性表（已校对无误）1. 一线性表表示如下：（a，a，…，a，a，a，…，a），其中每个a代表一个数据元素（或iii-11i+1n2结点）。a称为起始结点，a称为终端结点，i称为a在线性表中的位置（或序号）。i1n对任意一对相邻结点a，a，（1≤i≤n），a称为a的直接前驱，a称为a的直接后继。ii+1i+1iii+1
2. 对一个长度为n的线性表，要删除第i个元素，则在顺序表示的情况下，计算复杂性为O(n) ，在链式表示的情况下，计算复杂性为O(1) 。
3. 在一个长度为n的顺序表中，向第i个元素（1≤i≤n）之前插入一个新元素时，需向后移动n－i＋1 个元素。
4. 顺序表中逻辑上相邻的元素在物理位置上一定相连。
5. 在n个结点的顺序表中插入一个结点需平均移动n/2 个结点，具体的移动次数取决于表长n和插入位置i 。
6. 在顺序表中访问任意一个结点的时间复杂度均为O(1) ，因此，顺序表也称为随机访问
的数据结构。
7. 顺序表相对于链表的优点有随机访问和空间利用率高。
8. 在长度为n的顺序表中插入一个元素的时间复杂度为O(n) 。
9. 在带有头结点的单链表L中，若要删除第一个结点，则须执行下列三条语句：U＝L->next ；L->next=U->next；free（U）。
10. 链表相对于顺序表的优点有插入和删除操作方便。
11. 在单链表中除首结点外，任意结点的存储位置都由直接前驱结点中的指针指示。
12. 在n个结点的单链表中要删除已知结点*p，需找到它的直接前驱结点的地址，其时间复杂度为O(n) 。
13．单链表中设置头结点的作用是简化操作，减少边界条件的判断。14．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的前驱结点。
15. 在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后续结点。
16. 带头结点的单链表L为空的判定条件是L->next==NULL ，不带头结点的单链
表L为空的判定条件是L==NULL 。
17. 在单链表中，指针p所指结点为最后一个结点的条件是p->next==NULL 。
18. 循环链表的最大优点是从表中任意结点出发都可访问到表中每一个元素（或从表中任意结
点出发都可遍历整个链表）。
19. 设rear是指向非空、带头结点的循环单链表的尾指针，则该链表首结点的存储位置是
rear->next->next 。
20. 带头结点的双向循环表L为空表的条件是L->prior== L->next 。
21. 在循环链表中，可根据任一结点的地址遍历整个链表，而单链表中需知道
头指针才能遍历整个链表。
22. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 1 。
第3章栈和队列（已校对无误）1. 栈又称为后进先出表，队列又称为先
进先出表。
2. 向一个顺序栈插入一个元素时，首先使栈顶指针后移一个位置，然后把
待插入元素写入（或插入）到这个位置上。
3. 从一个栈删除元素时，需要前移一位栈顶指针。
4. 在一个顺序栈中，若栈顶指针等于－1 ，则为空栈；
若栈顶指针等于maxSize－1 ，则为满栈。
5. 在一个链式栈中，若栈顶指针等于NULL，则为空栈；在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列为空或该队列
只含有一个结点。
6. 向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给栈顶指针。7．在求表达式值的算符优先算法中使用的主要数据结构是栈。
8．设有一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素
的出栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为 3 。
9. 设有一个空栈，现输入序列为1，2，3，4，5。经过push，push，pop，push，pop，push，pop，push后，输出序列是2 3 4 。
10. 在按算符优先法求解表达式3－1＋5*2时，最先执行的运算是* ，最后执
行的运算是－。
11. 在栈的ADT定义中，除初始化操作外，其他基本操作的初始条件都要求栈存在。
12. 仅允许在同一端进行插入和删除的线性表称为栈。
13. 在顺序栈s中，栈为空的条件是== ，栈为满的条件是－＞= 。
14. 设有算术表达式x＋a*（y－b）－c/d，该表达式的前缀表示为－＋x*a－
yb/cd 。
后缀表示为xayb－*＋cd/－。
15. 用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S、X操作串为SXSSXSXX 。
16. 向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行p->link＝top 和top＝p
操作。
的非空链式栈中删除结点并不需要返回栈顶结点的值和回收结点时，top从一个栈顶指针为17.
应执行top＝top->link 操作。
18. 设有一个空栈，栈顶指针为1000H（十六进制。现有输入序列为1，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，输出序列是2，3 ，而栈顶指针是100C H。设栈为顺序栈，每个元素占4个字节。
19. 在作入栈运算时应先判别栈是否满；在作出栈运算时应先判别栈是否空。
10. 用一个大小为1000的数组来实现循环队列，当前rear和front的值分别为0和994，若要达到队满的条件，还需要继续入队的元素个数是993 。
20. 队列的插入操作在队尾进行，删除操作在队头进行。
21. 在一个循环队列Q中，判断队空的条件为== ，判断队满的条件为＋1)％maxSize== 。
22. 向一个循环队列中插入元素时，需要首先移动队尾指针，然后再向所指位置写入（或插入）新插入的元素。
23. 当用长度为n的数组顺序存储一个栈时，若用top==n表示栈空，则表示栈满的条件为
top==0 。
24. 循环队列的引入，目的是为了克服假溢出时大量移动数据元素。
第4章串（已校对无误）1. 两个串相等的充分必要条件是两个串的长度相等且对应位置的字符相同。
2. 空格串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。
3. 模式串′abaabade′的next函数值为01122341
补充：
1. 串的两种最基本的存储方式是顺序存储方式和链接存储方式。
2. 空串是零个字符的串，其长度等于零。
3. 组成串的数据元素只能是字符。
4. 串是一种特殊的线性表，其特殊性表现在其数据元素都是字符。
第5章数组（已校对无误）1. 将下三角矩阵A[18，18]的下三角部分逐行地
存储到起始地址为1000的内存单元中，已知每个元....素占4个单元，则元素A[7，5]的地址为1100 。
2. 二维数组A[0…9，0…19]采用列序为主方式存储，每个元素占一个存储单元，并且元素A[0，0]的存储地址是200，则元素A[6，12]的地址是332 。
3. 二维数组A[10…20，5…10]采用行序为主方式存储，每个元素占4个存储单元，并且元素A[10，5]的存储地址是1000，则元素A[18，9]的地址是1208 。
补充：
1. 一维数组的逻辑结构是线性结构，存储结构是顺序存储结构。
2. 对于二维数组或多维数组，分为按以行为主序和按以列为主序两种不同的存储方式存储。
3. 对矩阵压缩存储是为了节省存储空间。
4. 二维数组是一种非线性结构，其中的每一个数组元素最多有二个直接前驱（或直接后继）。
第6章树（已校对无误）4. 结点最少的树为只有一个结点的树，结点最少
的二叉树为空的二叉树。
5. 根据二叉树的定义，具有三个结点的二叉树有 5 种不同的形态，它们分别是。
6. 具有n个结点的完全二叉树的深度为。
8. 以数据集{4，5，6，7，10，12，18}为结点权值所构造的哈夫曼树为需用图示，其带权路径长度为165 。
9. 哈夫曼树是带权路径长度最短的树，通常权值较大的结点离根较近。
10. 在先序遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。
第7章图（已校对无误）1．n个顶点的连通图至少有n－1 条边。
2．在无权图G的邻接矩阵A中，若（vi，vj）或〈vi，vj〉属于图G的边集，则对应元素A[i][j]等于 1 ，否则等于0 。
3. 在无向图G的邻接矩阵A中，若A[i][j]等于1，A[j] [i]等于 1 。
4. 已知图G的邻接表如下图所示，其从顶点v1出发的深度优先搜索序列为v1 v2 v3 v6 v5 v4，其从顶点v1出发的广度优先搜索序列为v1 v2 v5 v4 v3 v6。
V1^V4 V2V5v2v3V5 ^
^v3V6
v4^VV3vV4v6
〉有向，无，但〈xy〉与〈yx）被认为，）与（，中的两顶点，则（是图，设5. xyGxyyx两条弧。0 i i已知一个图的邻接矩阵表示，6. 删除所有从个结点出发的边的方法是将矩阵的第行全部置为。
个结点的j 个结点的出度，而由第j列可得到第7. 在有向图的邻接矩阵上，由第i行可得到第i
入度。。是连通8. 在无向图中，如果从顶点v到顶点v′有路径，则称v和v′
查找第8章（已校对无误）；哈希表查找法采用链接法处理冲突时的平均查找
长/2 n＋1）1. 顺序查找法的平均查找长度为（。＋度为1。哈希表查找法 2. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。有序的顺序存储结构3. 二分查找的存储结构仅限于。的表，采用分块查找法，每块的最佳长度是15 4. 长度为255。 5. N个记录的有序顺序表中进行折半查找，最大的比较次数是㏒N 2；若采用二分法查找，则时间O(n) 的线性表，若进行顺序查找，则时间复杂度为 6. 对于长度为n n），则时间复杂度为；若采用分块查找（假定总块数和每块长度均接近n) O(㏒复杂度为2O(n) 。
7. 在散列存储中，装填因子a的值越大，则存取元素时发生冲突的可能性就越大；a的值越小，则
存取元素时发生冲突的可能性就越小。
8. 对于二叉排序树的查找，若根结点元素的键值大于被查元素的键值，则应该
在二叉树的左子树
上继续查找。
9. 高度为8的平衡二叉树至少有54 个结点。
10. 在散列函数H（key）=key % p中，p应取素数。
第9章排序（已校对无误）1. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第8个记录45插入到有序表时，为寻找插入位置需比较 5 次。
2. 对于关键字序列（12，13，11，18，60，15，7，20，25，100），用筛选法建堆，必须从键值为60的关键字开始。
3. 对n个记录的表r[1…n]进行简单选择排序，所需要进行的关键字间的比较次数为n(n－1)/2 。
4. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有希尔排序、选择排序、快速排序、堆排序。
5. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是快速排序，需要内存容量最多的是基数排序。
6. 在堆排序和快速排序中，若原始记录接近正序或反序，则选用堆排序，若原始记录无序，则最好选用快速排序。
7. 在插入排序和选择排序中，若初始数据基本正序，则选用插入排序；若初始数据基本反序，则选用选择排序。
8. 对n个元素的序列进行冒泡排序时，最少的比较次数是n－1 。
9. 基数排序不需要进行记录关键字间的比较。
《数据结构》填空作业题答案 第1章绪论（已校对无误） 1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。 2．程序包括两个内容：数据结构和算法。 3. 数据结构的形式定义为：数据结构是一个二元组： Data Structure =（D，S）。 4. 数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。 5. 数据的逻辑结构可以分类为线性结构和非线性结构两大类。 6. 在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。 7. 在树形结构中，数据元素之间存在一对多的关系。 8. 数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。 9. 数据的逻辑结构包括线性结构、树形结构和图形结构 3种类型，树型结构和有向图结构合称为非线性结构。 10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。 11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。 12. 数据的存储结构可用4种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。 13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。 14. 数据结构在物理上可分为顺序存储结构和链式存储结构。 15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。 16. 数据元素可由若干个数据项组成。 17. 算法分析的两个主要方面是时间复杂度和空间复杂度。 18. 一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。 19. 算法具有如下特点：有穷性、确定性、可行性、输入、输出。 20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切 的定义，并在有穷时间内计算出结果。 n 。 21. 下面程序段的时间复杂度为㏒ 3
书面作业练习题 李英龙 湖南科技大学数学与计算科学学院
内容简介 在习题部分，既有选择题、判断题，也有用图表解答的练习题、算法设计题或综合解答分析题。并且配有部分练习题的答案供学生自学、练习、参考。 目录 书面作业练习题 习题一绪论 -------------------------------------------------------------3 习题二顺序表示（线性表、栈和队列）-----------------------------------------6 习题三链表（线性表、栈和队列）---------------------------------------------9 习题四串-----------------------------------------------------------------12 习题五数组 --------------------------------------------------------------13 习题六树与二叉树 -------------------------------------------------------15 习题七图-----------------------------------------------------------------24 习题八查找---------------------------------------------------------------30 习题九排序---------------------------------------------------------------33
1．第1题 每个属性，都有一个取值范围，这叫属性（）。 A.域 B.值 C.主属性 D.关键字 答案:A 标准答案：A 2．第2题 关系模式的规范化过程主要是为克服数据库逻辑结构中存在的插入异常、删除异常以及( ) A.数据不一致性 B.结构不合理 C.数据冗余度大 D.数据丢失 答案:C 标准答案：C 3．第3题 数据的物理独立性是( )实现的． A.外模式／模式映像 B.外模式／内模式映像 C.模式／内模式映像 D.内模式／外模式映像 答案:C 标准答案：C 4．第4题 实体-联系模型是( )． A.概念模型 B.逻辑模型 C.现实世界 D.物理模型 答案:A 标准答案：A 5．第5题 常用的用户标识方法是( )． A.用户密码 B.用户名和口令字 C.用户权限 D.用户名 答案:B 标准答案：B 6．第6题 关于数据处理和数据管理，下列叙述正确的是( )
A.数据处理经历了人工系统、文件系统、数据库系统三个阶段 B.数据处理是数据管理的中心问题 C.数据管理的主要工作是对数据进行收集、分类整理、组织、存储、维护、检索等操作 D.数据管理技术优劣不影响数据处理的效率 答案:C 标准答案：C 7．第7题 下列四项中，不属于数据库特点的是( ) A.数据共享 B.数据完整性 C.数据冗余很高 D.数据独立性高 答案:C 标准答案：C 8．第8题 SQL语言通常称为( ) A.结构化查询语言 B.结构化控制语言 C.结构化定义语言 D.结构化操纵语言 答案:A 9．第16题 以下数据库的数据模型中，现今使用的主要的数据模型是( )． A.层次模型 B.网状模型 C.关系模型 D.面向对象模型 答案:C 标准答案：C 10．第17题 设关系模式R (A，B，C)，F是R上成立的FD集，F = {B→C}，则分解ρ = {AB，BC}相对于F （） A.是无损联接，也是保持FD的分解
数据结构练习题 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。 7. 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。 for (i=0;i 1、数据结构按结点间的关系，可分为4种逻辑结构： 集合、线性结构、树形结构、图状结构。 2、数据结构中的数据元素存在多对多的关系称为图 状结构结构。 3、在一个长度为n的顺序存储结构的线性表中，向第 i(1≤i≤n+1)个元素之前插入新元素时，需向后移动n-i+1个数据元素。 4、从长度为n的采用顺序存储结构的线性表中删除第 i(1≤i≤n+1)个元素，需向前移动n-i个元素。5、数据的逻辑结构在计算机中的表示称为物理结构 或存储结构。 6、除了第1个和最后一个结点外，其余结点有且只有一 个前驱结点和后继结点的数据结构为线性结构，每个结点可有任意多个前驱和后继结点数的结构为非线性结构。 7、算法的5个重要特性是有穷性、确定性、可形 性、有零个或多个输入、有零个或多个输出。 8、数据结构中的数据元素存在一对多的关系称树 形结构结构。 9、往栈中插入元素的操作方式是：先移动栈顶指针， 后存入元素。 10、数据结构中的数据元素存在一对一的关系称为线 性结构结构。 11、要求在n个数据元素中找其中值最大的元素，设基本 操作为元素间的比较。则比较的次数和算法的时间复杂度分别为n-1和O(n)。 12、在一个单链表中p所指结点之后插入一个s所指结点 时，应执行__s->next=p->next;__和p->next=s;的操作。 13、设有一个头指针为head的单向循环链表，p指向链 表中的结点，若p->next= =head，则p所指结点为尾结点。 14、在一个单向链表中，要删除p所指结点，已知q指向 p所指结点的前驱结点。则可以用操作q->next=p->next; 。 15、设有一个头指针为head的单向链表，p指向表中某 一个结点，且有p->next= =NULL,通过操作p->next=head;,就可使该单向链表构造成单向循环 链表。 16、每个结点只包含一个指针域的线性表叫单链表。 17、线性表具有顺序存储和链式存储两种 存储结构。 18、数据的逻辑结构是从逻辑关系上描述数据，它与数据 的关系存储结构无关，是独立于计算机的。19、在双向循环链表的每个结点中包含两个指针域，其 中next指向它的直接后继，prior指向它的直接前驱，而头结点的prior指向尾结点，尾结点的next指向头结点。 20、单向循环链表是单向链表的一种扩充，当单向链表带 有头结点时，把单向链表中尾结点的指针域由空指针改为头结点的指针；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向指向第一个结点的指针。 21、线性链表的逻辑关系时通过每个结点指针域中的指 针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种链式存储结构，又称为链表。 22、栈是限定在表的一端进行插入和删除操作的线性表， 又称为后进先出表。 23、队列的特性是先进先出表。 24、删除栈中元素的操作方式是：先取出元素，后移 动栈顶指针。 25、循环队列队头指针在队尾指针下一个位置，队列是 “满”状态 26、在队列的顺序存储结构中，当插入一个新的队列元素 时，尾指针增1 ，当删除一个元素队列时，头指针增1。 27、循环队列的引入，目的是为了克服假上溢。 28、向顺序栈插入新元素分为三步：第一步进行栈是否 满判断，判断条件是s->top=MAXSIZE-1 ；第二步是修改栈顶指针；第三步是把新元素赋给栈顶对应的数组元素。同样从顺序栈删除元素分为三步：第一步进行栈是否空判断，判断条件是s->top=-1。第二步是把栈顶元素；第三步修改栈顶指针。 29、假设以S和X分别表示入栈和出栈操作，则对输入序 列a,b,c,d,e一系列栈操作SSXSXSSXXX之后，得到的输出序列为bceda。 1、有一课程管理系统，有如下特点：一个系可开设多门课程，但一门课只在一个系部开设，一个学生可选修多门课程，每门课可供若干学生选修，一名教师只教一门课程，但一门课程可有几名教师讲授，每个系聘用多名教师，但一个教师只能被一个系所聘用，要求这个课程管理系统能查到任何一个学生某门课程的成绩，以及这个学生的这门课是哪个老师所教的。 （1）请根据以上描述，绘制相应的E-R图，并直接在E-R图上注明实体名、属性、联系类型； （2）将E-R图转换成关系模型，画出相应的数据库模型图，并说明主键和外键。 （3）分析这些关系模式中所包含的函数依赖，根据这些函数依赖，分析相应的关系模式达到了第几范式。对这些关系模式进行规范化。 1、参考答案： 2、设某汽车运输公司数据库中有三个实体集。一是“车队”实体集，属性有车队号、车队名等；二是“车辆”实体集，属性有牌照号、厂家、出厂日期等；三是“司机”实体集，属性有司机编号、姓名、电话等。 车队与司机之间存在“聘用”联系，每个车队可聘用若干司机，但每个司机只能应聘于一个车队，车队聘用司机有“聘用开始时间”和“聘期”两个属性； 车队与车辆之间存在“拥有”联系，每个车队可拥有若干车辆，但每辆车只能属于一个车队； 司机与车辆之间存在着“使用”联系，司机使用车辆有“使用日期”和“公里数”两个属性，每个司机可使用多辆汽车，每辆汽车可被多个司机使用。 （1）请根据以上描述，绘制相应的E-R图，并直接在E-R图上注明实体名、属性、联系类型； （2）将E-R图转换成关系模型，画出相应的数据库模型图，并说明主键和外键。 （3）分析这些关系模式中所包含的函数依赖，根据这些函数依赖，分析相应的关系模式达到了第几范式。对这些关系模式进行规范化。 2、参考答案： 《数据结构-C语言版》 第一章绪论 单项选择题 1．在数据结构中，数据的基本单位是_____ ____。 A. 数据项 B. 数据类型 C. 数据元素 D. 数据变量 2．数据结构中数据元素之间的逻辑关系被称为__ ____。 A. 数据的存储结构 B. 数据的基本操作 C. 程序的算法 D. 数据的逻辑结构3．在数据结构中，与所使用计算机无关的是数据的____ ___。 A. 存储结构 B. 逻辑和物理结构 C. 逻辑结构 D. 物理结构4．在链式存储结构中，数据之间的关系是通过____ ____体现的。 A. 数据在内存的相对位置 B. 指示数据元素的指针 C. 数据的存储地址 D. 指针 5．计算算法的时间复杂度是属于一种____ ___。 A. 事前统计的方法 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法 6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。 A. n2 B. nlogn C. n D. logn 7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。 A. O(1) B. O(n) C. O(200n) D. O(nlog2n) CDCBBDD 第二章线性表 单项选择题 1．链表不具有的特点是____ ____。 A. 可随机访问任一元素 B. 插入和删除时不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表的长度正比 2．设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。 A. 139 B. 140 C. 147 D. 148 3．在线性链表存储结构下，插入操作算法。 A. 需要判断是否表满 B. 需要判断是否表空 C. 不需要判断表满 D. 需要判断是否表空和表满 4．在一个单链表中，若删除p所指结点的后继结点，则执行。 A. p->next = p->next->next; B. p->next = p->next; C. p = p->next->next; D. p = p->next; p->next = p->next->next; 5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。A. O(n) B. O(1) C. O(m) D. O(m+n) 6．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是。 A. 单链表 B. 静态链表 C. 线性链表 D. 顺序存储方式ACCABB 填空题 1．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_____结点。2．在单链表中，指针p所指结点为最后一个结点的条件是。 3．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。4．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是。 5．在长度为n的顺序表中插入一个元素的时间复杂度为。 1前驱 2 p->next==NULL 复习题（一） 一．填空题（每空1分，共15分） 1.一个算法的效率可分为___________________效率和___________________效率。 2.__________________是被限定为只能在表的一端进行插入运算，在表的另一端 进行删除运算的线性表。 3.设S=“A;/document/Mary.doc”，则strlen(S)= _______________，“/”的字符定位 的位置为_______________。 4.设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列 序为主序顺序存储，则元素a[32,58]的存储地址为_______________。 5.一棵深度为6的满二叉树有_______________个分支结点和_______________个 叶子。 6.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度 是。 7.设有一稀疏图G，则G采用存储较省空间。 8.快速排序算法是对算法的一种改进。 9.在数据的存放无规律而言的线性表中进行检索的最佳方法 是。 10.大多数排序算法都有两个基本的操作： 和。 11.设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重 新排列，则：快速排序一趟扫描的结果是。 二．选择题（每题2分，共30分） （）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： （A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构 （）2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要 一、.创建带有输入和输出参数的存储过程。 A..创建计算某个学生的个人平均成绩的通用存储过程PJ，执行存储过程PJ,并打印学号= ‘ 9601005’计算结果。 use xssjk go create procedure PJ @st_no char(8),@average float output as select @average=avg(成绩) from 成绩 Where 学号=@st_no go 执行存储过程： declare @average float exec PJ'9601002',@average output print @average B.创建统计某门课程选课人数的通用存储过程TJ，执行存储过程TJ，打印课程号=‘005’的计算结果。 use xssjk go create procedure TJ1 @kch char(3),@xk int output as select @xk=COUNT(学号) from 成绩 where 课程号=@kch group by 课程号 Go 执行存储过程； use xssjk go declare @xk int exec TJ1'001',@xk output print @xk 二、 1.什么是游标？为什么要使用游标？ （1）游标是系统为用户开设的一个数据缓冲区，存放SQL语句的执行结果 每个游标区都有一个名字，用户可以用SQL语句逐一从游标中获取记录，并赋给主变量，交由主语言进一步处理。 （2）SQL语言与主语言具有不同数据处理方式 SQL语言是面向集合的，一条SQL语句原则上可以产生或处理多条记录； 主语言是面向记录的，一组主变量一次只能存放一条记录； 仅使用主变量并不能完全满足SQL语句向应用程序输出数据的要求。 2.创建游标及使用游标的步骤？ 习题1 一、单项选择题 1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) 5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 习题一 一、填空题 1. 算法具有有穷性、确定性、可行性、输入和输出五大特征。 2. 数据结构的内容包括以下三个方面：数据元素、数据关系和运算集合。 3. 数据结构的存储结构分为顺序、链式、索引、散列。 4. 评价算法性能的标准主要从算法执行时间和空间两方面考虑。 5. 在线性结构、树形结构和图状结构中，数据元素之间分别存在着1对1 、1对多和多对多关系。 二、分析题 2.设n为整数，分析下列程序段中，用*标明的语句的语句频度及时间复杂度。（1）for(n =1;n<=10;n++) *s=s+n; (2) for(i =1;i<=n;i++) *s=s+n; (3) for(i =1;i<=n;i++) for(j=1;j<=n;j++) *s=s+n (4) for(i =1;i<=n;i++) for(j=1;j<=i ;j++) *s=s+n; （5）for(i =1;i<=n;i++) for(j=1;j<=n;j++) { c[i][j]=0; for(k=1;k<=n;k++) *c[i][j]=c[i][j]+a[i][k]*b[k][j]; } 习题二 3.填空题 1.在顺序表中，逻辑上相邻的元素，其物理位置上一定相邻。 2.在单链表中，逻辑上相邻的元素，其物理位置上不一定相邻。 3.设单链表中，指针p指向结点s，若要删除s之后的结点（若存在），则需修改指针的操作为P=s->next;s->next=s->next->next;free(p); 。 4.在一个长度为n的顺序表中，如果要删除第i个元素，需移动n-i+1 个元素。 二、选择题 1.某线性表中最常用的操作是存取序号为i的元素和在最后进插入和删除运算，则采用（C ）存储方式的时间性能最好。 A.双向链表 B.双向顺环链表 C.顺序表 D.单向顺环链表 2.在一个单链表中，已知q结点是p结点的前驱结点，若在p和q之间插入s结点，则需执行（ C ）。 A.s->next=p->next;p->next=s B.p->next=s->next;s->next=p C.q->next=s;s->next=p D.p->next=s;s->next=q 一、选择题 1设有关系模式W(C,P,S,G,T,R),其中各属性的含义是:C 课程,P 教师, S 学生,G 成绩,T 时间,R 教室,根据语义有如下数据依赖集: D={C->P ,( S,C )->G , ( T , R)->C , (T , P)-> R,( T,S )->R} 关系模式W的一个关键字是( ) A (S ,C ) B ( T, R) C) (T ,P ) D) (T ,S ) 2 设有关系模式W（C，P，S，G，T，R），其中中各属性的 含义是：C课程，P教师，S学生。G成绩，T时间，R教室，根据主义有如下依据赖集：K={C→P，（S，C）→G，（T，R ）→C，（T，P）→R，（T，S）→R} 关系模式W的规范化程序最高达到（） A 1NF B 2NF C 3NF D BCNF 3规范化理论中分解（）主要消除其中多余的数据相关性。A关系运算 B 内模式 C外模式 D 视图 4现有职工关系W（工号，姓名，工程，定额），其中每一个工号（职工可能有同名）， 每个职工有一个工程，每个工程有一个定额，则关系W已达到（） A 1NF B2NF C3NF D4NF 5现有职工关系W（工号，姓名，工程，定额），其中每一 个职工有一个工号（职工可能有同名），每个职工有一个工程，每个工程有一个定额，则关系W已达到（） A1NF B2NF C3NF D4NF 6规范化理论是关系数据库进行逻辑设计的理论依据,根据这个理论，关系数据库中的关系必须满足：其每一属性都是（） A、互不相关的 B、不可分解的 C、长度可变的 D、互相关联的 7、在一个关系R中，若每个数据项都是不可再分割的，那 么关系R 一定属于（） A、1NF B、2NF C、3NF D、BCNF 8、根所关系数据库规范化理论，关系数据库的关系要满足 1NF，下面“部门”关系中，因（）属性而使它不满足1NF。 A、部门号 B、部门名 C、部门成员 D、 部门总经理 9、设有关系模式R（S，D，M）。其函数依赖集F={S->D， D->M}，则关系R的规范化程序至多达到（） A、1NF B、2NF C、3NF D、BCNF 10、下列关于函数依赖的叙述中，（）是不正确的 A、由X->Y,X->Z,有X->YZ B\由XY->Z,有 X->Z,Y->Z C、由X->Y,WY->Z,有xw->z D、由X->Y,Y->Z,有 第一章概论 一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作（研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作） 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。（线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素，有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继）（链表、栈、队列、数组、串） A. 图 B. 树 C. 广义表（线性表的推广） D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i 6、算法是（D ）。为了解决某一问题而规定的一个有限长的操作序列 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（B ）和运算等的学科。（关系和操作） A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（ A ）。 i=s=0; while(s 栈和队列 3.1 单项选择题 1. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是。 A. edcba B. decba C. dceab D. abcde 2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为。 A. i B. n=i C. n-i+1 D. 不确定 3. 栈结构通常采用的两种存储结构是。 A.顺序存储结构和链式存储结构 B. 散列方式和索引方式 C. 链表存储结构和数组 D. 线性存储结构和非线性存储结构 4. 判定一个顺序栈ST（最多元素为m0）为空的条件是。 A. top !=0 B. top= =0 C. top !=m0 D. top= =m0-1 5. 判定一个顺序栈ST（最多元素为m0）为栈满的条件是。 A. top！=0 B. top= =0 C. top！=m0 D.top= =m0-1 6. 栈的特点是 B ，队列的特点是 A 。 A. 先进先出 B. 先进后出 7. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行。 (不带空的头结点) A. HS—＞next=s; B. s—＞next= HS—＞next; HS—＞next=s; C. s—＞next= HS; HS=s; D. s—＞next= HS; HS= HS—＞next; 8. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行。(不带空的头结点) A. x=HS; HS= HS—＞next; B. x=HS—＞data; C. HS= HS—＞next; x=HS—＞data; D. x=HS—＞data; HS= HS—＞next; 9. 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是。 A. 4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D. 3，2，4，1 10. 判定一个循环队列QU（最多元素为m0）为空的条件是。 A. rear - front= =m0 B. rear-front-1= =m0 C. front= = rear D. front= = rear+1 11. 判定一个循环队列QU（最多元素为m0, m0= =Maxsize-1）为满队列的条件是。 A. ((rear- front)+ Maxsize)% Maxsize = =m0 B. rear-front-1= =m0 C. front= =rear D. front= = rear+1 12. 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是。 A. (rear-front+m)%m B. rear-front+1 《数据结构》程序填空复习题 说明：本文档中涉及到的算法并非本书的全部，有些可根据此处的情况自行看书和作业题，黑色为综合练习上的题目，红色为我另增加的题，这些空的选择是根据我个人的经验来决定的并不能完全代表中央电大的出卷老师，因此一定不能有肯定就考这些题目的想法。不能放弃其他内容的复习，切记！！！ 一、线性表 1.设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。 #define NULL 0 void main( ) {NODE a,b,c,d,*head,*p; a.data=6; b.data=10; c.data=16; d.data=4; /*d是尾结点*/ head= （1）; a.next=&b; b.next=&c; c.next=&d; （2）; /*以上结束建表过程*/ p=head; /*p为工作指针，准备输出链表*/ do {printf(“%d\n”, （3）); （4）; }while( （5）); } 答案： （1）&a （2）d next=NULL （3）p->data （4）p=p->next （5）p!=NULL 2. 以下函数在head为头指针的具有头结点的单向链表中删除第i个结点， struct node { int data; struct node *next; }; typedef struct node NODE int delete(NODE *head,int i ) { NODE *p,*q; int j; q=head; j=0; while((q!=NULL)&&( ___(1)_____)) { ___(2)_____; j++; } if(q==NULL) return(0); p= ___(3)_____; ___(4)_____=p->next; free(___(5)_____); return(1); } 答案： （1）j 数据结构练习题及参考答案 《数据结构》练习题 一、解答题（共50分） 1、（8分）假设用于通讯的电文字符集及其出现的频率如下表所 请为这8个字符设计哈夫曼编码，并画出其哈夫曼树，计算 WPL。 2.（8分）若一棵二叉树中序遍历和后序遍历序列分别为： DBEHGAFIC和DHGEBIFCA。试画出这棵二叉树，并写出其 先序遍历和层序遍历序列。 3.（16分）以下无向网络以邻接表为存储结构（假设邻接表的 顶点表按字母a、b、c、d、e、f、g、h的顺序依次存储，邻接表 的边表结点按顶点的下标由小到大链接）。请画出其邻接表，并 写出从顶点f出发，分别进行深度和广度优先遍历的序列，写出用Prime方法从顶点c 开始产生最小生成树的边的序列。 4.（8分）已知键值序列为(44，39，67，25，52，59，43，84，54，58，15，26，12，73，92，69)，取填充因子α=0.8，采用线性探查法处理冲突，试构造散列表。 ⒌（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81)，用希尔排序方法进行排序，d1=5,d2=3,d3=1,则第二趟的排序结果是（）。 ⒍（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81) ，用堆（大根堆）排序方法进 行排序，第一趟的排序结果是（）。 二、完善程序（共20分，每空2分） 1.假设一组递减有序的原始数据存储在数组r中，存放元素的下标下限为low,下标上限为high,以下是在数组中查找数值为k的折半查找算法。请填空完善程序。 int BinSearch(int r[ ], int low,int high,int k) { int l,h,m; l= low; h= high; while ( ⑴) { m= ⑵; if (k < r[m]) ⑶; else if (k > r[m]) ⑷; else return m; } return 0; } 2. 以下程序功能是将数组r中，从下标first到end之间的元素进行快速排序的分区。请填空，完善程序。 int Partition(int r[ ], int first, int end) { int i,j,t; i=first; j=end; //初始化 while ( ⑸) { while (i 数据库作业题目 作业一：ER 设计 题目一：用ER 图可以表达下列哪些数据完整性约束，不能表达哪些约束？能表达的给出ER 图。 1. 每门课选课人数不能低于10个，不能高于100个 答：不能表达约束 2. 课程名是唯一的 3. 不能供应不存在的零件 4. 性别只能为男或女 答：不能表达约束 5. 每个学生都必须得选课 6. 学生可以参加多个社团，但所参加的社团的活动时间必须不同 答：不能表达约束 7. 学生可以参加多个项目，参加不同的项目其指导老师也不同 课 课供 供 零 供应 零件 零件 零件 学 零 选 学 姓课课程课程 题目二：解答以下问题 1. 列举聚集、弱实体、细化/泛化的实用例子，并用ER 图表示出来。 聚集：客户签订合同与采购产品之间是聚集关系 弱实体：下图中教科书属于弱实体 学 项 老 参 指 细化/泛化：家俱与（桌子、椅子）属于细化/泛化关系 2.E1(a1, a2, a3)E2(a3, a4)E3(a5, a6)E4(a3, a5, a7)，其中带下划线的属性标识为所在关系模式的主码。试画出相应的E-R图，使得可以从该E-R图推导出上述关系模式。 E-R图如下： 家 桌椅 名厂 编编 IS 题目三：考虑设计一个关系数据库，它要存储以下信息： ●教师有教工号、教工名、职称；项目有项目号、项目名称、项目类型、 起始年份、截至时间、资助额；学生有学号、学生名、年龄、学位。 ●学生分为本科生和研究生，老师按职称可以分为讲师、副教授、教授， 副教授以上职称的可以作为研究生的导师。 ●一个教工可以负责多个项目；每个项目只能有一个负责人；一个老师可 以参与多个项目；一个本科生只能参与一个项目，一个研究生学生可以 参与多个项目；一个项目可以有多个学生和老师参与；学生参与项目时 必须（如果改为可以呢？）有一个老师作为他的指导老师。 E-R图如下： 题目四：下面是一张采购订单的票据，根据上面列出的信息，给出其实体联系模型。 数据结构习题 一、名词解释 1. 数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、 算法、时间复杂度、空间复杂度。 2. 线性表、顺序表、单链表、双向链表、循环链表、双向循环链表、三个概念的区别：头 指针、头结点、首元结点（第1个元素结点）。 3. 栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。 4. 树、叶子结点、结点的度、树的度、树的高（深）度、二叉树、遍历、满二叉树、完全二叉树、哈夫曼树、WPL哈夫曼编码。 5. 图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量）、 （最小）生成树、邻接矩阵、邻接表、DFS BFSO 6. 查找表、关键字、静态查找、动态查找、ASL、顺序查找、折半查找、分块查找、二叉排序树。 7. 排序、内（外）排序、稳定性、插入（直接、希尔），交换（起泡、快速），选择（直接、堆），2 路归并。 一、填空题 1. 数据结构是研究数据的 _逻辑结构_和—物理结构_ ,并在这种结构上定义相关的运算，设计实 现这些运算的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为—时间复杂度和空间复杂度—。 2. 数据的基本单位是数据元素，数据的最小单位是数据项。 3. 算法是对特定问题求解—步骤___的一种描述，是指令的有限序列。 4. 一个算法的时间复杂度为（3n3+2n — 7）,其数量级表示为_0 （ n3） __。 5. 一个算法具有5个特性：_确定性、—可行性_、_有穷性_、输入和输出。 6. 算法性能的分析和度量，可以从算法的时间复杂度一和—空间复杂度—来评价算法的优劣。 7. 数据的逻辑结构包括集合结构、_线性结构 _、—树形结构_和_图型结构—四种类型。 8. 数据结构在计算机中的表示称为数据的物理结构，它可以采用 _顺序存储_ 或_链式存储_ 两种存储方法。 9. 线性表有两种存储结构，分别为_顺序存储 _ 和___________ 链式存储_。 10. 链式存储的特点是利用指针—来表示数据元素之间的逻辑关系。 11. 若频繁地对线性表进行插入和删除操作，该线性表宜采用链式存储—存储结构。 12. 线性表中的数据元素之间具有 _一对一_的线性关系，除第一个和最后一个元素外，其他数据元素有且只有 一个_直接后继和直接前趋。 13. 在一个单链表中 P所指结点之后插入一个S所指结点时，应执行 s->next=_ p->next ___________ 和 p->next=_ S ________ 的操作。开放大学数据结构2020年考试必备填空题
数据库设计综合练习题及答案
数据结构复习题目和答案
数据结构复习题及答案
2020数据库作业题
数据结构习题及参考答案 .
数据结构习题
数据库练习题
数据结构试题答案
数据结构复习题
《数据结构》程序填空复习题
数据结构练习题及
数据库作业题目
数据结构复习题及答案
相关主题
文本预览