- 1、本文档共6页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
在职研究生全国联考数据结构模拟试题
一、选择题(20分,每题2分)1、学习数据结构主要目的是( C )。 A、处理数值计算问题 B、研究程序设计技巧 C、选取合适数据结构,写出更有效的算法 D、是计算机硬件课程的基础2、分块查找中确定块的查找采用的查找方法是( D )。 A、顺序查找 B、折半查找 C、顺序查找、折半查找都可以 D、顺序查找、折半查找都不可以3、在对应于序列(12,5,8,15,25,10,30,7)的二叉排序树中查找30需要进行( D )次比较。 A、1 B、2 C、3 D、44、当先后插入的关键字有序时,构成的二叉排序树蜕变成单支树。如果树的深度为n,其平均查找长度为( D )。 A、n B、n+1 C、n/2 D、(n+1)/25、已知序列{a,b,c,d}依次进入空栈,然后执行了2次出栈操作,则当前的栈顶元素是( B )。 A、a B、b C、c D、d6、已知长度为10的线性表采用顺序存储的方法,则插入或删除一个元素平均需要移动的元素个数为( B )。 A、11 B、5 C、4 D、107、在下列选项中,使用顺序表比链表好的运算是( C )。 A、插入 B、删除 C、根据序号查找 D、根据元素值查找8、适合作为经常在首尾两端进行操作的线性表的存储结构的是( C )。 A、顺序表 B、单链表 C、循环链表 D、双向链表9、设数组data[m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作后其头指针front值为( D )。 A、front=front+1 B、front=(front+1)%(m-1) C、front=(front-1)%m D、front=(front+1)%m10、在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D )。 A、e B、2e C、n2-e D、n2-2e?二、填空题(10分,每空1分)1、讨论算法时间复杂度往往分析(最坏)情况下的时间复杂度。2、队列又称为(先进先出)线性表。3、顺序查找查找成功时的最坏比较次数为(n-1)和查找失败时的比较次数为(n)。4、设有64个元素,用折半查找方法进行查找时,最大比较次数是(7),最小比较次数是(1)。5、对不同的关键字可能得到同一哈希地址,即key1!=key2,而f(key1)=f(key2),这种现象称为(冲突)。具有相同函数值的关键字对该哈希函数来说称作(同义词)。6、一棵深度为K且有2k-1个结点的二叉树称为(满二叉树)。7、在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时,其时间主要耗费在(元素的移动上)。?三、简答题(30分,每题5分)1、在AOE网中提高关键活动的速度应该注意什么?答:关键活动的速度提高是有限的。只有在不改变网的关键路径的情况下,提高关键活动的速度才有效。 若网中有几条关键路径,那么,单是提高一条关键路径上的关键活动的速度,还不能导致整个工程缩短工期,而必须提高同时在几条关键路径上的活动的速度。2、简述二叉排序树的定义。答:二叉排序树或者是一棵空树,或者是具有下列性质的二叉树: 1、若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 2、若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 3、它的左、右子树也分别为二叉排序树。3、直接插入排序算法最坏的情况是哪种情况,并说明为什么该算法的时间复杂度为O(n2)。答:最坏的情况是记录按照关键字非递增有序排列。因为第i趟时第i个记录必须与前面i-1个记录都做关键字比较,并且每做1次比较就要做1次数据移动。则总的关键字比较次数KCN和记录移动次数RMN分别为: 该算法的两个基本操作的频度都和n2有关。4、请比较快速排序和堆排序。答:可以得出的结论有:当待排序的结点个数 n较大时,则应该采用快速排序或堆排序。从平均排序速度来看,快速排序的速度最快,但在最坏情况下(待排序的结点序列已经几乎排好序),他的时间性能却很差。这时不如采用堆排序。但要注意快速排序和堆排序都是不稳定的。5、链栈中为何不设置头结点?答:链栈不需要在头部附加头结点,因为栈都是在头部进行操作的,如果加了头结点,等于要对头结点之后的结点进行操作,反而使算法更复杂,所以只要有链表的头指针就可以了。6、试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。答:开始结点是指链表中的第一个结点,也就是没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时),单链表由头指针唯一确定,因此单链表可以
文档评论(0)