问答题以二叉链表作存储结钩，试编写非递归的前序遍历算法。【华南理工大学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有何用途?请举例说明。
问答题用列主元Gauss消去法求下面线性方程纽的解：
问答题某个任务的数据模型可以抽象为给定的K个集合：S1，S2，…，SK。其中Si(1≤i≤k)中的元素个数不定。在处理数据过程中将会涉及元素的查找和新元素的插入两种操作，查找和插入时用一个二元组(i，x)来规定一个元素，i是集合的序号，x是元素值。设计一种恰当的数据结构来存储这k个集合的元素，并能高效地实现所要求的查找和插入操作。(1)借助Pascal的数据类型来构造和描述你所选定的数据结构，并且说明选择的理由；(2)若一组数据模型为S1={10．2，1．7，4．8，16．2)，S2={1．7，8．4，0．5}，S3={4．8，4．2，3．6，2．7，5．1，3．9)，待插入的元素二元组为(2，11．2)和(1，5．3)，按你的设计思想画出插入元素前后的数据结构状态。【北京工业大学1995七(20分)】
问答题一棵二叉排序树结构如下，各结点的值从小到大依次为1～9，请标出各结点的值。【厦门大学2002八、2(5分)】
问答题已知一循环队列的存储空间为[m.n]，其中n>m，队头和队尾指针分别为front和rear，则此循环队列判满的条件是__________。【中南大学2003三、4(1分)】
问答题对于双向链表，在两个结点之间插入一个新结点需修改的指针共__________个，单链表为__________个。【南京理工大学2000二、2(3分)】
问答题有n个结点并且其高度为n的二叉树的数目是多少?【西安电子科技大学2000计算机应用一、3(5分)】
问答题试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。
问答题设某文件经内排序后得到100个初始归并段(初始顺串)，若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少?【山东大学1992一、4(3分)】【东南大学1999一、3(5分)】
问答题建立上述表格的关系图。
问答题给出循环队列中元素个数的计算式(设队最大长度为N，队首指针FRONT，队尾指针REAR)【西北大学2000二、7(5分)】
问答题写一个HeapInsert(R，key)算法，将关键字插入到堆R中，并保证插入后R仍是堆。请分析算法的时间复杂度。
将key先插入R中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，然后自下往上调整，使插入的关键字满足堆性质。 算法如下： typedef struct{ KeyType key; InfoType otherinfo; }RecType; typedef struct{ RecType Rec[MaxNum]; //MaxNum是一个常量 int len; }SeqList; HeapInsert(SeqList R, KeyType key){ int i,j; R.Rec[++R.len].key=key; //增加新值到原堆中已有元素的尾部且堆的长度加1 i=R.len/2; j=R.len; while(i＞0){ //调整为堆 if(R.Rec[i].key＜R.Rec[j].key){ R.Rec[0]=R.Rec[i]; R.Rec[i]=R.Rec[j]; R.Rec[i]=R.Rec[0]; } j=i; i=i/2; //继续自底向上查找 } } 设该堆对应的树高为h，则满足h≤log2R.len，调整是自底向上查找，最多查找到树根，所以时间复杂度为O(log2R.len)。
问答题M叉树的前序和后序遍历分别与由它转换成的二叉树的哪种遍历相对应?【中国人民大学2000一、2(4分)】