2016年-2017年东华大学854计算机及软件工程专业基础综合考研真题试题试卷汇编

2015年全国硕士研究生入学统一考试计算机学科专业基础综合试题一、单项选择题：140小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项符合题目要求。

请在答题卡上将所选项的字母涂黑。

1．已知程序如下：int s(int n){ return (n<=0) ? 0 : s(n-1) +n; }void main(){ cout<< s(1); }程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是A．main()->S(1)->S(0) B．S(0)->S(1)->main()C．m ain()->S(0)->S(1) D．S(1)->S(0)->main()2．先序序列为a,b,c,d的不同二叉树的个数是A．13 B．14 C．15 D．163．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是A．24，10，5和24，10，7 B．24，10，5和24，12，7C．24，10，10和24，14，11 D．24，10，5和24，14，64．现在有一颗无重复关键字的平衡二叉树（A VL树）,对其进行中序遍历可得到一个降序序列。

下列关于该平衡二叉树的叙述中，正确的是A．根节点的度一定为2 B．树中最小元素一定是叶节点C．最后插入的元素一定是叶节点D．树中最大元素一定是无左子树5．设有向图G=(V,E)，顶点集V={V0,V1,V2,V3}，边集E={<v0,v1>,<v0,v2>,<v0,v3>，<v1,v3>},若从顶点V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是A．2 B．3 C．4 D．56．求下面带权图的最小（代价）生成树时，可能是克鲁斯卡（kruskal）算法第二次选中但不是普里姆（Prim）算法（从V4开始）第2次选中的边是A．(V1,V3) B．(V1,V4) C．(V2,V3) D．(V3,V4)7．下列选项中，不能构成折半查找中关键字比较序列的是A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508．已知字符串S为“abaabaabacacaabaabcc”. 模式串t为“abaabc”, 采用KMP算法进行匹配，第一次出现“失配”(s[i] != t[i]) 时，i=j=5,则下次开始匹配时，i和j的值分别是A．i=1，j=0 B．i=5，j=0 C．i=5，j=2 D．i=6，j=29．下列排序算法中元素的移动次数和关键字的初始排列次序无关的是A．直接插入排序B．起泡排序C．基数排序D．快速排序10．已知小根堆为8，15，10，21，34，16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是A．1 B．2 C．3 D．411．希尔排序的组内排序采用的是（）A．直接插入排序B．折半插入排序 C．快速排序D．归并排序12．计算机硬件能够直接执行的是（）Ⅰ．机器语言程序Ⅱ．汇编语言程序Ⅲ．硬件描述语言程序A．仅ⅠB．仅ⅠⅡC．仅ⅠⅢD．ⅠⅡⅢ13．由3个“1”和5个“0”组成的8位二进制补码，能表示的最小整数是（）A．-126 B．-125 C．-32 D．-314．下列有关浮点数加减运算的叙述中，正确的是（）Ⅰ. 对阶操作不会引起阶码上溢或下溢Ⅱ. 右规和尾数舍入都可能引起阶码上溢Ⅲ. 左规时可能引起阶码下溢Ⅳ. 尾数溢出时结果不一定溢出A．仅ⅡⅢB．仅ⅠⅡⅣC．仅ⅠⅢⅣD．ⅠⅡⅢⅣ15．假定主存地址为32位，按字节编址，主存和Cache之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（Write Back）方式，则能存放4K字数据的Cache 的总容量的位数至少是（）A．146k B．147K C．148K D．158K16．假定编译器将赋值语句“x=x+3;”转换为指令”add xaddt, 3”，其中xaddt是x 对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB，且Cache使用直写（Write Through）方式，则完成该指令功能需要访问主存的次数至少是（）A．0 B．1 C．2 D．317．下列存储器中，在工作期间需要周期性刷新的是（）A．SRAM B．SDRAM C．ROM D．FLASH18．某计算机使用4体交叉存储器，假定在存储器总线上出现的主存地址（十进制）序列为8005，8006，8007，8008，8001，8002，8003，8004，8000，则可能发生发生缓存冲突的地址对是（）A．8004、8008 B．8002、8007 C．8001、8008 D．8000、800419．下列有关总线定时的叙述中，错误的是（）A．异步通信方式中，全互锁协议最慢B．异步通信方式中，非互锁协议的可靠性最差C．同步通信方式中，同步时钟信号可由多设备提供D．半同步通信方式中，握手信号的采样由同步时钟控制20．若磁盘转速为7200转/分，平均寻道时间为8ms,每个磁道包含1000个扇区，则访问一个扇区的平均存取时间大约是( )A．8.1ms B．12.2ms C．16.3ms D．20.5ms21．在采用中断I/O方式控制打印输出的情况下，CPU和打印控制接口中的I/O端口之间交换的信息不可能是( )A．打印字符B．主存地址C．设备状态D．控制命令22．内部异常(内中断)可分为故障(fault)、陷阱(trap)和终止(abort)三类。

