《数据结构题库》由会员分享，可在线阅读，更多相关《数据结构题库（17页珍藏版）》请在金锄头文库上搜索。
1、2013-2014学年二学期数据结构期末考试模拟试卷(16卷)一、应用题(3 小题,共 24 分)1已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3 次、4次和9次，对该字符串用0，1进行前缀编码，问该字符串的编码至少有多少位。解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。其带权路径长度=2X5+1X5+3X4+5X3+9X2+4X3+4X3+7X2=98，所以，该字符串的编码长度至少 为98位。2. 已知关键码序列为(Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec),
2、散列表的地址空间为016,设散列函数为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 采用链地址法处理冲突，得到的开散列表如下：AAA A AAA
3、AA ADecAFebAJanMarUuLA?JunMay:ANov A3分析下面各程序段的时间复杂度(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;jnext;(1)返回结点*卩的直接前趋结点地址。while (q &. q-next!=p) q=q-neKt;if(Q return q;else erroi( not invoid DarLo2(ListNode p.Li
4、stNode *q)(2)交换结点*p和结点*q (p和q的值不变)。(是琏表中的 期个结点DataTyp 已 temp, temp=p-data; p-data=q-daX q-data=temp;1.对给定的一组权值W=(5, 2, 9, 11, 8, 3, 7),试构造相应的哈夫曼树，并计算它 的带权路径长度。【解答】构造的哈夫曼树如图所示。10WPL=2X4+3X4+5X3+7X3+8X3+9X2+11X2=1202已知散列函数 H(k)=k mod 12，键值序列为(25, 37, 52, 43, 84, 99, 120, 15, 26, 11, 70, 82) 采用链表法处理冲突，
5、试构造散列表。解答】H(25)=l, H(37)=l, 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 构造的开散列表如下：苑.AAA.-8425yyA7011A：120:怒373分析下面各程序段的时间复杂度1) for (i=0;in;i+)for (j=0;jm;j+)AijO(n*m)2) s=0;for (i=0;in;i+)for (j=0;jn;j+) s+=Bij;sum=s;O(n2)(3) A=B; B=C; C=A;O(1)3.设无向图G
6、 (所下图所示)，要求给出从1出发对该图进行深度优先和广度优先遍历的序 列。深度：125364，广度：123456 (不唯一)4.已知无向图G的邻接表如图所示，分别写出从顶点1出发的深度遍历和广度遍历序列。解答】深度优先遍历序列为：1，2，3，4，5，6广度优先遍历序列为：1，2，4，3，5，6二、判断正误（7小题,共14分）1线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。（V ）2. 个栈的输入序列为：A, B, C, D,可以得到输出序列：C, A, B, Do （X ）3. 稀疏矩阵压缩存储后，必会失去随机存取功能。（V4. 如果某个有向图的邻接表中第i条单链表为空，
7、则第i个顶点的出度为零。（V ）5. 用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。（V）6. 向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（X ）7. 逻辑结构与数据元素本身的内容和形式无关。（V ）1. 对链表进行插入和删除操作时不必移动链表中结点。（V ）3如果两个串含有相同的字符，则说明它们相等。（X ）4. 在线索二叉树中，任一结点均有指向其前趋和后继的线索。（X）5. 带权无向图的最小生成树是唯一的。（X ）6. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（V ）7无向图的邻接矩阵一定是对称的，有向图的邻接矩
8、阵一定是不对称的。（ X ）8. 分块査找的平均査找长度不仅与索引表的长度有关，而且与块的长度有关。（V ）1. 由树转化成二叉树，该二叉树的右子树不一定为空。（X ）2. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（V ）4分块査找的平均査找长度不仅与索引表的长度有关，而且与块的长度有关。（V）5. 设初始记录关键字基本有序，则快速排序算法的时间复杂度为0 （nlogi）。（ X ）6. 每种数据结构都具备三个基本操作：插入、删除和査找。（X 1. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（X）2. 在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位
9、置上并不一定紧邻。V3. 链表的每个结点都恰好包含一个指针域。（X）4. 有向图的邻接表和逆邻接表中表结点的个数不一定相等。（X）5. 对连通图进行深度优先遍历可以访问到该图中的所有顶点。（V ）6. 当装填因子小于1时，向散列表中存储元素时不会引起冲突。（X）2. 线性表的逻辑顺序和存储顺序总是一致的。（X）3非空的双向循环链表中任何结点的前驱指针均不为空。（V ）4.子串“ABC”在主串“AABCABCD”中的位置为2 （ V ）5. 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。（X） 7用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中
10、边 数有关。（X）9. 当装填因子小于1时，向散列表中存储元素时不会引起冲突。 （ X ）10. 散列技术的査找效率主要取决于散列函数和处理冲突的方法。（X）1线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。（乂）2. 稀疏矩阵压缩存储后，必会失去随机存取功能。（丁）5. 对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点 （乂 ）6当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（丁 ）7. 数据的逻辑结构和数据的存储结构是相同的。（乂）8. 数据的存储结构是数据的逻辑结构的存储映像。（V ） 三、单项选择题（8小题,共 16分）1. 下面
11、关于线性表的叙述错误的是（ D ）。A 线性表采用顺序存储必须占用一片连续的存储空间B 线性表采用链式存储不必占用一片连续的存储空间C 线性表采用链式存储便于插入和删除操作的实现D 线性表采用顺序存储便于插入和删除操作的实现2. 单链表的存储密度（ C ）。D. 不能确定A. 大于1B. 等于1C.小于13 . 设输入序列为 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
12、B.36C.37D.38 5.二叉排序树中，最小值结点的（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, 69C 32, 40, 21, 46, 69, 94, 90, 80B 21, 32, 46, 40, 80, 69, 90, 94D 90, 69, 80, 46, 21, 32, 94, 401
13、. 使用双链表存储线性表，其优点是可以（B ）。A 提高查找速度B 更方便数据的插入和删除C 节约存储空间D 很快回收存储空间2. 链表不具有的特点是（B ）A. 不必事先估计存储空间C.插入删除不需要移动元素B. 可随机访问任一元素D.所需空间与线性表长度成正比3下面关于线性表的叙述错误的是（ D ）。A 线性表采用顺序存储必须占用一片连续的存储空间B 线性表采用链式存储不必占用一片连续的存储空间C 线性表采用链式存储便于插入和删除操作的实现D 线性表采用顺序存储便于插入和删除操作的实现 4从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均 比较（ D ）个结点。A
14、 nB n/2C （n-1）/2D （n+1）/2 5在C或C+语言中，一个顺序栈一旦被声明，其占用空间的大小（ A ）A.已固定B.不固定C.可以改变 D.动态变化6. 两个字符串相等的充要条件是（C ）A两个字符串的长度相等B两个字符串中对应位置上的字符相等C同时具备（A）和（B）两个条件D以上答案都不对8. 设某二叉树中度数为0的结点数为NO,度数为1的结点数为Nl,度数为2的结点数为 N2,则下列等式成立的是（C ）A N0=N1+1B N0=Nl+N2C N0=N2+1D N0=2N1+l9. 在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（D ）A.eB.2eC.n2eD.n22e10. 设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B, T1、T2和T3的结 点
