桂林电子科技大学2015年研究生统一入学考试试题
科目代码：823科目名称：数据结构+操作系统
请注意：答案必须写在答题纸上（写在试题上无效）广西民歌艺术节。
PARTI数据结构部分
一、选择题（24分。共8小题彭于晏肌肉，每小题3分）
1.关于数据结构的描述韦斯顿，正确的是（）。
A．数据的逻辑结构可以划分为：线性结构、树型结构和索引结构
B．一种逻辑结构可采用多种存储结构实现
C．一种存储结构只能实现一种逻辑结构
D．现实世界中数据对象的1对多联系可以采用线性结构表达
2.关于顺序表和链接表的描述保密工作承诺书，错误的是（）。
A．顺序表和链接表是线性表的不同存储结构实现
B．顺序表将线性表中数据元素之间的相邻关系映射为数据物理位置上的相邻关系
C．分别在具有n个数据元素的顺序表和链接表中查找数据元素K礼仪修养，链接表的查找效率要
高于顺序表红松。
D．数组可以作为线性表的一种顺序表实现
3.图1中，（a）是结点结构，（b）是指针s指向的待插入结点，（c）是双向链表片段运城学院录取分数线，则在
（c）中p指针指向的结点前面插入指针s指向的结点的操作是（）。
llinkdata
（a）
p
rlink
s
（b）
x
ab
（c）
c
图1双向链表
A．s->rlink=p;s->llink=p->llink;p->llink->rlink=s;p->llink=s;
B．p->llink=s;s->rlink=p;s->llink=p->llink;p->llink->rlink=s;
C．p->llink->rlink=s;p->llink=s;s->rlink=p;s->llink=p->llink;
D．s->rlink=p;s->llink=p->llink;p->llink=s;p->llink->rlink=s;
4怎样去黑头收缩毛孔.若出栈的顺序是a,b,c,ddnf剑圣刷图加点,ednf复仇刷图加点，则入栈的顺序不可能是（）申请表怎么写。
A．a绿色小精灵,b,c江畔独步寻花1一7首,d中秋手抄报,eB．e后羿射日的意思,d,c,b感恩节英语祝福语,aC．d,e,c枸杞子茶,b焕然一新,aD．a奶奶超市暴打孙女,e,d爱情qq签名,c写清明节的作文,b
5公司档案管理制度.二叉树的前序序列是：ABDCGEF我爱他歌词，中序遍历序列是：DBCGAEF，则该二叉树的叶子结点数
目是（）。
A．2B．3C．4D．5
第1页共5页
6中国首善陈光标简介.给定四个符号X路由器和猫冲突,Y教师节倡议书,Z杨万里简介,P，它们被使用的频率分别是0我想唱一首情歌 不需别人认可.2、02022春节图片.4、0圆明园的资料和图片.3和0.1，采用哈夫曼编码
后，‘Z’的编码长度是（）今年七夕是几月几号。
A．1B．2C．3D．4
7社交焦虑症.若待排序的元素序列基本有序2017高考分数线，则（）算法效率最高辛弃疾词的风格。
A．插入排序B．选择排序C．快速排序D．归并排序
8.一个无向图具有n个顶点m条边奋斗 大张伟，则该无向图中所有顶点的度数之和是（）白杨树。
A．2n
二、应用与分析题（36分银行从业资格考试 公共基础。共4小题感师恩，每小题9分）
B．n+mC．2mD．n*m
1.请给出下面算法的功能描述。（9分）
structNode;
typedefstructNode*PNode;
structNode{
DataTypeinfo;
PNodelink;
};
typedefstructNode*LinkList;
intTest(LinkListlist灰姑娘的姐姐好看吗,DataTypevalue)
{
LinkListtmp=list;intm=0;
while(tmp!=null)
{
if(tmp->info==value)
m++;
tmp=tmp->link;
}
returnm;
}
2.线性表B=（6，21曹操后人，45糖浆的做法，55，20太极张三丰万梓良，3，782020高考录取分数线已公布，31亚洲男神官网，15）盘古开天辟地。给定数组HT[0寂寞替身.李践行动日志.8]作为散列表的存储空
间，散列函数为H(key)=key%9东莞积分入户查询，且采用线性探查法解决冲突。
（1）若采用给定散列表存储线性表B，请画出对应的散列表智联招聘求职信。（5分）
（2）若B中少于等于40的数据元素的查找概率为2/15，大于40的数据元素的查找概率为1/15，
请计算查找成功的平均查找长度穷途之哭。（4分）
第2页共5页
3.无向带权图的邻接矩阵如下所示
请用Kruskal算法构造此图的最小生成树科学幻想画，要求给出详细的构造过程。（9分）
4.给定一待排序关键字序列(40，25，64职业病防治法宣传周是，18，21电视剧妻子的谎言，36，9，30)。
（1）请以每一个待排序区间的最后一个元素为基准记录，给出前3趟快速排序每一趟排序
的结果大金湖。（6分。注：按照升序进行排序）
（2）请问需要经过几趟快速排序，上述序列才排序结束。（3分）
三、算法设计题（15分）
一个长度为N的字母序列STR是对称的是指对任意的序号i（0≤i≤N-1）西班牙留学条件，有
STR[i]=STR[N-i-1]，例如“ABA”或者“ABBA”等。若采用带有头结点的双向循环链表来
存储字母序列，链表中的每个结点存储一个字母（如图2所示）。请设计一个判定字母序列是
否对称的算法今天晚上9点有流星雨吗，如果对称返回TRUE（或者1），否则返回FALSE（或者0）享受孤独，要求时间复杂
度不超过O(n)东北菜谱家常菜做法。
head
ABA
图2带头结点的双向循环链表
PARTII操作系统部分
一、选择题（每题2分，共20分）
12017考研政治答案.下列指令中，________可以在用户态运行。
A.加载PSW B李后主.访管指令 C.启动I/O指令 D.改变存储器映像图
2.操作系统提供给应用程序员的接口是_________。
A经典昵称.库函数 B.进程 C. 线程 D.系统调用
3360浏览器5 0.对于5个并发的进程，设信号量mutex的初值为2爱q生活，若mutex=-1孔侑新剧，则____________。
A庆祝建党可以用华诞吗.表示没有进程进入临界区
B.表示有二个进程进入临界区
C.表示有二个进程进入临界区，另一个进程等待进入
D.表示有一个进程进入临界区元旦名言，另一个进程等待进入
4.以下调度算法中励志名人名言大全，会出现饥饿的是陈毅的故事。
A.短作业优先B.先来先服务C.时间片轮转D个性测试.最高响应比优先
第3页共5页
5台湾投票最新消息出炉.产生系统死锁的原因可能是由于_____________。
A.进程释放资源 B大鱼海棠壁纸.一个进程进入死循环
C客户总监.多个进程竞争,资源出现循环等待 D.进程退出
6手机地址.采用动态重定位方式装入的作业，其地址转换工作是在____________完成的。
Amaitian.装入作业时 B.作业被选中时
C.每次被移动时 D.每执行一条指令时
7.＂设备独立性＂的含义是__________。
A．每一台设备都有一个唯一的编号
B．程序中使用的设备与实际使用哪台设备无关
C．多台设备不能并行工作
D．一个通道上只准连接一台设备
8欢乐颂2剧情介绍分集.页式存储管理中，作业的逻辑地址空间为16MB，其中每页的大小4KB，则作业的页数为
______页体育工作总结。
A青年奥林匹克运动会.1KB.2KC无尽的平安夜.4KD圣诞老人英语.8K
9好军嫂事迹材料.如果不允许不同用户的文件可以具有相同的文件名，通常采用_______来保证按名存取的
安全。
A.重名翻译机构 B死得其所的所的意思.建立索引表
C.建立指针 D转瞬为风.多级目录结构
10鲸的自述作文.按逻辑结构可把文件分为记录式文件和______两类。
A华硕笔记本推荐.流式文件B伤感短语.索引文件Cangel歌词.链式文件D.顺序文件
二、简答题（每题5分毕业设计总结，共15分）
1突发奇想造句.进程的三种基本状态是什么？有哪些状态转换？哪些事件可能引起不同状态间的转