15年研究生昆明理工计算机818考试题目和答案

《15年研究生昆明理工计算机818考试题目和答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、昆明理工大学2015年硕士研究生招生入学考试试题(A卷)考试科目代码：818考试科目名称：计算机学科专业基础综合考生答题须知1．所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。2．评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。3．答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。4．答题时不准使用涂改液等具有明显标记的涂改用品。数据结构部分一、单项选择题（共15题，每题2分，共30分）1、下面语句段执行的时间复杂度是

2、（）for(i=1;i<=n;i++)for(j=i;j<=n;j++)s++;A)T(n)=n2B)T(n)=n3C)T(n)=O(n2)D)T(n)=O(n3)2、不可分割的、含有独立意义的最小数据单位称为（）A)数据B)数据元素C)数据项D)记录3、单链表中指针p指向结点A，若删除A之后的结点（结点若存在），则需修改指针的操作是（　）。A）p->next=p->next->nextB）p=p->nextC）p=p->next->nextD）next=p4、线性表是（　）。A）一个有限序列，可以为空　　B）一个有限序列，不能为空C）一个无限序列，可以

3、为空　　D）一个无限序列，不能为空5、在数组A[8][10]中，每一个数组元素占用4个字节，所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的空间是(）字节。10*8*4A)80B)100C)280D)3206、假定一个顺序循环队列中空一个存储单元不用，其队首和队尾指针分别用front和rear表示,则判断队满的条件为（）  A)front+1==rearB)rear+1==frontC)front==0D)front==rear7、一个栈的入栈序列是1,2,3,4,5,则该栈不可能的输出序列是（）A)54321B)43512C)4532

4、1D)123458、栈操作的特点是()。A)先进后出B)先进先出C)  随机存取D)顺序存取昆明理工大学2015年硕士研究生招生入学考试试题9、线性表若是采用链式存储结构时，要求内存中可用存储单元的地址()。A)必须是连续的B)部分地址必须是连续的C)一定是不连续的D)连续或不连续都可以10、树最适合用来表示（　　）。A）有序数据元素　B）元素之间具有分支层次关系的数据C）无序数据元素　D）元素间无联系的数据11、深度为5的二叉树最多有（　）个结点。A）10　　　B）16C）32　　　D）31:2^n-112、在以下所示的有向图中，顶点D的入度和出度分别

5、是（）A）12　　　B）21C）31　D）1313、一个AOV网的拓扑序列（）A）一定是唯一的B）不一定是唯一的C）一定不是唯一的D）以上说法都不正确14、对长度为18的顺序存储的有序表，采用二分查找，则查找第15个元素的比较次数为(　)。A）3B）4C）5D）615、在下面的排序方法中，关键字比较的次数与记录的初始排序次序无关的是（　　）。A）选择排序　　B）冒泡排序C）快速排序　　D）插入排序N(n-1)/2次二、判断题（共10题，每题1分，共10分）1、时间复杂度用来描述算法占用存储空间的多少【W】2、空串就是由空格组成的字符串。【W】3、在顺序表

6、中进行插入和删除操作需要移动大量元素，时间效率较低。【R】4、二叉树中结点最大的度为2。【R】5、树中所有结点都有双亲结点。【W】6、一个有n个顶点连通图，其生成树有n-1条边。【R】第1页共10页7、有向图跟无向图的领接矩阵都是对称距阵。【W】无向图的邻接矩阵是对称的有向图是非对称矩阵昆明理工大学2015年硕士研究生招生入学考试试题第1页共10页8、二叉排序树的中序编历序列是按结点关键字递增排序的有序序列。【R】9、若待排序的记录数目较小，可采用直接插入排序或直接选择排序。【R】10、直接插入排序是不稳定的。【W】快速排序不稳定三、完成如下问题:（共3

7、题，每题6分，共18分）1.已知一组权值W={6,8,2,4,9,15,19},请（按左小右大方式）构造一棵哈夫曼树,并计算出其WPL值。（6分）1612.一棵二叉树的后序序列和中序序列分别如下，试画出该二叉树。（6分）中序序列：a+b*c–d/e；后序序列:abc*+de/-后序放中间，中序分两边,依次找出跟http://www.zybang.com/question/498a155ac8fc8d35850973430d4473e3.htmlV1V2V3V4V5V6V7∞18∞∞234618∞5812∞∞∞5∞10∞∞∞∞810∞1520∞2312∞1

8、5∞25∞4∞∞2025∞76∞∞∞∞7∞V1V2V3V4V5V6V73.已知以