《2013山农大数据结构考试题样题》由会员分享，可在线阅读，更多相关《2013山农大数据结构考试题样题（4页珍藏版）》请在金锄头文库上搜索。
1、数据结构样题一、单项选择题：1若线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（） 存储方法最节省时间。A.单链表B.双链表C.带头指针的单循环链表D.带尾指针的单循环链表2设栈S和队列Q的初始状态为空，元素el，e2, e3, e4, e5, e6依次通过栈S, 个元素出栈 后即进入队列Q,若6个元素出队列的顺序是e2, e4, e3, e6, e5, el,则栈S的容量至少应该 是（）。A.6 B.4 C.3 D.23若数组A按行优先方式存储，元素A的起始地址与当A按列优先方式存储时的（）起始地 址一致。A. A85 B. A310 C. A58 D. A494
2、二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子5. 个高度为h的满二叉树共有n个结点，其中m个叶子结点，则有（）成立。A.n=h+m B.h+m=2n C.m=h-1 D.n=2m-16. 设n为网中的结点数，e为网中的边数，以下说法正确的是（）。A. prim算法的时间复杂度为O（n2）,适合于求边稠密的网的最小生成树，kruskal算法的时复杂度 为O（elog2e）,适合求边稀疏的网的最小生成树。B. kruskal算法的时复杂度为O（n2），适合求边稠密的网的最小生成树，prim算法的时
3、间复杂度为 O（elog2e）,适合求边稀疏的网的最小生成树。C. prim算法的时间复杂度为O（n2）,适合求边稀疏的网的最小生成树，kruskal算法的时复杂度为 O（elog2e）,适合于求边稠密的网的最小生成树。D. 以上都不对。7. G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。A.6 B.7 C.8 D.98设散列表表长m=14，散列函数H（k）=k mod 11。表中已有15、38、61、84四个元素，如果用线 形探测法处理冲突，则元素49的存储地址是（）。A.8 B.3C.5D.99. 在下列排序方法中，比较次数与待排序记录的初始状态无关的是()。A.插入排序和快
4、速排序B.归并排序和快速排序C.选择排序和归并排序D.插入排序和归并排序10. 排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是()。A.选择排序B.快速排序C.冒泡排序 D.插入排序二、填空题：1设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用.表示，现前序遍历二叉树，访问的结点的序列为ABD.G.CE.H.F.,则中序遍历二叉树时，访问的结点序 列为 后序遍历二叉树时，访问的结点序列为。2. 从有序表(12, 18, 30，43, 56, 78, 82, 95)中依次折半搜索元素82时，其搜索长度为。3. 如果一个有向图不存在,则该图全部定点可以排成一个
5、拓扑序列。4在有n个结点的线索二叉树中，共有个指针域是线索。5对于键值序列(12,13,11,18,60,15,7,18,25, 100),用筛选法建堆，必须从键值为的结点开始。6.表达式a*(b+c)-d的后缀表达式是。7数组Qn用来表示一个循环队列，front为当前队头的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为。&已知广义表LS= (a,(b,c,d),e),用Head和Tail函数取出LS中原子b的运算是。9.对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是。三、综合应用1. 设有关键码序列20,35,40,15,30,25,38,从空树开始构造平衡二叉树，画出每加入一个新结点时 二叉树的形态。若发生不平衡，指明需做的平衡旋转的类型及平衡旋转的结果。2. 已知数据序列为(12,5,9,20,6,31,24),对该数据序列进行排序，写出直接插入排序、快速排序每 趟的结果。3.关键码集合47, 7, 29, 11, 16, 92, 22, & 3散列函数为H(key)=key mod 11,用拉链法处理冲突,
