《2010湖南城市学院数据结构试卷a》由会员分享，可在线阅读，更多相关《2010湖南城市学院数据结构试卷a（3页珍藏版）》请在金锄头文库上搜索。
1、班级_ 学号_ 姓名_ （第 页， 共 页） -密-封-线-密-封-线-密-封-线-密-封-线-密-封-线-密-封-线-密-封-线-密-封-线-湖 南 城 市 学 院20092010 学年 第 1 期数据结构试卷A 卷 时间： 120 分钟 年级专业班级：0906601-02-03 【考试】 【闭卷】题型一二三四五六七八九十总分分数1020302416得分评卷人： 合分人： 核查人：一、判断题（共 10 分，每小题 1 分）得 分 （X ）1、数据元素是数据的最小单位。（X ）2、串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中符构成的有限序列。 （X ）3、子串定位函数的
2、时间复杂度在最坏情况下为 O（n*m），因此子串定位函数没有实际使用的价值。 （X ）4、在线性链表中删除中间的结点时，只需将被删结点释放。（X ）5、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（ ）6、递归定义的数据结构通常用递归算法来实现对它的操作。（ ）7、在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和按层遍历，则具有相同的结果。（ ）8、已知指针 P 指向键表 L 的某结点，执行语句 P=P-next 不会删除该链表中的结点。 （ ）9、对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。 （ ）10、进行折半搜索的表必须是顺序
3、存储的有序表。二、填空题（共 20 分，每空 1 分）得 分 1、数据结构被形式地定义为（D, R），其中 D 是数据元素的有限集合，R 是 D 上的 关系 有限集合。2、算法的五个重要特性是_ 有穷性 _ , _确定性 _ , _可行性_ _ , _输出性 _ , _ 输入性_。3、在图形结构中，每个结点的前驱结点数和后续结点数可以 任意个 。4、在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 一个 个直接前驱结点，叶子结点没有 后续 结点，其余每个结点的直接后续结点可以 任意个 。5、在具有 n 个单元的循环队列中，队满时共有 n-1 个元素。6、向栈中压入元素的操作是先 移
4、动栈顶指针 ，后 存入元素 。7、 零个字符的串 称为空串； 只有空白字符的串 称为空白串。8、如果含 n 个顶点的图形成一个环，则它有 n 棵生成树。9、有向图中的结点前驱后继关系的特征是 一个节点可能有若干个前驱，也有可能有若干个后继 。10、折半查找的存储结构仅限于_ 顺序存储结构 _，且是_ 有序的 _。三、选择题（共 30 分，每小题 2 分）得 分 1. 一个向量（即一批地址连续的存储单元）第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是_b _。 A. 110 B. 108 C. 100 D. 120 2. 线性表的顺序存储结构是一种_ a_的存储结
5、构，而链式存储结构是一种_ c_ _的存储结构。A随机存取 B索引存取 C顺序存取 D散列存取3. 线性表的逻辑顺序与存储顺序总是一致的，这种说法_b_ _。A. 正确 B. 不正确4设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作_b_。A. 连接 B. 模式匹配C. 求子串 D. 求串长5设串 s1=ABCDEFG，s2=PQRST，函数 con (x,y)返回 x 和 y 串的连接串，subs(s,i,j)返回串 s 的从序号 i 的字符开始的 j 个字符组成的子串，len(s)返回串 s 的长度，则 con (subs (s1,2,len (s2), subs (s1
6、,len (s2),2)的结果串是_d_。 A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF 6. 二维数组 A 中，每个元素 A 的长度为 3 个字节，行下标 i 从 0 到 7，列下标 j 从 0 到9，从首地址 SA 开始连续存放在存储器内，该数组按行存放时，数组元素 A74的起始地址为_c_。 A. SA+141 B. SA+144 C. SA+222 D. SA+225 7. 二维数组 A 中，每个元素 A 的长度为 3 个字节，行下标 i 从 0 到 7，列下标 j 从 0 到9，从首地址 SA 开始连续存放在存储器内，该数组按列存放时，元素 A47
7、的起始地址为_b_。 A. SA+141 B. SA+180 C. SA+222 D. SA+225班级学号_ 姓名_ （第 页， 共 页）-密-封-线-密-封-线-密-封-线-密-封-线-密-封-线-密-封-线-密-封-线-密-封-线-aedbchHf图 1 一棵二叉树jiEB EFA E CDKGHIJ图 6.128. 由于二叉树中每个结点的度最大为 2，所以二叉树是一种特殊的树，这种说法_b_。A. 正确 B. 错误9. 假定在一棵二叉树中，双分支结点数为 15，单分支结点数为 30 个，则叶子结点数为 b 个。 A15 B16 C17 D4710. 按照二叉树的定义，具有 3 个结点的
8、不同形状的二叉树有_c_种。 A. 3 B. 4 C. 5 D. 6 11. 按照二叉树的定义，具有 3 个不同数据结点的不同的二叉树有_c_种。 A. 5 B. 6 C. 30 D. 32 12. 在一个图中，所有顶点的度数之和等于所有边数的_c_倍。 A. 1/2 B. 1 C. 2 D. 4 13任何一个无向连通图的最小生成树 b 。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在14在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_b_倍。 A. 1/2 B. 1 C. 2 D. 4 15. 解决散列法中出现的冲突问题常采用的方法是 d 。A.数字分析法、除余法、平方
9、取中法 B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、多重散列法 D.线性探测法、多重散列法、链地址法四、简答题（共 24 分，每小题 6 分）得 分 1、根据二叉树的定义，具有三个结点的二叉树有 5 种不同的形态，请将它们分别画出。如图 6.10 所示2、.试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答： 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（1？），存储空间利用率高。缺点：插入或删除元素时不方便。2 分链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部
10、分存放结点值，另一部分存放表示结点间关系的指针2 分优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（1），存储空间利用率低。4 分顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。3假设一棵二叉树的先序序列为 EBADCFHGIKJ 和中序序列为 ABCDEFGHIJK。解：方法是：由前序先确定 root，由中序可确定 root 的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定 root 的左右孩子
11、。将他们分别作为新的 root，不断递归，则所有元素都将被唯一确定，问题得解4、画出下列网络的最小生成树。答： 五、综合题（共 16 分，每小题 8 分）得 分 1、由如图 1 所示的二叉树，回答以下问题：（1）画出该二叉树的中序线索二叉树；（2）画出该二叉树的后序线索二叉树；（3）画出该二叉树对应的森林。解：a图 6.10 树形 5 种aaac acccccbbbbbb班级学号_ 姓名_ （第 页， 共 页）-密-封-线-密-封-线-密-封-线-密-封-线-密-封-线-密-封-线-密-封-线-密-封-线-图图8 8. .1 18 8 中中序序和和后后序序线线索索树树j jh hc ce ed df fi ia ab bj jh hc ce ed df fi ia ab bN NU UL LL LN NU UL LL L图 1a 11dhjbkc图 1 对应的森林ief中序线索二叉树如图 1（左）所示；后序线索二叉树如图 1（右）所示；该二叉树转换后的的森林如图 1 所示。2、2、某通讯系统只可能有 A、B、C、D、E、F 6 种字符，其出现的概率分别是0.1、0.4、0.04、0.16、0.19、 0.11，试画出相应的哈夫曼树，并设计哈夫曼编码。（8分）解解：（4 分） 编码：A:1011 B:0 C:1010 D:110 E:111 F:100（4 分）
