北邮数据结构1998.docVIP

北京邮电大学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 A 0 1 0 1 0 0 0 0 B 1 0 1 0 1 1 1 0 C 0 1 0 1 0 0 0 0 D 1 0 1 0 0 0 1 0 E 0 1 0 0 0 0 0 1 F 0 1 0 0 0 0 1 1 G 0 1 0 1 0 1 0 1 H 0 0 0 0 1 1 1 0 缺少第三也 Lli