下载文档原格式
浙江大学远程教育学院《数据结构与算法》课程离线作业姓名：陈翠学号：713009014001年级：2013秋学习中心：金华学习中心—————————————————————————————一、填空题：（【序号，章，节】。
）【1，1，2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。
【2，1，2】为了最快地存取数据元素，物理结构宜采用顺序存储结构。
【3，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为顺序存储结构___，链式存储结构___。
【4，1，3】度量算法效率可通过时间复杂度___来进行。
【5，1，3】设n 为正整数，下面程序段中前置以记号@的语句的频度是n(n+1)/2 。
for (i=0; i<n; i++){for (j=0; j<n; j++)if (i+j==n-1)@ a[i][j]=0;}【6，1，3】设n 为正整数，试确定下列各程序段中前置以记号@的语句的频度:(1) i=1; k=0;while (i<=n-1){i++;@ k+=10 * i; // 语句的频度是_________n-1_______________。
}(2) k=0;1for (i=1; i<=n; i++){for (j=i; j<=n; j++)@ k++; // 语句的频度是_________n(n+1)/2________________。
}【7，3，2】线性表(a1，a2，…，a n)有两种存储结构：顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充：___顺序_ 存储密度较大；___顺序____存储利用率较高；___顺序____可以随机存取；__链式_____不可以随机存取；__链式____插入和删除操作比较方便。
【8，3，2】从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动n-i 个元素。
数据结构与算法(Python版)《数据结构》参考答案(A卷)引言概述：数据结构与算法是计算机科学中非常重要的基础知识，对于程序员来说，掌握好数据结构与算法对于编写高效、可靠的程序至关重要。
本文将以Python语言为基础，介绍《数据结构》参考答案(A卷)。
一、基础概念1.1 数据结构的定义与分类- 数据结构是指数据元素之间的关系和组织方式，常见的数据结构包括数组、链表、栈、队列、树、图等。
- 数据结构可分为线性结构和非线性结构，线性结构包括线性表、栈、队列等，非线性结构包括树、图等。
1.2 算法的概念与特性- 算法是解决特定问题的一系列步骤，它具有输入、输出、有穷性、确定性和可行性等特性。
- 算法的效率通常用时间复杂度和空间复杂度来衡量，时间复杂度表示算法执行所需的时间，空间复杂度表示算法执行所需的额外空间。
1.3 Python语言的特点与应用- Python是一种简洁、易读、易学的高级编程语言，它支持面向对象编程和函数式编程。
- Python在数据结构与算法领域有广泛的应用，它提供了丰富的内置数据结构和算法库，如列表、字典、集合、排序算法等。
二、常用数据结构2.1 数组- 数组是一种线性结构，它由相同类型的元素组成，通过索引来访问和操作元素。
- Python中的列表就是一种动态数组，它支持插入、删除、查找等操作，时间复杂度为O(1)。
2.2 链表- 链表也是一种线性结构，它由节点组成，每个节点包含数据和指向下一个节点的指针。
- Python中可以使用自定义类来实现链表，它支持插入、删除、查找等操作，时间复杂度为O(n)。
2.3 栈与队列- 栈是一种先进后出的数据结构，可以使用列表或者自定义类来实现。
- 队列是一种先进先出的数据结构，也可以使用列表或者自定义类来实现。
三、常用算法3.1 排序算法- 排序算法是对一组数据按照某种规则进行排序的算法，常见的排序算法有冒泡排序、插入排序、选择排序、快速排序等。
《数据结构与算法》作业参考答案说明：1、题号形式: 每题都以【sn，cha，sec】开头，sn表明本题的题目序号，每道题都有唯一的序号；cha表示内容所在的章；sec表示内容所在的节。
如:【17，2，1】表示序号17的题来自第2章第1节。
2、题型：1) 选择题：序号1-180题2) 是非题：序号181-220题3) 分析计算作图题：序号221-250题（选自《数据结构题集》—严蔚敏等编）3、内容取舍：根据本学期上课课件中的内容，未上课章节的练习可舍弃。
4、必做题或选做题：是非题和选择题（序号1-220）只要在上过课的章节中都是必做题，分析计算作图题（序号221-250）在每题后标出是必做题还是选做题，其中16个必做题14个选做题。
1) 选择题：序号1-180题序号参考答案1 BD2 D3 C4 A5 C6 D7 C8 D9 B10 D11 B12 D13 C14 C15 D16 A17 A18 A19 A20 A21 A22 D24 A25 B26 C27 C28 C29 B30 B31 B32 B33 B34 A35 A36 C37 D38 D39 B40 C41 B42 A43 D44 B45 D46 B47 C48 C49 B50 B51 A52 D53 D54 C55 A56 A57 C58 C59 C60 B61 A62 D64 B65 C66 B67 D68 D69 B70 A71 C72 B73 A74 D75 D76 B77 C78 C79 D80 B81 D82 C83 B84 A85 B86 C87 D88 B89 B90 B91 D92 C93 D94 A95 C96 C97 B98 A99 C 100 C 101 A 102 D 103 C105 C 106 D 107 C 108 B 109 B 110 D111 A 112 B 113 A 114 B 115 C 116 D 117 B 118 C 119 A 120 B121 A 122 A 123 C 124 C 125 B 126 B 127 B 128 C 129 C 130 B131 A 132 D 133 AB 134 D 135 C 136 C 137 B 138 A 139 B 140 B141 D 142 A 143 B145 A146 A147 C148 B149 C150 A151 B152 B153 C154 B155 A156 C157 C158 C159 A160 B161 C162 A163 A164 D165 B166 C167 D168 C169 C170 B171 B172 C173 B174 D175 C176 D177 B178 A179 A180 B2) 是非题：序号181-220题181 T182 T183 F184 T185 T186 F187 T188 T189 T190 T191 F192 T193 T194 F195 F196 T197 F198 T199 F200 T201 T202 T203 F204 T205 T206 F207 T208 T209 F210 T211 F212 T213 T214 F215 T216 T217 F218 T219 T220 F3) 分析计算作图题：序号221-250（选自《数据结构题集》—严蔚敏等编）【221，1，4】（选自《数据结构题集》1.8，选做题）设n为正整数，试确定下列各段程序中前置以记号@的语句的频度(语句的频度指的是该语句重复执行的次数)。
《数据结构与算法》课后答案课后习题解答判断题1．线性表的逻辑顺序与存储顺序总是一致的。
2．顺序存储的线性表可以按序号随机存取。
3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。
4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。
5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。
6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。
7．线性表的链式存储结构优于顺序存储结构。
8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。
9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。
10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
11．静态链表既有顺序存储的优点，又有动态链表的优点。
所以它存取表中第i个元素的时间与i无关。
12．线性表的特点是每个元素都有一个前驱和一个后继。
算法设计题1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。
试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。
【提示】直接用题目中所给定的数据结构，因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，然后插入x ，最后修改表示表长的变量。
int insert (datatype A,int *elenum,datatype x) elenum为表的最大下标*/ {if(*elenum==arrsize-1) return 0; 法插入*/ else {i=*elenum; while (i>=0 && A[i]>x) 边移动*/ {A[i+1]=A[i]; i--; } A[i+1]=x; /*找到的位置是/*边找位置/*表已满，无/*设插入位的下一位*/ (*elenum)++; return 1; } } 时间复杂度为O(n)。
数据结构与算法课后习题解答数据结构与算法课后习题解答第一章绪论（参考答案）1.3 (1) O(n)(2) (2) O(n)(3) (3) O(n)(4) (4) O(n1/2)(5) (5) 执行程序段的过程中，x,y值变化如下：循环次数x y0（初始）91 1001 92 1002 93 100。
9 100 10010 101 10011 9112。
20 9921 91 98。
30 101 9831 91 97到y=0时，要执行10*100次，可记为O（10*y）=O（n）数据结构与算法课后习题解答1.5 2100 , (2/3)n , log2n , n1/2 , n3/2 , (3/2)n , nlog2n , 2 n , n! , n n第二章线性表(参考答案)在以下习题解答中，假定使用如下类型定义：（1）顺序存储结构：#define ***** 1024typedef int ElemType;// 实际上，ElemTypetypedef struct{ ElemType data[*****];int last; // last}sequenlist;（2*next；}linklist;（3）链式存储结构（双链表）typedef struct node{ElemType data;struct node *prior,*next；数据结构与算法课后习题解答}dlinklist;（4）静态链表typedef struct{ElemType data;int next;}node;node sa[*****];2.1 la，往往简称为“链表la”。
是副产品）2.2 23voidelenum个元素，且递增有序，本算法将x插入到向量A中，并保持向量的{ int i=0,j;while (ielenum A[i]=x) i++; // 查找插入位置for (j= elenum-1;jj--) A[j+1]=A[j];// 向后移动元素A[i]=x; // 插入元素数据结构与算法课后习题解答} // 算法结束24void rightrotate(ElemType A[],int n,k)// 以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。
数据结构与算法(Python版)《数据结构》参考答案(A卷)数据结构与算法是计算机科学中非常重要的基础知识，它们在软件开辟中起着至关重要的作用。
在Python编程语言中，数据结构与算法同样扮演着重要的角色。
本文将介绍数据结构与算法在Python中的应用，匡助读者更好地理解和运用这些知识。
一、数据结构1.1 列表(List)Python中最常用的数据结构之一是列表，它可以存储任意类型的数据，并且支持增删改查等操作。
1.2 字典(Dictionary)字典是另一个常用的数据结构，它以键值对的形式存储数据，可以快速查找和修改数据。
1.3 集合(Set)集合是一种无序且不重复的数据结构，可以进行交集、并集、差集等操作，非常适合处理数学运算。
二、算法2.1 排序算法Python中有多种排序算法可供选择，如冒泡排序、快速排序、归并排序等，每种算法都有其适合的场景和特点。
2.2 查找算法查找算法用于在数据集中查找指定的元素，常见的查找算法有线性查找、二分查找等，可以提高查找效率。
2.3 图算法图算法是一类特殊的算法，用于解决图结构中的问题，如最短路径、最小生成树等，在网络分析和路由规划中有广泛应用。
三、应用实例3.1 数据处理数据结构与算法在数据处理中有着重要的应用，可以匡助我们高效地处理大量数据，如数据清洗、分析和建模等。
3.2 网络编程在网络编程中，我们时常需要使用数据结构与算法来处理网络数据包、路由信息等，确保网络通信的稳定和高效。
3.3 人工智能在人工智能领域，数据结构与算法也扮演着重要的角色，如机器学习算法中的数据预处理、特征选择等。
四、优化技巧4.1 空间复杂度优化在编写代码时，我们应该尽量减少空间复杂度，避免不必要的内存占用，提高程序的运行效率。
4.2 时间复杂度优化算法的时间复杂度直接影响程序的运行速度，我们可以通过选择合适的算法和数据结构来优化时间复杂度。
4.3 算法优化技巧除了选择合适的数据结构和算法外，我们还可以通过优化代码逻辑、减少循环嵌套等方式来提高程序的性能。
2.3 课后习题解答2.3.2 判断题1．线性表的逻辑顺序与存储顺序总是一致的。
（×）2．顺序存储的线性表可以按序号随机存取。
（√）3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。
（×）4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。
（√）5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。
（×）6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。
（√）7．线性表的链式存储结构优于顺序存储结构。
（×）8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。
（√）9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。
（√）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
（×）11．静态链表既有顺序存储的优点，又有动态链表的优点。
所以它存取表中第i个元素的时间与i无关。
（×）12．线性表的特点是每个元素都有一个前驱和一个后继。
（×）2.3.3 算法设计题1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。
试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。
【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x ，最后修改表示表长的变量。
int insert (datatype A[],int *elenum,datatype x) /*设elenum为表的最大下标*/ {if (*elenum==arrsize-1) return 0; /*表已满，无法插入*/else {i=*elenum;while (i>=0 && A[i]>x) /*边找位置边移动*/{A[i+1]=A[i];i--;}A[i+1]=x; /*找到的位置是插入位的下一位*/(*elenum)++;return 1; /*插入成功*/}}时间复杂度为O(n)。
第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
3．简述逻辑结构的四种基本关系并画出它们的关系图。
4．存储结构由哪两种基本的存储方法实现？5．选择题（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．树B．字符串C．队D．栈6．试分析下面各程序段的时间复杂度。
（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
《数据结构与算法》习题与答案（解答仅供参考）一、名词解释：1. 数据结构：数据结构是计算机存储、组织数据的方式，它不仅包括数据的逻辑结构（如线性结构、树形结构、图状结构等），还包括物理结构（如顺序存储、链式存储等）。
它是算法设计与分析的基础，对程序的效率和功能实现有直接影响。
2. 栈：栈是一种特殊的线性表，其操作遵循“后进先出”（Last In First Out, LIFO）原则。
在栈中，允许进行的操作主要有两种：压栈（Push），将元素添加到栈顶；弹栈（Pop），将栈顶元素移除。
3. 队列：队列是一种先进先出（First In First Out, FIFO）的数据结构，允许在其一端插入元素（称为入队），而在另一端删除元素（称为出队）。
常见的实现方式有顺序队列和循环队列。
4. 二叉排序树（又称二叉查找树）：二叉排序树是一种二叉树，其每个节点的左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。
这种特性使得能在O(log n)的时间复杂度内完成搜索、插入和删除操作。
5. 图：图是一种非线性数据结构，由顶点（Vertex）和边（Edge）组成，用于表示对象之间的多种关系。
根据边是否有方向，可分为有向图和无向图；根据是否存在环路，又可分为有环图和无环图。
二、填空题：1. 在一个长度为n的顺序表中，插入一个新元素平均需要移动______个元素。
答案：(n/2)2. 哈希表利用______函数来确定元素的存储位置，通过解决哈希冲突以达到快速查找的目的。
答案：哈希（Hash）3. ______是最小生成树的一种算法，采用贪心策略，每次都选择当前未加入生成树且连接两个未连通集合的最小权重边。
答案：Prim算法4. 在深度优先搜索（DFS）过程中，使用______数据结构来记录已经被访问过的顶点，防止重复访问。
答案：栈或标记数组5. 快速排序算法在最坏情况下的时间复杂度为______。
数据结构与算法(Python版)《数据结构》参考答案(A卷)引言概述：数据结构与算法是计算机科学中非常重要的概念，它们对于程序的性能和效率有着直接的影响。
本文将介绍数据结构与算法的基本概念和原理，并提供《数据结构》参考答案(A卷)的Python版实现。
一、数据结构的基本概念和分类1.1 线性结构- 线性结构是数据元素之间存在一对一的关系，常见的线性结构有数组、链表和栈等。
- 数组是一种连续存储的线性结构，可以通过下标直接访问元素，但插入和删除操作效率较低。
- 链表是一种离散存储的线性结构，通过指针将各个节点连接起来，插入和删除操作效率较高。
- 栈是一种特殊的线性结构，采用后进先出的原则，常用于递归、表达式求值等场景。
1.2 非线性结构- 非线性结构是数据元素之间存在一对多或者多对多的关系，常见的非线性结构有树和图等。
- 树是一种层次存储的非线性结构，由节点和边组成，常用于表示层次关系，如文件系统、二叉搜索树等。
- 图是一种任意存储的非线性结构，由顶点和边组成，常用于表示网络、社交关系等复杂关系。
1.3 常用数据结构的应用场景- 数组适合于随机访问和元素固定的场景，如矩阵运算、图象处理等。
- 链表适合于频繁插入和删除操作的场景，如LRU缓存、大整数运算等。
- 栈适合于递归和回溯等场景，如括号匹配、浏览器前进后退等。
- 树适合于层次关系的场景，如文件系统、数据库索引等。
- 图适合于复杂关系的场景，如社交网络、推荐系统等。
二、常用算法的基本原理和实现2.1 排序算法- 冒泡排序是一种简单的比较排序算法，通过相邻元素的比较和交换来实现排序。
- 快速排序是一种分治算法，通过选取一个基准元素将数组划分为两个子数组，并递归地对子数组进行排序。
- 归并排序是一种分治算法，通过将数组划分为两个子数组并分别排序，然后将两个有序子数组合并成一个有序数组。
2.2 查找算法- 顺序查找是一种简单的查找算法，通过逐个比较元素来查找目标元素。
浙江大学远程教育学院《数据结构与算法》课程离线作业姓名：陈翠学号：713009014001年级：2013秋学习中心：金华学习中心—————————————————————————————一、填空题：（【序号，章，节】。
）【1，1，2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。
【2，1，2】为了最快地存取数据元素，物理结构宜采用顺序存储结构。
【3，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为顺序存储结构___，链式存储结构___。
【4，1，3】度量算法效率可通过时间复杂度___来进行。
【5，1，3】设n 为正整数，下面程序段中前置以记号@的语句的频度是n(n+1)/2 。
for (i=0; i<n; i++){for (j=0; j<n; j++)if (i+j==n-1)@ a[i][j]=0;}【6，1，3】设n 为正整数，试确定下列各程序段中前置以记号@的语句的频度:(1) i=1; k=0;while (i<=n-1){i++;@ k+=10 * i; // 语句的频度是_________n-1_______________。
}(2) k=0;1for (i=1; i<=n; i++){for (j=i; j<=n; j++)@ k++; // 语句的频度是_________n(n+1)/2________________。
}【7，3，2】线性表(a1，a2，…，a n)有两种存储结构：顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充：___顺序_ 存储密度较大；___顺序____存储利用率较高；___顺序____可以随机存取；__链式_____不可以随机存取；__链式____插入和删除操作比较方便。
【8，3，2】从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动n-i 个元素。
【9，3，2】带头结点的单链表Head为空的条件是___ Head->next=NULL _ ______。
【10，3，2】在一个单链表中p所指结点(p所指不是最后结点)之后插入一个由指针s所指结点，应执行s->next=__ p->next ___;和p->next=___ s_ _____的操作。
【11，3，2】在一个单链表中删除p所指结点时，应执行以下操作：q= p->next;p->data= p->next->data;p->next= p->next->next _ ;free(q);【12，3，2】带头结点的单循环链表Head的判空条件是_ Head->next == Head ____；不带头结点的单循环链表的判空条件是_ Head == NULL ____。
【13，3，2】已知L是带表头结点的非空单链表, 且P结点既然不首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。
a. 删除P结点的直接前驱结点的语句序列是__10 12 8 11 4 14___。
b. 删除结点P的语句序列是__10 12 7 3 14______。
c. 删除尾元结点的语句序列是____9 11 3 14_____。
(1) P = P->next;(2) P->next = P;(3) P->next = P->next ->next;(4) P = P->next ->next;(5) while (P != NULL) P = P->next;(6) while (Q->next != NULL){P = Q; Q = Q->next};(7) while (P->next != Q) P = P->next;(8) while (P->next->next != Q) P = P->next;2(9) while (P->next->next != NULL) P = P->next;(10) Q = P;(11) Q = P->next;(12) P = L;(13) L = L->next;(14) free (Q);【14，3，3】对一个栈，给定输入的顺序是A、B、C，则全部不可能的输出序列有不可能得到的输出序列有CAB 。
【15，3，3】.在栈顶指针为HS的链栈中，判定栈空的条件是head->next==NULL。
【16，3，3】下列程序把十进制数转换为十六进制数，请填写合适的语句成分。
void conversion10_16(){ InitStack(&s);scanf(“%d”,&N);while(N){① ________Push(s, N%16)______ ;N = N/16;}while(!StackEmpty(s)){② _______ Pop(s, e)_ _______ ;if(e<=9)printf(“%d”,e);else printf(“%c”,e-10+’A’);}} /* conversion */【17，3，4】若用一个大小为6个元素的数组来实现循环队列，且当前rear=0和front=3。
当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是 2 和4 。
【18，3，4】堆栈和队列都是线性表, 堆栈是______后进先出_______的线性表, 而队列是____先进先出_______的线性表。
【19，3，4】若用一个大小为6个元素的数组来实现循环队列，且当前rear=0和front=3。
当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是2 和 4 。
【20，4，2】已知一棵树边的集合是{<a,d>,<d,c>,<d,j>,<e,a>,<f,g>,<d,b>,<g,h>,<g,i>,<e,f>}3。
那么根结点是 e ，结点b的双亲是 d ，结点a的子孙有bcdj ，树的深度是4 ，树的度是3 ，结点g在树的第 3 层。
【21，4，3】从概念上讲，树与二叉树是二种不同的数据结构，将树转化为二叉树的基本的目的是树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题。
【22，4，3】满三叉树的第i层的结点个数为3i-1，深度为h时该树中共有3 -1h结点。
【23，4，3】已知一棵完全二叉树有56个叶子结点，从上到下、从左到右对它的结点进行编号，根结点为1号。
则该完全二叉树总共结点有___111_____个；有__7__层；第91号结点的双亲结点是___45__号；第63号结点的左孩子结点是____32_____号。
【24，4，3】下列表示的图中，共有___5____个是树；有___3____个是二叉树；有__2____个是完全二叉树。
【25，4，4】n个结点的二叉排序树的最大深度是n ，最小深度为[log2n]+1。
【26，4，3】如果某二叉树的后序遍历序列是ABCDEFGHI，中序遍历序列是ACBIDFEHG4，则其先序遍历序列的第一个字母是 I ，最后一个字母是G。
【27，4，3】下列二叉树的中序遍历序列是_DBNGOAEC__;后序遍历序列是_____DNIGBECA________。
【28，5，4】设HASH表的大小为n (n=10), HASH函数为h(x)=x % 7,如果二次探测再散列方法Hi=(H(key)+di) mod 10 (di = 12,22,32,…,)解决冲突，在HASH表中依次插入关键字{1,14,55,20,84,27}以后，关键字1、20和27所在地址的下标分别是 1 、__7__和5 。
插入上述6个元素的平均比较次数是2 。
【29，6，3】设无权图G的邻接矩阵为A，若（vi,vj）属于图G的边集合，则对应元素A[i][j]等于 1 ，22、设无向图G的邻接矩阵为A，若A[i][j]等于0，则A[j][i]等于0 。
【30，6，3】若一个图用邻接矩阵表示，则删除从第i个顶点出发的所有边的方法是矩阵第 i 行全部置为零。
1【31，6，2】设一个图G={V,{A}},V={a,b,c,d,e,f},A={<a,b>,<b,e>,<a,e>,<c,a>,<e,d>,<d,f>,<f,c>}。
那么顶点e的入度是 2 ；出度是 1 ；通过顶点f的简单回路有 2 条；就连通性而言，该图是强连通图；它的强连通分量有 1 个；其生成树可能的最大深度是 5 。
【32，7，1】排序过程一般需经过两个基本操作，它们是比较和移动。
【33，7，2】在对一组关键字是（54,38,96,45,15,72,60,23,83）的记录进行直接插入排序时，当把第七个记录（关键字是60）插入到有序表时，为寻找插入位置需比较 3 次。
5【34，7，4】插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基数排序方法中，不稳定的排序方法有希尔排序、快速排序、堆排序。
67二、综合题（选自教材《数据结构》各章习题，采用word 文件格式上传）【1，1，3】试分析下面一段代码的时间复杂度：if ( A > B ){for ( i=0; i<N; i++ )for ( j=N*N; j>i; j-- )A += B;//A=A+B}else {for ( i=0; i<N*2; i++ )for ( j=N*2; j>i; j-- )A += B; //A=A+B}Answer ：if A>B 为真，则for 语句的外循环N 次，内循环为N （N-1）次，因此时间复杂度为O(N* N （N-1）)，也就是N 的三次方。
if A>B 为假，则for 语句的外循环2N 次，内循环为N 次，因此时间复杂度为O （2N*N ），也就是N 的平方。
【2，1，3】测试例1.3中秦九韶算法与直接法的效率差别。
令i x x f i i /1)(1001∑=+=，计算)1.1(f 的值。
利用clock()函数得到两种算法在同一机器上的运行时间。
Answer ：f(1.1)=137797.40625【3，1，3】 试分析最大子列和算法1.3的空间复杂度。
【4，1，3】试给出判断N是否为质数的)O的算法。
(NAnswer：int sushu(int N){int i;int flag=1;if (N==1) return false;//1既不是合数也不是质数if (N==2) return true;for (i=2;i<=sqrt(N);i++){if (N%i==0){flag=0break;}}return flag;}【5，2，2】请编写程序，输入整数n和a，输出S=a+aa+aaa+…＋aa…a(n个a)的结果。
