《计算机系《数据结构》平时测试试题一》由会员分享，可在线阅读，更多相关《计算机系《数据结构》平时测试试题一（6页珍藏版）》请在金锄头文库上搜索。
1、临沂大学 2015-2016 学年度第一学期数据结构平时测试试题一一、选择题(共20 题，每题2 分，共 40 分)1. 以下哪一个术语与数据的存储结构无关？()。A.栈B.哈希表C.线索树D.双向链表2. 下面的叙述不正确的是()。A. 线性表在链式存储时，查找第i个元素的时间同i的值成反比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关3. 向一个有127 个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动()个元素。A. 8B.63.5C.63D.74
2、. 单链表中，增加头结点的目的是为了()。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;6从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平 均比较()个结点？A.nB.n/2C.(n-1)/2D.(n+1)/27. 若已
3、知一个栈的入栈序列为1,2,3n其输出序列为p1,p2,p3,pn若p1=n，则pi为() 。A.iB.n-iC.n-i+1D.不确定8. 个栈的入栈序列是a,b,c,d,e，则出栈序列不可能是()。A.e,d,c,b,a B.d,e,c,b,a C.d,c,e,a,bD.a,b,c,d,e9. 表达式 a*(b+c)-d 的后缀表达式是()。A.abcd*+- B.abc+*d- C.abc*+d- D.-+*abcd10. 设n，m为一棵二叉树的两个结点，在中序遍历时，n在m前的条件是()。A.n 在 m 的右方B.n 是 m 的祖先C.n 在 m 的左方D.n 是 m 的子孙11. 树中
4、所有结点的度等于所有结点数加()。A.0B.1C.-1D.212. 设树T的度为4,其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子 数为()。A.5B.6C.7D.813. 对含有()个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。A.O B.1C.2D.不存在这样的二叉树14. 从AOE网络的源点到终点共有4条路径，路径长度分别是32, 10, 43, 18，则完成工程的最短时间是()。A.10 B. 43 C .32+10+43+18 D. (32+10+43+18)/415. 对下图进行拓补排序，可以得到不同的拓补序列的个数是()。A.4B.3C.2D.
5、116. 无向图中一个顶点的度是指图中()。A. 通过该顶点的简单路径数B. 通过该顶点的回路数C. 与该顶点相邻接的顶点数D. 与该顶点连通的顶点数17. 具有 12 个关键字的有序表，对每个关键字的查找概率相同，折半查找查找成功的平均查找长度 ASL 为()。A.37/12B.35/12C.39/12D.43/1218. 在常用的描述二叉排序树的存储结构中，关键字值最大的结点()。A.左指针一定为空B.右指针一定为空C.左右指针均为空D.左右指针均不为空19. 有一组数据15,9,7,8,20,-1,7,4，对其进行建堆，则初始堆为()。A.-1,4,8,9,20,7,15,7B.-1,7
6、,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. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树。 ()6. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。 ()7. 在叶子数目和权值
7、相同的所有二叉树中，最优二叉树一定是完全二叉树。 ()8. 有 n 个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。（）9. 对一棵二叉排序树按先序方法遍历得出的结点序列是从小到大的序列。（）10归并排序辅助存储为O （1）。（）三、解答题（共7 题，每题 5 分，共35 分）1.已知一棵二叉树的中序遍历序列:GLDHBEIA和后序遍历序列:LGHDIEBA（1）试画出该二叉树；（3 分）（2）试画出该二叉树对应的树；（2 分）2假设通信电文使用的字符集为a,b,c,d,e,f,g,字符的赫夫曼编码依次为：0110, 10，110, 111， 00， 0111
8、 和 010。（1）请根据赫夫曼编码画出此赫夫曼树,并在叶子结点中标注相应字符；（3 分）（2）若这些字符在电文中出现的频度分别为： 3, 35, 13, 15, 20, 5 和 9,求该赫夫曼树的 带权路径长度。（ 2 分）3.已知有向图 （1） 试画出它的邻接表。（表结点按顶点编号递减排列）（3 分） 求出从顶点v1开始深度优先遍历序列。（2分）4请对下图的无向带权图：从顶点a开始按普里姆算法求其最小生成树,（1）写出顶点集（2分）（2）写出边集（3 分）5.根据关键字序列48,68,72,60,36,25,45,40 （1）构造一棵二叉排序树；（3 分）求出等概率下的平均查找长度ASL。
9、（2分）6.已知待散列的线性表为（36, 15，40，63，22），哈希地址空间为0.6,假定选用的哈希函数是 H（K） = K %7，若发生冲突采用线性探测再散列处理，试：（1）在下图中填写出哈希表：（3分）求出在查找每一个元素概率相等情况下的平均查找长度。（2分）地址空间0123456关键字试探次数7.给出一组关键字T=（12216,30,8,28,4,10,20,6,18）,写出用下列算法从小到大排序时第一趟结束时的序列；（1） 希尔排序（第一趟排序的增量为5）（2分）共15分）（2） 快速排序（选第一个记录为枢轴（分隔）（3分）得分阅卷人四、算法设计题（共2题,1试写出一递归算法，判别两棵树是否相等。所谓两棵二叉树s和t相等为:两棵空二叉树相 等;若不空,根结点的数据域的值相等,并且左右子树也相等.(1)写出二叉链表的类型定义，数据域要求为字符型(2 分) (2)写出完成问题的算法(6 分)2删除带头结点的单链表L中数据元素的值为x的结点；假设链表的元素的值均不相同(1) 写出单链表的类型定义，数据域要求为整型(2 分)(2) 写出完成问题的算法(5 分)
