还剩5页未读,继续阅读
文本内容:
一、单项选择题每小题2分,共20分1以下数据结构中哪一个是线性结构?A有向图B队列C线索二叉树D B树2在一个单链表I1L中,若要在当前由指针p指向的结点后面插入一个由q指向的结点,则执行如下语句序列A p=q;p-next=q;B p-next=q;q-next=p;C p-next=q-next;p=q;D q-next=p-next;p-next=q;3不是队列的基本运算A在队列第i个元素之后插入一个元素B从队头删除一个元素C判断一个队列是否为空D读取队头元素的值4字符A、B、C挨次进入一个栈,按出栈的先后顺序组成不同的字符串,至多可以组成个不同的字符串A14B5C6D85由权值分别为3,8,6,2的叶子生成一棵哈夫曼树,它的带权路径长度为oA11B35C19D53以下6-8题基于下图6该二叉树结点的前序遍历的序列为A E、G、F、A、C、D、B BE、A、G、C、F、B、DC E、A、C、B、D、G、F DE、G、A、C、D、F、B7该二叉树结点的中序遍历的序列为A A、B、C、D、E、G、F BE、A、G、C、F、B、DC E、A、C、B、D、G、F D B、D、C、A、F、G、E8该二叉树的按层遍历的序列为oA E、G、F、A、C、D、B BE、A、C、B、D、G、FC E、A、G、C、F、B、D DE、G、A、C、D、F、B9下面关于图的存储的叙述中正确的是oA用邻接表法存储图,占用的存储空间大小只与图中边数有关,而与结点个数无关B用邻接表法存储图,占用的存储空间大小与图中边数和结点个数都有关C用邻接矩阵法存储图,占用的存储空间大小与图中结点个数和边数都有关D用邻接矩阵法存储图,占用的存储空间大小只与图中边数有关,而与结点个数无关10设有关键码序列q,g,叫z,a,n,p,x,h,下面哪一个序列是从上述序列出发建堆的结果?A a,g,h,m,n,p,q,x,Ba,g,m,h,q,n,p,x,z Cg,m,q,a,n,p,x,h,z Dz h,g,m,p,a,n,q,x,z
一、单项选择题1B2D3A4B5B6C7A8C9B10B
一、单项选择题每小题2分,共20分1设Huffman树的叶子结点数为m,则结点总数为A2m B2m-1C2m+l Dm+12若顺序存储的循环队列的QueueMaxSize二n,则该队列最多可存储个元素A n B n-l Cn+1D不确定3下述哪一条是顺序存储方式的优点?A存储密度大B插入和删除运算方便C获取符合某种条件的元素方便D查找运算速度快4设有一个二维数组A[m][n],假设A
[0]
[0]存放位置在60010,A
[3]
[3]存放位置在67810,每一个元素占一个空间,问A
[2]
[3]10存放在什么位置?脚注10表示用10进制表示,m3oA658B648C633D6535下列关于二叉树遍历的叙述中,正确的是A若一个叶子是某二叉树的中序遍历的最后一个结点,则它必是该二叉树的前序遍历最后一个结点B若一个结点是某二叉树的前序遍历最后一个结点,则它必是该二叉树的中序遍历的最后一个结点0若一个结点是某二叉树的中序遍历的最后一个结点,则它必是该二叉树的前序最后一个结点D若一个树叶是某二叉树的前序最后一个结点,则它必是该二叉树的中序遍历最后一个结点6k层二叉树的结点总数最多为A2k-l B2k+l C2K-1D2k-17对线性表进行二分法查找,其前提条件是A线性表以链接方式存储,并且按关键码值排好序B线性表以顺序方式存储,并且按关键码值的检索频率排好序C线性表以顺序方式存储,并且按关键码值排好序0线性表以链接方式存储,并且按关键码值的检索频率排好序对个记录进行堆排序,所需要的辅助存储空间为8n oA0log2n B0n C01D0n29对于线性表7,34,77,25,64,49,20,14进行散列存储时,若选用H K=K%7作为散列函数,则散列地址为0的元素有个A1B2C3D410下列关于数据结构的叙述中,正确的是oA数组是不同类型值的集合B递归算法的程序结构比迭代算法的程序结构更为精炼C树是一种线性结构D用一维数组存储一棵彻底二叉树是有效的存储方法
一、单项选择题每小题2分,共20分1B2B3A4D5A6A7C8C9D10D
一、单项选择题每小题2分,共20分1对一个算法的评价,不包括如下方面的内容A茁壮性和可读性B并行性0正确性D时空复杂度2在带有头结点的单链表HL中,耍向表头插入一个由指针p指向的结点,则执行oA p-next=HL-next;HL-next=p Bp-next=HL;HL=pC p-next=HL;p=HL DHL=p;p-next=HL3对线性表,在下列哪种情况下应当采用链表表示?A时常需要随机地存取元素B时常需要进行插入和删除操作C表中元素需要占领一片连续的存储空间D表中元素的个数不变4一个栈的输入序列为123,则下列序列中不可能是栈的输出序列的是oA231B3210312D1235每一趟都能选出一个元素放在其最终位置上,并且不稳定的排序算法是A冒泡排序B简单选择排序C希尔排序D直接插入排序6采用开放定址法处理散列表的冲突时,其平均查找长度oA低于链接法处理冲突B高于链接法处理冲突0与链接法处理冲突相同D高于二分查找7若需要利用形参直接访问实参时,应将形参变量说明为参数A值B函数C指针D引用8在稀疏矩阵的带行指针向量的链接存储中,每一个单链表中的结点都具有相同的oA行号B列号C元素值D非零元素个数9快速排序在最坏情况下的时间复杂度为oA0log2n B0nlog2n C0n D0n210从二叉搜索树中查找一个元素时,其时间复杂度大致为oA0nB01C0log2n D0n2
一、单项选择题每小题2分,共20分1B2A3B4C5B6B7D8A9D10C
一、单项选择题每小题2分,共20分1以下数据结构中哪一个是线性结构?A有向图B栈C二叉树DB树2若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点,则采用存储方式最节省时间A单链表B双链表C带头结点的双循环链表D单循环链表3不是队列的基本运算A在队列第i个元素之后插入一个元素B从队头删除一个元素C判断一个队列是否为空D读取队头元素的值4字符A、B、C、D挨次进入一个栈,按出栈的先后顺序组成不同的字符串,至多可以组成个不同的字符串?A15B14C16D215由权值分别为4,7,6,2的叶子生成一棵哈夫曼树,它的带权路径长度为oA11B37C19D53以下6-8题基于下面的叙述若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G,后序遍历的序列为B、D、C、A、F、G、Eo6则该二叉树结点的前序遍历的序列为oA E、G、F、A、C、D、B BE、A、G、C、F、B、DC E、A、C、B、D、G、F DE、G、A、C、D、F、B7该二叉树有个叶子A3B2C5D48该二叉树的按层遍历的序列为oA E、G、F、A、C、D、B BE、A、C、B、D、G、FC E、A、G、C、F、B、D DE、G、A、C、D、F、B10设有关键码序列q,g,m,z,a,序列是从上述序列出发建的小根堆的结9下面的二叉树中,不是彻底二叉树A a,g,m,q,z Ba,g,m,z,q Cg,m,q,a,z Dg,m,a,q,z
一、单项选择题每小题2分,共20分1B2C3A4B⑸B6C7A8C9C10B
一、单项选择题每小题2分,共20分1队列的特点是oB先进先出A先进后出D前面都不正确C任意位置进出2有n个记录的文件,如关键字位数为d,基数为r,则基数排序共要进行A nB dC rD n-d遍分配与采集3在二叉树结点的先序序列、中序序列和后序序列中,所有叶子结点的先后顺序oA都不相同B彻底相同C先序和中序相同,而与后序不同D中序和后序相同,而与先序不同4限定在一端加入和删除元素的线性表称为A双向链表B单向链表C栈D队列5快速排序执行一遍之后,已经到位的元素个数是A1B3CD6设森林F对应的二叉树为B,它有m个结点,为n,B的根为p,p的右子树上的结点个数森林F中第一棵树的结点个数是oA m-n-1B n+1C mrn+l Dm-n⑺设有198个初始归并段,如采用K-路平衡归并三遍完成排序,则K值最大为oA12B13C14D158下面关于广义表的叙述中,不正确的是A广义表可以是一个多层次的结构B广义表至少有一个元素C广义表可以被其他广义表所共享D广义表可以是一个递归表9设二叉树根结点的层次为0,一棵深度高度为k的满二叉树和同样深度彻底二叉树各有f个结点和c个结点,下列关系式不正确的是oA f〉=c Bcf Cf=2k+l-a Dcsk-l10从L=apple,pear,orange,banana中,取出banana元素的表达式为A headtailLB headheadtailLCtai1headtai1L Dheadtailheadtai1L
一、单项选择题每小题2分,共20分1B2B3B4C6D7C8B9B10D1下列文件的物理结构中,不利于文件长度动态增长的文件物理结构是oA顺序结构B链接结构C索引结构D Hash结构2在数据结构中,数据元素可由oA实体B域C数据项D字段3对于有n个顶点的有向图,由弗洛伊德Floyd算法求每一对顶之间的最短路径的时间复杂度是oA01B0n C0n D0n34对n个记录的文件进行快速排序,所需要的辅助存储空间为A01B0log2n C0n D0n25哈夫曼树中一定不存在A度为0的结点B度为1的结点C度为2的结点D带权的结点6设D={A,B,C,D},R={E,A,A,B,B,D,D,E,D,A},则数据结构D,{R}是oA树B图B线性表D前面都正确7关键码序列不符合堆的定义A A、C、D、G、H、M、P、Q、R、XB A、C、M、D、H、P、X、G、Q、RC A、D、P、R、C、Q、X、M、H、GD A、D、C、M、P、G、H、X、R、Q8假定关键字K=442205883,允许存储地址为四位十进制数,并且Hash地址为6111,则所采用的构造Hash函数的方法是A直接定址法B平方取中法C除留余数法,模为97D折叠法9在算法的时间复杂度中,n表示问题规模,fn表示基本操作重复执行的次数,则随问题的规模n的增大,算法执行时间的增长率同相同A fnB nC0n D前面都不正确10对线性表进行二分法查找,其前提条件是oA线性表以顺序方式存储,并且按关键码值排好序B线性表以顺序方式存储,并且按关键码值的检索频率排好序并且按关键码值排好序C线性表以链接方式存储,并且按关键码值的检索频率排好序D一线、性单表项以选链择接题方每式小存题储2,分,共20分1A2C3D4B5B6B7C8D9A10A
一、单项选择题每小题2分,共20分1若以1234作为双端队列的输入序列,则既不能由输入受限双端队列得到,也不能由输出受限双端队列得到的输出序列是oA1234B4132C4231D42132将一个A[l..100,L.100]的三对角矩阵,按行优先存入一维数组B
[298]中,A中元素a66,65即该元素下标在B数组中的位置k为假设B
[0]的位置是1A198B195C197D198【分析】如下所示,三对角矩阵第1行和最后1行非零元素个数为2个,其余各行的非零元素个数是3个,所知a66,65前面共有2+3*64=194个非零元素,a66,65本身是第195个非零元3若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为oA n-1B CD4若一个有向图具有拓扑排序序列,并且顶点按拓扑排序序列编号,那末它的邻接矩阵必然为oA对称矩阵B稀疏矩阵C三角矩阵D普通矩阵5设森林F对应的二叉树为有m个结点,此二叉树根的左子树的结点个数为k,则另一棵子树的结点个数为A m-k+1B k+1C m-k-l Dm-k6假定有K个关键字互为同义词,若用线性探测法把这K个关键字存入散列表中,至少要进行次探测A K-1次B K次C K+1次D KK+l/2次7一棵深度为k的平衡二叉树,其每一个非终端结点的平衡因子均为0,则该树共有个结点A2k-l-l B2k-l C2k-l+l D2k-l8如表r有100000个元素,前99999个元素递增有序,则采用方法比较次数较少A直接插入排序B快速排序C归并排序D选择排序9如果只考虑有序树的情形,那末具有7个结点的不同形态的树共有棵A132B154C429D前面均不正确10对ISAM文件的删除记录时,普通A只需做删除标B需挪移记录0需改变指针D一旦删除就要做整理
一、单项选择题每小题2分,共20分1参考答案C2【分析】如下所示,三对角矩阵第1行和最后1行非零元素个数为2个,其余各行的非零元素个数是3个,所知a66,65前面共有2+3*64=194个非零元素,a66,65本身是第195个非零元参考答案B3【分析】在哈夫曼树的非叶结点中最多惟独1个结点的度不为m,设非叶结点的个数为k,则其中有k-1个结点的度为m,设另1个结点的度为u,则2WuWm,设结点总数为n总,则有如下关系n总一1=011-1+11
①n总=k+n
②将
②代入
①可得k+nT=mkT+u,解得,由于2WuWm,所以可得OWnruVmT,所以可得WkV+1,可知参考答案C4【分析】设顶点按拓扑排序序列为vO,vl,-,vn-l,则对于邻接矩阵A,惟独当ij时,才可能有弧vi,vj,也就是当ij时,一定没有弧〈vi,vj,所以这时A[i][j]=O,可知邻接矩阵为三角矩阵参考答案C5【分析】设另一棵子树的结点个数为n,所以有m=n+k+l,可知n=m-k-lo参考答案06【分析】因为K个关键字互为同义词,惟独在存入第一个关键字的情况下不发生冲突,所以至少需进行1+2+…+K=KK+l/2次探测参考答案D7【分析】由于每一个非终端结点的平衡因子均为0,所以每一个非终端结点必有摆布两个孩子,且左子树的高度和右子树的高度相同,这样AVL树是满二叉树高度为k的满二叉树的结点数为2k-lo参考答案D8【分析】本题中惟独直接插入排序利用前面有序的子序列这个性质,如用直接插入排序对本题只需将最后一个元素插入到前面99999个元素的有序子序列中即可,显然比较次数较少参考答案A9【分析】具有n个结点有不同形态的树的数目和具有n-1个结点互不相似的二叉树的数目相同将树转化为二叉树时,根结点右子树为空,所以除根结点而外惟独左子树,其不相似的二叉树的等价于不相似的左子树具有n个结点互不相似的二又树的数目为,本题中应为参考答案A9参考答案A。