本文档如对你有帮助，请帮忙下载支持！
题目28 判断一个循环队列LU（最多元素为m）为空的条件是回答题目29 LU->front==LU->rear。 题干 向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行回答s->next=h;和h=s;操作。（结点的指针域为next） 题目30 从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行x=h-题目31 在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为回答和r=s; r->next=s;（结点的指针域为next） 题目32 在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的操作为回答f=f->next;。 （结点的指针域为next） 题目33 串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是回答字符题目34 。 空串的长度是回答0 空格字符的；空格串的长度是回答。 题目35 设广义表L=((),())，则表头是______________，表尾是______________，L的长度是______________。 则表头是（），表尾是（（）），L的长度是2 题目36 广义表A（（a，b，c），（d，e，f））的表尾为回答((d,e,f))。 题目37 设有n阶对称矩阵A，用数组s进行压缩存储，当i≥j时，A的数组元素aij相应于数组s的数组元素的下标为回答题目38 i(i-1)/2+j。（数组元素的下标从1开始） 对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的_______、_______和_______三项信息。 答案：行下标、列下标和非零元素值 题目39 本文档如对你有帮助，请帮忙下载支持！
循环队列用a[0]，…，a[7]的一维数组存放队列元素，（采用少用一个元素的模式)，设front和rear分别为队头和队尾指针，且front和rear 的值分别为2和7，当前队列中的元素个数是回答5
题目40
。
循环队列的引入，目的是为了克服回答三、问答题（每小题5分，共20分）
题目41 完成 满分5.00
假上溢。
题干
栈、队列和线性表的区别是什么？
答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。
队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。
题目42
设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是多少？
出队序列是e2,e4,e3,e6,e5,e1的过程： （1）e1入栈（栈底到栈顶元素是e1） （2）e2入栈（栈底到栈顶元素是e1，e2） （3）e2出栈（栈底到栈顶元素是e1） （4）e3入栈（栈底到栈顶元素是e1，e3） （5）e4入栈（栈底到栈顶元素是e1，e3，e4） （6）e4出栈（栈底到栈顶元素是e1，e3） （7）e3出栈（栈底到栈顶元素是e1） （8）e5入栈（栈底到栈顶元素是e1，e5） （9）e6入栈（栈底到栈顶元素是e1，e5，e6） （10）e6出栈（栈底到栈顶元素是e1，e5） （11）e5出栈（栈底到栈顶元素是e1） （12）e1出栈（栈底到栈顶元素是空）
栈中最多时有3个元素，所以栈S的容量至少是3。
题目43
有5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先的次序有哪几个？
本文档如对你有帮助，请帮忙下载支持！
从题中可知，要使C第一个且D第二个出栈，应是A入栈，B入栈，C入栈，C出栈，D入栈。之后可以有以下几种情况：
（1）B出栈，A出栈，E入栈，E出栈，输出序列为：CDBAE。 （2）B出栈，E入栈，E出栈，A 出栈，输出序列为CDBEA。 （3）E入栈，E出栈，B出栈，A出栈，输出序列为CDEBA 所以可能的次序有：CDBAE，CDBEA，CDEBA
题目44
简述广义表和线性表的区别和联系。
广义表是线性表的的推广，它也是n（n>0）个元素a1，a2，…，ai，…，an的有限序列，其中ai或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特殊情况，当ai都是原子时，广义表退化成线性表。 形考任务三
一、单项选择题（每小题2分，共32分）
题目1
假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（ ）。 选择一项： A. 17 B. 16 C. 15 D. 47
题目2
二叉树第k层上最多有（ ）个结点。 选择一项： A. 2k-1 B. 2k-1 C. 2k-1 D. 2k
题目3
设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（ ）。 选择一项： A. abedc B. abdec C. debac D. debca
本文档如对你有帮助，请帮忙下载支持！
题目4
将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（ ）。 选择一项： A. 35 B. 33 C. 34 D. 36
题目5
如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（ ）。 选择一项： A. 平衡二叉树 B. 完全二叉树 C. 二叉树 D. 哈夫曼树
题目6
在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ ）。 选择一项： A. 5 B. 4 C. 7 D. 6
题目7
在一棵度具有5层的满二叉树中结点总数为（ ）。 选择一项： A. 31 B. 32 C. 16 D. 33
题目8
利用n个值作为叶结点的权生成的哈夫曼树中共包含有（ ）个结点。 选择一项： A. n+1
本文档如对你有帮助，请帮忙下载支持！
B. 2*n C. n D. 2*n-1
题目9
利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子结点中的最长带权路径长度为（ ）。 选择一项： A. 16 B. 30 C. 12 D. 18
题目10
在一棵树中，（ ）没有前驱结点。 选择一项： A. 叶结点 B. 空结点 C. 树根结点 D. 分支结点
题目11
设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（ ）个结点。 选择一项： A. 2n-1 B. 2n+2 C. 2n+1 D. 2n
题目12
在一个图G中，所有顶点的度数之和等于所有边数之和的（ ）倍。 选择一项： A. 1 B. 1/2 C. 2 D. 4
题目13
邻接表是图的一种（ ）。
数据结构（本）形考作业答案
