天津工业大学大三软件专业算法与数据结构考试试卷及参考答案

天津工业大学算法与数据结构考试试卷及参考答案1一、单项选择题（5）1．下列关于线性表的叙述中正确的是（。、线性表的逻辑顺序与物理顺序总是一致的、线性表的顺序存储表示优于链式存储表示、线性表若采用链式存储表示时所有存储单元的地址可连续或可不连、每种数据结构都应具备三种基本运算：插入、删除和查找答案C2对一个初始为空的栈S执行操作S.Pus（5S.Pus（2（4S.Popx，S.getTop（x）后，x的值应是（、5、、、答案B3.将递归算法转换成对应的非递归算法时，除了单向递归和尾递归的情况外，通常需要使用（）保存中间结果。、链、栈、队列、顺序答案B4.算法的时间复杂度的表示方法是（。、实现算法的程序在指定机器上执行的时、标准程序在机器上的执行时间、基本操作重复次数，即问题规模n的某个函数、与刻画基本操作重复次数的函数同阶无穷大的函数答案D5.在树中，树的度与结点的度之间的关系是（、树的度就是结点的度、树的度为2，结点的度可以是0，1和、结点度中最大值为树的度、树的度与结点的度无答案C6.用链接方式存储的队列，在进行插入运算时、仅修改头指针头、尾指针都要修改、头、尾指针都要修、仅修改尾指针、头、尾指针可能都要修答案D7.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]放位置在676(10)每个元素占一个空间问A[3][3](10)存放在什么位置？(10)表示用10进制表示。、、、、答案C8.最好情况下插入排序的比较次数是（、O(n)、n、n-1、答案C二、多项选择题（5）1.以下程序段的完成的功能是():/*head是指向由data和link两个域的结点构成的单向链表头/P=;e(p=){;P=p->link;}、对链表的遍历、输出了链表中所有数据信息、没有功能，因为只是输出与循环、输出了除表头结之外的所有结点信答案AB2.数据是信息的载体，它有以下几种形式、整数和实型数、字符串、图像和声、信息、磁盘文答案ABC3.一维数组元素的类型可以是():、简单变量，如整数、浮点、复合变量，如结构体，数、只有简单变量、指针变、字符串答案ABD4在算法分析与数据结构中，算法描述方法有、自然语言、框图、类计算机语、数据结构答案ABC5.一棵含有25个结点的完全二叉树的深度是多少、4、、、答案AD二、判断题（5）1.数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行分配。答案：错误2.顺序存储方式只能用于存储线性结构答案：错误3.任意图都是其自身的子图答案：正确4.如果图中有一部分边的权为负值那么用Dijkstra算法求图的最短路径是可的。答案：错误5.线性表中的元素只能是简单类型答案：错误6.线性表是数组答案：错误7.指针就是地址，有人在数组中采用指示下标值的方法实现单向链表。另外的人说这不是链表结构，他的说法对吗？答案：错误8.栈满是数据对象栈的固有操作答案：错误9.在求最短路径的Dijkstra算法和Floyd算法中，Dijkstra算法只能求从点到其他各点的最短路径，而Floyd算法可以求图中两两点之间的最短路径。答案：错误填空题（5）1.栈只能在 插入和删除元素；对于队列只能在 插入和 删元素。答案：栈顶；队尾；队首2.一棵具有257个结点的完全二叉树，它的深度为 答案93.在一个顺序栈中，若栈顶指针等于 ，则为空栈；若栈顶指针等于 则为满栈。答案-1，maxSize-1简答题（20）1.数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链点是什么？答案线性结构的特点是在结构中所有数据成员都处于一个序列中有且仅一个开始成员和一个终端成员并且所有数据成员都最多有一个直接前驱和一直接后继。非线性结构的特点是一个数据成员可能有零个一个或多个直接前驱和直接继。2.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。答案DLR：ABDFJGKCEHILMLDR:BFJDGKACHELILRD：JFKGDBHLMIEC3．如果一棵有n为d（树根所在的层次为1，则给出推导式：1）用深度d表达其结点总数n。2）用结点总数n表达深度d。3若对该树的结点从1开始按中序遍历次序进行编号则树根结点的编号如何d表示？树根结点的左子女结点的编号如何用d表示？右子女结点的编号如何用表示？答案：（1）对于深度为d的满二叉树，结点个数为n=2d-1。（2）深度d=log