《数据结构与算法》期末练习题2

二填空题

1、在单链表L中，指针p所指结点有后继结点的条件是：

p->next!=null

2、n(n大于1)个结点的各棵树中，其深度最小的那棵树的深度是它共有一个叶子结点和一个非叶子结

点，其中深度最大的那棵树的深度是_，它共有一个叶子结点和一个非叶子结点。

(1)2(2)n-1(3)1(4)n(5)1(6)n-1

3、深度为9的完全二叉树最多有个结点

4、二叉树由—，—，—三个基本单元组成。

5、先根遍历树林正好等同于按—遍历对应的二叉树.

设只含根结点的二叉树的高度为0,则高度为k的二叉树的最大结点数为，最小结点数为。

7、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为

8、设y指向二叉线索树的一叶子，x指向一待插入结点，现x作为y的左孩子插入，树中标志域为Itag和rtag,

并规定标志为1是线索，则下面的一段算法将x插入并修改相应的线索，试补充完整：(Ichidrchild分别代表左，

右孩子)

xA.ltag:=___;xA.lchild:=___;yA.ltag:=___;

yA.lchild:=___;xA.rtag:=___;xA.rchild:=___;

IF(xA.lchild<>NIL)AND(xAlchildA.rtag=l)THENxA.lchildA.rchild:=

(1)1(2)yA〔child(3)0(4)x(5)1(6)y(7)x(本题按中序线索化)

9、有N个顶点的有向图，至少需要量______条弧才能保证是连通的。

10、在顺序表(8,11,15,19,25,26,30,33,42,48,50)中,用二分(折半)法查找关键码值11,需做的关键码比较次

数为

12、利用树的孩子兄弟表示法存储，可以将一棵树转换为。

13、n个结点的完全有向图含有边的数目_(7)

14、当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的。

15、假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX,

贝I」由“a*b+c/d”得至“ab*cd/+”的操作序列为,

16、在一棵度为3的树中，度为2的结点个数是1,度为0的结点个数是6,则度为3的结点个数是。

17、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个

数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数NO。N2、NL、NR、NO都是

全局量，且在调用count(t)之前都置为0.

typedefstructnode

{intdata;structnode*lchild,*rchild;}node;

intN2,NL,NR,N0;

voidcount(node*t)

{if(t->lchild!=NULL)if(l)―N2++;elseNL++;

elseif⑵___NR++;else⑶_;

if(t->lchild!=NULL)(4);if(t->rchild!=NULL)(5);

}/*callform:if(t!=NULL)count(t);*/

18、利用筛选法将关键字序列(37,66,48,29,31,75)建成的大根堆为()。

19、对长度为20的有序表进行二分查找的判定树的高度为。

20、阅读下列程序说明和程序，填充程序中的

【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示(编者略)。

本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树

的算法为：

(1)把根结点放入堆栈。

(2)当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。

(3)重复(2)直到堆栈为空时为止。

typedefstructnode"tree;

structnode{intdata;treeIchild,rchild;}

exchange(treet)

{treer,p;treestack[500];inttp=O;

(l)_stack[tp]=t

while(tp>=0)

{(2)___p=stack[tp-]

if(⑶—P—)

{r=p->lchild;p->lchild=p->rchild;p->rchild=r

stack[(4)—++tp]=p->lchild;stack[++tp]=p->rchild;

)

))

21、排序(sorting)有哪几种方法,,,，。

22、下面程序段的时间复杂度为o(用O估计)

FORi:=lTOnDO

FORj:=iTOnDO

s=s+j；

23、非线性结构包括和o

24、判断带头结点的双向循环链表L是否对称相等的算法如下所示，请在划线处填上正确的语句

FUNCTIONequal(l:pointer):boolean;

VARp,q:pointer;result:Boolean;

BEGINresult=true;p:=lA.link;q:=lA.pre;

WHILE(poq)AND((1))DO

IFpA.data=qA.dataTHENBEGIN⑵—;⑶;END；

ELSEresult=false;

retum(result);

END;

25、用一维数组表示顺序存储的循环队列，设队头和队尾指针分别是front

和rear,且队头指针所指的单元闲置，则队满的条件是，队空的条件是

26、下面表达式树所对应的表达式的前缀表达式是，后缀表达式是

27、已知中序遍历bt所指二叉树算法如下，s为存储二叉树结点指针的工作栈，请在划线处填入一条所缺语句。

PROCinorder(bt:bitreptr);

inistack(s);(1);

