西安交通大学《数据结构》期末考试拓展学习(四)6

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

数据结构期末考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指（）。

A. 执行算法所需要的计算工作量B. 执行算法所需要的存储空间C. 执行算法所需要的时间D. 执行算法所需要的内存大小答案：A2. 线性表的顺序存储结构和链式存储结构相比，其优点是（）。

A. 插入和删除操作快B. 存储密度高C. 存储空间可以动态分配D. 存储空间利用率高答案：B3. 栈的基本运算中，不包括（）。

A. 入栈B. 出栈C. 取栈顶元素D. 排序答案：D4. 在二叉树的遍历中，先序遍历的顺序是（）。

A. 先根后子B. 先子后根C. 先左后右D. 先右后左答案：A5. 哈希表解决冲突的方法不包括（）。

A. 分离链接法B. 线性探测法C. 链地址法D. 二分查找法答案：D6. 一个图的邻接矩阵表示法中，若第i行第j列的元素为1，则表示（）。

A. 顶点i和顶点j之间有一条边B. 顶点i和顶点j之间没有边C. 顶点i和顶点j之间有n条边D. 顶点i和顶点j之间有m条边答案：A7. 在查找算法中，二分查找法适用于（）。

A. 线性表B. 哈希表C. 树形结构D. 图结构答案：A8. 快速排序算法的时间复杂度在最坏情况下是（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(2^n)答案：C9. 一个有n个顶点的无向图，其边数最多为（）。

A. nB. n(n-1)/2C. n(n+1)/2D. 2n答案：B10. 以下哪个不是排序算法（）。

A. 冒泡排序B. 选择排序C. 插入排序D. 归并排序答案：D二、填空题（每题2分，共20分）1. 在数据结构中，一个算法的空间复杂度是指算法执行过程中所需要的___________。

答案：存储空间2. 线性表的链式存储结构中，每个节点包含___________和___________。

答案：数据元素，指针3. 栈的特点是___________，___________。

【期末复习】数据结构期末综合练习及参考答案四（算法分析题）数据结构（本科）期末综合练习四（算法分析题）1. 指出算法的功能并求出其时间复杂度。

