数据结构试题（一）

1、数据结构试题（一）一、选择题（共20分，每题1分）1从逻辑上可以把数据结构分为两大类,分别是（）。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构2.下面给出的四种排序法中( )排序法是不稳定的排序法。A. 插入 B. 冒泡 C. 二路归并 D. 堆排序3. 线性表是具有n个（）的有限序列（n>0）。 A表元素 B字符 C数据元素 D数据项4.在下面的程序段中，对x的赋值语句的频度为（ ）FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+50;A O(2n) BO(n) CO(n2) DO(log2n) 5. 下述哪一

2、条是顺序存储结构的优点？（ ）A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示6. 栈是一种（ ）的线性表。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序7. 设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。A. 4，3，1，2， B. 2，1，3，4， C. 1，4，3，2， D. 1，2，4，3，8. 双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（ ） A. p.llink:=q; q.rlink:=p; p.llink.rl

3、ink:=q; q.llink:=p.llink;B. q.llink:=p.llink; p.llink.rlink:=q; q.rlink:=p; p.llink:=q.rlink; C. q.rlink:=p; p.rlink:=q; p.llink.rlink:=q; q.rlink:=p;D. p.llink.rlink:=q; q.rlink:=p; q.llink:=p.llink; p.llink:=q;9设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表10. 树是结点

4、的有限集合，一棵非空的树它有（ ）根结点。A. 有0个或1个 B. 有0个或多个 C. 有且只有一个 D. 有1个或1个以上11设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）A求子串 B联接 C求串长 D匹配 12已知串S=aaab,其Next数组值为（ ）。A0123 B0012 C1231 D121113. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A不确定 B2n C2n+1 D2n-114. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）Am-n Bm-n-1 Cn+1 D条件不足

5、，无法确定15. 深度为h的满m叉树的第k层有（ ）个结点。(1=<k=<h)Amk-1 Bmk-1 Cmh-1 Dmh-116.树的后根遍历序列等同于该树对应的二叉树的( ). A. 先序序列 B. 中序序列 C. 后序序列 D.没有对应关系17. 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。AFEDCBA BCBEFDA C CBEDFA D不确定 18.在图的理论与应用中，关键路径是事件结点网络中（ ）。A从源点到汇点的最长路径 B从源点到汇点的最短路径C最长回路 D最短回路19.在一个有向图中，所有顶点的入度之和等于所有

6、顶点出度之和的（ ）倍。A1/2 B2 C1 D420.下列哪一种图的邻接矩阵是对称矩阵？（ ）A有向图 B无向图 CAOV网 DAOE网二、填空题（共30分，每空2分）1. 一棵具有 n个结点的完全二叉树的树高度（深度）是 （1）。2. 数据结构分别为逻辑结构、存储结构（物理结构），逻辑结构有分为四类基本结构，分别是（2）、（3）、（4）、（5）。存储结构（物理结构）又分为（6）存储结构和（7）存储结构。逻辑上（逻辑结构：数据元素之间的逻辑关系）可以把数据结构分成（8）结构和（9）结构。3. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（10）4. 树是结点的有

7、限集合, 树是由根结点和若干颗子树构成的。一个节点含有的子树的个数称为该节点（11）；一棵树高为K的完全二叉树至少有（12）个结点；高度为 K的二叉树最大的结点数为（13）。5. 霍夫曼树是一种带权路径最（14）的树，在一个度为m的霍夫曼树中，其叶结点个数为n，则非叶结点的个数为 （15）。三、简答题（共60分）1.（5分）如图1所示的二叉树，请分别写出中序和后序遍历序列。 图1 第一题图 图2第二题图2 .（5分）对于图2所示的无向带权图，构造最小生成树。3.（8分）什么是拓扑排序？简述AOV网的含义。4.（8分）有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,

8、3,4,7,8,9，试构造一棵哈夫曼树，并计算其加权路径长度WPL。5.（8分）（1）如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有多少条边？（2）如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少有多少条边？6.（8分）关键字序列 T=(21，25，49，25*，16，08），请写出一趟快速排序的结果。该排序方法是稳定的吗？为什么？7. （8分）简述关键路径的求解步骤。8. （10分）已知关键字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 ，设定哈希函数 H(key) = key MOD 11，请构造哈希表，利用线性探测再散列 di = cÍi ，其中 c=1解决冲突,并计算平均查找长度ASL。四、设计题（共40分）1. （20分）设计算法，求用顺序结构存储的串s和串t的一个最长公共子串。其中，串s用i指针(1<=i<=s.len)。t串用j指针(1<=j<=t.len)。（伪代码即可，要求表达描述清晰）2. （20分）医院选址问题：4个村庄之间的交通图如图所示，村庄之间的距离如图中各边上的权值所示。现在要从这4个村庄中选择