资源描述：
《计算机学科专业基础综合》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、昆明理工大学2014年硕士研究生招生入学考试试题(A卷)考试科目代码：818考试科目名称：计算机学科专业基础综合考生答题须知1．所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。2．评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。3．答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。4．答题时不准使用涂改液等具有明显标记的涂改用品。数据结构部分一、选择题:(25题，每题1分，共25分)
2、1.从一个具有n个结点单链表中查找其值等于x结点时，在查找成功时，需平均比较结点数是。(A)n(B)n/2(C)(n-1)/2(D)(n+1)/22.下面算法的空间复杂度为。floataver(floata[n]){intj;for(j=n;j<0;j--)printf(“%8.2f”,a[j]);}(A)O（1）(B)O（log2n）(C)O（n）(D)O（n2）3.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为。(A)O(1)(B)O(n)(C)O(n2)(D)O(log2n)4.在一个单链
3、表中，若要删除*p结点的后继结点，则执行。(A)p->next=p->next->next;(B)p->next=p->next->next;free(p->next);(C)p->next=p->next->next;q=p->next;free(q);(D)q=p->next;p->next=p->next->next;free(q);5.在一个链队列中，f和r分别为队首尾指针，则进行插入s结点的操作时执行。(A)f->next=s;f=s;(B)r->next=s;r=s;(C)s->next=r;r=s;D)s
4、->next=f;f=s;6.从顺序存储的循环队列中删除一个元素时，是。(A)先移动队首指针，后取出元素(B)先取出元素，后移动队首指针7.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为1个，那么度为0的结点数为个。(A)4(B)5(C)6(D)78.在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶结点数为个。(A)15(B)16(C)17(D)479.一棵二叉树结点数为18个，则其最小高度为，其最大高度为。(A)4,16(B)5,18(C)6,18(D)3,1810.
5、一棵三叉树结点数为50个，则其最小高度为。(A)3(B)4(C)5(D)6第4页共4页昆明理工大学2014年硕士研究生招生入学考试试题1.由分别带权为9，2，5，7的四个叶结点构造一棵哈夫曼树，则该树的带权路径长度是。(A)23(B)37(C)44(D)462.已知10个数据元素（54，28，16，34，73，62，95，60，26，43），按照依次插入结点的方法生成一棵二叉排序树后，则查找值为62的结点所需比较的次数是3；在查找成功的情况下，查找每个元素的平均比较次数（又称平均查找长度，即查找每个元素时平均比较的结点
6、数）为。(A)2.5(B)3.2(C)2.6(D)2.93.在一个无向图中，所有顶点的度数之和等于所有边数的倍。(A)1/2(B)1(C)2(D)44.有n个顶点的无向图中，要连通全部顶点至少需要条边。(A)n(B)(n+1)(C)(n-1)(D)n/25.有n个顶点和e条边的无向图中，若采用邻接表表示，则表头向量的大小为条边。(A)n(B)(n+1)(C)(n-1)(D)n/26.在有向图的邻接表中，每个顶点的邻接表链接着该顶点的所有邻接点；在有向图的逆邻接表中，每个顶点的邻接表链接着该顶点的所有邻接点；(A)出边，
7、入边(B)入边，出边7.对于一个具有n个顶点e条边的的图，若采用边集数组表示，则边集数组中的单元数至少为个。1235467(A)n(B)n+e(C)e(D)2e8.如图1所示，若从顶点V1出发按广度优先搜索法进行遍历可能得到的一种顶点序列是。(A)V1,V2,V5,V3,V6,V7,V4(B)V1,V5,V2,V4,V3,V7,V6图1(C)V1,V2,V5,V4,V3,V7,V6(D)V1,V5,V2,V3,V7,V6,V4312456128155420108969.如图2所示，在该图的最小生成树中，各边上权值之和是
8、；在该图的最小生成树中，从点V1到点V6的路径是。(A)31,(V1,V3,V4,V6)(B)36,(V1,V3,V4,V6)(C)38,(V1,V4,V6)图2(D)43,(V1,V4,V3,V6)10.如图3所示，该图得到的一种拓扑序列为。(A)(V1,V4,V6,V2,V5,V3)123456(B)(V1,V2,V3,V4,
