2015计算机专业基础综合真题及答案解析

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．13B．14C．15D．163．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是A．24，10，5和24，10，7B．24，10，5和24，12，7C．24，10，10和24，14，11 D．24，10，5和24，14，64．现在有一颗无重复关键字的平衡二叉树（A VL树）,对其进行中序遍历可得到一个降序序列。

下列关于该平衡二叉树的叙述中，正确的是A．根节点的度一定为2B．树中最小元素一定是叶节点C．最后插入的元素一定是叶节点D．树中最大元素一定是无左子树5．设有向图G=(V,E)，顶点集V={V0,V1,V2,V3}，边集E={<v0,v1>,<v0,v2>,<v0,v3>，<v1,v3>},若从顶点V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是A．2B．3C．4D．56．求下面带权图的最小（代价）生成树时，可能是克鲁斯卡（kruskal）算法第二次选中但不是普里姆（Prim）算法（从V4开始）第2次选中的边是A．(V1,V3)B．(V1,V4)C．(V2,V3)D．(V3,V4)7．下列选项中，不能构成折半查找中关键字比较序列的是A．500，200，450，180B．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=0B．i=5，j=0C．i=5，j=2D．i=6，j=29．下列排序算法中元素的移动次数和关键字的初始排列次序无关的是A．直接插入排序B．起泡排序C．基数排序D．快速排序10．已知小根堆为8，15，10，21，34，16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是A．1 B．2C．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、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)三类。

2015年408真题及答案2015 年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第1～40 小题，每小题2 分，共80 分。

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

1．已知程序如下：程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是。

A．main()→S(1)→S(0) B．S(0)→S(1)→main()B．main()→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．根结点的度一定为2B．树中最小元素一定是叶结点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．5 6．求下面带权图的最小（代价）生成树时，可能是克鲁斯卡（Kruskal）算法第2次选中但不是普里姆（Prim）算法（从V4 开始）第2次选中的边是。

A．(V1,V3) B．(V1,V4) C．(V2,V3) D．(V3,V4)7．下列选项中，不能构成折半查找中关键字比较序列的是。

int S(int n){ return (n<=0)?0:s(n-1)+n;}void main(){ cout<< S(1);}A．500,200,450,180 B．500,450,200,180·2·C ．180,500,200,450D ．180,200,500,4508．已知字符串 S 为“abaabaabacacaabaabcc”，模式串 t 为“abaabc”。

2015年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：1～40小题，每小题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．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．现有一棵无重复关键字的平衡二叉树(AVL树)，对其进行中序遍历可得到一个降序序列。

