还剩8页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
数据的存储结构即物理结构包括、、索引、散列种基本类型4抽象数据类型是指以及ADTo算法必须满足的准则为o逻辑结构在计算机中的表示称为结构在线性结构中,开始结点前驱结点,其余每一个结点有且惟独一个前驱结点算法的个重要特性是有穷性、数据结、、输入和输出5构被形式的定义为(D、R),穷集其中口是()的有穷集,R是D上的()有.算法数据元素A B.算法分析的目的是()C.数据操作D.关系找出数据结构的合理性A.研究算法中的输入输出关系B.分析算法的效率以求改进C.分析算法的易读性D.下列时间复杂度中最坏的是(()A.01B.On()C.O logn2D.On2;终端结点后继结点,其余每一个结点有且惟独一个后继结点每一个存储结点不仅含有一个数据元素,还包含一组指针,该存储方式是(顺序链式索引散列A.B.C.D.什么是数据结构?数据结构涉及哪几个方面?常用的存储表示方法有哪几种并给出其定义算法有哪些基本特征算法的时间复杂度是指什么与什么相关?如何计算算法在平均情况下的时间复杂度简述下列概念数据结构、逻辑结构、存储结构、线性结构、非线性结构顺序表线形表元素长度为4,Loc()则()a1=1000,Loc a3=同一栈内各元素的类型O同一数组中个元素所占空间O循环队列是空队列的条件是sqo线性表的节点没有前驱节点向一个长度为的顺序表的第个元素(W W)之前插入一个元素时,需向后挪移n i________________个元素在有个元素的顺序存储结构的线形表中插入一个新元素,需要平均挪移个元素n仅允许在表的同一端进行插入和删除运算的线形表被称为o栈的元素只能从栈的入栈、出栈一个队列的入队序列是、、、、,则队列的输出序列是1234o栈在进行出栈操作是首先要判断So已知循环队列在进行出队操作前首先要判断Sq,在线性结构中,开始结点前驱结点,其余每一个结点有且惟独一个前驱结点;终端结点后继结点,其余每一个结点有且惟独一个后继结点队列的特点是()先进先出任意进出.只进不出A.先进后出C DB.栈的特点是(先进后出任意进出只进不出先进先出B.C.D.A.设一个栈的输入序列为则借助一个栈所得的输出序列不可能的是(A,B,C,D,A.A,B,C,D B.D,C,B,AA,C.A,C,D,B D.D,B,C假设以数组存放循环队列的元素,其头尾指针分别是和则当前队列中的元A[m]front rear,素个数为(A.rear-front+m%m B.rear-front+1C.front-rear+m%m.D.rear-front%m队列中的元素个数是(不变的可变的A.B.任意的C.D.n+14个元素按A、B、C、D顺序连续进S栈,进行Pop(S,x)运算后,x的值是()B.B C.C D.DA.A)处进行删除操作的线形表队列是限定在(端点B.队头C.队尾D.中间A.经过下列栈的运算后()的值是GetTop s)(()()()lnistack s;Push s,a;Push s,b,Pop()s;C.1D.2A.a B.b顺序B.顺序表只能用()存储结构存储链表D.顺序和链表A.A.top=0B.top=1循环队占用的空间C.top=-1D.top=m()可以不连续必须连续B.A.不必连续.不能连续D.C每一个元素的长度为则第个元素的地址是()2,6一个向量第一个元素的存储地址是100,C.100D.120A.110B.108顺序表只能用()存储结构存储O顺序B..顺序和链表A链表D.散列C.如下A具.树有线性结构的数据结B构.有是向(图C.无向图D.栈与队列顺序栈是空栈的条件是(什么是顺序表?什么是栈?什么是队列?对于一个栈,若输入序列请问所有可能得到的输出是什么?A,B,C,、、三个元素进栈的顺序是、、写出所有可能的出栈序列和相应的操作,哪个顺序不会是A BC SA BC,出栈序列?设顺序循环队列的数据结构定义如下typedef StructDatatypequeue[Maxnum];int front;int rear;}SeqCycqueue;并设顺序循环队列采用少用一个存储单元的方法区分队列满和对列空,分别写出顺序循环队列的队列d满和队列空的条件简述下列算法的功能algo stacksint i,n,A
[255];n=0;while!EmytyStacks{n++;PopS,A[n];}fori=1;i=n;i++PushS,A[i];}在顺序表的位置插入值为的结点并且计算其时间复杂度position x链表线形表的存储结构分、两种单链表是的链接存储表示带头结点的单链表为空的判定条件是o在的情况下,链队列的出队操作需要修改尾指针从一个链栈中删除一个结点时,需要把栈顶结点域的值赋给o一个带头结点的单循环链表中,指向尾结点的直接前驱,则指向头结点的指可用表示为P headP head=链栈的栈顶元素安排为链表的首元素的原因是Iso在双向链表的一个结点中有个指针A.1B.2C.O D.3指针所指的元素是双向循环链表的尾指针的条件是P LA.P==L B.P==NULLC.P-Llink==L D.P-Rlink==L在单链表中,若耍向表头插入一个由指针指向的结点,则执行H P;;;;A.H=P P-next=H B.P-next=H H=P;;;;C.P-next=H P=H D.P-next=H-next H-next=P栈链的示意图如下,其栈顶元素是LC.c D.d两指针和分别指向单链表的两个元p q,素,所指元素是所指元素的前驱的条p qB.q-next==p件是A.a B.b)D.p-next==q-nextA.p-next=q个指针C.p==q在双向链表的一个结点中有A.1B.2C.0D.3不带头结点的单链表为空的判定条件是headA.head==NULL B.head-next==NULLC.head-next==head D.head!=next指针指向带头结点的循环单链表的首元素的条件是()P LoA.P==L B.P-n6xt==LC.L-next==P D.P-next==NULL在单链表中设置头结点的目的主要是什么?设计算法,插入一个值为的结点作为双链表的第一个结点x用带头结点的循环链表表示队列,但只设置一个指针指向队列队尾元素站点,试编写相应的初始化空队,判队空,入队,出队个算法4()置队空1()判队空2⑶入队()出队4字符串、数组、矩阵空串的定义是,其长度等于o对矩阵采用压缩存储是为了o设字符串,,,,则与连接后与连接的结果为a=data*567,c==a cb若对称的阶矩阵的下三角元素存储在一维数组中,则该数组中包含个元素n数组的三元组存储是对矩阵的压缩存储阶三角矩阵的上三角元素值相等,进行压缩存储时,该值存储在下标为的数组元素中(下标从开始)n1空串是,其长度等于已知二维数组采用行序为主方式存储,每一个元素占个存储单元,并且第一个元A[m,n]K素的存储地址是()则的地址是Loc A[1,1],A[i,j]o稀疏矩阵的三元组中第列存储的是稀疏数组中非零元素所在的1串是一种特殊的线性表,其特殊性体现在()可以顺序存储数据元素仅包含一个字符A.B.可以链接存储数据元素可以是多个字符C.D.稀疏矩阵普通的压缩存储方法有两种即()A.二维数组和三维数组B.三元组表和散列C.三元组表和十字链表D.散列和十字链表串是()A.不少于一个字母的序列B.任意个字母的序列C.少于一个字母的序列D.有限个字母的序列设有两个串和求在中首次浮现的位置的运算叫做()t p,p t求子串模式匹配串替换图状结构A.B.C.D.A.110B.108C.100D.120一个向量第一个元素的存储地址是每一个元素的长度为则第个元素的地址是(100,2,6设有两个串,是的子串在中浮现的位置是()T=STUDENT;S=TUDEN”S TS TA3B2C1D0假设以三元组表表示稀疏矩阵,则和下列三元组表对应的稀疏矩阵是()A.0-906B.0-906C.0-906D.0-90670007000000000007000-55000-50600200-500600300-5060000060000000000300求子串模式匹配串替换串联接A.B.C.D.设有两个串和求在中首次浮现的位置的运算叫做()t p,p t数组的声明如下;A shortA
[5]
[6]()数组被分配了多少字节?1A()若数组的地址请计算按行存储时和的地址2A A=1000,A
[3]
[2]()按行存储时数组的哪一项位于地址呢?310201034求模式的数组值的算法(注意写出所需的数据结构)p next字符串的模式匹配算法KMP设计产生稀疏矩阵的三元组表示(写出必要的数据结构)递归将转化成递归函数,其递归出口是,递归体是f=l+l/2+1/3+„4-1/n将一个递归算法改为对应的非递归算法时,通常需要使用()栈队列循环队列优先队列A.B.C.D.已知函数()()如果用递归函数表示,则其递归出口是()f n=1+2+3+,,+n,2()()()()A.f1=0B.f1=1C.f0=1D.f n=n回文是指正读反读均相同的序列,如和均是回文,但不是回文“abba”“andna”“good”试写一个算法判定给定的字符串是否是回文的算法(提示使用递归,或者将一半字符入栈)树树中根结点的层数为O简述树的定义和特点树的前序遍历的递归算法树的后序遍历的递归算法树的存储结构要考虑什么且有哪几种表示方法?二叉树高度为的平衡二叉树至少有个结点7在树与二叉树之间的转换方法中,树的根将变为二叉树的o在一个彻底二叉树的顺序存储中,若一个元素的下标为(行区,则其左孩子元素的下i0标,右孩子元素的下标为o深度为的二叉树共有个结点,该二叉树为二叉树k2k-l深度为(根层次为)的二叉树至多个结点61树和二叉树的两个主要差别是和O对二叉树从开始进行连续编号,要求每一个结点的编号大于摆布孩子的编号,同一的结点的1摆布孩子中,其左孩子的编号小于右孩子的编号,则可采用()的方式实现编号前序遍历中序遍历后序遍历从根开始的层次遍历A.B.C.D.彻底二叉树()二叉树一定是满可能是满不是一定不是满A.B.C.D.满二叉树()二叉树一定是彻底不一定是彻底A.B.不是不是彻底C.D.在二叉树中第层的结点数最多可以为()iA.2i B.2i-1C.2M DJ2二叉树的结构如下图标所示,其中序遍历的序列为()B.d,g,b,a,e,c,h,fC.g,d,b,e,h,f,c,aD.a,b,c,d,e,f,g,h在具有个结点的彻底二叉树中,结点的父结点是()n i=1在具有n个结点的彻底二叉树中,结点i(2ivn)的左孩子结点()A.是2i B.不存在C.是2i+1D.是2i-1)个结点深度为的二叉树至多有(5C.31D.10A.16B.32,结点i(2ivn)的左孩子结点()在具有n个结点的彻底二叉树中C.是2i+1D.是2i-1是不存在A.2i B.不存在是A.2i B.C.2i+1D.[i/2]二叉树的定义是什么根据二叉树的定义,具有三个结点的二叉树有几种不同的形态,它们分别是什么请画出来有如下图的二叉树分别写出其前序,中序,后序,按层遍历序列1画出该二叉树对应的森林2当一个彻底二叉树用数组存储时,若是彻底二叉树中的一个非根且非叶结点,写出的双亲结点,左孩子i结点,右孩子结点下标的计算公式设数组下标从开始0写出下列二叉树的前序、中序和后序遍例序列指出树和二叉树的主要差别是什么?已知一棵二叉树的前序遍历的结果是中序遍历的结果是是画出这棵二叉树ABECDFGHIJ,EBCDAFHIGJ,树的后序遍历的递归算法前序遍历二叉树的递归算法中序遍历二叉树的递归算法设计二叉树后序遍历的非递归实现算法图在有个结点的无向图中,其边数最多为n o若图中每条边都方向,则称为无向图G G具有4个顶点的无向彻底图有条边A.6B.8C.5D.20如下具有线性结构的数据结构是.树有向图A B.无向图栈与队列C.D.对如下所示的带权有向图,从顶点到顶点的最短路径为15A.1,4,5B.1,2,3,5有条边的有向图的邻接表中,表中共有个结点NC.1,4,3,5D.1,2,3,4,5有n个顶点的无向图,最多有(条边A.n B.2n C.n*n-1/2有条边的有向图的邻接矩阵存储法中,链表中结点的个数是()NA.N B.2N C.N/2D.N*N在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的()倍A.1/2B.1C.2D.4有拓扑排序的图,一定是(A.有圈图B.无圈任意图C.无向图D.无圈强连通图图的定义和表示是什么?图的存储要考虑什么常用的存储结构有哪几种设计图的深度优先遍历算法检索二分查找的平均时间复杂度为采用顺序查找方法,查找长度为的线性表时,等概率情况下其平均查找长度是(nA.n B.n/2C.n+1/2D.n-1/2二分查找算法的时间复杂度是(A.0(n2)B.O(n)C.OnlognD.Ologn高度为的平衡二叉树至少有个结点7如图所示的四棵二叉树,()是平衡二叉树A.简述什么叫检索内排序对个元素的序列进行冒泡排序时,至少的比较次数是n归并排序的方法是一种的排序方法在直接插入排序的方法中,当需耍将第个数据插入时,此时前・个数据是__________________.的i i1在待排序的元素序列基本有序的前提下,效率最高的排序方法是()直接插入排序选择排序快速排序归并排序A.B.C.D.下列几种排序方法种,要求辅助存储空间量最大的是()简单排序堆排序A.B.快速排序归并排序C.D.给定有个元素的顺序表,建立一个有序单链表的时间复杂度是()n()()A.01B.0n2()()C.O nD.O nlogn2下述几种排序方法中,平均时间复杂性最好的是()直接插入排序选择排序A.B.冒泡排序归并排序C.D.冒泡排序的方法要求被排序的数据()存储必须是顺序必须是链表顺序或者链表二叉树A.B.C.D.直接插入排序算法设计二分插入排序算法设顺序表是一个递减有序表,试写出一算法,将插入其后仍保持的有序性外排序L XL什么是内排序什么是外排序?。