WHILENOTempty(s)DO

[WHILEgettop(s)<>NILDOpush(s,gettop(s)t.Ichild);(2);

IFNOTempty(s)THEN[visit(gettop(s)A);p:=pop(s);⑶]]

ENDP;{inorder}

28.对有向图进行拓扑排序，若拓扑排序不成功，则说明该图_________________o下面有向图的一个拓扑有序

序列是O

29、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前

序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。

#defineMAX100

typedefstructNode

{charinfo;structNode*llink,*rlink;}TNODE;

charpred[MAX],inod[MAX];

main(intargc,int**argv)

{TNODE*root;

if(argc<3)exit0;

strcpy(pred,argvf1]);strcpy(inod,argv[2]);

root=restore(pred,inod,strlen(pred));

postorder(root);

)

TNODE*restore(char*ppos,char*ipos,intn)

{TNODE*ptr；char*rpos;intk;

if(n<=0)returnNULL;

ptr->info=(l);

for((2);rpos<ipos+n;rpos++)if(*rpos==*ppos)break;

k=(3);

ptr->llink=restore(ppos+1,(4),k);

ptr->rlink=restore((5)+k,rpos+l,n-l-k);

returnptr;

)

postorder(TNODE*ptr)

{if(ptr=NULL)return;

postorder(ptr->llink);postorder(ptr->rlink);printf(u%cJ,,ptr->info);

)

三简答题

1、名词解释：(1)抽象数据类型；抽象数据类型(AbstractDataType简称ADT)是指一个数学模型以及定义在

此数学模型上的一组操作。抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。抽

象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。

(2)算法的时间复杂性；一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

(3)散列法(hashing)；散列法(Hashing)或哈希法是一种将字符组成的字符串转换为固定长度(一般是更短长

度)的数值或索引值的方法，称为散列法，也叫哈希法。

(4)索引文件。由索引表和主文件两部分构成

2、堆与二元查找树的区别？

堆结点小于或等于(大于或等于)左右子树的值，而二元查找树必需左边的值小于右边的

3、(判断题)

非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子.Yxm:正确

深度为k具有n个结点的完全二叉树，其编号最小的结点序号为2k-2+1。Yxm:错误

在中序线索二叉树中，每一非空的线索均指向其祖先结点。Yxm:正确

当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。

Yxm：错误

用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的

边数无关。Yxm:正确

广度遍历生成树描述了从起点到各顶点的最短路径。Yxm：错误

连通图上各边权值均不相同，则该图的最小生成树是唯一的。Yxm:正确

一个有向图的邻接表和逆邻接表中结点的个数可能不等。Yxm：错误

4、如下所示的是一个带权无向图，带框的数字表示相应边的权，不带框的数字表示顶点号。用prime算法求最

小生成树时，如果已确定的边为(5,4),则，下一条边应在哪几条边中选取？选取哪一条？

yxh：(4,6)

5、如何衡量hash函数的优劣？简要叙述hash表技术中的冲突概念，并指出三种解决冲突的方法。

评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是

否简单高效。由于哈希函数是压缩映像，冲突难以避免。

散列表存储中解决碰撞的基本方法：

①开放定址法形成地址序列的公式是：Hi=(H(key)+di)%m,其中m是表长，di是增量。根据di

取法不同，又分为三种：

a.di=1,2,…，m-1称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决

碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。

b.di=12,-12,22,-22,…，k2(kWm/2)称为二次探测再散列，它减少了聚集，但不容易探测到全部表

空间，只有当表长为形如4j+3(j为整数)的素数时才有可能。

c.di=伪随机数序列，称为随机探测再散列。

②再散列法Hi=RHi(key)i=l,2,k,是不同的散列函数，即在同义词产生碰撞时，用另一散列

函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。

③链地址法将关键字为同义词的记录存储在同一链表中，散列表地址区间用表示，分量初始

值为空指针。凡散列地址为i(OWiWm-l)的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个

数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列

表称闭散列表，含义是元素个数受表长限制。

④建立公共溢出区设为基本表，凡关键字为同义词的记录，都填入溢出区

O[0..m-l]o

6、有一棵哈夫曼树共有5个叶子结点其权值分别为0.1,0.25,0.08,0.21,0.9,试画出该哈夫曼树。假设该叶子分别表

示a,b,c,d,e,分别给出五个叶子对应的哈夫曼编码。

yxh：a(H10),b(10),c(llll),d(110),e(0)(画出的哈夫曼树不唯一，其编码亦不同)

