软件技术基础系班级成绩一、填空题（每空1分，共25分）1.数据结构作为一门学科，主要研究数据的、存储结构以及三方面容。

2.当对一个线性表经常进行插入或删除操作时，则宜采用存储结构；而经常进行的是访问操作，而很少进行插入或删除操作时，则宜采用存储结构。

3.在线性结构中，首结点有个前驱结点，其余每个结点有且只有个前驱结点。

4.限定在表的一端进行插入，在表的另一端进行删除的线性表称为；限定在表的一端进行插入和删除运算的线性表称为。

5.一个8阶的下三角矩阵B按行优先顺序压缩存储在一维数组中，则数组的大小应设为。

6.按照二叉树的定义，具有3个结点的二叉树形态有种；具有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>}，结构（D，R）描述的数据结构是。

10.系统出现死锁一定是同时保持了，，和环路条件这四个必要条件。

11.操作系统通过记载、跟踪、控制进程的执行，它是进程存在的唯一页脚标志。

作业调度程序是从处于状态的作业中选取一个作业并把它装入主存。

12A.软件生命周期瀑布模型一般可分为问题分析、、、和软件维护五个阶段。

,二、选择题（每小题1分，共10分）1.已知： int x; 下列语句正确的是（）。

A. int *p=&x;B. int *p=x;C. int p=&x;D. int *p=*x;2.int a[ ]={1,2,3,4,5},b[5],*p; 则下列语句中不正确的语句是（）。

A. p=b+1;B.p=&a[3];C. p=a;D.b=a;3.设有以下说明语句struct node{ int a；float b；}；struct node node1,node2,*pnode;则下列语句中正确是（）。

A. node1=node2；B. pnode.a=10；C. return (node1+node2)；D. scanf(“%d %f”,node1);4.线性链表不具有的特点是（）。

A. 可随机访问任一个结点B．不必事先估计所需存储空间大小C. 插入与删除时不必移动元素D．所需空间与线性表长度成正比5.若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。

A．3，2，1 B．2，1，3C．3，1，2 D．1，3，26.有向图的邻接表中，顶点Vi的出度是（）。

A. 依附于Vi的弧数B.Vi链表中的邻接结点个数C. Vi在表结点中出现的次数D. Vi度的一半7.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。

页脚A．空或只有一个结点B．深度等于其结点数C．任一分支结点均无左子树D．任一分支结点均无右子树8.在一个单链表中,若指针p指向某一结点，指针q指向p的前驱结点，要在q与p之间插入一个由s所指的结点，则执行（）。

A．s→next=p→next；p→next=s；B．p→next =s；s→next =q；C．p→next =s→next；s→next =p；D．q→next =s；s→next =p；9.如果以链表作为栈的存储结构，则出栈操作时（）。

A．必须判别栈是否满B．对栈不作任何判别C．必须判别栈是否空D．判别栈元素的类型10.设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针操作为（）。

A. p->next=p->next->next B．p=p->nextC．p=p->next->next D．p->next=p11.具有6个顶点的无向图至少需要（）条边才能确保是一个连通图。

A. 6 B．7C．4 D．512.对线性表进行二分查找时，要求线性表必须满足（）。

A、以顺序方式存储B、以方式存储C、以顺序方式存储，且结点按关键字有序排列D、以方式存储，且结点按关键字有序排列13.对于进程的描述，下列说法错误的是（）。

A．一个进程可以包含若干个程序 B. 一个程序可能被多个进程执行C．一个程序仅对应一个进程 D.进程是程序的一次执行过程14.临界区是指并发进程中访问共享变量的（）段。

A.管理信息B.信息存储C.数据D.程序15.若当前进程因时间片用完而让出处理机时，该进程应转变为（）状态。

A、执行B、就绪C、阻塞D、唤醒页脚二、简答题（每题5分，共20分）1 . 软件设计的任务是什么？分为哪几个步骤？每个步骤的任务是什么？2. 用简单插入排序法，对关键字值序列为：12，3，24，45，1，18按从小到大的顺序进行排列，试写出每趟排序的结果。

（5分）3.已知一棵二叉树的中序遍历结果为DBHEAFICG，先序遍历结果为ABDEHCFIG，请画出该二叉树，并写出实现步骤。

(5分)页脚4. 给出下面有向图的邻接矩阵。

（5分）四、程序题（共40分）1.程序填空（5分）下面是实现二分查找算法的函数，试将其补充完整。

int binsearch(int s[ ],int k,int n){ int low,high,mid;low=0;while(){if(s[mid] ==k){ printf("searching success! \n ");return(mid);}else if(s[mid] <k)else}printf(" 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.设有一个带头结点的单链表，表中各数据元素为无序的正整数，编写下列2个函数。

（10分）（1）node *find_min_node(node *h) ：找出头指针h指向的单链表中数据值最小的结点，打印该结点的数据值，并返回该结点指针；（5分）页脚（2）void switch_next_node(node *p) ：若指针p指向的结点数据值为奇数，则将该结点与其直接后继结点的数值交换，若指针p指向的结点无后继结点或数据值为偶数，则不做任何操作；（5分）页脚软件技术基础答案一，填空1，逻辑结构；数据操作集合 2，链式；顺序 3，0 ；1 4，队列；栈5， 36 6， 5 ； 7 ； 1023 。

7， n-i+1 ； n-i 8， front == (rear + 1) % MAX ， front==rear 9，图 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，18第三趟：[3，12，24，45]，1，18第四趟：[1，3，12，24，45]，18第五趟：[1，3，12，18，24，45]34页脚四，程序题（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，100},*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->data[i]<x){ for (j=i+1; j<l->num; j++)L->data[j-1]=L->data[j];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=p;min=p->data;}p=p->next;}printf("min=%d\n",t->data);return t;}void switch_next_node(node *p){node *q;int t;q=p->next;if(q==NULL || p->data%2==0)return;t=p->data;p->data=q->data;q->data=t;}页脚。