当前位置：问答库＞考研试题

桂林电子科技大学

2016年硕士研究生统一入学考试试题

科目代码: 823 科目名称: 数据结构+操作系统

请注意：答案必须写在答题纸上（写在试题上无效）。答题纸请注明页码与总页数。 PART I： 数据结构

一、判断题。对每小题描述的正确性进行判定，正确的标记为T ，错误的标记为F （5小题，每小

题3分，共15分）

1）在线性表的顺序存储结构中，逻辑上相邻的数据元素在物理位置上也是相邻的（ ）

2）哈夫曼树中不存在度为 1 的结点（ ）

3）直接插入排序、简单选择排序、冒泡排序均具有相同的最坏时间复杂度（ ）

4）迪杰斯特拉算法用于在无向连通图中找出最小生成树（ ）

5）给定二叉树的前序周游序列和后序周游序列，可以唯一地确定一棵二叉树（ ）

二、单项选择题（5小题，每小题3分，共15分）

1）下列给定程序段的时间复杂度是（ ）

for(i=0; i

for(j=0; j

c[i][j]=0;

for(i=0; i

for(j=0; j

for(k=0; k

c[i][j]=c[i][j]+a[i][k]*b[k][j];

A ．O(m*n*t) B.O(m+n+t) C.O(m*t) D.O(m*t+n)

2）单向循环链表不具有的特点是（ ）

A ．随机访问 B．不必事先估计所需存储空间大小

C ．插入与删除时不必移动元素结点 D．所需空间与线性表长度成正比

3）有向图的边集为{, , <e, b>, <e, d>, , , }，下面正确的拓扑排序是（ ）

A．aebdcf B．acefbd C．aecdcf D．acefbd

4）二分查找法适用于存储结构为（ ）且按关键字排序的线性表

A. 顺序存储 B. 链接存储 C. 顺序存储或链接存储 D. 索引存储

5）对一个由n 个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应选用（ ）方法。

A. 归并排序 B.直接插入排序 C.直接选择排序 D.快速排序

第 1 页 共 6 页