计算机系数据结构平时测试试题一

1、临沂大学 2015-2016 学年度第一学期数据结构平时测试试题一选择题(共 20题，每题 2 分，共 40分)1. 以下哪一个术语与数据的存储结构无关？()。A.栈B.哈希表C.线索树D.双向链表2. 下面的叙述不正确的是 () 。A. 线性表在链式存储时，查找第B. 线性表在链式存储时，查找第C. 线性表在顺序存储时，查找第i 个元素的时间同 i 的值成反比 i 个元素的时间同 i 的值无关i 个元素的时间同 i 的值成正比D. 线性表在顺序存储时，查找第i 个元素的时间同 i 的值无关3. 向一个有 127 个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动( )个元素。A.

2、8 B.63.5 C.63 D.74. 单链表中，增加头结点的目的是为了 ()。A. 使单链表至少有一个结点B.标示表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储实现5. 在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 和 p 之间插入 s 结 点，则执行 ()。A. s-next=p-next;p-next=s;B. p-next=s-next;s-next=p;C. q-next=s;s-next=p;D. p-next=s;s-next=q;A.n6. 从一个具有 n 个结点的单链表中查找其值等于 x 的结点时，在查找成功的情况下，需平 均

3、比较 ( )个结点？7.若已知一个栈的入栈序列为B. n/2 C.(n-1)/2 D.(n+1)/21,2,3, ,n 其输出序列为 p1,p2,p3, ,pn 若 p1=n，则 pi 为() 。A.i B.n-iC.n-i+1D.不确定D.a,b,c,d,eD.-+*abcd10.设 n ，m 为一棵二叉树的两个结点，在中序遍历时， A.n 在 m 的右方 C.n 在 m 的左方 11.树中所有结点的度等于所有结点数加 A.0B.1C.-1D.212.设树 T 的度为 4，其中度为 1，2，n在 m前的条件是 (B.n 是 m 的祖先D.n 是 m 的子孙() 。)。3和 4的结点个数分别为

4、 4，2，1，1 则 T中的叶子8.一个栈的入栈序列是 a,b,c,d,e ，则出栈序列不可能是 ()。A.e,d,c,b,a B.d,e,c,b,a C.d,c,e,a,b9.表达式 a*(b+c)-d 的后缀表达式是 ()。A.abcd*+- B.abc+*d- C.abc*+d-数为 ()。A.5 B.6 C.7 D.813. 对含有 ()个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。A.0 B.1 C.2D.不存在这样的二叉树32，10，43，18，则完成工程14.从 AOE 网络的源点到终点共有 4 条路径，路径长度分别是 的最短时间是 ()。A.10 B. 43

5、C .32+10+43+18 D. (32+10+43+18)/4A.4 B.3 C.2D.116. 无向图中一个顶点的度是指图中 ()。A.通过该顶点的简单路径数B. 通过该顶点的回路数C. 与该顶点相邻接的顶点数D. 与该顶点连通的顶点数17. 具有 12 个关键字的有序表，对每个关键字的查找概率相同，折半查找查找成功的平均 查找长度 ASL为 ()。A.37/12 B.35/12 C.39/12 D.43/1218. 在常用的描述二叉排序树的存储结构中，关键字值最大的结点()。A.左指针一定为空B.右指针一定为空C. 左右指针均为空D.左右指针均不为空19. 有一组数据 15,9,7,8

6、,20,-1,7,4 ，对其进行建堆，则初始堆为 ()。A.-1,4,8,9,20,7,15,7B.-1,7,15,7,4,8,20,9C.-1,4,7,8,20,15,7,9D.以上都不是20. 下述排序算法中，稳定的是 ( )。A.直接选择排序B.基数排序C.快速排序D.堆排序二、 判断题(共 10题，每题 1 分，共 10分)1. 顺序存储方式只能用于存储线性结构。( )2. 在带头结点的单循环链表中，任一结点的后继指针均不空。()3. 双循环链表中，任一个结点的后继指针均指向其逻辑后继。()4. 通在对链队列作出队列操作，不会改变front 指针的值。 ( )5. 由于二叉树中每个结点

7、的度最大为2，所以二叉树是一种特殊的树。 ( )6. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。 ( )7. 在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。( )8. 有 n 个顶点的无向图 , 采用邻接矩阵表示 , 图中的边数等于邻接矩阵中非零元素之和的一半。 （ ）9. 对一棵二叉排序树按先序方法遍历得出的结点序列是从小到大的序列。（ ）10. 归并排序辅助存储为 O（1）。 （）三、解答题（共 7 题，每题 5 分，共 35分）1. 已知一棵二叉树的中序遍历序列 :GLDHBEIA和后序遍历序列 :LGHDIEBA （1）试画出该二叉树； （3 分）（2）试画出

8、该二叉树对应的树； （ 2 分 ）2. 假设通信电文使用的字符集为 a,b,c,d,e,f,g，字符的赫夫曼编码依次为： 0110 ，10，110， 111，00， 0111 和 010。（1）请根据赫夫曼编码画出此赫夫曼树，并在叶子结点中标注相应字符；（3 分 ）（2）若这些字符在电文中出现的频度分别为：3，35，13， 15，20，5 和 9，求该赫夫曼树的带权路径长度。 （ 2 分）3. 已知有向图（1） 试画出它的邻接表。 （表结点按顶点编号递减排列） （3 分）（2） 求出从顶点 v1 开始深度优先遍历序列。 （2 分）4. 请对下图的无向带权图：从顶点a 开始按普里姆算法求其最小生

9、成树 ,（1）写出顶点集（ 2 分）（2）写出边集（ 3 分）5. 根 据 关 键 字 序 列 48,68,72,60,36,25,45,40 （1）构造一棵二叉排序树； （ 3 分） （2）求出等概率下的平均查找长度 ASL。（2 分）6. 已知待散列的线性表为（ 36，15，40，63，22），哈希地址空间为 0.6 ，假定选用的哈希 函数是 H（K）= K %7，若发生冲突采用线性探测再散列处理，试： （1）在下图中填写出哈希表： （3 分） （2）求出在查找每一个元素概率相等情况下的平均查找长度。（2 分）地址空间0123456关键字试探次数7. 给出一组关键字 T=（12,2,16,30,8,28,4,10,20,6,18）, 写出用下列算法从小到大排序时第一趟结 束时的序列；得分阅卷人（1） 希尔排序（第一趟排序的增量为 5 ）（2） 快速排序（选第一个记录为枢轴（分隔）2 分）四、算法设计题（共 2 题，共 15分）（ 3 分）1.试写出一递归算法，判别两棵树是否相等。所谓两棵二叉树s和 t 相等为:两棵空二叉树相等;若不空 ,根结点的数据域的值