软件技术基础试题及答案

1、软件技术基础得分评卷人班级姓名一、填空题（每空1分，共25分）成绩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. 设 D=A , B , C , D, E, R=<A , B> , <C , D> , <D , B> , <C , E>，结构（

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

4、+1;B.p=&a3;C. p=a;D.b=a;设有以下说明语句C. retur n (no de1+ no de2);D. scanf( %d %f ”,nodel);4.线性链表不具有的特点是（A.可随机访问任一个结点B 不必事先估计所需存储空间大小C.插入与删除时不必移动元素D 所需空间与线性表长度成正比5.若让元素1 , 2, 3依次进栈,则出栈次序不可能出现（）种情况。structnodeint a; float b; ;struct nodeno de1, no de2,*p node;则下列语句中正确是（B. pnode.a=10 ;A.node1=node2 ;C. 3

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

6、next; st next =p ; D . qt next =s ; st next =p ;9. 如果以链表作为栈的存储结构，则出栈操作时（）。A 必须判别栈是否满B对栈不作任何判别C.必须判别栈是否空D判别栈元素的类型10. 设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针操作为（ ）。B . p=p->nextD . p->next=p）条边才能确保是一个连通图。B. 7D. 5A. p->next=p->next->nextC. p=p->next->next11. 具有 6 个顶点的无向图至少需要（A. 6C. 4

7、12.对线性表进行二分查找时，要求线性表必须满足（）。A、以顺序方式存储B、以链接方式存储C、以顺序方式存储，且结点按关键字有序排列D、以链接方式存储，且结点按关键字有序排列13.对于进程的描述，下列说法错误的是（）。A 一个进程可以包含若干个程序B. 一个程序可能被多个进程执行C. 一个程序仅对应一个进程D.进程是程序的一次执行过程14.临界区是指并发进程中访问共享变量的）段。A管理信息B. 信息存储C. 数据D. 程序15.若当前进程因时间片用完而让出处理机时，该进程应转变为（）状态。A、执行B 、就绪C、阻塞D、唤醒得分评卷人每题5分，共20 分）1 .软件设计的任务是什么？分为哪几个步

8、骤？每个步骤的任务是什么?2.用简单插入排序法，对关键字值序列为:12，3, 24，45，1，18按从小到大的顺序进行排列,试写出每趟排序的结果。（5分）DBHEAFICG，先序遍历结果为 ABDEHCFIG，请画出该二3.已知一棵二叉树的中序遍历结果为 叉树，并写出实现步骤。（5分）4.给出下面有向图的邻接矩阵。（5 分）得分评卷人四、程序题（共1.程序填空（5分）40分)下面是实现二分查找算法的函数，试将其补充完整。int bin search。nt s ,i nt k,i nt n） int low,high,mid;low=0;while()if(smid =k)prin tf(&qu

9、ot;search ing success! n ”);return(mid);else if(smid <k) elseprintf(” searchi ng 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.设有一个带头结点的单链表，表中各数据元素为无序的正整数，编写下列2 个函数。( 10 分)(1) node *find_m

10、in_node(node *h):找出头指针 h指向的单链表中数据值最小的结点，打印该 结点的数据值，并返回该结点指针； ( 5 分)（ 2）void switch_next_node（node *p） ：若指针 p 指向的结点数据值为奇数，则将该结点与其直接 后继结点的数值交换，若指针 p 指向的结点无后继结点或数据值为偶数，则不做任何操作； （ 5 分）软件技术基础答案一，填空1，逻辑结构；数据操作集合2,链式； 顺序 3, 0 ; 14，队列 ；栈5， 366， 5 ； 7 ； 1023。7， n-i+1； n-i 8， front = （rear + 1） % MAXfron t=re

11、ar9，图10，互斥条件；部分分配条件；不可剥夺条件11， pcb （进程控制块）；后备 12.软件设计；编程实现；软件测试二，选择ADAAC BBDCA DCCDB三，简答题1，（1 ）软件设计的任务是将需求分析阶段获得的需求说明书转换为计算机中可实现的系统，完成系统的结构设计，包括数据结构和程序结构，最好得到软件设计说明书。（2分）（2） 软件设计通常可分为两个步骤：概要设计和详细设计。（1分）（3）概要设计完成软件系统的模块的划分和模块的层次结构以及数据库设计；详细设计完成每个模块的控制流程的设计。（2分）2.,第一趟：3，12，24, 45, 1，18第二趟：3，12，24，45，1，

12、18第三趟：3，12，24，45，1，18第四趟：1，3，12，24，45，18第五趟：1，3，12，18，24，45四，程序题（ 5 分）1，下面是实现二分查找算法的函数，试将其补充完整。high=n-1; low<=high mid=(low+high)/2; low=mid+ high=mid-1; 2，typedef struct int data 10;int num ; listtype ;void dellist(listtype *L ， int x); /* 删除函数声明 */main( ) listtype list=78 ，91，66， 95，35，88，52，10

13、0,*L;/* 初始化顺序表 */int x;L=&list;l->num=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->dataj-1=L->dataj;L->num-;break;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!=NULL)if(p->data<min)t