精品文档
软件技术基础
系 班级 姓名 成绩
得分
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={
的数据结构是 。
10. 系统出现死锁一定是同时保持了 ， ， 和
环路条件这四个必要条件。
11. 操作系统通过 记载、跟踪、控制进程的执行，它是进程存在的唯一标志。作业调度程序是从处于 状态的作业中选取一个作业并把它装入主存。
.
评卷人 一、填空题（每空1分，共25分）
精品文档
12A.软件生命周期瀑布模型一般可分为问题分析、 、 、 和软件维护五个阶段。 , 得分 评卷人 二、选择题（每小题1分，共10分）
1. 已知： int x; 下列语句正确的是（ ）。
A. int *p=&x; C. int p=&x;
B. int *p=x;
D. int *p=*x;
2. int a[ ]={1,2,3,4,5},b[5],*p; 则下列语句中不正确的语句是（ ）。
A. p=b+1; C. p=a;
B.p=&a[3]; 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．不必事先估计所需存储空间大小 D．所需空间与线性表长度成正比
C. 插入与删除时不必移动元素
5. 若让元素1，2，3依次进栈，则出栈次序不可能出现（ ）种情况。
A．3，2，1 C．3，1，2
B．2，1，3 D．1，3，2
6. 有向图的邻接表中，顶点Vi的出度是（ ）。
A. 依附于Vi的弧数 C. Vi在表结点中出现的次数
B.Vi链表中的邻接结点个数 D. Vi度的一半
7. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
A．空或只有一个结点
.
B．深度等于其结点数
精品文档
C．任一分支结点均无左子树 D．任一分支结点均无右子树
8. 在一个单链表中,若指针p指向某一结点，指针q指向p的前驱结点，要在q与p之间插入
一个由s所指的结点，则执行（ ）。 A．s→next=p→next；p→next=s； C．p→next =s→next；s→next =p；
B．p→next =s；s→next =q； D．q→next =s；s→next =p；
9. 如果以链表作为栈的存储结构，则出栈操作时（ ）。
A．必须判别栈是否满 C．必须判别栈是否空
B．对栈不作任何判别 D．判别栈元素的类型
10. 设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针操作为
（ ）。
A. p->next=p->next->next C．p=p->next->next
B．p=p->next D．p->next=p
11. 具有6个顶点的无向图至少需要（ ）条边才能确保是一个连通图。
A. 6 C．4
B．7 D．5
12. 对线性表进行二分查找时，要求线性表必须满足（ ）。
A、以顺序方式存储
B、以链接方式存储
C、以顺序方式存储，且结点按关键字有序排列 D、以链接方式存储，且结点按关键字有序排列
13. 对于进程的描述，下列说法错误的是（ ）。
A．一个进程可以包含若干个程序
B. 一个程序可能被多个进程执行
C．一个程序仅对应一个进程 D.进程是程序的一次执行过程 14. 临界区是指并发进程中访问共享变量的（ ）段。
A.管理信息 C.数据
B.信息存储 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(\ return(mid); }
else if(s[mid] else } printf(\ return(-1); } 2.已知一顺序表L={78，91，66，95，35，88，52，100}，编写一函数void dellist(listtype *L，int .
软件技术基础试题及答案
