1、第 1 页，共 10 页软件技术基础系 班级 姓名 成绩 得分 评卷人一、填空题（每空 1 分，共 25 分）1. 数据结构作为一门学科，主要研究数据的 、存储结构以及 三方面内容。2. 当对一个线性表经常进行插入或删除操作时，则宜采用 存储结构；而经常进行的是访问操作，而很少进行插入或删除操作时，则宜采用 存储结构。3. 在线性结构中，首结点有 个前驱结点，其余每个结点有且只有 个前驱结点。4. 限定在表的一端进行插入，在表的另一端进行删除的线性表称为 ；限定在表的一端进行插入和删除运算的线性表称为 。5. 一个 8 阶的下三角矩阵 B 按行优先顺序压缩存储在一维数组中，则数组的大小应设为
2、。6. 按照二叉树的定义，具有 3 个结点的二叉树形态有 种；具有 65 个结点的完全二叉树其深度为 ; 深度为 10 的完全二叉树最多有 个结点7. 在长度为 n 的顺序表的第 i 个位置上插入一个元素，元素的移动次数为 ；删除第 i 个元素时，需要从前向后依次前移 个元素。(1in+1)8. 顺序存储结构的循环队列中，设 front 和 rear 分别为队头和队尾指示器，该队列中能存放的最大元素的个数为 M AX-1，则判断队列为满的条件为 ，而判断队列为空的条件是 。9. 设 D=A，B，C，D，E ，R=， ，结构（D，R）描述的数据结构是 。10. 系统出现死锁一定是同时保持了 ，
3、， 和环路条件这四个必要条件。第 2 页，共 10 页11. 操作系统通过 记载、跟踪、控制进程的执行，它是进程存在的唯一标志。作业调度程序是从处于 状态的作业中选取一个作业并把它装入主存。12A.软件生命周期瀑布模型一般可分为问题分析、 、 、和软件维护五个阶段。,得分 评卷人二、选择题（每小题 1 分，共 10 分）1. 已知： int x; 下列语句正确的是（ ） 。A. int *p= B. int *p=x;C. int p= D. int *p=*x;2. int a =1,2,3,4,5,b5,*p; 则下列语句中不正确的语句是（ ） 。A. p=b+1; B.p= C. p=a
4、; 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 依次进栈，则出栈次序不可能出现（ ）种情况。A3， 2，1 B2，1，3
5、C3，1，2 D1 ，3，26. 有向图的邻接表中，顶点 Vi 的出度是（ ） 。A. 依附于 Vi 的弧数 B.Vi 链表中的邻接结点个数C. Vi 在表结点中出现的次数 D. Vi 度的一半第 3 页，共 10 页7. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。A空或只有一个结点 B深度等于其结点数C任一分支结点均无左子树 D任一分支结点均无右子树8. 在一个单链表中,若指针 p 指向某一结点，指针 q 指向 p 的前驱结点，要在 q 与 p 之间插入一个由 s 所指的结点，则执行（ ） 。Asnext=pnext；pnext=s； Bpnext =s；snex
6、t =q；Cpnext =snext；snext =p； Dq next =s；snext =p；9. 如果以链表作为栈的存储结构，则出栈操作时（ ） 。A必须判别栈是否满 B对栈不作任何判别C必须判别栈是否空 D判别栈元素的类型10. 设单链表中指针 p 指着结点 A，若要删除 A 之后的结点（若存在） ，则需要修改指针操作为（ ） 。A. p-next=p-next-next Bp=p-nextCp=p-next-next Dp-next=p11. 具有 6 个顶点的无向图至少需要（ ）条边才能确保是一个连通图。A. 6 B7C4 D512. 对线性表进行二分查找时，要求线性表必须满足（
7、） 。 A、以顺序方式存储 B、以链接方式存储C、以顺序方式存储，且结点按关键字有序排列 D、以链接方式存储，且结点按关键字有序排列13. 对于进程的描述，下列说法错误的是（ ） 。A一个进程可以包含若干个程序 B. 一个程序可能被多个进程执行C一个程序仅对应一个进程 D.进程是程序的一次执行过程14. 临界区是指并发进程中访问共享变量的（ ）段。 A.管理信息 B.信息存储 C.数据 D.程序15. 若当前进程因时间片用完而让出处理机时，该进程应转变为（ ）状态。第 4 页，共 10 页A、执行 B、就绪 C、阻塞 D、唤醒得分 评卷人二、简答题（ 每题 5 分，共 20 分）1 . 软件设
8、计的任务是什么？分为哪几个步骤？每个步骤的任务是什么？ 2. 用简单插入排序法，对关键字值序列为：12，3，24， 45，1，18 按从小到大的顺序进行排列，试写出每趟排序的结果。 （5 分）3.已知一棵二叉树的中序遍历结果为 DBHEAFICG，先序遍历结果为 ABDEHCFIG，请画出该二叉树，并写出实现步骤。(5 分 )第 5 页，共 10 页4. 给出下面有向图的邻接矩阵。 （5 分）得分 评卷人四、程序题（共 40 分）1.程序填空（5 分）下面是实现二分查找算法的函数，试将其补充完整。int binsearch(int s ,int k,int n) int low,high,mi
9、d;low=0; while( ) if(smid =k) printf(“searching success! n “);return(mid);else if(smid num=8;scanf(“%d”,dellist(L,x); void dellist(listtype *L，int x)int i,j;for(i=0;inum;i+) if(L-datainum; j+)L-dataj-1=L-dataj;L-num-;break;3，typedef struct node int data;struct node *next;node;void main()第 10 页，共 10
10、页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-datadata;p=p-next;printf(“min=%dn“,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;
