数据结构与算法期末复习题（3）
班级 学号 姓名
一、选择题（在每小题备选答案中选一个最佳答案，共15小题 ,每小题2分,共30分）
1、数据结构是（ D ）。
A、一种数据类型 B、数据的存储结构 C、一组性质相同的数据元素的集合
D、相互之间存在一种或多种特定关系的数据元素的集合
2、在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ D ）。
A、插入 B、删除 C、排序 D、查找 3、线性表采用链式存储时，其地址( D )。
A、必须是连续的 B、一定是不连续的 C、部分地址必须连续 D、连续与否均可以
4、若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序
列为（ B ）。
A、3，2，6，1，4，5 B、3，4，2，1，6，5 C、1，2，5，3，4，6 D、5，6，4，2，3，1 5、栈和队列的共同点是（ C ）。
A、都是先进先出 B、都是先进后出 C、只允许在端点处插入和删除元素 D、没有共同点
6、在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（ A ）。
A、front=front->next B、rear=rear->next C、rear->next=front D、front->next＝rear
7、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个
元素的存储地址是（B ）。
共3页，第1页
A、98 B、100 C、102 D、106
8、下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（D ）。
A、堆排序 B、冒泡排序 C、快速排序 D、直接插入排序 9、二分查找要求关键字（B ）。
A、无序、顺序存储 B、有序、顺序存储C、有序、链接存储 D、无序、链接存储 10、对图的深度优先遍历，类似于对树的哪种遍历（ A）。
A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历 11、对某个无向图的邻接矩阵来说，下列叙述正确的是( A )。
A、第i行上的非零元素个数和第i列上的非零元素个数一定相等。 B、矩阵中的非零元素个数等于图中的边数。
C、第i行与第i列上的非零元素的总数等于顶点vi的度数。 D、矩阵中非全零行的行数等于图中的顶点数。 12、求下列程序段的时间复杂度（ B）。 i=1； while(i﹤=n) i=i*3；
A、O(1) B、O(n) C、O(n/3) D、O(log3n)
13、已知一组待排序的记录关键字初始排列如下：56,34,58,26,79,52,64,37,28,84,57。下列
选择中（ C ）是快速排序一趟排序的结果。
A、84，79，64，37，57，52，58，26，28，34，56。 B、28，34，52，26，56，57，58，37，79，84，64。 C、28，34，37，26，52，56，64，79，58，84，57。 D、52，34，64，84，56，26，37，57，58，28，79。 14、在有n个结点的二叉树的二叉链表表示中，空指针数为（ B）。
A、不定 B、n+1 C、n D、n-1 15、在一个无向图中，所有顶点的度数之和等于图的边数的（C ）倍。
A、1/2 B、1 C、2 D、4
1 3 ? a
1、栈和队列的存储方式既可是顺序方式，也可以是链接方式。 （ T ） b 2 4 ?
2、对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。 c 5 ? （ F ） d 2 5 ?
3、链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元
e 5 ? 向前移动。 （ F）
f ?
4、具有12个结点的完全二叉树有5个度为2的结点。 （ T ）
3、已知一个散列表如下图所示：
5、已知一棵树的先序序列和后序序列，一定能唯一构造出该树。 （ F ）
6、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （ F ）
0 1 2 3 4 5 6 7 8 9 10 11 12
7、一个无向图的连通分量是其极大的连通子图。 （ T ）
其散列函数为h(key)=key, 处理冲突的方法为线性探测再散列法。
8、对一个堆按层次遍历，不一定能得到一个有序序列。 （ T ）
回答下列问题：
9、邻接表可以表示有向图，也可以表示无向图。 （ T ）
（1）将关键字28、29、41、54、25、38填入散列表中。（3分）
10、哈希表的装填因子小于0.5的情况下, 冲突可以避免。 （ F ）
（2）对表中关键字28，41和54进行查找时，所需进行的比较次数各为多少?（3分）
二、判断题(本大题共10小题，每小题1分，共10分)
三、算法应用题（本大题共5小题，每小题8分，共40分）
1、已知一棵二叉树如下，请分别写出按先序、中序、后序和层次遍历时得到的结点序列，并将此二叉树转化成森林。
2、已知一个图的邻接表如下面所示。 （1）画出该图的图结构形态。(4分)
（2）根据邻接表分别写出从顶点a出发进行深度优先和广度优先遍历序列。(4分)
（3）该散列表在等概率查找时查找成功的平均查找长度为多少?（2分）
4、设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。
5、用prim算法求下图的最小生成树（从V1出发），写出最小生成树的生成过程。
50 V1 60 V3 V2 V1 V3 V1 50 V7 V3 45 52 42 V4 V2 V7 50 30 40 V5 V6 65 V4 V6 V4 V2 V7 V5 V5 V6 70 四、算法分析题（本大题共2小题, 每小题5分，共10分 ）
1、简述下列算法实现的功能：
共3页，第2页
（1）void preorder(bitree *T)
{bitree *stack[m]; int top; if(T!=NULL) {top=1; stack[top]= T; while( top>0 ) { p=stack[top]; top--;
printf(\
if(p->rchild!=NULL){ top++; stack[top]=p->rchild;} if(p->lchild!=NULL) { top++; stack[top]=p->lchild ;}
} } } 功能是：
—————————————————————————————————— （2）void conversion() {
Stack s; int n; SElemType e; initstack(s);
printf(\ scanf(\
while(n) {push(s,n%8); n=n/8; }
while(!stackempty(s)) {pop(s,e); printf(\ } } 功能是：
————————————————————————————————————
五、算法设计题（本大题共1小题, 共10分 ）
单链表结点的类型定义如下： typedef struct node { int data; struct node *next; }linknode, *linklist;
有一个带头结点的单链表，头指针为head，编写一个算法计算所有数据域为不等于x的结点的个数（不包括头结点）。实现算法的函数头给定如下，填充函数内部。 int countnode(linklist head, int x) {……}
共3页，第3页
数据结构与算法期末复习题(3) - 图文
