杭州电子科技大学2018数据结构期末试卷.docVIP

杭州电子科技大学学生考试卷（ A ）卷 考试课程 数据结构 考试日期 2018 年 月 日 成 绩 课程号 教师号 任课教师姓名 考生姓名 学号（8位） 年级 专业 一．判断题：（每小题2分，共20分） ? 1．链栈的初始化是指开辟足够多的结点，然后置栈顶指针为 NULL。?? （??? ） ? 2．数据的物理结构是指数据在计算机内的实际存储形式。 ???（??? ） ? 3．线性表采用链表存储时，查找第i个元素的时间与i的值无关。 ?? （? ） ? 4．将一棵树转成二叉树，根结点没有左子树。??? （??? ） ? 5．广义表的取表尾运算，其结果通常是个表，但有时也可是个原子。?? （??? ） ? 6．完全二叉树的某结点若无左孩子，则它必是叶结点。 ??? （??? ） ? 7．用邻接矩阵表示图时，矩阵元素的个数与边的条数有关。 ??? （??? ） ? 8．图的深度优先遍历序列和广度优先遍历序列不是唯一的。 ??? （??? ） ? 9．用简单选择排序算法，只需一趟扫描即可选出键值最大（或最小）的元素 。 （??? ） 10. 采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。 （ ） 二．选择题：（每小题2分，共18分） ? 1．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。 A. 13 B. 33 C. 18 D. 40 2．下面关于线性表的叙述中，错误的是哪一个？（ ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 ? 3．循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。 A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 4.对于深度为K的满二叉树(结点编号从1开始，根结点的层数为1)，其第K层上最后1个结点的编号为 (??? )。 ?? A.2K B.2K?1?? C.2K?1?1??? D.2K?1? ? 5．一个有N个顶点的无向图最多有（??? ）条边。 ?? A.N??? B.N*(N?1)??? C.N*(N?1)/2?? D.2*N ? 6．队列具有( )的特点，是操作受限的线性表。 A. 先进先出 B. 先进后出 C.没有特点 7. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。 A. 插入 B. 选择 C. 希尔 D. 二路归并 8. 在计算机内实现递归算法时所需的辅助数据结构是( ) A.栈 B.队列 C.树 D.图 9. 若一个算法的时间复杂度用O(n)表示，其中n的含义是（ ） A．问题规模 B．语句条数 C．循环层数 D．函数数量 三．填空题：（每空2分，共12分） 1．非空的平衡二叉树，树中每个结点的左子树和右子树的深度之差的绝对值不超过________。 2．深度为h的二叉树最少有________个结点。 ?3．对一棵二叉排序树进行______________遍历可以得到一个有序序列。 4. 具有10个顶点的连通图，其最小生成树的边数为______。 5. 在一棵m阶B-树中，每个非叶子结点至多有______ 个关键字。 6. 快速排序平均时间复杂度为O(nlogn) ,最坏情况下时间复杂度是________ 。 四．应用题：（每小题8分，共40分） 1．已知一棵二叉树T的先序序列为：EBADCFHGIKJ，中序序列为：ABCDEFGHIJK。 （1）试画出该二叉树. （2）若该二叉树用孩子兄弟表示