十套数据结构题简答,算法题目提取

六、编写算法（共8分）

统计出单链表HL中结点的值等于给定值X的结点数。 int CountX(LNode* HL,ElemType x) 二

三、应用题(36分)

1． 设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择

排序和第4趟直接插入排序后的结果。 2． 设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A

的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。 3． 设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用

二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。

4． 设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求

用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。 5． 设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。

6． 设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给

出构造过程。

四、算法设计题(16分)

1． 设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间

复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。

2． 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链

式存储结构表示。 三

三、计算题(每题10分，共30分)

1.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。

2．已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试： （1）计算出每一个元素的散列地址并在下图中填写出散列表：

` 0 1 2 3 4 5 6 （2）求出在查找每一个元素概率相等情况下的平均查找长度。

3．已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。 四、算法设计题(每题15分，共30分)

1． 设计在单链表中删除值相同的多余结点的算法。 2． 设计一个求结点x在二叉树中的双亲结点算法。