西安交通大学大数据结构复习资料

西交11秋学期《数据结构》考试复习题数据结构-学习指南一、单项选择题1. 算法指的是（）A.计算机程序B.解决问题的计算方法C.排序算法D.解决问题的有限运算序列2.线性表采用链式存储时，结点的存储地址（）A.必须是不连续的B.连续与否均可C.必须是连续的D.和头结点的存储地址相连续3.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点4.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B.头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改5.以下数据结构中哪一个是非线性结构？( d )A. 队列B. 栈C. 线性表D. 二叉树6.二叉树的第k层的结点数最多为( )A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为( )A.nB.n/2C.(n+1)/2D.(n-1)/29.在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q 与p之间插入一个s 所指的结点,则执行( )。

A.s→link=p→link; p→link=s;B.p→link=s; s→link=q;C.p→link=s→link; s→link=p;D.q →link=s; s→link =p;10.栈的插入和删除操作在（）进行。

A.栈顶B.栈底C.任意位置D.指定位置11. 组成数据的基本单位是（）。

A.数据项B.数据类型C.数据元素D.数据变量12．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（）。

数据结构复习资料(亲自整理)1、链表是一种存储数据的链式结构，每个数据之间都是相关联的。

2、线性结构是一个有序数据元素的集合，包括线性表、栈、队列、双队列、数组和串。

3、树是由n（n>=1）个有限节点组成一个具有层次关系的集合，而二叉树是每个结点最多有两个子树的有序树。

二叉树与树的主要差别在于，二叉树结点的最大度数为2，而树中结点的最大度数没有限制；二叉树的结点有左、右之分，而树的结点无左、右之分。

4、堆是一种可以被看做一棵树的数组对象，总是满足某个节点的值总是不大于或不小于其父节点的值，且堆总是一棵完全二叉树。

5、二叉排序树是一种满足以下递归定义的二叉树：若左子树非空，则左子树所有节点的值均小于它的根节点；若右子树非空，则右子树所有节点的值均大于于它的根节点；左右子树也分别为二叉排序树。

1、在已知前序遍历和中序遍历的情况下，可以通过画树的方法求得后序遍历。

具体步骤如下：首先根据前序遍历的特点，确定根节点；然后观察中序遍历，将左子树和右子树分别确定下来；接着对左子树和右子树分别进行递归，直到遍历完所有节点，最后得到后序遍历。

2、树和二叉树之间可以相互转换。

将树转换为二叉树的方法是：对于每个节点，将其第一个孩子作为其左孩子，将其兄弟作为其右孩子。

将二叉树转换为树的方法是：对于每个节点，将其右孩子作为其兄弟。

3、二叉树线索化是将二叉树中的空指针指向该节点在中序遍历中的前驱或后继节点的过程。

在线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是1.4、邻接表是图的一种链式存储结构，用于表示图中每个节点的邻居节点。

每个节点都有一个链表，存储着与该节点相邻的节点。

邻接表是一种图的存储结构，对于每个顶点建立一个单链表，单链表中的结点表示依附于该顶点的边（对于有向图是以该顶点为尾的弧）。

邻接表中的表结点和头结点分别表示边和顶点，包含信息如下：表结点adjvex（邻接点）。

nextarc（指向下一个表结点）（权值等信息）；头结点data（顶点信息）和firstarc（指向第一个表结点）。

习题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(‎) ‎C.O(n‎)D‎.O( )‎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.1‎953 ‎C.19‎64 ‎D.196‎89. ‎数据结构只‎是研究数据‎的逻辑结构‎和物理结构‎，这种观点‎（）。

31842-2019年西安交通大学814数据结构真题回忆814.数据结构。

选择五个。

忘了-大题avIl的题告诉11个数然后进行排序求平均长度二大题哈希表公共溢出区告诉12个数然后求平均长度三(1) 写图的邻接表结构(2)对一个图进行dfs与bfs(3) prim算法四编程题将一个链表进行逆置求时间复杂空间复杂oS填空10个吧。

忘了问答题三个1、三个调度。

然后进程挂起是靠那个调度完成的为什么?2、3、忘了。

大题一(1) 用ru调度进行22个关键数的页面置换(2) 设计一个ru (用计数器和栈) 有标志位(我好像见过原题)二pv 100个学生50台计算机两个学生必须--组才能去申请一个电脑然后管理员才让他们进去。

