2017年江苏科技大学计算机科学与工程学院845计算机综合之数据结构考研题库
● 摘要
一、选择题
1． 连续存储设计时，存储单元的地址（ ）。
A. 一定连续 B. 一定不连续 C. 不一定连续
D. 部分连续，部分不连续 【答案】A
【解析】连续存储是指数据的物理存储相连，即存储单元的地址是连续的。
2． 以下数据结构中，（ ）是非线性数据结构。
A. 树 B. 字符串 C. 队 D. 栈 【答案】A
【解析】非线性结构是指存在一对多或者多对一的关系。常见的非线性结构有树结构和图结构。
3． 执行（ ）操作时，需要使用队列做辅助存储空间。
A. 查找哈希（Hash ）表 B. 广度优先搜索网 C. 前序（根）遍历二叉树 D. 深度优先搜索网 【答案】B
【解析】查找哈希表不需要辅助存储空间，前序遍历二叉树和深度优先搜索网需要使用栈做辅助存储空间，广度优先搜索树需要队列做辅助存储空间。
4． 输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）。
【答案】B
【解析】根据输入序列和输出序列可知，输入序列全部进栈，然后再出栈。从中可以看出，
push 的数目始终大于等于pop 的数目。
5． 下列有关RAM 和ROM 的叙述中，正确的是（ ）。
I.RAM 是易失性存储器，ROM 是非易失性存储器 II.RAM 和ROM 都采用随机存取方式进行信息访问 III.RAM 和ROM 都可用作Cache IV.RAM 和ROM 都需要进行刷新 A. 仅I 和II B. 仅II 和III C. 仅 I 、II 和IV D. 仅II 、III 和IV 【答案】A
RAM 中的内容断电后即丢失ROM 中的内容断电后不会丢失，，【解析】（易失性）（非易失性），同时RAM 和ROM 都采用随机存取方式（即CPU 对任何一个存储单元的存取时间相同）区别在于RAM 可读可写，ROM 只读不写。而ROM 显然不可用作Cache , 也不需要刷新，所以III 和IV 的叙述都是错误的。
6． 假定编译器规定int 和short 类型长度分别为32位和16位，执行下列C
语言语句
得到y 的机器数为（ ）。
【答案】B 。
【解析】X 和y 均为无符号数，其中X 为16位，y 为32位，将16位无符号数转化成32位 无符号数，前面要补零。因为所以
7． 采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（ ）。
A. 递归次数与初始数据的排列次序无关
B. 每次划分后，先处理较长的分区可以减少递归次数 C. 每次划分后，先处理较短的分区可以减少递归次数 D. 递归次数与每次划分后得到的分区的处理顺序无关 【答案】D
【解析】快速排序是递归的，递归过程可用一棵二叉树给出，递归调用层次数与二叉树的深，采用快速排序方法，其对应递归调用度一致。例如：待排序列{48, 62，35, 77, 55, 14, 35, 98）过程的二叉树如下图所示。
在最坏情况下，若初始序列按关键码有序或基本有序时，快速排序反而蜕化为冒泡排序。即其对应递归调用过程的二叉树是一棵单支树。因此快速排序的递归次数与初始数据的排列次序有关。但快速排序的递归次数与每次划分后得到的分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。
8． 下列关于AOE 网的叙述中，不正确的是（ ）。
A. 关键活动不按期完成就会影响整个工程的完成时间 B. 任何一个关键活动提前完成，那么整个工程将会提前完成 C. 所有的关键活动提前完成，那么整个工程将会提前完成 D. 某些关键活动若提前完成，那么整个工程将会提前完成 【答案】B
【解析】关键路径是指从有向图的源点到汇点的最长路径。某些关键活动提前完成，那么整个工程将会提前完成，但不是任何一个关键活动提前完成，就能保证整个工程将会提前完成。
9． 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A. 单链表
B. 仅有头指针的单循环链表 C. 双链表
D. 仅有尾指针的单循环链表 【答案】D
【解析】仅有尾指针的单循环链表，在最后插入元素和删除第一个元素都会用到这个尾指针。
10．当字符序列作为图输入时，输出长度为3的且可用作C 语言标识符的序列的有（ ） 。
A.4个 B.5个 C.3个 D.6个
相关内容
相关标签