int fun(int n){int i =1,s=1;while(s< bdsfid="67" p=""><>return i;}功能为：时间复杂度为：2. 指出算法的功能并求出其时间复杂度。

void matrimult(int a[M][N], int b[N][L], int c[M][L]){ //M、N、L均为全局整型常量int i, j, k;for ( i = 0; i < M; i++ )for ( j = 0; j < L; j++ )c[i][j] = 0;for( i =0; i <m;i++)< bdsfid="79" p=""></m;i++)<>for(j=0;j<l;j++)< bdsfid="81" p=""></l;j++)<>for(k=0;k<n;k++)< bdsfid="83" p=""></n;k++)<>c[i][j]+=a[i][k]*b[k][j];}功能为：时间复杂性为：3. 针对如下算法，回答问题：若数组A[n] = {12, 24, 0, 38, 0, 0, 0, 0, 29, 0, 45, 0}, n = 12，给出算法执行后数组A[n]的状态。

templatevoid unknown ( T A[ ], int n ) {int free = 0;for ( int i = 0; i < n; i++ )if ( A[i] != 0 ) {if ( i != free ) {A[free] = A[i];A[i] = 0;}free++;}}算法执行的结果4. 设顺序表SeqList具有下列操作：int Length( ) const; //计算表长度并返回，若表为空则返回0T Remove( ); //删除当前表项并返回其值，置下一表项为当前表项T First( ); //取表中第一个表项的值并返回，并置为当前表项T Next( ); //取当前表项后继表项的值并返回，//并把此后继表项置为当前表项若顺序表中存放的数据为{29,38,47,16,95,64,73,83,51,10,0,26}，表的长度为12，参数值s=10, t=30，说明算法执行后顺序表的状态和长度的变化。

其他系统西安交通大学--数据结构所有答案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,用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。

2022年西安交通大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。

A.60B.66C.18000D.332、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-13、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。

A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V75、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。

A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

《数据结构》期末考试试卷试题及答案第一部分：选择题（每题2分，共20分）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. 堆7. 下面哪个数据结构用于实现最小树算法？A. 栈B. 队列C. 散列表D. 堆8. 下面哪个数据结构用于实现拓扑排序算法？A. 栈B. 队列C. 散列表D. 堆9. 下面哪个数据结构用于实现最短路径算法？A. 栈B. 队列C. 散列表D. 堆10. 下面哪个数据结构用于实现并查集算法？A. 栈B. 队列C. 散列表D. 堆第二部分：填空题（每题2分，共20分）1. 链表是一种______数据结构。

2. 二叉树的节点最多有______个子节点。

3. 堆是一种特殊的______。

4. 散列表的查找效率取决于______。

5. 图的遍历算法包括______和______。

6. 快速排序算法的平均时间复杂度为______。

7. 哈希表中的冲突解决方法有______和______。

8. 最小树算法包括______和______。

9. 最短路径算法包括______和______。

10. 并查集算法用于解决______问题。

第三部分：简答题（每题10分，共50分）1. 请简述栈和队列的区别。

2. 请简述二叉搜索树的特点。

3. 请简述哈希表的原理。

4. 请简述图的深度优先搜索算法。

5. 请简述最小树算法的原理。

第四部分：编程题（每题20分，共50分）1. 编写一个函数，实现链表的插入操作。

《数据结构》期末考试试卷试题及答案一、选择题（每题5分，共20分）1. 下列哪个不是线性结构？A. 栈B. 队列C. 图D. 数组2. 下列哪个不是栈的基本操作？A. 入栈B. 出栈C. 查找D. 判断栈空3. 下列哪个不是队列的基本操作？A. 入队B. 出队C. 查找D. 判断队列空4. 下列哪个不是图的基本概念？A. 顶点B. 边C. 路径D. 环二、填空题（每题5分，共20分）5. 栈是一种______结构的线性表，队列是一种______结构的线性表。

6. 图的顶点集记为V(G)，边集记为E(G)，则无向图G=(V(G),E(G))，有向图G=(______，______)。

7. 树的根结点的度为______，度为0的结点称为______。

8. 在二叉树中，一个结点的左子结点是指______的结点，右子结点是指______的结点。

三、简答题（每题10分，共30分）9. 简述线性表、栈、队列、图、树、二叉树的基本概念。

10. 简述二叉树的遍历方法。

11. 简述图的存储结构及其特点。

四、算法题（每题15分，共30分）12. 编写一个算法，实现栈的入栈操作。

13. 编写一个算法，实现队列的出队操作。

五、综合题（每题20分，共40分）14. 已知一个无向图G=(V,E)，其中V={1,2,3,4,5}，E={<1,2>,<1,3>,<2,4>,<3,4>,<4,5>}，画出图G，并给出图G的邻接矩阵。

15. 已知一个二叉树，其前序遍历序列为ABDCE，中序遍历序列为DBACE，请画出该二叉树，并给出其后序遍历序列。

答案部分一、选择题答案1. C2. C3. C4. D二、填空题答案5. 后进先出先进先出6. V(G),E(G)7. 0 叶结点8. 左孩子右孩子三、简答题答案9. （1）线性表：一个线性结构，其特点是数据元素之间存在一对一的线性关系。

西安交通大学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);}。

《数据结构》期末考试试题及答案一、选择题（每题2分，共20分）1. 下列哪种数据结构是线性结构？A. 栈B. 树C. 队列D. 图答案：A2. 在计算机科学中，什么是最基本的数据结构？A. 数组B. 链表C. 栈D. 树答案：C3. 下列哪种操作的时间复杂度是O(1)?A. 在链表中插入元素B. 在数组中查找元素C. 在树中删除节点D. 在图中寻找最短路径答案：B4. 下列哪种数据结构常常用于实现栈和队列？A. 数组B. 链表C. 树D. 图答案：A5. 下列哪种数据结构是有序的？A. 栈B. 队列C. 链表D. 图答案：C二、填空题（每题2分，共20分）1. 在数据结构中，栈是一种后进先出（____）的数据结构。

答案：线性表2. 队列是一种先进先出（____）的数据结构。

答案：线性表3. 链表是一种____数据结构，由一系列节点组成。

答案：非线性4. 二叉树是一种特殊的树，它的每个节点最多有两个____。

答案：子节点5. 哈希表是通过____函数将关键字映射到表中的位置来访问数据。

答案：哈希三、判断题（每题2分，共20分）1. 树是一种线性结构。

（）答案：错误2. 链表的插入和删除操作时间复杂度都是O(1)。

（）答案：错误3. 图是一种线性结构。

（）答案：错误4. 哈希表是一种基于顺序结构的的数据结构。

（）答案：错误5. 在数据结构中，时间复杂度O(n)表示算法随着输入规模的增加而线性增长。

（）答案：正确四、简答题（每题10分，共30分）1. 请简述栈和队列的特点和应用场景。

答案：栈是一种后进先出（LIFO）的数据结构，应用场景包括函数调用栈、表达式求值等。

队列是一种先进先出（FIFO）的数据结构，应用场景包括任务队列、缓冲区等。

2. 请简述链表的优缺点。

答案：链表的优点包括动态扩容、插入和删除操作时间复杂度为O(1)、可以方便地实现各种复杂数据结构。

缺点包括占用内存空间较大、不如数组支持随机访问。