1、第 1 页 ,共 3 页 浙浙 江江 理理 工工 大大 学学 20152015 年硕士学位研究生招生入学考试试题年硕士学位研究生招生入学考试试题 考试科目:软件基础考试科目:软件基础 代码:代码:965 (请考生在答题纸上答题,在此试题纸上答题无效)(请考生在答题纸上答题,在此试题纸上答题无效) 一一 选择题(每题选择题(每题 2 2 分,共分,共 2828 分)分) 1.若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点,则采用( )存储方法最节省时间。 A 单链表 B 带头指针的单循环链表 C 双链表 D 带尾指针的单循环链表。 2.在一个具有 n 个单元的顺序栈中,假定
2、以地址低端(即下标为 0 的单元)作为栈底,以 top作为栈顶指针,当出栈时,top 的变化为( )。 A 不变 B top=0; C top=top-1; D top=top+1; 3. 具有 100 个结点的完全二叉树的叶子结点数为( ) A 100 B 50 C 64 D 4.一个高度为 h 的满二叉树共有 n 个结点,其中有 m 个叶子结点,则有( )成立。 A n=h+m B h+m=2n C m=h-1 D n=2m-1 5 若front 和rear 分别表示链接队列的队头指针与队尾指针, 则向队列中插入一个由p指的新元素的过程是( )。 Arear=p; front=p; Bfr
3、ont=p; rear=p; Crearlink=p; rear=p; Dfrontlink=p; rear=p; 6.下列命题正确的是( )。 A 一个图的邻接矩阵表示是唯一的,邻接表表示也唯一 B 一个图的邻接矩阵表示是唯一的,邻接表表示不唯一 C 一个图的邻接矩阵表示不唯一的,邻接表表示是唯一 D 一个图的邻接矩阵表示不唯一的,邻接表表示也不唯一 7. 有一个按元素值排好序的顺序表(长度大于 2),分别用顺序查找和折半查找与给定值相等的元素,比较次数分别是 s 和 b,在查找成功的情况下,s 和 b 的关系是( ) A s=b B sb C snext) q=L; L=L-next; p
4、=L; while (p-next) p=p-next; p-next=q; q-next=NULL; return (L); 2. 给下图所示的程序流程图设计条件覆盖和判定覆盖测试用例并标明程序执行路径。( (1010 分分) ) (x1) AND (y=0)(x=2) OR (z1)语句段语句段1语句段语句段2开始开始结束结束TTFFabcde(x1) AND (y=0)(x=2) OR (z1)语句段语句段1语句段语句段2开始开始结束结束TTFFabcde 3. 卫星信道的数据率为 1Mbps,取卫星信道的单程传播时延为 0.25 秒,每一个数据帧长都是2000bit。忽略误码率、确认帧长和处理时间。若采用连续 ARQ 协议,发送窗口等于 7。试计算信道利用率?(10 分)分) 五五 设计题(共设计题(共 3030 分)分) 1. 在链式存储结构上建立一棵二叉排序树, 使用 C 语言描述二叉排序树的建立过程和结点插入过程(10 分)分) 。 2. 使用 PAD 图描述在数组 A(1)A(10)中找最大数的算法(10 分)分) 3. 一个单位有 C 类网络地址 200.1.1.0,下面共有 4 个部门,每个部门分别有计算机 72 台,35台,20 台,18 台,即共有 145 台计算机,请给出一种子网掩码分配方案,以及每个部门的有效IP 范围(10 分)分)