数据结构练习1.doc

综合练习一、全面复习所要求的课程内容和所做过的作业题（以下是题型示例。要掌握各种结构的基本概念和基本原理，学会各种结构的灵活应用）二、填空1、连通图是指 任意两个结点之间都有路径的图 。 2、对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入元素，在 队头 删除元素。3、线性表中数据元素的个数称为线性表的 长度 。4、删除带头结点的单链表L中的第一个元素结点的语句是 head-next=head-next-next; 。5、有向图G用邻接矩阵A n n 存储，结点i的入度是 矩阵A中第i列权值在0MaxWeight之间的元素个数的和 。6、所有结点的前驱和后继的个数都没有限制的数据结构是 图 结构。7、在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是_0n(n-1)/2_条。8、具有10个结点的无向图边的总数最多为 45 。9、在一个带头结点的单向循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head = = p-next-next 。10、栈顶的位置是随着 出栈 操作而变化的。11、从任何一个结点开始都能成功查找其他结点的单链表是 循环单链 表。12、满二叉树里，分支结点（非树叶结点）个数等于树叶的个数 减1 。13、任何包括n个结点的二叉树的二叉链存储表示中， 2n 个指针中只有 n-1 个用来指示结点的左右孩子，而另外 n+1 个为空指针。14、一个不带权的无向图采用邻接矩阵存储方法，其邻接矩阵是一个_对称_矩阵。15、在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着 一对一 、 一对多 和 多对多 的关系。16、一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有 33 个。17、一棵哈夫曼树有19个结点，则其叶子结点的个数是_10_。18、设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳_4_个元素。19、假设以S和X分别表示进、出栈操作，则对输入序列a、b、c、d、e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为 bceda 。20、无向图中的极大连通子图称为该无向图的 连通分量 。三、选择1、判定一个循环队列QU（最多元素为m）为满队列的条件是 B 。A、QU.front = = QU.rear B、QU.front = = (QU.rear + 1) % mC、QU.front != QU.rear D、QU.front != (QU.rear + 1) % m2、在数据结构中，从逻辑上可以把数据结构分成 C 。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构C、线性结构和非线性结构 D、内部结构和外部结构3、带头结点的单链表head为空的判定条件是 B 。A、head = = NULL B、head - next = = NULLC、head != NULL D、head - next != NULL4、有n个结点的二叉树采用二叉链表存储结构，该链表中共有 D 个指针域用于链接孩子结点。A、n B、2n C、n+1 D、n-15、一个有n个结点的无向图最多有 A 条边。A、n(n-1)/2 B、n(n-1) C、2n D、n6、在一非空二叉树的中序遍历序列中，根结点的左边 D 。A、只有右子树上的部分结点 B、只有左子树上的部分结点C、只有右子树上的所有结点 D、只有左子树上的所有结点7、设数组datam作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front的值为 D 。A、front = front + 1 B、front = ( fron + 1 ) % ( m 1 ) C、front = (front - 1 ) % m D、front = ( front + 1 ) % m8、在含n个结点和e条边的无向图邻接矩阵中，零元素的个数为 D 。A、e B、2e C、n2 - e D、n2 - 2e9、若入栈序列的元素顺序为A、B、C、D、E，判断下列哪一个出栈序列是不可能的(3)A、B、C、D、E B、C、D、E、A E、A、B、C、D D、C、B、A、E10、与链表不相适宜的叙述是 D 。 A、动态存储分配 B、可表示任何类型的数据结构 C、插入和删除操作灵活 D、查找速度快11、若长度为n的线性表采用顺序存储结构，删除它的第i个数据元素需要依次向前移动_A_个数据元素。 A、n - i B、n + i C、n - i - 1 D、n - i + 112、在一个单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行 D 。 A、q - next = p - next ; p - next = q ; B、p - next = q - next ; q = p ;C、q - next = p - next ; p - next = q ; D、p - next = q - next ; q - next = p ;13、链式栈与顺序栈相比，一个比较明显的优点是 B 。 A、插入操作更加方便 B、通常不会出现栈满的情况 C、不会出现栈空的情况 D、删除操作更加方便14、下列有关线性表的叙述中，正确的是 A 。A、线性表中的元素之间是线性关系 B、线性表中任何一个元素有且仅有一个直接前趋C、线性表中至少有一个元素 D、线性表中任何一个元素有且仅有一个直接后继15、以数组Qm存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是 D 。A、( rear qulen ) % m B、( rear - qulen + m ) % m C、( m qulen ) % m D、1 + ( rear + m qulen ) % m16、设结点x和结点y是二叉树T中的任意两个结点，若在前序遍历序列中x在y之前，而在后序遍历序列中x在y之后，则x和y的关系是 C 。A、x是y的左兄弟 B、x是y的右兄弟 C、x是y的祖先 D、x是y的后代17、已知某二叉树的前序遍历序列是ABDC，中序遍历序列是DBAC，它的后序遍历序列是 (2) 。 ABCD DBCA BCAD CABD18、对线性表L适合于使用链式存储结构的是 B 。 A、L中含有大量结点 B、需不断对L进行插入删除 C、需经常修改L中结点值 D、需经常访问L中数据元素19、一棵满二叉树同时又是一棵 C 。 A、无序树 B、哈夫曼树 C、完全二叉树 D、度为2的树20、按照二叉树的定义，具有3个结点的二叉树有 B 种不同形状。A、4 B、5 C、6 D、7四、简要回答下列问题1、在顺序表上如何进行插入、删除操作？在单链表上又如何进行？2、循环单链表有何特点？3、线性表的两种存储结构顺序结构和链式结构各有哪些优缺点？4、为什么队列又称为先进先出表？堆栈？5、为什么在顺序队列中可能会出现假溢出现象？6、分别简述顺序堆栈和链式堆栈元素进栈、出栈的基本步骤。7、分别简述顺序队列和链式队列元素进队、出队的基本步骤。8、为了区分顺序循环队列的队空和队满情况，通常可以采用哪些方法？怎样区分？9、什么是树中结点的度、树的度？10、如果用双亲表示法存储一棵树，如何找到编号为i的结点的双亲和孩子结点？孩子表示法？11、什么叫满二叉树？什么叫完全二叉树？12、将一棵有n个结点的完全二叉树按层次顺序对所有结点从0开始编号，如何求编号为i的结点的双亲、左右孩子？若是一棵一般二叉树情况又怎样？13、简述层序遍历二叉树的算法基本步骤。14、简述非递归的二叉树前序遍历算法的基本步骤。15、如何构造哈夫曼树？16、如果图用邻接矩阵存储怎样判断两点是否为邻接点？用邻接矩阵存储又怎样？17、如果有向图G用邻接矩阵、邻接表存储，分别如何求得结点i的出度和入度？无向图？18、为什么说图的遍历比树的遍历复杂？19、分别简述图的深度和广度优先遍历算法的基本思想。20、从初始结点出发一定能遍历全图吗？为什么？五、应用题1、根据问题写相关的几个语句（如：在一个链式队列中，队首和队尾指针分别为front和rear，现要插入由s所指向的结点，给出应该执行的几步操作。分别对无头结点和有头结点的情况解答。）2、画结构图（如某树的双亲表示法、孩子表示法等对应的结构图。）3、完成相应的操作（如：（1）某二叉树的结点数据采用顺序存储表示如下： I HABGC0123 EF 4567121314D 891011画出该二叉树的图形表示；写出该二叉树的前序、中序和后序遍历结点序列；将此二叉树看作森林的二叉树表示，试将它还原为森林。（2）若对某二叉树前序遍历结点序列为ABDGCEFH，中序遍历的结点访问顺序是DGBAECHF，画出该二叉树的图形表示，画出它的顺序存储结构图、二叉链存储结构图、仿真二叉链存储结构图。（3）根据给定的权集合设计哈夫曼树和哈夫曼编码。（4）对应某图（有向、无向）写出它的邻接链表（邻接矩阵），据此给出由某点起始的深度优先遍历序列和广度优先遍历序列。对应某无向连通网写出它的邻接矩阵（邻接表），给出利用Kruskal算法、Prim算法生成最小生成树的过