问答题关键字序列(Q，H C，Y, Q，A，M,S,R，D，E,X)，要按照关键字值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是__________；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是__________。【北京大学1997一、4(4分)】
问答题每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，对称序列是FEBGCHD，则它的后序序列是(1)。设上述二叉树是由某棵树转换而成，则该树的先根次序序列是(2)。【山东工业大学1997二(6分)】
问答题在含有n(n>0)个关键字的小根堆(堆顶元素最小)中，关键字最大的记录可能存储在什么位置上?说明理由。
问答题若5个元素A,B,C,D,E按此先后次序进入一初始为空的堆栈，请写出在所有可能的出栈序列，第一个元素为C、且第二个元素为D的出栈序列。
问答题证明：具有n个顶点和多于n一1条边的无向连通图G一定不是树。【东南大学1993四(10分)】
问答题给定有m个整数的递增有序数组a[1．．m]和有n个整数的递减有序数组b[1..n]，试写出算法：将数组a和b归并为递增有序数组c[1一..m+n]。(要求：算法的时间复杂度为O(m+n)。)【华中理工大学2000八、1(10分)】
问答题若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗?举例说明之。
问答题已知二叉树T，试写出复制该二叉树的算法(t→T)(1)(8分)递归算法(2)(12分)非递归算法【北方交通大学1993七(20分)】
问答题对于数组A
m*n
其元素a
ij
按行优先与按列优先存储时地址之差为__________。【东南大学2005数据结构部分二、3(1分)】
问答题试证明：若借助栈由输入序列1，2，…，n得到输出序列为P
1
，P
2
，…，P
n
(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着P
f
k
i。【上海交通大学1998二(15分)】
问答题顺序检索、二分检索、哈希(散列)检索的时间分别为O(n)、O(log
2
n)、O(1)。既然有了高效的检素方法，为什么低效的方法还不放弃?【北京邮电大学1993一、2(5分)】
问答题已知待排序的序列为(503，87，512，6l，908，170，897，275，653，462)，试完成下列各题。
问答题设后序线索树中结点构造为(Ltag，Lchild，Data，Rchild，Rtag)。其中：Ltag，Rtag值为0时，Lchild、Rchild分别为儿子指针；否则分别为直接前驱、直接后继的线索。请写出在后序线索树上找给定结点p^的直接前驱q的算法。【武汉交通科技大学1966四、1(13分)】
问答题设有上三角矩阵(a
ij
)
n*n
将其上三角中的元素按先行后列的顺序存于数组B(1：m)中，使得B[k]=a
ij
且k=f1(i)+f2(j)+c，请推导出函数f1、f2和常数c，要求f1和f2中不含常数项。【中科院自动化所1999】【山东科技大学2002— 5 (6分)
问答题有向图G的强连通分量是指__________。【北京科技大学1997一、7】
问答题一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域coef，指数域exp和指针域next现对链表求一阶导数，链表的头指针为ha，头结点的exp域为一1。 derivative(ha) {q=ha； pa=ha一>next； while((1) ) {if((2) ){(3) );free(pa); pa=((4) )； ) else{pa一>coef((5) )；pa->exp((6) )；q=((7))；} pa=((8) )； } }【南京理工大学2000三、3(10分)】
问答题设计在无头结点的单链表中删除第i个结点的算法。
问答题当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用__________存储结构。【北方交通大学2001二、4】
问答题对下面的关键字集{30，15，21，40，25，26，36，37)若查找表的装填因子为0．8，采用线性探测再散列方法解决冲突，做：
问答题线性结构包括__________、__________、__________和__________。线性表的存储结构分成__________和__________。【华北计算机系统工程研究所1999一、2(10分)】