数据结构模拟试题（答案）(1).docx

第PAGE5页共NUMPAGES5页

第一套（答案）

一、选择题

题号

1

2

3

4

5

6

7

8

9

10

答案

D

C

B

C

B

D

A

D

C

C

二、填空题（每空2分，共20分）

1、log2n

2、指针（地址）

3、n（n+1）/2

4、n2+1

5、n+1

6、Vi，Vj，Vk

7、把邻接矩阵中第i行所有的1改为0

8、小

9、2

10、（48，44，52，63，80，91）

HF

H

F

H

G

D

∧

1、功能：把二叉树叶子结点链成一个单链表。

2、ABCDEFGHIJKLM

MLKJIHGFEDCBA

3、a：00，b：100，c：01，d：11，e：101

4、（1）邻接矩阵中1的个数之和除2；

（2）邻接矩阵中对应第i行和第j列是否为1；

（3）对应的第i行或第j列1的个数之和。

5、（1）

散列地址

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

关键字

32

17

63

49

24

40

10

30

31

46

47

比较次数

1

1

6

3

1

2

1

1

1

3

3

（2）查找关键字63，H（k）=63MOD16=15，依次与31，46，47，32，17，63比较。

（3）查找关键字60，H（k）=60MOD16=12，散列地址12内为空，查找失败。

（4）ASLsucc=23/11

四、算法设计题（每小题15分，共60分）

1、算法：

intisrise(lklistL)

{p=L-next;b=p-data–L-data;

while(p-next!=NULL)

{q=p-next;

if(q-data–p-data!=b)return(0);

elsep=q;}

return(1);

}

2、方法是先依次让单链表上的元素进栈，然后再依次出栈。

voidinvert(lklisthead)

{LstackTps;

initstack(s);

p=head;

while(pnull)

{push(s,p-data);p=p-next;}

p=head;

while(notemptystack(s))

{pop(s,p-data);p=p-next;}

}

3、本题算法思路是：先设置一个空的邻接表，然后在邻接矩阵上查找值不为空的元素，找到后在邻表的对应单链表中插入相应的边的表结点。

voidmattolist(inta[][],AdjListb[],intn)/*n为图的结点个数*/

{for(i=0;in;i++)b[i].firstarc=NULL;/*邻接表置空*/

for(i=0;in;i++)/*逐行进行*/

for(j=n-1;j=0;j--)

if(a[i][j]!=0)

{p=(ArcNodeTp*)molloe(sizeof(ArcNodeTp));/*产生邻接点*/

p-adjvex=j;/*插入到表头*/

p-nextare=b[i].firstare;

b[i].firstarc=p;

}

}

4、分析：本题的算法思想是：先设置好上、下界，然后分别从线性表两端查找正数和负数，找到后进行交换，直到上、下界相遇。

voidexample(datatypeA[n])

{i=1,j=n;/*i,j为左右边界*/

while(ij)

{while((ij)(A[i]0))i++;/*在左边界找正数*/

while((ij)(A[j]0))j--;/*在右边界找负数*/

if(ij)

{temp=A[i];A[i]=A[j];A[j]=A[temp];/*交换两个元素的值*/

i++;j--;}

}

}

第二套（答案）

一、选择题

题号