2015年南京邮电大学数据结构初试真题

琴魂醉

2015年数据结构初试题目

只能记得这么多题目了...尽力了...

判断题（共15题*2分）

1.消除递归不一定需要使用栈，此说法

2.稀疏矩阵压缩存储后，必会失去随机存取功能

3.完全二叉树中，若一个结点没有左孩子，则它必是树叶

4.连通分量是无向图的极大强连通子图

5.在9阶B-树中，除叶子以外的任意结点的分支数介于5 和9 之间

6.在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转

选择题（共15题*2分）

1.以下属于逻辑结构的是（ ）。

A．顺序表 B. 哈希表 C.有序表 D. 单链表

2.下列数据中，（ ）是非线性数据结构。

A．栈 B. 队列 C. 完全二叉树 D. 堆

3.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）储方式最节省运算时间。

A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表

4.循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。

A. rear=rear+1 B. rear=(rear+1) mod (m-1)

C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)

5.二叉树在线索后，仍不能有效求解的问题是（ ）。

A．前（先）序线索二叉树中求前（先）序后继 B．中序线索二叉树中求中序后继

C．中序线索二叉树中求中序前驱 D．后序线索二叉树中求后序后继

6.下面几个符号串编码集合中，不是前缀编码的是（ ）。

A．{0,10,110,1111} B．{11,10,001,101,0001} C．{00,010,0110,1000}

D．{b,c,aa,ac,aba,abb,abc}

7.用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( )。

A．5 B．6 C．8 D．9

8.下列关于AOE 网的叙述中，不正确的是（ ）。

A．关键活动不按期完成就会影响整个工程的完成时间

B．任何一个关键活动提前完成，那么整个工程将会提前完成

C．所有的关键活动提前完成，那么整个工程将会提前完成

D．某些关键活动提前完成，那么整个工程将会提前完成

9.m 阶B-树是一棵( )

A. m 叉排序树 B. m 叉平衡排序树 C. m-1 叉平衡排序树 D. m+1 叉平衡排序树

10.关于杂凑查找说法不正确的有几个( ) 【南京理工大学 2000 一、16 （1.5 分）】

A. 采用链地址法解决冲突时，查找一个元素的时间是相同的

B. 采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的

C. 用链地址法解决冲不易引起聚集现象

D. 再哈希法不易产生聚集

11.在下列排序算法中,哪一个算法一趟不能确定一个元素的最终位置（ ）。

A． 直接插入排序 B. 气泡排序 C. 快速排序 D. 直接选择排序

简答题（共5题*10分）

1.举例说明顺序队的“假溢出”现象，并给出解决方案

2.什么是算法，算法有哪些特征

3.设T是具有n 个内结点的扩充二叉树，I 是它的内路径长度，E 是它的外路径长度。

（1）试利用归纳法证明E=I+2n, n>=0.

（2）利用（1）的结果试说明：成功查找的平均比较次数s 与不成功查找的平均比较次数u 之间的关系可用公式表示s=(1+1/n)u-1,n>=1。

4.一个图有0,1,2,3,4,5共6个结点,插入边(1,0)(1,3)(2,1)(2,3)(3,0)(3,2)(3,4)(4,1)(4,5)

（1）画出对应的邻接矩阵

（2）写出所有强连通分量

5.试画出从空树开始，由字符序列(t,d,e,s,u,g,b,j,a,k)构成的二叉平衡树，并为每一次的平衡处理指明旋转类型。再次插入字符a，画出此时的平衡二叉树

编程题（共4题*10分）

1.实现利用队列将栈中元素逆置并说明算法

2.已知无向图采用邻接表存储方式，试写出删除边（i，j）的算法。

3.有线性表(a1,a2,…,an),采用单链表存储，头指针为H，每个结点中存放线性表中一个元素，现查找某个元素值等于X 的结点。分别写出下面三种情况的查找语句。要求时间尽量少。

（1）线性表中元素无序。（2）线性表中元素按递增有序。 （3）线性表中元素按递减有序。

4.给定集合S，S的幂集是指以集合S的所有子集为元素构成的集合，利用递归算法编程求集合S的幂集

来源: 2015年南京邮电大学数据结构初试真题