当前位置：问答库＞考研试题

一、填空题

1． 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。

【答案】m/2

【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。

2． 有向图G=（V ，E ）, 其中V （G ）=[0, 1，2，3，4, 5}, 用三元组表示弧及弧上的权d 。 E （G ）为 E （G= {<0，5, 100>, <0，2，10>, <1，2，5>，<0，4, 30>，<4, 5, 60>，<3，5, 10>，<2. 3，50>， <4, 3, 20>}，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。

【答案】50; 4

3． 设二维数组A 的行和列的下标范围分别为

【答案】

当其值为

和

每个元素占2个单元，按行优先顺处的元素为_____。

序存储，第一个元素的存储起始位置为b ，则存储位置为

【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是时，则i=2，j=3。

4． —个字符串中_____称为该串的子串。

【答案】任意个连续的字符组成的子序列 5

．

求REPLACE （S ，V , m ）=_____。

【答案】

已

知

6． 每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_____。

【答案】前序是

。

.

，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的

【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的

7． 文件可按其记录的类型不同而分成两类，即_____和_____文件。

【答案】操作系统文件；数据库

8． 在有n 个顶点的有向图中，每个顶点的度最大可达。

【答案】2（n-l ）

【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。

9． 设数组的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素为_____。

【答案】9174；8788

【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，

则它的存储地址为

若以列序为主存储顺序，则它的存储地址为

10．二叉树由_____，_____，_____三个基本单元组成。

【答案】根结点；左子树；右子树

的存储地址为_____；若以列序为主序顺序存储，则元素

的存储地址

二、算法设计题

11．给定一个整数数组求出b 中最长平台的长度。

【答案】算法如下：

12．令G=（V , E）为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下 条件：若从顶点i 至顶点j 有一条弧，则应使i

【答案】算法如下：

//对以邻接表存储的DAG 图g 重新编号, 使若有

i< j

中连续的相等元素构成的子序列称为平台。试设计算法，

//求各顶点的入度

//记录结点的逆序序号

13．用邻接多重表存储结构，编写FIRST-ADJ （G ，V ）函数，函数返回值为第一个邻接点，若V 没有邻接点，返回零。

【答案】算法如下：

//在邻接多重表g 中，求v 的第一邻接点, 若存在，返回第一邻接点，否则返回0

（

//确定顶点v 在邻接多重表向量中的下标, 不考虑不存在v 的情况

//取第一个边结点

//返回第一邻接点，ivex 和jvex 中必有一个等干

i

14．设T 是一棵满二叉树，写一个把T 的后序遍历序列转换为前序遍历序列的递归算法。

【答案】算法如下：

//将满二叉树的后序序列转为前序序列，11、hl 、12、h2是序列初始和最后结点的下标。

//根结点

//左子树或右子树的结点数

//将左子树前序序列转为

后序序列

后序序列

//将右子树前序序列转为