昆明理工大学2014年硕士研究生招生入学考试试题(A卷)考试科目代码：818 考试科目名称：计算机学科专业基础综合
考生答题须知
1 所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。
2 评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。
3 答题时一律使用蓝、黑墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。
4 答题时不准使用涂改液等具有明显标记的涂改用品。
数据结构部分
广东省5184自考网一、选择题: (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
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.在宾馆管理中，要求每间客房的出租率均等，以保证维持每间客房硬件
设施的一个平均磨损率。回答如下问题：
1）利用《数据结构》中什么原理处理这一问题？（5分）
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协议可按功能划分为两层，其中负责建立、配置不同的网络层协议的是（）协议。
A.PPTP
B.HDLC
C.LCP
D.
四川公务员报名入口2022
NCP
昆明理工大学2014年硕士研究生招生入学考试试题
4、常用的A 类私有地址是（）。
A. 10.10.0.0～10.255.255.255
B. 10.0.0.0～10.255.255.255
C. 10.168.0.0～10.168.255.255
D. 172.16.0.0～172.31.255.255
5、下面（）动态路由协议属于IGP协议，使用了链路状态算法。
A.BGP
B.RIP
C.OSPF
D.EGP
6、在TCP/IP协议中，UDP协议是一种( )协议。
A.主机-网络层
B.互联网络层
C.传输层
D.应用层
7、如果有多个局域网需要互联起来，并希望将局域网的广播信息很好的隔离开，那么最基本的方法是用（）
A.网桥
B.路由器
C.网关
D.中继
8、香农定理从定量的角度描述了“带宽”与“速率”的关系。在香农定理的公式中与信道的最大传输速率相关的参数主要有信道宽度与( )
A.频率特性
B.信噪比
C.相位特性
公务员考试职位表在哪里下载D.噪声功率
9、( )用作商业机构的顶级域名.
A
B .edu
C
D .org
深圳公务员考试2022职位表E in-addr.arpa
10、将模拟信号转换为数字数据的过程叫做（）。
A.编码
B.解码
C.调制
D.解调
11、（）协议使用的是80端口，( )协议使用的是21端口。
A.HTTP,TELNET
B.DNS,TFTP
C.HTTP,DNS
D.HTTP,FTP
二、综合应用题（总分53分）
1、简述计算机网络的主要功能。（10分）
2、计算机网络拓扑结构有哪几种？（10分）
3、试分析TCP可靠性是如何实现的。（10分）
4、试解释TCP的三次握手过程。（10分）
5、已知某计算机所使用的IP地址是：195.169.20.25，子网掩码是：255.255.255.240，请计算出该计算机的网络号、子网号、主机号。（13分）
发布评论