2013-2014学年二学期数据结构期末考试模拟试卷(1~6卷)一、应用题(3小题,共24分)1．已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该字符串用[0，1]进行前缀编码，问该字符串的编码至少有多少位。
【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。
其带权路径长度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，该字符串的编码长度至少为98位。
2．已知关键码序列为（Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec），散列表的地址空间为0~16，设散列函数为H(x)=［ i/2 」(取下整数) ，其中i为关键码中第一个字母在字母表中的序号，采用链地址法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。
【解答】H(Jan)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0H(May)=13/2=6, H(Jun)=10/25, H(Jul)=10/25, H(Aug)=1/2=0H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2采用链地址法处理冲突，得到的开散列表如下：平均查找长度=(1×7+2×4+3×1)/12=18/123．分析下面各程序段的时间复杂度（1）s1(int n){ int p=1,s=0;for (i=1;i<=n;i++){ p*=i;s+=p; }return(s);} ——O(n)（2）s2(int n)x=0;y=0;For (k=1;k<=n;k++) x++;For (i=1;i<=n;i++)For (j=1;j<=n;j++)y++; ——O(n2)1．下述算法的功能是什么?（1）（1）返回结点*p的直接前趋结点地址。
（2）交换结点*p和结点*q（p和q的值不变）。
1．对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。
【解答】构造的哈夫曼树如图所示。
W PL=2×4+3×4+5×3+7×3+8×3+9×2+11×2=1202．已知散列函数H(k)=k mod 12，键值序列为(25, 37, 52, 43, 84, 99, 120, 15, 26, 11, 70, 82)，采用链表法处理冲突，试构造散列表。
【解答】H(25)=1, H(37)=1, H(52)=4, H(43)=7, H(84)=0, H(99)=3,H(120)=0, H(15)=3, H(26)=2, H(11)=11, H(70)=10, H(82)=10构造的开散列表如下：3．分析下面各程序段的时间复杂度（1）for (i=0;i<n;i++)for (j=0;j<m;j++)A[i][j]——O(n*m)（2） s=0;for (i=0;i<n;i++)for (j=0;j<n;j++)s+=B[i][j];sum=s;——O(n2)（3）A=B; B=C; C=A;——O(1)3．设无向图G（所下图所示），要求给出从1出发对该图进行深度优先和广度优先遍历的序列。
深度：125364，广度：123456 （不唯一）4．已知无向图G的邻接表如图所示，分别写出从顶点1出发的深度遍历和广度遍历序列。
【解答】深度优先遍历序列为：1，2，3，4，5，6广度优先遍历序列为：1，2，4，3，5，6二、判断正误(7小题,共14分)1．线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。
（√）2．一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。
（ㄨ）3．稀疏矩阵压缩存储后，必会失去随机存取功能。
（√）4．如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。
（√）5．用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。
（√）6．向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。
（ㄨ）7．逻辑结构与数据元素本身的内容和形式无关。
（√）1．对链表进行插入和删除操作时不必移动链表中结点。
( √ )3．如果两个串含有相同的字符，则说明它们相等。
( ㄨ )4．在线索二叉树中，任一结点均有指向其前趋和后继的线索。
(ㄨ)5．带权无向图的最小生成树是唯一的。
（ㄨ）6．稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。
（√）7．无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的。
( ㄨ ) 8．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。
（√）1．由树转化成二叉树，该二叉树的右子树不一定为空。
（ㄨ）2．稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。
（√）4．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。
（√）5．设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。
（ㄨ）6．每种数据结构都具备三个基本操作：插入、删除和查找。
（ㄨ）1．顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
（×）2．在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。
√3．链表的每个结点都恰好包含一个指针域。
（×）4．有向图的邻接表和逆邻接表中表结点的个数不一定相等。
（×）5．对连通图进行深度优先遍历可以访问到该图中的所有顶点。
（√）6．当装填因子小于1时，向散列表中存储元素时不会引起冲突。
（×）2．线性表的逻辑顺序和存储顺序总是一致的。
（×）3．非空的双向循环链表中任何结点的前驱指针均不为空。
（√）4．子串“ABC”在主串“AABCABCD”中的位置为2。
（√）5．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。
（×）7．用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。
（×）9．当装填因子小于1时，向散列表中存储元素时不会引起冲突。
（×）10．散列技术的查找效率主要取决于散列函数和处理冲突的方法。
（×）1．线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。
（）2．稀疏矩阵压缩存储后，必会失去随机存取功能。
（√）5．对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点。
（ㄨ）6．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。
（√）7．数据的逻辑结构和数据的存储结构是相同的。
（ㄨ）8．数据的存储结构是数据的逻辑结构的存储映像。
（√）三、单项选择题(8小题,共16分)1．下面关于线性表的叙述错误的是（ D ）。
A 线性表采用顺序存储必须占用一片连续的存储空间B 线性表采用链式存储不必占用一片连续的存储空间C 线性表采用链式存储便于插入和删除操作的实现D 线性表采用顺序存储便于插入和删除操作的实现2．单链表的存储密度（ C ）。
A．大于1 B．等于1 C．小于1 D．不能确定3．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ B ）。
A 5，3，4，6，1，2B 3，2，5，6，4，1C 3，1，2，5，4，6D 1，5，4，6，2，34．若串S="SOFTWARE"，其子串的数目最多是：（ C ）。
A．35 B．36 C．37 D．385．二叉排序树中，最小值结点的（A ）。
A 左指针一定为空B 右指针一定为空C 左、右指针均为空D 左、右指针均不为空6．在散列函数H(k)= k mod m中，一般来讲，m应取（C ）。
A 奇数B 偶数C 素数D 充分大的数7．用直接插入排序对下面四个序列进行由小到大排序，元素比较次数最少的是（ B ）。
A 94, 32, 40, 90, 80, 46, 21, 69B 21, 32, 46, 40, 80, 69, 90, 94C 32, 40, 21, 46, 69, 94, 90, 80D 90, 69, 80, 46, 21, 32, 94, 401．使用双链表存储线性表，其优点是可以（B ）。
A 提高查找速度B 更方便数据的插入和删除C 节约存储空间D 很快回收存储空间2．链表不具有的特点是（B ）A.不必事先估计存储空间B.可随机访问任一元素C.插入删除不需要移动元素D.所需空间与线性表长度成正比3．下面关于线性表的叙述错误的是（ D ）。
A 线性表采用顺序存储必须占用一片连续的存储空间B 线性表采用链式存储不必占用一片连续的存储空间C 线性表采用链式存储便于插入和删除操作的实现D 线性表采用顺序存储便于插入和删除操作的实现4．从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（ D ）个结点。
A nB n/2C (n-1)/2D (n+1)/25．在C或C++语言中，一个顺序栈一旦被声明，其占用空间的大小（ A ）。
A．已固定 B．不固定 C．可以改变 D．动态变化6．两个字符串相等的充要条件是（C ）。
A 两个字符串的长度相等B 两个字符串中对应位置上的字符相等C 同时具备(A)和(B)两个条件D 以上答案都不对8．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ C ）。
A N0=N1+1B N0=Nl+N2C N0=N2+1D N0=2N1+l 9．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D )A．e B．2e C．n2－e D．n2－2e10．设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（ A ）。
A N1-1B N2-1C N2+N3D N1+N311．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（D ）。
A 空或只有一个结点B 高度等于其结点数C 任一结点无左孩子D 任一结点无右孩子12．在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择（快速）排序，如果从节省存储空间的角度来考虑则最好选择（堆）排序。