南京大学网络教育学院“数据结构”课程期末试卷

《南京大学网络教育学院“数据结构”课程期末试卷》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、南京大学网络教育学院“数据结构”课程期末试卷提示：答案文档直接在学生平台提交一、单项选择题（每题2分，共16分）1.设某个算法的计算量是问题规模n的函数：T（n）=anc+blog2n+cn+d,则该算法的时间复杂度可表示成（）。A.O（nc）B.O（log2n）C.O（n）D.O（1）2.“能正确地实现预定的功能，满足具体问题的需要”。这种评价算法好坏的因素称为（）。A.正确性B.易读性C.健壮性D.时空性3.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构

2、应该是（）。A.栈B.队列C.树D.图4.在一个非空的单链表L中，指针p所指的结点为最后一个结点的条件是（）。A.p==NullB.p==LC.p->next==NullD.p->next==L5.若一棵二叉树的任一非叶结点的度为2，则该二叉树是（）。A.满二叉树B.完全二叉树C.哈夫曼树D.不确定6.对关键字序列{0，2，4，8，16，32，64，128}进行二分查找，则第一个被查找到的关键字是（）。A.0B.128C.8D.167.已知一个图下图所示，则从顶点a出发进行广度优先遍历，则可能得到的广度优先搜索的结果序列为（）。A.acefbdB.acbdfeC.acb

3、defD.acdbfe8.用冒泡排序方法对n个待排序的键值进行排序，则整个排序过程中所需历经的趟数至少是（）。A.nB.n-1C.1D.0二、填空题（每题2分，共16分）1.评价一个排序算法的优劣，通常用时间复杂度和______________________这两个指标。2.数据结构研究的主要内容包括数据的逻辑结构、______________________、以及对数据及其关系的操作运算。3.根据数据元素之间的关系，通常有四类基本的逻辑结构：集合、_______________、树形结构以及图状结构。4.从一个长度为n的顺序表中删除第i个元素（1£i£n）时，需向前移

4、动___________个元素。5.设线性表用带有头结点的单循环链表L（L为指向其头结点的头指针）表示，则判断该线性表长度为0的条件表达式是_______________。6.若一棵二叉树中度为1和度为2的结点个数均是3，则该二叉树叶子结点的个数是________。7.使用二分查找算法需要满足的条件是_______________。8.按关键字的输入序列{30，22，42，7，25}所生成的二叉排序树中，其左子树上关键字的个数共有______。三、名词解释（每题5分，共20分）1.队列2.满二叉树3.二叉查找树4.大顶堆四、问答题（每题6分，共30分）1.设有一个适当大

5、小的栈S，输入栈的序列为A,B,C,D,E。问：（1）能否得到如下输出序列①B,C,D,E,A②E,A,B,C,D③E,D,C,B,A；（2）写出尽可能多的正确的输出序列。2.某二叉树的先序、中序遍历序列的结果序列分别为EACBDGF、ABCDEFG，现要求画出该二叉树并写出该二叉树后序遍历的结果序列。3.一个有向图下图所示，分别画出该有向图的邻接表和逆邻接表。4.将关键字序列{7，8，30，11，18，9，14}散列存储到一个散列表中，设该散列表的存储空间是一个下标从0开始、大小（HashSize）为10的一维数组，散列函数为H(key)=(key×3)MODHash

6、Size，处理冲突采用线性探测再散列法。现要求画出所构造的散列表。5.若采用直接插入排序方法对关键字序列{265，301，751，129，937，863，742}进行升序排序，写出其每趟排序结束后的关键字序列。五、算法设计题（每题9分，共18分）1.计算出由指针head指向其头结点的单链表的表长（即单链表中数据元素的个数）。2.写出复制一棵二叉树的算法。设原二叉树根结点由指针root指向，复制得到的二叉树根结点由指针newroot指向，函数头为：voidCopyTree(BTNode*root,BTNode*newroot)。提交截止日期：2019年12月17日注：雷同

7、卷按0分处理！