数据结构作业题

4/4数据结构作业题答案出错，本宝宝概不负责，应该没错

作业题

一、填空题：

(1)一个有向图G中若有弧、和,则在图G的拓扑序列中，顶点vi,vj和vk的相对位置为_____i,j,k_____。

(2)队列是一种_线性的结构。

(3)在单链表中，指针p所指结点为最后一个结点的条件是p->next==NULL。

(4)二路归并排序的时间复杂度是__nlogn______。

(5)栈是一种_线性的结构。

(6)由____树____转换成二叉树时，其根结点的右子树总是空的。

(7)直接选择排序是不稳定的，其时间复杂性为__n2______。

(8)对无向图，其邻接矩阵是一个关于__对角线______对称的矩阵。

(9)由________转换成二叉树时，其根结点的右子树总是空的。

(10)归并排序要求待排序列由若干个____有序_______的子序列组成。

(11)已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有___12_______个叶子的结点。

二、单项选择题：

(1)设有一个无向图G=（V，E）和G’=（V’，E’）如果G’为G的生成树，则下面不正确的说法是（B）。

A.G’为G的子图；

B.G’为G的边通分量；

C.G’为G的极小连通子图且V’=V；

D.G’为G的一个无环子图。

(2)单链表的一个存储结点包含（D）。

A.数据域或指针域；

B.指针域或链域；

C.指针域和链域；

D.数据域和链域。

(3)二分查找要求被查找的表是（C）。

A.键值有序的链接表；

B.链接表但键值不一定有序；

C.键值有序的顺序表；

D.顺序表但键值不一定有序。

(4)设指针P指向双链表的某一结点，则双链表结构的对称性可用（C）式来刻画。

A.p->prior->next->==p->next->next；

B.p->prior->prior->==p->next->prior；

C.p->prior->next->==p->next->prior；

D.p->next->next==p->prior->prior。

(5)顺序查找法适合于（D）存储结构的查找表。

A.压缩；

B.散列；

C.索引；

D.顺序或链式。

(6)在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是（B）。

A.real和rear->next->next；

B.rear->next和rear；

C.rear->next->next和rear；

D.rear和rear->next。

（7）堆是一个键值序列{k1,k2,…,kn},对i=1,2,…,|_n/2_|,满足(C)。

A.ki≤k2i≤k2i+1；

B.kinext!=NULL)

{_____p=p->next___________;@

j++;

}

return(j);/*回传表长*/

2.以下为单链表按序号查找的运算，分析算法，请在____处填上正确的语句。

pointerfind_lklist(lklisthead,inti)

{p=head;j=0;

while(p->next!=null&&jnext;j++;}

if(i==j)return(p);

elsereturn(NULL);

}

}

3.以下为单链表的插入运算，分析算法，请在____处填上正确的语句。

voidinsert_lklist(lklisthead,datatypex,inti)

/*在表head的第i个位置上插入一个以x为值的新结点*/

{p=find_lklist(head,i-1);

if(p==NULL)error(“不存在第i个位置”)；

else{s=mailloc(size);s->data=x;

s->next=p->next；@

p->next=s;

}

}

4.程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去，请完成程序。

SeqStackS1,S2,tmp;

DataTypex;

...//假设栈tmp和S2已做过初始化

while(!StackEmpty(

Push(@

}

while(!StackEmpty(

Push(

Push(

}

5.以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。

Voidcountleaf(bitreptrt,int*count)/*根指针为t，假定叶子数count的初值为0*/

{if(t!=NULL)

{if((t->lchild==NULL)

countleaf(t->lchild,

countleaf(t->rchild,inti;

InitStack(

while(!StackEmpty(S))

if(i=Pop(@

while(!StackEmpty(Push(S,i);

}

}

7.以下是直接选择排序的算法。请分析算法，并在横线上填充适当的语句。

voidselect(listr,intn)

{for(i=1;ir[j])k=j;

if(_k!=I)swap(r[k],r[i]）;/*函数swap(r[k],r[i]）交换r[k]和r[i]的位置*/

}

8.以下为冒泡排序的算法。请分析算法，并在________上填充适当的语句。

voidbulbblesort(intn,listr)/*flag为特征位，定义为布尔型*/

{for(i=1;i

4.设某密码电文由8个字母组成，每个字母在电文中的出现频率分别是22，15，2，5，17，11，9，19，试为这8个字母设计相应的哈夫曼编码。

19=00

22=01

2=11000

15=101

11=100

5=11001

9=1101

17=111

5.请用类C语言编写从单链表中删除表头元素的算