1、重庆理工大学硕士研究生试题专用纸重庆理工大学2015年攻读硕士学位研究生入学考试试题学院名称：计算机科学与工程 学科、专业名称：计算机技术考试科目（代码）：计算机基础综合(814)A卷 （试题共3页）注意：1.所有试题的答案均写在专用的答题纸上，写在试题纸上一律无效。2.试题附在考卷内交回。一、单选题（每小题2分，共30分）1、一个具有n个顶点的无向完全图的边数为 。An(n+1)/2 Bn(n-1)/2 C n(n-1) Dn(n+1)2、栈的插入与删除操作在 进行。 A栈顶 B栈底 C任意位置 D指定位置3、世界上第一台电子计算机诞生在哪个国家 。 A.中国 B.英国 C.美国 D.法国4
2、、ENIAC是第几代计算机 。 A.第一代 B.第二代 C.第三代 D.第四代5、CPU的英文全称是 。 ACOMPUTER B.Central Processing Unit C.compile D.powerpoint6、1B等于多少位 。 A、8位 B、4位 C、16位 D、32位7、下面哪个软件不是操作系统 。 A、DOS B、EXCEL C、UNIX D、IOS8、下列一组数中最小的数是 。 A、1111(B) B、10（H） C、11（O） D、109、数值数据在计算机内表示时，其正负号用 表示。 A、+ B、- C、1或0 D、+或-10、下面哪个是-1的补码，用8位表示 。 A
3、、1000 0001 B、1111 1110 C、1111 1111 D、0000 000111、在计算机主板中用于存放硬件驱动程序及简单测试程序的芯片是 。 A、CMOS芯片 B、BIOS芯片 C、ROM芯片 D、RAM芯片12、下面哪个是常见的外设部件互联总线插槽 。 A、AGP B、PCI C、USB D、Socket 75413、下面哪种是动态存储器 。A、DRAM B、SRAM C、ROM D、Cache14、下面哪种不是数据模型 。A、层次模型 B、网状模型 C、关系模型 D、蜂窝模型15、Internet网络模型中网络层最重要的协议是 。A、TCP B、IP C、HTTP D、F
4、TP二、填空题（每空2分，共30分）1、在数据结构中，从逻辑上可以把数据结构分成有下列4类： 、 、 和集合。2、将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT(X)的编号为 。3、在单链表中，每个结点结构包含next（后继域）和 data（数据域），指针p所指结点为最后一个结点的条件是 。4、中央处理器包括两部分： 和 。5、常用的计算机数制有： 、 、 、 。6、按照地理范围可以把计算机网络分为： 、 、 。7、ISO制订的开放系统互联参考模型简称 。三、简答题（共60分）1、（10分）有七个带权结点，其权值分别为3,7,8,2,6,10,14，试以它们
5、为叶子结点构造一棵哈夫曼树（左子树结点小于或等于右子树结点），并计算出带权路径长度WPL。2、（5分）设图G=（V，E），V=1，2，3，4，5，6，E=，请画出其邻接表。3、（5分）已知序列49，38，65，97，76，13，27，请给出采用选择排序对该序列作升序排序的每一趟的结果。4、（5分）假定查找有序表A25中每一元素的概率相等，试分别求出进行顺序、二分查找每一元素时的平均查找长度。5、（5分）操作系统的发展经历了哪几个阶段？ 6、（10分）简述CPU的主要性能指标。7、（10分）举例说明Office 2003主要包括哪些应用程序（至少5个）？8、（10分）举例说明计算机网络传输介质（
6、至少5个）？四、算法设计题（每小题10分，共30分）1、设某单链表L的结点结构为data,next,试用C语言编写算法int fun(pointer *L)，实现判断若链表的元素都是递增的返回1，否则返回0功能。typedef struct nodeint data;struct node *next;pointer;2、完成直接插入(简单插入)排序算法void insertsort(int data,int n)，实现有n个元素下标为0.n-1的数组排序，要求按从小到大的顺序排列。3、假设二叉树T采用如下定义的存储结构： typedef struct node DataType data; struct node *lchild,*rchild; PBinTree; 其中，结点的lchild域和rchild域已分别填有指向其左、右孩子结点的指针。请编写一个递归算法Bitree_Revolute(PBinTree T)，将根结点为T中各结点的lchild和rchild域的值进行交换。2
