《2017年上海海事大学信息工程学院821数据结构考研题库.doc》由会员分享，可在线阅读，更多相关《2017年上海海事大学信息工程学院821数据结构考研题库.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年上海海事大学信息工程学院821数据结构考研题库一、填空题1 当两个栈共享一存储区时，栈利用一维数组当栈1空时，【答案】为_，栈2空时， 表示，两栈顶指针为则为_，栈满时为_。【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。2 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n个顶点用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。（1）若是边，则的值等于_，若不是边，则的值是一个比任何边的权，矩阵的对角线元素全为0。（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若【答案】（1） 已包括
2、进生成树，就把矩阵元素A （i ，j ）置成。 边上的权值；都大的数；（2）1; 负值；（3）为负；边（3）算法结束时，相邻矩阵中的元素指出最小生成树的3 无用单元是指_，例_【答案】用户不再使用而系统没有回收的结构和变量； 4 设用希尔排序对数组98，36，-9，0，47，23，1，8，10，7进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_趟，写出第一趟结束后，数组中数据的排列次序_。【答案】3; （10，7，-9，0，47，23，1，8，98，36）5 文件由_组成；记录由_组成。【答案】记录；数据项6 在进行入栈运算时应先判别栈是否_:在进行出栈运算时应先判别栈是否_:
3、当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_分别设在内存空间的两端，这样只有当_时才产生溢出。【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）7 栈是_的线性表，其运算遵循_的原则。；后进先出 【答案】操作受限（或限定仅在表尾进行插入和删除操作）8 阅读下列程序，指出其功能，并写出空格处应填上的语句。 【答案】【解析】本题是在哈希表ht中插入值为的元素，如该元素已在哈希表中，报告出错。9 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_次；当使用
4、监视哨时，若查找失败，则比较关键字的次数为_。【答案】 【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。 10在循环队列中，队列长度为n ，存储位置从0到，【答案】 编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是（ ）。11对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_，在给定值为x 的结点后插入一个新结点的时间复杂度为_。【答案】 【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。 12对单链表中元素按插入方法排序的C 语言描述算法如下，其中L
5、为链表头结点指针。请填充算法中标出的空白处，完成其功能。 【答案】（1）（2）（3）（4）（5）置空链表，然后将原链表结点逐个插入到有序表中当链表尚未到尾，p 为工作指针查P 结点在链表中的插入位置，这时q 是工作指针将P 结点链入链表中是q 的前驱，u 是下个待插入结点的指针二、选择题13计算机硬件能够直接执行的是（ ）。I .机器语言程序A. 仅B. 仅 汇编语言程序硬件描述语言程序C. 仅 D. 【答案】A【解析】机器语言是计算机唯一可以直接执行的语言。汇编语言属于低级语言，但其源程必须要翻译成目标程序成为机器语言程序后才能被直接执行。硬件描述语言是电子系统硬件行为描述、结构描述、数据流
6、描述的语言。 14主机甲与乙之间已建立一个TCP 连接，双方持续有数据传输，且无差错与丢失。若甲收到1个来自乙的TCP 段，该段的序号为1913、确认序号为2046、有效载荷为100字节，则甲立即发送给乙的TCP 段的序号和确认分别是（ ）A.2046、 2012 B.2046、 2013 C.2047、 2012 D.2047、 2012 【答案】B【解析】若甲收到1个来自乙的TCP 段，该段的序号seq=1913、确认序号ack=2046、有效载荷为100字节，则甲立即发送给乙的TCP 段的序号seql=ack=2046和确认序号ackl =seq+100=2013, 答案为B 。15 若X 是后序线索二叉树中的叶结点，且X 存在左兄弟结点Y ，则X 的右线索指向的是（ ）A.X 的父结点B. 以Y 为根的子树的最左下结点 C.X 的左兄弟结点YD. 以Y 为根的子树的最右下结点 【答案】A一、填空题考研试题
