山东理工大学数据结构期末试题及答案.docx

10-11学年第一学期计算机科学与技术专业张先伟、肖爱梅一、填空（每空1分，共20分）1、深度为k的完全二叉树至少有k个结点，具有10个叶结点的二叉树中有9个度为2的结点。2、设数组a[1..5,1..8]的基地址为200，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[4,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，则编号最大的非叶结点的编号为：509、己知有序表为(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)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是CA．快速排序 B．堆排序 C．归并排序 D．直接插入排序2、有五个元素按5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？AA．32154B． 4 5 3 1 2 C． 3 4 5 2 1 D． 2 3 4 1 53、无向图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)}，对该图进行深度优先遍历，得到的顶点序列正确的是DA．a,b,e,c,d,fB．a,c,f,e,b,d C．a,e,b,c,f,dD．a,e,d,f,c,b4、链表不具有的特点是BA．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性表长度成正比5、在一棵三叉树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为C个。A．4B．8 C．6 D．5 6、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是AA． 2和4 B． 1和 5 C． 4和2 D． 5和1 7、若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是BA．起泡排序 B.插入排序 C.选择排序 D.二路归并排序8、对稀疏矩阵进行压缩存储目的是CA．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度9、在下面的程序段中，对x的赋值语句的频度为Dfor ( i=1; i= n; i++)for ( j=1; j= n; j++)x=x+1;A． O(2n) B．O(n) C．O(log2n) D．O(n2) 10、双向链表中，在指针p指向的结点前插入指针q指向的结点的操作是CA． p-prior=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、（