2018年云南大学软件学院904计算机程序设计[专业硕士]之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____, 设计出相应的_____。
【答案】逻辑结构；物理结构；操作(运算) ；算法
2． 设有一个空枝，栈顶指针为1000H(十六进制) ，现有输入序列为1，2，3，4，5，经过PUSH ，PUSH ，POP ，PUSH ，POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序找，每个元素占4个字节。
【答案】23；100CH
3． 外排序的基本操作过程是_____和_____。
【答案】生成有序归并段(顺串) ；归并
4． 在基于关键字比较且时间为
【答案】归并；堆
5． 已知二维数组
【答案】1196
【解析】设元素的行标为i ，列标为j 。则它的存储位置为:l000＋[(i﹣l)*l0＋(j﹣0)]*4
6． 组成串的数据元素只能是_____。
【答案】字符
中每个元素占4个单元，在按行优先方式将其存储到起始地址_ 的排序中，若要求排序是稳定的，则可选用_____排序；若要求就地排序(及辅助空间为O(1))，则可选用_____排序。 为1000的连续存储区域时，A[5，9]的地址是: _____。
二、判断题
7． 哈希函数越复杂越好，因为这样随机性好，冲突概率小。（ ）
【答案】×
【解析】随机性好和冲突概率小跟哈希函数的复杂程度无关，是根据具体情况而定的，跟实际的数据有很大关系。
8． 树形结构中元素之间存在一对多的关系。（ ）
【答案】√
【解析】树形结构是非线性结构，存在一对多的关系。
9． 任何二叉树的后序线索树进行后序遍历时都必须用栈。（ ）
【答案】 ×
【解析】任何结点至多只有左子树的二叉树的遍历就不需要栈。
10．静态链表就是一直不发生变化的链表。（ ）
【答案】 ×
【解析】用数组描述的链表，即称为静态链表。仍具有链式存储结构的主要优点。不是指不发生变化的的链表。
11．强连通分量是无向图的极大强连通子图。（ ）
【答案】×
【解析】强连通分量是对有向图而言的，一般在无向图中讨论连通性。
12．抽象数据类型与计算机内部表示和实现无关。（ ）
【答案】 √
【解析】抽象数据类型只表示数据的逻辑结构，与计算机内部表示和实现无关。
三、单项选择题
13．下列调整中, 不可能导致饥饿现象的是（ ）
A. 时间片转移
B. 静态优先及调度
C. 非抢占式作业优先
D. 抢占式短作业优先
【答案】A
【解析】时间片转移方法能在一个周期内使每个进程都得到一个时间片的CPU 使用时间, 不会产生饥饿的现象, 其余三个都会产生饥饿。
14．下列程常段的时间复杂度是（ ）
A.O()
B.O(n) C.O()
D.O()
, 所以循环次数为; 【答案】C 【解析】外部循环的退出条件是k>n, 而对于k , 每次循环都执行
内部循环的退出条件是j>n, 对于j , 每次循环都执行, 所以每次循环次数为n 次。所以此程序
) , 即选C 。 段的时间复杂度为O(
15．循环两列放在一维数组中, end1指向队头元素, end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作, 队列中最多能容纳M-1个元素。初始时为空, 下列判断队空和队满的条件中, 正确的是（ ）
A. 队空:endl==end2; 队满:endl==(end2+l)modM
B. 队空Gendl==end2; 队满:Gend2==(endl+1)mod(M-1)
C. 队空Gend2==(endl+1)modM; 队满:Gendl==(end2+l)modM
D. 队空:
【答案】A
【解析】在循环队列中, 在少用一个元素空间的前提下, 可约定入队前, 测试尾指针在循环意义下加1后是否等于头指针, 若相等, 则队满。而队空的条件还是首尾指针是否相等。
16．已知串其Next 数组值为（ ）。
A.0123
B.1123
C.1231
D.1211
【答案】A
【解析】KMP 算法的next 数组建立的原则
队满:
17．将森林F 转换为对应的二叉树T , F 中叶结点的个数等于（ ）
A.T 中叶结点的个数
B.T 中度为1的结点个数
C.T 中左孩子指针为空的结点个数
D.T 中右孩子指针为空的结点个数
【答案】C
【解析】森林转化为对应的二叉树是„孩子-兄弟‟存储的, 即左孩子指针指向当前节点的孩子节点, 右孩子指针指向当前节点的兄弟节点, 所以在T 中左孩子指针为空则代表它在森林中并没有孩子即为叶结点。所以选C
相关内容
相关标签