还剩15页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
一、判断题(分本大题共小题,每小题分,在小题左面用表示是,表示否)io io14x.线性表的顺序存储结构是一种随机存储结构()
1.一个栈的入栈序列是则是一个不可能的输出序列2a,b,c,,d,edceab()•广义表()((的深渡,是))()3a,@b de,i j
2.树是一种重要的线性数据结构()
4.按照二叉树的定义,具有三个结点的二叉树有种
(55).已知一个有向图的邻接矩阵表示,计算第个结点的出度的方法是求矩阵第列非零元的个数()6i i.将递归算法转换为对应的非递归算法时,通常需要使用队列()
7.在哈夫曼编码中,当两个字符浮现的频率相同时,其编码也相同()
8.散列法存储的基本思想是由关键字的值决定数据的存储地址
(9)()是堆
二、填空题分本大题共小题,个空,
10.101,88,46,70,34,39,45,58,66,10()(1555每一个空分,将正确答案填在空格处)3将下三角矩阵.•的下]三角部份逐行地存储到起始地址为()()的内存单元中,已知
1.A[L8,1810每一个元素占个单元,则的]地址为4A[7,5o•若某二叉树有个叶结点,有个惟独一个孩子的结点,则该二叉树的总结点数为22030o.如果以{}作为叶子结点的权值构造哈夫曼树,则其带权路径长度是34,5,6,7,8o在顺序存储的二叉树中,编号为和编号为的结点处在同一层的条件是
4.i jo.有一个有序表为{)当折半查找值为的结点时,次比51,3,9,12,32,41,45,62,75,77,82,95,100,82较后查找成功
三、分)已知关键字序列为{)要求:(1046,57,84,32,73,36,15,48,90,20,()构造一棵二叉排序树;1()在等概率情况下,该二叉排序树查找成功的平均查找长度2
一、判断题(每小题分,共分)算法的执行时间和所需的存储空间15L都是问题规模的函数,进行算法分析就是要找出这种函数关系()彻底二叉树只能采用顺序存储方法,不能采用链表存储方法()Z.在顺序循环队列的第个元素之后插入一个元素是顺序循环队列的基本运算(3i).若一个叶子是某二叉树的中序遍历的最后一个结点,则它必是该二叉树的前序遍历的最后一个结点()
4.直接插入排序的关键码比较次数与初始罗列有关()
二、单项选择题(每小题分,共分)5210以下数据结构中哪一个是线性结构()L栈线索二叉树网二叉排序树A.B.C.AOV D..若有三个字符的字符序列执行入栈操作,则其所有可能的输出罗列共有()种种6a,b,c A.4B.5C.6种其它D..一棵树的广义表表示为((())棒)用左孩子一右兄弟链表表示时,右指针域非空的节点个7a b,c e,f g,数为()A.l B.2C.3D.
4.下面关于图的存储的叙述中正确的是8().用邻接矩阵法存储图,占用的存储空间大小与图中结点个数和边数都有关A用邻接矩阵法存储图,占用的存储空间大小只与图中边数有关,而与结点个数无关B.用邻接表法存储图,占用的存储空间大小只与图中边数有关,而与结点个数无关用邻接表法存储图,C.D.占用的存储空间大小与图中边数和结点个数都有关.对长度为的有序表采用顺序存储结构,折半查找技术,在等概率情况下,查找成功的平均查找长度是512()其它
三、应用题(每小题分,共分)A.37/12B.62/13C.49/12D.
5201、已知一棵三叉树的存储结构如下表所示,其中root=0,n=7o画出该二叉树0123456Ichild13-1-15-1-1data ab cd ef grchild24-1-16-1-
1、用克鲁斯卡尔算法求下图的最小生成树
2、下图是一棵二叉排序树,规定当二叉排序树被删除的结点既有左子树,又有右子树时,以其中序3前驱替代画出删除后的二叉排序树
55、已知散列表地址空间为散列函数为尸采用线性探测法处理冲突,将数据序列4HTQ.8],Hkey key%7,挨次存入散列表中试画出相应的散列表;并计算等概率下搜索成功的平均搜索长{107,27,28,42,3,25,99,38}度散列表及其查找各关键字要比较的次数如下所示012345678关键字比较次数搜索成功的平均搜索长度为ASL=
四、算法设计题每小题分,共分
515.已知顺序栈简述函数功能,当输入时,输出结果是多少?1s,fl80fl{initstacks;scanf%d”,n;whilen{pushs,n%8;n=n/8}while!Emptystcaks{pops,x;printfC%d,,,x;},写出二叉树前序遍历非递归算法的设计思想,然后写出算法
2.写出直接插入排序算法3
一、选择题(本大题共()小题,每小题分,共()分)
111.数据结构,与所使用的计算机无关的是数据的哪种结构()1存储物理逻辑物理和存储A.B.C.D..线性表是
(2)一个有限序列,可以为空一个有限序列,不能为空A.B.一个无限序列,可以为空一个无限序列,不能为空C.D.,下列哪个选项的邻接矩阵必然是对称矩阵
(3)有向图无向图网网A.B.C.AOV D.AOE.串是一种特殊的线性表,其特殊性体现在()4可以顺序存储数据元素是一个字符可以链式存储数据元素可以是多个字符.不含任何结点的A.B.C D.5空树是()是一棵树是一棵二叉树是一棵树也是一棵二叉树既不是树也不是二叉树.已知一维A.B.C D.6数组采用顺序存储结构,每一个元素占用个存储单元,第个元素的地址为则第一个元素的地址是A49144,()A.108B.180C.176D.
112.链表合用于哪种查找方法()7顺序二分法顺序,也能二分法随机A.B.C.D..用邻接表表示图,进行广度优先遍历时,通常是采用哪种结构来实现算法的()8栈队列.树图A.B.C D..任何一个无向连通图的最小生成树是()9儿惟独一棵一棵或者多棵一定有多棵可能不存在B.C.D..若某彻底二叉树的结点个数为则第个结点的度为()10100,60不确定A.O B.l C.2D.
二、填空题(本大题共小题,每小题分,共分)
5210、一棵深度为的满二叉树有个分支点和个叶子
16、一个字符串相等的充要条件是和2o、从邻接矩阵可以看出,该图共有个顶点如果是有向图,该图共有3A=o1o1o।010条弧、栈的特点是,队列的特点是4o、三元组表中的每一个节点对应与稀疏矩阵的一个非零元素,它包含有三个数据项,分别表示该元素的、5和值
三、简答题(本大题共小题,每小题分,共分)
2510、已知二叉树(如图)请给出它的种遍历序列先序13中序:后序、简述数据结构的概念?在讨论数据结构时,普通会从哪三个方面进行2
四、操作题本大题共小题,每小题分,共分
21020、已知一组关键字为{』』设哈希}函数为哈希表119,14,23,L68,20,84,27,55l0,79Hkey=keyMOD13,的地址范围为用线性探测再散列法处理冲突0-12完成问题构造哈希表1假定每一个关键字的查找概率相等,求查找成功时的平均查找长度2ASLo、已知某字符串中共有种字符各种字符分别浮现次,次,次,次,7次,2S8ab,cde£g h2145次,次,次试把它们作为叶子结点的权值构造一棵哈夫曼树,并求出其带权路径长度349WPL第章绪论(理解)1什么是数据结构
1.1数据结构的基本概念和常用的术语
1.2数据结构发展的历史以及数据结构在计算机科学中地位
1.3算法描述和算法分析
1.4第章线性表(熟练掌握)2线性表的逻辑结构
2.1线性表的顺序存储结构
2.2线性表的链式存储结构
2.3线性表应用举例
2.4第章栈与队列(熟练掌握)3栈
3.1表达式求值
3.2栈与递归过程
3.3队列
3.4第章串(掌握)4串及其操作
4.1串的存储结构
4.2串的应用举例
4.3第章数组和广义表(掌握)5数组的定义和运算
5.1数组的顺序存储结构
5.2矩阵的压缩存储
5.3广义表的定义
5.4广义表的存储结构
5.5第章树与二叉树(熟练掌握)6树的结构定义和基本操作
6.1二叉树
6.2遍历二叉树和线索二叉树
6.3数和森林
6.4哈夫曼树及其应用
6.5第章图(掌握)7图的定义和术语
7.1图的存储结构
7.2图的遍历
7.3图的连通性问题
7.4有向无环图的定义
7.5最短路径
7.6第章查找(掌握)9静态查找表
9.1动态查找表
9.2哈希表
9.3第章内部排序(掌握)10概述
10.1插入排序
10.2快速排序
10.3选择排序
10.4归并排序
10.5基数排序
10.6各种内部排序方法的比较讨论
10.7
四、分)假设在长度大于的循环链表中,既无头结点,也无头指针,为指向该链表中某个结点的指针(81p设计一个算法,删除指向结点的前趋结点p五.(分)设算术表达式由字符串表示,其中可以包括三种括号圆括号、方括号和花括号,嵌套的顺序任7b意,如{[()]是(正)确}的请编写一个算法,实现判别给定表达式中所含括号是否正确配对
一、单项选择题分、每题分
101、在一个单链表,已知所指向的是所指向结点的前驱结点,若在和之间插入所指向的结点,则1p qq ps执行、、A s-next=q-next;q-next=s Bq-next=s-next;s-next=q、、C p-next=s;s-next=q Dq-next=s;s-next=p、串是
2、一些符号构成的序列、一些字母构成的序列A B、一个以上的字符构成的序列、任意有限个字符构成的序列C D、数组的下标下界为每一个元素占个字节,存储在起始地址为的连续内存单元,则元3A
[10]
[10]1,210素的地址为A
[3]
[8]、、、、A138B154C111D
145、已知广义表恻,从中取出原子项的操作是、4L=x,y,zau,w,L yA、、headtailheadL BheadheadtailtailtailL CheadtailtailtailtailLHheadtailtailheadtailL、已知彻底二叉树有个结点,则整个二叉树有个度为的结点
5802、、、、A39B41C40D
38、赫夫曼树中度为的结点个数为、61A、、、不确定0B1C2D、具有个顶点的有向彻底图,边的总数为、7n A、、n Bnn-l Cn-1D nn-l/
2、二分查找法合用于存储结构为—的,且按关键字排好序的线性表
8、顺序存储、链接存储、顺序存储或者链接存储、索引存储A BC D、下列排序算法中,第一趟排序结束后,其最大或者最小元素一定在其最终位置上的算法是
9、归并排序、直接插入排序、快速排序、起泡排序A BC D、一个有向无环图的拓扑序列个数是
10、个、个或者多个、个、多个A1B1C0D
二、正误判断题分,正确打错误打每小题分104,x,
1、链表中结点数据域占的存储空间越多,存储密度越小
1、带头结点和不带头结点的单链表在查找、删除、求长度等操作上无区别
2、如果两个串串长相等且对应字符也相同,则这两个串相等
3、压缩存储的三角矩阵和对称矩阵的存储空间不相同
4、满二叉树是彻底二叉树
5、对于给定的树,与其对应的二叉树是惟一的
6、线索二叉树的指针域中,指向前驱或者后继的个数少于指向孩子的个数
7、给定图的邻接矩阵存储不一定惟一
8、若一个有向图的邻接矩阵主对角线以下的元素均为则该图拓扑有序序列存在90,、对个记录进行直接插入排序,其平均时间复杂度为10n Onlog2n
三、填空题分,题每空分,其他题每空分
10121、下列函数的功能是实现带头结点的单链表逆置1void turnslink*Lslink*p,*q;二;pL-next=NULL;while二q p;P=;q-next=L-next;L-next=q;、“算法就是对求解问题步骤的一种描述,也称为算法设计它具有以下五个特征有穷性,,,2”Algorithm输入和输出、评价算法好坏的五个方面,正,确性,可读性,茁壮性3
四、操作计算题分,每题分
105、有一组关键字序列写出用堆排序法进行升序排序的初始堆序列124,19,56,13,97,59,41,85,1,87,及第一趟排序后的堆序列
2、给定如下图所示的带权无向图G11画出该图的邻接矩阵9110给出采用普里姆算法从顶点出发构造最小生成树的的过程2325411
五、算法设计题分10给定二叉树,采用链式结构存储,编写算法实,现功能统计二叉树中度为的结点数voidcountBitTreE1目
一、填空题分,每空分)(
100.
5、根据数据元素之间关系的不同,数据的逻辑结构划分为、、、1o
2、栈是一种特殊的线性表,它允许在表的一端进行_________________操作,栈中元素的进出原则为、深度为的二叉树其结点数最多有个结点、通常象交通、3k4道路问题的数学模型是一种称为的数据结构、算法的五个重要5的特征是、、、、、两个字符串相等的6o充分必要条件是o、在一棵二叉树中,度为零的结点个数为,度为的结点个数为则有二7n2n,n o、树的度是指的最大值
8、在一个有向图中,某个结点的度是指该结点的和之和
9、在线性表的二分查找法中要求线性表的存储结构必须是采用,且表中的元素必须是10
二、选择题分,每题分)(
101.一个具有个顶点的无向彻底图应有条边()110A.9B.45C.55D.90长度为()的顺序循环队列中,和分别指示队首和对尾,判断队列为满队列的条件是
2.n l.・.n frontrear()()A.rear=front B.rear+l%n=frontC.rear=0D.front=0由组成的集合是一个数据对象(
3.)不同类型的数据项不同类型的数据元素A.B.相同类型的数据项相同类型的数据元素C.D.是表示线性数据结构的()
4.循环链表邻接多重表A.B.孩子链表单链表C.D..设一个栈的入栈元素序列为则不可得到出栈的元素序列有()5a,b,c,d,e,A.edcba B.decba C.dceab D.abcde又是一棵满二叉树()
6.二叉排序树深度为有个结点的二叉树A.B.531有个结点的彻底二叉树哈夫曼()树C.15D.Huffman.折半查找有序表)若查找元素需挨次与表中元素进行比7(2,5,8,20,25,36,40,60,60,较()A.20,36,40,60B.25,40C.25,40,60D.20,36,
40.查找哈希()表,解决冲突的方法有()8Hash链地址法线性探测再散列法A.B.直接地址法除留余数法C.D..一个排序算法时间复杂度的大小有关()9不与所需挪移记录的数目A.与该算法的稳定性B.与所需比较关键字的次数C.与所需辅助存储空间的大小D..数据的基本单位是()10o结点数据元素数据类型数据项A.B.C.D.
三、求解下列问题分,每题分)(105将下面的一个普通书转换成一棵二叉树,并写出它先序、中序、后序三种遍历的遍历序列
1.转换后的二叉树先序遍历序列:中序遍历序列:后序遍历序列:用克鲁斯卡尔算法将下面的图构造成最小生成树,画出生成过程
2.
四、程序填空分,每空分)(
101.将下面折半查找算法补充完整1算法说明已知是个记录的递增有序表,用折半查找法查找关键字为的记录,若查找失败返回r[l…n]n k零;否则返回该记录的序号值查找表顺序存储结构定义如下#define MAXSIZE100typedef struct(keytype key;}Nodetype;typedef NodetypeSqlist[MAXSIZE];算法(函数)Cint binsearchSqlist r,datatype k,int nintlow=1,high=n,mid;while*________________,if r[mid].key==k,else ifr[mid].keykelsereturn0;将下面单链表的插入算法补充完整
2.算法说明在带有头结点的单链线性表中第个位置之前插入元素i x:typedefDataType data;struct node*next;JLNode,*LinkList;int listinsertLinkList head,int i,DataType x{LinkList p=head.sint j=0;while p!=NULLji-lj++;if p==NULL return0;s=malloc sizeofLNode;s-data=x;return1;}
五、算法设计分1已知为顺序栈写出的存储结构类型描述编写算法实现将元素入栈操作入栈成功返回S Sx PushS,,x否则返回和删除栈顶元素的出栈操作出栈成功返回否则返回1,0Pop S1,0。