算法与数据结构试卷

1、、选择题(10*2%=20%)1.代码段 for (j=1; j=1; k/=2)count+;A、O(n2)B、O(nlogn)C、O(logn)D、O(n)对某个无向图的邻接矩阵来说，下列叙述正确的 A。A、第i行上的非零元素个数和第i列上的非零元素个数一定相等B、矩阵中的非零元素个数等于图中的边数C、第i行与第i列上的非零元素的总数等于顶点vi的度数D、矩阵中非全零行的行数等于图中的顶点数循环双链表中在p所指结点之后插入结点s的操作是 DA、p-next=s; s-prior=p; p-next-prior=s; s-next=p-nextB、p-next=s; p-next-prior

2、=s; s-prior=p; s-next=p-nextC、s-prior=p; s-next=p-next; p-next=s; p-next-prior=sD、s-prior=p; s-next=p-next; p-next-prior=s; p-next=s4个元素a1, a2, a3和a4依次通过一个栈，在a4进栈前，栈的状态如图，栈顶一栈底tA、a4，a3，a2，不可能的出栈顺序是a1B、 a3, a2, a4, a1C、a3，a1，a4，a2 D、a3，a4，a2，a1 TOC o 1-5 h z 下列四种排序方法中，不稳定的方法是D。A、插入排序B、冒泡排序C、归并排序D、选择排

3、序单个结点二叉树的高度为0，所有含有15个结点的二叉树中，最小高度DA、6B、5C、4D、3 在一个具有n个顶点的无向图中，要连通全部顶点至少需要B_条边。A、nB、n-1C、n/2D、n+1 快速排序法的运行效率取决于D。A、要排序的数据量B、要排序的数据中含有相同值的比例C、要排序的数据的局部有序性D、划分过程的对称性二叉树若用顺序存储结构(数组)存放，则下列四种运算中白最容易实现。A、先序遍历二叉树B、判断两个结点是否位于同一层C、层次遍历二叉树D、根据结点的值查找其存储位置 模式串ABBCABABDBABBC的前缀函数为CA、 00001212000121C、 000012120012

4、34B、 10000120001212D、 10000120012345二、填空题(15*2%=30%)1、已知某棵二叉树按中序遍历所得到的结点序列为DCBGEAHFIJK,按后序遍历所得到的 结点序列为DCEGBFHKJIA，该二叉树按前序遍历所得到的结点序列为ABCDGEIHFJK2、一个nxn的下三角矩阵A中的元素a (iNj, 1Wi, jWn)按行存于一个一维数组B1.n (n+1)/2中，对其中的任一元素aij,若在B中的位置为k,则k=j+(i-1)i/23、设一棵完全二叉树具有988个结点，则此完全二叉树有494个叶子结点，有493 个度为2的结点，有 1个结点只有非空左子树，

5、有一0个结点只有非空右子树。4、向一个有127个元素的有序线性表(数组实现)中插入一个随机的新元素并依然保持有序性，平均要移动635个元素。5、设栈S和队列Q的初始状态皆为空，元素a1, a2, a3, a4, a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3, a5, a4, a6, a2, a1则 栈S至少应该能容纳4个元素。6、顺序循环队列中，设队头指针为front ,队尾指针为rear ,队中最多可有MAX个元素， 则元素入队列时队尾指针的变化为(rear+1)%MAX；元素出队列时队头指针的变化为 (front+1)%MAX。若采用少用一个存储单元的

6、方法区分队满与队空问题，则可用 (rear+1)%MAX=front表示队满的判别条件。7、 在输入已经有序的情况下，整个冒泡排序算法需要执行n(n-1)/2次元素比较操作。8、设一个闭散列表的容量为m,用线性探测法解决冲突，要插入一个键值，若插入成功，至多要进行m-1次检测。0 1 09、用邻接矩阵A = 1 0 1表示一张图，如果该图是有向图，共 4条边；若是 0 1 0无向图，则共有_ 2一条边。三、简答题(28%)1、(5分)设下列二叉树是与某森林对应的二叉树，回答下列问题。森林中有几棵树？每一棵树的根结点标号分别是什么？每一棵树中有几个结点？森林中共有几个叶子结点？解答：(1) 3

