2017年北方民族大学计算机软件与理论832C语言程序设计与数据结构之数据结构考研冲刺密押题
● 摘要
一、填空题
1． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
2． 二进制地址为011011110000，大小为
【答案】011011110100；011011100000
011011110000是块的起始地址，
【解析】大小分别为式如下：
当大小为4时，起始地址
为
3． 模式串的next 函数值序列为_____。
【答案】01122312
4． 设有两个算法在同一机器上运行，其执行时闻分别为_____。
【答案】15
【解析】当时，而，时，
5． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：
第 2 页，共 39 页
和块的伙伴地址分别为：_____ 和
其伙伴块的起始地址计算公
当大小为16时，起始地址为
：
要使前者快于后者，n 至少为
【答案】
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
6． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】
完全二叉树的高度
7．
设单链表的结点结构为
为指针域，已知指针px 指向单链表中data 为x 的结
_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：
_____;
【答案】
8． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
9． 一个算法具有5个特性：_____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
10．对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构（网状结构）
二、判断题
11．队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 （ ）
【答案】
【解析】队列是一种先入先出型结构，而栈才是先进后出的线性结构。
12．在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。（ ）
【答案】×
【解析】伙伴系统的伙伴不一定是位置相邻的内存块。
起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
只要符合公式的内存块都是伙伴。
第 3 页，共 39 页
13．通常使用队列来处理函数或过程的调用。（ ）
【答案】
【解析】经常使用栈来处理函数或过程的调用。
14．抽象数据类型与计算机内部表示和实现无关。（ ）
【答案】
【解析】抽象数据类型只表示数据的逻辑结构，与计算机内部表示和实现无关。
15．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（ ）
【答案】
【解析】算法的健壮性是指当输入数据非法时，算法能作适当的处理并作出反应，而不应死机或输出异常结果。
16．对于有n 个结点的二叉树，其高度为
【答案】×
【解析】例如n 结点的单枝树，高度就为n 。
17．栈和队列都是限制存取点的线性结构。（ ）
【答案】
18．为了很方便的插入和删除数据，可以使用双向链表存放数据。（ ）
【答案】
【解析】链式存储结构便于数据的插入和删除，但只能顺序访问表中的元素。
19．文件系统采用索引结构是为了节省存储空间。（ ）
【答案】×
【解析】是为了缩短查找的时间，牺牲了一部分存储空间。
20．即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（ ）
【答案】
【解析】栈只是一种先入后出的存储结构。对于出栈、入栈的元素不进行修改，因此，输入序列的元素不相同，不可能得到相同的输出序列。
（ ）
三、算法设计题
第 4 页，共 39 页
相关内容
相关标签