山东理工大学数据结构期末试题及复习资料.pdf





《山东理工大学数据结构期末试题及复习资料.pdf》由会员分享,可在线阅读,更多相关《山东理工大学数据结构期末试题及复习资料.pdf(7页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、1/7 10-11 学年 第一学期 计算机科学与技术专业 张先伟、肖爱梅 一、填空(每空 1 分,共 20 分)1、深度为 k 的完全二叉树至少有 k 个结点,具有 10 个叶结点的二叉树中有 9 个度为 2 的结点。2、设数组 a1.5,1.8的基地址为 200,每个元素占 2 个存储单元,若以行序为主序顺序存储,则元素a4,6的存储地址为 200+(3*8+5)*2=258。3、数据结构中评价算法的两个重要指标是时间复杂度和空间复杂度。4、顺序存储结构是通过元素在存储器中的相对位置表示元素之间的关系的;链式存储结构是通过指示元素存储地址的指针表示元素之间的关系的。5、要在一个单链表中 p
2、所指结点之后插入一个子链表,子链表第一个结点的地址为 s,子链表最后一个结点的地址为 t,则应执行操作:t-next=p-next 和 P-next=s。6、设有向图 G 的存储结构用邻接矩阵 A 来表示,则 A 中第 i 行中所有非零元素个数之和等于顶点 i 的出度,第 i 列中所有非零元素个数之和等于顶点 i 的入度。7、对于表长为n的顺序存储的线性表,访问结点的时间复杂度为 O(1),删除结点的时间复杂度为 O(n)。8、将一棵有 100 个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点编号为 1,则编号最大的非叶结点的编号为:50 9、己知有序表为(12,18
3、,24,35,47,50,62,83,90,115,134),当用折半查找法查找 100 时,需 3 次才能确定不成功。10、Dijkstra 最短路径算法从源点到其余各顶点的最短路径的路径长度按路径长度递增次序依次产生。11、如果 T2 是由树 T1 转换而来的二叉树,那么 T1 中结点的后序遍历就是 T2 中结点的中序遍历。12、广义表 A=(d)则 Head(Tail(Head(Tail(Tail(A)的值为 d。13、设无向连通图的顶点个数为 n,则该图最少有 n-1 条边,最多有 n(n-1)/2 条边。二、选择(每题 2 分,共 20 分)1、若需在 O(nlog2n)的时间内完成
4、对数组的排序,且要求排序是稳定的,则可选择的排序方法是 C A 快速排序 B 堆排序 C 归并排序 D 直接插入排序 2、有五个元素按 5,4,3,2,1 的顺序进栈,问下列哪一个不是合法的出栈序列?A A 3 2 1 5 4 B 4 5 3 1 2 C 3 4 5 2 1 D 2 3 4 1 5 3、无向图 G=(V,E),其中:V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d),对该图进行深度优先遍历,得到的顶点序列正确的是 D Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c
5、,b 4、链表不具有的特点是 B A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性表长度成正比 2/7 5、在一棵三叉树中,度为 3 的结点数为 2 个,度为 2 的结点数为 1 个,度为 1 的结点数为 2 个,则度为 0 的结点数为 C 个。A4 B8 C6 D5 6、若用一个大小为 6 的数组来实现循环队列,且当前 rear 和 front 的值分别为 0 和 3,当从队列中删除一个元素,再加入两个元素后,rear 和 front 的值分别是 A A 2 和 4 B 1 和 5 C 4 和 2 D 5 和 1 7、若数据元素序列 11,12,13
6、,7,8,9,23,4,5 是采用下列排序方法之一得到的第二趟排序后的结果,则该排序算法只能是 B A起泡排序 B.插入排序 C.选择排序 D.二路归并排序 8、对稀疏矩阵进行压缩存储目的是 C A便于进行矩阵运算 B便于输入和输出 C节省存储空间 D降低运算的时间复杂度 9、在下面的程序段中,对 x 的赋值语句的频度为 D for(i=1;i=n;i+)for(j=1;jprior=q;q-next=p;p-prior-next=q;q-prior=q;B p-prior=q;p-prior-next=q;q-next=p;q-prior=p-prior;C q-next=p;q-prior
7、=p-prior;p-prior-next=q;p-prior=q;D q-prior=p-prior;q-next=q;p-prior=q;p-prior=q;三、应用题(40 分)1、(6 分)已知一个无向图 G=(V,E),其中 V=A,B,C,D,E,F,邻接矩阵表示如下所示。请回答下列问题:(1)请画出对应的图 G。(2)画出图 G 的邻接表存储结构。2、(6 分)对于关键字序列(503,87,512,61,908,120,897,275,653,462),建立初始堆(小顶堆)。3/7 3、(8 分)已知一棵二叉树的先序序列:A B D H I M E J C F K L G,中序序


- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 山东 理工大学 数据结构 期末 试题 复习资料

限制150内