数据结构(答卷).doc

南京航空航天大学数据结构（C语言版）期末考试姓名： 班级： 学号： 一、 选择题（1.5X18=27）1、 数据结构中，从逻辑上可以把数据结构分为：BA 紧凑结构和非紧凑结构 B线性结构和非线性结构 C动态结构和静态结构 D内部结构和外部结构2、 以下说法正确的是：AA数据元素是数据的基本单位B数据结构是带结构的数据项的集合C存储数据时只要考虑数据元素的值。D数据项是数据的可分割的最小单位。3、 在数据结构中，与所使用的计算机无关的是数据的 B结构。A存储 B逻辑C逻辑和存储D物理4、下列结构中，哪个是不属于数据逻辑结构。DA树形结构B图状结构C线性结构D物理结构4、 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是DA冒泡排序B直接插入排序C希尔排序D直接选择排序5、 查找效率最高的二叉排序树是：BA平衡二叉树B所有节点的右子树都为空的二叉排序树C没有左子树的二叉排序树D所有节点的左子树都为空的二叉排序树6、 一个二叉数节点的中序序列为ABCDEFG，后序序列为ABDCAFGE，则其左子树中节点数目为：CA2B3C4D57、 某森林F对应的二叉树为B，他有m个节点，B的根为p，p的右子树的节点个个数为n，森林F中第一棵树的节点的个数为：AAm-n Bm-n-1Cn-1Dm-18、 子串“ture”在主串“datadistructurer”中的位置是：DA5 B8C11D129、 一个有n个节点的二叉链表中，空链域的个数为：BAn Bn+1Cn-1D不确定10下面关于A树和A+树的表述，不正确的是CA A树和A+树都是平衡的多茶树B A树和A+树都可用于文件索引结构C A树和A+树都能有效的支持顺序查找D A树和A+树都能有效支持随即查找11、采用这版查找法查找长度为n的线性表时，每隔元素的平均查找长度为AA O（log2n）B O（n2）C O（nlog2n）D O（n+1）12、无向图中，所有顶点度数之和等于所有边数的C倍。A1/2 B1CCD413、某一数组中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1只10，从首地址SA开始连续存放的存储器内，该数组按行存放，元素85的起始地址为：BASA+141 SA+222C SA+225 D SA+22814、一个队列的入队列序列是2,4,6,8，则队列的输出队列是：DA 8,6,4,2 B2,6,4,8C2,8,6,4 D,2,4,6,815、数据结构中，队列与栈具有相同点是CA都是先进先出 B都是先进后出C只允许在端点处插入和删除元素 D没有相同点16在长度为m的线性表采取顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为AAO(m) B O(0)C O(1)D O(2m)17、深度为4的二叉树至多有B个节点。A8 B7C32D3118下列论述中，正确的是：DI只有一个节点的二叉树的度为0；II深度为k的满二叉树的节点数为2k-1；III二叉树的左右子树可任意交换；IV二叉树的第i层至多有2i-1个节点。AI III IV B I II III CII III IV D I II IV二、 判断题（2X10=20）1、 取线性表的第i个元素的时间同i的大小有关。错2、 具有10个顶点的无向图，边的总数最多为45。对3、 算法的五个重要特性是有穷性、不确定性、可行性、输入和输出。错4、 根据线性表的链式存储结构中每个节点包含的指针个数，可将线性链表分成单链表和双链表。对5、 在所有排列方法中，关键字的次数与记录的初始排列次序无关的冒泡排列。对6、 顺序查找法适合于存储结构为顺序存储或链式存储的线性表。对7、 具有10个叶子节点的二叉树中有8个度为2的节点。错8、 根据哈夫曼树，权值最小的节点离根节点最近，错9、 拓扑排列是按AOE网中的每个节点时间的最早发生时间对节点进行排序的。错10、串是一种特殊的线性表，特殊性在可以顺序存储。错三、 填空题（2X5=10）1、 算数分析的两个主要方面是：空间复杂度和时间复杂度。2、 对任何一课二叉树T，如其终端节点数位n0，度为2的节点数为n2，则n0与n2 之间满足关系为：n0=n2+1 。 3、 设计一个判别表达式中左、右括号是否配对出现的算法，采用 栈 数据结构最好。4、 需要分配较大空间，插入和删除不需要移动元素的线性表，这种存储结构是 静态链表 。5、 有某个集合上的偏序得到该集合上的一个全序，这个操作称之为： 拓扑排序 。四、 简答题(8+3+4=15)1、 写出程序设计中常用的三种错误处理方式，并简述其优缺点。答：1、用EXIT语句终止执行并报告错误；2、以函数的返回值区别正确返回或错误返回；3、设置一个整型变量的函数参数以区别正确返回或某种错误返回。EXIT常用于异常错误处理，它可以强行的中断程序的执行，返回操作系统；以函数的返回值判断正确与否常用于子程序的测试，便于实现程序的局部控制。用整型函数进行错误处理的优点是可以给出错误类型，便于迅速确定错误。2、 简述队列和堆栈这两种数据结构的相同点和不同点。3、 简述动态查找表的特点。答：表结构本身是在查找过程中动态生成的，对于给定之key，若表中存在其关键字等于key 的记录，则查找成功返回，否则插入关键字等于key的记录。五、 综合题1、已知L是无表头节点的单链表，且P节点既不是首元节点，也不是尾元节点，试从下列提供的答案中选择合适局域序