WORD 格式2015 年全国硕士研究生入学统一考试计算机学科专业基础综合试题、单项选择题： 140 小题，每小题 2分，共 80 分。

下列每题给出的四个选项中，只 有一个选项符合题目要求。

请在答题卡上将所选项的字母涂黑。

1．已知程序如下：ints(intn){ return(n<=0)?0:s(n-1)+n; }voidmain(){ cout<<s(1); } 程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是 A ．main()->S(1)->S(0) B ． S(0)->S(1)->main()C ．main()->S(0)->S(1)D ． S(1)->S(0)->main()2．先序序列为 a,b,c,d 的不同二叉树的个数是A ．13B ．14C ．15D ． 163．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫 曼树的是 A ．24，10，5和 24，10，7C ．24，10，10和 24，14，11 4．现在有一颗无重复关键字的平衡二 叉树 序序列。

下列关于该平衡二叉树的叙述中，正确的是B ．24，10，5和 24，12，7 D ．24，10，5和 24，14，6(AVL 树) , 对其进行中序遍历可得到一个降C．最后插入的元素一定是叶节点D．树中最大元素一定是无左子树5．设有向图G=(V,E) ，顶点集V={V0,V1,V2,V3} ，边集E={<v0,v1>,<v0,v2>,<v0,v3> ，<v1,v3>},若从顶点V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是A．2 B．3 C．4 D． 56．求下面带权图的最小(代价)生成树时，可能是克鲁斯卡( kruskal )算法第二次选中但不是普里姆( Prim )算法(从V 4 开始)第 2 次选中的边是A．(V1,V3) B．(V1,V4) C．(V2,V3) D．(V3,V4)专业资料整理WORD格式7．下列选项中，不能构成折半查找中关键字比较序列的是A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508．已知字符串S 为“ abaabaabacacaabaabcc 模式”串.t 为“ abaabc ”采用,KMP算法进行匹配，第一次出现“失配” （s[i]!=t[i]）时，i=j=5, 则下次开始匹配时，i 和j 的值分别是A．i=1 ，j=0 B．i=5 ，j=0 C．i=5 ，j=2 D．i=6 ，j=2A．直接插入排序B．起泡排序C．基数排序D．快速排序10．已知小根堆为8，15，10，21，34，16，12，删除关键字8 之后需重建堆，在此过9．下列排序算法中元素的移动次数和关键字的初始排列次序无关的是A．1 B． 2 C． 3 D．4程中，关键字之间的比较数是11．希尔排序的组内排序采用的是（）14．下列有关浮点数加减运算的叙述中，正确的是（）Ⅰ. 对阶操作不会引起阶码上溢或下溢Ⅱ. 右规和尾数舍入都可能引起阶码上溢Ⅲ. 左规时可能引起阶码下溢Ⅳ. 尾数溢出时结果不一定溢出A ．仅Ⅱ ⅢB ．仅ⅠⅡⅣC ．仅ⅠⅢ ⅣD ．ⅠⅡ ⅢⅣ专业资料整理WORD 格式 15． 为 假定主存地址 32 位，按字节编址，主存 和 Cache 之间采用直接映射方式，主存 块大小 4 个字，每 32 位，采用回写 WriteBack )方式，则能存 4K 字数据 Cache 为 字 ( 放 的 的总容量的位数至少是()A ． 146kB ．147KC ． 148KD ．158K16．假定编译器将赋值语 “ x=x+3; 转”换为指令” addxaddt,3 ，其”xadd 是 x 对应的句 中t 存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相A ．直接插入排序 B ．折半插入排 序 12．计算机硬件能够直接执行的是（）Ⅰ．机器语言程 序A ．仅Ⅰ Ⅱ．汇编语言程 C ．快速排序 D ．归并排序Ⅲ．硬件描述语言程序 C ．仅Ⅰ Ⅲ D ．ⅠⅡ Ⅲ13． 由3 个“1”和 5 个“ 0”组成的8 位二进制补码，能表示的最小整数是（） A ． -126 B ．-125 C ．-32 D ．-3应的TLB，且Cache 使用直写( WriteThrough )方式，则完成该指令功能需要访问主存的次数至少() 是A．0 B． 1 C． 2 D．317．下列存储器中，在工作期间需要周期性刷新的是()A．SRAM B．SDRAM C．ROM D．FLASH18．某计算机使用 4 体交叉存储器，假定在存储器总线上出现的主存地址(十进制)序列为8005，8006，8007，8008，8001，8002，8003，8004，8000，则可能发生发生缓存冲突的地址对是()A．8004 、8008B．8002、8007C．8001 、8008D．8000、800419．下列有关总线定时的叙述中，错误的是()A ．异步通信方式中，全互锁协议最慢B．异步通信方式中，非互锁协议的可靠性最差C．同步通信方式中，同步时钟信号可由多设备提供D．半同步通信方式中，握手信号的采样由同步时钟控制20．若磁盘转速为7200 转/ 分，平均寻道时间为8ms,每个磁道包含1000 个扇区，则访问一个扇区的平均存取时间大约是()A．8.1ms B．12.2ms C．16.3ms D．20.5ms21．在采用中断I/O 方式控制打印输出的情况下，CPU和打印控制接口中的I/O 端口之间交换的信息不可能是()A．打印字符B．主存地址C．设备状态D．控制命令22．内部异常(内中断)可分为故障(fault) 、陷阱(trap) 和终止(abort) 三类。

2016年哈工大计算机科学与技术专业854考研真题I．数据结构一、选择题1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。

Int x = n * n;While (x >= 1) {X = x / 2;}A.O(log2n)B.O(n)C.O(nlog2n)D.O(n1/2)2.需要分配一个较大的存储空间并且插入和删除操作不需要移动，元素满足以上特点的线性表存储结构是（）。

A.单向链表B.静态链表C.线性链表D.顺序表3.已知字符串S为”ababcabcacbab”，模式串T为”abcac”。

若采用KMP算法进行模式匹配，则需要（）遍（趟匹配），就能确定T是S的子串。

A. 3B. 4C. 5D. 64.已知某棵二叉树的前序序列是1,2,3,4，则不可能为该二叉树的中序序列的是（）。

A.1,2,3,4B.2,3,4,1C.1,4,3,2D.3,1,4,25.将森林F转换为对应的二叉树T，F中任何一个没有右兄弟的结点，在T中（）。

A.没有左子树B.没有右子树C.没有左子树和右子树D.以上都不对6.一个含有n个顶点和e条边的无向图，在其邻接矩阵存储结构中共有（）个零元素。

A. eB.2eC.n2-2eD.n2-e7.在一棵高度为2和7阶B树中，所含关键字的个数最少是（）。

A. 5B.7C.8D.148.设待排序的元素个数为n，则基于比较的排序最坏情况下的时间复杂度的下界为（）。

A.log2nB.nC.nlog2nD.n29.下面关于B树和B+树的叙述中，不正确的是（）。

A.B树和B+树都能有效地支持随机检索B.B树和B+树都能有效地支持顺序检索C.B树和B+树都是平衡的多路树D.B树和B+树都可以用于文件的索引结构10.若待排序关键字序列在排序前已按其关键字递增顺序排列，则采用（）方法比较次数最少。

A.插入排序B.快速排序C.堆排序D.选择排序二、填空题11.在一棵n个结点的二叉树中，所有结点的空子树个数为11 。

文档来源为 :从网络收集整理 .word 版本可编辑 .欢迎下载支持2015年全国硕士研究生入学统一考试计算机学科专业基础综合试题一、单项选择题： 140 小题，每小题 2 分，共 80 分。

下列每题给出的四个选项中，只 有一个选项符合题目要求。

请在答题卡上将所选项的字母涂黑。

1．已知程序如下： int s(int n) {return (n<=0) ? 0 : s(n-1) +n;}void main() { cout<< s(1); }程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是 A ． main()->S(1)->S(0) B ． S(0)->S(1)->main() C ． main()->S(0)->S(1)D ． S(1)->S(0)->main()2． 先序序列为 a,b,c,d 的不同二叉树的个数是 A ． 13B ．14C ．15D ．163．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫 曼树的是序序列。

下列关于该平衡二叉树的叙述中，正确的是5. 设有向图 G=(V,E)，顶点集 V={V o ,V i ,V 2,V 3}，边集 E={<v 0,v i >,<v 0,v 2>,<v o ,v 3>,<v i ,v 3>}, 若从顶点 V 0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是A. 2 B . 3C . 4D . 56.求下面带权图的最小(代价)生成树时，可能是克鲁斯卡(kruskal )算法第二次选 中但不是普里姆( Prim )算法(从 V 4开始)第 2 次选中的边是A. (V1,V3)B . (V1,V4)C . (V2,V3)D . (V3,V4)A ． 24， 10， 5 和 24，10，7 C ．24，10，10 和 24， 14，114．现在有一颗无重复关键字的平衡二叉树B ．24，10，5 和 24， 12，7 D ．24，10，5 和 24，14，6( AVL 树) ,对其进行中序遍历可得到一个降A .根节点的度一定为 2 C .最后插入的元素一定是叶节点B .树中最小元素一定是叶节点 D .树中最大元素一定是无左子树文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持7. 下列选项中，不能构成折半查找中关键字比较序列的是A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，450&已知字符串S为“ abaabaabacacaabaabcc模式串t为“ abaabc '采用KMP算法进行匹配，第一次出现“失配”(s[i] != t[i]) 时，i=j=5, 则下次开始匹配时，i 和j 的值分别是A．i=1，j=0 B．i=5，j=0 C．i=5 ，j=2 D．i=6，j=29．下列排序算法中元素的移动次数和关键字的初始排列次序无关的是A .直接插入排序B .起泡排序C .基数排序D .快速排序10．已知小根堆为8，15，10，21，34，16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是A. 1B. 2C. 3D. 411.希尔排序的组内排序采用的是()A .直接插入排序B .折半插入排序C .快速排序D .归并排序12.计算机硬件能够直接执行的是()I.机器语言程序n.汇编语言程序川.硬件描述语言程序A. 仅I B .仅I n C .仅I 川D. In出13.由 3 个“ 1 ”和5 个“ 0”组成的8位二进制补码, 能表示的最小整数是()A.-126 B . -125C. -32D. -314.下列有关浮点数加减运算的叙述中, 正确的是()I.对阶操作不会引起阶码上溢或下溢n.右规和尾数舍入都可能引起阶码上溢川.左规时可能引起阶码下溢I V 尾数溢出时结果不一定溢出A.仅n 川 B .仅inv C .仅I川V D. In川V15.假定主存地址为32 位，按字节编址，主存和Cache 之间采用直接映射方式，主存块大小为4 个字，每字32位，采用回写( Write Back )方式，则能存放4K 字数据的Cache 的总容量的位数至少是()A. 146kB. 147KC. 148KD. 158K16.假定编译器将赋值语句“x=x+3;转换为指令” add xaddt, 3,其'中xaddt是x对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB ，文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持且Cache使用直写(Write Through )方式，则完成该指令功能需要访问主存的次数至少是()文档来源为 :从网络收集整理 .word 版本可编辑 .欢迎下载支持A ． 0B ．1C ．2D ．317．下列存储器中，在工作期间需要周期性刷新的是() A ． SRAMB ．SDRAMC ．ROMD ．FLASH18．某计算机使用 4 体交叉存储器，假定在存储器总线上出现的主存地址(十进制)序 列为 8005， 8006，8007， 8008，8001，8002，8003，8004，8000，则可能发生发生缓存冲 突的地址对是()B ．8002、8007C ．8001、 8008D ．8000、8004 19．下列有关总线定时的叙述中，错误的是()A •异步通信方式中，全互锁协议最慢 B. 异步通信方式中，非互锁协议的可靠性最差 C. 同步通信方式中，同步时钟信号可由多设备提供 D. 半同步通信方式中，握手信号的采样由同步时钟控制20. 若磁盘转速为 7200转/分，平均寻道时间为 8ms,每个磁道包含1000个扇区，则访 问一个扇区的平均存取时间大约是 ( )A. 8.1ms B . 12.2msC . 16.3msD . 20.5ms21. 在采用中断I/O 方式控制打印输出的情况下，CPU 和打印控制接口中的I/O 端口之 间交换的信息不可能是 ( )A .打印字符B .主存地址C .设备状态D .控制命令22. 内部异常(内中断)可分为故障(fault)、陷阱(trap)和终止(abort)三类。

2016年全国硕士研究生入学统一考试《计算机学科专业基础综合》真题(总分：150.00，做题时间：180分钟)一、单项选择题(总题数：40，分数：80.00)1.已知表头元素为c的单链表在内存中的存储状态如下表所示现将f存放于1014H处并插入到单链表中，若f在逻辑上位于a和e之间，则a,e,f的“链接地址”依次是（）。

（分数：2.00）A.1010H，1014H，1004HB.1010H，1004H，1014HC.1014H，1010H，1004HD.1014H，1004H，1010H√prev data next结点，正确的语句序列是（）。

（分数：2.00）A.p->next->prev=p->prev;p->prev->next=p->prev;free(p);B.p->next->prev=p->next;p->prey->next=p->next;free(p);C.p->next->prev=p->next;p->prev->next=p->prev;free(p);D.p->next->prey=p->prey;p->prev->next=p->next;fr ee(p);√3.设有如下图所示的火车车轨，入口到出口之间有n条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。

现有编号为1～9的9列列车，驶入的次序依次是8，4，2，5，3，9，1，6，7。

若期望驶出的次序依次为1～9，则n至少是（）。

2.00）A.2B.3C.4√D.54.有一个100阶的三对角矩阵M，其元素mi,j(1≤i≤100，1≤j≤100)按行优先次序压缩存入下标从0开始的一维数组Ⅳ中。

元素m30,30在N中的下标是（）。

（分数：2.00）A.86B.87√C.88D.895.若森林F有15条边、25个结点，则F包含树的个数是（）。

2017考研计算机真题及答案：篇一：2017考研计算机专业考研备考资料2017考研计算机专业考研备考资料计算机专业已成为当前考研最热门专业之一，纵观近几年报名录取情况会发现：报考人数在逐年增加，竞争压力在持续升温，而录取概率却非常小。

今天小编为同学们推荐一些优质权威的计算机专业课复习资料，以帮助同学们提升复习效果。

考试内容计算机科学与技术学科的初试科目调整后为4门：政治理论（100分）、外国语（100分）、数学一（150）和计算机学科专业基础综合（150分）。

计算机学科专业基础综合科目，主要考查考生掌握相关基础知识、基本理论和分析问题解决问题的能力。

考试实行联合命题，考试内容包括：数据结构、计算机组成原理、操作系统和计算机网络。

各阶段资料推荐第一阶段（3～7月）这一阶段为基础复习阶段，复习资料应该选择和大纲吻合的教材以及配套的习题。

数据结构可以选用严蔚敏主编、清华大学出版社出版的C语言版的《数据结构》，习题建议选用李春葆主编、清华大学出版社出版的《数据结构习题与解析》。

计算机组成原理有两个版本的教材可供选择：一个是白中英主编、科学出版社出版的《计算机组织与结构》（最新版是第4版）及配套习题；另一个是唐朔飞主编、高等教育出版社出版的《计算机组成原理》及配套习题。

操作系统建议选用：汤子瀛主编、西安电子科技大学出版社出版的《计算机操作系统》，配套习题可以选用李春葆主编、清华大学出版社出版的《操作系统习题与解析》。

计算机网络选用谢希仁主编、电子工业出版社出版的《计算机网络》（最新版是第5版）及配套习题。

在复习书本知识的基础上，同学们可以配合网络课程学习。

该阶段我们推荐考试点网络免费课程： 2017年考研计算机专业备考指南。

该节课对同学们帮助非常大，尤其是一战学子。

第二阶段（７～10月）第二阶段为强化复习、重点深入阶段，时间一般是7～10月份。

该阶段可以选用的教材有：高等教育出版社出版的的《计算机专业基础综合考试大纲解析》、复旦大学出版社出版的《计算机专业基础综合考试复习指南》。

软件工程专业基础综合考研真题详解1下列关于线程的描述中，错误的是（）。

[2019年408统考]A．内核级线程的调度由操作系统完成B．操作系统为每个用户级线程建立一个线程控制块C．用户级线程间的切换比内核级线程间的切换效率高D．用户级线程可以在不支持内核级线程的操作系统上实现【答案】B查看答案【解析】用户级线程仅存在于用户空间中，与内核无关，其线程库对用户线程的调度算法与OS的调度算法无关，不需要操作系统为每个用户级线程建立一个线程控制块。

2下列选项中，可能将进程唤醒的事件是（）。

[2019年408统考] Ⅰ．I/O结束Ⅱ．某进程退出临界区Ⅲ．当前进程的时间片用完A．仅ⅠB．仅ⅢC．仅Ⅰ、ⅡD．Ⅰ、Ⅱ、Ⅲ【答案】C查看答案【解析】可能唤醒进程的事件包括I/O结束、某进程退出临界区等。

当前进程的时间片用完会引起另一个进程的调度并运行，不是唤醒进程。

3下列关于系统调用的叙述中，正确的是（）。

[2019年408统考] Ⅰ．在执行系统调用服务程序的过程中，CPU处于内核态Ⅱ．操作系统通过提供系统调用避免用户程序直接访问外设Ⅲ．不同的操作系统为应用程序提供了统一的系统调用接口Ⅳ．系统调用是操作系统内核为应用程序提供服务的接口A．仅Ⅰ、ⅣB．仅Ⅱ、ⅢC．仅Ⅰ、Ⅱ、ⅣD．仅Ⅰ、Ⅲ、Ⅳ【答案】C查看答案【解析】系统调用接口是连接操作系统和应用程序的桥梁，而接口是以具体程序中的函数实现的，称之为系统调用，在不同的操作系统中，具有不同的系统调用，但是它们实现的功能是基本相同的。

4下列选项中，可用于文件系统管理空闲磁盘块的数据结构是（）。

[2019年408统考]Ⅰ．位图Ⅱ．索引节点Ⅲ．空闲磁盘块链Ⅳ．文件分配表（FAT）A．仅Ⅰ、ⅡB．仅Ⅰ、Ⅲ、ⅣC．仅Ⅰ、ⅢD．仅Ⅱ、Ⅲ、Ⅳ【答案】B查看答案【解析】文件系统管理空闲磁盘块的数据结构包括位图、链表、文件分配表。

索引结点是指在许多类Unix文件系统中的一种数据结构。

每个索引节点保存了文件系统中的一个文件系统对象的元信息数据，但不包括数据内容或者文件名。

2016考研计算机学科专业基础综合真题及答案一、单项选择题：1-40小题，每小题2分，共80分，下列每小题给出的四个选项中，只有一项符合题目要求的。

请在答题卡上将所选项的字母涂黑。

)1. 设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是x=2;while(xx=2*x;A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)解答：A。