然后上机操作操作完了要让老师检查。

然后管理员才让走。

计算机组成原理。

四道大题忘了第一道大题告诉16位指令15-11指令10-8是寻址方式7-5通用寄存器4-0是地址。

有000是一次间接寻址001 010011分布是寄存器间接寻址变址寻址相对寻址第一问指令数量寄存器数量。

还有多少种寻址方式第二问问各个寻址的范围第三问问一个指令的数据是多少。

那个画成2进制然后是相对寻址第二道大题。

10位阶补尾补各带一个符号位,第一问写正数负数的最大值最小值第二问写出x= (-23/32) *2^7与y= (23/32) *2^6第三问x+y=?第四问把第三问结果表示出来915[题型分布与分值]选择10*2判断5*2.填空5*2简答7道应该是15*2+16*1+7*4编程题15*2+10*1代码题1输入有限个xy。

xy代表二伟空间一个点，寻找-个最小矩形，包含所输入的所有点要求输出该矩形左下顶点和右上的顶点2.判断一个字符串是否是回文串(其中有空格,需要排除空格)，第一问递归解决。

第二问用栈解决3.-个无序序列，找出其中的逆序对,要求O(nlogn), 如果不能在这个时间复杂度下实现，自己写一个程序,声明其时间复杂度.大题第一个满k叉树的分支节点数为n其叶子结点满足(K-1)n+1数归法证明第二个是用队列的基本操作实现栈的push和pop后题, hash表, 10个数据，表长17,哈希函数H1(key) = key%17,冲突解决采用双重散列H2(key)= (key%7 ==0 ? 8:key%7),第一问画表，第二问求查找成功ASL还有个是.支撑树定义最小支撑树mst什么的，我不懂还有4个任务abcd,问分别用哪些数据类型可以解决，写出基本算法还有个相似二叉树算法填空题有广义表快排递归时间复杂度深度优先搜索邻接两种复杂度。

其他系统西安交通大学--数据结构所有答案3,栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。

,A 正确 B错误,答案是：A3,在使用后缀表表示实现计算器时用到一个栈的实例，其作用是暂存运算对象。

,A正确 B错误,答案是：A3,具有n个结点的完全二叉树的高度为┖log2n┘1。

,A正确 B错误,答案是：B3,为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。

,A正确 B错误,答案是：A3,闭散列法通常比开散列法时间效率更高。

,A正确 B错误,答案是：B3,一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。

,A 正确 B错误,答案是：B3,有向图的邻接表和逆邻接表中表结点的个数不一定相等。

,A正确 B错误,答案是：B3,对链表进行插入和删除操作时不必移动链表中结点。

,A正确 B错误,答案是：A3,希尔排序算法的时间复杂度为On2。

,A正确 B错误,答案是：B3,用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。

,A正确 B错误,答案是：B3,通常使用两个类来协同表示单链表，即链表的结点类和链表类。

,A正答案是：A3,顺序表用一维数组作为存储结构，因此顺序表是一维数组。

,A正确 B 错误,答案是：B3,二维数组是数组元素为一维数组的线性表，因此它是线性结构。

,A正确 B错误,答案是：B3,算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。

要想准确地计算总运算时间是不可行的。

,A正确 B错误,答案是：A3,堆是完全二叉树，完全二叉树不一定是堆。

（）,A正确 B错误,答案是：A3,顺序表查找指的是在顺序存储结构上进行查找。

（）,A正确 B错误,答案是：B3,入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。

,A正确 B错误,答案是：A3,中序遍历一棵二叉排序树可以得到一个有序的序列。

,A正确 B错误,答案是：A3,用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。

