数据结构清华大学模拟试题一答案.doc

清华大学模拟题一一 单项选择题（2分/题）1 一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（）。知道这题的解题思路吗？A.23415 B.54132 C.31245 D.142532 设循环队列中数组的下标范围是1n，其头尾指针分别为f和r，则其元素个数为（）。A.r-f B.r-f+1 C.(r-f) mod n +1 D.(r-f+n) mod n3 二叉树在线索化后，仍不能有效求解的问题是（）。这题是线索化问题，可能你没看过。可以等我去给你讲。A.先序线索二叉树中求先序后继 B. 中序线索二叉树中求中序后继 C.中序线索二叉树中求中序前驱 D. 后序线索二叉树中求后序后继4 求最短路径的FLOYD算法的时间复杂度为（）。（那Djstla的时间复杂度呢？）A.O(n) B.O(n+e) C.O(n2) D.O(n3)5 一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（）。（知道是哪个指针域吗？就是最后一个访问的节点的右指针，因为它没有后继节点。）A.0 B.1 C.2 D.不确定6 数组A1.5,1.6的每个元素占5个单元，将其按行优先顺序存储在起始地址为1000的连续的内存单元中，则元素A5,5的地址为（）。这题可要会哟 A.1140 B.1145 C.1120 D.11257 在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是（）。(要知道为什么，这个我跟你讲过)A.快速排序 B.希尔排序 C.冒泡排序 D.堆排序8 对有18个元素的有序表做折半查找，则查找A3的比较序列的下标依次为（）。（这题的数组下标应该说明一下是A1.18）A.1-2-3 B.9-5-2-3 C.9-5-3 D. 9-4-2-39 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（）。这些题出的都不错！A.堆排序 B.冒泡排序 C.快速排序 D.直接插入排序10 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则做（）型调整以使其平衡。A.LL B.LR C.RL D.RR二 判断题（1分/题）1.（）线性表的长度是线性表所占用的存储空间的大小。2.（）双循环链表中，任意一结点的后继指针均指向其逻辑后继。3.（）在对链队列做出队操作时，不会改变front指针的值。4.（）如果两个串含有相同的字符，则说它们相等。5.（）如果二叉树中某结点的度为1，则说该结点只有一棵子树。6.（）已知一棵树的先序序列和后序序列，一定能构造出该树。7.（）图G的一棵最小代价生成树的代价未必小于G的其它任何一棵生成树的代价。8.（）图G的拓扑序列唯一，则其弧数必为n-1（其中n为顶点数）。9.（）对一个堆按层次遍历，不一定能得到一个有序序列。10.（）直接选择排序算法满足：其时间复杂度不受数据的初始特性影响，为O(n2)。 三 填空题（2分/空）1已知完全二叉树的第8层有8个结点，则其叶子结点数是（68）。2将下三角矩阵A1.8,1.8的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A7,5的地址是（1100）。3有n个顶点的强连通有向图G至少有（n）条弧。4有n个结点并且其高度为n的二叉树的数目是（2n-1）。5高度为8的平衡二叉树的结点数至少是（54）。63个结点可构成（3）棵不同形态的树。7对下图所示的网，执行prim算法可得到最小生成树，试在下表的空白处填上适当的内容，以说明该算法的执行过程。 顶点 1 3 4 U V51 (U,V) (2,1) (2,3) (2,4) 2 1,3,41 代价 4 25 (U,V) (4,1) (2,3) 2,4 1,343 代价 5 4 (U,V) (3,1) 2,4,3 124 代价 1 2 (U,V) 2,4,3,1 代价 8设散列表函数为H(key)，用拉链法解决冲突，H的值域为0,.,n-1，构造的散列表类型如下： TYPE link=node; node=RECORD key:keytype; next:link; . END; openhash=array0.n-1 of link; 请在下列算法划线处填上适当内容，以完成查找键值等于K的结点，若查找成功，返回该结点的指针，否则返回空指针。 FUNC research(K:keytype; HP:openhash):link; i:=H(K); SUC:=false; p:=HPi ; while (pnil) and not(SUC) do if p.keyK then p:=p.next else SUC:=true; return(p) ENDC; researsh四 应用题（5分/题）1 对下面两棵二叉树，分别画出它们的顺序存储结构。 A A B C B C D E F G D E F I J K I J 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11 A B C D E F G I J K A B C D E F I J 2 设图G=(V,E),V=1,2,3,4,5,6, E=,。请写出图G中顶点的所有拓扑序列。521 1-2-3-6-5-4463 3-2-6-5-4 6-2-5-43 对下面3阶B-树依次执行下列操作，画出每步的操作结果。 100插入300 200 50（1） 插入70（2） 插入3026015060 80 10 40（3） 删除150 100（1） 200 50260 30015060 80 10 40 100 （2）260 300 200 50 708015060 10 40 50 100 （3）70 200 30260 30040801506010 50 100 （4） 260 30703008020060104064 求出下面AOE网中的关键路径，要求标明每个顶点的最早和最迟发生时间，并画出关键路径。726334723544534554545108312226108316462524627945794 1 2 3 4 5 6 7 8 9 10 e 0 4 5 4 10 11 13 14 13 18 l 0 8 5 4 12 11 15 16 13 18五 算法设计题（10分/题）1 设计算法将一个带头结点的单循环链表A分解为两个具有相同结构的链表B和C，其中B表中结点为A表中值为奇数的结点，而C表中结点为A表中值为偶数的结点（要求利用原表结点）。算法思想：B表头结点利用A表头结点；为C表产生一个头结点。从A的首元结点检查每个结点应插入B表还是C表，从而从A表取下，做响应的插入操作。设节点定义如下：struct nodeint key; struct node* next;则算法如下：void give_b_c() struct node*B, *C; B=A; /现在B和A是一回事，即将奇数留下，偶数/拿出来放到C中 C=(struct node*)malloc(sizeof(struct node); p1=B; p2=p1-next; q=C; /p1 p2是B上的工作指针 q是C上的工作指针 while (p2!=B) if (p2-key mod 2=0) /偶数则放入C中 p1-next=p2-next; q-next=p2; q=p2; p2=p1-next else /奇数则不变 p1=p2; p2=p1-next; q-next=C;2 设计算法判断无向图G是否是连通的，若连通则返回true，否则返回false。可以使用以下几个函数调用：firstadj(G,v)返回图G中顶点v的第一个邻接点，若不存在返回0nextadj(G,v,w)返回图G中顶点v的邻接点中处于w之后的邻接点，若不存在返回0nodes(G)返回图G中的顶点数算法思想：从某个顶点出发深度/广度遍历。设辅助数组visitedmax则算法如下：bool total_search_dfs(Graph G) /这里bool的定义缺省了，这是算法与程序的差别for (i=0; inode(G);i+) visitedi=false; son_search_dfs(G,0); /从第一个元素开始深度遍历，当然，从任何一个都行 for (i=0;iadjvex=false son_search_dfs(G,p-adjvex); p=nextadj(G,i,p) 3 已知数组A1.n的元素递增有序，试设计算法以数组A中的元素构造一棵二叉排序树，并使其满足平衡二叉树的条件。算法思想：递归算法，以居中的元素作为根结点。设二叉树节点结构定义如下：struct nodestruct node *lchild,*rchi