浙大城院数据结构期末模拟2

模拟2得分一选择题 (本大题共 15 题，每题 1 分，共 15 分) 1数据在计算机内存中的表示是指 。 A. 数据的存储结构 B. 数据结构 C. 数据的逻辑结构 D. 数据元素之间的关系2. 对线性表，在下列情况下应当采用链表表示的是 。 A. 经常需要随机地存取元素 B. 经常需要进行插入和删除操作 C. 表中元素需要占据一片连续的存储空间 D. 表中的元素个数不变3与单链表相比，双链表的优点之一是 。A插入、删除操作更加简单。 B可随机访问。 C可以省略表头指针或表尾指针 D访问前驱结点更加方便4如果最常用的操作是取第i个结点及前驱，则采用 存储方式最节省时间。A顺序表 B双链表 C单循环链表 D单链表5可以用带表头附加结点的链表表示线性表，也可以用不带表头附加结点的链表表示线性表，前者最主要的好处是 。A可以加快对表的遍历 B. 使空表和非空表的处理统一 C节省存储空间 D. 可以提高存取表元素的速度6. 一个队列的入队序列是1,2,3,4, 则队列的输出序列是 。 A. 4,3,2,1 B. 1,2,3,4C. 1,4,3,2 D. 3,2,4,17栈和队列的共同点是 。A都是先进先出 B都是先进后出C属于非线性结构 D只允许在端点处插入和删除元素8以下不是栈的基本运算的是 。 A删除栈顶元素 B. 删除栈底元素 C判断栈是否为空 D. 将栈置为空栈9一个递归的定义可以用递归过程求解，也可以用非递归过程求解，若从运行时间来看，通常_。A非递归算法比递归算法快B非递归算法比递归算法慢C非递归算法与递归算法时间一样D非递归算法与递归算法时间不一定10. 在一个非空二叉数的中序遍历序列中，根结点的右边 。A. 只有右子树上的所有结点 B.只有右子树上的部分结点C. 只有左子树上的部分结点 D.只有左子树上的所有结点11. 有关树和二叉树的叙述错误的有 。A. 树中的最大度数没有限制，而二叉树结点的最大度数为2；B. 树的结点无左右之分，而二叉树的结点有左右之分；C. 树的每个结点的孩子数为0到多个, 而二叉树每个结点均有两个孩子；D. 树和二叉树均为树形结构。12深度为k的完全二叉树至少有 个结点，至多有 个结点。A. (2k-1, 2k-1) B. (2k-1, 2k) C. (2k-1, 2k) D. (2k-1-1, 2k-1)13. 具有4个顶点的无向完全图，有 条边。 A. 3 B. 6 C. 12 D. 1614一个具有n个顶点的无向图，要确保是一个连通图，至少需要 条边。A. n-1 B. n C. n+1 D. n/215在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。A. 4 B. 2 C. 1 D. 1/2得分二填空题 (本大题共 10 个空，每个空 2 分，共 20 分)1. 数据的逻辑结构被分为集合、 、 、图形结构四种。2. 数据的存储结构主要分为 和 两种。3. 不同形式的时间复杂度O(logn)、O(nlogn)、O(n)、O(n2)、O(2n)，随着n的增长，其增长速度关系为（按从小到大排列） 。4在单链表中，要删除某一指定的结点，必须找到该结点的 。5. 在一个长度为n 的顺序表中删除表中的第i个元素（0in-1）时，需向前移动 元素。6. 已知某无向图的二元组表示为 DS=(K, R), K=a, b, c, d, e，R=r， r=(a,b),(a,c),(a,d),(b,e),(d,e),(c,d),，则顶点b的度为 。7. 已知一棵树用广义表表示为a(b, c(d(e(f), g, h), i), j)，则此树的度为 ，深度为 。 得分三解答题 ( 本大题共 3 题，每题 6 分，共 18 分) 1设有字符串 3*a-b/4 ，试利用栈写出将此次序改变为3a*b4/- 的操作步骤。例如: ABC变BCA，操作步骤为 Push; Push; Pop; Push; Pop; Pop。2已知一棵二叉树的中序遍历序列是abcdjefhgi，前序遍历序列是 eadcbjfghi，请画出这棵二叉树，并写出这棵二叉树的后序遍历序列。3. 设有向图G=(V,E)，V=V1,V2,V3,V4,V5,V6，G的邻接矩阵如下： 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 请画出图G的强连通分量; 请根据邻接矩阵存储结构有向图的广度优先遍历算法，写出从顶点V1出发所得到的顶点序列。得分四程序阅读题 (本大题共 2 题，每题 5 分，共 10 分) 1. 设head为非递减有序的单链表的头指针，单链表中各结点的值依次为 ( 2, 3, 3, 3, 4, 7, 8, 8, 9, 10,10) ，阅读下列算法，写出运行该算法后单链表中各结点的值。void fun1(LNode* &head )LNode *p=head, *q;while ( p != NULL & p- next != NULL ) if ( p-data = p-next-datap-data = p- next -data ) q = p-next;p-next = q-next; temp = p- next; p-next = temp- next;free(q); else p = p-next;2. 阅读下列程序，说明该算法的功能。ElemType fun2(Queue q) ElemType x; Queue temp; InitQueue(temp); while (!QueueEmpty(q) x=OutQueue(q);EnQueue(temp, x); while (!QueueEmpty(temp) x=OutQueue(temp);EnQueue(q, x); return x; 得分五程序填空题 (本大题共 6 个空，每空 2 分，共 12 分) 阅读下列程序，在空白处填入适当的语句，使算法完整。1设有一个顺序表L，其元素为整型数据，下列算法将L中所有小于0的整数放在前半部分，大于0的整数放在后半部分。提示：从L的两端查找，前端找大于0的数据，后端找小于0的数据，然后将两位置的数据交换。顺序表结构定义如下：struct ListElemType *list; /动态存储空间的基地址，指针int size; /线性表当前实际长度int MaxSize; /当前动态数组分配的长度 ;算法如下：void Move(List &L) int i=0, j=L.size-1, temp; while(ij) while (ij & L.listi0) i+; while (i0) ; if ( ) temp=L.listi;L.listi= L.listj; ; 2. 下列算法用于输出邻接表表示的无向图中序号为num的顶点的所有邻接点。邻接表结构定义如下： typedef struct node int adjvex; struct node *next; edgenode;typedef edgenode *adjlistMaxVertexNum;算法如下：void OutAdjVex(adjlist GL, int num) edgenode *p; p = ; while ( ) coutnext; 得分六程序设计题 (本大题共 2 题，第1题 10 分，第2题 15 分，共 25 分) 1. 根据下列函数声明编写求二叉树BT中所有结点数和叶子结点数的递归算法，其值分别由引用参数C1和C2带回，C1和C2的初值均为0。函数声明为：void Count(BTreeNode *BT , int &C1, int &C2)结点结构定义如下：struct BTreeNode ElemType data; B