南京林业大学考研真题—数据结构2004
- 格式：docx
- 大小：17.15 KB
- 文档页数：6
南 京 林 业 大 学
2004年攻读硕士学位研究生入学考试
数 据 结 构 试题
注意事项：
1. 答案一律写在答题纸上；
2. 答案卷应字迹清楚、语义确切；
3. 算法应对主要数据类型、变量给出说明，所写算法应结构清晰、简明易懂，可加上必要的注释；
4. 算法可用（类）PASCAL语言、C语言等你所熟悉的高级语言编写，但要注明语种。
一、单项选择题（本大题共15小题，每小题2分，共30分）
1. 算法指的是（ ）。
A．计算机程序 B．解决问题的计算方法
C．排序算法 D．解决问题的有限运算序列
2. 线性表采用链式存储时，结点的存储地址（ ）。
A．必须是不连续的 B．部分地址必须是连续的
C．连续与否均可 D．和头结点的存储地址相连续
3. 若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为s1,s2,s3,…sn,若s1=n, 则si为（ ）。
A．i B．n=i C．n-i+1 D．以上都不对
4. 算法的时间复杂度取决于（ ）。
A．问题的规模 B．待处理数据的初态
C．A与B都对 D．算法的易读性
5. 将两个各有n1和n2个元素的有序表(递增)归并成一个有序表，仍保持其递增顺序，则最少的比较次数是（ ）。
A．n1 B．n2 C．n1+n2-1 D．min (n1,n2)
6. 一个非空广义表的表头（ ）。
A．不可能是子表 B．只能是子表
C．只能是原子 D．可以是子表或原子
7. 深度为6的二叉树至多有（ ）个结点。
A．32 B．40 C．63 D．64
8. 下面哪一个方法可以判断出一个有向图中是否有环（回路）（ ）。
A．广度优先遍历 B．拓朴排序
C．求最短路径 D．求关键路径
9. 按照二叉树的定义，具有3个结点的二叉树有( )种。
A．3 B．4 C．5 D．6 10. 在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( )。
A．e B．2e C．n2－e D．n2－2e
11. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是( )的二叉树。
A．空或只有一个结点 B．任一结点只有左孩子
C．高度等于其结点数 D．任一结点只有右孩子
12. 一个具有n个顶点的无向图最多有( )条边。
A．n B．n(n-1) C．n(n-1)/2 D．2n
13. 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：
20，15，21，25，47，27，68，35，84
15，20，21，25，35，27，47，68，84
15，20，21，25，27，35，47，68，84
则所采用的排序方法是（ ）。
A．选择排序 B．希尔排序 C．归并排序 D．快速排序
14. 假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是( )。
A．O(n) B．O(e) C．O(n+e) D．O(n*e)
15. 下述二叉树中,哪一种满足性质：从任意结点出发到根的路径上所经过的结点序列按其关键字有序：（ ）。
A．哈夫曼树 B．AVL树 C．堆 D．二叉排序树
二、填空题：（本大题共15小题，每小题2分，若有两个空格，每个空格1分，共30分）
1．评价算法的效率性能从利用计算机资源角度看主要从 和
两个方面进行分析。
2．有一个含头结点的单重循环链表，头指针为head,则判断其是否为空的条件为： 。
3．用数组Queue（其下标在0～n-1中，共有n个元素）表示一个循环队列，front为当前队头元素的前一位置，rear为队尾元素的位置。假定队列中元素个数总小于n，则队列中元素个数为： 。
4．设栈S和队列Q的初始状态为空，元素a,b,c,d,e,f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b,d,c,f,e,a,则栈S的容量至少应该是 。
5．设n行n列的上三角矩阵A已压缩存储到一维数组B[1..n*(n+1)/2]中，且按行为主序存储，则aij对应的B中的存储位置为 。
6．从任何一个结点开始都能成功查找其他结点的单链表是 表。
7．设SS[1..maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，当栈未满时，将元素e压入栈需执行下列语句： 和 。
8．所有结点的前驱和后继的个数都没有限制的数据结构是 结构。
9．若一个二叉树的叶子结点，是某子树的中序遍历序列中的最后一个结点，则它必是该子树的 序列中的最后一个结点。
10．用二分法查找一个线性表时，要求线性表必须以 方式存储，且 。
11．采用散列法实现查找时，需要解决的主要问题有： 和 。
12．设广义表L=（（（a））），则该广义表的长度是 ，深度是 。
13．有向图G有n个顶点{v1,v2,…,vn}，它的邻接矩阵为A，A[i,j]=1表示vi到vj存在邻接关系，而A[i,j] =0表示不存在邻接关系。则G中顶点vi的度为 。
14．n个顶点的有向强连通图用邻接矩阵表示时，该矩阵至少有 个非零元素。
15．若一个二叉树含有n个结点，则它的二叉链表中必有 个空的链域。
三、是非题：（判断下列各题是否正确，正确的在括号内打 “√”，错的打“×”。每小题2分，共20分）
1．线性表的逻辑顺序与存储顺序总是一致的。（ ）
2．消除递归不一定需要使用栈。（ ）
3．队列是后进先出的线性表。（ ）
4．任何一个数据结构至少有一个结点没有前驱。（ ）
5．将一棵树转换成二叉树后，根结点没有左子树。（ ）
6．若采用以行序为主序三元组表示法存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。（ ）
7．对于不同的存储结构，应采用不同的检索方法。（ ）
8．如果一个二叉树中没有度为1的结点，则必为满二叉树。（ ）
9．树和二叉树的逻辑结构是一致的。（ ）
10．不仅需要使用内存，而且还要使用外存的排序称为外排序。（ ）
四、解答题：（本大题共5小题，每小题4分，共20分）
1．将算术表达式 ((a+b)+c*(d+e)+f)*(g+h) 转化为二叉树。(注：括号无需在树中出现)
2．子串的定位运算通常称为串的模式匹配，是各种串处理系统中最重要的运算之一，其中KMP匹配算法是效率较高的方法。
（1） 请问KMP匹配算法的基本思想是什么？
（2） 求字符串’ababaababcabb’的NEXT数组。
3．假设用下述两种结点的链表作广义表的存储结构：
表结点
原子结点
试画出广义表LA=((((a),b)), ((( ), (d)), (e,f)))的存储结构。
4．（1）若一棵二叉树先序遍历与中序遍历的次序分别为:
先序序列:ABDEHCFGI；中序序列：DBEHAFCIG。试画出这棵二叉树。
（2）给出二叉树的先序和中序序列、中序和后序序列、先序和后序序列。试问是否在任何情况下都可确定唯一的一棵二叉树；若有不能者，请举出一个反例说明之。
5．设有向图G为：
tag=1 hp(表头指针) tp(表尾指针)
tag=0 data(值域)
（1） 写出所有的拓朴序列；
（2） 在图中添加一条弧，使得仅可能有唯一的拓朴序列。
五、算法阅读题：（本大题共2小题，每小题5分，共10分）
1．设有算法如下:
typedef int KeyType;
typedef struct
{ KeyType key;
OtherType other_data;
}ListType;
void function(ListType R[ ],int length)
{ int i,j;
for(i=2;i
{ R[0]=R[i]; j=i-1;
while (R[0].key
{ R[j+1]=R[j];j=j-1;}
R[j+1]=R[0];
}
}
请回答下面两个问题：
（1）该算法的功能是什么？
（2）这个算法是否稳定？并请说明你的理由。
2．设有算法如下：
#define NULL 0
typedef struct node
{ KeyType key;
struct node *lchild, *rchild;
}BSN, *BST;
void unknown (BST *bs, KeyType key)
{ BST s; V1
V3
V4 V2 if (*bs== NULL)
{ s=(BST)malloc(sizeof(BSN));
s->key=key;
s->lchild=NULL;
s->rchild=NULL;
*bs=s;
}
else if ( key= = (*bs)->key)
printf (“The node exists in the binary tree!”);
else if (key <(*bs)->key)
unknown (&((*bs)->lchild),key);
else
unknown (&((*bs)->rchild),key);
}
函数unknown实现了对二叉排序树的一种运算；
（1）试说明unknown的功能。
（2） 若root是BST型变量，且root指向如下二叉树的根结点，试画出执行完unknown (root,‘X’) 后，root指向的二叉树。
六、算法设计题：（本大题共3小题，共４0分）
