《《数据结构》形成性考核册》由会员分享，可在线阅读，更多相关《《数据结构》形成性考核册（49页珍藏版）》请在金锄头文库上搜索。
1、第 1 页 共 50 页广东广播电视大学计算机应用专业省管课程 数据数据结结构构 形成性考核册形成性考核册形成性考核总成绩形成性考核总成绩 学生姓名：学生姓名： 学学 号：号： 所属电大：所属电大： 广东广播电视大学编印广东广播电视大学编印第 2 页 共 50 页形成性考核成形成性考核成绩记录绩记录考核形式考核形式单项成绩单项成绩比例（比例（% %）折合成绩折合成绩作业 115%作业 215%作业 315%作业 415%记分作业作业 515%上机实验 15%小组学习10%形考总成绩形考总成绩: : _ 教师签名教师签名:_:_年年_月月_日日（注：1. 形成性考核至少包括两种不同形式。2. 形
2、成性考核总成绩=折合成绩，折合成绩=单项成绩比例）第 3 页 共 50 页数据结构数据结构作业作业 1 1第一章第一章 绪绪 论论一、 填空题1、 一种抽象数据类型包括_和_两大部分。2、 数据的逻辑结构被分为_、_、_和_四种3、 当需要用一个形参访问对应的实参时，该形参应说明为_。4、 线性结构中元素之间存在_关系，树形结构中元素之间存在_关系，图形结构中元素之间存在_关系。5、 线性表的逻辑顺序与物理存储顺序总是一致的，这种说法是_的(对/不对？)。6、 在图形结构中，每个结点的前驱结点数和后继结点数可以_。7、下面程序段的时间复杂度是_。for (i=0;ix) return 1;el
3、se return 0;（2）int suml(int n)int p=1,s=0;for (int i=1; inext;p-data=p-next-data;p-next=_;delete q;9、 在一个单链表中 p 所指结点之后插入一个 s 所指结点时， 应执行 s-next=_;和 p-next=_;的操作。第 9 页 共 50 页10、 在一个长度为 n 的顺序存储线性表中，删除第 i 个元素(1in+1)时，需要_(从前向后/从后向前?) 依次_（前移/后移？）_个元素。11、 对一个具有 n 个结点的单链表，在已知 p 所指结点后插入一个新结点的时间复杂度是 _ ；在给定值为
4、x 的结点后插入一个新结点的时间复杂度为_。12、 从一个具有 n 个结点的单链表中查找其值为 x 结点时，在查找成功的情况下，需平均比较_个结点。13、 对于一个长度为 n 的顺序存储的线性表，在表头插入元素的时间复杂度为_，在表尾插入元素的时间复杂度为_。14、 用数组 A 存储的单链表，假定 p 为数组 A 中的下标，则 Ap的后继结点（若存在的话）的下标为_。15、 在由数组 A 中元素结点构成的单链表中，在下标为 i 的结点的后面插入一个下标为 j 的结点时，需要进行的操作为_和_。16、 在线性表的单链表中，每个结点包含_和_这两个域。二、 选择题1、在一个单链表 HL 中，若要向
5、表头插入一个由指针 p 指向的结点，则执行_。A. HL=p;p-next=HL;B. p-next=HL;HL=p;C. p-next=HL;p=HL;D. p-next=HL-next;HL-next=p;2、在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 和 p 之间插入 s 结点，则以下操作哪个是正确的（ ）。第 10 页 共 50 页A. s-next=p-next；p-next=s； B. p-next=s-next；s-next=p；C. p-next=s；s-next=q；D. q-next=s；s-next=p；3、在循环双链表的 p 所指结点之后插入
6、 s 所指结点的操作是（ ）。A.p-right=s；s-left=p；p-right-left=s；s-right=p-right；B. p-right=s；p-right-left=s；s-left=p；s-right=p-right；C. s-left=p；s-right=p-right；p-right=s；p-right-left=s； D. s-left=p；s-right=p-right；p-right-left=s；p-right=s；4、若 HL 为一个不带表头结点的循环单链表的表头指针，若有 HL-next= =HL 条件存在，则该循环单链表是（ ）。A.空表 B.只有 1
7、个元素；C.空表或只有一个元素 D.非空表5、若 HL 为一个带表头结点的单链表的表头指针，则该表为空表的条件是（ ）。A.HL=NULL B.HL-next=NULLC.HL-next=HL D.HL!=NULL三、 应用题1、 在下面的每个程序段中，假定线性表 La 的类型为 List，元素类型 ElemType为 int，并假定每个程序段是连续执行的，试写出每个程序段执行后所得到的线性表La。（1）InitList(La);int a =48,26,57,34,62,79;for (i=0; i1）为_。12、对于一棵具有 n 个结点的二叉树，对应的二叉链表中指针总数为_个，其中_个用于
8、指向孩子结点，_个指针空闲。13、假设一棵二叉树中有叶子结点 6 个，那么其双分支结点数为_。14、将树转换为其对应的二叉树形式是将树中每个结点的_结点转换为其左孩子结点，_结点转换为其右孩子结点。15、一棵树中所有结点的度数之和为 8，则树中结点数为_。二、 选择题1、度为 K 的二叉树中第 i 层上至多有_个结点（i1） 。A Ki-1 BKi-1 CKi-1-1 DKi+12、具有 20 个结点的完全二叉树的深度为_。A 3 B 4 C 5 D 63、具有 50 个结点的完全二叉树的深度为_。A 4 B 5 C 6 D 74、在一棵高度为 4 的理想平衡树中，最少含有_个结点。A 7 B
9、8 C 16 D 325、由三个结点 a、b、c 组成的不同结构的二叉树中，共有_种不同的结构。A 4 B 5 C 6 D 7三、 应用题1、 已知一棵二叉树的广义表表示为：A（B（, C （ D， E） ） ） ，写出对其进行前序、中序、后序和层次遍历的结果。第 26 页 共 50 页2、 已知一棵树的广义表表示为： A（B（E，F） ，C（G（K，L） ） ，D（H，I，J（M） ） ） ，写出对其进行先根、后根和层次遍历得到的结点序列。3、 已知一棵树的广义表表示为：A（B（E，F） ，C（G（K，L） ） ，D（H，I，J（M） ） ） ，请将其转换为对应的二叉树表示形式。第 27 页
10、 共 50 页4、 已知一棵度为 m 的树中有 n1个度为 1 的结点，n2个度为 2 的结点，nm个度为 m 的结点，问树中有多少个叶子结点。第 28 页 共 50 页第六章 二叉树的应用一、 填空题1、 在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定_ 该结点的值，右子树上所有结点的值一定_该结点的值。2、 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个_。3、 从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明 _，若元素的值小于根结点的值，则继续向_查找，若元素的值大于根结点的值，则继续向_查找。4、 在一个堆的顺序存储中，若一个元素的下标为 i ，则
11、它的左孩子元素的下标为 _，右孩子元素的下标为_。5、 在一个小根堆中，堆顶结点的值是堆中所有结点中的_，在一个大根堆中，堆顶结点的值是堆中所有结点中的_。6、 当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层_调整，直到被调整到_位置为止。7、 当向一个大根堆插入一个具有最大值的元素时，该元素需要逐层_调整，直到被调整到_位置为止。8、 哈夫曼树是 n 个带权叶子结点构成的所有二叉树中，_最小的二叉树。9、 堆的插入操作是首先把新元素插入到_， 然后再进行调整，使之成为一个新堆。10、 堆的删除操作是删除_元素，并把_元素移到_位置，然后再进行调整，使之成为一个新堆。11、 向二叉搜
12、索树中插入元素的方法是：若二叉树为空，则新元素为二叉树的_结点插入；否则，若待插入的元素小于根结点的值，则将新结点插入到_，若待插入的元素大于根结点的值，则将新结点插入到_。第 29 页 共 50 页二、 应用题1、 给定权值集合 3，7，8，2，6，10，14, 构造相应的 Huffman 树，并计算它的带权外部路径长度。2、 已知一组元素为：（26，18，79，62，12，50，70，22） ，画出按元素排列顺序输入生成的一棵二叉搜索树。第 30 页 共 50 页3、 从空堆开始依次向最小堆中插入线性表（28，12，49，16，34，72，30，25，13）中的每一个元素，要求以线性表的形式给出每插入一个元素后堆的状态。再从堆中依次删除元素二个元素后堆的线性表表示。第 31 页 共 50 页第 32 页 共 50 页数据结构数据结构作业作业 4 4第七章 图一、 填空题1、 在一个图中，所有顶点
