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