软件技术基础试题及答案.doc

软件技术根底
系 班级 姓名 成绩
得分
评卷人
一、填空题〔每空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，3
C．3，1，2 D．1，3，2
6. 有向图的邻接表中，顶点Vi的出度是〔 〕。
A. 依附于Vi的弧数 i链表中的邻接结点个数
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->next
C．p=p->next->next D．p->next=p
11. 具有6个顶点的无向图至少需要〔 〕条边才能确保是一个连通图。
A. 6 B．7
C．4 D．5
12. 对线性表进展二分查找时，要求线性表必须满足〔 〕。
A、以顺序方式存储 B、以链接方式存储
C、以顺序方式存储，且结点按关键字有序排列 D、以链接方式存储，且结点按关键字有序排列
13. 对于进程的描述，以下说法错误的选项是〔 〕。
A．一个进程可以包含假设干个程序 B. 一个程序可能被多个进程执行
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]
3
4
四，程序题〔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;
第 10 页