程序中，执行频率最高的语句为“x=2*x”。

设该语句执行了t次，则2t+1=n/2，故t=log2(n/2)-1=log2n-2= O(log2n)。

2. 元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是A.3B.4C.5D.6解答：B。

出栈顺序必为d_c_b_a_，e的顺序不定，在任意一个“_”上都有可能。

3. 已知循环队列存储在一维数组A[0...n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。

若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是A.0,0B.0，n-1C.n-1,0D.n-1，n-1解答：B。

插入元素时，front不变，rear+1.而插入第一个元素之后，队尾要指向尾元素，显然，rear初始应该为n-1,front为0。

4. 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是A.257B.258C.384D.385解答：C。

叶结点数为n，则度为2的结点数为n-1,度为1的结点数为0或1，本题中为1(总结点数为偶数)，故而即2n=768。

5. 若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的中序遍历序列不会是A.1,2,3,4B.2,3,4,1C.3,2,4,1D.4,3,2,1解答：C。

由前序和后序遍历序列可知3为根结点，故(1,2)为左子树，(4)为右子树，C不可能。

2015年全国硕士研究生入学统一考试计算机学科专业基础综合试题一、单项选择题：140小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项符合题目要求。

请在答题卡上将所选项的字母涂黑。

1．已知程序如下：int s(int n){ return (n<=0) ? 0 : s(n-1) +n; }void main(){ cout<< s(1); }程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是A．main()->S(1)->S(0) B．S(0)->S(1)->main()C．m ain()->S(0)->S(1) D．S(1)->S(0)->main()2．先序序列为a,b,c,d的不同二叉树的个数是A．13 B．14 C．15 D．163．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是A．24，10，5和24，10，7 B．24，10，5和24，12，7C．24，10，10和24，14，11 D．24，10，5和24，14，64．现在有一颗无重复关键字的平衡二叉树（A VL树）,对其进行中序遍历可得到一个降序序列。

下列关于该平衡二叉树的叙述中，正确的是A．根节点的度一定为2 B．树中最小元素一定是叶节点C．最后插入的元素一定是叶节点D．树中最大元素一定是无左子树5．设有向图G=(V,E)，顶点集V={V0,V1,V2,V3}，边集E={<v0,v1>,<v0,v2>,<v0,v3>，<v1,v3>},若从顶点V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是A．2 B．3 C．4 D．56．求下面带权图的最小（代价）生成树时，可能是克鲁斯卡（kruskal）算法第二次选中但不是普里姆（Prim）算法（从V4开始）第2次选中的边是A．(V1,V3) B．(V1,V4) C．(V2,V3) D．(V3,V4)7．下列选项中，不能构成折半查找中关键字比较序列的是A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508．已知字符串S为“abaabaabacacaabaabcc”. 模式串t为“abaabc”, 采用KMP算法进行匹配，第一次出现“失配”(s[i] != t[i]) 时，i=j=5,则下次开始匹配时，i和j的值分别是A．i=1，j=0 B．i=5，j=0 C．i=5，j=2 D．i=6，j=29．下列排序算法中元素的移动次数和关键字的初始排列次序无关的是A．直接插入排序B．起泡排序C．基数排序D．快速排序10．已知小根堆为8，15，10，21，34，16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是A．1 B．2 C．3 D．411．希尔排序的组内排序采用的是（）A．直接插入排序B．折半插入排序 C．快速排序D．归并排序12．计算机硬件能够直接执行的是（）Ⅰ．机器语言程序Ⅱ．汇编语言程序Ⅲ．硬件描述语言程序A．仅ⅠB．仅ⅠⅡC．仅ⅠⅢD．ⅠⅡⅢ13．由3个“1”和5个“0”组成的8位二进制补码，能表示的最小整数是（）A．-126 B．-125 C．-32 D．-314．下列有关浮点数加减运算的叙述中，正确的是（）Ⅰ. 对阶操作不会引起阶码上溢或下溢Ⅱ. 右规和尾数舍入都可能引起阶码上溢Ⅲ. 左规时可能引起阶码下溢Ⅳ. 尾数溢出时结果不一定溢出A．仅ⅡⅢB．仅ⅠⅡⅣC．仅ⅠⅢⅣD．ⅠⅡⅢⅣ15．假定主存地址为32位，按字节编址，主存和Cache之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（Write Back）方式，则能存放4K字数据的Cache 的总容量的位数至少是（）A．146k B．147K C．148K D．158K16．假定编译器将赋值语句“x=x+3;”转换为指令”add xaddt, 3”，其中xaddt是x 对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB，且Cache使用直写（Write Through）方式，则完成该指令功能需要访问主存的次数至少是（）A．0 B．1 C．2 D．317．下列存储器中，在工作期间需要周期性刷新的是（）A．SRAM B．SDRAM C．ROM D．FLASH18．某计算机使用4体交叉存储器，假定在存储器总线上出现的主存地址（十进制）序列为8005，8006，8007，8008，8001，8002，8003，8004，8000，则可能发生发生缓存冲突的地址对是（）A．8004、8008 B．8002、8007 C．8001、8008 D．8000、800419．下列有关总线定时的叙述中，错误的是（）A．异步通信方式中，全互锁协议最慢B．异步通信方式中，非互锁协议的可靠性最差C．同步通信方式中，同步时钟信号可由多设备提供D．半同步通信方式中，握手信号的采样由同步时钟控制20．若磁盘转速为7200转/分，平均寻道时间为8ms,每个磁道包含1000个扇区，则访问一个扇区的平均存取时间大约是( )A．B．C．D．21．在采用中断I/O方式控制打印输出的情况下，CPU和打印控制接口中的I/O端口之间交换的信息不可能是( )A．打印字符B．主存地址C．设备状态D．控制命令22．内部异常(内中断)可分为故障(fault)、陷阱(trap)和终止(abort)三类。

软件工程试题及答案第一部分选择题一、单项选择题每小题1分，共20分。

（在每小题的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内）1．在下列工具与环境中（）属于较早期的CASE。

A．基于信息工程CASE B．人工智能CASEC．结构的基于图形CASE D．集成的CASE环境2．Putnam成本估算模型是一个（）模型。

A．静态单变量 B．动态单变量 C．静态多变量 D．动态多变量3．在McCall软件质量度量模型中，（）属于面向软件产品修改。

A．可靠性 B．可重用性C．适应性 D．可移植性4．ISO的软件质量评价模型由3层组成，其中用于评价设计质量的准则是（）A．SQIC B．SQMC C．SQRC D．SQDC5．软件复杂性度量的参数包括（）A．效率 B．规模 C．完整性 D．容错性6．对象实现了数据和操作的结合，使数据和操作（）于对象的统一体中。

A．结合 B．隐藏C．封装 D．抽象7．软件调试技术包括（）A．边界值分析 B．演绎法 C．循环覆盖 D．集成测试8．瀑布模型的存在问题是（）A．用户容易参与开发B．缺乏灵活性 C．用户与开发者易沟通 D．适用可变需求9．软件测试方法中的静态测试方法之一为（）A．计算机辅助静态分析 B．黑盒法 C．路径覆盖 D．边界值分析10．软件生命周期中所花费用最多的阶段是（）A．详细设计 B．软件编码 C．软件测试D．软件维护11．第一个体现结构化编程思想的程序设计语言是（）A．FORTRAN语言B．Pascal语言 C．C语言D．PL/1语言12．程序的三种基本控制结构是（）A．过程、子程序和分程序B．顺序、选择和重复 C．递归、堆栈和队列 D．调用、返回和转移13．在详细设计阶段，经常采用的工具有（）A．PAD B．SA C．SC D．DFD14．详细设计的结果基本决定了最终程序的（）A．代码的规模 B．运行速度 C．质量 D．可维护性15．需求分析中开发人员要从用户那里了解（）A．软件做什么 B．用户使用界面 C．输入的信息 D．软件的规模16．结构化程序设计主要强调的是（）A．程序的规模 B．程序的效率C．程序设计语言的先进性D．程序易读性17．IDEF。

[考研类试卷]计算机专业基础综合数据结构（集合）历年真题试卷汇编5.doc[考研类试卷]计算机专业基础综合数据结构（集合）历年真题试卷汇编5一、填空题1 对于具有144个记录的文件，若采用分块查找法，且每块长度为8，则平均查找长度为__________。

【北方交通大学2001二、8】2 有一个2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是 (1)，分成 (2) 块最为理想，平均查找长度是 (3) 。

【中国矿业大学2000一、6(3分)】3 分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成__________块最好；若分成25块，其平均查找长度为__________。

【北京工业大学1999一、5(2分)】4 执行顺序查找时，储存方式可以是(1)，二分法查找时，要求线性表(2)，分块查找时要求线性表(3)，而散列表的查找，要求线性表的存储方式是(4)。

【山东大学1998一、1(3分)】5 查找是非数值程序设计的一个重要技术问题，基本上分成(1)查找，(2)查找和(3)查找。

处理哈希冲突的方法有(4)、(5)、(6)和(7)。

【华北计算机系统工程研究所1999一(5分)】6 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。

【山东大学1999二、1(4分)】7 在含有n个结点的二叉排序树中查找一个关键字，进行关键字比较次数的最大值是__________。

【北京交通大学2004一、15(2分)】8 在二叉排序树上成功地找到一个结点，在平均情况下的时间复杂性是：__________，在最坏情况下的时间复杂性是__________。

【上海交通大学2004五、1(15／4分)】9 AVL树__________是完全二叉树；完全二叉树__________是AVL 树。

【电子科技大学2005二、5(1分)】10 一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有__________个结点。

注意：答案请做在答题纸上，做在试卷上无效
第 1 页，共 2 页 东华理工大学2016年硕士生入学考试初试试题
科目代码： 811 ; 科目名称：《数据结构（含C 程序设计）》；（A 卷） 适用专业（领域）名称：077500、081200计算机科学与技术
一、编写程序题：（共5小题，每小题12分，共60分）
1. 某百货公司进行促销活动，对于购物价格x≥5000元的8折，5000>x≥3000元的
8.5折，3000>x≥1000的9折，否则没有折扣。

编写函数，计算对购物x 元的折后价。

2. 计算1+(1×2)+(1×2×3)+…+(1×2×3×…×n)。

3. 已知一个班1门课的成绩，计算高于平均分的学生人数所占的百分数。

4. 输入一行字符，统计出26个大小写英文字母的个数。

5. 从键盘输入一串字符，除了空格，逐个把这些字符写入磁盘文件中，直到用户输入一个‘@’为止。

二、综合过程题：（共9小题，每小题10分，共90分）
1.设结点的类型如下：
typedef struct node
{ char data;
struct node *next;
}linklist;
编写建立带头结点的单链表的函数,结点值从键盘输入，当输入为‘#’时结束。

2.已知顺序栈的结构定义如下，编写出栈的函数。

typedef struct
{ int d[100];
int top;
}sqstack;
3.已知二叉树如下图，写出其前、中、后续的遍历结果。

2017中国人民大学计算机科学与技术(855)、软件工程(856) 真题(回忆版)学硕(855)计算机专业基础综合数据结构一、选择题(5个*3分)1、出栈顺序2、next数组3、2016个结点的八叉树，高度是多少4、顶点为n、边数为e的有向图，求拓扑排序的时间复杂度二、简答题(4个*5分)1、长度为2016的顺序表：(1)第i个位置删除和插入元素，需要移动多少个元素；(2)插入和删除，平均需要移动多少个元素。

2、普里姆算法求最小生成树，按顺序写出边。

3、给出a、b、c、d、e、f、g、h八个结点和每个结点的权值：(1)构造哈夫曼树，要求左子树根的权值小于等于右子树根的权值；(2)求出每个结点的哈夫曼编码。

4、哈希表：除留余数法的Hash函数，冲突处理方法分别用线性探查法和链地址法，分别求出两种方法的平均查找长度三、算法题(15分)1)图以邻接矩阵形式存储，写出完整的图的定义；2)输出一条由顶点v到顶点u的简单路径；3)输出全部简单路径。

离散数学一、自然推理系统两道1、命题逻辑：给出前提和结论。

2、谓词逻辑：符号化下述语句，并进行推理证明。

二、集合论1、偏序关系：告诉一个偏序关系，求最大元、最小元、极大元、极小元。

2、等价关系：已知R是等价关系，关系S满足<a,b>∈{∃c|<a,c>∈R∧<c,b>∈R }，证明S也是等价关系。

三、代数结构1、证明阶数小于6的群，都是交换群。

2、a,b,c都是群G中的元素，证明|abc|=|bca|=|cab|。