数据结构导论作业一

第六章树和二叉树
6.45 编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
6.46 编写复制一棵二叉树的非递归算法。
6.59 编写算法完成下列操作：无重复地输出以孩子兄弟链表存储的树T中所有的边（这里的边是指树T本身的分支，而不是孩子兄弟链表所形成的二叉树的分支）。输出的形式为（k1, k2）, ..., (ki, kj), ..., 其中，ki和kj为树结点中的结点标识。
1.20试编写算法求一元多项式 的值Pn(x0)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为ai（i=0, 1,…, n）、x0和n，输出为Pn(x0)。
第二章线性表
2.11设顺序表va中的数据元素非递减有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
注：根据同学们的要求，将作业量从六道题减少到三道题，希望同学们能及时完成。
第五章数组和广义表
5.21 假设稀疏矩阵A和B均以三元组顺序表作为存储结构。试写出矩阵相加的算法，另设三元组C存放结果矩阵。
5.26 试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。
5.33 试编写递归算法，输出广义表中所有原子项及其所在的层次。
第十二章 文件
12.10假设某个有3000张床位的旅店需建立一个便于管理的文件,每个记录是一个旅客的身份和投宿情况。其中旅客身份证号(15位十进制数字)可作为主关键字，此外还需建立按姓名、投宿日期、从哪来等次关键字项索引。请为此文件确定一种组织方式(如:主文件如何组织,各次关键字项索引如何建立等
第十章 排序
10.23 试以L.r[k+1]作为监视哨改写直接插入排序算法。其中，L.r[1...k]为待排记录且k<MAXSIZE。

一、选择题1.在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行。

A．q一）next＝p一）next；p一）next＝q；B．p一）next＝q一）next；q＝p；C．q一）next＝p一）next；p一）next＝q；D．p一）next＝q一）next； q一）next＝p；2. 在一个顺序队列中，队首指针指向队首元素的位置：A．前一个 B．后一个 C．当前3. 下列数据组织形式中，（）的结点按逻辑关系依次排列形成一个“锁链”。

A.集合B.树形结构C.线性结构D.图状结构4. 数据结构可以形式化地定义为（S，△），其中S指某种逻辑结构，△是指（）A.S上的算法B.S的存储结构C.在S上的一个基本运算集D.在S上的所有数据元素5. 下列说法正确的是（）A.线性表的逻辑顺序与存储顺序总是一致的B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续C.线性表的线性存储结构优于链式存储结构D.每种数据结构都具有插入、删除和查找三种基本运算6. 设非空单链表的数据域为data，指针域为next，指针p指向单链表中第i个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为第i个结点，下列算法段能正确完成上述要求的是（）A.s->next=p->next;p->next=s；B.p->next=s;s->next=p->next；C.s->next=p->next;p->next=s;交换p->data和s->data；D.p=s;s->next=p；7. 将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点（）A.无左、右孩子B.有左孩子，无右孩子C.有右孩子，无左孩子D.有左、右孩子8. 采用线性探测法解决冲突问题，所产生的一系列后继散列地址（）A.必须大于等于原散列地址B.必须小于等于原散列地址C.可以大于或小于但不能等于原散列地址D.地址大小没有具体限制9. 用快速排序方法对包含有n个关键字的序列进行排序，最坏情况下执行的时间复杂度为（）A.O(n)B.O(log2n)C.O(nlog2n)D.O(n2)10. 下列数据结构中，( )不都是线性结构。

数据结构（本）形考作业指导作业1参考答案一、单项选择题1．C 2．D 3．B 4．C 5．D 6．C 7．B 8．C 9．A 10．B11．C 12．D 13．C 14．A 15．B 16．C 17．C 18．B 19．B 20．D二、填空题1．n-i+1 2．n-i3．集合线性结构树形结构图状结构4．物理结构存储结构5．线性结构非线性结构6．有穷性确定性可形性有零个或多个输入有一个或多个输出7．图状结构8．树形结构9．线性结构10．n-1 O(n) 11．s->next=p->next; 12．head13．q->next=p->next; 14．p->next=head; 15．单链表16．顺序存储链式存储17．存储结构18．两个直接后继直接前驱尾结点头结点19．头结点的指针指向第一个结点的指针20．链式链表三、问答题1．简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。

数据在计算机中的存储表示称为数据的存储结构。

可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。

尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。

采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。

2．解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。

答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。

优点：一般情况下，存储密度大，存储空间利用率高。

缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。

《数据结构导论》课程考核形式：闭卷考试需用时间：100分钟层次：专科班级：计应专朗沃姓名：学号：1．在数据结构中，与所使用的计算机无关的是（）。

A.存储结构B.物理结构C.物理和存储结构D.逻辑结构2．线性表采用链式存储结构时，其地址是（）。

A.必须是连续的B.一定是不连续的C.部分地址必须是连续的D.连续与否均可以3．在下列链表中不能从当前结点出发访问到其余各结点的是（）。

A.单链表B.单循环链表C.双向链表D.双向循环链表4．设一个栈的进栈序列是 a，b，c，d，进栈的过程中可以出栈，不可能的出栈序列是（）A.d，c，b，aB.c，d，b，aC.d，c，a，bD.a，b，c，d 5．设循环队列中数组的下标是0～N-1，其头尾指针分别为f 和r ，则其元素个数为（）A. r-fB.r-f-1C.(r-f)%N+1D.(r-f+N)%N6．广义表((a),a)的表头和表尾分别是：A. a, ((a))B. (a), (a)C. b, (a)D. ((a)), a 7．对稀疏矩阵采用压缩存储，其缺点之一是（）。

A.无法判断矩阵有多少行和多少列B.无法根据行列号查找某个矩阵元素C.无法根据行列号计算矩阵元素的存储地址D.使矩阵元素之间的逻辑关系更加复杂8．以下说法错误的是（）。

A.一般在哈夫曼树中，权值越大的叶子离根结点越近B.哈夫曼树中没有度数为 1 的分支结点C.若初始森林中共有 n 棵二叉树，最终求得的哈夫曼树中共有 2n-1个结点D.若初始森林中共有 n 棵二叉树，进行 2n-1 次合并后才能剩下最终的哈夫曼树9．任何一个无向连通图（）最小生成树。

A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在10．树最适合用来表示（）：A. 有序数据元素B. 无序数据元素C. 元素之间具有分支层次关系的数据D. 元素之间无联系的数据二、填空题（本大题共9小题，每空2 分，共20分）1．在双向链表中，每个结点包含两个指针域，一个指向__ __结点，另一个指向_ ___结点。

数据结构导论试题12.1-02.10（答案03.10、04.10、05.10、09.10、10.10、11.1、11.10）浙江省2001年10月自学考试数据结构导论试题课程代码：02142一、单项选择题(在每小题的四个备选答案中选出一个正确答案，并将其号码填在题干的括号内。

每小题1分，共14分)1.算法分析的目的是( )A.找出数据结构的合理性B.研究算法中的输入/输出关系C.分析算法的效率以求改进D.分析算法的易读性2.在需要经常查找结点的前驱与后继的场合中，使用( )比较合适。

A.单链表B.双链表C.顺序表D.循环链表3.下面关于线性表的叙述中，错误的为( )A.顺序表使用一维数组实现的线性表B.顺序表必须占用一片连续的存储单元C.顺序表的空间利用率高于链表D.在链表中，每个结点只有一个链域4.带头结点的单链表head为空的判断条件是( )A. head=NILB. head↑.next=NILC. head↑.next=headD. head<>NIL5.队列通常采用两种存储结构是( )A.顺序存储结构和链表存储结构B.散列方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构6.按照二叉树的定义，具有3个结点的二叉树有( )A.3B.4C.5D.67.二叉树的结构如下图所示，其中序遍历的序列为( )A.a,b,d,g,c,e,f,hB.d,g,b,a,e,c,h,fC.g,d,b,e,h,f,c,aD.a,b,c,d,e,f,g,h8.深度为5的二叉树至多有( )个结点。

A.16B.32C.31D.109.对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组的大小为( )A.nB.n+1C.n-1D.n+边数10.在一个具有n个顶点的无向图中，要连通全部顶点至少需要( )条边。

A.nB.n+1C.n-1D.n/211.静态查找表与动态查找表二者的根本差别在于( )A.它们的逻辑结构不一样B.施加在其上的操作不同C.所包含的数据元素的类型不一样D.存储实现不一样12.散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。

全国自学考试数据结构导论试题及答案4套第一套试题一、选择题（每题4分，共40分）1. 下列哪个数据结构是一种非线性结构？A. 数组B. 栈C. 队列D. 树2. 下列哪种算法不适用于解决排序问题？A. 冒泡排序B. 快速排序C. 深度优先搜索D. 归并排序3. 在数据结构中，堆的底层实现通常采用哪种数据结构？A. 数组B. 栈C. 链表D. 队列4. 下列哪个选项是描述图结构的准确说法？A. 图结构是一种线性结构B. 图结构由节点和指向节点的边构成C. 图结构不能存储数据D. 图结构不支持插入和删除操作5. 下列哪个排序算法具有最坏时间复杂度为O(nlogn)？A. 冒泡排序B. 插入排序C. 选择排序D. 希尔排序二、填空题（每题4分，共40分）1. 在二叉树中，每个节点最多有____个子节点。

2. 图的两个顶点之间的路径长度是指连接这两个顶点所需的____数。

3. 链表是一种____结构。

4. 快速排序算法的核心思想是____。

5. 栈和队列都属于线性结构，其主要区别在于____操作的限制。

三、简答题（每题10分，共30分）1. 请简要描述栈的特点以及栈的应用场景。

2. 请简要介绍图的基本概念，并说明图的应用领域。

3. 请解释递归算法的原理，并给出一个使用递归算法解决问题的例子。

四、编程题（共30分）请使用任意编程语言实现一个简单的栈数据结构，并编写测试代码进行验证。

第二套试题一、选择题（每题4分，共40分）1. 在二叉搜索树中，中序遍历的结果是____。

A. 升序排列B. 降序排列C. 随机排序D. 不确定的排序2. 在哈希表结构中，解决冲突问题的常用方法是____。

A. 线性探测B. 链地址法C. 开放地址法D. 扩容法3. AVL树是一种____。

A. 二叉搜索树B. 哈希表C. B树D. 红黑树4. 以下哪个算法不是用于解决查找问题？A. 二分查找B. 深度优先搜索C. 广度优先搜索D. 哈希查找5. 以下哪个数据结构不支持随机访问元素？A. 数组B. 栈C. 链表D. 哈希表二、填空题（每题4分，共40分）1. 在二叉树中，每个节点最多有____个子节点。

1、章节作业第一章概论1．设计算法在整型数组A[n]中查找值为K的元素，若找到，则输出其位置i(0≤i≤n-1)，否则输出-1作为标志，并分析算法的时间复杂度。

int search (int A[],int n,int k){ int i;i=0;while (i<=n-1)if (A[i]!=k) i++;else break;if (i<=n-1) return I;else return -1；}当查找成功时，A[i]与k比较次数≤n；当查找不成功时，A[i]与k比较n次，所以，算法时间复杂度T(n)=O(n)。

2．写出计算方阵A[n][n]与B[n][n]乘积C[n][n]的算法，分析算法的时间复杂度。

void matrixmultiply (int A[][n],int B[][n],int C[][n],int n){ int I,j;for (i=0;i<n;i++)for (j=0;j<n;j++){ C[i][j]=0;for (k=0;k<n;k++)C[i][j]+=A[i][j]*B[k][j];}}以方阵阶数n作为输出规模。

可知第二层循环中的第一条赋值语句共执行n2次，第三层循环体中的乘法和赋值语句共执行n3次，所以此算法的计算量为n3+n2，算法时间复杂T(n)=O(n3)第二章线性表1．设带头结点的单链表的结点结构如下：struct node { DataType data；struct node *next；} Node， *LinkList；试编写一个函数int count(LinkList head，DataType x)统计单链表中数据域为x的结点个数。

int count(LinkList head,DataType x){LinkList p=head->next;Int m=0;while (p!=NULL){ if(p->data==x) m++;p=p->next;}return m;}2．试分别以顺序表和带头结点的单链表作存储结构，各写一个实现线性表的就地(即使用尽可能少的附加空间)逆置的算法，在原表的存储空间内将线性表(a1，a2，…，a n)逆置为(a n，a n-1，…，a1)。

全国自考《数据结构导论》真题及答案解析-卷面总分：86分答题时间：60分钟试卷题量：43题一、单选题（共30题，共60分）1.在顺序表中查找第i个元素，时间效率最高的算法的时间复杂度为（）A.O(1)B.O(√n)C.O(log2n)D.O(n)正确答案：A您的答案：本题解析：暂无解析2.树形结构中，度为0的结点称为（）A.树根B.叶子C.路径D.二叉树正确答案：B您的答案：本题解析：暂无解析3.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={}，则图G的拓扑序列是（）A.V1,V3,V4,V6,V2,V5,V7B.V1,V3,V2,V6,V4,V5,V7C.V1,V3,V4,V5,V2,V6,V7D.V1,V2,V5,V3,V4,V6,V7正确答案：A您的答案：本题解析：暂无解析4.有关图中路径的定义，表述正确的是（）A.路径是顶点和相邻顶点偶对构成的边所形成的序列B.路径是不同顶点所形成的序列C.路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合正确答案：A您的答案：本题解析：暂无解析5.串的长度是指（）A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数正确答案：B您的答案：本题解析：暂无解析6.组成数据的基本单位是（）A.数据项B.数据类型C.数据元素D.数据变量正确答案：C您的答案：本题解析：暂无解析7.程序段的时间复杂度为（）A.O（1）=B.O（n）C.O（n2D.O(n3)正确答案：B您的答案：本题解析：暂无解析8.与串的逻辑结构不同的数据结构是（）A.线性表B.栈C.队列D.树正确答案：D您的答案：本题解析：暂无解析9.二叉树的第i(i≥1)层上所拥有的结点个数最多为（）A.B.2iC.D.正确答案：C您的答案：本题解析：暂无解析10.设单链表中指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为（）A.p-&gt;next=p-&gt;next-&gt;nextB.p=p-&gt;nextC.p=p-&gt;next-&gt;nextD.p-&gt;next=p正确答案：A您的答案：本题解析：暂无解析11.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（）A.堆排序B.冒泡排序C.直接插入排序D.快速排序正确答案：C您的答案：本题解析：暂无解析12.设字符串S1=″ABCDEFG″，S2=″PQRST″，则运算S=CONCAT(SUBSTR(S1,2,LENGTH(S2)),SUBSTR(S1,LENGTH(S2),2))后S的结果为()A.″BCQR″B.″BCDEF″C.″BCDEFG″D.″BCDEFEF″正确答案：D您的答案：本题解析：暂无解析13.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并且A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则使其平衡的调整方法为()A.LL型B.LR型C.RL型D.RR型正确答案：B您的答案：本题解析：暂无解析14.如果结点A有3个兄弟结点，而且B为A的双亲，则B的度为（）A.1B.3C.4D.5正确答案：C您的答案：本题解析：15.数据表A中每个元素距其最终位置较近，则最省时间的排序算法是（）A.堆排序B.插入排序C.直接选择排序D.快速排序正确答案：B您的答案：本题解析：暂无解析16.在表长为n的顺序表上做插入运算，平均要移动的结点数为（）A.n/4B.n/3C.n/2D.n正确答案：C您的答案：本题解析：暂无解析17.顺序表中有19个元素，第一个元素的地址为200，且每个元素占一个字节，则第14个元素的存储地址为()A.212B.213C.214D.215正确答案：B您的答案：本题解析：暂无解析18.由顶点V1，V2，V3构成的图的邻接矩阵为，则该图中顶点V1的出度为(C)A.0B.1C.2D.3正确答案：C您的答案：本题解析：暂无解析19.元素的进栈次序为A，B，C，D，E，则退栈中不可能的序列是（）A.A，B，C，D，EB.B，C，D，E，AC.E，A，B，C，DD.E，D，C，B，A正确答案：C本题解析：暂无解析20.由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）A.23B.37C.44D.46正确答案：C您的答案：本题解析：暂无解析21.在已知尾指针的单循环链表中，插入一个新结点使之成为首结点，其算法的时间复杂度为（）A.O（1）B.（log2n）C.O（n）D.O(n2)正确答案：A您的答案：本题解析：暂无解析22.已知一个有序表为(13，18，24，35，47，50，62，83，90，115，134)，当二分查找值为90的元素时，查找成功时需比较的次数为（）A.1B.2C.3D.4正确答案：B您的答案：本题解析：暂无解析23.在查找顺序表各结点概率相等的情况下，顺序按值查找某个元素的算法时间复杂度为（）A.O(1)B.O(n)C.O(√n)D.O(log2n)正确答案：B您的答案：本题解析：暂无解析24.下列各项键值序列中不是堆的为（）A.{5，23，16，68，94，72，71，73}B.{5，16，23，68，94，72，71，73}C.{5，23，16，73，94，72，71，68}D.{5，23，16，68，73，71，72，94}正确答案：C您的答案：本题解析：暂无解析25.在线性表的下列存储结构中进行插入、删除运算，花费时间最多的是（）A.单链表B.双链表C.顺序表D.单循环链表正确答案：C您的答案：本题解析：暂无解析26.在栈中进行插入和删除操作的一端称为（）A.栈顶B.栈底C.任意位置D.指定位置正确答案：A您的答案：本题解析：暂无解析27.用n个值构造一棵二叉排序树，它的最大高度为A..n/2B.nC.√nD.log2n正确答案：B您的答案：本题解析：暂无解析28.冒泡排序的时间复杂度是（）A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)正确答案：A您的答案：本题解析：暂无解析29.设无向图的邻接表如题14图所示，则该图的边数为（）A.4B.5C.10D.20正确答案：B您的答案：本题解析：暂无解析30.带表头结点链队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）A.front==rearB.front!=NULLC.rear!=NULLD.front==NULL正确答案：A您的答案：本题解析：暂无解析二、填空题（共13题，共26分）31.下列程序段的时间复杂度为________正确答案：O(n)您的答案：32.数据的逻辑结构被分为集合结构、________、树形结构和图状结构4种。

