《2017年云南农业大学基础与信息工程学院813计算机导论与数据结构考研仿真模拟题.doc》由会员分享，可在线阅读，更多相关《2017年云南农业大学基础与信息工程学院813计算机导论与数据结构考研仿真模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年云南农业大学基础与信息工程学院813计算机导论与数据结构考研仿真模拟题一、填空题1 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空： 【答案】 【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。 2 在单链表中设置头结点的作用是_。【答案】方便运算3 顺序栈用【答案】存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_。 【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。4 G 是一个非连通无向图，共有28条边，则该
2、图至少有_个顶点。【答案】9【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。5 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_，又称P 为_。【答案】模式匹配；模式串 6 阅读下列程序，指出其功能，并写出空格处应填上的语句。 的元素，如该元素已在哈希表中，报告出错。 【答案】【解析】本题是在哈希表ht中插入值为7 外排序的基本操作过程是_和_。；归并 【答案】生成有序归并段（顺串） 8 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_、_、_、_。【答案】 9 串是一种特殊的线性表，其特殊性表现在_; 串的两种最基本的存
3、储方式是_、_; 两个串相等的充分必要条件是_。【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等10有向图G=（V ，E ）, 其中V （G ）=0, 1，2，3，4, 5, 用三元组表示弧及弧上的权d 。 E （G ）为 E （G= , , ， ，则从源点0到顶点3的最短路径长度是_，经过的中间顶点是_。【答案】50; 4 11如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_。【答案】69【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。12克鲁斯卡尔算法的时间复杂度为_，它对
4、_图较为适合。【答案】O （eloge ）; 边稀疏13给定一组数据的值为_。 【答案】5；96【解析】每次找两个最小的权值构建哈夫曼树：以它构造一棵哈夫曼树，则树高为_，带权路径长度 14线性表【答案】（n 1）/2 用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。【解析】删除第一个元素需要移动n i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为 15数据结构是研讨数据的_和_以及它们之间的相互关系，并对与这种结构定义相应的_，设计出相应的_。；算法 【答案】逻辑结构；物理结构；操作（运算）二、判断题16AOE 网一定是有向无环图。（ ）【答
5、案】【解析】在带权的有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销，则称 这种有向图表示活动的网络，简称为AOE 网。因此对AOE 网是否是有向无环图没有要求。 17在链队列中，即使不设置尾指针也能进行入队操作。（ ）【答案】 【解析】因为存在头指针，根据链表的性质，根据头指针可以找到为指针。 18对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）【答案】【解析】索引顺序存取方法插入操作比较麻烦，对于处理大量数据，会有大量的记录进入溢出区，而基本区中又浪费很多空间。192，. ，n , 输出序列是栈的输入序列是1，【答案】 比如1进栈，然后出栈， 【解析】出栈序列不一定满足 若则有： （ ）一、填空题考研试题
