北京邮电大学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分) (请在答卷上写上题号和选择框[ ]内的标号以及在各题供选择答案中选择的正确答案的标号.)
表长为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表中取出原子项大的运算是 [ ].供选择的答案:
head(tail(tail(l))) (2) tail(head(head(tail(l)))
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结点开始深度优先遍历,得到的结点序列是 [ ].
A
B
C
D
E
F
G
H

下一页