《2017年南昌航空大学软件学院817数据结构考研仿真模拟题.doc》由会员分享，可在线阅读，更多相关《2017年南昌航空大学软件学院817数据结构考研仿真模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年南昌航空大学软件学院817数据结构考研仿真模拟题一、填空题1 高度为4的3阶B-树中，最多有_个关键字。【答案】26【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。 2 在基于关键字比较且时间为O （nl g2n ）的排序中，若要求排序是稳定的，则可选用_，则可选用_排序。 排序；若要求就地排序（及辅助空间为0（1）【答案】归并；堆 3 在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_。【答案】 【解析】由于栈底在地址高端，栈中压入一
2、个元素时，栈顶向地址底端移动一个单位，所以4 己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_次查找成功，查找47时_成功，查找100时，需_次才能确定不成功。【答案】2；4；3【解析】二分法查找元素次数列表 查找100是找到115就停止了。 5 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_的排序方法。【答案】稳定 6 一个有2001个结点的完全二叉树的高度是_。【答案】11【解析】完全二叉树的高度 7 实现字符串拷贝的函数strcpy 为： 【答案】 8 如下的算法分别是后序线索二叉树求给定结点n
3、ode 的前驱结点与后继结点的算法，请在算法，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。Prior （node , x ） if（node !=null）If （ （1） ） *x=node-right；else * x-node-left;next （bt , node, x ）/*bt是二叉树的树根*/ （2） ; if （node-rflag）（3）
4、; else do t=*x；;while （*x=node ）; *x=t; 【答案】nodc-rflag=O; *x=ht; *x=nodc-right; prior （t , X ） 9 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n个顶点用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。（1）若是边，则的值等于_，若不是边，则的值是一个比任何边的权，矩阵的对角线元素全为0。（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若【答案】（1） 已包括进生成树，就把矩阵元素A （i ，j ）置成。 边上
5、的权值；都大的数；（2）1; 负值；（3）为负；边中，其下标值最大的分支结点为_。（3）算法结束时，相邻矩阵中的元素指出最小生成树的10设有个结点的完全二叉树顺序存放在向量【答案】 【解析】最大的分支结点是最后一个叶子结点的父结点。二、选择题11主机甲通过1个路由器个路由器（存储转发方式）与主机乙互联，两段链路的数据传输速率均为10Mbps ，主机甲分别采用报文交换和组大小为10kb 的分组交换向主机乙发送1个大小为的报文。若忽略链路传播延迟、分组头开销和拆装时间，则两种交换方式完成该报文传输所需的总时间分别为（ ）A.800ms 1600ms B.801ms 、1600msC.1600ms
6、、800ms D.1600ms 、801ms 【答案】D【解析】不进行分组时，发送一个报文的时延是的时延也是800ms 共计1600ms 。进行分组后发送一个报文的时延是在接收端接收此报文件接收一个报文的时延也是1ms ，但是在发送第二个报文时，第一个报文已经开始接收。共计有800个分组，总时间为801 ms。 12某计算机使用4体交叉存储器，假定在存储器总线上出现的主存地址（十进制）序列为8005, 8006，8007，8008, 8001，8002，8003，8004，8000， 则可能发生发生缓存冲突的地址对是（ ）。A.8004、8008 B.8002、8007 C.8001、8008
7、 D.8000、8004 【答案】D【解析】交叉存储器，又称低位交叉编址，即低位地址为体号，高位地址为体内地址。本题中，主存地址对应的体号分别是：1，2，3，4，1，2，3，4，4。地址为8004和8000都是存取的四号储存器，可能导致8004存储还未完成而又存取8000地址，因此可能发生缓存冲突。 13下列四个序列中，哪一个是堆（ ）？A.75，65，30，15，25，45，20，10 B.75，65，45，10，30，25，20，15 C.75，45，65，30，15，25，20，10 D.75，45，65，10，25，30，20，15 【答案】C【解析】堆的定义： n 个关键字序列且且 称为堆，当且仅当该序列满足如下性质（简称为堆性质）： 小根堆：满足第种情况的堆； 大根堆：满足第种情况的堆。一、填空题考研试题
