西南大学 西南大学网络与继续教育学院课程考试试题卷 类别： 网教 (网教/成教) 专业： 2019 年 3 月 课程名称【编号】： 数据结构 【0012】 A卷 大作业 满分：100 分 答案必须做在答题卷上，做在试题卷上不予记分。 一、 选择题（共10题，3分/题，共30分） 1.栈和队列的共同特点是( A )。 (A)只允许在端点处插入和删除元素 (B)都是先进后出 (C)都是先进先出 (D)没有共同点 2. 下面关于线性表的叙述错误的是（ D ）。 (A)线性表采用顺序存储必须占用一片连续的存储空间 (B)线性表采用链式存储不必占用一片连续的存储空间 (C)线性表采用链式存储便于插入和删除操作的实现 (D)线性表采用顺序存储便于插入和删除操作的实现 3. 设有n个待排序的记录关键字，则在堆排序中需要（A ）个辅助记录单元。 2 (A) 1 (B) n (C) nlog2n (D) n 4. 设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ D ）。 (A) n，e (B) e，n (C) 2n，e (D) n，2e 5.下列四种排序中（ A ）的空间复杂度最大。 (A) 快速排序 (B) 冒泡排序 (C) 希尔排序 (D) 堆 6.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（ A）。 21/2 (A) O(n) (B) O(n) (C) O(n) (D) O(1og2n) 7. 设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（ C ）。 (A) head==0 (B) head->next==0 (C) head->next==head (D) head!=0 8. 字符串的长度是指（ C ）。 (A) 串中不同字符的个数 (B) 串中不同字母的个数 (C) 串中所含字符的个数 (D) 串中不同数字的个数 9. 设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（A ）。 (A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3 10. 设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（ B ）。 (A) 10 (B) 19 (C) 28 (D) 55 二、 判断题（共10题，3分/题，共30分） 1． 子串“ABC”在主串“AABCABCD”中的位置为2。(错) 22． 希尔排序算法的时间复杂度为O(n)。( 错) 3． 堆是完全二叉树，完全二叉树不一定是堆。（ 对 ） 4． 入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。( 对 ) 5. 二维数组和多维数组均不是特殊的线性结构。（错 ） 6. 非空的双向循环链表中任何结点的前驱指针均不为空。（对） 7. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（ 对） 8. 完全二叉树中的叶子结点只可能在最后两层中出现。（对） 9. 由树转化成二叉树，该二叉树的右子树不一定为空。（ 错） 10. 带权无向图的最小生成树是唯一的。（错） 三、应用题 1. 设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字 比较次数并计算出查找成功时的平均查找长度。 2. 已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。 答： 西南大学 二、大作业要求 大作业共需要完成22道题： 第1大题必做，满分30分； 第2大题必做，满分30分； 第3大题选作2题，满分40分。 三、大作业提交方式（网络课程由网继院考务办在试题卷和管理系统中填写；面授课程根据任课教师要求提交）： 3. 已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。 答： (8,9,4,3,6,1),10,(12,18,18) (1,6,4,3),8,(9),10,12,(18,18) 1,(3,4,6),8,9,10,12,18,(18) 1,3,(4,6),8,9,10,12,18,18 1,3, 4,6,8,9,10,12,18,18 4. 设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列为(25，31，8，27，13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。 答： 5. 下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。 struct record {int key;datatype others;}; void quickpass(struct record r[], int s, int t, int &i) { int j=t; struct record x=r[s]; i=s; while(i