7、采用哈希函数H(k)=3*kmod13并用线性探测开放地址法处理冲突，在数列地址空间[0..12]中对关键字

序列22,列,53,46,30,131,67,51

(1)构造哈希表(画示意图)；(2)装填因子；等概率下(3)成功的和(4)不成功的平均查找长度。

(1)

散列地址0123456789101112

关键字13225314167465130

比较次数111212111

(2)装填因子=9/13=0.7(3)ASLsucc=ll/9(4)ASLunsucc=29/13

8、已知一个图如下，试画出其逆邻接链表。

9、若一个栈的输入序列是1,2,3...,n,其输出序列为pl,p2,....pn,

若pl=n,则pi为多少？

yxh：i=n-i+l

10、非空的二叉树的中根遍历序列中，根的右子树的所有结点都在根结点的后边，这说法对吗？

11、

11,已知二叉树的中根遍历序列为abc,试画出该二叉树的所有可能的形态。(5种)

12、已知一个图如图所示，如从顶点a出发进行按深度优先遍历，可否得到序列acebdf?为什么？若按广度优

先遍历，能否得到序列abedfc?为什么？

©—

13、栈的存储方式有哪两种？(顺序存储和链式存储)

14、对于单链表、单循环链表和双向链表，如果仅仅知道一个指向链表中某结点的指针p,能否将p所指结点的

数据元素与其确实存在的直接前驱交换?请对每二种链表作出判断,若可以，写出程序段；否则说明理由。其中:

单链表和单循环链表的结点结构为|date|next|

双向链表的结点结构为priordatenext

(对于单链表要知道头结点就可以，单循环链表和双向链表可以)

15、假设通信电文使用的字符集为{a,b,c,d,e,f,g},字符的哈夫曼编码依次为：0110,10,110,111,00,0111和

010o

(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；

(2)若这些字符在电文中出现的频度分别为：3,35,13,15,20,5和9,求该哈夫曼树的带权路径长度。

16、试为下列关键字设计哈希表，要求所设计的表在查找成功时的平均查找长度不超过2.0。并请验证你造的哈

希表的实际平均查找长度是否满足要求。

(CHA,CAI,LAN,WEN,LONG,ZHAO,WU,LIU,CHEN,LI,WANG,CAO,YUN,CHANG,YANG)

设用线性探测再散列解决冲突，根据公式Snl^(1+1/(1-a))/2。可求出负载因子为a=0.67。再根据数据

个数和装载因子，可求出表长m=15/0.67,取m=23。设哈希函数H(key)=(关键字首尾字母在字母表中序号

之和)MOD23o

从上表求出查找成功时的平均查找长度为ASLsucc=19/15<2.0,满足要求。

17、用链表表示的数据的简单选择排序，结点的域为数据域data,指针域next；链表首指针为head,链表无

头结点。

selectsort(head)

p=head;

while(p(l))

{q=P；r=(2)

while((3))

{if((4))q=r;

『(5)；

}

tmp=q->data;q->data=p->data;p->data=tmp;p=(6);

)

题中p指向无序区第一个记录，q指向最小值结点，一趟排序结束，p和q所指结点值交换，同时向后移p指针。

(l)!=null(2)p->next(3)r!=null(4)r->data<q->data(5)r->next(6)p->next

18、设某二叉树的前序遍历序列为：ABCDEFGHI,中序遍历序列为：BCAEDGHFL(1)试画出该二叉树；(2)

画出该二叉树后序线索化图。(3)试画出该二叉树对应的森林。

19、一棵二叉排序树结构如下,各结点的值从小到大依次为1-9,请标出各结点的值。

20、下面的排序算法的思想是：第一趟比较将最小的元素放在r[l]中，最大的元素放在r[n]中，第二趟比较将次

小的放在r[2]中，将次大的放在r[n-l]中，…，依次下去，直到待排序列为递增序。(注：<->)代表两个变量的数

据交换)。

voidsort(SqList&r,intn){

i=l；

while((l)—){

min=max=l;

for(j=i+l;(2);++j)

{if((3))min=j;elseif(r[j].key>rfmax].key)max=j;}

if((4))r[min]<-—>r[j];

if(max!=n-i+l){if((5)___)r[min]<---->r[n-i+l];else((6)_);}

i++；

}

}//sort

(l)i<n-i+l(2)j<=n-i+l(3)r[j].key<r[min].key(4)min!=i(5)max==i(6)r[max]<—>r[n-i+1]

