文档介绍：北京邮电大学98考研题
注意事项:
1、解答请写在答题纸上,字迹要清楚、语义确切,图表工整。
2、算法题应有变量说明,并简要说明算法思想适当加注试题。
一、判断题:(16分) (请在答卷上写上题号,并注明正确划“√”或错误划“×”
。
,结点和结点内部的存储空间可以是不连续的。
(依次)进栈,=[1/(n+1)]*(2n)!/[(n!)*(n!)]
, 任一结点X,其左子树根结点的值<该结点(X)的值;其右子树根结点的值≥该结点(X)的值,则此二叉树一定是二叉排序树。
5. 有几个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩中非零元素之和的一半。
6. 有n个数存放在一维数组A[1..n],在进行顺序查找时, 这n个数的排列有序或无序其平均查找长度不同.
,而且所需附加空间也最少。
,可利用内部排序的方法进行排序,因此排序所花的时间取决于内部排序的时间。
二、选择题:(12分) (请在答卷上写上题号和选择框[ ]内的标号以及在各题供选择答案中选择的正确答案的标号。)
表长为n的顺序存储的线性表,当在任何位置上插入或刚除一个元素的概率相等时,插入一个元素所需移动的元素的平均个数为[ ],删除一个元素需要移动元素的平均个数为[ ]。供选择的答案:
(1) (n-1)/2 (2) n (3) n+1 (4) n-1 (5) n/2 (6) (n+1)/2 (7) (n-2)/2
Llink data rlink
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、模式串大=“aabdab”,该模式串的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)