专升本数据结构考试题2（还有很多哦，大家进我的账号下载）

9. 设散列表的长度为8，散列函数H(k)=k % 7，用线性探测法解决冲突，则根据一组初始

关键字序列(8，15，16，22，30，32)构造出的散列表的平均查找长度是________。 10. 设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟冒泡排序结束后的

结果为_____________________。

11. 设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟简单选择排序后的

结果为______________________。

12. 设有向图G中的有向边的集合E={<1，2>，<2，3>，<1，4>，<4，5>，<5，3>，<4，6>，

<6，5>}，则该图的一个拓扑序列为_________________________。

13. 下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。 typedef struct node{int data;struct node *lchild;________________;}bitree; void createbitree(bitree *&bt) {

scanf(“%c”,&ch);

if(ch=='#') ___________;else

{ bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch; ________;createbitree(bt->rchild);} }

14. 下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确

的内容。

typedef struct node {int data; struct node *next;} lklist; void lklistcreate(_____________ *&head ) {

for (i=1;i<=n;i++) {

p=(lklist *)malloc(sizeof(lklist));scanf(“%d”,&(p->data));p->next=0; if(i==1)head=q=p;else {q->next=p;____________;} } }

三、算法设计题(22分)

1． 设计在链式存储结构上合并排序的算法。 2． 设计在二叉排序树上查找结点X的算法。

3． 设关键字序列(k1，k2，?，kn-1)是堆，设计算法将关键字序列(k1，k2，?，kn-1，x)调

整为堆。