软件技术基础试题及答案

1、班级软件技术基础姓名成绩得分评卷人、填空题（每空1分，共25分）第3页，共10页1 .数据结构作为一门学科，主要研究数据的 、存储结构以及 三方面内容。2 .当对一个线性表经常进行插入或删除操作时，则宜采用 存储结构；而经常进 行的是访问操作，而很少进行插入或删除操作时，则宜采用 存储结构。3 .在线性结构中，首结点有 个前驱结点，其余每个结点有且只有 个前驱结点。4 .限定在表的一端进行插入，在表的另一端进行删除的线性表称为 ;限定在表 的一端进行插入和删除运算的线性表称为 。5 . 一个8阶的下三角矩阵B按行优先顺序压缩存储在一维数组中，则数组的大小应设为。6 .按照二叉树的定义，具有3个

2、结点的二叉树形态有 种；具有65个结点的完全二叉树其深度为 ;深度为10的完全二叉树最多有 个结点7 .在长度为n的顺序表的第i个位置上插入一个元素，元素的移动次数为;删除第i个元素时，需要从前向后依次前移 个元素。（1 < i < n+1）8 .顺序存储结构的循环队列中，设front和rear分别为队头和队尾指示器，该队列中能存放的最大元素的个数为 M AX-1,则判断队列为满的条件为 , 而判断队列为空的条件是 。9 . 设口=伊，B, C,D, E, R=<A,B>, <C, D> ,D, B>, <C, E>,结构（D, R）描述的

3、数 据结构是。10 .系统出现死锁一定是同时保持了 , ,和环 路条件这四个必要条件。11 .操作系统通过 记载、跟踪、控制进程的执行，它是进程存在的唯一标志。作业调度程序是从处于状态的作业中选取一个作业并把它装入主存12A。软件生命周期瀑布模型一般可分为问题分析、和软件维护五个阶段。得分评卷人1.二、选择题（每小题分，共10分）.6.7.已知：intx;下列语句正确的是（A.int *p= &x;Co int p= &x;int a 1 = 1 , 2, 3, 4,5,b5 , *p;A.p=b+1 ;Co p=a;设有以下说明语句struct node int

4、 a; floatstruct node node1,node2则下列语句中正确是（A。 node1=node2 ;C. return (node1+node2) ;线性链表不具有的特点是（A。可随机访问任一个结点Co插入与删除时不必移动元素b；)oB.int * p=x;D. int *p= * x;则下列语句中不正确的语句是（BoD.b=a ;*pnode ;Dop= & a3;Bo pnode.a=10 ；scanf( %d%f”, node1 );B.不必事先估计所需存储空间大小D.所需空间与线性表长度成正比若让元素1 , 2,3依次进栈，则出栈次序不可能出现A. 3, 2,1

5、C. 3, 1 , 2有向图的邻接表中，顶点 Vi的出度是（A.依附于Vi的弧数C.Vi在表结点中出现的次数B.2,1, 3D.B。1,3,2）种情况.Vi链表中的邻接结点个数D. Vi度的一半某二叉树的先序序列和后序序列正好相反，则该二叉树一定是）的二叉树。B 深度等于其结点数A 空或只有一个结点C.任一分支结点均无左子树D.任一分支结点均无右子树8. 在一个单链表中 ,若指针 p 指向某一结点，指针q 指向 p 的前驱结点，要在q 与 p 之间插入一个由 s 所指的结点，则执行（） 。A. s-next=p fnext; p - next=s ; B. p next =s ; s-next

6、 =q ;C. p next =sfnext; s next =p ; D . qnext =s ; s-next =p ;9. 如果以链表作为栈的存储结构，则出栈操作时（ ） 。A 必须判别栈是否满B 对栈不作任何判别C.必须判别栈是否空D.判别栈元素的类型10. 设单链表中指针p 指着结点A ，若要删除A 之后的结点（若存在）,则需要修改指针操作为（）.A 。 p->next=p >next- nextC p=p- next next11. 具有 6 个顶点的无向图至少需要（A 。6C 412. 对线性表进行二分查找时，要求线性表必须满足（A、以顺序方式存储C、 以顺序方式存储

