数据结构模拟卷.docVIP

一、选择题（10*2%=20%） 1．代码段 for (j=1; j=n;j++) 的时间复杂性是 B 。 for (k=n; k=1; k/=2) count++; A、B、C、D、循环双链表p所指结点之后结点的操作是 。p-next=s; s-prior=p; p-next-prior=s; s-next=p-next B、p-next=s; p-next-prior=s; s-prior=p; s-next=p-next C、s-prior=p; s-next=p-next; p-next=s; p-next-prior=s D、s-prior=p; s-next=p-next; p-next-prior=s; p-next=s 4．4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态如图， ，不可能的出栈顺序是 C 。 A、a4，a3，a2，a1 B、a3，a2，a4，a1 C、a3，a1，a4，a2 D、a3，a4，a2，a1 5．下列四种排序方法中，不稳定的方法是 D 。 插入排序 B、冒泡排序 C、归并排序 D、选择排序 6．单个结点二叉树的高度为0，所有含有15个结点的二叉树中，最小高度是 D 。 A、6 B、5 C、4 D、3 7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要 B 条边。 n B、n-1 C、n/2 D、n+1 8．快速排序法的运行效率取决于 D 。 A、B、C、D、A、B、C、D、表示一张图，如果该图是有向图，共有 4 条边；若是无向图，则共有 2 条边。 三、简答题（28%） 1、（5分）设下列二叉树是与某森林对应的二叉树，回答下列问题。 （1）森林中有几棵树？ （2）每一棵树的根结点标号分别是什么？ （3）每一棵树中有几个结点？ （4）森林中共有几个叶子结点？ 解答： （1）3 （2）A C F （3）6 2 3 （4）6 2、（6分）用Prim算法（初始顶点集S＝{7}）构造出下图的一棵最小生成树，请用图示法画出其构造过程。 图解： 3．（6分）已知序列{17，31，13，11，20，35，25，8}，请将上述序列初始建为一个极小化堆，并给出输出前两个最小关键字后重建的堆。（要求画出初始建堆和两次调整后堆的示意图）。 图解： 4．（5分）设有一组关键字{10 100 32 45 58 126 3 29 200 400 0}，散列表大小hashSize=13，表项下标从0到12，散列函数h(x)采用先将关键码各位数字折叠相加, 再用%hashSize将相加的结果映像到表中的办法，采用二次散列技术（h2i-1(x)=|h(x)+i2|%hashsize，h2i(x)=|h(x)-i2|%hashsize解决冲突，画出相应的闭散列表，并指出每一个产生冲突的关键码分别产生了多少次冲突。 解答： 下标 关键字 冲突次数 0 58 0 1 10 0 2 100 1 3 3 0 4 400 0 5 32 0 6 200 3 7 8 9 45 0 10 126 1 11 29 0 12 0 9 5．（6分）已知如图所示的有向图，请按照Dijkstra算法找出顶点A到所有其它顶点的最短路径。（要求给出具体迭代过程） 解答： 迭代 S U Dist[B] Dist[C] Dist[D] Dist[E] Dist[F] Dist[G] 初始 A - 5 3 ∞ ∞ ∞ ∞ 1 {A,C} C 5 3 10 10 ∞ ∞ 2 {A,C,B} B 5 3 10 8 ∞ 6 3 {A,C,B,G} G 5 3 10 7 ∞ 6 4 {A,C,B,G,E} E 5 3 9 7 8 6 5 {A,C,B,G,E,F} F 5 3 9 7 8 6 6 {A,C,B,G,E,F,D} D 5 3 9 7 8 6 A－B：5 A－C：3 A－B－G－E－D：9 A－B－G－E：7 A－B－G－E—F：8 A－B－G：6 四、程序填空题（共6分） 1、（6分）下列算法实现在中序线索二叉树中求结点p的前驱，请在空白处填入正确的语句或表达式。 ThreadedNode *Predecessor( ThreadedNode