武汉大学数据结构考试试题(附答案)_第1页
武汉大学数据结构考试试题(附答案)_第2页
武汉大学数据结构考试试题(附答案)_第3页
武汉大学数据结构考试试题(附答案)_第4页
武汉大学数据结构考试试题(附答案)_第5页
已阅读5页,还剩6页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、1.以下过程的执行次数为(a)for(I=0);I I;J-)状态;A.n (N2) 2b。(n-1) (N2) 2 c.n (n1) 2d。(n-1) (N2)2.向量的第一个元素存储地址为100,每个元素长度为2,第五个元素地址为(B )A. 110 B .108 C. 100 D. 1203.如果堆栈的堆栈序列为a、B、C、d、e,则堆栈的不可能输出序列为(C )A. edcba B .decba C. dceab D. abcde4.循环队列将元素值存储在数组a 0,m-1中。如果已知头部和尾部指针分别为front和rear,则当前队列中的元素数为(d)A.(rear-front m)

2、% m b . read-front 1c . read-front-1d . read-front5.不带头节点的单个连接列表head为空的判断条件是(a)a . head=null b . head-next=nullc . head-next=head . head!=NULL6.如果在单个链接表中,P指向最后一个节点以外的节点,并且在P之后插入S指向的节点,则执行(B)A. s-next=p。p-next=s;b . s-next=p-next;p-next=s;c . s-next=p-next;p=s;d . p-next=s;s-next=p;7.在具有n个节点的单链表中,如果该

3、值与x节点的值相同,则查询成功时需要比较的平均节点数(d) a.n b.n2 C. (n-1) 2d。(n 1) 28。在堆栈顶部指针中,hh HS=HS-next;b . x=HS-data;c . HS=HS-next;x=HS-data;d . x=HS-data;HS=HS-next;9.字符串是特殊的线性表,其特殊性是(b)A.可以按顺序保存。b .数据元素是字母c .可链接存储d .数据元素是多字符11.2维数组m的元素,按4个字符(每个字符一个存储单元)的字符串、行下标I的范围0至4、列下标j的范围0至5、m牙齿行保存时,元素m 312.阵列A中每个元素A的长度为3个字节,行下标

4、I为1到8,列下标J为1到10,从第一个地址SA开始按顺序保存在存储器中。逐行存储牙齿阵列时,元素A85的起始地址为(C) A.SA。13.如果设置为高度h的二叉树上只有度0和度2的节点,则这些二叉树中包含的节点数至少为(B )A. 2h B .2h-1 C. 2h 1 D. h 1或更高14.二叉树后巡回序列称为dabec,中旬巡回序列称为debac,前巡回序列称为(D )A. acbed B .decab C. deabc D. cedba15.树的基本遍历策略可分为先根遍历和后根遍历。二叉树基本巡回策略可以分为先巡回,后巡回,后巡。在这里,我们称之为树木变形的二叉树对应二叉树。正确的(A

5、 )A .树中的第一个根遍历序列与相应的二叉树遍历序列相同B.树的后根遍历顺序与相应的二叉树后根遍历顺序相同。c .树的有序遍历序列与相应的二叉树中旬遍历序列相同D.以上都是16。具有6个顶点的无向图的至少几条边,以确保连接图(A )A. 5 B .6 C. 7 D. 817.顺序祖怀方法存储结构为(b)的线性表a .散列存储b .顺序存储或链接存储c .压缩存储d .索引存储18.使用顺序祖怀方法查找长度为n的线性表。每个元素的平均祖怀长度为(C )A. n B .n2 C. (n 1)2 D. (n-1)219.有长度为12的已排序表格。用两分祖怀方法查找牙齿表,在概率中查找成功所需的平均

6、比较次数为(b)A.3512 B .3712 C. 3912 D. 431220.1,3,9,12,32,41,45,62,75,77,82,95,100二、填空问题(每空格1分,共20分)1.线性表的顺序存储中,元素之间的逻辑关系通过物理存储位置确定。线性表格的链接存储中元素之间的逻辑关系由链字段中的指针值确定。2.对于具有N个节点的单链表,时间复杂度O(1)在已知节点P之后插入新节点,时间复杂度O(N)在指定值为X的节点之后插入新节点。3.通过空白梣树、现有输入序列1,2,3,4,5、push、push、pop、push、pop、push、push,输出序列为2,3。4.在无方向图中,所有

7、顶点的角度之和等于所有边数的两倍。5.对于具有n个节点的树,该树中所有节点的角度之和为n-1。6.在一棵三叉树中,有2个节点数为3度,1个节点数为2度,2个节点数为1度,6个节点数为0度7.在霍夫曼编码中,如果编码长度可以小于或等于4,则除了2个字符编码加0和10外,最多可以使用4对字符编码。8.对于具有n个顶点和e个边的连接图形,跨度树中的顶点数和边数分别为n和n-1。9.归并排序20个记录时,共需要5次合并,第三次合并时将2个长度为4的顺序表合并为长度为8的顺序表。第三,问答1。下面简要介绍了算法功能(堆栈和队列的元素类型都是int)Void algo3(Queue Q)stack S;i

