2015 年河南财经政法大学数据结构考研真题
一、选择题(本题共 10 个小题,每小题 3 分,共计 30 分)
1.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为(
)。
(A)存储结构
(B)逻辑结构
(C)顺序存储结构
(D)链式存储结构
2. 一个向量第一个元素的存储地址是 100,每个元素的长度为 2,则第 5 个元素的地址是
(
)。
(A)110
(B)108
(C)100
(D)120
3. 设有一个长度为 n 的顺序表,要在第 i 个元素之前(也就是插入元素作为新表的第 i 个元
素),则移动元素个数为(
)。
A.n-i+1
B.n-i
C.n-i-1
D.i
4. 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动(
)
个元素。
(A)8
(B)63.5
(C)63
(D)7
5 判定一个队列 QU(最多元素为 m0)为满队列的条件是(
)。
(A)QU->rear - QU->front = = m0
(B)QU->rear - QU->front -1= = m0
(C)QU->front = = QU->rear
(D)QU->front = = QU->rear+1
6. 链表是一种采用(
)存储结构存储的线性表。
(A)顺序
(B)链式
(C)星式
(D)网状
7. 线性表若采用链式存储结构时,要求内存中可用存储单元的地址(
)
(A)必须是连续的
(B)部分地址必须是连续的
(C)一定是不连续的
(D)连续或不连续都可以
8. 线性表L在(
)情况下适用于使用链式结构实现。
(A)需经常修改L中的结点值 (B)需不断对L进行删除插入
(C)L中含有大量的结点
(D)L中结点结构复杂
9. 若已知一个栈的入栈序列是 1,2,3,…,n,其输出序列为 p1,p2,p3,…,pn,若 p1=n,
则 pi 为(
)。
(A)i
(B)n=i
(C)n-i+1
(D)不确定
10.设某无向图中有 n 个顶点 e 条边,则该无向图中所有顶点的度之和为(
)。
(A) n
(B) e
(C) 2e
(D) 7
二、填空题(本题共 10 个小题,每小题 3 分,共计 30 分)
1.设有一个顺序共享栈 S[0:n-1],其中第一个栈项指针 top1 的初值为-1,第二个栈顶指针
top2 的初值为 n,则判断共享栈满的条件是____________________。
2.在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。
3.设有一个 n 阶的下三角矩阵 A,如果按照行的顺序将下三角矩阵中的元素(包括对角线上元
素)存放在 n(n+1)个连续的存储单元中,则 A[i][j]与 A[0][0]之间有_______个数据元素。
4.设一棵完全二叉树的顺序存储结构中存储数据元素为 ABCDEF,则该二叉树的后序遍历序列为
___________。
5.设一组初始记录关键字序列(k1,k2,……,kn)是堆,则对 i=1,2,…,n/2 而言满足的条件
为_______________________________。
6.设关键字序列为(Kl,K2,…,Kn),则用筛选法建初始堆必须从第______个元素开始进行筛选。
7.设有一组初始关键字序列为(24,35,12,27,18,26),则第 3 趟直接插入排序结束后的结
果的是________________________。
8.设有一组初始关键字序列为(24,35,12,27,18,26),则第 3 趟简单选择排序结束后的结
果的是________________________。
9.设一棵二叉树的前序序列为 ABC,则有______________种不同的二叉树可以得到这种序列。
10.设输入序列为 1、2、3,则经过栈的作用后可以得到___________种不同的输出序列。
三、判断题(本题共 10 个小题,每小题 3 分,共计 30 分)
(请在小题括号内打√或×)
(
(
(
(
(
(
(
(
(
)1.调用一次深度优先遍历可以访问到图中的所有顶点。
)2.分块查找的平均查找长度不仅与索引表的长度有关,而且与块的长度有关。
)3.冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。
)4.满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。
)5.设一棵二叉树的先序序列和后序序列,则能够唯一确定出该二叉树的形状。
)6.层次遍历初始堆可以得到一个有序的序列。
)7.设一棵树 T 可以转化成二叉树 BT,则二叉树 BT 中一定没有右子树。
)8.线性表的顺序存储结构比链式存储结构更好。
)9.中序遍历二叉排序树可以得到一个有序的序列。
(
)10.快速排序是排序算法中平均性能最好的一种排序。
四、简答题(本题共 2 个小题,每小题 15 分,共计 30 分)
1.设无向图 G(如图 1 所示),给出该图的最小生成树上边的集合并计算最小生成树各边上的
权值之和。
2.从空树起,依次插入关键字 37,50,42,18,48,12,56,30,23,构造一棵二叉排序树。
图 1
(1)画出该二叉排序树;
(2)画出从(1)所得树中删除关键字为 37 的结点之后的二叉排序树。
五、算法设计题(本题共 2 个小题,每小题 15 分,共计 30 分)
1. 设计在链式存储结构上建立一棵二叉树的算法。
2.设计在单链表中删除值相同的多余结点的算法。