一、选择题
1、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A.N B.2N-1 C.2N D.N-1
2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。
A.13 B.33 C.18 D.40
3、计算机算法指的是解决问题的步骤序列，它必须具备（ ）三个特性。
A.可执行性、可移植性、可扩充性
B.可执行性、确定性、有穷性
C.确定性、有穷性、稳定性
D.易读性、稳定性、安全性
4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（ ）。
A.h->next=s
B.s->next=h
C.s->next=h;h->next=s
D.s->next=h-next;h->next=s
5、动态存储管理系统中，通常可有（ ）种不同的分配策略。
A.1 B.2 C.3 D.4
6、下列关于无向连通图特性的叙述中，正确的是（ ）。
Ⅰ．所有的顶点的度之和为偶数 Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1
A．只有Ⅰ．只有Ⅱ C．Ⅰ和Ⅱ．Ⅰ和Ⅲ
7、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（ ）。
8、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（ ）。
A.在树T中，X是其双亲的第一个孩子
B.在树T中，X一定无右兄弟
C.在树T中，X一定是叶结点
D.在树T中，X一定有左兄弟
9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有（ ）个叶子。
A.log2n（n－1）/2n+1 D.（n＋1）/2
10、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
A.（100，80，90，60，120，110，130）
B.（100，120，110，130，80，60，90）
C.（100，60，80，90，20，110，130）
D.（100，80，60，90，120，130，110）
二、填空题
11、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为______。
12、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。
13、VSAM系统是由______、______、______构成的。
14、应用Prim算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。
（2）下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。
15、n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。
注：(1)图的顶点号从0开始计。
(2)indegree是有n个分量的一维数组，放顶点的入度，
(3)函数crein用于计算顶点入度。
(4)有三个函数push(data)，pop()，check()其含义为数据data入栈，出栈和测试栈是否空(不空返回l，否则0)。
16、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。
17、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是______。
18、设广义表L=（（），（）），则head（L）是______； tail（L）是______；L的长度是______；深度是______。
三、判断题
19、倒排文件的目的是为了多关键字查找。（ ）
20、直接访问文件也能顺序访问，只是一般效率不高。（ ）
21、循环队列也存在空间溢出问题。（ ）
22、一个广义表可以为其他广义表所共享。（ ）
23、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（ ）
24、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（ ）
25、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
（ ）
26、在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（ ）
27、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（ ）
28、有向图中顶点V度等于其邻接矩阵中第V行中的1的个数。（ ）
四、简答题
29、三维数组A[1..10，-2..6，2..8]的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间?如果数组元素以行优先的顺序存储，设第一个元素的首地址是100，试求元素A[5，0，7]的存储首地址。
30、假定对有序表：（3，4，5，7，24，30，42，54，63，72，87， 95）进行折半查找，试回答下列问题：
（1）画出描述折半查找过程的判定树。
（2）若查找元素54，需依次与哪些元素比较?
（3）若查找元素90，需依次与哪些元素比较?
（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。
31、已知有6个顶点（顶点编号为0～5）的有向带权图G，其邻接矩阵A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。
要求：
（1）写出图G的邻接矩阵A。
（2）画出有向带权图G。求图G的关键路径，并计算该关键路径的长度。
五、算法设计题
32、设有一个数组中存放了一个无序的关键序列K1，K2，…，Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n（注：用程序实现）。
33、请编写完整的程序。如果矩阵A中存在这样的一个元素A[i，j]满足条件：A[i，j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A的所有马鞍点。
34、编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A～Z这26个字母和0～9这10个数字）。
35、写出算法，求出中序线索二叉树中给定值为x的结点之后继结点，返回该后继结点的指针。线索树中结点结构为：（ltag，lc，data，rc， rtag）。其中，data存放结点的值；lc、rc为指向左、右孩子或该结点前驱、后继的指针，ltag、rtag为标志域，若值为0，则lc、rc为指向左、右孩子的指针；若值为1，则lc、rc为指向其前驱、后继结点的指针。
参
一、选择题
1、【答案】A
2、【答案】B
3、【答案】B
4、【答案】D
5、【答案】C
6、【答案】A
7、【答案】D
8、【答案】D
9、【答案】D
10、【答案】C
二、填空题
11、【答案】（n+1）/2
12、【答案】n（n-1）/2
13、【答案】索引集；顺序集；数据集
14、【答案】
(1)(0，3，1)；(3，5，4)；(5，2，2)；(3，1，5)；(1，4，3)
(2)① T[k]；toVex=i② min=MaxInt;③ mispos=i④ exit(0)⑤ T[i]； fromVex=v
【解析】Prim算法的执行类似于寻找图的最短路径的Dijkstra算法。假设 N={V，E}是连通图，ET是N上最小生成树边的集合。算法从VT={u0}， ET开始，重复执行下述操作：在所有u属于VT，v属于V-VT的边（u， v）属于E中找一条代价最小的边（u0，v0）加入集合ET，同时将v0并入VT，直到VT=V为止。
15、【答案】0；j；i；0；indegree[i]=0；[vex][i]；k==l；indegree[i]=0
【解析】有向图用邻接矩阵表示时，顶点i的入度等于第i列的所有元素之和。拓扑排序过程：首先将入度为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其他顶点的入度减一，然后判断这些顶点的入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。
16、【答案】
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s和t，则结点i和j在同一层上的条件是
17、【答案】s=（LinkedList*）ma11oc（sizeof（LNode））；s->data=x；s->next=r->next；r->next=s；r=s。
18、【答案】（）；（（））；2；2
三、判断题
19、【答案】√
20、【答案】×
21、【答案】√
22、【答案】√
23、【答案】×
24、【答案】√
25、【答案】×
26、【答案】×
27、【答案】√
28、【答案】×
四、简答题
29、答：数组占的存储字节数=10*9*7*4=2520；A[5，0，7]的存储地址=100+[4*9*7+2*7+5]*4=1184。
30、答：（1）判定树如图所示：
（2） 若查找元素54，需依次和元素30、63、42、54比较，查找成功。
（3） 若查找元素90，需依次和元素30、63、87、95比较，查找失败。
（4）
31、答：（1）由题可以画出待定上三角矩阵的结构图如下（图中？为待定元素）：
可以看出，第一行至第五行主对角线上方的元素分别为5，4，3，2，1 个，由此可以画出压缩存储数组中的元素所属行的情况，如下图所示：
将各元素填入各行即得邻接矩阵：
（2）根据第一步所得矩阵A容易做出有向带权图G，如下：
（3）关键路径为0-＞1-＞2-＞3-＞5（如下图所示粗线表示），长度为4＋5＋4＋3＝16。
五、算法设计题
32、答：算法如下：
33、答：算法如下：
34、答：算法如下：
35、答：算法如下：下载本文