7、(2 分)A C F (1 分)6 2 3(1 分)6(1 分)2、（6分）用Prim算法（初始顶点集S = 7）构造出下图的一棵最小生成树，请用图示法画出其构造过程。图解：（每图1分）（1）（6分）已知序列17, 31, 13, 11, 20, 35, 25, 8,请将上述序列初始建为一个极小 化堆，并给出输出前两个最小关键字后重建的堆。（要求画出初始建堆和两次调整后堆的示 意图）。图解:（每图2分）4. （5 分）设有一组关键字10 100 32 45 58 126 3 29 200 400 0散列表大小 hashSize=13, 表项下标从0到12,散列函数h（x）采用先将关键码各位数字

8、折叠相加，再用%hashSize将 相加的结果映像到表中的办法，采用二次散列技术（h2i-1（x）=|h（x）+i2|%hashsize, h2i（x）=|h（x）-i2|%hashsize解决冲突，画出相应的闭散列表，并指出每一个产生冲突的关键 码分别产生了多少次冲突。解答：（每项包括位置和冲突次数0.5分）下标关键字冲突次数0580110021001330440005320620037894501012611129012095. （6分）已知如图所示的有向图，请按照Dijkstra算法找出顶点A到所有其它顶点的最短 路径。（要求给出具体迭代过程）解答：(每迭代0.5分，每个顶点距离0.5分

9、)迭代SUDistBDistCDistDDistEDistFDistG初始A-5388881A,CC531010882A,C,BB53108863A,C,B,GG53107864A,C,B,G,EE5397865A,C,B,G,E,FF5397866A,C,B,G,E,F,DD539786A-B： 5AC： 3AB G E D： 9AB G E： 7AB G EF： 8AB G： 6四、程序填空题(共6分)1、(6分)下列算法实现在中序线索二叉树中求结点p的前驱，请在空白处填入正确的语句 或表达式。ThreadedNode *Predecessor( ThreadedNode *p ) Thr

10、eadedNode *q;if ( (1) p-LeftThread )return (p-LeftChild);elseq=p-LeftChild;while ( (2) !q-RightThread)(3)q=q-RightChild ;return(q);/Predecessor五、算法设计题(共16分)1、(8分)二叉搜索树预先假设搜索是基于一个关键字的。如果我们想要执行或者基于关键 字keyl或者基于关键字key2的查找，可以使用一种类似于二叉树的结构一2-d树。但是 在一棵2-d树中，偶数层用keyl进行分叉，奇数层用key2进行分叉(根结点层数为0)。图 中就是一棵2-d树的示例

11、，以名(first name)和姓(last name)作为两个关键字对二战以 后的美国总统进行查找。总统的姓名是按照年代顺序插入的(Truman、Eisenhower、Ford、 Carter、Reagan、Bush、Clinton)。请根据上述描述，编写实现2-d树的插入操作。算法设计思想：从根结点开始，从上往下搜索元素X合适的插入位置，搜索过程中，记录当前结点current 所在层次(根结点层次为0)，若current的层次为奇数时，用key2进行比较，当current-key2x-key2，则搜索current的左子树，否则搜索其右子树；同理，若current 的层次为偶数时，用key

12、1进行比较，当current-key1x-key1,则搜索current的左子树， 否则搜索其右子树。搜索过程中要记录当前结点current的父结点，以便找到一个空指针的 时候，可以直接在这个位置插入新的结点，并将元素x存储在这个新结点中。算法设计题酌情给分2、(8分)现有一个计算机网络和一个双向连接表，每一个连接A-B表示文件可以在计算 机A和B之间传送，如果存在M个连接和N台计算机，设计一个有效的算法帮助判定能否 将一个文件从网络上任意一台计算机发送到任意的另外一台计算机上。要求：算法时间复杂性为O(M+N)算法设计思想：将每一台计算机视为某一张无向图G中的结点，每一个连接A-B表示结 点A和B之间存在一条边。可通过图的连通性判断是否能将一个文件从网络上任意一台计 算机发送到任意的另外一台计算机上。由于这样的一张图具有N个结点和M条边，为了满 足时间复杂性的要求，采用邻接表的方式实现图，并对图进行深度优先搜索也可以初始将每一台计算看