数据结构考试大纲Word文档格式.docx
- 文档编号:5770621
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:34
- 大小:41.50KB
数据结构考试大纲Word文档格式.docx
《数据结构考试大纲Word文档格式.docx》由会员分享,可在线阅读,更多相关《数据结构考试大纲Word文档格式.docx(34页珍藏版)》请在冰点文库上搜索。
=null)if(p!
=null&
&
p->
next!
=null)
{q->
next=s;
{q=p->
next;
s->
next=p;
next=p->
next->
}free(q);
else}
{q->
else
s->
next=null;
returnnull;
}returnhead;
}
11.数据结构研究的主要内容、:
1)杂乱的数据不能表达和交流信息;
2)数据之间是有联系的;
3)数据之间是有结构的;
4)在某种数据结构上可定义一组数据。
12.各种排序方法的优缺点、:
2.、选择排序:
每一趟从待排序的数据元素中选出最小或最大的一个元素顺序放在已排好序的数列的最后直到全部待排序的数据元素排完。
选择排序是不稳定的排序方法。
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果①初始状态无序区为R[1..n]有序区为空。
②第1趟排序在无序区R[1..n]中选出关键字最小的记录R[k]将它与无序区的第1个记录R[1]交换使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……③第i趟排序第i趟排序开始时当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。
该趟排序从当前无序区中选出关键字最小的记录R[k]将它与无序区的第1个记录R交换使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
优点:
移动数据的次数已知,n-1次
缺点:
比较次数多
3.、冒泡排序:
已知一组无序数据a[1]、a[2]、……a[n]需将其按升序排列。
首先比较a[1]与a[2]的值若a[1]大于a[2]则交换两者的值否则不变。
再比较a[2]与a[3]的值若a[2]大于a[3]则交换两者的值否则不变。
再比较a[3]与a[4]以此类推最后比较a[n-1]与a[n]的值。
这样处理一轮后a[n]的值一定是这组数据中最大的。
再对a[1]~a[n-1]以相同方法处理一轮则a[n-1]的值一定是a[1]~a[n-1]中最大的。
再对a[1]~a[n-2]以相同方法处理一轮以此类推。
共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。
稳定
慢,每次只能移动相邻两个数据
4.快速排序:
快速排序是冒泡排序的改进版是目前已知的最快的排序方法。
已知一组无序数据a[1]、a[2]、……a[n]需将其按升序排列。
首先任取数据a[x]作为基准。
比较a[x]与其它数据并排序使a[x]排在数据的第k位并且使a[1]~a[k-1]中的每一个数据<
a[x]a[k+1]~a[n]中的每一个数据>
a[x]然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n]两组数据进行快速排序。
极快,数据移动少
不稳定。
冒泡排序是稳定的,选择和快速排序是不稳定的;
快速排序是最快的排序;
快速排序是以牺牲空间为代价的。
13.树的定义、什么是递归、其优缺点、:
树:
树是由n(n>
=0)个结点构成的集合递归算法:
若一个算法直接或间接地调用自己的本身
递归算法的优缺点:
结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带来很大方便。
递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多
14.栈的进、出栈的可能性、:
进栈是否是满栈,出栈是否是空栈。
15.冒泡和选择算法的算法程序的书写、:
写出选择法排序的算法或程序。
(5分)
解:
voidsimpleselectsorlklist(lklist*&
head)
{
lklist*p,*q,*s;
intmin,t;
if(head==0||head->
next==0)return;
for(q=head;
q!
=0;
q=q->
next)
{
min=q->
data;
s=q;
for(p=q->
p!
p=p->
if(min>
p->
data)
{min=p->
s=p;
if(s!
=q)
{
t=s->
data=q->
q->
data=t;
C语言冒泡排序程序:
main()
{
inti,j,temp;
inta[10];
for(i=0;
i<
10;
i++)
scanf("
%d,"
&
a[i]);
for(j=0;
j<
=9;
j++)
{for(i=0;
10-j;
if(a[i]>
a[i+1])
{temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
for(i=1;
11;
printf("
%5d,"
a[i]);
\n"
);
}
16.链表的合并、:
设计两个有序单链表的合并排序算法。
voidmergelklist(lklist*ha,lklist*hb,lklist*&
hc)
lklist*s=hc=0;
while(ha!
=0&
hb!
=0)
if(ha->
data<
hb->
data){if(s==0)hc=s=ha;
else{s->
next=ha;
s=ha;
};
ha=ha->
else{if(s==0)hc=s=hb;
else{s->
next=hb;
s=hb;
hb=hb->
if(ha==0)s->
elses->
17.链表的插入和删除和节点的算法、:
18.通过二叉树的前中后生成的一种树加密、:
例如()
已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,.试写出这棵二叉树的后序遍历结果;
并生成此二叉树;
利用生成的二叉树对1001011001010110加密,写出密文。
(15分)解:
二叉树为:
(如图)
二叉树后序遍历为:
EDCBIHJGFA
加密后密文为:
343743572
一、选择题
1.组成数据的基本单位是()
(A)数据项(B)数据类型(C)数据元素(D)数据变量
参考答案:
C
2.数据结构是研究数据的()以及它们之间的相互关系。
(A)理想结构,物理结构(B)理想结构,抽象结构
(C)物理结构,逻辑结构(D)抽象结构,逻辑结构
3.在数据结构中,从逻辑上可以把数据结构分成()
(A)动态结构和静态结构(B)紧凑结构和非紧凑结构
(C)线性结构和非线性结构(D)内部结构和外部结构
4.数据结构是一门研究非数值计算的程序设计问题中计算机的(①)以及它们之间的(②)和运算等的学科。
①(A)数据元素(B)计算方法(C)逻辑存储(D)数据映像
②(A)结构(B)关系(C)运算(D)算法
AB
5.算法分析的目的是()。
(A)找出数据结构的合理性(B)研究算法中的输入和输出的关系
(C)分析算法的效率以求改进(D)分析算法的易懂性和文档性
6.计算机算法指的是(①),它必须具备输入、输出和(②)等5个特性。
①(A)计算方法(B)排序方法(C)解决问题的有限运算序列(D)调度方法
②(A)可执行性、可移植性和可扩充性(B)可行性、确定性和有穷性
(C)确定性、有穷性和稳定性(D)易读性、稳定性和安全性
CB
二、判断题
1.数据的机内表示称为数据的存储结构。
( )
2.算法就是程序。
()
3.数据元素是数据的最小单位。
4.算法的五个特性为:
有穷性、输入、输出、完成性和确定性。
5.算法的时间复杂度取决于问题的规模和待处理数据的初态。
1、√2、×
3、×
4、×
5、√
三、填空题
1.数据逻辑结构包括________、________、_________和_________四种类型,其中树形结构和图形结构合称为_____。
线性、树形、图形、集合;
非线性(网状)
2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点;
最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。
没有;
1;
1
3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点;
叶子结点没有________结点,其余每个结点的后续结点可以_________。
前驱;
后继;
任意多个
4.在图形结构中,每个结点的前驱结点数和后续结点数可以_________。
5.线性结构中元素之间存在________关系,树形结构中元素之间存在______关系,图形结构中元素之间存在_______关系。
一对一;
一对多;
多对多
6.算法的五个重要特性是_______、_______、______、_______、_______。
有穷性;
确定性;
可行性;
输入;
输出
7.数据结构的三要素是指______、_______和________。
数据元素;
逻辑结构;
存储结构
8.链式存储结构与顺序存储结构相比较,主要优点是________________________________。
插入、删除、合并等操作较方便
9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_________结构,为了方便插入一个元素,数据结构宜用____________结构。
顺序存储;
链式存储
一、选择题(20分)
1.组成数据的基本单位是()。
(A)数据项(B)数据类型(C)数据元素(D)数据变量
2.设数据结构A=(D,R),其中D={1,2,3,4},R={r},r={<
1,2>
,<
2,3>
3,4>
4,1>
},则数据结构A是()。
(A)线性结构(B)树型结构(C)图型结构(D)集合
3.数组的逻辑结构不同于下列()的逻辑结构。
(A)线性表(B)栈(C)队列(D)树
4.二叉树中第i(i≥1)层上的结点数最多有()个。
(A)2i(B)2i(C)2i-1(D)2i-1
5.设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为()。
(A)p->
next(B)p=p->
next
(C)p=p->
next(D)p->
next=p
6.设栈S和队列Q的初始状态为空,元素E1、E2、E3、E4、E5和E6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出列的顺序为E2、E4、E3、E6、E5和E1,则栈S的容量至少应该是()。
(A)6(B)4(C)3(D)2
7.将10阶对称矩阵压缩存储到一维数组A中,则数组A的长度最少为()。
(A)100(B)40(C)55(D)80
8.设结点A有3个兄弟结点且结点B为结点A的双亲结点,则结点B的度数数为()。
(A)3(B)4(C)5(D)1
9.根据二叉树的定义可知二叉树共有()种不同的形态。
(A)4(B)5(C)6(D)7
.设有以下四种排序方法,则()的空间复杂度最大。
(A)冒泡排序(B)快速排序(C)堆排序(D)希尔排序
、填空题(30分)
1.
设顺序循环队列Q[0:
m-1]的队头指针和队尾指针分别为F和R,其中队头指针F指向当前队头元素的前一个位置,队尾指针R指向当前队尾元素所在的位置,则出队列的语句为F=____________;
。
2.
设线性表中有n个数据元素,则在顺序存储结构上实现顺序查找的平均时间复杂度为___________,在链式存储结构上实现顺序查找的平均时间复杂度为___________。
3.
设一棵二叉树中有n个结点,则当用二叉链表作为其存储结构时,该二叉链表中共有________个指针域,__________个空指针域。
4.
设指针变量p指向单链表中结点A,指针变量s指向被插入的结点B,则在结点A的后面插入结点B的操作序列为______________________________________。
5.
设无向图G中有n个顶点和e条边,则其对应的邻接表中有_________个表头结点和_________个表结点。
6.
设无向图G中有n个顶点e条边,所有顶点的度数之和为m,则e和m有______关系。
7.
设一棵二叉树的前序遍历序列和中序遍历序列均为ABC,则该二叉树的后序遍历序列为__________。
8.
设一棵完全二叉树中有21个结点,如果按照从上到下、从左到右的顺序从1开始顺序编号,则编号为8的双亲结点的编号是___________,编号为8的左孩子结点的编号是_____________。
9.
下列程序段的功能实现子串t在主串s中位置的算法,要求在下划线处填上正确语句。
intindex(chars[],chart[])
i=j=0;
while(i<
strlen(s)&
j<
strlen(t))if(s[i]==t[j]){i=i+l;
j=j+l;
}else{i=_______;
j=______;
if(j==strlen(t))return(i-strlen(t));
elsereturn(-1);
10.
设一个连通图G中有n个顶点e条边,则其最小生成树上有________条边。
二选择题(24分)
1.下面关于线性表的叙述错误的是()。
(A)线性表采用顺序存储必须占用一片连续的存储空间
(B)线性表采用链式存储不必占用一片连续的存储空间
(C)线性表采用链式存储便于插入和删除操作的实现
(D)线性表采用顺序存储便于插入和删除操作的实现
2.设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有()个空指针域。
(A)2m-1(B)2m(C)2m+1(D)4m
3.设顺序循环队列Q[0:
M-1]的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置,尾指针R总是指向队尾元素的当前位置,则该循环队列中的元素个数为()。
(A)R-F(B)F-R(C)(R-F+M)%M(D)(F-R+M)%M
4.设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历该二叉树得到序列为()。
(A)BADC(B)BCDA(C)CDAB(D)CBDA
5.设某完全无向图中有n个顶点,则该完全无向图中有()条边。
(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-1
6.设某棵二叉树中有2000个结点,则该二叉树的最小高度为()。
(A)9(B)10(C)11(D)12
7.设某有向图中有n个顶点,则该有向图对应的邻接表中有()个表头结点。
(A)n-1(B)n(C)n+1(D)2n-1
8.设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字5为基准进行一趟快速排序的结果为()。
(A)2,3,5,8,6(B)3,2,5,8,6
(C)3,2,5,6,8(D)2,3,6,5,8
填空题(24分)
为了能有效地应用HASH查找技术,必须解决的两个问题是____________________和__________________________。
下面程序段的功能实现数据x进栈,要求在下划线处填上正确的语句。
typedefstruct{ints[100];
inttop;
}sqstack;
voidpush(sqstack&
stack,intx)
if(stack.top==m-1)printf(“overflow”);
else{____________________;
_________________;
中序遍历二叉排序树所得到的序列是___________序列(填有序或无序)。
快速排序的最坏时间复杂度为___________,平均时间复杂度为__________。
设某棵二叉树中度数为0的结点数为N0,度数为1的结点数为N1,则该二叉树中度数为2的结点数为_________;
若采用二叉链表作为该二叉树的存储结构,则该二叉树中共有_______个空指针域。
设一组初始记录关键字序列为(55,63,44,38,75,80,31,56),则利用筛选法建立的初始堆为___________________________。
三选择题(30分)
1.设某数据结构的二元组形式表示为A=(D,R),D={01,02,03,04,05,06,07,08,09},R={r},r={<
01,02>
01,03>
01,04>
02,05>
02,06>
03,07>
03,08>
03,09>
(A)线性结构(B)树型结构(C)物理结构(D)图型结构
2.下面程序的时间复杂为()
for(i=1,s=0;
i<
=n;
i++){t=1;
for(j=1;
=i;
j++)t=t*j;
s=s+t;
(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)
3.设指针变量p指向单链表中结点A,若删除单链表中结点A,则需要修改指针的操作序列为()。
(A)q=p->
next;
data;
next=q->
free(q);
(B)q=p->
data=p->
(C)q=p->
(D)q=p->
4.设有n个待排序的记录关键字,则在堆排序中需要()个辅助记录单元。
(A)1(B)n(C)nlog2n(D)n2
5.设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以20为基准记录的一趟快速排序结束后的结果为()。
(A)10,15,14,18,20,36,40,21
(B)10,15,14,18,20,40,36,21
(C)10,15,14,20,18,40,36,2l
(D)15,10,14,18,20,36,40,21
6.设二叉排序树中有n个结点,则在二叉排序树的平均平均查找长度为()。
(A)O
(1)(B)O(log2n)(C)(D)O(n2)
7.设无向图G中有n个顶点e条边,则其对应的邻接表中的表头结点和表结点的个数分别为()。
(A)n,e(B)e,n(C)2n,e(D)n,2e
8.设某强连通图中有n个顶点,则该强连通图中至少有()条边。
(A)n(n-1)(B)n+1(C)n(D)n(n+1)
9.设有5000个待排序的记录关键字,如果需要用最快的方法选出其中最小的10个记录关键字,则用下列()方法可以达到此目的。
(A)快速排序(B)堆排序(C)归并排序(D)插入排序
10.下列四种排序中()的空间复杂度最大。
(A)插入排序(B)冒泡排序(C)堆排序(D)归并排序
、填空殖(48分,其中最后两小题各6分)
数据的物理结构主要包括_____________和______________两种情况。
设一棵完全二叉树中有500个结点,则该二叉树的深度为__________;
若用二叉链表作为该完全二叉树的存储结构,则共有___________个空指针域。
设输入序列为1、2、3,则经过栈的作用后可以得到___________种不同的输出序列。
设有向图G用邻接矩阵A[n][n]作为存储结构,则该邻接矩阵中第i行上所有元素之和等于顶点i的________,第i列上所有元素之和等于顶点i的________。
设哈夫曼树中共有n个结点,则该哈夫曼树中有________个度数为1的结点。
设有向图G中有n个顶点e条有向边,所有的顶点入度数之和为d,则e和d的关系为_________。
__________遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序)。
设查找表中有100个元素,如果用二分法查找方法查找数据元素X,则最多需要比较________次就可以断定数据元素X是否在查找表中。
不论是顺序存储结构的栈还是链式存储结构的栈,其入栈和出栈操作的时间复杂度均为____________。
设有n个结点的完全二叉树,如果按照从自上到下、从
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 考试 大纲