大学数据结构期末考试复习题(六七)
- 格式：doc
- 大小：38.00 KB
- 文档页数：3
数据结构期末复习题六
1设有序表的关键字序列为（（b,c,d,e,f,g,q,r,s,t），则在折半查找关键字b的过程中，
先后进行比较的关键字为：（ ）
A f , c, b B f, d, b C g ,c, b D g , d, b
2画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找
长度。
3已知数据序列为46，50，70，30，20，66，70，85，请按照这个序列构造一棵二叉排序树，
求出查找成功时的平均查找长度，并画出分别删除20，50，70后的二叉排序树。
4已知数据序列46，50，70，30，20，66，70，85，请按照这个序列构造一棵平衡二叉树。
5选取哈希函数H(k)=(3k)%11，用线性探测再散列法处理冲突。试在0-10的散列地址空间
中，对关键字序列(22,41,53,46,30,13,01,67)构造哈希表，并求等概率情况下查找成功与
不成功时的平均查找长度。
数据结构期末复习题七
1、设顺序表va中的数据元素递增有序，试写一算法，将x插入到顺序表的适当位置上，以
保持该表的有序性。
2、已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和
n。试写一算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后
一个结点之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间
完成连接运算。请分析你的算法的时间复杂度。
3、试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,„，an ）
逆置为（an,an-1, „，a1）.
4、已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字
符和其他字符），试编写算法将该线性表分割为三个循环链表，其中每个循环链表表示的线
性表中均只含一类字符。
5、 试编写如下定义的递归算法，并根据算法画出求g(5,2)时栈的变化过程。
nnmgnmg)2,1(
0
),(
6、 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设
头指针），试编写相应的队列初始化、入队列和出队列的算法。
7、 假设称正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，
‘ababab’则不是回文，试写一个算法判别读入的一个以‘@’为结束符的字符序列是
否是“回文”。
8、试写一算法，实现对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。
9、试写一算法，求以L为头指针的含头结点的单链表中第K个结点，K为正整数，若查找
成功，返回该结点的data域的值，并返回1，否则只返回0。
10、 单链表的类型定义如下:
typedef struct node {
DataType data;
struct node *next;
} LinkNode, *LinkList;
试编写一算法,将一个头指针为head且不带头结点的单链表改造为一个含头结点且头指
针仍为head的单向循环链表,并分析算法的时间复杂度。
M=0,n>=0
m>0,n>=0
