已选分类
工学
问答题一个有向图G=(V,E)的平方图G
2
=(V,E
2
)满足下述性质：(u，w)∈E
2
当且仅当存在某个顶点v∈V，使得(u，v)∈E且(v，w)∈E。写一个算法从给定的G求出G
2
，G和G
2
可分别用两个邻接表表示。【中国科学技术大学1998六(15分)】
问答题下图所示的伙伴系统中，回收两块首地址分别为768及128，大小为27的存储块，请画出回收后该伙伴系统的状态图。【北京邮电大学1996二(10分)】
问答题求出下图中顶点1到其余各顶点的最短路径。【厦门大学2002八、2(5分)】
问答题以下是一个5×5阶螺旋方阵。设计一个算法输出该形式的n×n(n＜10)阶方阵(顺时针方向旋进)。
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
问答题设某二叉树的前序遍历序列为：ABCDEFGHI，中序遍历序列为：BCAEDGHFI。(1)试画出该二叉树。(2)写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。(3)设具有4个结点的二叉树的前序遍历序列为abcd；S为长度等于4的由a，b，c，d排列构成的字符序列，若任取S作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么?试列出具有4个结点二叉树的全部形态及相应的中序遍历序列。【浙江大学1997六(15分)】
问答题假设在二叉树中值为x的结点不多于一个，试编写算法输出值为x的结点的所有祖先。
问答题设一组记录的关键字按以下次序进行插入：4、5、7、2、1、3、6，构造生成一棵平衡二叉树的过程。
问答题广义表A(b，A)的长度为 (1) ，深度为 (2) 。【电子科技大学2005二、4(1分)】
问答题什么是索引顺序文件?【哈尔滨工业大学2001三、5(3分)】
问答题给出图G：
问答题对于待排序序列{12，11，13，49，26，14，8，7}
问答题编写程序 编写程序，一个班级有n个学生，每个学生有学号、姓名和三门课的成绩。要求编程实现以下功能。 ①先输入n，再依次输入n个学生的信息。 ②按学生平均分从高到低排序。 ③将排序结果写到文件C:STU.TXT文件中，每个学生占一行。 (已知每班学生数少于100个，姓名和学号长度不超过10个字符；要求使用结构体类型。)
问答题以二叉链表作存储结钩，试编写非递归的前序遍历算法。【华南理工大学2005三、1(5分)】
问答题假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如下图所示。设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为。请设计一个时间上尽可能高效的算法，找出由str1和str2所指的两个链表共同后缀的起始位置(如图中字符i所在结点的位置p)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度。[2012年全国试题42(13分)】
问答题克鲁斯卡尔算法的时间复杂度为__________，它对__________图较为适合。【中科院计算所1999二、3(2分)】
问答题设计算法以实现对无向图G的深度遍历，要求：将每一个连通分量中的顶点以一个表的形，式输出。例如，下图的输出结果为：(1，3)(2，6，7，4，5，8)(9，10)。注：本算法中可以调用以下几个函数：firstadj(g，1，)——返回图g中顶点v的第一个邻接点的号码，若不存在，则返回0。nextadj(g，v，w)——返回图g中顶点v的邻接点中处于w之后的邻接点的号码，若不存在，则返回0。nodes(g)——返回图g中的顶点数。【合肥工业大学2000五、4(8分)】
问答题在很多查找和排序算法中，经常使用“监视哨”，其目的是什么?以顺序表上的顺序查找为例，说明如何设置“监视哨”?【江苏大学2006三、8(5分)】
问答题已知Q是一个非空队列，s是一个空栈。仅用队列和栈的ADT函数和少量工作变量，使用C语言编写一个算法，将队列Q中的所有元素逆置。栈的ADT函数有：【清华大学2000年】 makeEmpty(s：stack)； ／／置空栈 push(s：stack；value：datatype)； ／／新元素value进栈 pop(s：stack)：datatype； ／／出栈，返回栈顶值 isEmpty{s：stack)：Boolean； ／／判栈空否 队列的ADT函数有： enqueue(q：queue；value：datatype)； ／／元素value进队 deQueue(q：queue)：datatype； ／／出队列，返回队头值 isEmpty(q：queue)：boolean； ／／判队列空否
问答题己知完全二叉树结点的前序序列是abcdefghi，请画出这棵完全二叉树的逻辑结构图。
问答题指令NOP有何用途?请举例说明。