![](https://csdnimg.cn/release/download_crawler_static/87298527/bg5.jpg)
数据结构试卷(四)
1. 设一组初始记录关键字序列为(20,18,22,16,30,19),则以 20 为中轴的一趟快速
排序结果为______________________________。
2. 设一组初始记录关键字序列为(20,18,22,16,30,19),则根据这些初始关键字序
列建成的初始堆为________________________。
3. 设某无向图 G 中有 n 个顶点,用邻接矩阵 A 作为该图的存储结构,则顶点 i 和顶点 j
互为邻接点的条件是______________________。
4. 设无向图对应的邻接矩阵为 A,则 A 中第 i 上非 0 元素的个数_________第 i 列上非 0
元素的个数(填等于,大于或小于)。
5. 设前序遍历某二叉树的序列为 ABCD,中序遍历该二叉树的序列为 BADC,则后序遍
历该二叉树的序列为_____________。
6. 设散列函数 H(k)=k mod p,解决冲突的方法为链地址法。要求在下列算法划线处填上
正确的语句完成在散列表 hashtalbe 中查找关键字值等于 k 的结点,成功时返回指向关
键字的指针,不成功时返回标志 0。
typedef struct node {int key; struct node *next;} lklist;
void createlkhash(lklist *hashtable[ ])
{
int i,k; lklist *s;
for(i=0;i<m;i++)_____________________;
for(i=0;i<n;i++)
{
s=(lklist *)malloc(sizeof(lklist)); s->key=a[i];
k=a[i] % p; s->next=hashtable[k];_______________________;
}
}
三、计算题(每题 10 分,共 30 分)
1、画出广义表 LS=(( ) , (e) , (a , (b , c , d )))的头尾链表存储结构。
2、下图所示的森林:
(1) 求树(a)的先根序列和后根序列;
(2) 求森林先序序列和中序序列;
(3)将此森林转换为相应的二叉树;
3、设散列表的地址范围是[ 0..9 ],散列函数为 H(key)= (key
2
+2)MOD 9,并采用链
表处理冲突,请画出元素 7、4、5、3、6、2、8、9 依次插入散列表的存储结构。
四、算法设计题(每题 10 分,共 30 分)
1. 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符),要求利用原单链
表中结点空间设计出三个单链表的算法,使每个单链表只包含同类字符。
2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。
3. 在链式存储结构上建立一棵二叉排序树。