山东理工大学数据结构期末试题及复习资料.pdf
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 所指结点之后插入一个子链表，子链表第一个结点的地址为 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，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)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是 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,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，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=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，中序序列：H D I M B J E A K F L C G，请画出该二叉树，并简单说明理由。4、（6分）采用哈希函数 H(k)=3*k MOD 13，并用线性探测开放地址法处理冲突，在数列地址空间0.12中对关键字序列 22、41、53、46、30、13、1、67、51，构造哈希表（画示意图）。5、（6 分）下图为无向带权图，用克鲁斯卡尔算法构造其最小生成树，并写出选边的顺序。6、（8 分）对关键字序列30,15,28,20,24,10,12,68,35，（1）构造一棵二叉排序树；（2）对初始序列构造一棵二叉平衡树。四、算法阅读与设计题(本大题共 2 小题，共 20 分)1、（8 分）已知下列程序，Ls 指向带头结点的单链表。Typedefstruct node DataType data;struct node*next;*LinkList;void f30(LinkList Ls)LinkList p,q;q=Ls-next;if(q&q-next)Ls-next=q-next;p=q while(p-next)p=p-next;p-next=q;q-next=NULL;请回答下列问题：4/7(1)当 Ls 指向的链表如下图所示，请画出执行本函数之后的链表的结果。(2)请简述算法的功能。2、（12 分）写出二叉树的二叉链表类型，设计算法求二叉树中度为 1 的结点的数目。（用自然语言给出设计思想，再用代码实现。06-07 学年 第二学期 计算机科学与技术专业 张先伟 一填空（每空 1 分，共 20 分）1.数据的存储结构主要有两类:_存储结构和_存储结构。2.栈与队列都是限定性的数据结构，栈的操作特性是_，队列的操作特性是_。3.在顺序表中插入或删除一个元素，需要平均移动_元素，具体移动的元素的个数与_有关。4.组成串的数据元素只能是_，空串的长度是_。5.广义表（a，（b）的深度是_，表尾是_。6.深度为 K 的完全二叉树至少有_个结点，具有 100 个结点的完全二叉树的深度是_。7.N 个定点的无向连通图至少有_条边，图的遍历有广度优先搜索遍历和_搜索遍历两种方法。8.在 一 个 单 链 表 中 在 指 针 P 所 指 结 点 之 后 插 入 一 个 S 结 点，应 执 行 的 操 作 依 次 是：Snext=_和 Pnext=_。9.影响哈希表查找长度的主要因素是_、_和哈希因子。10.折半查找必须基于_存储的_表进行。二选择（每题 2 分，共 20 分）1一个带头结点的单链表，头指针为 head，判断其是否为空的条件是_。A、head=NULL B、headnext=NULL C、head!=NULL;D、headnext=head 2设栈的输入序列是 1，2，3，4，则_不可能是其输入序列。A、1，2，4，3 B、2，1，3，4 C、4，3，1，2 D、3，2，1，4 3稀疏矩阵的压缩存储不包含下面哪种方式_。A、三元组顺序表 B、行逻辑连接的顺序表 C、邻接多重表 D、十字链表 4有 N 个叶结点的哈夫曼树的结点总数是_。A、不确定 B、2N C、2N+1 D、2N-1 5下列排序方法中，待排记录有序时花费时间反而最多的是_。A、快速排序 B、希尔排序 C、起泡排序 D、堆排序 6下面有关二叉树的说法正确的是_。A、二叉树的度为 2 B、二叉树的度可以小于 2 C、二叉树中至少有一个节点的度数为 2 D、二叉树中任何一个结点的度数都为 2 7堆的形状是一棵_。A、二叉排序树 B、满二叉树 C、完全二叉树 D、平衡二叉树 8、关键路径是 AOE 网中_。A、从源点到汇点的最长路径 B、从源点到汇点的最长回路 C、从源点到汇点的最短路径 D、从源点到汇点的最短回路 9、循环队列是空队列的条件是_。A、Qrear=Qfront B、（Qrear+1）%maxsize=Qfront C、Qrear=0 D、Qfront=0 10、在有向图 G 的拓扑排序序列中，若定点 Vi 在顶点 Vj 之前，则下列情形不可能出现的是_。A、G 中有弧 B、G 中有一条从 Vi 到 Vj 的路径 C、G 中没有弧 D、G 中有一条从 Vj 到 Vi 的路径 三、问答与综合（共 5 个题目，36 分）5/7 1、（6 分）什么是数据的逻辑结构？简述常见的逻辑结构的分类及其特点。2、（8 分）已知二叉树，其中序序列 DBCAFGE，后序序列 DCBGFEA，（1）构造该二叉树，并简单说明理由；（2）将该二叉树转换成相应的树（或森林）。3、（8 分）对于如下的无向网 （1）写出其邻接表；（2）按照 Prime 算法求网的一棵最小生成树（写出过程）。4、（8 分）对下面的二叉排序树：（1）求二叉排序树在等概率查找时平均查找长度；（2）画出插入关键码 16 后的结果；（3）画出对原树删除关键码 40 后的结果。6/7 5、（6 分）初始关键字序列为（30，4，28，58，5，13，90，47，18）（1）写出对其做一趟直接插入排序后的结果；（2）对其初始序列以 30 为枢轴做一次快速排序后的结果。四、算法阅读（共两个题目，12 分）1、阅读下面算法，说明该算法的功能，并分析其时间复杂度（已知 h 是带头结点的单链表的头指针）Void rever(lnode *h)lnode p,q;p=h-next;h-next=null;while(p)q=p;p=p-next;q-next=h-next;h-next=q;/end while /end rever 2、下面是折半查找算法，在_处将算法语句补充完整。int Search(SSTable ST,KeyType key)low=1;high=ST.lengh;while(_)mid=_;if(EQ(key,ST.elemmid.key)return mid;else if(LT(key,ST.elemmid.key)_;else low=mid+1;return 0;五、编写算法（共 1 题，12 分）编写算法，遍历二叉树，求该二叉树叶子节点的个数。int LeafNum(lnode*root)7/7