数据结构复习资料复习提纲知识要点归纳数据结构复习资料：复习提纲知识要点归纳一、数据结构概述1. 数据结构的定义和作用2. 常见的数据结构类型3. 数据结构与算法的关系二、线性结构1. 数组的概念及其特点2. 链表的概念及其分类3. 栈的定义和基本操作4. 队列的定义和基本操作三、树结构1. 树的基本概念及定义2. 二叉树的性质和遍历方式3. 平衡二叉树的概念及应用4. 堆的定义和基本操作四、图结构1. 图的基本概念及表示方法2. 图的遍历算法：深度优先搜索和广度优先搜索3. 最短路径算法及其应用4. 最小生成树算法及其应用五、查找与排序1. 查找算法的分类及其特点2. 顺序查找和二分查找算法3. 哈希查找算法及其应用4. 常见的排序算法：冒泡排序、插入排序、选择排序、归并排序、快速排序六、高级数据结构1. 图的高级算法：拓扑排序和关键路径2. 并查集的定义和操作3. 线段树的概念及其应用4. Trie树的概念及其应用七、应用案例1. 使用数据结构解决实际问题的案例介绍2. 如何选择适合的数据结构和算法八、复杂度分析1. 时间复杂度和空间复杂度的定义2. 如何进行复杂度分析3. 常见算法的复杂度比较九、常见问题及解决方法1. 数据结构相关的常见问题解答2. 如何优化算法的性能十、总结与展望1. 数据结构学习的重要性和难点2. 对未来数据结构的发展趋势的展望以上是数据结构复习资料的复习提纲知识要点归纳。

希望能够帮助你进行复习和回顾，加深对数据结构的理解和掌握。

在学习过程中，要注重理论与实践相结合，多进行编程练习和实际应用，提高数据结构的实际运用能力。

祝你复习顺利，取得好成绩！。

西安交通大学智慧树知到“计算机科学与技术”《数据结构》网课测试题答案（图片大小可自由调整）第1卷一.综合考核(共10题)1.字符串的长度是指()。

A.串中不同字符的个数B.串中不同字母的个数C.串中所含字符的个数D.串中不同数字的个数2.顺序查找法适用于存储结构为顺序或链接存储的线性表。

()A.错误B.正确3.下列程序段的时间复杂度为()。

I=0，s=0;while(s＜n){s=s+i;i++;}A.O(n1/2)B.O(n1/3)C.O(n)D.O(n2)4.线性表中的每个结点最多只有一个前驱和一个后继。

()A.错误B.正确5.有向图的邻接表和逆邻接表中表结点的个数不一定相等。

()A.错误B.正确6.磁带是顺序存取的外存储设备。

()A.错误B.正确7.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为()。

A.q=p->next;p->data=q->data;p->next=q->next;free(q)B.q=p->next;q->data=p->data;p->next=q->next;free(q)C.q=p->next;p->next=q->next;free(q)D.q=p->next;p->data=q->data;free(q)8.一个栈的输入序列为123...n，若输出序列的第一个元素是n，输出i(1A.不确定B.n-i+1C.iD.n-i9.图可以没有边，但不能没有顶点。

()A.错误B.正确10.分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。

()A.错误B.正确第1卷参考答案一.综合考核1.参考答案：C2.参考答案：B3.参考答案：A4.参考答案：B5.参考答案：A6.参考答案：B7.参考答案：A8.参考答案：B9.参考答案：B10.参考答案：B。

西安交通大学17年3月课程考试《数据结构》作业考核试题一、单选题（共30 道试题，共60 分。

）1. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）A. 存储结构B. 逻辑结构C. 算法D. 操作正确答案：B2. 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。

A. 8B. 7C. 6D. 5正确答案：B3. 利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（）。

A. O(n)B. O(nlog2n)C. O(n)D. O(1og2n)正确答案：C4. 栈的插入和删除操作在（）进行。

A. 栈顶B. 栈底C. 任意位置D. 指定位置正确答案：A5. 二路归并排序的时间复杂度为（）。

A. O(n)B. O(n)C. O(nlog2n)D. O(1og2n)正确答案：C6. 设某强连通图中有n个顶点，则该强连通图中至少有（）条边。

A. n(n-1)B. n+1C. nD. n(n+1)正确答案：C7. 设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为（）A. A[1]，A[2]，A[3]，A[4]B. A[1]，A[14]，A[7]，A[4]C. A[7]，A[3]，A[5]，A[4]D. A[7]，A[5]，A[3]，A[4]正确答案：C8. 下列各种排序算法中平均时间复杂度为O（n）是（）。

A. 快速排序B. 堆排序C. 归并排序D. 冒泡排序正确答案：D9. 如下陈述中正确的是（）A. 串是一种特殊的线性表B. 串的长度必须大于零C. 串中元素只能是字母D. 空串就是空白串正确答案：A10. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置（）？脚注(10)表示用10进制表示。

A. 688B. 678C. 692D. 696正确答案：C11. 适于对动态查找表进行高效率查找的组织结构是（）A. 有序表B. 分块有序表C. 三叉排序树D. 线性链表正确答案：C12. 设某完全无向图中有n个顶点，则该完全无向图中有（）条边。

西交《数据结构》（六）第六章树与二叉树两个二叉树相关的常见题目前记：这一章课件里主要讲了树和二叉树的属性和一些常用的操作。

下面针对二叉树的遍历举一个具体的例子，这个题目在等级考试或者面试中都经常出现，大家多思考一下。

一题目描述：已知二叉树前序遍历和中序遍历分别为：ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为？答案：DGEBHFCA解题思路：1)先序遍历的第一个结点是根结点，所以A是根；2)然后在中序遍历中找到A，（DBGE）A（CHF）；3)由中序遍历的定义知（DBGE）是左子树的中序遍历，（CHF）是右子树的中序遍历。

