818计算机学科专基础综合
业
精品资料
昆明理工大学2014年硕士研究生招生入学考试试题(A卷)
考试科目代码：818 考试科目名称 ：计算机学科专业基础综合
考生答题须知
1． 所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无
效。请考生务必在答题纸上写清题号。
2． 评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。 3． 答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。 4． 答题时不准使用涂改液等具有明显标记的涂改用品。
数据结构部分 一、选择题: (25题，每题1分，共25分) 1. 从一个具有n个结点单链表中查找其值等于x结点时，在查找成功时，需平均比较 结点数是 。 (A) n (B) n/2 (C) (n-1)/2 (D) (n+1)/2 2. 下面算法的空间复杂度为 。 float aver(float a[n]) { int j; 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. 在一个单链表中，若要删除*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->next=f;f=s; 6. 从顺序存储的循环队列中删除一个元素时，是 。 (A) 先移动队首指针，后取出元素 (B) 先取出元素，后移动队首指针 7. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为1个，那么度为0的结点数为 个。 (A) 4 (B) 5 (C) 6 (D) 7 8. 在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶结点数为 个。 (A) 15 (B) 16 (C) 17 (D) 47 9. 一棵二叉树结点数为18个，则其最小高度为 ，其最大高度为 。 (A) 4,16 (B)5,18 (C) 6,18 (D) 3,18 10. 一棵三叉树结点数为50个，则其最小高度为 。 (A) 3 (B) 4 (C) 5 (D) 6 仅供学习与交流，如有侵权请联系网站删除 谢谢1
精品资料
昆明理工大学2014年硕士研究生招生入学考试试题
仅供学习与交流，如有侵权请联系网站删除 谢谢2
精品资料
11. 由分别带权为9，2，5，7的四个叶结点构造一棵哈夫曼树，则该树的带权路径长度是 。 (A) 23 (B)37 (C) 44 (D) 46 12. 已知10个数据元素（54，28，16，34，73，62，95，60，26，43），按照依次插入结点的方法生成一棵二叉排序树后，则查找值为62的结点所需比较的次数是3；在查找成功的情况下，查找每个元素的平均比较次数（又称平均查找长度，即查找每个元素时平均比较的结点数）为 。 (A) 2.5 (B)3.2 (C) 2.6 (D) 2.9 13. 在一个无向图中，所有顶点的度数之和等于所有边数的 倍。 (A) 1/2 (B) 1 (C) 2 (D) 4 14. 有n个顶点的无向图中，要连通全部顶点至少需要 条边。 (A) n (B) (n+1) (C) (n-1) (D) n/2 15. 有n个顶点和e条边的无向图中，若采用邻接表表示，则表头向量的大小为 条边。 (A) n (B) (n+1) (C) (n-1) (D) n/2 16. 在有向图的邻接表中，每个顶点的邻接表链接着该顶点的所有 邻接点；在有向图的逆邻接表中，每个顶点的邻接表链接着该顶点的所有 邻接点； (A) 出边，入边 (B) 入边，出边 17. 对于一个具有n个顶点e条边的的图，若采用边集数组表示，则边集数组中的单元数至少为 个。 (A) n (B) n+e (C) e (D) 2e 1 18. 如图1所示，若从顶点V1出发按广度优先搜索法进行遍历可能得到的一种顶点序列是 。 (A) V1,V2,V5,V3,V6,V7,V4 3 2 (B) V1,V5,V2,V4,V3,V7,V6 图1 5 (C) V1,V2,V5,V4,V3,V7,V6 6 4 (D) V1, V5,V2,V3,V7,V6,V4 19. 如图2所示，在该图的最小生成树中，各边上权值之和是 ；在该图的最小生成树中，从点V1到点V67 的路径是 。 12 1 2 (A) 31 , (V1,V3,V4,V6) 15 5 (B) 36 , (V1,V3,V4,V6) 8 20 3 10 (C) 38 , (V1,V4,V6) 图2 6 4 5 (D) 43 , (V1,V4,V3,V6) 8 4 9 20. 如图3所示，该图得到的一种拓扑序列为 。 6 (A) (V1,V4,V6,V2,V5,V3) (B) (V1,V2,V3,V4,V5,V6) （C) (V1,V4,V2,V3,V6,V5) 图3 2 3 1 (D) (V1,V2,V4,V6,V3,V5) 4 6 5 仅供学习与交流，如有侵权请联系网站删除 谢谢3
精品资料
昆明理工大学2014年硕士研究生招生入学考试试题
21. 在对长度为n的顺序存储的有序表进行二分查找时，对应的二分查找判定树的高度为 。 (A) n (B) ?log2n? (C) ?log2(n+1)? (D) ?log2(n+1)? 22. 顺序查找一个具有n个元素的线性表，其时间复杂度为 ，二分查找为一个具有n个元素的线性表，其时间复杂度为 。 (A) O(n),O(log2n) (B)O(log2n),O(log2n) (C) O(n2),O(n) (D) O(nlog2n),O(log2n) 23. 已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当二分查找值为90的元素时， 次比较后查找成功；当二分查找值为47的元素时， 次比较后查找成功。 (A) 1，4 (B) 2，4 (C) 3，2 (D) 4，2 24. 在顺序存储的线性表A[30]上进行顺序查找的平均查找长度为 。 (A) 15 (B) 15.5 (C) 16 (D) 20 25. 已知一个线性表为（38，25，74，63，52，48），假定采用H（K）=K mod 7计算散列地址进行散列存储时，若利用线性探测的开放定地址法处理冲突，则在该散列表上进行查找的平均查找长度为 ；若利用链接法处理冲突，则在该散列表上进行查找的平均查找长度为 。 (A) 1.5,1 (B) 1.7,3/2 (C) 2,4/3 (D) 2.3,7/6 二、综合应用题：(2题，每题25分，共50分) 1. 中缀表达式中，如果不规定运算符的优先级又不加括号，则运算结果不唯一；后缀表达式中，不规定运算符的优先级又不需括号，就能得到唯一的运算结果。现以中缀表达式：（8+3*6）/（2+3*5-4）为例，回答如下问题： 1) 利用什么原理实现中缀表达式转换成后缀表达式？（5分） 2) 写出中缀表达式转换成后缀表达式的算法思想。（10分） 3) 用上中缀表达式为例，图示表现出其转换成后缀表达式的过程及结果。（10分） 2. 在宾馆管理中，要求每间客房的出租率均等，以保证维持每间客房硬件设施的一个平均磨损率。回答如下问题： 3. 1）利用《数据结构》中什么原理处理这一问题？（5分） 4. 2）请简述并画出示意描述图。（20分） 计算机网络部分 一、单项选择题（每小题2分，总分22分） 1、按照0比特插入/删除方法规定，在两个标志字段为F的比特序列中，如果检查出连续的（）1，不管后面的比特位是0或1，都需要增加一个0。 A．4 B. 5 C. 6 D. 8 2、在（）差错控制方式中，只会重新传输那些出错的数据帧。 A. 连续工作 B. 停止等待 C. 选择重发 D.后退N帧 3、PPP协议可按功能划分为两层，其中负责建立、配置不同的网络层协议的是（）协议。 仅供学习与交流，如有侵权请联系网站删除 谢谢4
最新818计算机学科专业基础综合汇总
