二O 一四年招收硕士研究生入学考试试题
考试科目代码及科目名称:856数据结构(C 语言版)
答题内容写在答题纸上,写在试卷或草稿纸上一律无效考完后试题随答题纸交回。考试时间3小时,总分值
150
分。
姓名:
报考专业:
准考证号码:密封线内不要写题
一、选择题(10小题,每题2分,共20分)
1.算法分析的主要内容是()。
A)正确性B)可读性和稳定性C)简单性D)空间复杂性和时间复杂性2.线性表若采用链式存储结构时,要求内存中可用存储单元的地址()。
A)必须是连续的B)部分地址必须是连续的C)一定是不连续的D)连续或不连续都可以
3.设有6个元素按1、2、3、4、5、6的顺序进栈,下列不合法的出栈序列是()。
A)234165B)324651C)431256D)546321
4.设有二维数组A[1..12,1..10],其每个元素占4个字节,数据按行优先顺序存储,第一个
元素的存储地址为100,那么元素A[5,5]的存储地址为()。A)76B)176C)276D)376
5.已知一棵二叉树的先序序列为ABDGCFK,中序序列为DGBAFCK,则后序序列为()。
A)ACFKDBG B)GDBFKCA C)KCFAGDB D)ABCDFKG 6.在二叉树结点的先序,中序和后序序列中,所有叶子结点的先后顺序()。
A)都不相同B)完全相同C)先序和中序相同,而与后序不同D)中序和后序相同,而与先序不同7.图的深度优先遍历类似于二叉树的()。
A)先序遍历B)中序遍历C)后序遍历D)层次遍历8.下面()算法适合构造一个稠密图G 的最小生成树。
A)Prim 算法B)Kruskal 算法C)Floyd 算法D)Dijkstra 算法9.对关键码{46,79,56,38,40,84}采用堆排序,则初始化堆(小堆)后最后一个元素是()。
A)84B)46C)56D)3810.在Hash 函数H(k)=k MOD m 中,一般来讲m 应取()。
A )奇数
B )偶数
C )素数
D )充分大的数
二、填空题(10小题,每题2分,共20分)
1.在单向链表某P 结点之后插入S 结点的操作是()。
2.线性表L用数组表示,假定删除表中任一元素的概率相同,则删除一个元素平均需要移动
元素的个数是()。
3.一个栈的输入序列是:1,2,3则不可能的栈输出序列是()。
4.一棵二叉树高度为h,所有结点的度或为0,或为2,则该二叉树最少有()结点。
5.在完全二叉树中,编号为i 和j 的两个结点处于同一层的条件是()。
6.若无向图G=(V,E),其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)},现采
用图的()遍历方法从顶点a开始遍历图,得到的序列为abecd。
7.求最短路径的Dijkstra算法的时间复杂度为()。
8.假定有k个关键字互为同义词,若用线性探测再散列法把这k个关键字存入散列表中,至
少要进行()次探测。
9.设在已排序的线性表中共有元素n个,若用二分法查找表中的元素。若查找成功,至少要
比较()次
10.对一组记录(54,38,96,23,15,2,60,45,83)进行直接插入排序,当把第7个记录60插入
到有序表时,为寻找插入位置需比较()次。
三、综合应用题(7小题,每题10分,共70分)
1.已知A[1..N]是一棵顺序存储的完全二叉树,如何求出A[i]和A[j]的最近的共同祖先?
2.请给出一棵哈夫曼树中分支数B与叶子节点数n0所满足关系式,并证明你的结论。
3.下面的排序算法的思想是:第一趟比较将最小的元素放在r[0]中,最大的元素放在r[n-1]
中,第二趟比较将次小的放在r[1]中,将次大的放在r[n-2]中,…,依次下去,直到待排序列为递增序。(注:<-->代表两个变量的数据交换)。
void sort(SqList&r,int n)
{i=0;
while((1))
{min=max=i;
for(j=i+1;(2);++j)
{if((3))min=j;else if(r[j].key>r[max].key)max=j;}
if((4))r[min]<-->r[i];
if(max!=n-i-1)
{if((5))r[min]<-->r[n-i-1];else r[max]<-->r[n-i-1];}
i++;
}
}//sort
4.如下图所示的AOE网
(1)写出所有的拓扑序列
(2)求各顶点代表的事件的最早发生时间和最迟发生时间
(3)求各条弧代表的活动的最早开始时间和最迟开始时间
(4)给出其关键路径
5.设哈希函数H(K)=3K mod11,哈希地址空间为0~10,对关键字序列(32,13,49,
24,38,21,4,10),按下述两种解决冲突的方法构造哈希表,并分别求出等概率下查找
成功时和查找失败时的平均查找长度ASL
succ 和ASL
unsucc
。
(1)线性探测法(2)链地址法
6.全国有10000人参加竞赛,只录取成绩优异的前10名,并将他们从高分到低分输出。而
对落选的其他考生,不需排出名次,问此种情况下,用何种排序方法速度最快?为什么?
7.假定对有序表(3,4,5,17,24,35,40,54,58,72,80,123)进行折半查找,试回答问题:
(1)画出描述折半查找过程的判定树;
(2)若查找元素54,需依次与那些元素比较?
(3)若查找元素20,需依次与那些元素比较?
(4)分别求等概率情况下查找成功和不成功时的平均查找长度。
四、算法设计与编程(4小题,每题10分,共40分)
1.设有一头指针为L的带有表头结点的非循环双向链表,其每个结点中除有pred(前驱指
针),data(数据)和next(后继指针)域外,还有一个访问频度域freq。在链表被启用前,其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时,令元素值为x的结点中freq域的值增1,并使此链表中结点保持按访问频度非增(递减)的顺序排列,同时最近访问的结点排在频度相同的结点的最后,以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法,该运算为函数过程,返回找到结点的地址,类型为指针型。
2.已知二叉树用下面的顺序存储结构,写出先序遍历该二叉树的算法。
123456789
data A B C D E F G H I
Lc240008000
Rc356079000
3.编写在后序线索二叉树中求任一结点直接前驱的算法(结点结构包括数据域data、左孩
子域left、右孩子域right、左标志域ltag和右标志域rtag,标志域为0表示没有孩子,孩子域为线索)。
4.有n个记录存储在带头结点的双向链表中,现用双向冒泡排序法对其按上升序进行排序,
请写出这种排序的算法。(注:双向冒泡排序即相邻两趟排序向相反方向冒泡)。