数据结构10年考研试题及答案(整理)
- 格式：doc
- 大小：40.00 KB
- 文档页数：7
数据结构考试重点及部分答案
自己做的答案 不是很正确 如果有问题请联系 后面的大题不知道原题，所以不知道怎么做 见谅！！！
题型和分值
选择题：15*2=30
填空题：10*2=20
解答题：5*4=20
算法阅读题：5*4=20
算法设计题：10
1 栈的进栈、出栈函数顺序，求一个表达式的顺序
eg：进栈顺序是123 计算 POP(S)+2 POP(S) =3+2*2=7
2 给定二叉排序树的数据 求平均查找长度
Eg：已知长度为9的表{16 ，3 ，7 ，11 ，9 ，26，18，14，15}，建立二叉顺序树后进行查找，则等概率的情况下查找成功的平均查找长度为（ ）
二叉排序树（Binary Sort Tree）又称二叉查找树。
它或者是一棵空树；或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树； 根据上述性质，按照给出的表，建立的树如下图：（旁边的数表示查找长度）
平均查找长度为：（1+2+2+3+3+4+5+5+6）/9 = 31/9
3 树的概念
树是n(n>=0)个结点的有限集
4 二重循环的平均时间复杂度的求解（使用嵌套、统计次数）
时间复杂度：该算法的运行时间与问题规模的对应关系，时间复杂度用T（n）=O（f（n））来表示
Eg：S=0
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
s=s+1
答案为0（n*m)
求解算法复杂度时：
1、首先确定核心操作。
很显然此算法中，核心的操作是s=s+1;
2.这个算法中，存在两重循环。第一重循环n次，第二重循环m次，总共执行核心操作n*m次。
3.确定此算法的时间复杂度为：O (n*m)
若复杂度为 O (n*n)，则算法可以是如下的样子：
S=0
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
s=s+1
5 单链表中 R是P的前驱，在P Q之间插入S，则则如何插入（语句表示）
在相邻元素R、P之间插入一个值为X的数据元素的基本操作步骤：
（1）生成一个数据域值为X的结点S
（2）使X结点的指针域指向结点P：S->next=P->next
（3）修改R结点的指针域指向结点X：P->next=S
6 已知顺序表，求查找X的平均查找长度
(n+1)/2
7 栈的插入和删除的位置
栈顶
8 已知入队序列 求出队序列
原则：先进先出
9 在图中，所有度数和等于边的几倍
两倍
10 邻接矩阵中行和列分别表示什么意思
无向图邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。
有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非零元素个数之和。
11 串的基本概念
串（字符串）是由零个或多个字符组成的有限序列，只有当两个串的长度相等，并且各个对应位置的字符都相等时才相等
12 将一棵100个结点的完全二叉树，从根结点编号，则非叶子结点的最大编号是多少？
50
13.直接插入排序中循环的次数 课本第266页 正序：n-1 逆序：（n+2）（n-1）/2 随即：n^2/4
14 数据结构的二元组中R表示什么
R表示数据结构中数据元素上关系的有限集
15. 关键路径是什么
关键路径：网络终端元素的元素的序列，该序列具有最长的总工期并决定了整个项目的最短完成时间。
16 串的三种存储表示方式
定长顺序存储表示 堆分配存储表示 串的块链存储表示
17 已知一个广义表，求其中的一个元素
EG：广义表L=（a,（b，(c,(d)),e）,f）
通过表头和表尾求出单元素c
（1）L1=Tail(L)=((b,(c,(d)),e)f)
(2) L2=Head(L1)=(b,(c,(d)),e)
(3)L3=Tail(L2)=（（c（d））,e）
(4)L4=Head(L3)=(c,(d))
(5)L5=Head(L4)=c
总的操作：Head(Head(Tail(Head（Tail(L)))))
18 一个满二叉树的深度为K，则有多少个也叶子结点？
2^(k-1)
19 N个顶点有向完全图包含的边数
n(n-1)
20 单链表和循环链表的判空条件分别是什么
Head->next=head
21 N个元素的一维数组，求循环队列 (不会做) 22 数据结构按逻辑分为什么
线性结构和非线性结构
23 非线性结构中最重要的是什么
树型结构
24 一个只有度数为3和度数为0的树，求叶子结点
2k+1
25 顺序查找成功时所用的比较次数是多少
如果每次都成功，则比较次数是n/2
否则比较次数是（n+1）/2
26 已知无向图，顶点集是V，边集是E，求遍历方式
1、深度优先搜索
注意：每个结点只能被访问一次，又因为一个结点可以和其它的任何结点相邻接，
为了避免对一个结点的重复访问，必须对访问过的结点加以标记。
结点的邻接结点的次序是任意的，因此深度优先搜索的序列可能有多种。
深度优先搜索类似于树的前序周游。
访问方式：1、选中第一个被访问的结点。
2、对结点作已访问过的标志。
3、依次从结点的未被访问过的第一个、第二个、第三个…… 邻接结
点出发，进行深度优先搜索。转向2。
4、如果还有顶点未被访问，则选中一个起始结点，转向2。
5、所有的结点都被访问到，则结束。
Boolean visited[MAX] ; //用于标识结点是否已被访问过
Status ( * VisitFunc) (int v); //函数变量
void DFSTraverse( Graph G, Status ( * VisitFunc) (int v));
{ VisitFunc = Visit;
for ( v=0; v
for ( v=0; v
if ( ! Visited[ v ] ) DFS(G, v )
}
void DFS( Graph G, int v );
{ Visited[v] = true; VisitFunc(v);
for ( w = FirstAdjVex(G, v) ; w ; w = NextAdjVex(G, v, w) )
if ( ! Visited[ w ] ) DFS(G, w )
}
2、广度（宽度）优先搜索
注意：每个结点只能被访问一次，又因为一个结点可以和其它的任何结点相邻接， 为了避免对一个结点的重复访问，必须对访问过的结点加以标记。
结点的邻接结点的次序是任意的，因此广度优先搜索的序列可能有多种。
广度优先搜索类似于树的从根出发的按层次遍历。
访问方式：1、选中第一个被访问的结点 V
2、对结点 V 作已访问过的标志。
3、依次从结点 V 的未被访问过的第一个、第二个、第三个……第 M个
邻接结点 W1 、W2、W3…… Wm ，且进行标记。
4、依次访问结点 W1 、W2、W3…… Wm的邻接结点，且进行标记。
5、如果还有结点未被访问，则选中一个起始结点，也标记为V，转向2。
6、所有的结点都被访问到，则结束。
void BFSTraverse( Graph G, Status ( * VisitFunc) (int v));
{ VisitFunc = Visit;
for ( v=0; v
InitQueue(Q);
for ( v=0; v
if ( ! Visited[ v ] )
{ Visited[ v ] = TRUE; Visit(v); EnQueue(Q,v);
while (!EmptyQueue(Q))
{ DeQueue(Q,u);
for ( w = FirstAdjVex(G, u) ; w ; w = NextAdjVex(G, u, w) )
if ( ! Visited[ w ] )
{ Visited[ v ] = TRUE; Visit(v); EnQueue(Q, w) } ;
}
}
27 已知一个森林，画出二叉树并写出中序序列
森林与二叉树的转换见课本137页
二叉树的中序序列操作见课本128页
28 给出有向图的边集和顶点集，画出有向图，根据有向图写出拓扑排序序列
解决方案见课本182页
29 用线性探测法构造哈希图并处理冲突，写出查找成功时的平均查找长度 哈希表见课本251页
构造哈希图的方法是除留余数法 课本255页
处理冲突的方法是线性探测法 课本257页
查找长度 课本260和261页
30 判断字符串是否对称字符串 用函数填写
31 对顺序表R按递增直接插入排序
32 对整型数组进行折半查找
33 已知递归参数，则调用递归函数的返回值
34 已知单链表的头指针 head
（1）使用遍历方法输出接点的个数
（2）在链表中查找分数最低的结点并删除该结点
