暨南大学计算机830数据结构2018年真题
- 格式:doc
- 大小:109.00 KB
- 文档页数:5
数据结构暨南大学期末试卷试题一、判断题(共10分)1. 当静态链表采用数组实现时,插入与删除操作仍需移动元素。
2. 栈也是一种线性表,也同样有顺序存储结构和链式存储结构。
3. 二叉树的三种遍历算法区别仅在于对树根、左右子树访问先后顺序的不同。
4. 邻接表是图的一种顺序存储结构。
5. 二叉树就是度数为2的树。
6. 在哈希表中勿需比较就可找到记录在表中的位置。
7. 线性表的链式存储结构既方便其存取操作,也方便其插入与删除操作。
8. 顺序存储结构既适合于完全二叉树,也同样适合于一般的二叉树。
9.一个算法是正确的、高效率的,还不能说它就是一个“好”的算法。
10. 快速排序与堆排序的平均时间复杂度相同。
二、概念填空(共20分,每题2分)1.对顺序存储结构的线性表,设表长为La;在各元素插入为等概率条件下,插入一个数据元素需平均移动表中元素_______ 个;在最坏情况下需移动表中元素_______ 个。
2.从逻辑角度看,四种基本的数据结构可分为__________、___________、____________和____________;两种存储结构为_____________和_________________。
3.一个深度为,的满k(k>2)叉树,其第i层(若存在)有________个结点;编号为p(p>1)的结点其父结点(父结点为非根结点)编号是___________________。
4.具有n个结点的完全二叉树的深度为____________;编号为p(<n)的结点其右孩子(若存在)结点编号是___________。
5.堆栈被称为一个_____________的线性表;队列被称为一个_____________的线性表。
6.静态查找表的查找方法主要有:有序表查找及________________________;在n个记录中进行折半查找,当查找不成功时,与关键字比较次数最多为_____________________。
由此可知,左子树为o,右子树为1,故答案为A 。
6.解析:根据二叉排序树的特性:中序遍历(LNR)得到的是一个递增序列。
图中二叉排序树的中序遍历序列为Xi ,X3, X 5, X 4, X 2, 可知X3<�5<X407.解析:拓扑排序每次选取入度为0的结点输出,经观察不难发现拓扑序列前两位一定是1,5或5, 1 (因为只有1和5的入度均为o,且其他结点都不满足仅有1或仅有5作为前驱)。
因此D 显然错误。
8.解析:m阶B树的基本性质:根结点以外的非叶结点最少含有「m/21-1个关键字,代入m =3得到每个非叶结点中最少包含1个关键字,而根结点含有1个关键字,因此所有非叶结点都有两个孩子。
此时其树形与h =5的满二叉树相同,可求得关键字最少为31个。
9.解析:根据题意,得到的HT如下:二2 34 5 643 15ASL 成功(1 + 2 + 3)/3 = 2。
10.解析:初始序列:8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6第一趟:1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8第二趟:I I I I I I I I I I I1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9 I I I I I I I I I I I第一趟分组:8, 1, 6; 3, 4; 9, 7; 11, 5; 2,.10; 间隔为5,排序后组内递增。
第二趟分组:1,5,4,10; 3,2,9,8; 7,6,11; 间隔为3,排序后组内递增。
故答案选D 。
11.解析:要熟练掌握建堆、堆的调整方法,从序列末尾开始向前遍历,变换过程如下图所示。
6)� 6')'/.)一5�气;。
\三12. 解析:对于I,二进制由千只有0,1两种数值,运算规则较简单,都是通过A LU部件转换成加法运算。
对于II,二进制只需要高电平和低电平两个状态就可以表示,这样的物理器件很容易制造。
暨南大学2018年真题参考答案一、名词解释1.由于手术创伤的反应,术后病人的体温可略升高0.1~1℃,一般不超过38℃,称之为外科手术热或吸收热。
(外6 P.115)2.脑组织从高压区向低压区移位,导致脑组织、血管及脑神经等重要结构受压和移位,被挤入小脑幕裂孔、枕骨大孔、大脑镰下间隙等生理性或病理性间隙或孔道中,从而出现一系列严重的临床症状。
(外6 P.222)3.分级护理是指根据病人病情的轻重缓急以及自理能力的评估结果,给予病人不同级别的护理,通常分为四个护理级别,即特级护理、一级护理、二级护理及三级护理。
(基6 P.096)4.体温骤然上升至39℃以上,持续数小时或更长,然后下降至正常或正常以下,经过一个间歇,体温又升高,并反复发作,即高热期和无热期交替出现。
(基6 P.240)5.由于支气管-肺组织、胸廓或肺血管病变引起肺血管阻力增加,产生肺动脉高压,继而右心室结构和(或)功能改变的疾病。
(内6 P.083)6.是由于窦房结病变导致功能减退,从而产生多种心律失常的综合表现。
(内6 P.172)7.又称过期流产,是指胚胎或胎儿已死亡滞留在宫腔内尚未自然排出者。
(妇6 P.140)8.由各种肾脏疾病所致的,以大量蛋白尿(尿蛋白>3.5g/d)、低蛋白血症(血清白蛋白<30g/L)、水肿、高脂血症为临床表现的一组综合征。
(内6 P.396)二、单项选择题1. C解析:外6 P.473 注:“外6 P.473”表示“第六版外科护理学第473页”2.C解析:外6 P.0153.D解析:外6 P.5964.A解析:外6 P.4235.E解析:外6 P.4996.D解析:外6 P.5737.B解析:外6 P.0928.A解析:外6 P.0659.B解析:外6 P.70910.B解析:外6 P.50111.A解析:外6 P.23412.A解析:外6 P.424解析:基6 P.346 14.A解析:基6 P.359 15.B解析:基6 P.150 16.E解析:基6 P.280 17.C解析:基6 P.270 18.B解析:基6 P.036 19.A解析:内6 P.498 20.A解析:内6 P.049 21.B解析:内6 P.574 22.D解析:内6 P.845 23.A解析:内6 P.083 24.D解析:内6 P.618 25.C解析:内6 P.296 26.E解析:内6 P.585 27.C解析:内6 P.329 28.B解析:内6 P.455 29.A解析:内6 P.485 30.C解析:内6 P.472 31.E解析:妇6 P.025 32.B解析:妇6 P.143 33.B解析:妇6 P.299 34.E解析:妇6 P.141解析:儿6 P.21336.B解析:儿6 P.44037.E解析:儿6 P.17638.D解析:儿6 P.38039.B解析:儿6 P.20040.B解析:儿6 P.342三、简答题1.答:凡是需要营养支持但又不能或不宜接受肠内营养的病人,包括预计1周以上不能进食、或因胃肠道功能障碍、不能耐受肠内营养者,或通过肠内营养无法达到机体需要的目标量者,均是肠外营支持的适应症。
2023 年招收攻读硕士学位研究生入学考试试题A 卷******************************************************************************************** 招生专业与代码:网络空间安全考试科目名称及代码:数据结构 830考生注意:所有答案必须写在答题纸(卷)上,写在本试题上一律不给分。
一、单项选择题(每题 2 分,共 20 分)1.以下数据结构中, ( )是非线性数据结构A.字符串B.树C.队列D.栈2.请选择下面程序段的时间复杂度( )i = 1;while (i <= n)i = i * 3;A.O(n)B. O(log3 n)C. O(n2)D. O(i * n)3.顺序表中第一个元素的存储地址为120,每个元素的长度为5,则第4 个元素的地址为 ( )A. 135B. 140C. 130D. 1454.在单链表中,要将L所指节点插入到M所指节点之后,其语句应为( )A.L->next = M+1; M->next = L;B.(*M).next = L; (*L).next = (*M).next;C.L->next = M->next; M->next = L->next;D.L->next = M->next; M->next = L;5.若让元素1,2,3,4,7 依次进栈,则出栈顺序不可能为( )A. 7, 4, 3, 2, 1B. 4, 3, 1, 2, 7C. 2, 1, 7, 4, 3D. 2, 3, 7, 4, 16.假设栈 S 与队列 Q 的初始状态为空,元素 e1、e2、e3、e4、e5 和 e6 依次进入栈 S,一个元素出栈后即进入 Q,若 6 个元素出队的序列是 e2、e4、e3、e6、e5 和e1,则栈S 的容量至少为( )A.2 B. 4 C. 3. D.67.假设以行序列为主序存储二维数组 A = array[1..100,1..100],设每个数据元素占 2 个存储单元,基地址为 10,则 LOC[5, 5] = ( )A.808 B.1010 C.818 D.10208.由3个不同结点可计算出多少种不同的二叉树?( )A. 3B. 4C. 5D. 69.广度优先遍历类似于二叉树的( )A.先序遍历B. 中序遍历C. 层次遍历D.后序遍历10.设哈希表长为14,哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84 共四个,现要将关键字为49 的元素加到表中,用二次探测法解决冲突,则放入的位置是( )A.8 B.3 C.5 D.9考试科目:数据结构共 3 页,第 1 页。
一、选择题1. B【解答】由n0=n2+1可得,n2=10,所以分支数为:2*10+1*2=222. D【解答】满二叉树的结点最多3. A【解答】可以直接画出二叉树如下所示,从而直接得到结果4. B【解答】看清楚题目所要求的,为逆邻接表,根据定义,所以为出度5. A6. B7. C8. B9. A【解答】根据数组给出的顺序,可以将之画成完全二叉树,看哪一个选项满足情况。
10. B【解答】在本题中,因为是对称矩阵,那么直接存储下三角元素即可。
存储方法为a11a12 a22a13 a23 a33a14 a24 a34 a44a15 a25 a35 a45 a55...a18 a28 a38 a48 a58一共1+2+3+4+5+6+7+5=3311. D【解答】可能该队列只存在一个节点12. C【解答】画出Huffman树的得,可以得到带权路径长度为:7*1+5*2+(2+4)*3=3513. C14. C15. D二、填空题1. 为了保证处理第一个节点和后面的节点的时候设计的算法相同,实现程序的高效性。
2. 队列3. 是有序的顺序表4. 遍历其右子树时第一个访问的结点,即右子树的最左下结点。
5. 最小近6. m-17. O(n)8. 题目说的不是很清楚,若是采用邻接矩阵存储,那么时间复杂度为O(n^2),若是采用邻接表存储,那么时间复杂度为O(n+e)9. 距离源点路径长度小的三、判断题1. X2. X3. √4. X5. √6. √(最小生成树的形态可能不唯一)7. √8. √9. √10. √四、解答题1. 拓扑排序的序列可能为:a) 1、2,、3、4、5、6b) 1、2、4、3、5、6c) 2、1、3、4、5、6d) 2、1、4、3、5、6对于有向无环图,还可以采用深度优先遍历算法。
2. 该二叉树为:3. 第一趟:12 2 4 3 6 13 18 9 19 8第二趟:3 2 4 8 6 13 12 9 19 18第三趟:3 2 4 8 6 9 12 13 19 18第四趟:2 3 4 6 8 9 12 13 18 194. 构造的散列表如下:0 1 2 3 4 5 6 7 8 9 1033 41 30 1 20 24 13 67查找成功的平均查找长度为:(1+1+2+2+1+1+1+6)/8=15/85. 该问题的实质:单源最短路径,需要一个个的进行分析再得到结果a) 假设学校建在ab->a 的路径长度为6c ->a 的路径长度为2+1+6=9d->a 的路径长度为1+6=7e->a 的路径长度为5+1+6=12那么总共需要的距离之和为:6+9+7+12=34b) 假设学校建在ba->b 的路径长度为1c->b 的路径长度为2+1=3d ->b 的路径长度为1e ->b 的路径长度为5+1=6那么总共需要的距离之和为:1+3+1+6=11c) 假设建在ca->c 1+2=3;b->c 2;d->c 3 e->c 5+3=8那么总共需要的距离之和为:3+2+3+8=16d) 假设建在da->d 1+2+2=5; b->d 2+2=4; c->d 2; e->d 5那么总共需要的距离之和为:5+4+2+5=16e) 假设建在ea->e 1+2+4=7; b->e 2+4=6; c->e 4; d->e 3+4=7那么总共需要的距离之和为:7+6+4+7=24综上比较可知,建在b较好。
暨南大学硕士研究生入学考试自命题科目830《数据结构》考试大纲Ⅰ考试形式一、试卷满分及考试时间本试卷满分为150分,考试时间为180分钟二、答题方式答题方式为闭卷、笔试Ⅱ考查目标1.理解数据结构的基本概念;掌握数据结构的逻辑结构、存储结构及其差异,以及各种基本操作的实现。
2.掌握基本的数据处理原理和方法的基础上,能够对算法进行设计与分析。
3.能够选择合适的数据结构和方法进行问题求解。
一、基本概念和术语(一)数据元素、数据结构、抽象数据类型等概念(二)算法设计的基本要求(三)语句的频度和估算时间复杂度二、线性表(一)线性表的定义和基本操作(二)线性表的实现1.顺序存储结构2.链式存储结构3.线性表的应用三、栈、队列和数组(一)栈和队列的基本概念(二)栈和队列的顺序存储结构(三)栈和队列的链式存储结构(四)栈和队列的应用(五)特殊矩阵的压缩存储四、树与二叉树栈(一)树的概念(二)二叉树1.二叉树的定义及其主要特征2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历4.线索二叉树的基本概念和构造5.二叉排序树6.平衡二叉树(三)树、森林1.树的存储结构2.森林与二叉树的转换3.树和森林的遍历(四)树的应用1.特价类问题2.哈夫曼(Huffman)树和哈夫曼编码五、图(一)图的概念(二)图的存储结构及基本操作1. 邻接矩阵2.邻接表(三)图的遍历1.深度优先搜索2.广度优先搜索(四)图的基本应用1.最小(代价)生成树2.拓扑排序3.关键路径4.最短路径六、查找(一)查找的基本概念(二)顺序查找法(三)折半查找法(四)B-树(五)散列(Hash)表及其查找(六)查找算法的分析及应用七、内部排序(一)排序的基本概念(二)插入排序1.直接插入排序2.折半插入排序(三)气泡排序(bubble sort)(四)简单选择排序(五)希尔排序(shell sort)(六)快速排序(七)堆排序(八)二路归并排序(merge sort)(九)基数排序(十)各种内部排序算法的比较(十一)内部排序算法的应用Ⅲ特别推荐1.严蔚敏、吴伟民, 数据结构(C语言版),清华大学出版社出版2.严蔚敏, 吴伟民,《数据结构习题解析》,清华大学出版社出版。
2018年计算机学科专业基础综合试题参考答案一、单项选择题1.B2.C3.A4.A5.A6.C7.D8.B9.C10.D11.A12.D13.C14.A15.A16.B17.C18.B19.A20.D21.B22.C23.C24.D25.B26.A27.C28.D29.D30.A31.D32.C33.B 34.C 35.D 36.D 37.D 38.C 39.B 40.D二、综合应用题41.解析:1)题目要求算法时间上尽可能高效,因此采用空间换时间的办法。
分配一个用于标记的数组B[n],用来记录A中是否出现了1~n中的正整数,B[0]对应正整数1,B[n-1]对应正整数n,初始化B中全部为0。
由于A中含有n个整数,因此可能返回的值是1~n+1,当A中n个数恰好为1~n时返回n+1。
当数组A中出现了小于等于0或者大于n的值时,会导致1~n中出现空余位置,返回结果必然在1~n中,因此对于A中出现了小于等于0或者大于n的值可以不采取任何操作。
经过以上分析可以得出算法流程:从A[0]开始遍历A,若0<A[i]<=n,则令B[A[i]-1]=1;否则不做操作。
对A遍历结束后,开始遍历数组B,若能查找到第一个满足B[i]==0的下标i,返回i+1即为结果,此时说明A中未出现的最小正整数在1~n之间。
若B[i]全部不为0,返回i+1(跳出循环时i=n,i+1等于n+1),此时说明A中未出现的最小正整数是n+1。
int findMissMin(int A[],int n){int i,*B; //标记数组B=(int *)malloc(sizeof(int)*n); //分配空间memset(B,0,sizeof(int)*n); //赋初值为0for(i=0;i<n;i++)if(A[i]>0&&A[i]<=n) //若A[i]的值介于1~n,则标记数组BB[A[i]-1]=1;for(i=0;i<n;i++) //扫描数组B,找到目标值if (B[i]==0) break;return i+1; //返回结果}3)时间复杂度:遍历A一次,遍历B一次,两次循环内操作步骤为O(1)量级,因此时间复杂度为O(n)。
2020年全国硕士研究生统一入学考试自命题试题B卷********************************************************************************************学科、专业名称:网络空间安全研究方向:网络空间安全083900考试科目名称及代码:数据结构830考生注意:所有答案必须写在答题纸(卷)上,写在本试题上一律不给分。
一、单项选择题(每题2分,共30分)1. 下述关于顺序存储结构优点的说法,哪个是正确的()A. 插入运算方便B. 可方便地用于各种逻辑结构的存储表示C. 存储密度大D. 删除运算方便2. 假设根结点为第1层,深度为h层的二叉树至少有( ) 个结点(h>1);A. 2hB. 2h-1C. 2h+1D. 2h-13. 用单向链表来实现容量为n的堆栈时,链表头指针指向堆栈顶部元素,链表尾指针指向堆栈底部元素,则以下说法错误的是( )A. 入栈操作的复杂度为O(1)B. 出栈操作的复杂度为O(1)C. 删除底部元素的复杂度为O(1)D. 插入一个新的堆栈底部元素复杂度为O(1)4. 以下关于递归算法的论述,不正确的是( )A. 递归算法的代码可读性好B. 递归算法可以提高程序运行效率C. 递归调用层次太深有可能造成堆栈溢出D. 递归调用层次太深会占用大量内存5. 设有字符集合{4,6,3,W,S},将字符序列6W43S中的字符按顺序进入堆栈,出栈可发生在任何时刻。
则以下的出栈序列错误的是()。
A. 64WS3B. 4W36SC. 6W34SD. WS4366. 在管理城市道路交通网络据时,最适合采用()数据结构来对其进行存储。
A.有向图B.无向图C.树D.矩阵7. 具有k个顶点的完全有向图的边数为( )。
A. k(k-1)B. k(k-1)/2C. k2-1D. k2+18. 若线性表最常用的操作是增加或者删除某个元素, 则采用( )存储方式节省时间.A. 单链表B. 双链表C. 单循环链表D. 顺序表9. 由权为6,3,2,8的四个叶子结点构造一个哈夫曼树,该树的带权路径长度为()。
2018年全国硕士研究生统一入学考试自命题试题(A卷)********************************************************************************************学科、专业名称:计算机科学与技术、软件工程研究方向:计算机系统结构081201,计算机软件与理论081202,计算机应用技术081203,软件工程083500,计算机技术(专业学位) 085211考试科目名称及代码:数据结构830考生注意:所有答案必须写在答题纸(卷)上,写在本试题上一律不给分。
考试科目:数据结构共5页,第1 页考试科目:数据结构共5 页,第2 页图12。
一棵二叉树,若根结点的左右子树均有三个结点,其左子树的先序序列与中序序列相同,右子树的中序序列与后子序序列相同,试构造该二叉树。
(7分)3。
已知序列(12,18,4,3,6,13,2,9,19,8).请给出采用希尔排序对该序列作升序排序的每一趟结果(步长分别为5,3,2,1).(8分)4. 设有一组关键字(33,41,20,24,30,13,01,67),采用散列函数H(key)=(3*key) 11,采用线性探测再散列解决冲突,H i=(H(key)+d i)%11,其中d i=1,2,…,10. 试在0~10散列地址空间中对该关键字序列(按从左到右的次序)构造散列表,并计算在查找概率相等的前提下查找成功时的平均查找长度。
(10分)5.已知图2所示的有向图。
设其顶点a,b,c,d,e表示一个乡的5个村庄,弧上的权值表示为两村之间的距离。
乡内要建立一所学校,问学校设在哪个村庄才能使从各村出发到学校的距离总和最小.(要求回答解决上述问题应采用什么算法,并写出应用该算法解答上述问题的每一步计算结果)。
(10分)图2考试科目: 数据结构共5 页,第3 页五、算法填空(共2小题,每空2分,共20分)1。
2018年全国硕士研究生统一入学考试自命题试题(A卷)
********************************************************************************************
学科、专业名称:计算机科学与技术、软件工程
研究方向:计算机系统结构081201,计算机软件与理论081202,计算机应用技术081203,
软件工程083500,计算机技术(专业学位) 085211
考生注意:所有答案必须写在答题纸(卷)上,写在本试题上一律不给分。
一、单项选择题(每题2分,共30分)
1. 任何一棵二叉树T, 如果度为1的结点数为2,度为0结点数为11,其分支数为( ) 。
A. 23
B. 22
C. 24
D. 21
2. 深度为k的二叉树至多有( ) 个结点(k>=1);
A. 2k
B. 2k-1
C. 2k+1
D.2k-1
3. 已知一棵二叉树结点的中序序列为BDCEAFHG, 后序序列为DECBHGFA, 则结点的先序序
列为( ) 。
A. ABCDEFGH
B. DGBFHCA
C. DECBGFAH
D. CAFHGDB
4. 在有向图的逆邻接表存储结构中,顶点v在表结点中出现的次数是()。
A. 顶点V的度
B. 顶点V的出度
C. 顶点V的入度
D. 依附于顶点V的边数
5. 顺序栈s的GetTop(s, e)操作是用e返回s的栈顶元素,则下列( )是正确的操作。
A. e=*(s.top)
B. e=*(s.top-1)
C. e=*(--s.top)
D. e=s.top-1
6. 若线性表最常用的操作是存取第i个元素及其前趋的值, 则采用( )存储方式节省时间.
A. 单链表
B. 双链表
C. 单循环链表
D. 顺序表
7. 在一棵非空m阶的B-树上,除根之外的所有非终端结点()。
A. 至少有⎣⎦2/m棵子树
B. 至多有⎣⎦2/m棵子树
C. 至少有⎡⎤2/m棵子树
D. 至多有⎡⎤2/m棵子树
8. 若用单链表来表示队列,最适合队列操作的是()。
A. 带尾指针的非循环队列
B. 带尾指针的循环链表
C. 带头指针的非循环链表
D. 带头指针的循环链表
9. 下面的序列中, ( )是堆。
A. 12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49
B. 12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49
C. 12, 36, 27, 20, 40, 34, 98, 81, 73, 55, 49
D. 12, 36, 35, 65, 40, 34, 98, 81, 73, 55, 49
10. 设有一个10阶的对称矩阵A, 采用压缩存储方式, 以行序为主序存储其下三角,a11为第一个
元素, 其首存储地址为1, 每个元素占1个地址空间, 则a85的地址为( ) 。
A. 32
B. 33
C. 34
D. 40
考试科目:数据结构共5页,第1 页
考试科目:数据结构共5 页,第2 页
图1
2. 一棵二叉树,若根结点的左右子树均有三个结点,其左子树的先序序列与中序序列相同,右子树的中序序列与后子序序列相同,试构造该二叉树。
(7分)
3. 已知序列(12,18,4,3,6,13,2,9,19,8)。
请给出采用希尔排序对该序列作升序排序的每一趟结果(步长分别为5,3,2,1)。
(8分)
4. 设有一组关键字(33,41,20,24,30,13,01,67), 采用散列函数H(key)=(3*key) %11, 采用线性探测再散列解决冲突, H i=(H(key)+d i)%11,其中d i=1,2,…,10. 试在0~10的散列地址空间中对该关键字序列(按从左到右的次序)构造散列表,并计算在查找概率相等的前提下,查找成功时的平均查找长度。
(10分)
5.已知图2所示的有向图。
设其顶点a,b,c,d,e表示一个乡的5个村庄,弧上的权值表示为两村之间的距离。
乡内要建立一所学校,问学校设在哪个村庄才能使从各村出发到学校的距离总和最小。
(要求回答解决上述问题应采用什么算法,并写出应用该算法解答上述问题的每一步计算结果)。
(10分)
图2
考试科目:数据结构共5 页,第3 页
考试科目:数据结构共5 页,第4 页
考试科目:数据结构共5 页,第5 页。