北京邮电大学2016年硕士研究生入学考试试题考试科目：计算机学科基础综合请考生注意：①所有答案（包括选择题和填空题）一律写在答题纸上，否则不计成绩。
②不允许考生使用计算器。
一、单项选择题（每小题2分，共80分）1.以下与数据的存储结构无关的术语是A.循环队列B.线索树C.栈D.数组2.若双栈共享空间S[0.n-1]，初始时topl=-1、top2=n，则判栈满为真的条件是A.topl==top2B.topl-top2=1C.topl+top2=nD.top2-topl=13.若用带头结点的单循环链表表示非空队列，队列只设一个指针Q，则插入新元素结点P的操作语句序列是A.P->next=Q->next；Q->next=P；Q=PB.Q->next=P；P>next=Q->next；Q=PC.P->next=Q->next->next；Q=PD.p->next=Q->next；Q=P4.模式串"abaabcac”的nextval数组值是A.01122312B.01021302C.00011201D.010112015.数组A[0..7][0..9]中，每个元素占用3个存储单元，起始存储地址是1000，则数组元素A[5][3]的存储地址是A.1126B.1141C.1156D.11596.在一棵具有20个关键字的3阶B树中，含关键字的结点个数至少是A.10B.11C.12D.137.关键路径是AOE网络中A.从源点到汇点的最长路径B.最长回路C.从源点到汇点的最短路径D.最短回路8.具有n个顶点的强连通图，边数最少是A.2nB.n+lC.nD.n-19.下述顺序存储结构排序算法中，关键字比较次数与元素初始排列次序无关的是A.快速排序B.堆排序C.直接插入排序D.简单选择排序10.若一组待排记录的关键字为（46，79，38，40，84），利用堆排序建立的初始堆为A.（38，40，46，79，84）B.（84，79，46，40，38）C.（84，79，38，46，40）D.（38，40，84，79，46）11.在关键字随机分布的情况下，用二又排序树方法进行查找，下列方法中与其平均查找长度数量级相当的是A.顺序查找B.折半查找C.分块查找D.均不正确12.冯诺依曼计算机的特点是I.采用二进制Ⅱ.存储程序Ⅲ.控制流驱动方式Ⅳ.数据流驱动方式A.仅I、ⅡB.仅I、Ⅱ、ⅢC.仅I、Ⅱ、ⅣD.I、Ⅱ、Ⅲ、Ⅳ13.某8位计算机的存储器按字节编址，如果某字节类型变量对应的存储器单元的值为10000010，那么我们可得出如下结论A.无法得出结论B.这是一个补码C.值为130D.这是一个负数14.下列关于IEEE754浮点数格式的叙述中，正确的是A.尾数和阶码均用原码表示B.尾数用补码表示、阶码用原码表示C.只能表示规格化数D.可以表示规格化数和非规格化数15.一个八体低位交叉存储器，每个存储体的容量为256M*64位，若每个体的存储周期为80ns，那么该存储器能提供的最大带宽是A.426.67MB/sB.800MB/SC.213.33MB/SD.400MB/S16.一个八路组相联Cache共有64块，主存共有8192块，每块64个字节，那么主存地址的标记x、组号y、和z块内地址分别是A.x=4，y=3，z=6B.x=1，y=6，z=6C.x=10，y=3，z=6D.x=7，y=6，z=617.在某计算机系统中，已知A为累加器，SP为堆栈指示器，Me为Sp指示的栈顶单元，如果进栈操作的顺序是（A）→Ms9，（SP）H1→5P，那么出栈操作的顺序应为A.（Msp）→A，（SP）-1→SPB.（Msp）→A，（SP）+1→sPC.（SP）-1→SP，（Msp）→AD.（SP）+1-SP，（Msp）→A18.在一个具有四级流水线的浮点加法器中，假设四个阶段的时间分别是T1=60ms、T2=50ns、T3=90ns、T4=80ns，则加法器流水线的时钟周期至少为X；如果采用同样的逻辑电路，但不是流水线方式，则浮点加法所需的时间为Y。
北京邮电大学2017年硕士研究生入学考试试题考试科目：计算机学科基础综合请考生注意：①所有答案（包括选择题和填空题）一律写在答题纸上，否则不计成绩。
②不允许使用计算器一、单项选择题（每小题2分，共80分）1.下列选项中与算法的时间复杂度有关的是A.问题规模B.计算机硬件性能C.编译程序质量D.程序设计语言2.用单链表存储两个各有n个元素的有序表，若要将其归并成一个有序表，最少的比较次数是A.n-lB.nC.2n-1D.2n3.一个队列用只带尾指针的单循环链表存储，则队列插入和删除操作的时间复杂度分别是A.O（l）、O（l）B.O（l）、O（n）C.O（n）、o（l）D.O（n）、O（n)4.已知一个三维数组A[l.15][0.9][-3.6]的每个元素占用5个存储单元，该数组总共需要的存储空间单元数为A.1500B.4050C.5600D.75005.一棵具有n（m>1）个结点的树，其高度最小和最大分别是A.1、log2nB.1、nC.2、nD.log2n、n6.在下列选项中，不能作为树的存储形式是A.孩子链表表示法B.双亲表示法C.按层次的顺序存储表示法D.孩子兄弟表示法7.一个具有n个顶点的强连通图，边数最多是A.n-1B.nC.n（n-1）/2D.n（n-l）8.下列关于图的叙述中，正确的是A.在有向图中，各顶点的入度之和等于各顶点的出度之和。
B.若图的临界矩阵是对称矩阵，则该图一定是连通的无向图。
C.连通分量是无向图中的极小连通子图。
D.用临界表存储图所用的空间大小只与图的顶点数有关。
9.查找有序表中的某一指定元素时，折半查找比顺序查找的比较次数A.一定少B.一定多C.相同D.不确定10.下列关于排序算法的叙述中，正确的是A.算法的稳定性是指在各种情况下的时间效率相差不大的特性。
B.希尔（Shell）排序的实质是多次利用直接插入排序方法。
C.所有时间复杂度为O（n2）的简单排序算法都是稳定的。
北京邮电大学2017年计算机学科基础综合考试真题803北京邮电大学2017年硕士研究生入学考试试题考试科目：计算机学科基础综合请考生注意：①所有答案（包括选择题和填空题）一律写在答题纸上，否则不计成绩。
②不允许使用计算器一、单项选择题（每小题2分，共80分）1.下列选项中与算法的时间复杂度有关的是A.问题规模B.计算机硬件性能C.编译程序质量D.程序设计语言2.用单链表存储两个各有n个元素的有序表，若要将其归并成一个有序表，最少的比较次数是A.n-lB.nC.2n-1D.2n3.一个队列用只带尾指针的单循环链表存储，则队列插入和删除操作的时间复杂度分别是A.O（l）、O（l）B.O（l）、O（n）C.O（n）、o（l）D.O（n）、O（n)4.已知一个三维数组A[l.15][0.9][-3.6]的每个元素占用5个存储单元，该数组总共需要的存储空间单元数为A.1500B.4050C.5600D.75005.一棵具有n（m>1）个结点的树，其高度最小和最大分别是A.1、log2nB.1、nC.2、nD.log2n、n6.在下列选项中，不能作为树的存储形式是A.孩子链表表示法B.双亲表示法C.按层次的顺序存储表示法D.孩子兄弟表示法7.一个具有n个顶点的强连通图，边数最多是A.n-1B.nC.n（n-1）/2D.n（n-l）8.下列关于图的叙述中，正确的是A.在有向图中，各顶点的入度之和等于各顶点的出度之和。
B.若图的临界矩阵是对称矩阵，则该图一定是连通的无向图。
C.连通分量是无向图中的极小连通子图。
D.用临界表存储图所用的空间大小只与图的顶点数有关。
9.查找有序表中的某一指定元素时，折半查找比顺序查找的比较次数A.一定少B.一定多C.相同D.不确定10.下列关于排序算法的叙述中，正确的是A.算法的稳定性是指在各种情况下的时间效率相差不大的特性。
B.希尔（Shell）排序的实质是多次利用直接插入排序方法。
