《南京大学网络教育学院“数据结构”课程期末试卷》由会员分享，可在线阅读，更多相关《南京大学网络教育学院“数据结构”课程期末试卷（3页珍藏版）》请在金锄头文库上搜索。
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=Null B. p=L C. p-next=Null D. p-next=L5. 若一棵二叉树的任一非叶结点的度为2，则该二叉树是 （ ）。A. 满二叉树 B. 完全二叉树 C. 哈夫曼树 D. 不确定6. 对关键字序列0，2，4，8，16，32，64，128进行二分查找，则第一个被查找到的关键字是（ ）。A. 0 B. 128 C. 8 D. 167. 已知一个图下图所示，则从顶点a出发进行广度优先遍历，则可能得到的广度优先搜索的结果序列为（ ）。 A.
3、acefbd B. acbdfe C. acbdef D. acdbfe8. 用冒泡排序方法对n个待排序的键值进行排序，则整个排序过程中所需历经的趟数至少是（ ）。A. n B. n-1 C. 1 D. 0二、填空题（每题2分，共16分）1. 评价一个排序算法的优劣，通常用时间复杂度和_这两个指标。2. 数据结构研究的主要内容包括数据的逻辑结构、_、以及对数据及其关系的操作运算。3. 根据数据元素之间的关系，通常有四类基本的逻辑结构：集合、_、树形结构以及图状结构。4. 从一个长度为n的顺序表中删除第i个元素（1in）时，需向前移动_个元素。5. 设线性表用带有头结点的单循环链表L（L为指向其
4、头结点的头指针）表示，则判断该线性表长度为0的条件表达式是_。6. 若一棵二叉树中度为1和度为2的结点个数均是3，则该二叉树叶子结点的个数是_。7. 使用二分查找算法需要满足的条件是_。8. 按关键字的输入序列30，22，42，7，25所生成的二叉排序树中，其左子树上关键字的个数共有_。三、名词解释（每题5分，共20分）1. 队列2. 满二叉树3. 二叉查找树4. 大顶堆四、问答题（每题6分，共30分）1. 设有一个适当大小的栈S，输入栈的序列为A,B,C,D,E。问：（1）能否得到如下输出序列B,C,D,E,A E,A,B,C,D E,D,C,B,A；（2）写出尽可能多的正确的输出序列。2.
5、 某二叉树的先序、中序遍历序列的结果序列分别为EACBDGF、ABCDEFG，现要求画出该二叉树并写出该二叉树后序遍历的结果序列。3. 一个有向图下图所示，分别画出该有向图的邻接表和逆邻接表。 4. 将关键字序列7，8，30，11，18，9，14散列存储到一个散列表中，设该散列表的存储空间是一个下标从0开始、大小（HashSize）为10的一维数组，散列函数为H(key) =(key3) MOD HashSize，处理冲突采用线性探测再散列法。现要求画出所构造的散列表。5. 若采用直接插入排序方法对关键字序列265，301，751，129，937，863，742进行升序排序，写出其每趟排序结束后的关键字序列。五、算法设计题（每题9分，共18分）1. 计算出由指针head指向其头结点的单链表的表长（即单链表中数据元素的个数）。2. 写出复制一棵二叉树的算法。设原二叉树根结点由指针root指向，复制得到的二叉树根结点由指针newroot指向，函数头为：void CopyTree(BTNode *root, BTNode *newroot)。提交截止日期：2019年12月17日注：雷同卷按0分处理！
