数据结构复习题答案汇总.doc

数据结构复习题（二）填空(答案可靠)1、连通图是指 任意一对结点都是连通的图 。 2、对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入元素，在 队头 删除元素。3、线性表中数据元素的个数称为线性表的 长度 。4、删除带头结点的单链表L中的第一个元素结点的语句是 head-next=head-next-next 。5、有向图G用邻接矩阵A n n 存储，结点i的入度是 矩阵第i列非0元素之和 。6、所有结点的前驱和后继的个数都没有限制的数据结构是 图 结构。7、在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是_m/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，判断下列哪一个出栈序列是不可能的( )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个数据元素需要依次向前移动_D_个数据元素。 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，它的后序遍历序列是 。 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、在顺序表上如何进行插入、删除操作？在单链表上又如何进行？简要叙述操作过程。答：在顺序表L 的第 i ( 0 i size )个位置前插入新数据元素x：后移元素，空出 i 位；插入元素 x ，线性表长度加1。删除顺序表L 中第i ( 0 i size - 1 ) 个数据元素并存放到 x 中：前移元素，压盖 i 位；线性表长度减1。在单链表中插入： q - next = p - next ; p - next = q ;删除： s = p - next ; p - next = p - next - next2、循环单链表有何特点？答：是链表中最后一个结点的指针指向链表的头结点或第一个结点，整个链表形成一个环。删除和插入比较方便，从任何一个结点开始都能成功查找其他结点。3、线性表的两种存储结构顺序结构和链式结构各有哪些优缺点？答：顺序结构优点;是随机存取的结构，读取速度快；空间利用率高；缺点： 数据元素最大个数需预先确定；插入和删除操作时需要移动大量数据，不适合要频繁进行插入和删除操作的问题。链式存储结构优点：插入与删除操作不需移动数据元素； 缺点：结点的指针域需额外占用存储空间； 是一种非随机存储结构4、为什么队列又称为先进先出表？堆栈？答：每次进栈的数据元素都放在原当前栈顶元素之前成为新的栈顶元素，每次退栈的数据元素都是原当前栈顶元素，这样，最后进入堆栈的数据元素总是最先退出堆栈，因此，堆栈也称后进先出表。每次入队列的数据元素都放在原来的队尾之后成为新的队尾元素，每次出队列的元素都是原来的队头元素，这样，先入队列的数据元素总是最先出队列，所以队列也称作先进先出表。5、为什么在顺序队列中可能会出现假溢出现象？答：假溢出是由于队尾指针rear的值和对头指针front的值不能由所定义存储空间的最大值 自动转为所定义存储空间的最小值而产生的。6、分别简述顺序堆栈和链式堆栈元素进栈、出栈的基本步骤。答：顺序堆栈进栈：判断顺序堆栈是否已满，若已满则算法结束，否则执行；把新元素数据存到栈顶位置，并且栈顶指针top自加，算法结束。 顺序堆栈出栈：判断堆栈是否已空，若已空则算法结束；否则栈顶指针自减，（如果要求保留删除元素时）把top指向的元素数据存到某个存储单元，算法结束。 链式堆栈进栈：动态申请一个结点存储空间，再把插入元素数据赋给新结点的数据域；修改新结点的指针域使其指向当前栈顶结点，然后修改栈顶指针使其指向新结点。 链式堆栈出栈：判断堆栈是否已空，若是，则算法结束；否则，修改栈顶指针使其指向栈顶结点的下一个结点。7、分别简述顺序队列和链式队列元素进队、出队的基本步骤。答：顺序队列入队：判断顺序堆栈是否已满，若已满则算法结束；否则新元素数据存到当前队尾指针指向的存储位置，并且队尾指针（rear）按rear=（rear+1）%MaxQueneSize修改。顺序队列出队：判断顺序堆栈是否已空，若已空则算法结束；否则队头指针（front）按front=（front+1）%MaxQueneSize修改。 链式队列入队：动态申请新结点存储空间，把插入数据赋给新结点数据域，初始化新结点的指针域为NULL；若当前队尾指针（rear）不为空，则修改指针rear-next指向新结点，并修改人rear指向新结点，算法结束；否则执行修改指针rear使其指向新结点，并修改队头指针（front）使其指向新结点。链式队列出队： 判断顺序堆栈是否已空，若已空则算法结束；否则修改队头指针（front）使其指向队头元素的下一个元素，若修改后的队头指针为NULL，则把队尾指针也修改为NULL。8、为了区分顺序循环队列的队空和队满情况，通常可以采用哪些方法？怎样区分？答：P74-759、什么是树中结点的度、树的度？答：结点的度：几点所拥有子树的个数；树的度：树中所有结点的度的最大值。10、如果用双亲表示法存储一棵树，如何找到编号为i的结点的双亲和孩子结点？孩子表示法？答：双亲表示法：访问结点编号为i的双亲域（parent），便可得到双亲结点的编号，通过这个编号便可以访问双亲结点。扫描所有结点的双亲域，记录下parent为i的结点的标号j1，j2，js，则结点编号为j1,j2，js，就是i的孩子结点。孩子表示法：扫描所有结点的孩子域，记录下孩子为i的结点的标号j（或指针），则结点编号为j的结点就是i的双亲结点。访问结点编号为i的孩子域，便可得到孩子结点的编号（或指针），通过这个编号（或指针）便可以访问孩子结点。11、什么叫满二叉树？什么叫完全二叉树？答：满二叉树：在一棵二叉树中，若所有分支结点都存在左子树和右子树，并且所有叶结点都在同一层上，这样的二叉树称为满二叉树。若一棵具有 n 个结点的二叉树的结构与满二叉树的前 n 个结点的结构相同，这样的二叉树称为完全二叉树。12、将一棵有n个结点的完全二叉树按层次顺序对所有结点从0开始编号，如何求编号为i的结点的双亲、左右孩子？若是一棵一般二叉树情况又怎样？答：P163性质5如果i0，则序号为 i 的结点的双亲结点的序号为 (i-1)/2；否则， 序号为 i 的结点是根结点，无双亲结点。若2i+1n，则序号为 i 的结点的左孩子结点的序号为2i+1 ；如果2i+1n，则序号为 i 的结点无左孩子。若2i+2n，则序号为 i 的结点的右孩子结点的序号为2i+2 ；如果2i+2n，则序号为 i 的结点无右孩子。13、简述层序遍历二叉树的算法基本步骤。答：P17014、简述非递归的二叉树前序遍历算法的基本步骤。答：P17615、如何构造哈夫曼树？答：p185由给定的 n个权值 w1 , w2 , , wn 构造 n 棵只有根结点的二叉树，从而得到一个二叉树森林F = T1 , T2 , , Tn ；在 F 中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；在集合 F 中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合 F 中； 重复、两步，当 F 中只剩下一棵二叉树时，即得哈夫曼树。16、如果图用邻接矩阵存储怎样判断两点是否为邻接点？用邻接表存储又怎样？答： （参看课件）17、如果有向图G用邻接矩阵、邻接表存储，分别如何求得结点i的出度和入度？无向图？答：邻接矩阵：无向图：各结点的度：第i行（或第i列）中非零元素个数（或之和）就是结点i的度。有向图： 第i行中非零元素个数（或之和）就是结点i的出度； 第i列中非零元素个数（或之和）就是结点i的入度 邻接表：无向图：第i个链表的结点个数为第i个结点的度。有向图：有向图的邻接表中，第 i 个链表的结点个数为第 i 个结点的出度。若求入度，则需扫描整个邻接表，所有链表中dest域为i的个数之和即为入度。18、为什么说图的遍历比树的遍历复杂？答：图的特点是没有首尾之分，所以算法的参数要指定访问第一个结点对图的遍历路径有可能构成回路从而造成死循环，所以算法设计要考虑遍历路径可能出现的死循环问题一个结点可能与若干个结点都是邻接结点，要使一个结点的所有邻接结点按照次序被访问。19、分别简述图的深度和广度优先遍历算法的基本思想。答：深度优先遍历法：递归的深度优先搜索算法的基本思想： 访问指定的起始结点 v0； 访问一个与 v0邻接的结点 w1，再从 w1 出发访问与 w1邻接且未被访问过的结点w2；依次类推，重复上述过程； 当到达一个所有邻接点都被访问过的结点时，则又从最后被访问过的结点开始，依次回退到最近被访问的还有邻接点未被访问过的结点，从该结点出发，重复上述步骤，直到所有被访问过的结点的邻接点都被访问过为止。非递归的广度优先搜索算法的基本思想 访问指定的起始结点 v0； 从 v0出发依次访问 v0 的所有未被访问过的邻接结点 w1 , w2 , , wk ，然后再依次从 w1 , w2 , , wk出发，访问各自的未被访问过的邻接结点； 重复上述步骤，直到所有被访问过的结点的邻接点都被访问过为止。20、从初始结点出发一定能遍历全图吗？为什么？答：不一定，对图的遍历路径可能构成一个回路，从而造成死循环，则不一定能遍历全图。（五）应用题1、根据问题写相关的几个语句（如：在一个链式队列中，队首和队尾指针分别为front和rear，现要插入由s所指向的结点，给出应该执行的几步操作。分别对无头结点和有头结点