《2017年军事医学科学院总后勤部卫生部药品仪器检验所836计算机应用之数据结构考研强化模拟题.doc》由会员分享，可在线阅读，更多相关《2017年军事医学科学院总后勤部卫生部药品仪器检验所836计算机应用之数据结构考研强化模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年军事医学科学院总后勤部卫生部药品仪器检验所836计算机应用之数据结构考研强化模拟题一、填空题1 在二叉树中，指针p 所指结点为叶结点的条件是_。【答案】 【解析】叶子节点的左右孩子都不存在。2 顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_。【答案】 【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。 3 克鲁斯卡尔算法的时间复杂度为_，它对_图较为适合。【答案】O （eloge ）; 边稀疏 4 对于给定的元素，可以构造出的逻辑结构有_，_，_，_四种。【答案】集合；线性结构；树形结构；图状结构（网状结构）5 实现字符串拷贝的函数strcpy 为：
2、 【答案】 6 当广义表中的每个元素都是原子时，广义表便成了_。【答案】线性表【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。 7 设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_，而栈顶指针值是_。设栈为顺序栈，每个元素占4个字节。【答案】23; 100CH8 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：【答案】33【解析】设存储的元素的行标为i ，列标为j 。若则的地址为若第 2
3、页，共 35 页，）则 的地址为_。的地址为将代入得33。 9 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_则算法，最费时间的是_算法。【答案】起泡；快速，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为（n ） 而快速排序算法需要比较的次数达到最大，时间复杂度为 10线性表用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。【答案】（n 1）/2【解析】删除第一个元素需要移动n i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为11对于一个具有n 个结点的单链表，在已知的结点半p 后插入
4、一个新结点的时间. 复杂度为_，在给定值为x 的结点后插入一个新结点的时间复杂度为_。【答案】 【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。 12用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_和_；若只设尾指针，则出队和入队的时间复杂度分别是_和_。【答案】 【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结
5、点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。 13以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。 【答案】（1）（2）第 3 页，共 35 页链表未到尾就一直进行将当前结点作为头结点后的第一元素结点插入14设有两个算法在同一机器上运行，其执行时闻分别为_。【答案】15【解析】当时，而，时，15设有个结点的完全二叉树顺序存放在向量【答案】 要使前者快于后者，n 至少为中，其下标值最大的分支结点为_。【解析】最大的分支结点是最后一个叶子结点的父结点。二、选择题16下列关于SMTP 协议的叙述中，正确的是（ ）I. 只支持传输7比特ASCII 码内
6、容 II. 支持在邮件服务器之间发送邮件 III. 支持从用户代理向邮件服务器发送邮件 IV. 支持从邮件服务器向用户代理发送邮件 A. 仅 I 、II 和 III B. 仅 I 、II 和 IV C. 仅 I 、III 和 IV D. 仅 II 、III 和 IV 【答案】A【解析】根据下图可知，SMTP 协议支持在邮件服务器之间发送邮件，也支持从用户代理向邮件服务器发送信息。SMTP 协议只支持传输7比特的ASCII 码内容 17假定编译器将赋值语句“x=x+3; ”转换为指令” add xaddt, 3”，其中xaddt 是x 对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB ，且Cache 使用直写（Write Through）方式，则完成该指令功能需要访问主存的次数至少是（ ）。A.0 B.1 C.2 D.3【答案】C【解析】采用页式虚拟存储管理方式时，若页表全部放在内存中，则存取一个数据最少要访第 4 页，共 35 页一、填空题考研试题
