《2016软件技术基础A综述.doc》由会员分享，可在线阅读，更多相关《2016软件技术基础A综述.doc（12页珍藏版）》请在三一文库上搜索。
1、第 1 页共 9 页 1. 下列程序段的时间复杂度为 for(i=1;i 学 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 由我学业 : 予 1 诺授亠 第 2 页共 9 页 其出栈序列。 A. 1243 B. 2134 C. 1432 D. 4312 4. _ 前序遍历和中序遍历结果相同的二叉树为 _ 。 A. 一般二叉树 B.只有根结点的二叉树 C.所有结点只有左孩子的二叉树 D.所有结点只有右孩子的二叉树 5. 一个线性顺序表第一个元素的存储地址是 100，每个元素的长度为 2,则第 5 个元素的地址为 _ 。 A. 110 B.
2、108 C. 100 D. 120 6. 在一个单链表中，若 p 所指结点不是最后结点，在 p 之后插入 s 所指的结点， 贝 y 执行 _ 。 A. s-n ext二p; p-n ext=s B. s-n ext=p-n ext; p-n ext=s C. s-n ext=p-n ext; p=s D. p-n ext=s; s-n ext=p 7. 完全二叉树 _ 二叉树。 A. 一定是满 B.可能是满 C.不是 D. 一定不是满 8. 在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的 _ 倍。 A . 1/2 B. 1 C. 2 D. 4 9. 要进行二分查找，则线性表 _ 。
3、A.必须以顺序方式存储 B.必须以链接方式存储 C.必须以队列方式存储 D.必须以顺序方式存储，且元素有序 10. 排序方法中，从未排序的序列中依次取出元素与已排序序列（初始时为空）中 的元素进行比较，将其放入已排序的序列的正确位置上的方法为 _ 。 A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序 11. 操作系统的功能是进行处理机管理、 _ 管理、设备管理和文件管理。 A.进程 B.存储器 C.硬件 D.软件 12. 系统中有两个进程 A 和 B，每个都需使用 1 台打印机和扫描仪，但系统中现在 只有一台打印机和 1 台扫描仪。如果当前进程 A 已获得 1 台打印机，进程 B 已获
4、得了 1第 3 页共 9 页 台扫描仪，此时如果进程 A 申请扫描仪，进程 B 申请打印机，两个进程都 会等着使用已经被另一进行占用的设备，则此时两个进程就进入到了 _ 状态。 A.竞争 B.死锁 C.互斥 D.同步第 4 页共 9 页 13. 一作业 8: 00 到达系统，估计运行时间为 2 小时，若 10: 00 开始执行该作业, 其响应比是（ ） A. 2 B. 1 C. 3 D. 0.5 14. 任何两个并发进程之间 _ 。 A. 一定相互独立 B. 一定存在存在交往 C.可能存在交往 D.都有共享变量 15. 在页式存储管理方案中，采用 _ 实现地址变换。 A.页表 B.段表 C.段
5、表和页表 D.空闲区表 16. 软件工程的出现主要是由于 _ 。 A.程序设计方法学的影响 B.其它工程科学的影响 C.软件危机的出现 D.计算机的发展 17. 结构化分析中最常见的图形工具是 _ 。 A.程序流程图 B.实体关系图 C.数据流图 D.结构图 18. 好的软件结构应该是 _ 。 A.高耦合、高内聚 B.低耦合、高内聚 C.高耦合、低内聚 D.低耦合、低内聚 19. _ 白盒测试法通过分析程序的 来设计测试用例 A.应用范围 B.内部逻辑 C.功能 D.输入数据 20. _ 在软件测试中，逻辑覆盖标准主要用于 _ A.黑盒测试 B.白盒测试 C.灰盒测试 D.软件验收法 是非判断
6、题，请将每题的答案填写在下面的表格 中，正确填T，错误填F，写在其他地方均不得分。 （每题1分，共10分） 1 2 3 4 5 6 7 8 9 10 得分 评阅人 第 5 页共 9 页 1. 数据元素是数据的基本单位，数据项是数据的最小单位。 （） 2. 栈是特殊的线性表，须用一组地址连续的存储单元来存储其元素。 （） 3. 广义表是一种递归的数据结构。（）第 6 页共 9 页 4哈希表的查找效率主要取决于所选择的哈希函数与处理冲突的方法。 （） 5. 冒泡排序算法是一种只能实现升序排序，不能实现降序排序的算法。 （） 6. 原语是一种不可分割的操作。（） 7作业与进程的主要区别是前者是由系统
7、自动生成的， 后者是由用户提交的。（） 8. 能影响中断享有次序的技术是中断优先级和中断屏敝。 9. 操作系统的存储器管理部分负责对进程进行调度。 （ 10. 对临界资源应采取互斥访问方式来实现共享。（） 三、简答题（每题5分，共20分） 1. 何谓进程？请图示具有基本进程状态的状态转移图， 并指出其转移原因。 2. 什么是文件和文件系统？简要说明文件系统的主要功能得分 评阅人 第 7 页共 9 页 3. 什么是软件危机？软件危机表现在那些方面? 4. 瀑布型模型的主要缺点是什么？快速原型模型的基本方法是什么?第 8 页共 9 页 四、综合题 1. 对于下面的每一步，画出栈元素与栈顶指针示意图
8、 (5分) (1) 栈空； (2) 在栈中插入一个元素 A ； (3) 在栈中插入一个元素 X ； (4) 删除栈顶元素； (5) 在栈中插入一个元素 T。 2. 对于下图所示的无向图，列出深度优先和广度优先遍历所得的顶点序列。(5分) 3. 哈希表的地址区间为 0-17,哈希函数为 H(k)二k mod 17。采用线性探测法处理冲 突，试构造关键字序列26,25,72,38,8,18,59的散列表。(5分) 得分 评阅人 第 9 页共 9 页 4. 单链表的删除运算思想为：要在头指针为 head 的单链表中删除第 i 个结点，首 先要计数寻找到第 i 个结点，并使指针 p 指向其前驱结点，即
9、第 i-1 个结点，然 后删除第 i 个结点并释放被删除结点空间。其算法如下，请在划线处填上 C 语 言指令。(5分) int Delete(struct ListNode *head, int i) /在头指针为 head 的单链表中删除第 i 个结点，删除成功返回 1,否则返回 0 struct ListNode *p=head, *s; in t j=1; /寻找第 i 个结点，p 指向其前驱 while(p- next != NULL & &jn ext; _ ; 删除第 i 个结点 free(s); /释放被删结点的内存 return 1; 5.设有一棵二叉树的顺序存储表示为 A C
10、 B D G E F H 试问： (1) 哪个是 D 的双亲结点？ 第 10 页共 9 页 (2) C 的左右孩子是什么？ (3) A 的双亲是什么？ (4) 画出这棵二叉树。 (5) 将其转换为一般树或森林。(20分)第 11 页共 9 页 6.程序题：简单选择排序的基本思想是首先从关键字序列中选出最小的数与第一 个关键字交换，再选出次小的数和第二个关键字交换，如此下去，得到一个由 小到大的序列。假设用变量 min 记下最小值的下标，则简单选择排序的算法如 下，在划线处填入 C 语言指令。 struct Record int key; r5=3,4,1,5,2; selectsort(str
11、uct Record r, int n) int min ,i,j,temp,k; for(i=0;i n-1;i+) _ ; /min 为最小数的下标 for( j=i+1;jn;j+) 依次取出下标 i 后面的每个数 if( _ ) min =j; 记下最小数的下标 if(min != i ) _ ; /暂存大数 /将最小数放到原来大数的位置 ; _ /将大数放到最小数的位置 printf(第2d 趟:,i+1); /打印每趟排序结果*/ for(k=0;k n;k+) prin tf(%3d,rk.key); prin tf(n); void mai n() int n二 5, i; printf(初始序列:); 第 12 页共 9 页 for(i=0; in; i+) prin tf(%3d,ri.key); prin tf(n); selectsort(r,n); / 排序