问答题设稀疏矩阵M
m
中有f个非零元素，用三元组顺序表的方式存储。请设计一个算法，计算矩阵M的转置矩阵N，要求转置算法的时间复杂度为O(n+t)。【苏州大学2005四(20分)】【中南大学2004三、4(10分)】【兰州大学2002八(10分)】
问答题举例并说明：在最坏情况下，快速排序的时间复杂度为O(n
2
)。【南京航空航天大学2005一(5分)】
问答题简单比较文件的多重表和倒排表组织方式各自的特点。【东南大学2000一、2(6分)】
问答题当你为解决某一问题而选择数据结构时，应从哪些方面考虑?【西安电子科技大学2000】
问答题评价各种不同数据结构的标准是什么?
问答题设有两个链表，ha为单向链表，hb为单向循环链表。编写算法，将两个链表合并成一个单向链表，要求算法所需时间与链表长度无关。【南京航空航天大学1997四(8分)】
问答题在等概率情况下，对具有n个元素的顺序表进行顺序查找，查找成功(即表中有关键字等于给定值K的记录)的平均查找长度为__________：查找不成功(即表中无关键字等于给定值K的记录)的平均查找长度为__________。【哈尔滨工业大学2005一、3(1分)】
问答题对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为__________，在给定值为x的结点后插入一个新结点的时间复杂度为__________。【哈尔滨工业大学2001一、1(2分)】
问答题用栈实现将中缀表达式8一(3+5)*(5—6／2)转换成后缀表达式，画出栈的变化过程图。【南京航空航天大学2001五(10分)】
问答题证明：在二叉树的三种遍历序列中，所有叶子结点间的先后关系都是相同的。要求每步论断都指出根据。【北京工业大学2001二、3(5分)】
问答题顺序存储结构是通过__________表示元素之间的关系的；链式存储结构是通过__________表示元素之间的关系的。【北京理工大学2001七、2(2分)】
问答题设计算法求距离顶点V
0
的最短路径长度(以弧数为单位)为K的所有顶点，要求尽可能地节省时间。【东南大学2002八(10分)2005五(10分)】
问答题有n个顶点的有向图，至少需要__________条弧才能保证是连通的。【西安电子科技大学2003一、8(2分)】
问答题有一个无头结点的单链表，结点有数据域data，指针域next，表头指针为h，通过遍历链表，将链表中所有的链接方向逆转。要求逆转后的链表的表头指针h指向原链表的最后一个结点。算法如下所示，请在空格处填入正确的语句。void Inverse(＆h){if(1) ) return；p=h一>next；pr=NULL；while(2) )(h一>next=pr；pr=h；h=p； (3)；}h一>next=pr；}／／inverse【南京理工大学2005二、1(3分)】
问答题一无向图G(V，E)，其中V(G)={1，2，3，4，5，6，7)，E(G)={(1，2)，(1，3)，(2，4)，(2，5)，(3，6)，(3，7)，(6，7)，(5，1))，对该图从顶点3开始进行遍历，去掉遍历中未走过的边，得一生成树G，(V，E")，V(G")=坎G)，E(G")={(1，3)，(3，6)，(7，3)，(1，2)，(1，5)，(2，4)}，则采用的遍历方法是__________。【南京理工大学1997三、6(1分)】
问答题在二叉排序树上成功地找到一个结点，在平均情况下的时间复杂性是：__________，在最坏情况下的时间复杂性是__________。【上海交通大学2004五、1(15／4分)】
问答题设LS是一个线性表，LS=(a
1
，a
2
，…，a
n
)，若采用顺序存储结构，则在等概率的前提下，插入一个元素需要平均移动的元素个数是多少?若元素插在a
i
与a
i+1
之间(0≤i≤n一1)的概率为(n一i)／n
*
(n+1)／2)，则插入一个元素需要平均移动的元素个数又是多少?【西安电子科技大学2001软件二、3(5分)】
问答题对任何一棵二叉树，如果终端结点数为n0，度为2的结点数为n2，则一定有n0=n2+1。