算法与数据结构试卷.docx

本文格式为Word版，下载可任意编辑算法与数据结构试卷 专业 学号 姓名 一、选择题（10*2%=20%） 1．代码段 for (j=1; j=1; k/=2) count++; A、O(n2) B、O(nlogn) C、O(logn) D、O(n) 2．对某个无向图的邻接矩阵来说，以下表达正确的是 A A、第i行上的非零元素个数和第i列上的非零元素个数确定相等 B、矩阵中的非零元素个数等于图中的边数 C、第i行与第i列上的非零元素的总数等于顶点vi的度数 D、矩阵中非全零行的行数等于图中的顶点数 3．循环双链表中在p所指结点之后插入结点s的操作是 D A、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 C、a3，a1，a4，a2 B、a3，a2，a4，a1 D、a3，a4，a2，a1 5．以下四种排序方法中，不稳定的方法是 D A、 插入排序 B、冒泡排序 C、归并排序 D、选择排序 6．单个结点二叉树的高度为0，全体含有15个结点的二叉树中，最小高度是 D A、6 B、5 C、4 D、3 7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要 B 条边 A、 n B、n-1 C、n/2 D、n+1 8．快速排序法的运行效率取决于 D A、要排序的数据量 B、要排序的数据中含有一致值的比例 D、划分过程的对称性 C、要排序的数据的局部有序性 9．二叉树若用依次存储布局（数组）存放，那么以下四种运算中的 C 最轻易实现。

A、 先序遍历二叉树 B、判断两个结点是否位于同一层 C、层次遍历二叉树 D、根据结点的值查找其存储位置 10．模式串ABBCABABDBABBC的前缀函数为 C 专业 学号 姓名 A、00001212000121 B、10000120001212 C、00001212022234 D、10000120222345 二、填空题（15*2%=30%） 1、已知某棵二叉树按中序遍历所得到的结点序列为DCBGEAHFIJK，按后序遍历所得到的结点序列为DCEGBFHKJIA，该二叉树按前序遍历所得到的结点序列为ABCDGEIHFJK 2、一个n×n的下三角矩阵A中的元素aij（i≥j，1≤i，j≤n）按行存于一个一维数组B[1..n（n＋1）/2]中，对其中的任一元素aij，若在B中的位置为k，那么k＝j+(i-1)i/2 3、设一棵完全二叉树具有988个结点，那么此完全二叉树有 494 个叶子结点，有 493 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。

4、向一个有127个元素的有序线性表（数组实现）中插入一个随机的新元素并照旧保持有序性，平均要移动 63.5 个元素 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 若采用少用一个存储单元的方法区分队满与队空问题，那么可用 (rear+1)%MAX==front 表示队满的判别条件 7、在输入已经有序的处境下，整个冒泡排序算法需要执行 n(n-1)/2 次元素对比操作 8、设一个闭散列表的容量为m，用线性探测法解决冲突，要插入一个键值，若插入告成，至多要举行 m-1 次检测 1 0??0 ??表示一张图，假设该图是有向图，共有 4 条边；若是19、用邻接矩阵A?1 0 ???1 0??0 ?无向图，那么共有 2 条边。

三、简答题（28%） 1、（5分）设以下二叉树是与某森林对应的二叉树，回复以下问题 （1）森林中有几棵树？ （2）每一棵树的根结点标号分别是什么？ （3）每一棵树中有几个结点？ （4）森林中共有几个叶子结点？ 解答： （1）3 (2分) 专业 （2）A C F （1分） （3）6 2 3 （1分） （4）6 （1分） 学号 姓名 2、（6分）用Prim算法（初始顶点集S＝{7}）构造出下图的一棵最小生成树，请用图示法画出其构造过程 图解：（每图1分） 5066 ① ② 4065 503 60 50 ⑦ 45 42 30 ③ 70④ ⑤ ⑦ 45 ⑥ ⑦ 45 ① ② ⑤ （1） ① ④ ② ⑤ （2） ⑦ 45 ① ④ ② ⑤ （3） ③ ⑥ ③ 42 ③ 42 30 ④ ⑥ ⑥ ① ② ⑦ 45 ① ④ ② ③ ⑦ 45 42 ① ④ ② 5066 ⑦ 45 ③ 42 ③ 42 ④ 5030 5030 40 5030 403 3 3 ⑤ ⑥ ⑤ ⑥ ⑤ （5） 4） （（6） ⑥ 3．（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)采用先将关键码各位数字折叠相加, 再用%hashSize将相加的结果映像到表中的手段，采用二次散列技术（h2i-1(x)=|h(x)+i2|%hashsize，h2i(x)=|h(x)-i2|%hashsize解决冲突，画出相应的闭散列表，并指出每一个产生冲突的关键码分别产生了多少次冲突 解答：（每项包括位置和冲突次数0.5分） 5．（6分）已知如下图的有向图，请按照Dijkstra算法找出顶点A到全体其它顶点的最短路径要求给出概括迭代过程） 下标 0 1 2 3 4 5 6 7 8 9 10 11 12 关键字 58 10 100 3 400 32 200 45 126 29 0 冲突次数 0 0 1 0 0 0 3 0 1 0 9 专业 学号 姓名 B5A2D3762C2F1371G1E解答：（每迭代0.5分，每个顶点距离0.5分） 迭代 S 初始 A 1 2 3 4 5 6 {A,C} {A,C,B} {A,C,B,G} {A,C,B,G,E} {A,C,B,G,E,F} U - C B G E F Dist[B] 5 5 5 5 5 5 5 Dist[C] 3 3 3 3 3 3 3 Dist[D] ∞ 10 10 10 9 9 9 Dist[E] ∞ 10 8 7 7 7 7 Dist[F] ∞ ∞ ∞ ∞ 8 8 8 Dist[G] ∞ ∞ 6 6 6 6 6 {A,C,B,G,E,F,D} D 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 *p ) { ThreadedNode *q; if ( （1） p->LeftThread ) return (p->LeftChild); else { q=p->LeftChild; while ( （2） !q->RightThread ) （3） q=q->RightChild ; return(q); } }//Predecessor 五、算法设计题（共16分） 1、（8分）二叉探寻树预先假设探寻是基于一个关键字的假设我们想要执行或者基于关键 专业 学号 姓名 字key1或者基于关键字key2的查找，可以使用一种类似于二叉树的布局——2-d树但是在一棵2-d树中，偶数层用key1举行分叉，奇数层用key2举行分叉(根结点层数为0)图中就是一棵2-d树的例如，以名（first name）和姓（last name）作为两个关键字对二战以后的美国总统举行查找。

总统的姓名是按照年头依次插入的（Truman、Eisenhower、Ford、Carter、Reagan、Bush、Clinton）请根据上述描述，编写实现2-d树的插入操作 算法设计思想： 从根结点开头，从上往下探寻元素X适合的插入位置，探寻过程中，记录当前结点current所在层次（根结点层次为0），若current的层次为奇数时，用key2举行对比，当current->key2>x->key2，那么探寻current的左子树，否那么探寻其右子树；同理，若current的层次为偶数时，用key1举行对比，当current->key1>x->key1。