下列关于该平衡二叉树的叙述中，正确的是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．3C．4 D．56．求下面带权图的最小(代价)生成树时，可能是克鲁斯卡尔(Kruskal)算法第2次选中但不．是普里姆(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，450R．已知字符串s为“abaabaabacacaabaabcc”，模式串t为“abaabc5’。

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

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

1．已知程序如下：程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是。

A．main()→S(1)→S(0) B．S(0)→S(1)→main()B．main()→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．5 6．求下面带权图的最小（代价）生成树时，可能是克鲁斯卡（Kruskal）算法第2 次选中但不是普里姆（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,180int S(int n){ return(n<=0)?0:s(n-1)+n;}voidmain(){ cout<<S(1);}C．180,500,200,450 D．180,200,500,4508．已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”。

2015年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：1～40小题，每小题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．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．现有一棵无重复关键字的平衡二叉树(AVL树)，对其进行中序遍历可得到一个降序序列。

下列关于该平衡二叉树的叙述中，正确的是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．3C．4 D．56．求下面带权图的最小(代价)生成树时，可能是克鲁斯卡尔(Kruskal)算法第2次选中但不．是普里姆(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，450R．已知字符串s为“abaabaabacacaabaabcc”，模式串t为“abaabc5’。

2015 年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第 1～40 小题，每小题 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()B．main()→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．5 6．求下面带权图的最小（代价）生成树时，可能是克鲁斯卡（Kruskal）算法第2次选中但不是普里姆（Prim）算法（从V4 开始）第2 次选中的边是。

A．(V1,V3) B．(V1,V4) C．(V2,V3) D．(V3,V4)7．下列选项中，不能构成折半查找中关键字比较序列的是。

2015年考研计算机专业（基础综合）真题试卷(总分：130.00，做题时间：90分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题1-40小题。

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

__________________________________________________________________________________________ 2.已知程序如下：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()3.先序序列为a，b，c，d的不同二叉树的个数是_______。

A.13B.14 √C.15D.164.下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是_______。

A.24，10，5和2，4，10，7B.24，10，5和24，12，7C.24，10，10和24，14，11D.24，10，5和24，14，6 √5.现有一棵无重复关键字的平衡二叉树(AVL树)，对其进行中序遍历可得到一个降序序列。

下列关于该平衡二叉树的叙述中，正确的是_______。

A.根结点的度一定为2B.树中最小元素一定是叶结点C.最后插入的元素一定是叶结点D.树中最大元素一定是无左子树√6.设有向图G=(V，E)，顶点集V={V 0，V 1，V 2，V 3 }，边集E={＜V 0，V 1＞，＜V 0，V 1＞，＜V 0，V 3＞，＜V 1，V 3＞}。

若从顶点V 0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是_______。

第一部分选择题-计算机基础知识共15题15分1．个人计算机简称PC机,这种计算机属于______. AA．微型计算机 B．小型计算机 C．超级计算机 D．巨型计算机2．对于信息，下列说法错误的是______。

DA．信息是可以处理的 B．信息是可以传播的C．信息是可以共享的 D．信息可以不依附于某种载体而存在3．在计算机中，用数值、文字、语言和图像等所表示的内容都可称为______。

CA．表象 B．文章 C．信息 D．消息4．冯·诺依曼在1946年提出了计算机的程序存储原理。

按此原理设计的计算机称为______.C A．智能计算机 B．高性能计算机C．存储程序计算机或冯·诺依曼结构计算机 D．现代化的计算机5．巨型电子计算机指的是______。

CA．体积大 B．重量大 C．功能强 D．耗电量大6．“使用计算机进行数值运算，可根据需要获得千分之一到几百万分之一甚至更高的精确度。

"，该描述说明计算机具有______。

DA．自动控制能力 B．高速运算的能力 C．记忆能力 D．很高的计算精度7．用计算机进行图书资料检索工作，属于计算机应用中的______。

AA．数据处理 B．科学计算 C．人工智能 D．实时控制8．冯·诺依曼在1946年提出了计算机的程序存储原理。

关于计算机的程序，其说法错误的是______.D A．程序由指令构成 B．程序和数据都用二进制数表示C．指令由操作码和地址码构成 D．计算机以程序为中心9．运算器的组成部分不包括______。

BA．控制线路 B．译码器 C．加法器 D．寄存器10．计算机中的所有信息都是以二进制方式表示的，这两个二进制数是______。

CA．1和2 B．0和2 C．0和1 D．1和1011．下面哪一项不是计算机采用二进制的主要原因_____。

DA．二进制只有0和1两个状态,技术上容易实现 B．二进制运算规则简单C．二进制数的0和1与逻辑代数的“真”和“假”相吻合，适合于计算机进行逻辑运算D．二进制可与十进制直接进行算术运算12．计算机的运算速度是它的主要性能指标之一.计算机的主要性能指标还包括_____.AA．内存容量 B．显示器尺寸 C．机箱类型 D．绘图机的图纸幅面大小13．下列设备中,多媒体计算机所特有的设备是______。

2015年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：1～40小题，每小题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．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．现有一棵无重复关键字的平衡二叉树(AVL树)，对其进行中序遍历可得到一个降序序列。

下列关于该平衡二叉树的叙述中，正确的是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．3C．4 D．56．求下面带权图的最小(代价)生成树时，可能是克鲁斯卡尔(Kruskal)算法第2次选中但不．是普里姆(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，450R．已知字符串s为“abaabaabacacaabaabcc”，模式串t为“abaabc5’。

第一部分选择题-计算机基础知识共15题15分1．个人计算机简称PC机，这种计算机属于______。

AA．微型计算机 B．小型计算机 C．超级计算机 D．巨型计算机2．对于信息，下列说法错误的是______。

DA．信息是可以处理的 B．信息是可以传播的C．信息是可以共享的 D．信息可以不依附于某种载体而存在3．在计算机中，用数值、文字、语言和图像等所表示的内容都可称为______。

CA．表象 B．文章 C．信息 D．消息4．冯·诺依曼在1946年提出了计算机的程序存储原理。

按此原理设计的计算机称为______。

C A．智能计算机 B．高性能计算机C．存储程序计算机或冯·诺依曼结构计算机 D．现代化的计算机5．巨型电子计算机指的是______。

CA．体积大 B．重量大 C．功能强 D．耗电量大6．“使用计算机进行数值运算，可根据需要获得千分之一到几百万分之一甚至更高的精确度。

”，该描述说明计算机具有______。

DA．自动控制能力 B．高速运算的能力 C．记忆能力 D．很高的计算精度7．用计算机进行图书资料检索工作，属于计算机应用中的______。

AA．数据处理 B．科学计算 C．人工智能 D．实时控制8．冯·诺依曼在1946年提出了计算机的程序存储原理。

关于计算机的程序，其说法错误的是______。

D A．程序由指令构成 B．程序和数据都用二进制数表示C．指令由操作码和地址码构成 D．计算机以程序为中心9．运算器的组成部分不包括______。

BA．控制线路 B．译码器 C．加法器 D．寄存器10．计算机中的所有信息都是以二进制方式表示的，这两个二进制数是______。

CA．1和2 B．0和2 C．0和1 D．1和1011．下面哪一项不是计算机采用二进制的主要原因_____。

DA．二进制只有0和1两个状态，技术上容易实现 B．二进制运算规则简单C．二进制数的0和1与逻辑代数的“真”和“假”相吻合，适合于计算机进行逻辑运算D．二进制可与十进制直接进行算术运算12．计算机的运算速度是它的主要性能指标之一。

一、单项选择题1-40小题，每小题2分，共80分。

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

1 【正确答案】 A2 【正确答案】 B3 【正确答案】 D4 【正确答案】 D5 【正确答案】 D6 【正确答案】 C7 【正确答案】 A8 【正确答案】 C9 【正确答案】 C10 【正确答案】 C11 【正确答案】 A12 【正确答案】 A13 【正确答案】 B14 【正确答案】 D15 【正确答案】 C16 【正确答案】 B17 【正确答案】 B18 【正确答案】 D19 【正确答案】 C20 【正确答案】 B21 【正确答案】 B22 【正确答案】 D23 【正确答案】 B24 【正确答案】 C25 【正确答案】 D26 【正确答案】 B27 【正确答案】 A28 【正确答案】 A29 【正确答案】 B30 【正确答案】 C31 【正确答案】 C32 【正确答案】 C33 【正确答案】 D34 【正确答案】 A35 【正确答案】 B36 【正确答案】 B37 【正确答案】 A38 【正确答案】 C39 【正确答案】 A40 【正确答案】 C二、综合应用题41-47小题，共70分。

41 【正确答案】算法的基本设计思想算法的核心思想是用空间换时间。

使用辅助数组记录链表中已出现的数值，从而只需对链表进行一趟扫描。

因为｜data｜≤n，故辅助数组q的大小为n+1，各元素的初值均为0。

依次扫描链表中的各结点，同时检查q[｜data｜]的值，如果为0，则保留该结点，并令q[｜data｜]=1；否则，将该结点从链表中删除。

42 【正确答案】使用C语言描述的单链表结点的数据类型定义typedef struct node{int data；struct node*link；}NODE；Typedef NODE *PNODE。

43 【正确答案】算法实现void func (PNODE h，int n){PNODE p=h，r，int *q，m；q=(int *)malloc(sizeof(int)*(n十1))；／／申请n+1个位置的辅助空间for(int i=0，i＜n+1，i++)／／数组元素初值置0*(q+i)=0；while(p-＞link!=NULL){m=p-＞link-＞data＞0?p-＞link-＞data：-p-＞link-＞data；if(*(q+m)==0)／／判断该结点的data是否己出现过{*(q+m)=1，／／首次出现p=p-＞link；／／保留}else／／重复出现{r=p-＞link；／／删除P-＞link=r-＞finkfree(r)；}44 【正确答案】算法的时间复杂度为O(m)，空间复杂度为O(n)。

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

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

1．已知程序如下：程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是。

A．main()→S(1)→S(0) B．S(0)→S(1)→main()B．main()→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．5 6．求下面带权图的最小（代价）生成树时，可能是克鲁斯卡（Kruskal）算法第2次选中但不是普里姆（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,180int S(int n){ return (n<=0)?0:s(n-1)+n;}void main(){ cout<< S(1);}C．180,500,200,450 D．180,200,500,4508．已知字符串S 为“abaabaabacacaabaabcc”，模式串t 为“abaabc”。

绝密★启用前江苏省2015年普通高校专转本选拔考试计算机基础试题卷注意事项：1．本试卷分为试题卷和答题卡两部分，试题卷共8页。

全卷满分100分，考试时间90分钟。

2．必须在答题卡上作答，作答在试题卷上无效。

作答前务必将自己的姓名和准考证号准确清晰地填写在试题卷和答题卡上的指定位置。

3．考试结束时，须将试题卷和答题卡一并交回。

一、判断题（本大题共20小题，每小题1分，共20分。

下列各小题表述正确的在答题卡上将A涂黑，错误的将B涂黑）1．现代计算机采用的是冯·诺依曼提出的“存储程序控制”思想，科学家们正在研究的生物计算机采用非冯·诺依曼结构。

2．通信系统的基本任务是传递信息，至少需由信源、信宿和信息三个要素组成。

3．CPU、内存储、总线等构成了计算机的“主机”，外存储器、输入／输出设备通常称为计算机的“外设”。

4．若某处理器具有64GB的寻址能力，则该处理器的地址线有64根。

5．高速缓存(cache)可以看作是主存的延伸，与主存统一编址，接受CPU的访问，其存取速度远高于主存。

6．高基硬盘(SSD)是一种基于半导体存储器芯片的外存储设备，可用来替代笔记本电脑中的传统硬盘。

7．因特网上提供的免费软件均是自由软件。

8．易理解性是衡量算法是否易调、易测和易维护的重要标准。

9．从系统功能的角度看，计算机网络主要由资源子网和通信子网两部分组成。

其中通信子网主要包括连网的计算机、终端、外部设备、网络协议及网络软件等。

10．常见的数据交换方式有电路交换、报文交换及分组交换等，因特网采用的交换方式是电路交换方式。

11．网卡的MAC地址是标识主机的硬件地址，由48位二进制组成，通常用16进制数表示。

12．UCS／Unicode编码是我国制定的汉字编码标准。

13．在未缩放的情况下，若屏幕(或窗口)只显示了某图像的一部分，说明该图像的分辨率超过了显示器的分辨率。

14．用数码相机拍摄得到的图像是位图图像，用扫描仪扫描得到的图像是矢量图形。

第一部分选择题—计算机基础知识共15题15分1．个人计算机简称PC机，这种计算机属于______。

AA．微型计算机 B．小型计算机 C．超级计算机 D．巨型计算机2．对于信息，下列说法错误的是______。

DA．信息是可以处理的 B．信息是可以传播的C．信息是可以共享的 D．信息可以不依附于某种载体而存在3．在计算机中，用数值、文字、语言和图像等所表示的内容都可称为______。

CA．表象 B．文章 C．信息 D．消息4．冯·诺依曼在1946年提出了计算机的程序存储原理。

按此原理设计的计算机称为______。

C A．智能计算机 B．高性能计算机C．存储程序计算机或冯·诺依曼结构计算机 D．现代化的计算机5．巨型电子计算机指的是______。

CA．体积大 B．重量大 C．功能强 D．耗电量大6．“使用计算机进行数值运算，可根据需要获得千分之一到几百万分之一甚至更高的精确度。

”，该描述说明计算机具有______.DA．自动控制能力 B．高速运算的能力 C．记忆能力 D．很高的计算精度7．用计算机进行图书资料检索工作，属于计算机应用中的______。

AA．数据处理 B．科学计算 C．人工智能 D．实时控制8．冯·诺依曼在1946年提出了计算机的程序存储原理。

关于计算机的程序，其说法错误的是______。

D A．程序由指令构成 B．程序和数据都用二进制数表示C．指令由操作码和地址码构成 D．计算机以程序为中心9．运算器的组成部分不包括______。

BA．控制线路 B．译码器 C．加法器 D．寄存器10．计算机中的所有信息都是以二进制方式表示的，这两个二进制数是______.CA．1和2 B．0和2 C．0和1 D．1和1011．下面哪一项不是计算机采用二进制的主要原因_____。

DA．二进制只有0和1两个状态,技术上容易实现 B．二进制运算规则简单C．二进制数的0和1与逻辑代数的“真"和“假”相吻合，适合于计算机进行逻辑运算D．二进制可与十进制直接进行算术运算12．计算机的运算速度是它的主要性能指标之一。