4010+数据结构本Word文档下载推荐.docx
- 文档编号:6454785
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:30
- 大小:38.81KB
4010+数据结构本Word文档下载推荐.docx
《4010+数据结构本Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《4010+数据结构本Word文档下载推荐.docx(30页珍藏版)》请在冰点文库上搜索。
1.理解线性表的定义及两种存储结构
2.理解线性表顺序存储的特点、实现方法和应用。
3.理解双向链表、循环链表的原理和相关操作。
第3章栈和队列
1.掌握栈和队列的操作特点
2.理解顺序栈、顺序队列的基本操作
3.能按照后续章节(例如二叉树、排序等)的要求利用递归程序设计技术实现相关算法
掌握在实际编程中栈和队列的不同应用。
理解循环队列的概念、实现方法。
掌握循环队列判空、判满的条件。
第4章串
1.理解串的定义和存储方法
2.掌握用C语言处理字符串的语法规则
掌握串的基本操作和相关算法
第5章数组和广义表
1.掌握特殊矩阵进行压缩存储的下标转换公式。
2.理解稀疏矩阵的压缩存储原理。
3.掌握利用三元组表示稀疏矩阵的方法。
1.掌握数组的存储结构。
2.掌握广义表的概念和存储结构。
第6章树和二叉树
1.掌握二叉树的基本性质,能利用相关性质解决简单计算问题
2.掌握二叉树的链式存储结构、相关操作
3.掌握二叉树的有关算法并能编程实现
4.掌握利用遍历序历构造二叉树的规则和具体步骤
5.掌握哈夫曼树的定义、性质和构造方法
1.掌握树和二叉树的定义
2.掌握二叉树的顺序存储结构
3.掌握哈夫曼树的应用
第7章图
1.掌握图的存储方法(邻接矩阵、邻接表)
2.掌握图的深度优先和广度优先遍历的规则和步骤
1.掌握图的基本概念
2.掌握在连通图中求最小生成树的方法。
了解求图的最短路径等相关算法及其应用
第8章查找
1.掌握顺序表的查找方法、步骤、程序实现、时间复杂度和平均查找长度。
2.掌握在有序的顺序表上进行折半查找的方法、步骤、程序实现。
3.掌握折半查找的判定树的构造方法。
能利用判定树求平均查找长度。
4.掌握二叉排序树的确切定义,掌握建立二叉排序树的步骤和方法。
理解在二叉排序树中进行输入、删除操作的规则。
1.掌握查找的相关概念。
2.掌握哈希表的相关概念和原理,了解常用哈希函数的构造和处理冲突的方法。
理解哈希函数和哈希表的关系及在查找中的应用。
第9章排序
1.掌握教材中介绍的各种排序算法的基本原理、步骤。
2.能针对小规模具体实例,按相关排序算法的规则人工完成排序;
能通过分析排序的中间结果判断所用的排序算法。
3.能正确理解相关排序算法的程序实例,并重点掌握算法中的关键步骤和关键语句。
4.掌握堆和特殊的完全二叉树的对应关系。
掌握建堆、筛选算法和完全二叉树相关操作的对应关系。
第三部分综合练习题
一、填空题
1.在单链表中设置头结点的作用是_____________________________。
2.在双向循环链表的每个结点中包含_____________指针域,其中next指向它的_____________,prior指向它的_____________,而头结点的prior指向_____________,尾结点的next指向_____________。
3.串的两种最基本的存储方式是_____________和_______________。
4.线性表具有_____________和_____________两种存储结构。
5.算法的5个特性是____________、____________、____________、____________和____________。
6.设有一个头指针为head的单向循环链表,p指向链表中的结点,若p->
next==____________,则p所指结点为尾结点。
7.栈是限定在表的一端进行插入和删除操作的线性表,又称为__________。
8.用邻接矩阵存储图,占用的存储空间与图中的________数有关。
9.快速排序在最坏情况下的空间复杂度为____________。
10.数据的逻辑结构在计算机中的表示称为_______________或_______________。
11.向一个栈顶指针为h的链栈中插入一个s所指结点时,可执行________________和h=s;
操作。
(结点的指针域为next)
12.一棵高度为5的完全二叉树中,最多包含有________个结点。
假定树根结点的高度为0。
13.n个顶点的连通无向图的生成树含有________条边。
14.需要压缩存储的矩阵可分为___________矩阵和__________矩阵两种。
15.假定一棵二叉树的结点数为18,则它的最小高度为________。
16.设广义表L=((),()),则表头是__________,表尾是__________,L的长度是__________。
17.在一个长度为n的顺序存储结构的线性表中,向第i(1≤i≤n+1)个元素之前插入新元素时,需向后移动_____________个数据元素。
18.n(n﹥0)个顶点的无向图中顶点的度的最大值为________。
19.在一个链队中,设f和r分别为队头和队尾指针,则删除一个结点的操作为___________。
(结点的指针域为next)
20.循环队列队头指针在队尾指针______________位置,队列是“满”状态
21.顺序表中,逻辑上相邻的元素物理位置___________相邻;
单链表中逻辑上相邻的元素物理位置___________相邻。
22.队列的特性是______________________。
23.一个递归算法必须包括________________和_______________。
24.线性结构中元素之间存在____________关系,树形结构中元素之间存在____________关系,图形结构中元素之间存在____________。
25.往栈中插入元素的操作方式是:
先_____________,后______________。
26.假设以S和X分别表示入栈和出栈操作,则对输入序列a,b,c,d,e一系列栈操作SSXSXSSXXX之后,得到的输出序列为_______________________。
27.设有一个头指针为head的单向链表,p指向表中某一个结点,且有p->
next==NULL,通过操作_____________,就可使该单向链表构造成单向循环链表。
28.除了第1个和最后一个结点外,其余结点有且只有一个前驱结点和后继结点的数据结构为_____________,每个结点可有任意多个前驱和后继结点数的结构为_____________。
29.删除栈中元素的操作方式是:
先______________,后_________________。
30.数据的逻辑结构包括____________、____________、____________和____________四种类型。
31.两个串相等的充分必要条件是__________________。
32.判断一个循环队列LU(最多元素为m0)为空的条件是__________________
33.数据结构按结点间的关系,可分为4种逻辑结构:
_____________、_____________、____________、_____________。
34.每个结点只包含一个指针域的线性表叫_____________。
35.循环队列的引入,目的是为了克服__________________。
36.串是一种特殊的线性表,其特殊性表现在组成串的数据元素都是_______________。
37.在一个单链表中p所指结点之后插入一个s所指结点时,应执行_____________和p->
next=s;
的操作。
38.在一个链队中,设f和r分别为队头和队尾指针,则插入s所指结点的操作为___________和r=s;
39.空串的长度是___________;
空格串的长度是____________。
40.从长度为n的采用顺序存储结构的线性表中删除第i(1≤i≤n+1)个元素,需向前移动____________个元素。
41.带头结点的单链表head为空的判定条件是______________________。
42.n(n﹥0)个顶点的连通无向图各顶点的度之和最少为________。
43.数据结构中的数据元素存在一对一的关系称为_____________结构。
44.对稀疏矩阵进行压缩存储,矩阵中每个非零元素对应的三元组包括该元素的____________、___________和_____________三项信息。
45.在队列的顺序存储结构中,当插入一个新的队列元素时,尾指针_____________,当删除一个元素队列时,头指针_____________。
46.数据结构中的数据元素存在一对多的关系称为_____________结构。
47.广义表A((a,b,c),(d,e,f))的表尾为_______________。
48.已知p为单链表中的非首尾结点,在p结点后插入s结点的语句为______________________。
49.单向循环链表是单向链表的一种扩充,当单向链表带有头结点时,把单向链表中尾结点的指针域由空指针改为_____________;
当单向链表不带头结点时,则把单向链表中尾结点的指针域由空指针改为指向_____________。
50.从一个栈顶指针为h的链栈中删除一个结点时,用x保存被删结点的值,可执行x=h->
data;
和_______________。
51.带头结点的单链表L中只有一个元素结点的条件是_____________________________。
52.存储结构主要有____________、____________、____________、____________四种。
53.数据结构中的数据元素存在多对多的关系称为_____________结构。
54.在一个单向链表中,要删除p所指结点,已知q指向p所指结点的前驱结点。
则可以用操作_____________。
55.在一棵二叉树中,假定双分支结点数为5个,单分支结点数为6个,则叶子结点数为________个。
二、单项选择题
1.判断栈S满(元素个数最多n个)的条件是()。
A.s->
top==0B.s->
top!
=0C.s->
top==n-1D.s->
=n-1
2.线性表在链式存储中各结点之间的地址()。
A.必须连续B.部分地址必须连续
C.不能连续D.连续与否无所谓
3.一个队列的入队顺序是a,b,c,d,则离队的顺序是()。
A.a,d,cbB.a,b,c,dC.d,c,b,aD.c,b,d,a
4.图的深度优先遍历算法类似于二叉树的()遍历。
A.先序B.中序C.后序D.层次
5.权值为{1,2,6,8}的四个结点构成的哈夫曼树的带权路径长度是()。
A.18B.28C.19D.29
6.设有如下遗产继承规则:
丈夫和妻子可以互相继承遗产,子女可以继承父亲和母亲的遗产,子女间不能相互继承,则表示该遗产继承关系最合适的数据结构应该是()结构。
A.树形B.图形C.线性D.集合
7.已知一个有序表为{11,22,33,44,55,66,77,88,99},则顺序查找元素55需要比较()次。
A.3B.4C.5D.6
8.设有一个长度为n的顺序表,要删除第i个元素移动元素的个数为()。
A.n-i+1B.n-iC.n-i-1D.i
9.下列说法中,不正确的是()。
A.数据元素是数据的基本单位
B.数据项是数据中不可分割的最小可标识单位
C.数据可有若干个数据元素构成
D.数据项可由若干个数据元素构成
10.树最适合于用来表示()。
A.线性结构的数据
B.顺序结构的数据
C.元素之间无前驱和后继关系的数据
D.元素之间有包含和层次关系的数据
11.在一个链队中,假设f和r分别为队头和队尾指针,则插入s所指结点的运算为()。
A.f->
f=s;
B.r->
r=s;
C.s->
next=r;
D.s->
next=f;
f=s;
12.有关线性表的正确说法是()。
A.每个元素都有一个直接前驱和一个直接后继
B.线性表至少要求一个元素
C.表中的元素必须按由小到大或由大到下排序
D.除了一个和最后一个元素外,其余元素都有一个且仅有一个直接前驱和一个直接后继
13.下面关于线性表的叙述错误的是()。
A.线性表采用顺序存储,必须占用一片地址连续的单元
B.线性表采用顺序存储,便于进行插入和删除操作
C.线性表采用链式存储,不必占用一片地址连续的单元
D.线性表采用链式存储,便于进行插入和删除操作
14.在一个单链表中,p、q分别指向表中两个相邻的结点,且q所指结点是p所指结点的直接后继,现要删除q所指结点,可用语句()。
A.p=q->
nextB.p->
next=q
C.p->
next=q->
nextD.q->
next=NULL
15.每个存储结点不仅含有一个数据元素,还包含一组指针,该存储方式是()存储方式。
A.顺序B.链接C.索引D.散列
16.关于哈希查找的说法正确的是()。
A.除留余数法是最好的
B.哈希函数的好坏要根据具体情况而定
C.删除一个元素后,不管用哪种方法处理冲突,都只需简单地把该元素删除掉
D.因为冲突是不可避免的,所以装填因子越小越好
17.采用分块查找时,若线性表中共有324个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块,每块应分()个结点最佳。
A.10B.18C.6D.324
18.邻接表是图的一种()。
A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构
19.在一个栈顶指针为top的链栈中,将一个p指针所指的结点入栈,应执行()。
A.top->
next=p;
B.p->
next=top->
next;
top->
next=top;
top=p;
D.p->
top=top->
20.下列有关二叉树的说法正确的是()。
A.二叉树中度为0的结点的个数等于度为2的结点的个数加1
B.二叉树中结点个数必大于0
C.完全二叉树中,任何一个结点的度,或者为0或者为2
D.二叉树的度是2
21.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序()。
A.不发生改变B.发生改变
C.不能确定D.以上都不对
22.组成数据的基本单位是()。
A.数据项B.数据类型C.数据元素D.数据变量
23.若串S=="
English"
,其子串的个数是()。
A.9B.16C.36D.28
24.无向图的邻接矩阵是一个()。
A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵
25.数据结构中,与所使用的计算机无关的是数据的()。
A.存储结构B.物理结构C.逻辑结构D.物理和存储结构
26.向顺序栈中压入新元素时,应当()。
A.先移动栈顶指针,再存入元素B.先存入元素,再移动栈顶指针
C.先后次序无关紧要D.同时进行
27.设二维数组A[5][6]按行优先顺序存储在内存中,已知A[0][0]起始地址为1000,每个数组元素占用5个存储单元,则元素A[4][4]的地址为()。
A.1140B.1145C.1120D.1125
28.在一个单链表中p所指结点之后插入一个s所指的结点时,可执行()。
A.p->
next=s;
s->
next=p->
nextB.p->
next=s->
C.p=s->
nextD.s->
p->
29.一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆是()。
A.79,46,56,38,40,80 B.84,79,56,38,40,46
C.84,79,56,46,40,38 D.84,56,79,40,46,38
30.有一个有序表{1,3,9,12,32,41,45,62,75,77,82,95,100},当用二分查找法查找值为82的结点时,经()次比较后查找成功。
A.1B.2C.3D.4
31.在一个图G中,所有顶点的度数之和等于所有边数之和的()倍。
A.1/2B.1C.2D.4
32.一个线性表第一个元素的存储地址是100,每个元素的长度为4,则第5个元素的地址是()。
A.110B.116C.100D.120
33.将含有150个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点的编号为1,则编号为69的结点的双亲结点的编号为()。
A.33B.34C.35D.36
34.若让元素1,2,3依次进栈,则出栈顺序不可能为()。
A.3,2,1B.2,1,3C.3,1,2D.1,3,2
35.一组记录的关键字序列为(25,48,16,35,79,82,23,40,36,72),其中,含有5个长度为2的有序表,按归并排序的方法对该序列进行一趟归并后的结果为( )。
A.16,25,35,48,23,40,79,82,36,72
B.16,25,35,48,79,82,23,36,40,72
C.16,25,48,35,79,82,23,36,40,72
D.16,25,35,48,79,23,36,40,82,72
36.一个具有n个顶点的无向完全图包含()条边。
A.n(n1)B.n(n1)C.n(n1)/2D.n(n1)/2
37.链表不具有的特点是()。
A.可随机访问任一元素B.插入删除不需要移动元素
C.不必事先估计存储空间D.所需空间与线性表长度成正比
38.在数据结构中,从逻辑上可以把数据结构分成()。
A.动态结构和静态结构B.紧凑结构和非紧凑结构
C.线性结构和非线性结构D.内部结构和外部结构
39.一个队列的入队序列是1,2,3,4。
则队列的输出序列是()。
A.4,3,2,1B.1,2,3,4
C.1,4,3,2D.3,2,4,1
40.两个字符串相等的条件是()。
A.两串的长度相等
B.两串包含的字符相同
C.两串的长度相等,并且两串包含的字符相同
D.两串的长度相等,并且对应位置上的字符相同
41.如果将给定的一组数据作为叶子数值,所构造出的二叉树的带权路径长度最小,则该树称为()。
A.哈夫曼树B.平衡二叉树
C.二叉树D.完全二叉树
42.稀疏矩阵采用压缩存储的目的主要是()。
A.表达变得简单B.对矩阵元素的存取变得简单
C.去掉矩阵中的多余元素D.减少不必要的存储空间的开销
43.下列有关图遍历的说法不正确的是()。
A.连通图的深度优先搜索是一个递归过程
B.图的广度优先搜索中邻接点的寻找具有"
先进先出"
的特征
C.非连通图不能用深度优先搜索法
D.图的遍历要求每一顶点仅被访问一次
44.在有向图的邻接表中,每个顶点邻接表链接着该顶点所有()邻接点。
A.入边B.出边
C.入边和出边D.不是入边也不是出边
45.长度为255的表,采用分块查找法,每块的最佳长度是()。
A.14B.15C.16D.17
46.使用折半查找法时,要求查找表中各元素的键值必须是()排列的。
A.递增或递减B.递增C.递减D.无序
47.把数据存储到计算机中,并具体体现数据元素间的逻辑结构称为()。
A.逻辑结构B.物理结构
C.算法的具体实现D.给相关变量分配存储单元
48.设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好选用()排序法。
A.起泡排序 B.快速排序C.堆排序 D.基数排序
49.如果以链表作为栈的存储结构,则退栈操作时()。
A.必须判断栈是否满B.判断栈元素类型
C.必须判断栈是否空D.对栈不作任何判断
50.假定一棵二叉树中,双分支结点数为15,单分支结点数为30,则叶子结点数为()。
A.15B.16C.17D.47
51.如果要求一个线性表既能较快地查找,又能动态适应变化要求,可以采用()查找方法。
A.顺序B.分块C.折半D.散列
52.设有一个长度为n的顺序表,要在第i个元素之前(也就是插入元素作为新表的第i个元素),则移动元素个数为()。
A.n-i+1B.n-iC.n-i-1D.i
53.串是()。
A.不少于一个字母的序列B.任意个字母的序列
C.不少于一个字符的序列D.有限个字符的序列
54.对于具有n
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 4010 数据结构