数据结构专升本模拟题及参考答案2.doc

作业题（一） 一、单项选择题 1. 从逻辑上可以把数据结构分为（ ）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 2. 链表不具有的特点是（ ） A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 3.下面程序段的时间复杂度的量级为（ ）。 For(i=1;i=n;i++) For(j=1;j=I;j++) For(k=1;k=j;k++) X=x+1; A．O(1) B．O(n) C．O(n2) D．O(n3) 4.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（ ）个指针域的值。 A．2 B．3 C．4 D．6 5、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（ ）。 A．98 B．100 C．102 D．106 6、判定一个栈s（最多元素为m0）为空的条件是（ ）。 A．s-〉top! =0 B．s-〉top= =0 C．s-〉top! =m0 D．s-〉top= =m0 7、循环队列用数组A[m]（下标从0到m-1）存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（ ）。 A．（rear-front+m）%m B．rear-front+1 C．rear-front-1 D． rear-front 8、设有两个串S1与S2，求串S2在S1中首次出现位置的运算称作（ ）。 A．连接 B．求子串 C．模式匹配 D．判子串 9、设串S1=ABCDEFG，S2=PQRST，函数con（x，y）返回x和y串的连接串，subs(s,i,j)返回串S的的从序号i的字符开始的j个字符组成的子串，len(s)返回串S的长度，则con(subs(S1,2,len(S2)),subs(S1,len(S2),2))的结果是（ ）。 A．BCDEF B．BCDEFG C．BCPQRST D．BCDEFEF 10、数组常用的两种基本操作是（ ）。 A．建立与查找 B．删除与查找 C．插入与索引 D．查找与修改 二、填空题 1. 所谓稀疏矩阵指的是________且分布没有规律2. 队列是________的线性表，其运算遵循________的原则。 3. 空格串是________________________________。 4.简单选择排序和起泡排序中比较次数与序列初态无关的算法有________。 5、设图G有n个顶点和e条边，则对用邻接矩阵表示的图进行深度或广度优先有哪些信誉好的足球投注网站遍历时的时间复杂度为　　　，而对用邻接表表示的图进行深度或广度优先有哪些信誉好的足球投注网站遍历时的时间复杂度为　　　，图的深度或广度优先有哪些信誉好的足球投注网站遍历时的空间复杂度均为　　　。 6、一个图的　　　　表示法是唯一的，而　　　表示法是不唯一的。 三、算法 设二叉树采用二叉链表结构，试设计一个算法统计给定二叉树中的一度结点数目。 四、应用题 1、对关键字无序序列(36，25，48，12，65，43，20，58)进行直接选择排序，请写出每一趟排序的结果。（10分） 2、对无向带权图，用克鲁斯卡尔算法构造最小生成树。（10分） 3、已知记录关键字集合为（53,17,19,61,98,75,79,63,46,49）要求散列到地址区间（100,101,102,103,104,105,106,107,108,109）内，若产生冲突用开型寻址法的线性探测法解决。要求写出选用的