长沙理工大学数据结构模拟试题1及答案.docVIP

长沙理工大学数据结构模拟试题1

一、填空题〔每空1分，共15分〕

1、实现数据结构的根本存储方法有：⑴，⑵。

2、假设算法中的语句执行次数之和为T(n)=3525n+4nlogn，那么算法的时间复杂度是⑶。

3、假设以S和X分别表示进栈和出栈操作，那么对输入序列a,b,c,d,e进行一系列操作SSXSXSSXXX之后，得到的输出序列为⑷。

4、在串S=structure中，以t为首字符的子串有⑸个。

5、下三角矩阵A[n][n]按行优先存储在一维数组B中，实现随机存取下三角中元素A[i][j]的地址公式是⑹。〔注意元素下标是从0开始〕

6、广义表((a,b),c,d,(e,(f,g)))的表头是⑺，表尾是⑻，表的长度为⑼，表的深度为⑽。

7、包含n个结点的二叉树，深度最大为⑾，深度最小为⑿。

8、含有n个结点和e条边的无向图的邻接矩阵中，零元素的个数为⒀。

9、快速排序在⒁的初始状态下，时间效率最差，其时间复杂度为O〔n2〕。平均情况下快速排序的时间复杂度为⒂。

二、简答题〔每题5分，共20分〕

1、数据结构中研究的经典结构有那些？各有什么特点？

2、栈上有那些根本运算？请写出链栈的抽象数据类型定义。〔提示：先定义结点结构，再定义链栈类，在类中只给出函数声明，不需要定义函数〕

3、什么叫稳定排序？请列举出三种实现稳定排序的排序算法名称。

4、散列函数的设计原那么是什么？有那些常用的散列函数设计方法？

三、假设在长度大于1的循环链表中，即无头结点也无头指针，S为指向链表中某个结点的指针，试编写算法删除结点S的前趋结点。〔8分〕

四、叶子结点〔a,b,c,d,e,f〕及对应的权值〔12,5,3,20,9,10〕，请画出哈夫曼树并给出各叶子结点的哈夫曼编码。〔10分〕

五、有如下二叉树：〔共15分〕

(1)画出该二叉树的二叉链表存储示意图；〔4分〕

(2)写出前序遍历的递归算法；〔5分〕

(3)写出前序、中序、后序遍历得到的结点序列〔6分〕

六、有向图：〔共15分〕

G=〔V，E〕

V={a,b,c,d,e,f,g}

E={a,b,a,c,a,d,b,d,b,e,c,f,d,f,e,g,f,g}

(1)画出此有向图的邻接表存储结构图示；〔5分〕

(2)写出一个拓扑序列；〔2分〕

(3)假设初始时各顶点的入度已经存放在邻接表的in域中，请用伪代码写出拓扑排序算法。〔8分〕

七、散列函数为：H(k)=kmod7，用拉链法处理冲突，请画出依次插入23,14,9,6,18,30,49,12,34后的散列表，并求出检索成功的平均检索长度。〔9分〕

八、设有八枚硬币，分别表示为a，b，c，d，e，f，g，h，其中有且仅有一枚硬币是伪造的，假币的重量与真币的重量不同，可能轻，也可能重。现要求以天平为工具，用最少的比拟次数挑选出假币，并同时确定这枚硬币的重量比其它真币是轻还是重。写出你的判定过程或画出判定树。〔8分〕

答案:

一、填空题〔每空1分，共15分〕

1、⑴顺序存储结构；⑵链接存储结构

2、⑶O〔nlogn〕

3、⑷b,c,ed,a

4、⑸12

5、⑹i×(i+1)/2+j

6、⑺(a,b)；⑻(c,d,(e,(f,g)))；⑼4；⑽3

7、⑾n；⑿[log2n]+1

8、⒀n2-2e

9、⒁正序或逆序；⒂O〔nlogn〕

二、简答题〔每题5分，共20分〕

1、答：根据数据元素之间逻辑关系的不同，数据结构分为四类：

⑴集合数据元素之间就是“属于同一个集合”，除此之外，没有任何关系；

⑵线性结构数据元素之间存在着一对一的线性关系；

⑶树形结构数据元素之间存在着一对多的层次关系；

⑷图型结构数据元素之间存在着多对多的任意关系。

2、答：栈上有的根本运算有：入栈、出栈、取栈顶元素、判断栈是否为空