上海应用技术学院计算机学院,2017年上海应用技术学院计算机学院816数据结构与算法考研题库...

短命女 2022-10-07 04:46 175阅读 0赞

一、填空题

1． 已知二叉排序树的左右子树均不为空，则\_\_\_\_\_上所有结点的值均小于它的根结点值，\_\_\_\_\_上所有结点的值均大于它的根结点的值。

【答案】左子树；右子树 【解析】二叉排序树

或者是一棵空树，或者是具有下列性质的二叉树：①若它

的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。

2． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共\_\_\_\_\_个，单链表为\_\_\_\_\_个。

【答案】4; 2

3． 设用希尔排序对数组\{98，36，-9，0，47，23，1，8，10，7\}进行排序，给出的步长(也称 增量序列)依次是4，2，1则排序需\_\_\_\_\_趟，写出第一趟结束后，数组中数据的排列次序\_\_\_\_\_。

【答案】3; (10，7，-9，0，47，23，1，8，98，36)

4． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 \_\_\_\_\_。

【答案】2

【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。

5． 在二叉树中，指针p 所指结点为叶结点的条件是\_\_\_\_\_。

【答案】

【解析】叶子节点的左右孩子都不存在。

6． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是\_\_\_\_\_、\_\_\_\_\_、\_\_\_\_\_、\_\_\_\_\_。

【答案】

7． 已知一循环队列的存储空间为环队列判满的条件是( )

【答案】

8． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：

第 2 页，共 73 页

其中

队头和队尾指针分别为front 和rear , 则此循

【答案】

【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。

9． 设有个结点的完全二叉树顺序存放在向量中，其下标值最大的分支结点为\_\_\_\_\_。

【答案】

【解析】最大的分支结点是最后一个叶子结点的父结点。

10．在下面的程序段中，对X 的赋值语句的时间复杂度为\_\_\_\_\_(表示为n 的函数)。

【答案】1＋(1＋2)＋(1＋2＋3)＋"•＋(l ＋2＋... ＋n )=n(n ＋1)(n ＋2)/6，即

【解析】当i=l时，赋值语句就被执行了一次。当i=2时，赋值语句被执行了1＋2次。当i=3时，赋值语句被执行了1＋2＋3次。可以推出赋值语句总共被执行了1＋(1＋2)＋(1＋2＋3)＋…＋(l ＋2＋... ＋n )=n(n ＋1)(n ＋2)/6次。

二、选择题

11．对任意一棵树，设它有n 个结点，这n 个结点的度数之和为( )。

A.n

D. 【答案】C

【解析】每个结点(除根节点外)都是一个分支，即所有结点的度数之和等于分支个数等于总的结点数减一，即n-1。

12．下列选项中，导致创建新进程的操作是( )。

用户登录成功

设备分配

启动程序执行 A.

仅

和

第 3 页，共 73 页

仅

和C.

仅

和D.

和

【答案】C

【解析】进程创建是需要填写PCB 表的，其中唯一不需要的是II 。考察一个进程创建的过程是这样的：当进程被创建，可以是用户创建，例如双击相关图标；也可以由父进程创建，例如lock ( )时，操作系统首先到PCB 表区搜索空闲的表格，若无则直接拒绝创建进程，若有则填，许多操写PCB 表创建进程。通常填写PCB 表的过程有一段时间(主要涉及资源分配需要协调)，也有的操作系统不设这个中间状态。此时操作系作系统为此设立了一个中间状态称为“初始化”

统填写进程ID 号、处理机参数、进程参数(状态、特权、优先级)、分配内存(若是虚拟存储就分配虚拟地址)、映射文件等，一切就绪，将控制权交给系统进行下一步调度。设备分配可能引起进程状态的改变，但不会创建新进程，用户登录成功和启动程序执行都会创建新的进程，所以本题答案为C 。

13．在缺页处理过程中，操作系统执行的操作可能是( )。

I. 修改页表 II. 磁盘I/O III. 分配页框 A. 仅 I 、II B. 仅II C. 仅III D.I 、II 和III 【答案】D

【解析】首先我们要考虑的是，为什么会发生缺页中断? 当然，在一个采用虚拟存储管理技术的系统中，程 序是部分装入的，还有部分是处于外存上的，因此，当需要访问那部分位于外存上的代码或数据时，系统会产生 缺页中断。产生缺页中断的目的是要将位于外存上的代码或数据装入内存，据此，缺页中断接下去所做的工作就是首先要在内存中找到空闲页框并分配给需要访问的页(若没有空闲的页面则要调用页面置换程序找到一处页 面，将该页面的内容处理掉，或回写，分配妥当以后，缺页中断处理程序调用设备磁盘，或覆盖掉，然后将此页分配给需要访问的页)

驱动程序做磁盘1/0, 将位于外存(一般是磁盘)上的页面调入内存，调入后转身去修改 页表，将，将物理页表中代表该页是否在内存的标志位(一般称为存在位或有效位、在位位)修改为“真”页框号填入相应位置，若必要还需修改其它相关表项等。完成上述任务后，缺页中断处理程序返 回，继续程序的执行。 从上述过程可以看出，涉及的相关处理非常多，因此，答案就显而易见了。

14．用邻接表存储图所用的空间大小( )。

A. 与图的顶点数和边数都有关 B. 只与图的边数有关

第 4 页，共 73 页