暨南大学计算机学科与技术基础综合研究生考研考试真题.docx
- 文档编号:7325359
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:9
- 大小:48.70KB
暨南大学计算机学科与技术基础综合研究生考研考试真题.docx
《暨南大学计算机学科与技术基础综合研究生考研考试真题.docx》由会员分享,可在线阅读,更多相关《暨南大学计算机学科与技术基础综合研究生考研考试真题.docx(9页珍藏版)》请在冰点文库上搜索。
暨南大学计算机学科与技术基础综合研究生考研考试真题
2013年全国硕士研究生统一入学考试自命题试题(副卷)
********************************************************************************************
学科与专业名称:
计算机系统结构、计算机软件与理论、计算机应用技术、软件工程
考试科目代码与名称:
834计算机学科与技术基础综合
考生注意:
所有答案必须写在答题纸(卷)上,写在本试题上一律不给分。
一.选择题(每题2分,共30分)
1.在数据结构中,从逻辑上可以把数据分为()。
A.动态结构和静态结构B.紧凑结构和非紧凑结构
C.线性结构和非线性结构D.内部结构和外部结构
2.设某无向图中有n个顶点e条边,则该无向图中所有顶点的度之和为()。
A.nB.eC.2nD.2e
3.在内部排序中,排序时不稳定的有()。
A.插入排序B.冒泡排序C.快速排序D.归并排序
4.在循环队列中,若front与rear分别表示队头元素和队尾元素的位置,则判断循环队列空的条件是()。
A.front==rear+1B.rear==front+1C.front==rearD.front==0
5.设单链表中指针p指着结点A,若要删除A之后的结点(若存在),则需要修改指针的操作为()。
A.p->next=p->next->nextB.p=p->next
C.p=p->next->nextD.p->next=p
6.最坏情况下堆排序的时间复杂度是()。
A.O(log2n)B.O(log2n2)C.O(nlog2n)D.O(n2)
7.设使用的邻接表表示某有向图,则顶点vj在表结点中出现的次数等于()。
A.顶点vj的度B.顶点vj的出度C.顶点vj的入度D.无法确定
8.树最适合用来表示()。
A.有序数据元素B.无序数据元素
C.元素之间具有分支层次关系的数据D.元素之间无联系的数据
9.具有n个顶点的连通图至少应有()条边。
A.n-1B.nC.n(n-1)/2D.2n
10.时间复杂度不受数据初始状态影响而恒定为O(nlog2n)的是()。
A.堆排序B.冒泡排序C.希尔排序D.快速排序
考试科目:
计算机学科与技术基础综合共6页,第1页
11.任何一颗二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序()。
A.不变B.发生改变C.不能确定D.以上全不对
12.一组记录(50,40,95,20,15,70,60,45,80)进行冒泡排序时,第一趟需进行相邻记录的交换的次数为()。
A.5B.6C.7D.8
13.循环队列中是否可以插入下一个元素()。
A.与曾经进行过多少次插入操作有关.
B.只与队尾指针的值有关,与队头指针的值无关.
C.只与数组大小有关,与队首指针和队尾指针的值无关
D.与队头指针和队尾指针的值有关.
14.某二叉树的先序遍历序列为abdgcefh,中序遍历序列为dgbaechf,则它的左子树的结点数目为()。
A.3B.4C.5D.6
15.对于元素是整数(占2个字节)的对称矩阵A,采用以行序为主的压缩存储方式(下三角),若A[0][0]的地址是400,则元素A[8][5]的存储地址是(C)。
A.440B.480
C.482D.582
二.填空题(每题2分,共20分)
1.稀疏矩阵一般的压缩存储方法主要有两种,即和。
2.线性结构中元素之间存在的关系,树形结构中元素之间存在的关系。
3.由n个权值构成的哈夫曼树共有个结点。
4.在散列表(hash)查找中,评判一个散列函数优劣的两个主要条件是:
和。
5.线索二叉树的左线索指向,右线索指向。
6.在一棵二叉树中,度为零的结点的个数为n0,度为2的结点的个数为n2,则该二叉树有
个叶子结点。
7.有一个100×90的稀疏矩阵,非0元素有10,设每个整型数占2个字节,则用三元组表示该矩阵时,所需的字节数是。
8.带头结点的循环单链表L为空的条件是。
9.设给定权值集合w={9,2,5,7},对应huffman树的加权路径长度WPL为。
10.若某记录序列的关键字序列是(50,40,95,20,15,70),用简单选择法进行排序,第一次收集的结果是。
考试科目:
计算机学科与技术基础综合共6页,第2页
三.判断题(每题1分,共10分,正确的选t,错误的选f)
1.采用邻接表存储的图的深度优先遍历相当于树的中序遍历。
()
2.无向图的邻接矩阵一定是对称的。
()
3.线性表中的每一个元素都有一个前驱和后继元素。
()
4.B和B+树都能有效地支持随机查找。
()
5.拓扑排序是按AOE网中每个结点事件的最早发生事件对结点进行排序。
()
6.一颗满二叉树同时又是一颗平衡树。
()
7.对初始堆进行层次遍历可以得到一个有序序列。
()
8.冒泡排序是稳定的。
()
9.哈夫曼树中权值最小的结点离跟最近。
()
10.带权无向图的最小生成树是唯一的。
()
四.简答题(50分)
1.对图1.所示的有向带权图,使用Dijkstra(迪杰斯特拉)算法求出从顶点0到其余各顶点的最短路径,要求写出过程。
(10分)
图1.
2.设使用堆排序法对关键字序列T=(10,27,5,50,60,7,40,43,75)进行排序:
(10分)
(1)画出初始大根堆对应的完全二叉树
(2)写出大根堆序列
(3)画出第一趟排序后新堆对应的完全二叉树
3.简述下列算法的功能。
(6分)
typedefstructBiTNode{
intdata;
StructBiTNode*lchild;
StructBiTNode*rchild;
}BiTNode,*BiTree;
intfunc(BiTreeT)
考试科目:
计算机学科与技术基础综合共6页,第3页
{
if(T==NULL)return(0);
else
if(T->data==0)
return(1+func(T->lchild)+func(T->rchild));
else
return(func(T->lchild)+func(T->rchild));
}
4.使用Prime算法构造出图1所示的图G的一棵最小生成树(要求写出构造过程)。
(10分)
16
v1
v2
6
11
21
19
6
33
14
v6
v3
5
v5
v4
18
图1
5.假设二叉树采用顺序存储结构,如图2所示。
(6分)
(1)画出二叉树表示
(2)写出先序遍历,中序遍历,后序遍历的结果
A
B
C
D
E
F
G
H
I
图2
6.设关键字序列为(64,5,95,53,18,25,65,27,16),散列函数为H(key)=key%7,采用链地址法解决冲突,请回答:
(8分)
(1)画出散列表示意图(用头插法向单链表中插入结点)
(2)查找关键字95时,需要依次与哪些关键字比较
(3)求等概率下查找成功的平均查找长度
五.算法填空,(每空2分,共18分)
1.设计一个函数功能为:
在带头结点的单链表中删除值最小的元素。
请将代码补充完整。
考试科目:
计算机学科与技术基础综合共6页,第4页
typedefintDataType;
typedefstructNode
{DataTypedata;
structNode*next;
}LinkList;
voiddeleteMin(LinkList*L)
{LinkList*p=L->next,*q;
q=p;
while()
{if(p->data
q=p;
;
}
if(!
q)return;
p=L;
while(p->next!
=q)
p=p->next;
;
;
}
2以下程序使用冒泡排序法对存放在a[1],a[2],……,a[n]中的序列进行排序,完成程序中的空格部分,其中n是元素个数,要求按升序排列。
typedefstruct{
intkey;
infotypeotherinfo;
}Node;
voidbsort(Nodea[],intn)
{NODEtemp;
inti,j,flag;
for(j=1;;j++);
{flag=0;
for(i=1;;i++)
if(a[i].key>a[i+1].key)
{flag=1;
temp=a[i];
;
;
}
if()break;
}
}
考试科目:
计算机学科与技术基础综合共6页,第5页
.六.编写算法(22分)
1.设计在顺序有序表中实现折半查找的算法。
(10分)
2.设计AOV-网拓扑排序的算法(12分)
考试科目:
计算机学科与技术基础综合共6页,第6页
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 暨南大学 计算机 学科 技术 基础 综合 研究生 考研 考试