(2)

堆是一种有用的数据结构.堆排序是一种_(1)_排序，堆实质上是一棵_(2)一结点的层次序列。对含有N个元素的

序列进行排序时，堆排序的时间复杂度是一(3)一，所需的附加存储结点是一(4)_。关键码序列05,23,16,68,94,

72,71,73是否满足堆的性质一(5)一。

(1)选择(2)完全二叉树(3)O(nk)gn底数为2)(4)0(1)(5)满足堆的性质

22、在堆排序、快速排序和合并排序中：

(1).若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？

(2).若只从排序结果的稳定性考虑，则应选取哪种排序方法？

(3).若只从平均情况下排序最快考虑，则应选取哪种排序方法？

(4).若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？

(1)堆排序，快速排序，归并排序(2)归并排序(3)快速排序(4)堆排序

算法模拟

设待排序的记录共7个，排序码分别为8,3,2,5,9,1,6。

(1)用直接插入排序。试以排序码序列的变化描述形式说明排序全过程(动态过程)要求按递减顺序排序。

(2)用直接选择排序。试以排序码序列的变化描述形式说明排序全过程(动态过程)要求按递减顺序排序。

(3)直接插入排序算法和直接选择排序算法的稳定性如何？

(1)直接插入排序

第一趟(3)[8,3],2,5,9」,6第二趟(2)[8,3,2],5,9,1,6第三趟(5)[8,5,3,2],9,1,6

第四趟(9)[9,8,5,3,2],1,6第五趟(1)19,8,5,3,2,1J,6第六趟(6)19,8,6,5,3,2,1J

(2)直接选择排序(第六趟后仅剩一个元素，是最小的，直接选择排序结束)

第一趟(9)[9],3,2,5,8,1,6第二趟(8)[9,8],2,5,3,1,6第三趟(6)[9,8,6],5,3,1,2

第四趟(5)[9,8,6,5],3』,2第五趟(3)[9,8,6,5,3],1,2第六趟(2)[9,8,6,5,3,2]』

(3)直接插入排序是稳定排序，直接选择排序是不稳定排序。

四算法阅读

1、voidAE(Stack&S){

InitStack(S);

Push(S,3)；

Push(S,4)；

intx=Pop(S)+2*Pop(S);

Push(S,x);

inti,a[5]={1,5,8,12,15);

for(i=0;i<5;i++)Push(S,2*a[i]);

while(!StackEmpty(S))print(Pop(S));

}

该算法被调用后得到的输出结果为：

2、voidABC(BTNode*BT,int&cl,int&c2){

if(BT!=NULL)

(

ABC(BT->left,cl,c2);

cl++;

if(BT->left==NULL&&BT->right==NULL)c2++;

ABC(BT->right,cl,c2);

}//if

)

该函数执行的功能是什么？

3、在下面的每个程序段中，假定线性表La的类型为List,e的类型为ElemType,元素类型ElemType为int,并假

定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表Lao

(1)InitList(La);

Inta[]={100,26,57,34,79);

For(i=0;i<5;i++)

ListInsert(La,1,a[i]);

(2)ListDelete(La,l,e);

ListInsert(La,ListLength(La)+l,e);

(3)ClearList(La);

For(i=0;i<5;i++)

ListInsert(La,i+l,a[i]);

4、intPrime(intn)

(

inti=l;

intx=(int)sqrt(n);

while(++i<=x)

if(n%i==0)break;

if(i>x)return1;

elsereturn0;

)

(1)指出该算法的功能；

(2)该算法的时间复杂度是多少？

5.写出下述算法A的功能：

其中BiTree定义如下：

