数据结构期末考卷13-14.doc

年级：_ 专业：_ 班级：_ 学号：_ 姓名：_.装.订.线诚信应考 考出水平 考出风格浙江大学城市学院2013 2014 学年第 一 学期期末考试试卷 数据结构基础 开课单位： 计算分院 ；考试形式：闭卷；考试时间： 2014 年 1 月 14 日；所需时间： 120 分钟题序一二三四五六总 分得分评卷人得分一选择题 (本大题共 18 题，每题 1 分，共 18 分) 1. 数据的 包括集合、线性结构、树形结构和图形结构四种基本类型。 A. 存储结构 B. 逻辑结构 C. 基本运算 D. 算法描述 2. 中任何两个结点之间都没有逻辑关系。A. 树形结构 B. 集合C. 图形结构 D. 线性结构3. 下面的程序段违反了算法的 原则。 void fun() int x=2; while (!(x%2) x=x*2; printf(“%d”,x); A. 健壮性 B. 确定性 C. 可行性 D. 有穷性4. 算法分析的两个主要方面是 。A. 空间复杂性和时间复杂性B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性5. 用数组表示线性表的优点是 。A. 便于插入和删除操作B. 便于随机存取C. 可以动态地分配存储空间D. 不需要占用一片相邻的存储空间6. 循环链表的主要优点是 。 A. 节约存储空间 B. 已知某个结点的位置后，能够很容易找到它的直接前驱 C. 在进行插入、删除运算时，能更好的保证链表不断开 D. 从表中的任意结点出发都能访问到任何一个结点7. 可以用带表头附加结点的链表表示线性表，也可以用不带头结点的链表表示线性表，前者最主要的好处是 。A. 可以加快对表的遍历B. 节省存储空间C. 使空表和非空表的处理统一D. 可以提高存取表元素的速度8. 在头指针为h且表长大于1的单向循环链表中，指针p指向表中的某个结点，若p-next-next=h，则 。 A. p指向头结点 B. p指向尾结点C. *p的直接后继是头结点 D. *p的直接后继是尾结点9. 线性表中，只有直接前驱而无后继的元素是 。A. 首元素 B. 尾元素C. 中间元素 D. 全部元素10. 以下不是栈的基本运算的是 。A. 删除栈顶元素 B. 删除栈底元素C. 判断栈是否为空 D. 将栈置为空栈11. 若用一个大小为6的数组来实现循环队列，且当前rear和fornt的值分别为1和4。从当前队列中删除一个元素，再加入两个元素后，rear和front的值分别为 。 A. 3和5 B. 2和0C. 0和2 D. 5和312. 最不适合用作链队的链表是_。 A. 只带队头指针的非循环双链表 B. 只带队头指针的循环双链表 C. 只带队尾指针的循环双链表 D. 只带队尾指针的循环单链表13. 最不适合用作栈的链表是 。 A. 只有表头指针没有表尾指针的循环双链表 B. 只有表尾指针没有表头指针的循环双链表 C. 只有表尾指针没有表头指针的循环单链表 D. 只有表头指针没有表尾指针的循环单链表14. 一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程效率 。 A. 高 B. 低 C. 相同 D. 无法确定15. 设n和m为一棵二叉树上的两个结点，中序遍历时，n在m后的条件是 。A. n在m的右子树上 B. n是m祖先C. n在m的左子树上 D. n是m子孙16. 已知一棵普通树的广义表表示为a(b, c(e(h, i, j), f), d(g)，则此树的深度为 。 A. 2 B. 3 C. 4 D. 517. G是一个非连通无向图，共有21条边，则该图至少有_个顶点。 A. 7 B. 8 C. 9 D. 2318. 用邻接表存储图，所用的空间大小_。 A. 与图的顶点数和边数都有关 B. 只与图的边数有关 C. 只与图的顶点数有关 D. 与边数的平方有关得分二填空题 (本大题共 10 题，每题 2 分，共 20 分)1. 数据结构主要研究三方面的内容：数据的逻辑结构、 。2. 计算机算法指的是解决问题的有限运算序列，它必具备输入、输出、有穷性和 这五个特性。3. 下列算法的时间复杂度为 。 int test(int n) int s=1; while(snext; q-next=p; p=q; q=r; h=p; 2已知线性表中的元素按值递增有序排列，阅读下列程序，说明算法的功能： typedef struct ElemType *list; int size; int MaxSize; SeqList; void f2(SeqList &L, ElemType m, ElemType n) int i=0, j; while(iL.size & L.listi=m) i+; j = i; while (jL.size & L.listjn) j+; if (i=j) return; while (jdata=x ) return BT-parent; p=t1(BT-left, x); if (p!=NULL) return p; p=t1( ); if (p!=NULL) return ; return NULL; 2. 下列算法是由无向图的邻接表生成邻接矩阵，请在空白处填入适当的语句，使该算法完整。 typedef struct Node int adjvex; struct Node *next; edgenode;/边结点 typedef edgenode *adjlist MaxVertexNum ; /邻接表存储结构 typedef int adjmatrixMaxVertexNumMaxVertexNum; /邻接矩阵存储结构 void t2(adjlist GL, adjmatrix GA, int n) /由GL建立GA，n是图的顶点数 int i, j; edgenode *p; for ( i = 0 ; i MaxVertexNum; i+ ) /初始化邻接矩阵 for ( j = 0 ; j ; j+ ) GAij =0; for ( i = 0 ; i adjvex ; ; p = p-next; 得分六程序设计题 (本大题共 2 题，每题 10 分，共 20 分) 1. 设链式队列用只带队头指针的循环双向链表表示，如下图所示: front 要求： 写出该链式队列的结点结构定义（即循环双向链表的结点结构定义）； 写出在该循环双链链式队列上进行入队列操作的算法（函数）。2. 设以二叉链表方式存储二叉树BT，要求： 写出