数据结构与算法（C语⾔）——期末复习试题与解析（题量多！）
你好，我是罡罡同学！
代码谱第⼀页忘掉⼼上⼈，最后⼀页。。。。。。
欢迎阅读罡罡同学的⽂章（关注不迷路）
(记得点赞关注哈)
还在为代码⽆法正常运⾏⽽烦恼，关注罡罡同学不迷路，解决你的烦恼。
如果你觉得，本⽂章对你有那么⼀丢丢的帮助，记得点赞关注转发，罡罡同学⾮常感谢哈！
后续⽂章是关于数据结构⼀些基础实验，本⼈都已经成功运⾏，如果有问题，欢迎在评论区留⾔。
您的⽀持是罡罡同学前进的最⼤动⼒！
**我是罡罡同学，⼀位初⼊⽹安的⼩⽩。 ☜(ˆ▽ˆ) **
（疯狂暗⽰ 点赞 ！关注！转发  点赞 ！关注！转发 ）
XXX⼤学2019—2020学年第2学期
《数据结构》期末考试模拟试题答卷
专业:XXX 班级：XXX 学号：XXX 姓名：XXX
考试时间：120分钟
第1题 第2题 第3题 第4题 第5题 第6题 总分 评阅⼈
（题量有些多，⼲就完了。） 为⽅便⼤家刷题，题⽬后紧跟答案
码字⾟苦！求点赞+关注！！
⼀、名词解释
1.算法：算法是对特定问题求解的⼀种描述，它是指令的有限序列，其中每⼀条指令表⽰⼀个或多个操作。
2.模式匹配算法：给定主串S=“S S S…S”和模式串T=“t t t…t”，在S中寻T的过程称为模式匹配。如果匹配成功，返回T在S中
123n123n
的位置，如果匹配失败，返回0。
3.AOV⽹：在⼀个表⽰⼯程的有向图中，⽤顶点表⽰活动，⽤弧表⽰活动之间的优先关系，称这样的有向图为顶点表⽰活动的⽹，简称AOV⽹。
4.AOE⽹：在⼀个表⽰⼯程的带权有向图中，⽤顶点表⽰事件，⽤有向边表⽰活动，边上的权值表⽰活动的持续时间，称这样的有向图叫做边表⽰活动的⽹，简称AOE⽹。
5.内部排序：在排序的整个过程中，待排序的所有记录全部被放置在内存中。
6.外部排序：由于待排序的记录个数太多，不能同时放置在内存，⽽需要将⼀部分记录放置在内存，另⼀部分记录在外存上。整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。
7.⽆向完全图：在⽆向图中，如果任意两个顶点之间都存在边，称该图为⽆向完全图。
8.有向完全图：有向图有n个顶点，则最多有n(n-1)条边，将具有n(n-1)条边的有向图称为有向完全图。
9.孩⼦兄弟表⽰法：将树转换为⼆叉树的存储结构，⼀个数据域，两个指针域，左指针指向第⼀个孩⼦节点，右指针指向下⼀个兄弟节点。
10.抽象数据类型（ADT）：由⽤户定义的，表⽰应⽤问题的数学模型，以及定义在这个模型上的⼀组操作的总称。
11.数据结构：相互之间存在⼀种或多种特定关系的数据元素的集合。
12.堆：堆是具有下列性质的完全⼆叉树：每个结点的值都⼩于或等于其左右孩⼦结点的值（称为⼩根堆），或每个结点的值都⼤于或等于其左右孩⼦结点的值（称为⼤根堆）。
13.哈希表：根据设定的哈希函数H（Key）和处理冲突的⽅法，将⼀组关键字映像到⼀个有限的连续的地址集上，并以关键字地址作为记录在表中的存储位置，这⼀存储结构称为构造哈希表（散列表）。
14.数据的逻辑结构：对数据之间关系的描述，它与数据的存储结构⽆关，同⼀种逻辑结构可以有多种存储结构。
15.数据的物理结构：⼜称存储结构，是数据的逻辑结构在计算机中的表⽰。它包括数据元素的表⽰和关系的表⽰。
⼆、判断题
1.不管⼀颗哈夫曼树有偶数或是奇数个叶⼦结点，其树中总结点的个数必为奇数。 T
2.由⼆叉树的前序和后序遍历序列可以唯⼀的确定⼀颗⼆叉树逻辑结构。 F
3.表达式a*(b+c)-d的后缀表达式是abc+*d-。T
4.线性表的逻辑顺序与存储顺序总是⼀致的。F
5.算法可以⽤不同的语⾔描述，如C、C++、Python等，因此算法实际上就是程序了。F
6.算法的确定性是指算法只能有唯⼀的⼀条执⾏路径，即只要输⼊是相同的就只能得到相同的输出结果。T
7.数据元素是数据的最⼩单位。F
8.
三、简答题
1、设有⼀个栈，元素⼊栈的次序为A，B，C，D，E，能否得到“E，C，A，B，D”的出栈序列，若能，写出操作序列；若不能，说明原因。
不能。栈的特点是先进后出。按ABCDE⼊栈，E出栈后，下⼀个应为D，⽽不可能是C。
2、在长度为11的哈希表中填写关键字17，49，29，38，哈希函数为H（key）=key MOD 11，采⽤⼆次探测再散列。
3、数组A中，每个元素的长度为2个字节，⾏下标i的范围从1到8，列下标j的范围从1到10，从⾸地址SA开始连续存放在存储器内，存放该数组⾄少需要多少个单元？存放⼀⾏⼀列数据需要多少单元？
（字节可以简单理解为单元）
存放该数组⾄少需要：8X10X2=160个单元
（8+10-1）x2=34个单元
4.写出下图两种不同的⼴度优先遍历序列，从V 顶点出发。
V V V V V V V V V V V V V V （本题答案不唯⼀）
5.已知⼀颗完全⼆叉树的结点总数为19，最后⼀层的结点数为多少，解释原因。
在完全⼆叉树中，易知i层完全⼆叉树⾄多2-1个结点。设该完全⼆叉树共h层，易知前h-1层中每⼀层结点都是满的，且2-1<19<2-1，所以该完全⼆叉树有5层，最后⼀层结点数为19-（2-1）=4个
6.具有65个结点的完全⼆叉树其深度为？（根的深度为1）
直接代⼊公式 [log (n+1)] (需要向上取整)，解得深度为7
7.⽤顺序存储的⽅法将完全⼆叉树中所有结点按层逐个从左到右的顺序存放在⼀维数组R[1…N]中，若结点R[i]有右孩⼦，则其右孩⼦是？右孩⼦为：R[2i+1] 左孩⼦是：R[2i]
8.某⼆叉树的中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，则其左⼦树中结点数⽬为？
将该⼆叉树构造出来，答案就出来了。
有图易知，答案为4
11234657
1324657
i 4542
9.设树T有3个3度、2个2度结点，其余均为叶⼦结点，则T中的叶⼦树为？试解释原因。
10.D=（D，R），其中D={1 2 3 4 5 6}，R={（1,2）,（1,4）,（2,3）,（2,4）,（3,4）,（3,5）,（3,6）,（4,6)}该结构为？
A.集合
B.线性表
C.树
D.图
选D
满⾜多对多
11.向⼀个栈顶指针为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=->next
选C
12.循环队列的初始化、判空、判满条件是什么？如何求循环队列的实际长度？
初始化：front=rear=0;
判空：front=rear;
判满：(rear+1)%maxsize=front;
实际长度：(rear-front+maxsize)%maxsize;
13.若⼀个栈的输⼊序列是1，2，3…n，输出序列的第⼀个元素是n，能否确定第k个输出元素是什么？若不能说明原因。
可以确定。因为第⼀个输出序列为n，那么前n-1个元素都是依次进栈，那么第K个元素为n-k+1。
14.⽤⼀条语句实现单链表中删除P所指结点的后继结点。
P->next=p->next->next;
15.for(i=0;i<m;i++)
for(j=0;j<n;j++)
A [i] [j] =i*j
上述语句的事件复杂度为多少？
O(n )
16.
四、画图与算法应⽤
1、构造下图稀疏矩阵的三元组表。
2、序列{36，98，14，23，83，13，28}，构造⼀棵⼆叉排序树。
3、写出序列{36，98，14，23，83，13，28}快速排序的每⼀趟结果。
4.给定⼀组权值{3，6，9，14，8，5，4，19，25}设计相应的哈夫曼树，并计算带权路径长度。
5.⽤迪杰斯特拉算法求顶点V 到其它各顶点的最短路径。
6.已知序列{05 13 19 21 37 56 64 75 80 88 90}分别写出查“88”和“68 ”两个元素的查次数和查轨迹。
查“88”：查3次 查轨迹：56、80、88
查“68”：查4次 查轨迹：56、80、64、75
20
7.对给定的数列{40 28 6 72 100 3 54 1 80 91 38}，以“40 ”为根节点构造⼀棵⼆叉排序树。
（1）画出⼆叉排序树。
（2）画出删除结点“72”后的⼆叉排序树。
8.设有关键码序列{22 37 45 10 32 25 38}，构造⼀棵平衡⼆叉树。要求写清楚过程。
9.给出⼀颗树的逻辑结构T=（N，R），其中：N={A,B,C,D,E,F,G,H,I,J,K},R={r}，r={(A,B),(B,E),(B,F),(F,G),(F,H),(A,C),(C,I),(C,J),(J,K), (A,D)} 试回答下列问题：（以A为根节点）（1）哪个是F的⽗结点？
（2）哪些是B的⼦孙？（3）以结点C为根的⼦树的深度是多少？
由图可得（1）B（2）E F G H (3)3
10.以权值{3 7 8 2 6 10 14}7个结点，构造⼀颗哈夫曼树，计算带权路径长度WPL。要求：按照每个结点的左⼦树根结点的权⼩于等于右⼦树根结点的权的次序构造。
11.⼀⽚电⽂，原⽂为：AMCADEDDMCCAD。现在要把原⽂转换成01串发送给对⽅。为了节省资源，我们希望翻译好的01串长度尽量的短。试设计编码⽅案，并将⽅案与等长编码做⽐较。
五、算法设计
1.头插⼊法创建链表。
void create(node *head,int a[],int n)//数组a[]中是带存储的元素
{  node *p;int i;
node *m=(node*)malloc(sizeof(node));//动态分配内存
m->next=NULL;//m相当于头节点
for(i=0;i<n;i++)
{ p=(node*)malloc(sizeof(node));//待插⼊的新结点
p->data=a[i];//将数组中的元素赋值
p->next=m->next;//头插法
m->next=p;//头插法
}
}
2.折半查算法
int search(table *ST)//折半查在动态数组上查
{int low=0,high=ST->length-1,key,mid;//⾼、低位指针初始化
scanf("%d",&key);//待查关键字
while(low<=high)// 当low>high时循环结束
{ mid=(low+high)/2;
if(key==ST->data[mid])
return mid+1;//输出的是该关键字是
else if(key<ST->data[mid])
high=mid-1;//转换区域
else
low=mid+1;//转换区域
}
}
3.设计算法判断双向循环链表L是否对称。
int duichen(node *head)
{ node *p;node *q;
p=head->next;
q=head->rior;//rior为前指针域
while(p!=q&&p->next!=q)
先序中序后序遍历二叉树{if(p->data==q->data)
{ p=p->next;
q=q->next;
}
else
return0;
}
return1;
}
4.采⽤顺序存储的字符串，设计算法实现从i位置开始删除连续的j个字符。
int sqstring_delete(sqstring* str1,sqstring* str2)
{int i,j,k;
str2->length=0;
str2->data=(char*)malloc((str1->length-j+1)*sizeof(char));
if(i<=0||i>str1->length||i+j-1>str1->length||j<=0)
return0;
for(k=0;k<i-1;k++)
str2->data[k]=str1->data[k];
for(k=i+j-1;k<str->length;k++)
str2->data[k-j]=str1->data[k];
str2->length=str1->length-j;
return1;
}
5.单链表的就地逆置
void nizhi(node* head)
{  node* p;node* q;
p=head->next;
head->next=NULL;
while(p!=NULL)
{ q=p->next;
p->next=head->next;
head->next=p;
p=q;
}
}
6.简单选择排序
void SelectSort(sqlist *L)
{int i,j,k,temp;
for(i=1;i<L->length;i++)
{ k=i;
for(j=1+i;j<=L->length;i++)
if(L->data[k]>L->data[j])
k=j;
if(k!=j)
{ temp=L->data[i];
L->data[i]=L->data[k];
L->data[k]=temp;
}
}
}
7.在循环队列中插⼊⼀个元素x。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。