TypedefstructBiTNode{

TElemTypedata;

structBiTNode*LChild,*RChild;

[BiTNode,*BiTree;

StatusA(BiTreeT)

(

QueueQ;

InitQueue(Q);

ENQueue(Q,T);

While(notQueueEmpty(Q))

{DeQueue(Q,e);

If(e==NULL)break;

Else

{Print(e.data);

ENQueue(Q,e.LChild);

ENQueue(Q.e.RChild);

)

6.阅读下列函数algo,并回答问题：

⑴假设队列q中的元素为(2,4,578),其中“2”为队头元素。写出执行函数调用algo(&q)后的队列q；

⑵简述算法algo的功能。

voidalgo(Queue*Q)

(

StackS;

InitStack(&S);

while(!QueueEmpty(Q))

Push(&S,DeQueue(Q));

while(!StackEmpty(&S))

EnQueue(Q,Pop(&S));

)

yxh：(l)q中的元素为(8,7,5,4,2);(2)把队列q中的元素倒序。

五算法填空

1、下面是在带表头结点的循环链表表示的队列上，进行出队操作，并将出队元素的值保留在x中的函数，其中

rear是指向队尾结点的指针。请在横线空白处填上适当的语句。

typedefstructnode

{intdata;

structnode*nexl;

}Iklist;

voiddel(Iklistrear,int&x);

{Iklistp,q;

q=rear->next;//q为头结点

if(_q->next==q)//rear->next==rear

print""itisempty!\n^^);

else{

p=q->next;

x=p->data;

___q->next=p->next;//删除首元结点

if(_q->next==q)rear=q;〃空，或rear=p

free(p);

)；

)；

2、堆分配存储方式下，串连接函数。

typedefstruct

(

char*ch；

intlen；

}HString；

HString*s,t;

StatusStrCat(s,t)/*将串t连接在串s的后面*/

(

inii;

char*temp;

if(temp==NULL)return(O);

for(i=0;;i++)

temp[i]=s->ch[i];

for(;i<s->len+t.len;i++)

tempLi]=t.chEi-s->len];

s->len+=t.len;

frs->ch=temp;

retum(l);

)

3、向单链表的末尾添加一个元素的算法。

LNode是一个包含(data,Next)的结构体

VoidInsertRear(LNode*&HL,constElemType&item)

(

LNode*newptr;

newptr=newLNode;

If()

(

cerr«uMemoryallocationfailure!u«endl;

exit(l);

)

_________________________=item;

newptr->next=NULL;

if(HL==NULL)

HL=;

else{

LNode*P=HL;

While(P->next!=NULL)

p->next=newptr;

})

4、L为一个带头结点的循环链表。函数130的功能是删除L中数据域data的值大于c的所有结点，并由这些结

点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一

个完整的算法。

LinkListf30(LinkListL,intc)

(

LinkListLc,p,pre;

pre=L;

p=(1);p=L->next

Lc=(LinkList)malloc(sizeof(ListNode));

Lc->next=Lc;

while(p!=L)

if(p->data>c)

(

pre->next=p->next;

(2);p->next=Lc->next

Lc->next=p;

p=pre->next;

)

else

(

pre=p;

(3);p=p->next

)

returnLc;

5、己知图的邻接链表的顶点表结点结构为vertexfirstedge

边表结点EdgeNode的结构为adjvexnext

下列算法计算有向图G中顶点vi的入度。请在空缺处填入合适的内容，使其成为一个完整的算法。

intFindDegree(ALGraph*Ginti)//ALGraph为图的邻接表类型

(

intdgree,j;

EdgeNode*p;

degree=(1);0

for(j=0;j<G->n;j++)

p=G->adjlist[j].firstedge;

while(⑵)p

if((3))p->adjvex==i

(

degree++;

break;

}

p=p->next;

)

)

returndegree;

)

六简单应用题

1、已知一个非空二叉树，其按中根和后根遍历的结果分别为：

中根：CGBAHEDJFI

后根：GBCHEJIFDA

试将这样二叉树构造出来;若已知先根和后根的遍历结果，能否构造这棵二叉树，为什么？

(基本方法：先由后根序列确定根结点，再到中序序列中分割该二叉树)

2、对于下图，画出按Kruskal(克鲁斯卡尔)算法和Prim(普里姆)算法构造最小生成树的过程。

18

3、画出由下面的二叉树转换成的森林。

©®Q

6、考虑右图：

(1)从顶点A出发，求它的深度优先生成树(4分)

(2)从顶点E出发，求它的广度优先生成树(4分)

(3)根据普利姆(Prim)算法，求它的最小生成树(请画出过程)

(设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排21工：歹U)(6分)

答案如下:

(l)ABGFDEC(2)EACFBDG

(3)

£

(?)-GU/T)3

B

七编写算法题

1、设计函数，求一个单链表中值为x的结点个数。并将结果放在头结点的data域中。

voidcountl(lklisthead,intx)

2、假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。(注:已知

树中结点数)

由于以双亲表示法作树的存储结构，找结点的双亲容易。因此我们可求出每一结点的层次，取其最大层次就是树

有深度。对每一结点，找其双亲，双亲的双亲，直至(根)结点双亲为0为止。

intDepth(Ptreet)〃求以双亲表示法为存储结构的树的深度，Ptree的定义参看教材