7、， 且结点按关键字有序排列排列13. 对于进程的描述,下列说法错误的是（A 一个进程可以包含若干个程序C. 一个程序仅对应一个进程14. 临界区是指并发进程中访问共享变量的A 。管理信息Co数据15. 若当前进程因时间片用完而让出处理机时，该进程应转变为（A 、执行B 、就绪B p=p- nextD p- next=p）条边才能确保是一个连通图。B 7D 5）。B 、以链接方式存储D 、 以链接方式存储,且结点按关键字有序）.B. 一个程序可能被多个进程执行D 。进程是程序的一次执行过程（）段。B 。信息存储D. 程序该进程应转变为（C、阻塞）状态 .D 、唤醒第#页，共10页得分评卷人二、简

8、答题（每题5分，共20分）1 .软件设计的任务是什么？分为哪几个步骤？每个步骤的任务是什么？2。用简单插入排序法，对关键字值序列为: 试写出每趟排序的结果。（5分）12, 3, 24, 45,1, 18按从小到大的顺序进行排列3。已知一棵二叉树的中序遍历结果为二叉树，并写出实现步骤。（5分）DBHEAFICG ,先序遍历结果为 ABDEHCFIG ,请画出该第5页，共10页4.给出下面有向图的邻接矩阵。（5分）得分评卷人四、程序题（共40分）1。程序填空（5分）下面是实现二分查找算法的函数，试将其补充完整。int binsearch（int s ,int k,int n ） int low ,

9、 high,mid;low=0;while() if(smid =k) printf( " searching success!);return(mid );else if(s midk)elseprintf(" searching failed ! n "); return(-1);2 .已知一顺序表L=78 ， 91， 66， 95， 35， 88， 52， 100 ，编写一函数void dellist （listtype *L ，int x）：删除顺序表L中第一个值小于x的元素，若该表中没有小于 x的元素则不作任何操作。（10分）3。设有一个带头结点的单链表

10、，表中各数据元素为无序的正整数，编写下列 2 个函数。 （ 10分）（ 1 ） node find_min_node（node h ） ：找出头指针 h 指向的单链表中数据值最小的结点，打印该结点的数据值，并返回该结点指针； （5 分）第6页，共10页（ 2 ） void switch_next_node （ node *p） ：若指针 p 指向的结点数据值为奇数，则将该结点与其直接后继结点的数值交换,若指针 p 指向的结点无后继结点或数据值为偶数，则不做任何操作； （ 5分）第9页，共10页软件技术基础答案一，填空1,逻辑结构；数据操作集合2,链式；顺序 3, 0 ; 14,队列；栈5, 3

11、66, 5 ; 7 ； 1023。7, n-i+1; ni8 , front =(rear + 1 ) % MAXfront=rear9,图10,互斥条件；部分分配条件；不可剥夺条件11 , pcb （进程控制块）；后备12。软件设计；编程实现 ；软件测试第9页共10页ADAAC BBDCA DCCDB三,简答题1 ,，完成系（1 ）软件设计的任务是将需求分析阶段获得的需求说明书转换为计算机中可实现的系统统的结构设计，包括数据结构和程序结构，最好得到软件设计说明书.（2分）（2）软件设计通常可分为两个步骤：概要设计和详细设计。（1分）（3）概要设计完成软件系统的模块的划分和模块的层次结构以及数

12、据库设计；详细设计完成每个模块的控制流程的设计。（2分）2.,第一趟：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, 455 分）1 下面是实现二分查找算法的函数试将其补充完整。high=n 1 ； low<=high2,typedef struct int data 10; int num ; listtype ；void dellist(listtype *L ， int x) ； main ( ) lis

13、ttype list=78 ， 91， 66， 95， int x;L= list ；lnum=8 ；scanf(“ %d”， &x ) ； dellist ( L,x);void dellist(listtype L,int x )int i,j;for(i=0;i L >num;i+) if(L >datai<x) for (j=i+1; j<l->num; j+)L data j-1=L L- num- ； break;mid= ( low+high ) /2 ； low=mid+ high=mid 1；/* 删除函数声明 */35， 88 ， 52

14、 ， 100 L ；/* 初始化顺序表*/data j 3，typedef struct node int 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 ！ =NUL