南京工业大学
2014年硕士研究生入学考试初试试题（A卷）
科目代码：828科目名称：数据结构与操作系统满分：150分
注意:①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；
③本试题纸须随答题纸一起装入试题袋中交回！
第一部分：数据结构（共90分）
一、单项选择题（下列每题给出的四个选项中，只有一项符合试题要求。每小题2分，共30分）
1、通常所说的算法的时间复杂度是指。
A.语句的频度
B.算法的时间消耗
C.渐进时间复杂度
D.最坏的时间复杂度
2、将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是。
A.n
B.2n-1
C.2n
D.n-1
3、在一个带头结点的单链表HL中，若要向表头插入一个由指针p所指向的结点，则执行的语句是。
A.HL=p；p→next=HL；
B.p→next=HL，HL=p；
C.p→next=HL；p=HL；
D.p→next=HL→next；HL→next=p；
4、设有一个顺序栈，元素A，B，C，D，E，F依次进栈，如果6个元素出栈的顺序是B，D，C，F，E，A，则栈的容量至少为。
A.3
B.4
C.5
D.6
5、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为。
A.5和1
B.4和2
C.2和4
D.1和5
6、已知串S=“abab”，在KMP模式匹配算法中，其中Next数组值为。
A.0123
B.0121
C.0112
D.0122
7、在按行优先顺序存储的三元组表中，下列陈述错误的是。
A.同一行的非零元素，是按列号递增次序存储的。
B.同一列的非零元素，是按行号递增次序存储的
C.三元组表中三元组行号是非递减的
D.三元组表中三元组列号是非递减的
8、若广义表A满足Head（A）=Tail（A），则A为。
A.（）
B.（（））
C.（（），（））
D.（（），（），（））
9、在一棵树中，如果结点A有3个兄弟，B是A的双亲，则B的度为。
A.1
B.2
C.2
D.4
10、具有n（n﹥1）个结点的完全二叉树中，结点i（2i﹥n）的左孩子结点是。
A.2i
B.2i+1
C.2i-1
D.不存在
11、G是一个非连通无向图，共有28条边，则该图至少有个顶点。
A.6
B.7
C.8
D.9
12、在下图所示的AOE网中，活动a9（阴影表示）的最早开始时间为。
A.13
B.14
C.15
D.16
13、.假定有K个关键字互为同义词，若用线性探测法把这K个关键字填入Hash表中，至少要进行次探测。
A.K-1
B.K
C.K+1
D.K（K+1）/2
14、下面给出的四种排序方法中，排序过程中的比较次数与序列初始状态无关的是。
A.归并排序
B.插入排序
C.快速排序
D.冒泡排序
15、下列关于m阶B-树的说法错误的是。
A.根结点至多有m棵子树
B.所有叶结点都在同一层次上
C.非叶结点至少有m/2（m为偶数）或m/2+1（m为奇数）棵子树
D.根结点中的数据是有序的
二、综合应用题（5小，共60分）；
16.（本题16分）写一个算法合并两个已排序的线性表（线性表用指针表示（链表），且两个线性表都是升序排列）
要求：
(1)定义线性表节点的结构celltype，其所包含数据element为整型，并定义节点的型LIST （celltype指针的类型定义）和位置的型position。
(2)假设线性表的基本操作已经定义。
(3)在1，2的基础上，完成本题，即编写函数void merge（LIST﹠L，LIST L1，LIST L2），实现将线性表L1和L2合并，其结果存放在L中。
17.（本题10分）已知非空二叉树T，写一个算法，求该树中度为2的结点的个数。
要求：
1、用左右链表示方法定义二叉树的抽象数据类型和型BTREE。
2、假设二叉树的基本操作已定义。
3、编写函数int count2（BTREE T），返回树T中度为2的节点的个数。
18.（本题8分）已知二叉树的先根序列是ABDHKEICFGJ，中根序列是HKDBEIAFCJG，画出此二叉树、并画出后序线索二叉树（带头节点）。
19.（本题民10分）传输一段电文如下：aaaabcabcabcabcdabcdabcdabcdeabcde，通过构造哈夫曼树设计出这段电文中的每个字符（a，b，c，d，e）的哈夫曼编码，并计算整段电文的编码长度。
20.（本题16分）如下图所示的有向网络，利用Dijkstra 算法求从顶点v1到其他各顶点的最短距离和最短路径（填写下表所示的Dijkstra
算法的执行过程）。循环
S W D[2]D[3]D[4]D[5]初X
{v1}-80∞2070
1
2
34第二部分：操作系统（共60分）
一、单项选择题（第小题2分、共24分）
1.若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作是。
Ⅰ、处理越界错Ⅱ、置换页Ⅲ、分配内存
A.仅Ⅰ、Ⅱ
B.仅Ⅱ、Ⅲ
C.仅Ⅰ、Ⅲ
D.仅Ⅰ、Ⅱ、Ⅲ2.若某文件系统索引结点中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是。
A.索引结点的总数
B.间接地址索引的级数
C.地址项的个数
D.文件块大小
3.设文件索引节点中有10个地址项，其中8个地址项是直接地址索引，1个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4B （4字节）。若磁盘索引块和磁盘数据块大小均为1KB （1024字节），则可表示的单个文件最大长度是。
A.1057KB
B.16513KB
C.65800KB
D.163840KB
4.下列文件物理结构中，适合随机访问且易于文件扩展的是。
A ．连续结构 B.索引结构
C.隐式链接结构且磁盘块定长
D.隐式链接结构且磁盘块变长
5.引入高速缓冲的主要目的是。
A.提高CPU 的利用率
B.提高I/O 设备的利用率
C.改善CPU 和I/O 设备之间速度不匹配的情况
D.节省内存
6.某系统采用页式存储管理，页的大小为4KB ，设内存容量为2GB ，内存的分配使用情况采用“位示图”表示，则位示图需要字字。
A.8K
B.16K
C.32K
D.64K
7.在一个分页虚存系统中，设页长1KB ，某用户程序有100页，若该程序的虚页0、1、
2、3、
4、7、14、17已分别装入内存块4、17、18、20、2
5、2
6、30、32中，则该程序中的虚地
址0EC5H和3AC5H对应的物理地址分别是。
A.52C5H和7AC5H
B.52C5H和1EAC5H
C.8AC5H和7AC5H
D.8AC5H和1EAC5H
8.在缺页项处理过程中，操作系统执行的操作可能是。
Ⅰ.修改页表Ⅱ.磁盘I/OⅢ.分配页框
A.仅Ⅰ、Ⅱ
B.仅Ⅱ
C.仅Ⅲ
D.Ⅰ、Ⅱ和Ⅲ
9.已知某虚拟页式系统采用FIEO页面置换算法，对于如下页面引用序列，当窗口尺寸（分
配的内存块数）为3和4时，在T6时刻的驻留集（驻留在内存的页的页号的集合，称为驻
留集）为。
时刻T1T2T3T4T5T6T7T8T9T10引用页1432154322 A.{1，4，5}和{1，2，4，5} B.{1，2，5}和{1，2，4，5}
C.{1，2，5}和{2，3，4，5}
D.{1，4，5}和{2，3，4，5}
10.假定某作业进入输入井的时间为S，被作业调度选中的时间为T，被进程调度选中的时间
为t，得到计算结果的时间为E，则该作业的周转时间为。
A.T-S
B.t-S
C.E-T
D.E-S
11.设与某资源关联的信号量初值为3，当前值为2。若M表示该资源的可用个数，N表示等
待该资源的进程数，则M、N分别是。
A.0、1
B.1、0
C.1、2
D.2、0
12.采用时间片轮转调度算法时，对不同的进程可以规定不同的时间片，一般来说，对进
程给一个较小的时间片比较合适。
A.需运算时间长的
B.需经常启动外设的
C.不需使用外设的
D.排在就绪队列末尾的
二、计算（综合）题（3小题，共36分）
13.（本题12分）设自行车生产车间有两个货架，货架A可以存放8个车架，货架B可以存
放20个车轮；又设有4个工人，他们的活动是重复劳动，分别为：工人1加工一个车架放
入货架A中；工人2、3分别加工车轮放入货架B中（每人每次放入1个车轮）；工人4从
货架A中取一个车架，两从货架B中取两个车轮，组装成一辆自行车。试用PV操作实现四
个工人的合作。
14.（本题12分）请求分页管理系统中，假设某进程的页表内容如下表所示。
页表内容
页号页据（Page frame）号有效位（存在位）
02C8H1
1-0
23A5H1
页面大小为4KB，一次内存的访问时间是60ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为2000ns（已含更新TLB和页表的时间）。进程的驻留集大小固定为2，采用最近最久未使用页面置换算法（LRU）和局部淘汰策略，假设①TLB初始为空；②地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；
③有效位为0表示页面不在内存，产生缺页中断，缺页中断后已获得新调入页所在的页框号，无需再访问页表或快表，设有虚地址访问序列23E2H、1566H、2CB7H。请问：
（1）依次访问上述三个虚地址，各需多少时间？给出计算过程。
（2）基于上述访问序列，虚地址1566H的物理地址是多少？请说明理由。
15.（本题12分）某磁盘的转速为3000（转/分），每个磁道有100个扇区，磁头臂的移动速度为0.3（ms/道），假设当前磁头位于1号柱面1号扇区开始位置，有如下5个要求：请求柱面号磁头号扇区号
1728
27215
3712
429553
5366
试分析对这5个请求如何调度，可使总的花费时间最少？完成这5个请求的最少时间为多少？
数据结构 一、单选题 1. 计算机算法指的是（b ）。 A．程序B．问题求解步骤的描述C．调度方法D．排序方法 2. 以下数据结构中，（a ）个是非线性数据结构。 A．树B．字符串C．队D．栈 3. 对于顺序存储的线性表，访问元素和插入元素的时间复杂度分别为：（c ）。 A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1) 4. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（b ）。 A.p->next=s;s->next=p->next B.s->next=p->next; p->next=s C.p->next=s;p->next=s->next D.p->next=s->next; p->next=s 5. n个顶点的有向图中,含有向边的数目最多为( d ) A．n-1 B．n C．n(n-1)/2 D．n(n-1) 6. 循环队列存储在数组A[0..m]中，则入队时的操作为（ d ） A．rear=rear+1 B．rear=(rear+1)mod(m-1) C．rear=(rear+1)mod m D．rear=(rear+1)mod(m+1) 7. 字符串?ababaabab?的next函数为（d ） A.011232232 B.012341234 C.011122334 D. 011234234 8. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为（ b ）A．9 B．11 C．15 D．不确定 9. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当以列为主序存放时，元素A[5,8]的首地址为（ b ）。A．BA+141 B．BA+180 C．BA+222 D．BA+225 10. n个顶点的带权无向连通图的最小生成树包含(b )个顶点 A．n-1 B．n C．n/2 D．n+1 11．有关二叉树的下列说法正确的是（ b ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 12．关键路径是AOE网中（ a ）。 A．从源点到汇点的最长路径B．从源点到汇点的最短路径 C．最长回路 D．最短路径（从源点到汇点的所有路径中，经过弧的数目最多的路径） 13．若查找每个记录的概率相等，则在具有n个记录的连续文件中采用顺序查找查找一个记录，其平均查找长度ASL为（c）。 A．(n-1)/2 B．n/2 C．(n+1)/2 D．n 14．就平均性能而言，目前最好的内部排序方法是（d ） A．冒泡排序B．希尔排序C．堆排序D．快速排序 15．已知广义表LS=((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e的运算是（d ）A．head(tail(LS)) B．tail (head (LS) C．head(tail(head(tail(LS)))) D．head(tail(tail (head (LS)))) 17．在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：( a ) A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B. 在第i个结点后插入一个新结点（1≤i≤n）
土木工程学院 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/f05267074.html,/xlcx/）； 应届本科生需持本人身份证原件及复印件1份、学生证原件、《教育部学籍在线验证报告》的打印件（网址https://www.doczj.com/doc/f05267074.html,/index.action）； 因毕业时间早而不能在线验证的，需提供教育部《中国高等教育学历认证报告》原件（网址https://www.doczj.com/doc/f05267074.html,/xlrz/）。 3）成绩单：本科段学习成绩单原件（用于验证）；往届生可从本人档案中复印一份并加盖档案部门公章，报到时交给学院验证； 4）英语水平证明：考生需带英语等级证书原件或成绩单原件进行验证，并复印一份报到时交给学院。 5）个人政审材料。应届本科毕业生由所在学校所在院（系）党组织填写并加盖公章；非应届毕业生由档案所在单位或户口所在单位填写并加盖公章。 6）录取专业调剂申请表 6. 复试安排 （1）复试形式及安排
“数据结构”期末考试试题 一、单选题(每小题2分，共12分) 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL； D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空1分，共28分) 1．数据的存储结构被分为——、——、——和——四种。 2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。 3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。 4．在一棵高度为h的3叉树中，最多含有——结点。 5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。 8．表示图的三种存储结构为——、——和———。 9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为——和——· 11．假定对长度n＝144的线性表进行索引顺序查找，并假定每个子表的长度均
数据结构试题样题及答案 一、单项选择题（每小题2分，共30分） 1.数据结构中，与所使用的计算机无关的是数据的（）结构。 A. 逻辑 B. 物理 C. 存储 D. 逻辑与物理 2.下述各类表中可以随机访问的是（）。 A. 单向链表 B. 双向链表 C.单向循环链表 D.顺序表 3.在一个长度为n的顺序表中为了删除第5个元素，从前到后依次移动了15个元素。则原顺序表的长度为（）。 A. 21 B. 20 C. 19 D. 25 4.元素2，4，6按顺序依次进栈，则该栈的不可能的输出序列是（）。 A. 6 4 2 B. 6 2 4 C. 4 2 6 D. 2 6 4 5.一个队列的入队序列是5，6，7，8，则队列的输出序列是（）。 A. 5 6 7 8 B. 8 7 6 5 C. 7 8 6 5 D.可能有多种情况 6. 串函数StrCmp（“d”，“D”）的值为（）。 A．0 B．1 C．-1 D．3 7．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。 A．p=q→next B．p→next=q C．p→next=q→next D．q→next=NULL 8.设一棵哈夫曼树共有n个非叶结点，则该树一共有（）个结点。 A. 2*n-1 B. 2*n +1 C. 2*n D. 2*(n-1) 9.对如图1所示二叉树进行中序遍历，结果是（）。 A. dfebagc B. defbagc C. defbacg D.dbaefcg 图1 10 . 任何一个无向连通图的最小生成树（）。 A.至少有一棵 B.只有一棵 C.一定有多棵 D.可能不存在 11．设有一个10阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素A8,5在一维数组B中的下标是（）。 A．33 B．32 C．85 D．41 12 .一组记录的关键字序列为（37，70，47，29，31，85），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。 A．31，29，37，85，47，70 B．29，31，37，47，70，85
南邮通信原理真题集团标准化办公室：[VV986T-J682P28-JP266L8-68PNN]
南京邮电大学 2014硕士研究生入学考试初试试题 一．选择填空题 选项在本题末。有些选项可以重复选，也可以从不选。 1.信息量定义的原则，它是消息出现（1）的（2）函数，它还必须满足（3）。 2.模拟信道数学模型是（4）；二进制数字信道模型是（5）。 3.若单音调制时，双边带DSB调整值的输出信噪比为SNR=S i/n0f m，其中fm为调制信号带宽，si为接受信号功率，n0为信道噪声功率谱。则下列调制的输出信噪比分别为：调制指数为1的AM调制为（6）；SSB调制为（7）；调制指数为2的FM调制（8）。 4.时域均衡采用（9）滤波器，以消除（10）。 5.数字已调信号的检测=（11）+（12）。 6.格雷码的作用是在数字调制中使得码字的（13）距离与星座点的（14）距离相适应。 7.在数字通信系统中，控制差错的方法有（15)、（16）和（17）三大类。
8.扩展频谱通信用低速率的（18）序列对高速率的（19）序列进行（20），因而提高信号的（21）能力。在无线信道上传输，它能够提供（22）。尽管它占用的频带增大，但是与（23）相结合，不会降低（24）。 9.载波同步和符号同步都可以采用（25）法和（26）法。 a）（1/3）SNR n）汉明 b） 6SNR o）横向 c） ARQ p）解调 d） FEC q) 抗干扰 e） HARQ r）可加性 f） SNR s）调制 g） s0（t）=f[s i（t）]+n（t） t）码分多址 h） PN u）码间干扰 i）抽样判决 v）欧式 j）单调减 w）频带利用率 k）导频辅助 x）信号变换
《数据结构》期末考试试卷样卷 成绩＿＿＿＿＿＿＿＿ 一、单项选择题：（每题2分，共30分） 1、以下说法正确的是（）。 A. 数据元素是数据的最小单位 B. 数据项是数据的基本单位 C. 数据结构是带有结构的各数据项的集合 D. 一些表面上很不相同的数据可以有相同的逻辑结构 2、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。 A. 存储结构 B. 存储实现 C. 逻辑结构 D. 运算实现 3、判断一个队列QU（最多元素为m0）为满队的条件是（）。 A. QU->rear-QU->front==m0 B. QU->rear-QU->front-1==m0 C. QU->rear==QU->front D. QU->front==QU->rear+1 4、给定n个数据元素，建立对应的有序单链表的时间复杂度是（）。 A. O(1) B. O(n) C. O(n2) D. O(nlog2n) 5、一个非空广义表的表头（）。 A. 不可能是子表 B. 只能是子表 C. 原子或子表均可 D. 只能是原子 6、设完全二叉树中拥有65 个结点，则其深度为（）。 A. 5 B. 6 C. 7 D. 8 7、根据二叉树的（），可以唯一确定该二叉树的形态。 A. 先序和中序序列 B. 先序和后序序列 C. 中序和后序序列 D. 先序和层序序列 8、若广义表A满足Head(A)=Tail(A)，则A为（）。 A. () B. (()) C. ((),()) D. ((),(),()) 9、下面不正确的说法是（）。 (1)在AOE网中，减少任一关键活动上的权值后，整个工期也就相应减小； (2)AOE网工程的工期为关键活动上的权值之和； (3)在关键路径上的活动都是关键活动，而关键活动也必定在关键路径上。 A. (1) B. (2) C. (3) D. (1) 、(2) 10、图的深度优先遍历算法分别类似于二叉树的（）。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层序遍历 11、从图的邻接矩阵中，容易确定（）。 A. 主对角线的元素全部为1 B. 主对角线的元素不全为0 C. 任意两个顶点之间是否关联 D. 是否为一个连通图 12、顺序查找适用于存储结构为（）的线性表。 A. 散列存储 B. 压缩存储 C. 顺序存储或链式存储 D. 索引存储 13、从具有n个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂度为（）。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 14、在关键字随机分布的情况下，用二叉排序树进行查找，其查找长度与（）量级相当。 A. 顺序查找 B. 折半查找 C. 分块查找 D. 均不是 15、一组记录的关键字序列为{46,79,56,38,40,84}，利用快速排序方法，以第一个记录为基准得到的一次划分是（）。 A. 38,40,46,56,79,84 B. 40,38,46,79,56,84 C. 40,38,46,56,79,84 D. 40,38,46,84,56,79 - 1 -
南京邮电大学 2010年攻读硕士学位研究生入学考试 通信系统原理试题 01-05：DDCBD 06-10：BDDDB 注意事项：所有答案写在答题纸上，并标明每题的题号，计算题要求解题步骤完整，保持卷面整洁。 一、选择题（每题2分，共60分） 1、纠错码的应用可以改善通信系统的误码性能，但是付出的代价是___D___。 A）误码率B）信噪比C）效率D）带宽 2、滚降滤波器信道的应用，是牺牲带宽，换取接收机___D_____。 A）频带利用率B）抗干扰性C）抗噪声性D）抗定时抖动能力3、PCM信号的带宽是相应模拟信号带宽的__C____倍。 A）0.5 B）2 C）20D）0.1 4、单音100%调制AM信号的制度增益约是___B___，SSB的制度增益是______。 A）2，2 B）2/3，1 C）1/3，2 D）1/9，1 ?5、下列不含离散谱只含连续谱的信号是__D__。 A）DPSK，AM B）PSK，FSK C）MSK，PSK D）DSB，PSK 6、要传100kB的基带信号，无码间干扰100%滚降信道的带宽为__B____，这时频带利用率为______。 A）100kHz，2B/Hz B）100kHz，1B/Hz C）150kHz，2B/Hz D）140kHz，2B/Hz 7、偶监督码的最小汉明距离为__D____，则最多可纠正______位错。 A）6，2 B）5，4 C）4，2 D）2，0 8、PCM3032系统帧长为__D____微秒，含码元个数为______位。 A）64，128 B）64，64 C）256，125 D）125，256 9、样值为-139个标准单位，则A律13折统量化编码的极性码为__D____，段落码为______。A）0，110 B）1，100 C）1，101 D）0，100 10、准同步数字序列一次群帧结构含有___B___个非话路时障，故非话音比特的速率为______kbits/s。 A）30，2 B）2，128 C）2，64 D）32，2 11-15：ADBAB 16-20：BDCAB 11、电缆信道中继属于_A_____信道，短波电离层信道属于______信道。 A）恒参，随参B）恒参，时不变C）恒参，恒参D）恒参，定参 ?12、采用多进制信号传输二进制序列可以节省__D____，付出的代价是______。 A）功率，带宽B）时间，复杂度C）带宽，信噪比D）时间，信噪比
2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出
8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点
《433结构力学》考研复习大纲（2007年） 第二章结构的几何构造分析（10分） 掌握几何构造分析的概念及几何不变体系的组成规律，熟悉应用几何不变体系的组成规律进行几何分析； 理解平面杆件体系自由度的计算。 第三章静定结构的受力分析第四章静定结构总论（15分）掌握分段叠加法作内力图，熟悉静定多跨梁、静定框架、静定平面桁架、组合结构的内力分析； 理解三铰拱的压力线，三铰拱的合理轴线的概念。 第五章影响线（10分） 理解移动荷载和影响线的概念； 掌握静力法作影响线、机动法作影响线及影响线的运用； 理解简支梁的包络图和绝对最大弯矩。 第六章结构位移计算与虚功—能量法简述（15分）掌握杆件结构的虚功原理、结构位移计算的一般公式、图乘法、互等定理； 熟悉荷载作用下的位移计算、非荷载作用下的位移计算及广义位移的计算。 第七章力法（20分） 掌握超静定次数的确定； 理解力法的基本概念； 熟悉超静定刚架和排架、超静定桁架和组合结构受力分析（内力计算并绘制内力图）和位移的计算； 熟悉应用对称结构的特性进行受力分析。
第八章位移法（20分） 理解位移法的基本概念； 掌握等截面杆件的刚度方程及位移法的基本体系的确定； 熟悉无侧移刚架、有侧移刚架受力分析（内力计算并绘制内力图）和位移的计算； 熟悉应用对称结构的特性进行受力分析。 第九章渐近法及超静定结构影响线（10分） 理解力矩分配法的基本概念； 掌握多结点的力矩分配、无剪力分配法、力矩分配法与位移法的联合应用； 熟悉力矩分配计算、超静定结构的影响线； 理解连续梁的最不利荷载分布及内力包络图。 第十章矩阵位移法（10分） 掌握单元刚度矩阵（局部坐标系、整体坐标系）、连续梁的整体刚度矩阵、刚架的整体刚度矩阵及等效结点荷载的求解； 熟悉对刚架、桁架进行整体分析； 理解组合结构整体分析。 第十三章结构的动力计算（20分） 掌握单自由度体系的自由振动、单自由度体系的强迫振动、阻尼对振动的影响、多自由度体系的自由振动、多自由度体系主振型的正交性和主振型矩阵及多自由度体系在简谐荷载下的强迫振动； 熟悉近似法求自振频率； 理解多自由度体系在一般动荷载下的强迫振动、无限自由度体系的自由振动； 理解矩阵位移法求刚架的自振频率。
哈尔滨工业大学 二〇〇八年硕士研究生考试模拟试题（一） 考试科目：计算机专业基础 适用专业：计算机科学与技术 I 数据结构（含高级语言）部分（共75分） 一、填空题（每空1分，共9分） +?++的后缀表达式 1.表达式23((12*32)/434*5/7)108/9 是。 2.设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1），则a85 的地址为。 3.设有广义表A=（（（a，b），x），（（a），（b）），（c，（d，（y）））），得到y的对广义表 A的操作序列为。 4.如果二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总节点数 为。 5.G是一个非连通无向图，共有28条边，则该图至少有个顶点。 6.构造n个结点的强联通图，至少有条弧。 7.设表长为1023的有序线性表，查找每个元素的概率相等，采用折半查找方法，查 找成功的ASL是。 8.分别采用堆排序、快速排序、冒泡排序和归并排序，对初太为有序的表，则最省时 间的是算法，最费时间的是算法。 二、单项选择题（每题1分，共11分） 1.静态链表中指针表示的是（） A 下一元素的地址 B 内存储器的地址 C 下一元素在数组中的位置 D 左链或右链指向的元素的地址 2.计算算法的时间复杂度是属于一种（） A 事前统计的方法 B 事前分析估算的方法 C 事后统计的方法 D 时候分析估算的方法 3.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3， 当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（） A 1和5 B 2和4 C 4和2 D 5和1 4.若6行5列的数组以列序为主序顺序存储，基地址为1000，每个元素占2个存储 单元，则第3行第4列的元素（假定无第0行第0列）的地址是（） A 1040 B 1042 C 1026 D 都不正确 5.一棵124个叶节点的完全二叉树，最多有（）个节点。
数据结构期末考试题及标准答案
————————————————————————————————作者：————————————————————————————————日期：
2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。
s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。
得到拟录取消息的前些天一直忐忑不安，想象着自己失败时的沮丧或者自己成功时的兴奋。 终于尘埃落定，内心激动，又面色平静地拿起手机给每一个关心我的家人和朋友发了这个好消息。也想在这里写下自己考研路上的点点滴滴，给自己留一个纪念，也希望大家能从中得到一些收获。 立大志者得中志，立中志者得小志，立小志者不得志。 所以我建议刚开始大家就朝着自己喜欢的，最好的学校考虑，不要去担心自己能不能考上的问题，以最好的学校的标准来要求自己去学习。大家可以去自己想报考的学校官网上下过去的录取分数线，报录比之类的信息给自己一个参考和努力目标。包括找一些学长学姐问下经验也是很有用的。 备考那个时候无论是老师还是同学们都给了我很多的帮助，让我在备考的路上少走了很多的弯路，尤其是那些珍贵的笔记本，现在回想起来依然很是感动，还好现在成功上岸，也算是没有辜负大家对我的期望。 所以想着成功之后可以写一篇经验贴，希望可以帮助大家。话不多说，下面跟大家介绍一下我的经验吧。 文末有笔记和真题下载，大家可自取。 南京工业大学土木水利专硕 初试科目： 101思想政治理论 204英语二 302数学二 834误差理论与测量平差基础或835地理信息系统(GIS)原理或838水处
理微生物学基础或839传热学或831材料力学（土）或832工程地质学或833结构力学或825工程建造与管理 参考书目： 《工程项目管理》，孙剑主编．中国水利水电出版社，2016 《工程力学2》，范钦珊、郭光林主编，高等教育出版社，2011 《材料力学》(第5版)，孙训方，高等教育出版社, 2009 《工程地质》（第二版），石振明，孔宪立主编，中国建筑工程出版社，2011 《工程地质》（第四版），孙家齐，陈新民主编，武汉理工大学出版社，2011 《工程地质》，张忠苗主编，重庆大学出版社，2011 《结构力学I—基本教程》(第3版)，龙驭球包世华袁驷，高等教育出版社，2012 《结构力学II—专题教程》(第3版)，龙驭球包世华袁驷，高等教育出版社，2012 《结构力学》（第2版）（上、下册），朱慈勉张伟平，高等教育出版社，2009 《误差理论与测量平差基础》(第二版)，武汉大学测绘学院测量平差学科组，武汉大学出版社，2009 《误差理论与测量平差基础习题集》，武汉大学测绘学院测量平差学科组，武汉大学出版社，2005 《地理信息系统原理》（第二版），李建松、唐雪华，武汉大学出版社，2015 《水处理生物学》（第五版），顾夏生等编著，中国建筑工业出版社 《环境工程微生物学》(第三版)，周群英、高廷耀，高等教育出版社，2008
数据结构试题（A05） 一、选择题（共10小题，每小题1分，共10分） 1.下面程序段的时间复杂度是( ) m=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) m=m+1； A. O(n2) B.O(m+n+1) C.O(m+n) D. O(n) 2.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是( ) A.p=p->next; B.p->next=p->next->next; C.p->next=p; D.p=p->next->next; 3.在长度为n的顺序表，当在任何位置上删除一个元素的概率相等时，删除一个元素需要移动的元素的平均个数为( ) A.n/2 B.（n-1）/ 2 C.(n+1)/2 D.(n+2)/2 4.一个栈的输入序列为 1 2 3 4 5，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 6.设循环队列中数组的下标范围是1～n，其头尾指针分别为f和r，则其元素个数为( ) A. r-f B. r-f+1 C. (r-f) mod n+1 D. (r-f+n) mod n 7.以下序列不是堆的是( )。 A.（100，85，98，77，80，60，82，40，20，10，66） B.（100，98，85，82，80，77，66，60，40，20，10） C.（100，85，40，77，80，60，66，98，82，10，20） D.（10，20，40，60，66，77，80，82，85，98，100） 8．在有序表（12，24，36，48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为( )。 A. 3 B. 4 C. 5 D. 2 9.在待排序的元素序列基本有序的前提下，效率最高的排序方法是( )。 A.选择排序 B.冒泡排序 C.快速排序 D.插入排序 二、填空题（共20小题，每小题1分，共20分） 1、在单链表中，删除指针P所指结点的后继结点的语句是。 2、线性表的两种存储结构分别是和。 3、己知完全二叉树的第4层有5个结点，则其叶子结点数是。 4、将下三角矩阵A[1….8，1….8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7，5]的地址是。 5、有n个结点的强连通有向图G至少有条弧。 7、在有序表A[1….20]中，采用二分查找算法查找元素值等于A[12]的元素，所
１ XXX 级本科《通信原理》试题（卷） 题 号 1 2 3 4 5 6 7 8 9 总分 分 数 说明：答案要求简明扼要，全部做在考试题（卷）上。 一、 （20分）填 空 １、 数字通信系统的主要优点是 __________ 、_____________、 ________________、________________。 ２、 通信系统的主要质量指标通常用_________和________衡量， FSK 系统指标具体用______ _和_ _______衡 量，FM/PM 系统具体指标用______ 和______ _衡量。 ３、 PCM 量化可以分为 和 。在线性PCM 中，抽样频率为8 KHZ ，对双极性信号编码时 编码器输出码元速率为72 KB ，则量化信噪比为_______dB 。 ４、 ΔM 信号携带着输入信号的_______信息，Σ—ΔM 信号携带着输入信号的_______信息，PCM 信号携带着输入信号的_______信息，。 ５、 窄带高斯噪声的一维随机包络服从_________ 分布，其概率密度函数p （x ）= ；OOK 信号加窄带 高斯噪声的 一维随机包络服从 分布。 ６、 在0—-T 时刻内高度为A 的矩形信号，与之相匹配 姓 名 学 号 期 班 密 封 线
的滤波器的单位冲激响应h（t）图形为，传递函数H(ω)= ,最大输出信噪比r0max= ,最大信噪比出现的时刻t o=。 ７、门限效应是；用示波器观察眼图的方法步骤是 （1）， （2）。 ８、二进制代码1011000000000000101的差分码是；HDB3码是+1 。 9、在ΔM系统中，输入信号f(t)=Acosωk t，抽样速率为f s，量化台阶为δ，要求系统不出现过载现象，而且能正常编码，输入信号f(t)的幅度范围应为。 10、信道带宽为6 MHz，信号功率与噪声谱密度之比为6 MHz，则信道最大传输速率为，当信道带宽B趋向无穷大时，则信道最大传输速率为。二、（15分）已知语音信号的最高频率fm为4kHz,幅度范围为（-5.120V，+5.120V）,采用13折线法对其进行PCM，试回答计算下列问题： 1求当采样值为-1.450V时编码器的输出C0C1C2C3C4C5C6C7（设段内码为戈雷码）； 2求量化误差为多少（伏）； ２
2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序
南京工业大学2016年硕士研究生《土木工程施工》考试大纲 一、考试的基本要求 要求学生熟悉建筑施工个主要工程的施工技术，掌握工艺原理，掌握施工方案的基本内容与编制方法；要求学生树立施工组织的基本理论与施工组织设计的编制方法；培养学生分析、解决一般土木工程施工技术与组织管理的整体能力，并能了解建筑施工新技术、新工艺、新材料、新设备的发展与应用。 二、考试方式和考试时间 闭卷考试，总分150，考试时间为3小时。 三、参考书目（仅供参考） 《土木工程施工》（第2版），郭正兴，东南大学出版社，2012年 四、试题类型： 主要包括填空题、选择题、判断题、名词解析、简答题、计算题等类型，并根据每年的考试要求做相应调整。 五、考试内容及要求 第一部分土方工程 掌握：土的分类和性质；场地平整施工中的竖向规划、土方量计算和施工；基坑开挖施工中的降低地下水位方法，边坡稳定及支护结构设计方法的基本原理；填土压实的要求和方法。 熟悉：常用土方机械的性能和使用方法。 了解：土方施工的特点； 第二部分深基础工程 掌握：各种灌注桩的施工要点、施工全过程及主要优缺点。 熟悉：钢筋混凝土预制桩的预制、起吊、运输及堆放方法。 了解：地下连续墙、墩式基础、沉井基础的施工过程和施工工艺要点。 第三部分砌筑工程 掌握：脚手架的安全技术措施；砖砌体施工工艺、质量要求及保证质量的技术措施；砌块排列组合及错缝搭接要求。 了解：各种砌体材料的物理和力学性能；砌块砌体、石砌体的规格、施工工艺。 第四部分混凝土结构工程 掌握：模板系统的构成、基本形式；模板系统的基本要求；模板的设计方法；各种钢筋连接技术要点；一般混凝土和大体积混凝土的施工工艺和施工方法，包括其施工配料计算、质量检验与评定方法。 了解：钢筋的种类、性能及加工工艺；混凝土结构工程的特点及施工过程；混凝土的冬期施工。 第五部分预应力混凝土工程 掌握：先张法、后张法的施工工艺；预应力混凝土结构施工和使用中的几种预应力损失及其计算方法。 了解：预应力混凝土工程的特点及工作原理；预应力筋的类型、锚夹具及张拉机具。 第六部分结构安装工程 掌握：单层混凝土结构工业厂房结构安装的工艺过程（包括吊装方案和施工方法等）；柱、屋架等主要构件的绑扎、吊升、就位、临时固定、校正、最后固定方法。 熟悉：钢结构吊装的一般方法。 了解：各种起重机械及索具设备的类型、主要构造、技术性能及选用原则。 第七部分防水工程 掌握：卷材防水屋面、涂膜防水屋面的施工要点及质量标准。 熟悉：屋面防水的施工工艺。 了解：卷材防水屋面的构造及各层作用；地下工程的防水方案，卷材防水层、水泥砂浆防水层的构造、
要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题（每小题2分，共20分） 1. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 。 A. 数据的处理方法 B. 数据元素的类型 C. 数据元素之间的关系 D. 数据的存储方法 2. 下述函数中对应的渐进时间复杂度（n 为问题规模）最小是 。 (n)=nlog 2n+5000n (n)=n 2 -8000n (n)= n n 2 log -6000n (n)=7000log 2n 3. 设线性表有n 个元素，以下操作中， 在顺序表上实现比在链表上实现效率更高。 A.输出第i （1≤i ≤n ）个元素值 B.交换第1个元素与第2个元素的值 C.顺序输出这n 个元素的值 D.输出与给定值x 相等的元素在线性表中的序号 4. 设n 个元素进栈序列是p 1，p 2，p 3，…，p n ，其输出序列是1，2，3，…，n ，若p 3=3，则p 1的值 。 A.可能是2 B.一定是2 C.不可能是1 D.一定是1 5. 以下各种存储结构中，最适合用作链队的链表是 。 A.带队首指针和队尾指针的循环单链表 B.带队首指针和队尾指针的非循环单链表 C.只带队首指针的非循环单链表 D.只带队首指针的循环单链表 6. 对于链串s （长度为n ，每个结点存储一个字符），查找元素值为ch 的算法的时间复杂度为 。 (1) (n) (n 2) D.以上都不对 7. 设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素a[3][5]的存储地址为1000，则a[0][0]的存储地址是 。 8. 一个具有1025个结点的二叉树的高h 为 。 ～1025 ～1024 9. 一棵二叉树的后序遍历序列为DABEC ，中序遍历序列为DEBAC ，则先序遍历序列为 。 10. 对图1所示的无向图，从顶点1开始进行深度优先遍历；可得到顶点访问序列 。
2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。
s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。