4)然后在先序遍历中把左子树和右子树划开，A（BDEG）（CHF），所以B是左子树根，C是右子树根。

5)然后继续在中序遍历中找到B和C，（（D）B（GE））A（C（HF））。

6)对于DBEG，B是根，D是左子树，EG是右子树的中序遍历，对于CHF，C是根，HF是右子树的中序遍历。

因为仍然有没划分完的部分，所以继续看先序。

7)对于BDEG，B是根已知，D是整个左子树已知，所以EG是右子树的先序遍历，E是右根，再对照中序可知G是E的左子树，CHF同理。

所以树的结构是A（B（D，E（G，）），C（，F（H，）））把它画成图，后序遍历就是DGEBHFCA总之先序序列是用来确定根结点，中序序列是用来划分出左右子树。

二题目：建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果[基本要求]从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。

[测试数据]ABC DE G F （其中表示空格字符）则输出结果为先序：ABCDEGF中序：CBEGDFA后序：CGBFDBAC语言描述的方法：//示例的是先序遍历，其它的可以在这个基础上改。

#include<>#include<>typedef struct tnode{ char data;struct tnode *lchild;struct tnode *rchild;}tnode;tnode *Tree_creat(tnode *t){ char ch;ch=getchar();if(ch==' ')t=NULL;else{if(!(t=(tnode *)malloc(sizeof(tnode))))printf("Error!");t->data=ch;//printf("[%c]",t->data);t->lchild=Tree_creat(t->lchild);t->rchild=Tree_creat(t->rchild);}return t;}void preorder(tnode *t){ if(t!=NULL){ printf("%c ",t->data);preorder(t->lchild);preorder(t->rchild);}}void main(){tnode *t=NULL;t=Tree_creat(t);preorder(t);}。

西安交大数据结构习题及答案西安交大数据结构习题及答案1：栈和队列1.1 栈1.1.1 基本概念栈是一种后进先出（Last-In-First-Out, LIFO）的数据结构，即最后进入的元素最先被访问。

1.1.2 基本操作- push(x): 元素x入栈- pop(): 弹出栈顶元素- top(): 返回栈顶元素- isEmpty(): 判断栈是否为空1.2 队列1.2.1 基本概念队列是一种先进先出（First-In-First-Out, FIFO）的数据结构，即最先进入的元素最先被访问。

1.2.2 基本操作- enqueue(x): 元素x入队- dequeue(): 移除队首元素- front(): 返回队首元素- rear(): 返回队尾元素- isEmpty(): 判断队列是否为空2：链表2.1 单链表2.1.1 基本概念单链表是一种线性结构，每个节点含有数据和指向下一个节点的指针。

2.1.2 基本操作- 初始化链表- 在链表头插入节点- 在链表尾插入节点- 在指定位置插入节点- 删除节点- 查找节点- 遍历链表2.2 双向链表2.2.1 基本概念双向链表是一种线性结构，每个节点含有数据、指向前一个节点的指针和指向后一个节点的指针。

2.2.2 基本操作- 初始化双向链表- 在链表头插入节点- 在链表尾插入节点- 在指定位置插入节点- 删除节点- 查找节点- 遍历链表3：树3.1 二叉树3.1.1 基本概念二叉树是一种数据结构，每个节点最多有两个子节点：左子节点和右子节点。

