软件技术基础试题(14A卷答案).doc

苏州市职业大学20142015学年第二学期试卷标准答案及评分标准软件技术基础（集中 A卷 闭卷 笔试）出卷人 陶志福 出卷人所在系 电子信息工程系 使用班级 14专接本 得分评卷人一、填空题（每空1分，共25分）1. 数据结构作为一门学科，主要研究数据的 逻辑结构 、存储结构以及 数据操作集合 三方面内容。2. 当对一个线性表经常进行插入或删除操作时，则宜采用 链式 存储结构；而经常进行的是访问操作，而很少进行插入或删除操作时，则宜采用 顺序 存储结构。3. 在线性结构中，首结点有 0 个前驱结点，其余每个结点有且只有 1 个前驱结点。4. 限定在表的一端进行插入，在表的另一端进行删除的线性表称为 队列 ；限定在表的一端进行插入和删除运算的线性表称为 栈 。5. 一个8阶的下三角矩阵B按行优先顺序压缩存储在一维数组中，则数组的大小应设为 36 。6. 按照二叉树的定义，具有3个结点的二叉树形态有 5 种；具有65个结点的完全二叉树其深度为 7 ; 深度为10的完全二叉树最多有 1023 个结点7. 在长度为n的顺序表的第i个位置上插入一个元素，元素的移动次数为 n-i+1 ；删除第i个元素时，需要从前向后依次前移 n-i 个元素。(1in+1)8. 顺序存储结构的循环队列中，设front 和rear分别为队头和队尾指示器，该队列中能存放的最大元素的个数为MAX-1，则判断队列为满的条件为 front = (rear + 1) % MAX ，而判断队列为空的条件是 front=rear 。9. 设D=A，B，C，D，E，R=，结构（D，R）描述的数据结构是 图 。10. 系统出现死锁一定是同时保持了 互斥条件 ， 部分分配条件 ， 不可剥夺条件 和环路条件这四个必要条件。11. 操作系统通过 pcb（进程控制块） 记载、跟踪、控制进程的执行，它是进程存在的唯一标志。作业调度程序是从处于 后备 状态的作业中选取一个作业并把它装入主存。12A.软件生命周期瀑布模型一般可分为问题分析、 软件设计 、 编程实现 、 软件测试 和软件维护五个阶段。12B.判断char型变量c是否为小写字母的正确表达式为 (c=a)&(c=z) ；设a=12,表达式a+=a-=a*=a的值是 0 ；若已知：int i,x; 则语句for( i=x=0;inext=p-next-next Bp=p-nextCp=p-next-nextDp-next=p11. 具有6个顶点的无向图至少需要（ D ）条边才能确保是一个连通图。A. 6B7C4D512. 对线性表进行二分查找时，要求线性表必须满足（ C ）。 A、以顺序方式存储 B、以链接方式存储C、以顺序方式存储，且结点按关键字有序排列 D、以链接方式存储，且结点按关键字有序排列13. 对于进程的描述，下列说法错误的是（ C ）。A一个进程可以包含若干个程序 B. 一个程序可能被多个进程执行C一个程序仅对应一个进程 D.进程是程序的一次执行过程14. 临界区是指并发进程中访问共享变量的（ D ）段。 A.管理信息 B.信息存储 C.数据 D.程序15. 若当前进程因时间片用完而让出处理机时，该进程应转变为（ B ）状态。A、执行 B、就绪 C、阻塞 D、唤醒得分评卷人二、简答题（ 每题5分，共20分）1A. 软件设计的任务是什么？分为哪几个步骤？每个步骤的任务是什么？ （1）软件设计的任务是将需求分析阶段获得的需求说明书转换为计算机中可实现的系统，完成系统的结构设计，包括数据结构和程序结构，最好得到软件设计说明书。（2分）（2）软件设计通常可分为两个步骤：概要设计和详细设计。（1分）（3）概要设计完成软件系统的模块的划分和模块的层次结构以及数据库设计；详细设计完成每个模块的控制流程的设计。（2分）1B .试写出程序运行结果。(5分)(1) void main() (3分)int n,s;scanf(“%d”,&n);printf(“Output:”);dos=n%10; printf(“%d”,s);n/=10;while(n!=0);输入：123输出结果：321(2) #include stdio.h (2分)void main( ) int a=-1，b=4，m; m=(+a0)|!(b- -0); printf(%d,%d,%d,a,b,m); 结果：0,3,12. 用简单插入排序法，对关键字值序列为：12，3，24，45，1，18按从小到大的顺序进行排列，试写出每趟排序的结果。（5分） 第一趟：3，12，24，45，1，18 第二趟：3，12，24，45，1，18 第三趟：3，12，24，45，1，18 第四趟：1，3，12，24，45，18 第五趟：1，3，12，18，24，453.已知一棵二叉树的中序遍历结果为DBHEAFICG，先序遍历结果为ABDEHCFIG，请画出该二叉树，并写出实现步骤。(5分)4. 给出下面有向图的邻接矩阵。（5分）BADCE 得分评卷人四、程序题（共40分）1. 程序填空（5分）下面是实现二分查找算法的函数，试将其补充完整。int binsearch(int s ,int k,int n) int low,high,mid; low=0; high=n-1; while( low=high ) mid=(low+high)/2; if(smid =k) printf(searching success! n ); return(mid); else if(smid num=8; scanf(“%d”,&x); dellist(L,x); void dellist(listtype *L，int x)int i,j; for(i=0;inum;i+) if(L-dataix) for (j=i+1; jnum; j+) L-dataj-1=L-dataj; L-num-; break;3. 设有一个带头结点的单链表，表中各数据元素为无序的正整数，编写下列2个函数。（10分）（1）node *find_min_node(node *h) ：找出头指针h指向的单链表中数据值最小的结点，打印该结点的数据值，并返回该结点指针；（5分）（2）void switch_next_node(node *p) ：若指针p指向的结点数据值为奇数，则将该结点与其直接后继结点的数值交换，若指针p指向的结点无后继结点或数据值为偶数，则不做任何操作；（5分）typedef struct nodeint data;struct node *next;node;void main() node *head,*p; head=creat( ); /*创建单链表*/ p=find_min_node(head); /*查找数据值最小的结点*/switch_next_node(p); node *find_min_node(node *h)int min;node *p,*t;if(h=NULL)return NULL;p=h-next;t=NULL;min=p-data;while(p!=NULL)if(p-datadata;p=p-nex