课程代码：02142

一、单项选择题(本大题共15小题，每小题2分，共30分)

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1.数据的基本单位是（　　　）

A.数据项                                                                B.数据类型

C.数据元素                                                            D.数据变量

2.下列程序的时间复杂度为（　　　）

i=0；s=0；

while（s<n）

{ i++；

s=s+i；

}

A.O（ ）                                                           B.O（ ）

C.O（n）                                                                D.O（n2）

3.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（　　　）

A.单链表                                                                B.仅有头指针的单循环链表

C.双链表                                                                D.仅有尾指针的单循环链表

4.从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（　　　）

A.n-i                                                                       B.n-i+1

C.n-i-1                                                                    D.i

5.顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（　　　）

A.s.elem［top］=e；                                               B.s.elem［top+1］=e；

s.top=s.top+1；                               s.top=s.top+1；

C.s.top=s.top+1；                                                    D.s.top=s.top+1；

s.elem［top+1］=e；                           s.elem［top］=e；

6.循环队列sq中，用数组elem［0··25］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（　　　）

A.8                                                                        B.16

C.17                                                                       D.18

7.设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为（　　　）

A.13                                                                       B.35

C.17                                                                       D.36

8.含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（　　　）

A.3                                                                         B.4

C.5                                                                         D.6

9.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为（　　　）

A.24                                                                       B.25

C.98                                                                       D.99

10.可以惟一地转化成一棵一般树的二叉树的特点是（　　　）

A.根结点无左孩子                                                  B.根结点无右孩子

C.根结点有两个孩子                                               D.根结点没有孩子

11.有n个结点的有向完全图的弧数是（　　　）

A.n2                                                                        B.2n

C.n(n-1)                                                                  D.2n(n+1)

12.设图的邻接链表如题12图所示，则该图的边的数目是（　　　）

题12图

A.4                                                                        B.5

C.10                                                                       D.20

13.已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素时，检索成功需比较的次数是（　　　）

A.1                                                                        B.2

C.3                                                                         D.4

14.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（　　　）

A.选择排序                                                             B.快速排序

C.冒泡排序                                                             D.插入排序

15.排序算法中，不稳定的排序是（　　　）

A.直接插入排序                                                      B.冒泡排序

C.堆排序                                                                D.归并排序

二、填空题(本大题共13小题，每小题2分，共26分)

请在每小题的空格中填上正确答案。错填、不填均无分。

16.在数据结构中，数据的逻辑结构分为集合、________、树形结构和图状结构等四类。

17.通常从正确性、易读性、________和高效率等4个方面评价算法（包括程序）的质量。

18.顺序表的存储密度为________，而链表的存储密度为________。

19.对于栈只能在________插入和删除元素。

20.在循环队列中，存储空间为0～n-1,设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么队满标志为front=(rear+1)%n，队空标志为________。

21.三个结点可构成________种不同形态的二叉树。

22.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中________个用于链接孩子结点。

23.有向图G用邻接矩阵A［1··n，1··n］存储，其第i列的所有元素之和等于顶点Vi的________。

24.对二叉排序树进行________遍历，可得到排好序的递增结点序列。

25.采用折半查找方法进行查找的数据序列应为________且________。

26.索引文件只能是________，因为索引文件的组织方式是为随机存取而设计的。

27.在插入和选择排序中，若初始数据基本正序，则选用________；若初始数据基本反序，则选用________。

28.快速排序最好情况下的时间复杂度为________，最坏情况下的时间复杂度为________。

 

三、应用题(本大题共5小题，每小题6分，共30分)

29.已知一棵二叉树的中根序列和后根序列分别为B、D、C、E、A、F、H、G和D、E、C、B、H、G、F、A，试画出这棵二叉树，并给出其先根序列。

30.已知如题30图所示，用普里姆（prim）算法从顶点A开始求最小生成树。在算法执行之初，顶点的集合U={A，B}，边的集合TE={（A，B）}。试按照最小生成树的生成过程，分步给出加入顶点和边以后的集合U和TE的值。

31.设散列函数H（key）=key mod 11，给定键值序列为13、41、15、44、6、68、17、26、39、46，试画出相应的开散列表，并计算在等概率情况下查找成功时的平均查找长度。

32.从一个空的二叉排序树开始，依次插入关键字25、13、15、34、7、20、37，试分别画出每次插入关键字后的二叉排序树。

33.画出对应于序列{10，20，7，75，41，67，3，9，30，45}的初始堆（堆顶元素取最小值）。

四、算法设计题(本大题共2小题，每小题7分，共14分)

34.在下面冒泡排序算法中（1）～（4）处填入适当内容，以使该算法在发现有序时能及时停止。

bubble（R）

Rectype R［n］；

{int i，j，exchang；

Rectype temp；

i=1；

do

{exchang=False；

for（j=n；j>= （1）________；j--）

if（R［j］<R［j-1］

{temp=R［j-1］；

 R［j-1］=R［j］；

 R［j］=temp；

 exchang= （2）________；

}

 （3）________；

}

while（exchang= （4）________）；

}

35.下列函数是在无向图的邻接表中删除一条边的算法，请在（1）～（4）处填入适当内容加以完善。

Void deledge（ALGraph *G，int i，int j）

{ EdgeNode *p，*q；

p=G→adjlist［i］.firstedge；

if（p→adjvex==j）{G→adjlist［i］.firstedge=p→next；free（p）；}

else{while（p→next→adjvex!=j&&p→next）

（1）________；

if（p→next!=NULL）{q=p→next；（2）________；free（q）；}

}

p=G→adjlist［j］.firstedge；

if（p→adjvex==i）{G→adlist［j］.firstedge=p→next；free（q）；}

else{while（p→next→adjvex!=i&&p→next）

（3）________；

if（p→next!=NULL）{q=p→next；（4）________；free（q）；}

}

}