3.1.2 基本操作- 创建二叉树- 先序遍历- 中序遍历- 后序遍历- 层次遍历3.2 AVL树3.2.1 基本概念AVL树是一种自平衡的二叉搜索树，保证任意节点的左子树和右子树的高度差最多为1：3.2.2 基本操作- 插入节点- 删除节点- 查找节点- 遍历树4.1 图的表示4.1.1 邻接矩阵表示法4.1.2 邻接表表示法4.2 图的遍历4.2.1 深度优先搜索（DFS）4.2.2 广度优先搜索（BFS）4.3 最短路径算法4.3.1 Dijkstra算法4.3.2 Floyd-Warshall算法5：排序算法5.1 冒泡排序5.2 插入排序5.3 选择排序5.4 快速排序5.5 归并排序5.6 堆排序本文档涉及附件，请查看附件文件以获取更详细的信息。

西交《数据结构》（五）第五章数组和广义表1、什么是数组，有哪些基本操作？1）数组=(数据，顺序)。

数组在程序设计中，为了处理方便，把具有相同类型的若干变量按有序的形式组织起来。

这些按序排列的同类数据元素的集合称为数组。

在Ｃ语言中，数组属于构造数据类型。

一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。

因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。

2）基本操作4个(1)InitArray (＆A，n，bound1，…,boundn)建A 若维数n和各维长度合法，则构造相应的数组A，并返回OK(2)DestroyArray(＆A)删A 销毁数组A(3)Value(A，＆e，index1，…，indexn)取a A是n维数组，e为元素变量，随后是n 个下标值。

若各下标不超界，将e赋值为所指定的A的元素值，并返回OK(4)Assign(＆A，e，index1，…，indexn)a←e赋值A是n维数组，e为元素变量，随后是n个下标值。

若每个下标不超界，则将e的值赋给指定的A的元素，并返回OK2、什么是稀疏矩阵，如何存储？如果在矩阵中，多数的元素并没有数据，称此矩阵为稀疏矩阵（sparse matrix）。

矩阵在程序中常使用二维阵列表示，二维阵列的大小与使用的存储器空间成正比，如果多数的元素没有数据，则会造成存储器空间的浪费，为此，必须设计稀疏矩阵的阵列储存方式，利用较少的存储器空间储存完整的矩阵数据。

3、稀疏矩阵的优点。

稀疏矩阵的优点：稀疏矩阵的计算速度更快,因为M AT L A B只对非零元素进行操作,这是稀疏矩阵的一个突出的优点。

假设矩阵A,B中的矩阵一样.计算2*A需要一百万次的浮点运算,而计算2*B只需要2 0 0 0次浮点运算。

对于一个用二维数组存储的稀疏矩阵Amn,如果假设存储每个数组元素需要L个字节,那么存储整个矩阵需要m*n*L个字节.但是,这些存储空间的大部分存放的是0元素,从而造成大量的空间浪费.为了节省存储空间,可以只存储其中的非0元素.对于矩阵Amn的每个元素aij,知道其行号i和列号j就可以确定其位置.因此对于稀疏矩阵可以用一个结点来存储一个非0元素.该结点可以定义如下：[i,j,aij] 该结点由3个域组成,i:行号,j:列号;aij元素值.这样的结点被称为三元组结点。

西安交通大学智慧树知到“计算机科学与技术”《数据结构》网课测试题答案（图片大小可自由调整）第1卷一.综合考核(共10题)1.单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。

()A.错误B.正确2.设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列()存储方式最节省运算时间。

A.单向链表B.单向循环链表C.双向链表D.双向循环链表3.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为()。

A.O(n)B.O(nlog2n)C.O(1)D.O(n2)4.程序段如下：s=i=0;do{i=i+1;s=s+i;} while(i=n);其时间复杂度为()。

A.O(n)B.O(nlog2n)C.O(n2)D.O(n3/2)5.在B+树中查找和在B-树中查找的过程完全相同。

()A.错误B.正确6.快速排序是排序算法中平均性能最好的一种排序。

()A.错误B.正确7.设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X 的操作序列为()。

A.p->right=s;s->left=p;p->right->left=s;s->right=p->rightB.s->left=p;s->right=p->right;p->right=s;p->right->left=sC.p->right=s;p->right->left=s;s->left=p;s->right=p->rightD.s->left=p;s->right=p->right;p->right->left=s;p->right=s8.对一棵二叉排序树进行()遍历，可以得到该二叉树的多有结点按值从小到大排列的序列。

