长沙理工大学计算机与通信工程学院
2013-2014学年二学期数据结构期末考试模拟试卷(1卷)
班级:___________学号:___________姓名:___________得分:___________
题号 得分 阅卷 一 二 三 四 五 六 七 八 九 十 成绩 复核 题目部分，(卷面共有29题,100分,各大题标有题量和总分) 一、应用题(3小题,共24分)
1．已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该字符串用[0，1]进行前缀编码，问该字符串的编码至少有多少位。
2．已知关键码序列为（Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec），散列表的地址空间为0~16，设散列函数为H(x)=［ i/2 」(取下整数) ，其中i为关键码中第一个字母在字母表中的序号，采用链地址法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。
3．分析下面各程序段的时间复杂度 （1） s1(int n)
{ int p=1,s=0;
for (i=1;i<=n;i++) { p*=i;s+=p; } return(s); }
（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++;
二、判断正误(7小题,共14分)
1．线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。（ ）
2．一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。（ ）
3．稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）
4．如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（ ） 5．用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。（ ）
6．向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（ ）
7． 逻辑结构与数据元素本身的内容和形式无关。（ ）
三、单项选择题(8小题,共16分)
1．下面关于线性表的叙述错误的是（ ）。
A 线性表采用顺序存储必须占用一片连续的存储空间 B 线性表采用链式存储不必占用一片连续的存储空间 C 线性表采用链式存储便于插入和删除操作的实现 D 线性表采用顺序存储便于插入和删除操作的实现
2．单链表的存储密度（ ）。
A． 大于1 B． 等于1 C．小于1 D． 不能确定
3． 设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ ）。
A 5，3，4，6，1，2 B 3，2，5，6，4，1 C 3，1，2，5，4，6 D 1，5，4，6，2，3
4．若串S=\，其子串的数目最多是：（ ） 。 A．35 B．36 C．37 D．38
5．二叉排序树中，最小值结点的（ ）。 A 左指针一定为空 B 右指针一定为空
C 左、右指针均为空 D 左、右指针均不为空
6．在散列函数H(k)= k mod m中，一般来讲，m应取（ ）。 A 奇数 B 偶数 C 素数 D 充分大的数
7．用直接插入排序对下面四个序列进行由小到大排序，元素比较次数最少的是（ ）。 A 94, 32, 40, 90, 80, 46, 21, 69 B 21, 32, 46, 40, 80, 69, 90, 94 C 32, 40, 21, 46, 69, 94, 90, 80 D 90, 69, 80, 46, 21, 32, 94, 40
四、算法设计题(2小题,共24分)
1．设计在顺序存储结构上实现求子串算法。
2．编写算法，要求输出二叉树后序遍历序列的逆序。
五、填空题(6小题,共12分)
1．在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为（ ）。
2．设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有（ ）关系。 3．顺序查找技术适合于存储结构为（ ）的线性表
4．对n个元素进行起泡排序，在（ ）情况下比较的次数最少，其比较次数为（ ）。 5．快速排序算法的空间复杂度平均情况下为（ ），最坏的情况下为（ ）。 6．树形结构结构中的元素之间存在（ ）的关系
六、简答题(2小题,共10分)
1．下图所示是一个无向带权图，请按Prim算法从a出发求最小生成树。
2．求下列算法的时间复杂度。 count=0; x=1; while (x { x*=2; count++; }
return count;
长沙理工大学计算机与通信工程学院
2013-2014学年二学期数据结构期末考试试卷(1卷)
答案部分，(卷面共有29题,100.0分,各大题标有题量和总分) 一、应用题(3小题,共24分)
1．以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。其带权路径长度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，该字符串的编码长度至少为98位。
2．【解答】H(Jan)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Jun)=10/25, H(Jul)=10/25, H(Aug)=1/2=0
H(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/12
3．O(n) O(n2)
二、判断正误(7小题,共14分)
1．（√） 2．（ㄨ） 3．（√） 4．（√） 5．（√） 6．（ㄨ） 7．（√）。因此逻辑结构是数据组织的主要方面。
三、单项选择题(8小题,共16分) 1．D 2．C 3．B 4．C 5．A 6．C 7．B
四、算法设计题(2小题,共24分)
1．void substring(char s[ ], long start, long count, char t[ ])
{
long i,j,length=strlen(s);
if (start<1 || start>length) printf(\
else if (start+count-1>length) printf(\characters to be copied\ Else { for(i=start-1,j=0; i } 2．要想得到后序的逆序，只要按照后序遍历相反的顺序即可，即先访问根结点，再遍历根结点的右子树，最后遍历根结点的左子树。 void Postordern(BiTree *H) { if (H) { visit(H->data); Postordern(H->rchild); Postordern(H->lchild); } } 五、填空题(6小题,共12分) 1．O(n) 2．m=2e 3．顺序存储和链接存储 4．正序，n-1 5．O(nlog2n)， O(n) 6． 一对多 六、简答题(2小题,共10分) 1．【解答】按Prim算法求最小生成树的过程如下： 2．Ｏ(log2n)