南京工业大学
2018年硕士研究生入学考试初试试题（A卷）
科目代码：828科目名称：数据结构与操作系统满分：150分
注意:①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；
③本试题纸须随答题纸一起装入试题袋中交回！
第一部分：数据结构（共90分）
单项选择题（下列每题给出的四个选项中，只有一项符合试题要求。每小题2分，共30分）
1、通常所说的时间复杂度是指。
A.语句的频度
B.算法的时间消耗
C.渐进时间复杂度
D.最坏的时间复杂度
2、等概率条件下,在由n个结点构成的顺序表上做插入结点操作,需平均移动的结点数为。
A.n
B.(n-1)/2
C.n/2
D.(n+1)/2
3、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是。
A.O(1)
B.O(n)
C.O(n2)
D.O(logan)
4、从一个栈顶指针为top的链栈中删除一个结点时,用x保存被删除的结点,20应执行下列命令。
A.x=top:top-top>next
B.top=Top->next;=top>data
B.C.x=Top->data;D,x=Top->data;Top-top->next
5、循环队列SQ队满的条件是。
A.SQ->rear=SQ->froat;
B.(SQ->rear+1)%MAXLEN=SQ->froat
C.SQ->rear+2=SQL->froat
D.(SQ->rear+2)%MAXLEN=SQL>froat
6、某队列允许在两端进行入队操作,但仅允许在一端进行出队操作(称为输出受限的双端队列),若五个元素a,b,c,d,e依次进队,则不可能得到的出队顺序是。
A.bacde
B.dbace
C.dbcae
D.ecbad
7、对特殊矩阵采用压缩存储的目的主要是为了。
A.表达变得简单
B.对矩阵元素的存取变得简单
C.去掉矩阵中的多余元素
D.减少不必要的存储空间
8、一颗具有25个叶结点的完全二叉树最多有个结点。
A.48
B.49
C.50
D.51
9、在线索二叉树中,t所指结点没有左子树的充要条件是。
A.t->left=NULL
B.t->Itag=TRUE
C.t->Itag=TRUE且t->left=NULL
D.以上都不对
10、设有一个二维数组A[m][n],假设A[O][0]存放位置在644,A[2][2]存放位置在676,每个元素占一个空间,则A[3][3]存放位置为。
A.688
B.678
C.692
D.696
11、将一棵树转换为二又树后,这棵二叉村的形态是。
A.唯一的,根结点没有左孩子
B.唯一的,根结点没有右孩子
C.有多种,根结点都没有左孩子
D.有多种,根结点都没有右孩子
12、在图1中,从顶点a 出发,按深度优先遍历,不可能得到的顶点的序列为。
A.a,b,e,c,d,f
B.a,b,e,c,f,d
C.a,c,d,f,b,e
D.a,b,c,d,f,e
13、下面关于工程计划的AOE 网的叙述中，不正确的是。
A.关键活动不按期完成就会影响整个工程的完成时间
B.任何一个关键活动提前完成，那么整个工程将会提前完成
C.所有关键活动都提前完成，那么整个工程将会提前完成
D.某些关键工程若提前完成，那么整个工程将会提前完成
14、分别以下列列序构造二叉排序数(二叉查找树,与用其他三个数列所构造的结果不同的是。
A(30,10,40,5,50,20,35) B.(30,40,5,50,10,20,35)
C.(30,40,10,50,5,35,20)
D.(30,10,5,20,40,50,35)
15、有一组关键字(3,12,258,33,15,22,64,20,55,26),采用除留余数法构造散列函数,H(key)=key mod 11,则将发生次冲突。
A.3
B.4
C.5
D.6
二、综合应用题（5小题，共60分）
16、已知一个箭头结点的单项箭表,试完成函数vold copyList(LIST h1,list &h2),实现将链表h1中的所有元素复制到链表h2中,具体要求如下:
(1)定义链表的结点的抽象数据类型node,其所包涵的数据为:int data,并定义链表结点的型LIST(node 类型的指针);
(2)在(1)的基础上完成函数copyList 。
17、试完成求二叉树的叶子结点的函数int leafNunt(BTREE,T),具体如下:
(1)定义用左右键方法表示的二叉树的抽象数据类型node 和型BTREE(node)类型的指针,
(2)编写函数leafNunt(BREE T),返回树T 的叶子结点的个数。
18、现在所有如下9个元素:7、16、49、82、5、31、6、2、44,画出将每个元素依次插入堆中构成最大堆的过程,具体要求如下,用第一个元素7构成一个二叉树,然后将第二个元素16插入该二叉树中,再将第三个元素49插入堆中直到最后一个元素插入为止。上述每一个插入过程都要求画图完成,并标注每一个结点插入的初始位置以及调整路线和调整后的位置。
19.给定如图2所示的有向网络,利用Dijkstra 法求从顶点v1
到其他各定点的最短路径。V1V3V4V6
V2V545
10
101530151520602015
具体要求如下
(1)填写下表,模拟Dijkstra算法的实现过程。其中S为当前已考虑的点的集合；w为每一步加入集合S的点的编号;D[i]为v1到vi的最高距离(如果v到vi之间还没有通路,则D[i]为INF);p[i]
为v1到vi的最短路径中离vi最近的点。
(2)根据上表中的D的值,求v1到其他各顶点之间的距离
(3)根据上表中的P的值,求v1到其他各顶点之间的最短路径,并简要说明求解过程。
20、给定AOE网如图3所示(起始点为V1,结束点为V10)；
(1)分别计算每个事件Vi的最早发生时间VE(i)和最迟发生时间VL(i)。
(2)根据(1)的结果,分别计算每个活动ai的最早发生时间E(i)和最迟发生时
间L(i)
(3)根据(2)的结果,求得关键活动。并画出表示关键活动的有向图。
步骤S W D[2]D[3]D[4]D[5]D[6]P[2]P[3]P[4]P[5]P[6]初态1—4515INF15INF11111
2
3
4
5
6
第二部分:操作系统(共60分)
一、单项选择题
1、操作系统是一组。
A.文件管理程序
B.中断处理程序
C.资源管理程序
D.设备管理程序
2、现化操作系统的两个基本特征是和资源共享。
A.多道程序设计
B.中断处理程序
C.程序的并发执行
D.实现分时与实时处理
3、进程控制块是描述进程状态和特性的数据结构,一个进程。
A.可以有多个进程控制块
B.可以和其他进程共用一个进程控制块
C.可以没有进程控制块
D.只能有唯一的进程控制块
4、采用时间片轮转法进行进程调度是为了。
A.多个终端都能得到系统的及时响应
B.先来先服务
C.优先级较高的进程得到及时响应
D.需要CPU最短的进程先做
5、资源的有序分配策略破坏条件,是一种死锁预防策略。
A.互斥条件
B.保持和请求条件
C.不剥夺条件
D.环路等待条件
6、按照作业到达的先后次序调度作业,排队等特时间够长的作业被优先调度,
这是指调度算法
A.先来先服务
B.最短作业优先
C.定时轮转法
D.优先数法
7、在存储管理中,为实现地址映射,硬件应提供两个容存器,一个是基址寄存
器,另一个是。
A.控制寄存器B,程序状态寄存器
C.限长寄存器
D.通用寄存器
8、很好地解决了内存“碎片”问题的存储管理方式是。
A分页存储管理 B.分段存储管理
C.可变分区存储管理
D.固定分区存储管理
9、现在现代操作系统中采用缓冲技术的主要目的是。
A.改善用户编程环境
B.提高CPU的处理速度
C.提高CPU和设备之间的并行程度
D.实现设备与无关性
10、索引式(随机)文件组织的一个主要优点是。
A.不需要链接指针
B.能实现物理的动态分配
C.回收实现比较简单
D.用户存取方便
二、计算题
11、桌上有一空盘,允许存放一只水果。爸爸可向盘中放苹果,也可向盘中放橘子,儿子专等吃盘中的橘子,女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用,请用P,V 原语实现爸爸儿子、女儿三个并发进程的同步。
12、假设有四个作业的单道系统。它们的提交、运行时间如下表所示(时间单位:
小时,以十进制进行计算)。
若采用越于优先权的非抢占式调度算法(优先数高者优先权低)
试回答
(1)作业应以怎样的顺序调度?给出分析过程。
(2)计算平均带权周转时间。
作业号到达时间运行时间优先数
A8.0 2.04
B8.50.56
C9.00.22
D9.5 1.05
13、在分页存储管理系统中,存取一次内存的时间是8ns,查询一次快表的时间
是1ns,缺页中断的时间是20ns。
假设页面的查询与快表的查询同时进行,当查询页表时,如果该页在内存但快表
中没有页表项,系统将自动把该页页表项送入快表，一个作业最多可能保留3个
页面内存,现在开始执行一作业,系统连续对作业的2,4,5,2,7,6,4,8页面的数据进行一次存取,如分别采用FIFO算法和最优页面置算法,求每种算法存取这些
数据需要的总时间。
14、旋转型设备上信息的优先化分布能减少若干个I/O服务的总时间。设磁鼓上
分为20个区,每区存放一个记录,磁鼓旋转一周需20毫秒,读出每个记录平均
需用1毫秒,读出后经2毫秒处理,再继续处理下一个记录。在不知当前磁鼓位
置的情况下,
(1)顺序存放记录1、…、记录20时,试计算读出并处理20个记录的总时间;
(2)给出优先分布20个记录的一种方案,使得所花的总处理时间减少,且计算出这个方案所花的总时间。
土木工程学院 2016年硕士研究生复试方案及录取办法一、复试名单及复试分数线 二、复试安排 1．报到时间：2016年 3 月17 日，上午 9：00-12：00；下午 13：00-16：00。 2．报到地点：南京工业大学江浦校区，地坤楼 409。 3. 复试费 80 元/人，报到时交学院。考生复试期间的食宿费、往返路费，本人自理。 4．体检分两天进行，时间为3月17日、18日，上午8：30－12：00，下午12：30－16：00，请考生合理选择时间段自行前往。 体检地点：浦口区浦珠南路30号，南京工业大学江浦校区校医院（北苑旁）； 体检费：25元/人（体检现场缴纳）；请各位考生体检时带1寸照片一张（贴在体检表上）5．考生报到时必须持下列资料：
1）2016年硕士研究生入学考试准考证。 2）证件：往届生需持本人身份证原件及复印件1份、学历证书原件及复印件1份、学位证书原件及复印件1份、《教育部学历证书电子注册备案表》打印件（网址https://www.doczj.com/doc/e54384563.html,/xlcx/）； 应届本科生需持本人身份证原件及复印件1份、学生证原件、《教育部学籍在线验证报告》的打印件（网址https://www.doczj.com/doc/e54384563.html,/index.action）； 因毕业时间早而不能在线验证的，需提供教育部《中国高等教育学历认证报告》原件（网址https://www.doczj.com/doc/e54384563.html,/xlrz/）。 3）成绩单：本科段学习成绩单原件（用于验证）；往届生可从本人档案中复印一份并加盖档案部门公章，报到时交给学院验证； 4）英语水平证明：考生需带英语等级证书原件或成绩单原件进行验证，并复印一份报到时交给学院。 5）个人政审材料。应届本科毕业生由所在学校所在院（系）党组织填写并加盖公章；非应届毕业生由档案所在单位或户口所在单位填写并加盖公章。 6）录取专业调剂申请表 6. 复试安排 （1）复试形式及安排
数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素
2013年4月份自考操作系统试题及答案 操作系统试题 课程代码：02326 本试卷分为两部分，满分100分；考试时间为150分钟。 一、单项选择题（本大题共20小题，每小题1分，共20分） 1、开发UNIX第一个版本所使用的计算机是（ A ） A、PDP-7 B、PDP-8 C、PDP-11/45 D、PDP-11/70 2、操作系统提供给程序员级使用的接口是（D） A、操作控制命令 B、过程调用 C、作业控制语言 D、系统功能调用 3、下面关于管态和目态的叙述中不正确的是（ D ） A、中央处理器执行系统程序的状态是管态 B、中央处理器执行用户程序的状态是目态 C、目态下不允许执行特权指令 D、访管指令只能在管态下执行(在目态下执行) 4、UNIX用于改变对文件访问权限的命令是（ D） A、chmod B. rename C、link D、lseek 5、采用多道程序设计技术不必注意的是(D ） A、主存储器的保护 B、主存的程序浮动 C、系统资源的分配和调具体功能 D、用户程序的具体功能 6、不属于进程控制原语的是（ D） A、创建原语 B、撤销原语 C、唤醒原语 D、互斥原语(阻塞原语) 7、不属于进程特（C ） A、动态性性 B、并发性 C、同步性 D、异步性 8、申请启动了外围设备，该进程状态的变化是（ D ） A、成等待状态 B、从运行状态变成就绪状态 C、状态变成就绪状态 D、从就绪状态变成运行状态
9、采用多道程序设计后，用户在程序中使用的地址称为（ C ）逻辑地址 A、静态地址 B、绝对地址 C、相对地址 D、物理地址 10、在早期的分时系统中，让多个用户的作业轮流进入主存储器执行。先把一个作业装入主存储器执行，当出现等待事件或用完一个时间片时，把该作业从主存换出，再把由调度程序选中的另一作业调到主存中。这种技术称为（B ） A、覆盖技术 B、对换技术 C、移动技术 D、调度技术 11、采用页式存储管理的系统中，若相对地址用32位表示，其中20位表示页号，则可以表示的页内地址范围是（ C） A、0~1023 B. 0～2047 C、0～4095 D、0—8191 12、在页式虚存系统中，将近期访问次数最少的页面调出的页面调度算法是（ B ） A、最佳调度算法(OPT) B、最近最不经常使用调度算法(LFU) C、先进先出调度算法(FIFO) D、最近最久未使用调度算法(LRU) 13，UNIX文件系统分成基本文件系统和子文件系统两部分，说法正确的是（C ） A、两部分都可以装卸 B、两部分都不可以装卸 C、两部分都有自己独立的目录结构 D、两部分都没有自己独立的目录结构 14、文件系统提供了一些基本文件操作，下面不属于基本文件操作的是（D） A、建立文件、删除文件 B、打开文件、关闭文件 C、读文件、写文件 D、移动文件、复制文件 15、具有“设备独立性”的计算机系统中，下列说法正确的是（D） A、在分配设备时适应性好，灵活性强 B、用户编制程序时，对欲使用的设备需要指定 C、用户编制程序时，对欲使用的设备仅需相对号 D、用户编制程序时，欲使用的设备与实际关 16、假设读写磁头正在50号柱面上执行出而等待访问者依次要访问的柱面号是60，118，39，15，130。当50号柱，若采用最短寻找时间优先调度算法，为完成这些请求，磁头需要过的( B） A、150 B、170 C、180 D、200
一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1
C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆
答案仅为参考 1.Which of the following scheduling alogrithms could result in starvation and why? (1)First-come,first-served (2)Shortest job first (3)Round robin (4)Priority【来自课后习题】 答：最短工作优先调度和优先级调度算法会引起饥饿。优先级调度算法会使某个低优先级进程无穷等待CPU，此时，可能发生两种情况，要么进程最终能进行，要么系统最终崩溃并失去所有未完成低优先级进程。 解决方式——老化，老化是一种技术，以逐渐增加在系统中等待很长时间的进程的优先级。（最短工作优先调度会使工作长度最大的进入无限等待CPU） 2.Can a resource allocation graph (资源分配图) have cycle without deadlock（死锁）? If so,state why and draw a sample graph（画一个死锁点的图）; if no,state why not? 答：有死锁，死锁部分为P2-R4-P5-R3。 3.What is the cause of thrashing(颠簸)? How dose the system detect（检测）thrashing? Once it detects thrashing,what can the system do to eliminate（消除）this problem?【来自课后习题】 答：分配的页数少于进程所需的最小页数时发生颠簸，并迫使它不断地页错误。该系统可通过对比多道程序的程度来估计CPU利用率的程度，以此来检测颠簸。降低多道程序的程度可以消除颠簸。 4.某Demand Paging system,拥有逻辑空间64页，每页2KB，拥有物理空间1MB。 (1)写出逻辑地址的格式。 解：11位页内地址，5位页号 (2)若不考虑访问权限等，进程的页表最多有多少项？每项至少有多少位？ 解：因为有32个逻辑页面，所以页表有32项。因为有1M/2K= 2的9次方物理块，所以每个页表项至少有9位 (3)如果物理空间减少一半，页表结构应相应作怎样的改变？ 解：32项，每项至少需要8位
模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针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依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( )
一．选择题（每小题1分，共8分） 1.设有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主存储，a[0][0]的存储地址为100，每个元素占1个地址空间，则a[3][2]的地址为（）。 （A）102 （B）105 （C）106 （D）108 2.森林转换为二叉树后，从根结点开始一直沿着右子数下去，一共有4个结点，表明（）。 （A）森林有4棵树（B）森林的最大深度为4 （C）森林的第一棵树有4层（D）森林有4个结点 3.在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）。 （A）e （B）2e （C）n^2－e （D）n^2－2e 4.在内部排序中，排序时不稳定的有（）。 （A）插入排序（B）冒泡排序（C）快速排序（D）归并排序 5.设一数列的顺序为1，2，3，4，5，通过栈结构不可能派成的顺序数列为（）。 （A）3，2，5，4，1 （B）1，5，4，2，3 （C）2，4，3，5，1 （D）4，5，3，2，1 6.一个n条边的连通无向图，其顶点的个数至多为（）。 （A）n－１（B）n（C）n＋１（Ｄ）nlog2n 7.总共3层的完全二叉树，其结点数至少有（）个。 （A）3 （B）4 （C）7 （D）8 8.已知某算法的执行时间为（n^3+n^2+n）log2（n+2），n为问题规模，则该算法的时间复杂度是（）。 （A）O（n）（B）O（n^2） （C）O（log2n）（D）O（n^3log2n） 二．判断题（每题1分，共8分。正确的打√，错误的打×） 1.只要是算法，肯定可以在有限的时间内完成。（） 2.无论是线性表还是树，每一个结点的直接前驱结点最多只有一个。（） 3.不论是行优先还是列优先，二维数组的最后一个元素的存储位置是一样的。（） 4.直接插入排序时，关键码的比较次数与记录的初始排列无关。（） 5.二叉树的先序遍历不可能与中序遍历相同。（） 6.任何一棵二叉树，不可能没有叶子结点。（） 7.一个稀疏矩阵采用三元组法存储不可能是（5，3，7），（5，4，4），（5，3，5）。（） 8.一个无序的顺序表不能采用折半查找法进行查找。（）。
青岛大学2005年硕士研究生入学考试试题 学科代码：407 科目名称：数据结构（共4页）请考生写明题号，将答案全部答在答题纸上，答在试卷上无效 一．单项选择题（本大题共10道小道小题，每小题3分，共30分） 1. 算法的时间复杂度取决于【】 A. 问题的规模 B. 待处理数据的初始状态 C. 软件和硬件的组合 D. 操作系统 2. 向一个栈顶指针为top的链栈中插入一个s结点，则执行【】 A. top->next=s; B. s->next=top->next; top->next=s; C. s->next=top; top=s; D. s->next=top; top=top->next; 3. 广义表（（a））的表头是【】 A. a B. (a) C. () D. ((a)) 4. 由带权为8、2、5、7的叶子结点构造一棵哈夫曼树，该树的带权路径长度为【】 A. 37 B. 32 C. 46 D. 43 5. 采用邻接表存储的图，其BFS算法类似于二叉树的【】 A. 中序遍历 B. 先序遍历 C. 后序遍历 D. 按层遍历 6. 在非空m阶B_树上，除根结点之外的所有其他非终端结点【】 A. 至少有??2/m棵子树 B.至多有??2/m棵子树 C. 至少有??2/m棵子树 D. 至多有??2/m棵子树 7. 对线性表进行顺序查找时，要求线性表的存储结构为【】 A. 散列存储 B. 顺序存储或者链式存储 C. 压缩存储 D. 索引存储 8. 在关键字“基本有序”的情况下，最佳排序算法为【】 A. 快速排序 B. 冒泡排序 C. 直接插入排序 D. 基数排序 9. 折半查找法和二叉排序树的时间性能【】 A. 与处理数据量有关 B. 相同 C. 不相同 D. 不确定 10. 串是一种特殊的线性表，其特殊性体现在【】 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符 二、填空题（本大题共10小题，每小题2分，共20分） 1. 在具有n个单元的循环队列中，队满时共有____________个元素。 2. 单链表中设置头结点的目的是____________。 3. 消除递归_____________需要使用栈。 4. 在具有n(n≥1)个结点的k叉树中，有_____________个空指针。 5. 深度为5的二叉树至多有_________个结点。 6. 一个连通图的__________是一个极小连通子图。 7. 对稀疏图进行DFS遍历时，应该采用___________作为其存储结构。 8. 在哈希表中，装填因子α越大，则_______________________。
学习-----好资料 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是_____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后
A B 开卷闭卷其他
11、假设一个系统有4个页面，页表项的信息如下表所示。Second-chance（clock）算法将置换哪个页面？（ D ） （A）0；（B）1；（C）2；（D）3。 页面加载时间最后访问 时间Valid/Invalid bit Modify bit Reference bit 0 1 2 3 167 321 254 154 374 321 306 331 1 1 1 1 1 1 1 1 12、在11题的表中，哪个页面被置换时需要写回（write back）到磁盘？（C ）（A）0；（B）1；（C）2；（D）3。 13、假设一个系统的逻辑地址空间为32个页面，其中每一个页面占1024字节，物理内存为16个页帧（frame），该系统的逻辑地址和物理地址各需要多少位？（ B ）（A）16，15。 （B）15，14。 （C）15，16。 （D）14，15。 14、下列文件系统的分配方式不具有随机访问能力的是（ C ） （A）单级索引分配。（×） （B）双向链表分配。 （C）单向链表分配。 （D）连续分配。（×） 15、下列哪个数据结构或算法的局部性比较好？（ C ） （A）二分查找（binary search）。 （B）指针。 （C）冒泡排序。 （D）哈希表（hash table）。 16、下面那个缩写表示进程间通信？（ C ） （A）IRQ。 （B）ISR。 （C）IPC。 （D）IVT。 17、关于虚拟内存，哪一个是正确的？（C ） （A）虚拟内存只能通过请求式调页（demand paging）实现。 （B）缺页率总是随着物理内存的增加而减少。（C）在虚拟内存中，有效内存访问时间近似正比于缺页异常（page fault）发生的概率。 （D）一台拥有4GB物理内存的32位计算机永远不会发生缺页异常。 18、请求分页内存管理中，若把页面大小增加一倍，在程序顺序执行时，则缺页异常次数一般会（ B ） （A）增加。 （B）减少。 （C）不变。 （D）可能增加也可能减少。 19、下面哪一个说法是不正确的？（B ） （A）策略和机制分离是操作系统设计应该遵循的重要原则。 （B）如果没有对临界区进行保护，程序每一次运行一定都会得到错误的结果。（C）如果系统采用两级页表结构，则每一个进程必须有独立的页表。 （D）为了获得最好的地址转换性能，页面大小一般都设为2幂次方。 20、哪一个说法是正确的？（D ） （A）资源分配图中如果存在有向环，一定发生了死锁。（×） （B）线程只能在操作系统内核中实现。（×） （C）当进程执行一个除零操作时，将触发一个外部中断。 （D）操作系统获得CPU的控制权时，CPU一定运行在内核模式。 二、简答题（54分） 1、 (10分)列出进程的状态，并画出状态变迁图。 2、 (8分)请写出用信号量解决读者-写者（readers-writers）问题的伪代码。 3、 (6分)竞争条件的解决方法要满足哪些条件？ 4、 (4分)列出死锁的四个必要条件。 5、 (6分)列出三种常见的内存分配方法，并分别描述它们各自的分配算法。 6、 (6分)名词解释：局部性（locality）模型和工作集（working-set）模型。它们有什 么联系？ 7、 (4分)名词解释：颠簸（Thrashing），并给出颠簸发生的条件。 8、 (6分)描述缺页异常的处理流程。 9、 (4分)描述分段内存管理方法，包括分段的原因以及具体的做法。
南京工业大学2016年硕士研究生《土木工程施工》考试大纲 一、考试的基本要求 要求学生熟悉建筑施工个主要工程的施工技术，掌握工艺原理，掌握施工方案的基本内容与编制方法；要求学生树立施工组织的基本理论与施工组织设计的编制方法；培养学生分析、解决一般土木工程施工技术与组织管理的整体能力，并能了解建筑施工新技术、新工艺、新材料、新设备的发展与应用。 二、考试方式和考试时间 闭卷考试，总分150，考试时间为3小时。 三、参考书目（仅供参考） 《土木工程施工》（第2版），郭正兴，东南大学出版社，2012年 四、试题类型： 主要包括填空题、选择题、判断题、名词解析、简答题、计算题等类型，并根据每年的考试要求做相应调整。 五、考试内容及要求 第一部分土方工程 掌握：土的分类和性质；场地平整施工中的竖向规划、土方量计算和施工；基坑开挖施工中的降低地下水位方法，边坡稳定及支护结构设计方法的基本原理；填土压实的要求和方法。 熟悉：常用土方机械的性能和使用方法。 了解：土方施工的特点； 第二部分深基础工程 掌握：各种灌注桩的施工要点、施工全过程及主要优缺点。 熟悉：钢筋混凝土预制桩的预制、起吊、运输及堆放方法。 了解：地下连续墙、墩式基础、沉井基础的施工过程和施工工艺要点。 第三部分砌筑工程 掌握：脚手架的安全技术措施；砖砌体施工工艺、质量要求及保证质量的技术措施；砌块排列组合及错缝搭接要求。 了解：各种砌体材料的物理和力学性能；砌块砌体、石砌体的规格、施工工艺。 第四部分混凝土结构工程 掌握：模板系统的构成、基本形式；模板系统的基本要求；模板的设计方法；各种钢筋连接技术要点；一般混凝土和大体积混凝土的施工工艺和施工方法，包括其施工配料计算、质量检验与评定方法。 了解：钢筋的种类、性能及加工工艺；混凝土结构工程的特点及施工过程；混凝土的冬期施工。 第五部分预应力混凝土工程 掌握：先张法、后张法的施工工艺；预应力混凝土结构施工和使用中的几种预应力损失及其计算方法。 了解：预应力混凝土工程的特点及工作原理；预应力筋的类型、锚夹具及张拉机具。 第六部分结构安装工程 掌握：单层混凝土结构工业厂房结构安装的工艺过程（包括吊装方案和施工方法等）；柱、屋架等主要构件的绑扎、吊升、就位、临时固定、校正、最后固定方法。 熟悉：钢结构吊装的一般方法。 了解：各种起重机械及索具设备的类型、主要构造、技术性能及选用原则。 第七部分防水工程 掌握：卷材防水屋面、涂膜防水屋面的施工要点及质量标准。 熟悉：屋面防水的施工工艺。 了解：卷材防水屋面的构造及各层作用；地下工程的防水方案，卷材防水层、水泥砂浆防水层的构造、
青岛大学2017年硕士研究生入学考试试题 科目代码：910 科目名称：数据结构（共5 页）请考生写明题号，将答案全部答在答题纸上，答在试卷上无效 一、单项选择题（本大题共10 道小题，每小题 2 分，共20 分） 1．计算机算法指的是（）。 A．计算方法B. 排序方法C. 解决问题的步骤序列D. 存储结构 2．链表不具有的特点是（）。 A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 3．连续存储设计时，存储单元的地址（）。 A．一定连续B．一定不连续 C．不一定连续D．部分连续，部分不连续 4．一个递归算法必须包括（）。 A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D. 终止条件和迭代部分 5．栈和队列的共同点是（）。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 6．任何一棵二叉树的叶子结点在先序、中序和后序遍历中的相对次序（）。 A．不发生改变B．发生改变C．不能确定D．以上都不对 7．由带权为{8，2，5，7}的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）。 A．23 B．37 C．46 D 43 8．若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。 A．非连通B．连通C．强连通D．有向 9．适用于折半查找的表的存储方式及元素排列要求为（）。 A．链接方式存储，元素无序B．链接方式存储，元素有序
C．顺序方式存储，元素无序D．顺序方式存储，元素有序 10．对n 个关键字作快速排序，在最坏情况下，算法的时间复杂度是（）。A．O(n) B．O(n2) C．O(nlog2n) D．O(n3) 二、简答题（本大题共 6 道小题，每题5 分，共30 分） 1．如果有n 个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？ 2．有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D 最先出栈（即 C 第一个且 D 第二个出栈）的次序有哪几个？3．简述树与二叉树的转化方法。试举一个例子说明。 4．简要说明图的各种遍历方法。 5．简述顺序查找和折半查找的优缺点。 6．简要说明归并排序的基本思想。 三、综合应用题（本大题共 4 道小题，每题12 分，共48 分） 1．已知一棵二叉树的中序遍历序列为BCAFEC，后序遍历序列为CBECFA，试画出该二叉树，并给出该二叉树的先序序列。 2．对于下图所示的有向图，试给出： (1)邻接表； (2)从顶点v1 出发的深度优先遍历序列； (3)从顶点v3 出发的广度优先遍历序到。 3．设将关键字集合Keys=｛2, 6, 7, 5, 4, 3, 1｝中的元素依次插入到一个空的平衡二叉排序树中，画出所得的平衡二叉排序树。假设查找每一个元素的概率相同，查找此平衡二叉树排序中任一结点的平均查找长度为多少？ 4．某设待排序的关键字集合为{12，2，16，30，28，10，16*，20，6，18}，试分别回答下面的问题。 ①给出希尔排序（增量选取5，3，1）的结果；
四川大学 《数据结构与算法分析》课程 考试模拟试卷 模拟试卷一 一、单选题（每题2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针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依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。
A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而 且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左孩 子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有双 亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整 到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 三、运算题（每题6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调 图2 整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};
2016年4月高等教育自学考试全国统一命题考试 操作系统试卷 (课程代码 02326) 本试卷共7页，满分l00分，考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。4．合理安排答题空间，超出答题区域无效。 第一部分选择题(共30分) 一、单项选择题(本大题共20小题，每小题l分，共20分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡” 的相应代码涂黑。错涂、多涂或来涂均无分。 1、能实现把一个计算问题分成若干个子计算，每个子计算可以在计算机网络中的各计算机上并行执行的操作系统是 A、分布式操作系统 B、网络操作系统 C、多处理器操作系统 D、嵌入式操作系统 2、能使用户通过与计算机相连始终端来使用计算机系统，允许多个用户同时与计算机系统进行一系列交互的是 A、网络操作系统 B、分时操作系统 C、实时操作系统 D、批处理操作系统 3、IBM公司在他们的PC机、工作站和大型机上都配置的UNIX操作系统，被称为 A、4BSD UNIX B、Ultrix C、AIX D、XENIX 4、现代计算机系统的层次结构中，最层是硬件系统，最外层是使用计算机系统的人，介于它们之间的是软件系统。软件系统的层次结构从到外依次为 A、应用软件、系统软件、支撑软件 B、系统软件、支撑软件、应鼹软件 C、系统软件、应用软件、支撑软件 D、支撑软件、系统软件、应用软件 5、当操作系统退出执行，让用户程序执行时，处理器工作状态会 A、继续保持目态 B、继续保持管态 C、从目态转换为管态 D、从管态转换为目态 6、UNIX用于终止子进程执行的系统调用是 A、kill B、exec C、exit D、fork 7、进程在执行过程中其状态不断发生变化，这种特性称为进程的 A、势发性 B、动态幢 C、同步性 D、异步性 8、程序状态字PSW中的“程序基本状态”信息不包括 A、中断码 B、指令地址 C、条件码 D、目态／管态 9、根据作监对资源的要求分类，作数调度从各类作业中去挑选作业，尽可能让使用不同资源的作业同时执行。这样的作业调度算法是 A、先来先服务算法 B、计算时间最短的作业优先算法 C、均衡调度算法 D、优先级调度算法
南京工业大学 土木工程专业《钢结构》课程复习题 一、选择题 1.承压型高强度螺栓连接比摩擦型高强度螺栓连接( B ) A.承载力低，变形大 B.承载力高，变形大 C.承载力低，变形小 D.承载力高，变形小 2.当沿受力方向的连接长度时，螺栓的抗剪和承压设计承载力均应降低，以防止（ B ）。 A、中部螺栓提前破坏； B、端部螺栓提前破坏； C、螺栓受弯破坏； D、螺栓连接的变形过大。 3.为提高轴心受压构件的整体稳定，在杆件截面面积不变的情况下，杆件截面 的形式应使其面积分布（ B ） A．尽可能集中于截面的形心处B．尽可能远离形心 C．任意分布，无影响D．尽可能集中于截面的剪切中心 4.梁整体失稳的方式为（ D ） A.弯曲失稳 B.剪切失稳 C.扭转失稳 D.弯扭失稳 5、对于直接承受动力荷载的结构，宜采用（C ）。 1
A、焊接连接； B、普通螺栓连接； C、摩擦型高强度螺栓连接； D、承压型高强度螺栓连 6.双轴对称焊接工字形单向压弯构件，若弯矩作用在强轴平面内而使构件绕弱轴弯曲，则此构件可能出现的整体失稳形式是( A ) A.平面内的弯曲屈曲 B.扭转屈曲 C.平面外的弯扭屈曲 D.平面内的弯曲屈曲或平面外的弯扭屈曲7．钢材的标准应力-应变曲线是通过下列哪项试验得到的?（ B ）A．冷弯试验B．单向拉伸试验 C．冲击韧性试验D．疲劳试验 8.钢材的抗拉强度f u与屈服点f y之比f u/f y反映的是钢材的( A ) A.强度储备 B.弹塑性阶段的承载能力 C.塑性变形能力 D.强化阶段的承载能力 9.钢结构焊接常采用E43xx型焊条，其中43表示（ A ）A．熔敷金属抗拉强度最小值B．焊条药皮的编号 C．焊条所需的电源电压D．焊条编号，无具体意义 10.在Q345钢的基础上，加入钒可( B ) A.降低钢材的可焊性 B.提高钢材的强度 C.降低钢材的冲击韧性值 D.降低钢材的延伸率 2
硕士入学考试大纲 考试科目代码及名称：910数据结构 一、考试要求 1、掌握数据结构的基本概念、基本原理和基本方法。 2、掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。 3、能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。 二、考试内容 一、线性表 (一) 线性表的定义和基本操作 (二) 线性表的实现 1、顺序存储 2、链式存储 3、线性表的应用 二、栈、队列和数组 (一) 栈和队列的基本概念 (二) 栈和队列的顺序存储结构 (三) 栈和队列的链式存储结构 (四) 栈和队列的应用 (五) 特殊矩阵的压缩存储
三、树与二叉树 (一) 树的基本概念 (二) 二叉树 1、二叉树的定义及其主要特征 2、二叉树的顺序存储结构和链式存储结构 3、二叉树的遍历 4、线索二叉树的基本概念和构造 (三) 树、森林 1、树的存储结构 2、森林与二叉树的转换 3、树和森林的遍历 (四) 树与二叉树的应用 1、二叉排序树 2、平衡二叉树 3、哈夫曼(Huffman) 树和哈夫曼编码 四、图 (一) 图的基本概念 (二) 图的存储及基本操作 1、邻接矩阵法 2、邻接表法 3、邻接多重表、十字链表 (三) 图的遍历
1、深度优先搜索 2、广度优先搜索 (四) 图的基本应用 1、最小(代价) 生成树 2、最短路径 3、拓扑排序 4、关键路径 五、查找 (一) 查找的基本概念 (二) 顺序查找法 (三) 分块查找法 (四) 折半查找法 (五) B-树及其基本操作、B+树的基本概念 (六) 散列(Hash) 表 (七) 字符串模式匹配 (八) 查找算法的分析及应用 六、排序 (一) 排序的基本概念 (二) 插入排序 1、直接插入排序 2、折半插入排序 (三) 冒泡排序(Bubble Sort)