A.前序B.中序C.后序D.按层次9.磁带是顺序存取的外存储设备。

习题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.1946B.1953C.1964D.19689.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。

A.正确B.错误C.前半句对，后半句错D.前半句错，后半句对10.计算机内部数据处理的基本单位是（）。

A.数据B.数据元素C.数据项D.数据库二、填空题1.数据结构按逻辑结构可分为两大类，分别是______________和_________________。

2.数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。

2018数据结构总复习第一章概论1.1数据结构的定义和分类1.数据结构的定义数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。

2.数据结构包括的内容（1）逻辑结构：数据元素之间的逻辑关系。

（2）存储结构：数据元素及其关系在计算机存储器内的表示。

（3）操作：数据的运算（检索、排序、插入、删除、修改）。

1.2为什么学习数据结构1.学习数据结构的作用（1）计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。

（2）同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。

（3）程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。

而好的算法在很大程度上取决于描述实际问题的数据结构。

2.电话号码查询问题（1）要写出好的查找算法，取决于这张表的结构及存储方式。

（2）电话号码表的结构和存储方式决定了查找（算法）的效率。

1.3算法的概念和特点1.算法的概念和特点算法是由若干条指令组成的有穷序列，具有以下特点：（1）输入：具有0个或多个输入的外界量。

（2）输出：至少产生1个输出。

（3）有穷性：每一条指令的执行次数必须是有限的。

（4）确定性：每条指令的含义都必须明确，无二义性。

（5）可行性：每条指令的执行时间都是有限的。

2.算法与程序的区别（1）一个程序不一定满足有穷性，但算法一定。

（2）程序中的指令必须是机器可执行的，而算法无此限制。

（3）一个算法若用机器可执行的语言来描述，则它就是一个程序。

1.4算法分析1.时间复杂度算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。

记作T(n)=O(f(n))，称O(f(n)) 为算法的渐近时间复杂度，简称时间复杂度。

算法效率的度量，采用时间复杂度。

第一章绪论1、数据结构的主要研究内容①数据的逻辑结构--数据关系之间的逻辑关系②数据的存储结构--数据的逻辑结构在计算机中的表示2、数据逻辑结构的种类：集合、线性表、树和图的性质和特点。

❖集合结构中的元素是各自独立的，元素之间没有联系❖线性结构中的元素是一个接一个串联起来的，它有一个头元素和一个尾元素，其余为中间元素；每个中间元素既有前驱元素，又有后继元素❖在树结构中，树根结点只有后继结点，而没有前驱结点；除树根结点外，每个结点都有唯一一个前驱结点，又称为是父结点或双亲结点❖在图结构中，每个结点或称顶点都可以有任意多个前驱结点和任意多个后继结点。

❖树结构是图结构的特例，线性结构是树结构的特例。

为了区别于线性结构，时常把树结构和图结构称为非线性结构。

3、数据结构的二元组定义，能根据给出的二元组来判断数据的逻辑结构类型。

❖集合结构中的元素集合K和二元关系R分别为：K={A，B，C，D，E，F，G}R={ }❖线性结构中的元素集合K和二元关系R分别为：K={A，B，C，D，E，F，G}R={<A,B>，<B,C>，<C,D>，<D,E>，<E,F>，<F,G>}❖树结构中的元素集合K和二元关系R分别为：K={A，B，C，D，E，F，G}R={<A,B>，<A,C>，<A,D>，<C,E>，<C,F>，<D,G>}❖图结构中的元素集合K和二元关系R分别为：K={A，B，C，D，E，F，G}R={<A,B>，<A,C>，<A,G>，<D,G>，<D,F>，<C,E>，<C,F>，<G,F>}4、了解数据的几种存储结构〔物理结构〕与它们各自的性质和特点。

〔1〕顺序的方法: 将逻辑上相邻的元素存储到物理上相邻的存储位置. 常用于线性的数据结构.〔2〕链式结构：给结点附加一个指针字段, 指出其后继节点的位置, 即存放结点的存储单元分为两局部:〔3〕散列〔hashing) 结构：散列的方法是用结点的关键字值直接计算出结点的存储地址。