8、nt d;InitStack(S):While(!queue empty(Q)DeQueue(Q,d);推(s,d);While(!stack empty(S)流行(s,d);EnQueue(Q,d);算法功能:使用堆栈作为辅助,元素翻转队列中的数据2.我知道一棵二叉树的中旬巡回序列和先到先得的巡回序列,能唯一确认一棵二叉树吗?如果给定的顺序通过序列和后序列,那么唯一能确定吗?(*译者:译者:)中间顺序遍历序列和顺序遍历序列可以唯一标识一棵二叉树。先到先得和后得巡回序列不能唯一确定一棵二叉树。一、选择题1.以下过程的执行次数为()for(I=0);I I;J-)状态;A.n (N2) 2b。(

9、n-1) (N2) 2 c.n (n1) 2d。(n-1) (N2)2.确定堆栈ST(最大元m0)是否为空的条件是()a . ST-top 0b . ST-top=0c . ST-topm 0d . ST-top=m03.如果堆栈的堆栈序列为a、B、c、d、e,则堆栈的不可能输出序列为()A. edcba B .decba C. dceab D. abcde4.在单个链接表中,如果P指向不是最后一个节点的节点,并且在P后插入S指向的节点,则执行()a . S-next=P;p-next=s;b . s-next=p-next;p-next=s;c . s-next=p-next;p=s;d .

10、 p-next=s;s-next=p;5.假设在链组中,f和r牙齿分别是组的开始和结束指针,删除一个节点的运算时()a . r=f-next;b . r=r-next;c . f=f-next;d . f=r-next;6.字符串是可以按()a .顺序存储的特殊线性表。b .数据元素是字母c .可连接的存储d .数据元素是多个字符7 .有两种稀疏矩阵常规压缩方法。即()a .二维数组和三维数组B. 3圆和散列C. 3圆和交叉链表d .散列和交叉链表8。将递归算法转换为相应的非递归算法时,通常需要()a .堆栈b .队列c .链表d .树9.2维数组M的四个元素,列下标j的范围从0到5。如果按M

11、牙齿行保存,则元素M35的起始地址与按M牙齿列保存时以下哪一个元素起始地址相同()a.m 元素A85的起始地址为()A.SA144B.SA180C.SA22D.SA2511。如果T2是从有序树T转换而来的二叉树,那么在T中,节点的后顺序是T2中节点的()a .前顺序b .中间顺序c .后顺序d .层次顺序12。具有n个顶点的无向图的最大边数()a.n b.n (n-1) c.n (n)13.根据二叉树定义,具有三个节点的二叉树()种类A. 3 B .4 C. 5 D. 6 14。在非空二叉树的顺序遍历序列中,根节点的右侧()a .右侧子树的所有节点b .右侧子树的部分节点c .仅15.在一个图

12、中,所有顶点的度之和是所有面数的多少倍()A. 12 B .1 C. 2 D. 416.使用邻接表存储的图的深度优先通过算法。二叉树()a .先遍历b。中序遍历c .下序遍历d .按层次遍历17.使用顺序祖怀方法查找长度为n的线性表。每个元素的平均祖怀长度为()A. n B .n2 C. (n 1)2 D. (n-1)2第二,填空1。算法计算量的大小称为计算的_ _ _ _ _ _ _。2.数据结构研究数据的总和以及它们之间的相互关系,定义了这种结构对应的计算,设计了相应的计算,这种计算后的新结构是结构类型。3.要从单个连接的列表中删除p节点,必须执行以下操作:q=p-next;p-data=

13、p-next-data;p-next=;free(q);4.通过空白梣树、现有输入序列5,4,3,2,1、push、push、pop、push、pop、push、push,输出序列如下:5.在双向链表期间,每个节点都有两个指针字段。一个指向节点,另一个指向节点。一维阵列的逻辑结构如下:7.具有40个节点的理想平衡树的高度为_ _ _ _ _ _。8.假设对长度N=50的有序表执行半次搜索。评估树的高度为,评估树的前五层节点数为,最后一层节点数为。9.假设唱片组的排序代码为(46,79,56,38,40,80)。归并排序期间的第二次合并结果是_ _ _ _ _。10.假设唱片组的排序代码为(46,79,56,38,40,80),则一次快速排序拆分的结果为_ _ _ _ _。第三,简单的回答1。假设4个元素A、B、C、D依次进入堆栈,在堆栈进入过程中允许堆栈,那么尝试写出所有可能的堆栈序列吗?2.一棵包含n个节点的K树可以达到的最大深度和最小深度分别是多少?

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论