电子科大工程硕士2003、2004、2005软件工程试题.docVIP

电子科技大学 2003年攻读工程硕士专业学位研究生入学试题 科目名称：软件基础 第一部分 数据结构 项选择题 （每题1分，共10分） 1．在下面有关关键路径的叙述中，正确的是（　　　　　　　） （a）在从源点到汇点之间的路径中，边数最多的路径，称为关键路径 （b）在从源点到汇点之间的路径中，边数最少的路径，称为关键路径 （c）在从源点到汇点之间的路径中，带权路径长度最短的路径，称为关键路径 （d）在从源点到汇点之间的路径中，带权路径长度最长的路径，称为关键路径 2．广义表A=（a,b,(c,d),(e,(f,g))）,则式子Head(Tail(Head(Tail(Tail(A)))))的值为（ ） ???(a) （g）??? (b) (d)??? (c) c??? (d) d 3． 无向图的存储结构有（ ） （a） 逆邻接表　 （b）邻接多重表 （c）十字链表 （d）二叉链表 4．按照二叉树的定义，具有3个结点的二叉树具有的形态个数是（ ） （a）3 （b）4 （c）5 （d）6 5．假设栈足够大，输入序列为（A，B，C，D），不可能得到的输出序列是?（ ） ???（a）（A，B，C，D）?（b）（D，C，B，A）?（c）（A，C，D，B）?（d）（C，A，B，D） 6．能在O（1）时间内访问线性表的第i个元素的结构是（ ） （a）顺序存储结构 （b）单链表 （c）单向循环链表（d）双向链表 7．中序遍历和后序遍历所得序列完全相同的二叉树是（ ） （a）任何二叉树 （b）所有左儿子域均为空 （c）所有右儿子域均为空 （d）儿子域中至少有一个为空 8．线性表顺序存储结构的特点是（ ） （a）逻辑相邻的元素，其物理位置不一定相邻 （b）是可进行随机存取的存储结构 （c）是静态存储结构也可以是动态存储结构 （d）适合进行大量插入和删除 9．在下列排序算法中，不采用比较关键字的方法是（ ） （a）选择排序 （b）快速排序 （c）基数排序 （d）堆排序 10．队列的运算特性是（ ） （a）先进后出 （b）先进先出 （c）一端进出 （d）首进尾出 二、简答题 （每题5分，共20分） 1．对序列33，17，5，4，40，19，100，77，23，45，1，33，17 ，构造二叉排序树。 2．树的路径长度和树的带权路径长度有什么区别？ 3．顶点表示活动的网，即AOV网可解决哪些问题？ 4．什么是网的最小生成树？ 综合应用题（每题10分，共20分） 1．完成下列算法，将v转化为单链表。 PROC exam1(v:sqlisttp; VAR la:linklist); {v是线性表的顺序存储结构，包括数组v.elem和记载长度的v.last, la 为新建链表 的头指针} new(la)； t:=la； {形成带头结点的单链表} FOR i:=1 TO v.last DO [ ； ； ； ] ； ； ENDP; { exam1} 2．说明以下算法的功能；修改该算法，完成输出所有度为1的结点的功能。 PROC exam2 (bt：bitreptr)； {bt为指向二叉树根结点的指针} IF btNIL THEN [ exam2 (bt↑．lchild) ； visite (bt↑．data) ； exam2 (bt↑．rchild) ] ENDP; { exam2} 第二部分 操作系统 单项选择题（在每小题1分，共 15 分） 1．父进程和子进程（ ） ①可以并发执行 ②不能并发执行 ③只能顺序执行 ④只能交叉执行 2．信号量的值（ ）。 ①总是为正 ②总是为0 ③总是为负 ④可以为负整数 3