2016年真题823数据结构+操作系统(2016-B)

2016年真题823数据结构+操作系统(2016-B)

ID:33991069

大小:166.50 KB

页数:6页

时间:2019-03-03

2016年真题823数据结构+操作系统(2016-B)_第1页
2016年真题823数据结构+操作系统(2016-B)_第2页
2016年真题823数据结构+操作系统(2016-B)_第3页
2016年真题823数据结构+操作系统(2016-B)_第4页
2016年真题823数据结构+操作系统(2016-B)_第5页
2016年真题823数据结构+操作系统(2016-B)_第6页
资源描述:

《2016年真题823数据结构+操作系统(2016-B)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、桂林电子科技大学2016年硕士研究生统一入学考试试题科目代码:823科目名称:数据结构+操作系统请注意:答案必须写在答题纸上(写在试题上无效)。答题纸请注明页码与总页数。PARTI:数据结构一、判断题。对每小题描述的正确性进行判定,正确的标记为T,错误的标记为F(5小题,每小题3分,共15分)1)在线性表的顺序存储结构中,逻辑上相邻的数据元素在物理位置上也是相邻的()2)哈夫曼树中不存在度为1的结点()3)直接插入排序、简单选择排序、冒泡排序均具有相同的最坏时间复杂度()4)迪杰斯特拉算法用于在无向连通图中找出最小生成树()

2、5)给定二叉树的前序周游序列和后序周游序列,可以唯一地确定一棵二叉树()二、单项选择题(5小题,每小题3分,共15分)1)下列给定程序段的时间复杂度是()for(i=0;i

3、先估计所需存储空间大小C.插入与删除时不必移动元素结点D.所需空间与线性表长度成正比3)有向图的边集为{,,,,,,},下面正确的拓扑排序是()A.aebdcfB.acefbdC.aecdcfD.acefbd4)二分查找法适用于存储结构为()且按关键字排序的线性表A.顺序存储B.链接存储C.顺序存储或链接存储D.索引存储5)对一个由n个整数组成的序列,借助排序过程找出其中的最大值,希望比较次数和移动次数最少,应选用()方法。A.归并排序B.直接插入排序C.

4、直接选择排序D.快速排序第6页共6页三、分析与算法设计题(4小题,共45分)1)采用长度为7的一维数组(下标是0..6)表示哈希表。采用双散列函数解决哈希冲突,h(key)=(h1(key)+i*h2(key))mod7,i=0,1,2,…。其中h1(key)=keymod7,h2(key)=(1+k)mod5。如果到达的键值分别是8,1,15,4,16,请(a)请构造哈希表(5分)(b)计算上述哈希表在等概率情况下成功检索时的平均检索长度(5分)2)下面的算法对一个由非零整数组成的序列进行重排列,将负数排在前面,正数排在后

5、面void swap(int array[], int i, int j){int tmp=array[i];array[i]=array[j];array[j]=tmp;}void Sort (int array[], int n) { int i, j; i = 0; j = n-1; while (i < j) {    while(array[i]<0) ; (S1)   while(array[j]>0) ;(S2)   if () break; (S3)   swap(array, i, j);    i++; 

6、j--; } }(a)请将空白处的代码补充完整(6分)(b)若有数组int a[]={10,-6,-3,20,-18,5,9,-16},则执行Sort(a, 8)后,请给出数组a的值(4分)3)图G={V1,V2,V3,V4,V5,V6,V7,V8},其邻接表存储如图1所示。请基于该邻接表存储结构:(a)给出从顶点V4出发的广度优先遍历序列(请注意该答案唯一,5分)(b)给出从顶点V2出发的深度优先遍历序列(请注意该答案唯一,5分)第6页共6页图1邻接表4)下面代码的主要功能是借助于栈的作用,将循环队列的内容倒置,循环队列和

7、栈均采用数组存储(假设队列和栈的存储空间均足够大),图2给出了将队列进行倒置的示意图。请根据上述要求将下面的代码补充完整。(15分)图2队列内容逆置示意图#defineMAXSIZE100//队列定义typedefstructQueue{DataTypedata[MAXSIZE];intfront,rear;//队头指针和队尾指针,队头指针始终指向队列第一个元素的前一个位置,队尾指针始终指向队列的最后一个元素}Queue;第6页共6页//栈定义typedefstructStack{DataTypedata[MAXSIZE];

8、inttop;//栈顶指针,其始终指向栈顶元素}Stack;Queue*Reverse(Queue*q){Stack*s=(Stack*)malloc(sizeof(Stack));s->top=-1;while((a)){(b);(c);s->data[s->top]=q->data[q

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。