数据结构导论自考题-1(总分100, 做题时间90分钟)一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的。

1.算法的便于阅读和理解的特性称为( )A．正确性B．易读性C．健壮性D．时空性SSS_SIMPLE_SINA B C D分值: 2答案:B[解析] 本题主要考查的知识点是算法的易读性。

[要点透析] 算法的易读性是指易于阅读、理解和交流，便于调试、修改和扩充。

2.给定有n个元素，建立一个有序单链表的时间复杂度为( ) A．O(1) B．O(n)n)C．O(n2) D．O(nlog2SSS_SIMPLE_SINA B C D分值: 2答案:B[解析] 本题主要考查的知识点是建立有序单链表的时间复杂度。

[要点透析] 在创建有序单链表的过程中，每一次将新结点链接入有序表的时间分两部分，其一是查找插入的合适位置，其二是将元素插入。

后者的时间复杂度是常量O(1)，而前者的时间复杂度由比较元素的次数决定，由于元素比较的次数是不确定的，只能取平均比较次数，为(n+1)/2，故其时间复杂度为O(n)。

由线性累加规则可得整个算法的时间复杂度为：O(n)。

3.在双链表中某结点(已知其地址)前插入一新结点，其时间复杂度为( ) A．O(n) B．O(1)C．O(n2) D．O(logn)2SSS_SIMPLE_SINA B C D分值: 2答案:B4.顺序栈s中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为( )A．s.elem[top]=e;s.top=s.top+1;B．s.elem[top+1]=e;s.top=s.top+1;C．s.top=s.top+1;s.elem[top+1]=e;D．s.top=s.top+1;s.elem[top]=e;SSS_SIMPLE_SINA B C D分值: 2答案:D5.一个数组的第一个元素的存储地址是100，每个元素占2个存储单元，则第5个元素的存储地址是( )A．110 B．108C．100 D．120SSS_SIMPLE_SINA B C D分值: 2答案:B6.已知某完全二叉树采用顺序存储结构，结点数据的存放顺序依次为A、B、C、D、E、F、G、H，该完全二叉树的后序遍历序列为( )A．HDBEFCGA B．HDEBFGCAC．DHEBFGACA D．DEHBFGCASSS_SIMPLE_SINA B C D分值: 2答案:B[解析] 本题主要考查的知识点是完全二叉树的后序遍历。

数据结构导论自考试题及答案一、选择题（每题2分，共10分）1. 在数据结构中，队列是一种（）。

A. 集合B. 线性表C. 树D. 图答案：B2. 对于长度为n的线性表，在最坏情况下，查找一个元素需要比较的次数是（）。

A. nB. n/2C. 1D. 0答案：A3. 在二叉树的遍历中，先序遍历的顺序是（）。

A. 根-左-右B. 左-根-右C. 右-根-左D. 根-右-左答案：A4. 哈希表的冲突可以通过（）来解决。

A. 链接法B. 排序C. 折半查找D. 二分查找答案：A5. 一个具有n个顶点的无向图至少有多少条边？A. nB. n-1C. n(n-1)/2D. 0答案：D二、填空题（每题3分，共15分）6. 在顺序存储的堆栈中，判断栈为空的条件是______。

答案：栈顶指针等于-1或者指向第一个元素的前一个位置7. 快速排序的平均时间复杂度是______。

答案：O(n log n)8. 一个长度为n的链表，删除已知第i个位置元素的时间复杂度是______。

答案：O(n)9. 一个平衡二叉树的查找、插入和删除操作的时间复杂度是______。

答案：O(log n)10. 用邻接表表示图时，对于有n个顶点的无向图，邻接表中所有链表的节点数之和至少是______。

答案：n三、简答题（每题10分，共20分）11. 什么是递归？请举例说明递归算法的工作原理。

答案：递归是一种在程序中调用自身的方法，它允许函数解决问题的更小版本，直到达到一个简单的基本情况。

例如，计算n的阶乘可以使用递归算法：```function factorial(n) {if (n <= 1) {return 1;} else {return n * factorial(n - 1);}}```12. 请简述图的遍历算法有哪些，并说明它们的特点。

答案：图的遍历算法主要有深度优先搜索（DFS）和广度优先搜索（BFS）。

DFS使用栈（可以是显式的栈或者隐式的递归调用栈）来逐层深入地访问图中的顶点，直到找到一个未被访问的邻接顶点。

填空题1.运算的实现是指完成该运算功能的（程序）。

运算实现的核心是处理步骤的规定，即（算法设计）。

2.从某种意义上说，数据、数据元素和数据项实际反映了数据组织的三个层次，数据可由若干个（据元素）成，数据元素可由若干个（数据项）构成。

3.在一个长度为n的顺序表中删除第I个元素(1<=I<=n)时，需平均向前移动((n-1)/2)个元素。

4. 对计算机专业人员来说必须完成的两项基本任务是：数据表示和数据处理。

5. 数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式。

6. 存储结构是逻辑结构的存储实现，即数据按逻辑结构规定的形式在计算机存储器中存放的方法。

7. 凡能被计算机存储、加工的对象统称为数据。

8. 数据元素是数据的基本单位。

9. 在有些场合下，数据项又称为字段或域，它是数据的不可分割的最小标识单位。

10. 从某种意义上说，数据、数据元素、和数据项实际反映了数据组织的三个层次，数据可由若干个数据元素构成，而数据元素又可由若按个数据项组成。

11. 在任何问题中，数据元素都不是孤立的，他们之间存在某种关系，通常称这种关系为结构。

12. 所谓逻辑关系是指数据元素之间的关联方式或称“邻接关系”。

数据元素之间逻辑关系的整体称为逻辑结构。

数据的逻辑结构就是数据的组织形式。

13. 在数据结构中，数据的逻辑结构分为集合、线性结构、树形结构、图状结构等四类。

14. 一般的，运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。

15. 根据操作的效果，可将运算分成以下两种基本类型：加工型运算和引用型运算。

16. 存储实现的基本目标是建立数据的机内表示。

17. 存储结构的主要部分是数据元素之间关联方式的表示。

通常，存储结点之间可以有四种关联方式，称为四种基本存储方式：顺序存储方式、链式存储方式、索引存储方式和散列存储方式。

18. 算法分为：运行终止的程序可执行部分、伪语言算法、非形式算法。

第1次作业一、单项选择题(本大题共60分，共20小题，每小题3分)1.在长度为n的顺序表求最小值的时间复杂度为()。

A.0(1)B.0 (n)C.O (n2)D.O (logn)2.顺序表中数据元索的存取方式是()oA.顺序存取B.链式存取C.随机存取D.散列存取3.对于一个具有n个结点的单链表，，在给定值为x的结点后插入一个新结点的平均时间复杂度为()。

A.0(0)B.0(1)C.O(n)D.0(n2)4.在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有和同的()。

A.行号B.列号C.元素值D.地址5.数组A [0.. 5] [0.. 5]的每个元素占5个字节，将其以列为主序存储在起始地址为1000的内存单元中，则元索A [5] [5]的地址是( )。

A.1175B.1180C.1205D.12106.下而程序段的时间复杂度是()。

i = 0； while (i<=n) i二i * 3；A.0 (3n)B.0(log3n)C.0 (n3)D.0(n2)7.假设顺序表中第一个数据元索的存储地址是1000,每个元索占用4个字节，则第7个元索的存储地址是()。

A.1024C.1004D.10078・设栈S和队列Q的初始状态为空，元素el, e2, e3, e4, e5和e6依次通过栈S, —个元素出栈后即进队列Q,若6个元素出队的序列是e2, e4,e3, e6, e5, el则栈S的容量至少应该是（）。

A.B.4C.3D.29.判断带头结点的循环单链表L屮只冇一个结点的条件是（）。

A.L二二NULLB.L->next->next==LD.L->next==NULL10.下而关于算法说法错误的是（）。

A.算法最终必须rti计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错谋的11.用单链表表示的链队列中，队头在链表的（）位置。

全国自考数据结构导论（数组、矩阵和广义表）模拟试卷1一、单项选择题1 常对数组进行的两种基本操作是______。

（A）建立与删除（B）索引与修改（C）查找与修改（D）查找2 设有一个8阶的对称矩阵A，采用压缩存储方式，以行序为主序存储，每个元素占用一个存储单元，基址为100，则A63的地址为_________。

（A）118（B）124（C）151（D）1603 已知数组A[1…6，2…8]在内存中以行序为主序存放，且每个元素占两个存储单元，则计算元素A[i，j]地址的公式为_______。

（A）LOC(A[i，j])=LOC(A[1，2])+[(i一1)*7+(j一2)]*2（B）LOC(A[i，j])=LOC(A[1，2])+[(j一2)*6+(i一1)]*2（C）LOC(A[i，j])=LOC(A[1，2])+(i*8+j)*2（D）LOC(A[i，j])=LOC(A[1，2])+(j*6+i)*24 二维数组A的每个元素是由6个字符组成的串，其行下标i=0，1，…，8，列下标j=1，2，…，10，且每个字符占一个字节。

若A以行序为主序存放，元素A[8，5]的起始地址与当A以列序为主序存放时的元素_______的起始地址相同。

（A）A[7，8]（B）A[6，5]（C）A[0，7]（D）A[3，10]5 对稀疏矩阵进行压缩存储的目的是________。

（A）降低运算的时间复杂度（B）节省存储空间（C）便于存储（D）便于进行矩阵运算6 以下有关广义表说法中不正确的是_______。

（A）广义表的表头总是一个原子（B）广义表的表尾总是一个广义表（C）广义表的元素可以是单个元素（D）广义表的元素可以是一个子表7 广义表L=(a，(b，(c)，d)，(()，e))的长度为________。

（A）∞（B）6（C）4（D）38 广义表L=(a)，则表尾为_________。

（A）a（B）(())（C）空表（D）(a)9 已知广义表L=((a，b，c)，a，(x，y，z))，从L表中取出原子项y的运算是_________。

综合试题一参考答案：一、单项选择题1.B2.B3.B4.D5.D6.D7.B8.C9.D 10.A11.B 12.C 13.A 14.C 15.D二、填空题16．线性结构图状结构 17．O(n2)18．顺序实现链接实现 19．顺序存储结构链式存储结构 20． 2i-1 2k-1 21．-1、O、122．右 23．稀疏图24．nm／2 25．散列文件索引文件26．外排序 27．循环链表28．O(log2n)三、应用题29．解：首先统计每个字符出现的次数，有8个字符一共22次I:5，R:2，H:3，S:5，T:3，O:2，C:1，Y:l然后8个字符对应8个叶子结点，根据出现次数，每次找两个最小的结点合并成一个结点，逐次把森林连成一棵二叉树。

30. 解30 22 25 18 40 12 34 4022 25 18 30 12 34 40 4022 18 25 12 30 34 40 4018 22 12 25 30 34 40 4018 12 22 25 30 34 40 4012 18 22 25 30 34 40 4012 18 22 25 30 34 40 4031．解后根序列46532132．解struct node *lcopy(struct node *P){struct node *head=0，*tail=O；while(p){struct node *t=malloc(sizeof(struct node))；t->data=p->data；t->next=O；if(tail)tail->next=t；tail=t；P=P->next；if(head==O)head=t；}return head；}33．解四、算法设计题34．解因为当front==rear时，不知道是空还是满。

改进设计，可以在结构中添加一个整数变量，用以记录当前队列中元素个数。

typedef struct{DataType data[maxsize]；int front，rear；int count；//记录当前队列中的元素个数}可以从count判断是满还是空，如果满了则不能加入队列元素，如果空了则不能移除队列元素，其他时候和以前的操作一样。

数据结构导论真题分类整理详细第一章概述真题16.下列程序段的时间复杂度为____________。

for(i=1；i for(j=1；j for(k=1；k s=i+j+k；17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____________。

16.下列程序段的时间复杂度为________。

i=0；s=0；while{ i++；s=s+i；} 17.数据的逻辑结构被分为集合结构、_____、树形结构和图状结构4种。

1.数据的不可分割的最小标识单位是A.数据项 B.数据记录 C.数据元素 D.数据变量 2. for for c ［i］［j］=0；for for for c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；上列程序的时间复杂度为(m+n×t)(m+n+t)(m×n×t) (m×t+n) 16.在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、_____和散列存储方式等四种。

17.作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为______。

1.从逻辑上可以把数据结构分为 A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 2.关于算法的描述，不正确的是 A.算法最终必须计算机程序实现 B.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 C.健壮的算法不会因非法的输入数据而出现莫名其妙的状态 D.算法的优劣与算法描述语言无关16.在任何问题中，数据元素都不是孤立的，它们之间总存在某种关系，通常称这种关系为_____。

17.存储结点之间通常有四种基本存储方式，即顺序存储方式、索引存储方式、_____和散列存储方式。

1.在数据结构中，数据的基本单位是( ) A.数据项 B.数据元素 C.数据对象 D.数据文件1 2. k=1; for for A［i］［j］=k++；上述程序段的时间复杂度为( )16.数据的逻辑结构通常包括集合、线性结构、____________和图状结构。

数据结构导论1一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1.下述文件中适合于磁带存储的是（）A.顺序文件B.索引文件C.散列文件D.多关键字文件2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（）A.acbedB.becabC.deabcD.cedba3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( )A.n-1B.nC.n+1D.n+24.在一个图中，所有顶点的度数之和与图的边数的比是( )A.1∶2B.1∶1C.2∶1D.4∶15.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( )A.O(1)B.O(1og2n)C.O(n)D.O(n2)6.下述几种排序方法中，要求内存量最大的是( )A.插入排序B.快速排序C.归并排序D.选择排序7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( )A.n-1B.nC.n+1D.n(n-1)／28.对线性表进行二分查找时，要求线性表必须( )A.以顺序方式存储B.以链式方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( )A.O(1)B.O(n)C.O(nlog2n)D.O(n2)10.当利用大小为n的数组顺序存储一个队列时，该队列的最大容量为( )A.n-2B.n-1C.nD.n+111.有关插入排序的叙述，错误的．．．是( )A.插入排序在最坏情况下需要O(n2)时间B.插入排序在最佳情况可在O(n)时间内完成C.插入排序平均需要O(nlog2n)时间D.插入排序的空间复杂度为O(1)12.有关树的叙述正确的是( )A.每一个内部结点至少有一个兄弟B.每一个叶结点均有父结点C.有的树没有子树D.每个树至少有一个根结点与一个叶结点。