北京邮电大学98考研题
注意事项：
1、解答请写在答题纸上,字迹要清楚、语义确切,图表工整。
2、算法题应有变量说明,并简要说明算法思想适当加注试题。
一、判断题：（16分） （请在答卷上写上题号，并注明正确划“√”或错误划“×”
1.数据元素是数据的最小单位。
2.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。
3.有n个数顺序（依次）进栈，出栈序列有Cn种，Cn=[1/（n 1）]*（2n）!/[(n!)*(n!)]
4.二叉树中除叶结点外, 任一结点X，其左子树根结点的值<该结点（X）的值；其右子树根结点的值≥该结点（X）的值,则此二叉树一定是二叉排序树。
5. 有几个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩中非零元素之和的一半。
6. 有n个数存放在一维数组A[1..n]，在进行顺序查找时， 这n个数的排列有序或无序其平均查找长度不同.
7.快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。
8.外部排序是把外存文件调入内存,可利用内部排序的方法进行排序,因此排序所花的时间取决于内部排序的时间。
二 、选择题：（12分） （请在答卷上写上题号和选择框[ ]内的标号以及在各题供选择答案中选择的正确答案的标号。）
1、表长为n的顺序存储的线性表，当在任何位置上插入或刚除一个元素的概率相等时，插入一个元素所需移动的元素的平均个数为 [ ],删除一个元素需要移动元素的平均个数为[ ]。供选择的答案：
(1) (n-1)/2 (2) n (3) n 1 (4) n-1 (5) n/2 (6) （n 1）/2 (7) (n-2)/2
2、在双向循环链表中,在P指针所指向的结点前插入一个指针所指向的新结点,其修改指针的操作是A.(注:双向链表的结点结构为:
供选择的答案：
（1） p↑.llink： =q； q↑.rlink：=p； p↑.llink↑.rlink：=q； q↑.llink：=q；
（2） p↑.llink：=q； p↑.llink↑rlink：=q ； q↑.rlink：= p； q↑.llink:=p↑.llink；
（3）q↑.rlink：=p；q↑.llink：=p↑.llink； p↑.llink↑.rlink：=q; p↑.llink：=q;
（4）q↑.llink:=p↑.llink； q↑.rlink:=p； p↑.llink：=q； p↑.llink：=q；
3、模式串大=“abcaabbccaabdab”，该模式串的next数组的值为 [ ],nextval数组的值为 [ ]。 供选择的答案：
(1) 0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 （2）0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2
(3) 0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 (4) 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2
（5）0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 （6）0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1
4、已知广义表L=（（x、y、z），a，（u，t，w）），从L表中取出原子项大的运算是 [ ]。供选择的答案：
（1）head（tail（tail（l））） （2） tail（head（head（tail（l）））
(3) head（tail（head（tail（l））） （4） head（head（tail（tail（l）））
5、一个A[1‥100，1‥100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即元素下标I=66，j=65），在B数组中的位置K为[ ]。供选择的答案：
（1）198 （2）195 （3）197
6、已知有8个结点值为A、B、C、D、E、F、G、H的无向图，其邻接矩阵的存储结构如下所示，由此结构从A结点开始深度优先遍历，得到的结点序列是 [ ]。
ABCDEFGH
A01010000
B10101110
C01010000
D10100010
E01000001
F01000011
G01010101
H00001110
缺少第三页