{intmaxdepth=O;

for(i=l;i<=t.n;i++)

{temp=0;f=i;

while(f>0){temp++;f=t.nodes[f].parent;}//深度加1,并取新的双亲

if(temp>maxdepth)maxdepth=temp;〃最大深度更新

)

retum(maxdepth);//M回树的深度

}//结束Depth

3、设计建立有向图正邻接矩阵的函数(数据输入格式自定)。

Typedefstruct

{intdata[maxsize][maxsize];

intdem,e;

Jsqgraph;

sqgraphcrt(sqgraphg)

{scanf(n,e);g.dem=n;

for(i=l;i<=n;i++)

for(j=1；j<=n;j++)g.data[i][j]=0;

for(i=l;i<=e;i++)

{scanf(beg,end);

g.data[beg][end]=l;

returng;

)

4、设计函数，将不带表头结点的单链表清除。

Iklistclear(Iklisthead)

{while(head)

{p=head;

head=head->next;

free(p);

)

returnhead;

)

5、设计递归函数，求一棵非空的二叉树的深度。

intdepth(bitreptrroot)

{if(!root)return0;

else{dl=depth(root->lc);

dr=depth(root->rc);

returnl+(dl>dr?dl:dr);

)

)

6、设线性表A=(al,a2,a3,…,an)以带头结点的单链表作为存储结构。编写一个函数，删去A中序号为奇数的结点。

7、试编写一个算法，能由大到小遍历一棵二叉树。

voidShowTree(TreeNode*current)

(

if(current==NULL)

(

return;

)

ShowTree(current->right);

cout«endl«current->data;

ShowTree(current->left);}

8、对于二叉树的链接实现，完成非递归的中序遍历过程。

voidInOrder(BiTreebt)

{BiTrees[],p=bt;〃s是元素为二叉树结点指针的栈，容量足够大

inttop=0;

while(p||top>0)

{while(p){s[++topj=p;bt=p->lchild;}〃中序遍历左子树

if(top>0){p=s[top-];printf(p->data);p=p->rchild;}〃退栈，访问，转右子树

})

9、利用直接插入排序的方法对一组记录按关键字从小到大的顺序排序。

10、给出一棵表示表达式的二叉树，其中运算符和运算对象都用一个字符表示，求该表达式的值。设二叉树用二

叉链表表示，表达式中仅包含二元运算，函数operated,b,op)可求任何一种二元运算的值，其中参数叩表示运

算符，a和b分别表示左右两个运算对象。算法中允许直接引用函数operate(函数operate不必定义)，如果需要

还允许引用栈和队列的基本操作。

11编写算法，将一单链表逆转。要求逆转在原链表上进行，不允许重新构造一个链表(可以申明临时变量、指

针)。

该链表带头节点、头节点和数据节点的结构定义如下

typedefstructLNode

(

ElemTypedata;

StructLNode*next;

}List,LNode;

函数定义：voidinvert(List&L)

12、编写算法计算给定二叉树中叶结点的个数。

其中树节点定义如下

typedefstructBiTNode{

DataTypedata;

StructBiTNode*LChild,*RChild;

[BiTNode,*BiTree;

函数定义：CountLeaf(BiTreeT,int&LeatNum)

voidCountLeaf(BiTreeT,int&LeafNum)

(

if(T)

(

if(!T->lchild&&!T->rchild)

LeafNum++;

else

(

CountLeaf(T->lchild,LeafNum);

CountLeaf(T->rchild,LeafNum);

}}}

13、写出二叉树前根遍历的递归算法

已知二叉树结点定义为：

structnode{

elemtpdata;

structnode*lc,*rc;

)；

Typedefstructnode*bitreptr(指向根)，丸pointer(指向一般结点);

voidpreorder(bitreptrP)//P指向树根节点

voidpreorder(bitreptrP)

(

If(P!=0)

(

printf(P->data);

preorder(P->lc);

preorder(P->rc);

})

14、在邻接矩阵存储结构上实现图的基本操作：

InsertVex(Gv)//插入顶点

StatusInsert_Vex(MGraph&G,charv)〃在邻接矩阵表示的图G上插入顶点v

(

if(G.vexnum+1)>MAX_VERTEX_NUMreturnINFEASIBLE;

Gvexs[++G.vexnum]=v;

returnOK;

}//Insert_Vex

15、已知某哈希表的装载因子小于1,哈希函数H(key)为关键字(标识符)的第一个字母