问答题试用关键字序列(33，10，45，20，53，43，31，15，65，40)，构造哈希(Hash)表，设哈希函数为：H(key)=key％11，其中key为关键字，％为求余运算符；用开放定址法处理冲突，用线性探测再散列法查找空位，用长度为14的数据元素组A[14]表示哈希表。(1)画出该哈希表的存储结构图；(2)假定每个元素的查找概率相等，计算查找成功时的ASL；(3)计算查找不成功时的ASL。【华中科技大学2007四、25(10分)】
问答题两个整数序列A=a
1
,a
2
，a
3
，…，a
n
和B=b
1
，b
2
,b
3
，…，b
n
已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序列。【东北大学1999年】
问答题设有一个带表头结点的链表，结点的结构为(data，link，sort)，其中data为整型值域，link和sort都是指针域。已知链表所有结点都已通过link域指针链接起来，构成单链表，且所有结点数据的值互不相同。试编写一个算法，利用sort域把所有结点按照数据的值从小到大的顺序链接起来。
问答题如何衡量Hash函数的优劣?简要叙述Hash表技术中的冲突概念，并指出三种解决冲突的方法。【南京航空航天大学1996九、2(6分)】
问答题给定8个权值集合(2，5，3，10，4，7，9，18)，画出含有8个叶子结点的最佳三叉归并树，并计算出wpl为多少?【东北大学1996一、2(5分)】
问答题编写一个过程，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。【中科院软件所1996】
问答题设有广义表A=(c，(a，b))，(x，(a，b)，y))，则运算head(taead(tail(A)))的结果是__________。【东南大学2005数据结构部分二、4(1分)】
问答题模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m，模式的长度为n，则在主串中寻找模式的KMP算法的时间复杂性是多少?如果某一模式’P=-"abcaacabaca"，请给出它的NEXT。函数值及NEXT函数的修正值NEXTVAL之值。【上海交通大学2000一(5分)】
问答题编写程序段，利用中序全线索树求其中任意结点p^的前序后继结点，结果仍用p指出。要求先描述结构和算法思路。设线索树不带头结点，其中序序列第一结点的左标志和最后结点的右标志皆为0(非线索)，对应指针皆为空。【北京工业大学2000七(10分)】【哈尔滨工业大学2004五、2(8分)】【上海交通大学2003三(15分)】
问答题已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成?请简述原因。【西北大学2001三、6】
问答题对于后序线索二叉树，怎样查找任意结点的直接后继；对于中序线索二叉树，怎样查找任意结点的直接前驱?【西北工业大学1998一、4(4分)】
问答题如果给出了一个二叉树结点的前序序列和对称序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。如果给出了一个二叉树结点的前序序列和后序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。【北京大学1998二、2(5分)】
问答题设二叉树用二指针结构存储(可以是动态存储结构)，元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶子结点。【华南理工大学20032．3(2)(23／2分)】
问答题下图是一个3阶B树。分别画出在插入65、15、40、30后B树的变化。
问答题已知二叉树的先序遍历序列为ABCELMNDFGHK，中序遍历序列为(；BLM-NEAFDHKG，要求： (1)画出该二叉树； (2)画出与该二二叉树相对应的森林。
问答题二叉树的动态二叉链表结构中的每个结点有三个字段：dam，lchild，rchild。其中指针lchild和rchild的类型为bike。静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：data，lchild，rchild。所不同的是，lchild和rdhild为integer型，分别用于存储左右孩子的下标，如果没有左右孩子，则相应的值为0。例如，下面左图所示的二又树的静态二叉链表如右图所示。编写算法由二叉树的动态二叉链表构造出相应的静态二又链表a[1..n]，并写出其调用形式和有关的类型描述。其中n为一个确定的整数。【合肥工业大学2000五、3(8分)】
问答题阅读下列程序，指出其功能，并写出空格处应填上的语句。 void testl(element item，list_pointer ht[]) {int hash—value=hash(item．key)； list_pointer ptr l trail=NULL。lead=ht[hash value]； for(；lead；trail=lead，lead=lead->1ink) (if{!strcmp(1ead->item．key，item．key)) (fprintf(stderr，“The key is in the table＼n”)；exit(1)；) } ptr=(1ist_pointer)malloc(sizeof(1ist))； if(IS—FULL(ptr)) (fprintf(stderr，“The memoty is full＼n”)；exit(1)；) ptr一>item=item；ptr一>1ink=NULL； if(trail) (1) ；else (2) ； }【浙江大学2002六(10分)】
问答题
问答题假设一个有向图G已经以十字链表形式存储在内存中，试写一个判断该有向图中是否有环路(回路)的算法。【中科院研究生院2005五(15分)】【东南大学2005数据结构部分五(15分)】
问答题编写程序，对单链表结构的线性表进行排序，并详细说明排序算法，分析时间复杂度。【南京航空航天大学2003四(10分)】