1998年北京市文凭考试“数据结构”试题

　　适用专业：计算机应用、计算机网络

　　一、判断题(每小题1分，共10分)

　　1.程序是用计算机语言表述的算法。()

　　2.线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。

()

　　3.用一组地址连续的存储单元存放的元素一定构成线性表。()

　　4.堆栈、队列和数组的逻辑结构都是线性表结构。()

　　5.给定一组权值，可以唯一构造出一棵哈夫曼树。()

　　6.给定AOE网的关键路径是唯一的。()

　　7.建立索引文件时，用户除了提供该文件的基本数据外，还必须提供索引表。()

　　8.相对于索引文件的基本数据，索引表包含的信息量相对少得多，因此。索引表可以常驻内存。()

　　9.在平均情况下，快速排序法最快，堆积排序法最节省空间。()

　　10.快速排序法是一种稳定性排序法。()

　　二、单项选择题(每小题2分，共10分)

　　1.采用顺序查找方法查找长度为n的线性表，平均查找长度为()。

　　A.nB.n/2

　　C.(n+1)/2D.(n-1)/2

　　2.对线性表采用折半查找法，该线性表必须()。

　　A.采用顺序存储结构B.采用链式存储结构

　　C.采用顺序存储结构，且元素按值有序

　　D.采用链式存储结构，且元素按值有序

　　3.已知二叉树的前序序列为ABDCEFG，中序序列为DBCAFEG，则后序序列为()。

　　A.DCBAFGEB.DCBFGEA

　　C.DCBFEGAD.DCBGFEA

　　4.按逐点插入法建立对应于序列(54，28，16，34，73，62，95，60，26，43)的二叉排序树后，查找62要进行____次比较。()

　　A.6次B.5次C.3次D.2次

　　5.根据堆积定义，下面的四个序列中，_______是堆积。()

　　A.75，65，30，15，25，45，20，10

　　B.75，65，45，10，30，25，20，15

　　C.75，45，65，30，15，25，20，10

　　D.75，45，65，10，25，30，20，15

　　二、填空题(每空2分，共20分)

　　1.算法独立于具体的_________________，与具体的程序设计语言____________。

　　2.若堆栈采用顺序存储结构，在不产生溢出的时候往堆栈中插入一个新元素，首先_________________________，然后再___________________。

　　3.在一棵二叉树中有n0个叶结点，有n2个度为2的结点，则n0=_____________。

　　4.索引文件包括_____________和_____________两部分，而且________________是按照关键字值有序排列的。

　　5.对具有n个元素的序列采用插入排序法和选择排序法，排序趟数均为_______，而采用泡排序法进行排序，排序趟数是一个范围___________________。

　　三、简答题(共20分)

　　1.空串与由空格组成的串有何区别？(5分)

　　2.一个带权连通图的最小生成树是否唯一？什么情况下可能不唯一？(7分)

　　3.从数据结构和操作两方面说明杂凑(Hash)文件有什么特点？(8分)

　　四、问题求解题(每小题10分，共20分)

　　1.已知一稀疏矩阵的三元组存储如下所示，请画出其十字链表表示。

　　678

　　146

　　235

　　262

　　427

　　512

　　551

　　564

　　618

　　2.若杂凑表的地址范围为0:9，杂凑函数为H(key)=(key2+2)MOD9，并且采用链地址方法处理冲突，请画出元素7,4,5,3,6,2,8,9,1依次插入该杂凑表以后，该杂凑表的状态。

　　六、算法题(每小题10分,共20分)

　　1.已知二叉排序树中任意分支结点的值均大于其左孩子的值(若左孩子存在)，并且小于或等于其右孩子的值(若右孩子存在)，设二叉排序树采用二叉链表存储结构，链结点的构造为lchilddatarchild，根结点的地址由T指出。下面是在该二叉排序树中查找值为key的结点的非递归算法，查找成功，返回被查到结点的地址，否则返回nil。

　　请在算法的空缺处填入适当内容，使之能够正常工作。

　　nSORTSRCH(T,key)

　　p←T

　　whilep≠nildo

　　┏━━━━━━━━━━━━━━━━━━┓

　　┃┃

　　┃┃

　　┃┃

　　┃┃

　　┃┃

　　┃┃

　　┗━━━━━━━━━━━━━━━━━━┛

　　end

　　return(nil)

　　end

　　2.已知二叉树采用二叉链表存储结构，链结点的构造为lchilddatarchild，根结点的指针为T。下面是利用中序遍历的方法统计二叉树中度为1的结点的个数的算法，算法中设置了一顺序存储结构的堆栈STACK1:M，栈顶指针为top，请在算法的空缺处填入适当内容，使之能正常工作。

　　nSTACKS(T)

　　n←0

　　ifT=nilthen

　　return(n)

　　top←0

　　p←T

　　repeat

　　whilep≠nildo

　　if┏━━━━━━━━━━━━━━┓then

　　┗━━━━━━━━━━━━━━┛

　　callERROR(STACKISOWERFLOW)

　　rerurn

　　┏━━━━━━━━━━━━━━┓

　　┗━━━━━━━━━━━━━━┛

　　STACKtop←p//进栈//

　　p←lchird(p)

　　end

　　p←STACKtop//退栈//

　　┏━━━━━━━━━━━━━━┓

　　┗━━━━━━━━━━━━━━┛

　　if┏━━━━━━━━━━━━━━━━━┓then

　　┗━━━━━━━━━━━━━━━━━┛

　　n←n+1//度为1的结点个数增1//

　　p←rchild(p)

　　until┏━━━━━━━━━━━━━━┓

　　┗━━━━━━━━━━━━━━┛

　　return(n)

　　end