2017年西藏大学文学院824计算机专业基础综合之数据结构考研题库
● 摘要
一、选择题
1．
已知操作符包括的后缀表达式将中缀表达式转换为等价
时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（ ）。
A.5
B.7
C.8
D.11
【答案】A 。
【解析】基本思想是：采用运算符栈是为了比较运算符的优先级，所有运算符必须进栈。只将大于栈顶元素优先级的运算符直接进栈，否则需要退栈栈顶运算符（先出栈的运算符先计算，同优先级的运算符在栈中的先计算）
。表达式
所列：
产生后缀表达式的过程如下表
通过上表可以看出，显然转换过程中同时保存在栈中的操作符的最大个数是5。
2． 循环队列
元素数是（ ）。
存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的
【答案】A
【解析】对于循环队列，需要深刻理解队头在队尾进行进队操作。和队尾的概念，在队头进行出队操作，如果为负则元可能为正也可能为负，为正时元素个数=
素的个数=所以统一的公式就是
3． 下列选项中，会导致用户进程从态切换到内核的操作是（ ）
I. 整数除以零 II. Sin（ ）函数调用 III. read系统调用
A. 仅 I 、II
B .仅 I 、III
C. 仅II 、III
D. I、II 和III
【答案】B
【解析】对于I ，系统发生异常，需要进入内核态由操作系统进行处理，而read 系统调用函数也是在内核态执行，sin （ ）就是普通的用户函数，在用户态执行，故答案为C 。
4． 下列程常段的时间复杂度是（ ）
A.
B.
C.
D.
【答案】C
而对于k ，每次循环都执行所以循环次数为【解析】外部循环的退出条件是
内部循环的退出条件是对于j ，每次循环都执行所以每次循环次数为n 次。所以此程序段的时间复杂度为O 即选C 。
5． 设X 是树T 中的一个非根结点，B 是T 所对应的二叉树。在B 中，X 是其双亲的右孩子，下列结论正确的是（ ）。
A. 在树T 中，X 是其双亲的第一个孩子
B. 在树T 中，X —定无右兄弟
C. 在树T 中，X —定是叶结点
D. 在树T 中，X —定有左兄弟
【答案】D
【解析】由树和二叉树的转换关系可知，X 一定有左兄弟，X 是其双亲的第二个孩子，不能确定在树T 中，X 是否有右兄弟，是否是叶结点。
6． 在下述结论中，正确的有（ ）。
①只有一个结点的二叉树的度为0; ②二叉树的度为2; ③二叉树的左右子树可任意交换，④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A. ①②③
B. ②③④
C. ②④
D. ①④
【答案】D
【解析】只有根节点的二叉树的度为0，二叉树的左右子树隐含着他们的位置关系。因此，②③均错。
7． 下列选项中会导致进程从执行态变为就绪态的事件是（ ）。
A. 执行P （wait ）操作
B. 申请内存失败
C. 启动I/O设备
D. 被尚优先级进程抢占
【答案】D
【解析】D 项，被高优先级进程抢占，进程会由执行态变为就绪态。ABC 三项，程序由于缺少资源而由执行态转为阻塞态。
8． 下列排序算法中，其中（ ）是稳定的。
A. 堆排序，起泡排序
B. 快速排序，堆排序
C. 直接选择排序，归并排序
D. 归并排序，起泡排序
【答案】D
9． 在下列存储形式中，哪一个不是树的存储形式？（ ）
A. 双亲表示法
B. 孩子链表表示法
C. 孩子兄弟表示法
D. 顺序存储表示法
【答案】D
【解析】顺序存储就是利用一段连续的存储单元依次存储线性表中的元素。树中某个结点的
相关内容
相关标签