《2017年华南师范大学计算机学院925数据结构考研冲刺密押题.doc》由会员分享，可在线阅读，更多相关《2017年华南师范大学计算机学院925数据结构考研冲刺密押题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年华南师范大学计算机学院925数据结构考研冲刺密押题一、填空题1 在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_。【答案】 【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，所以2 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_、_、_、_。【答案】3 设广义表则 是_tail（L ）是_；L 的长度是_；深度是_。；2；2 【答案】（ ）（ ）【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表
2、；表的长度指表中元素的个数；表的深度指展开后括号的层数。 4 有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_。（3在4之前出栈）【答案】3个【解析】以3, 4先出栈的序列有34521、34215、34251共3个。 5 执行顺序查找时，存储方式可以是_，折半查找时，要求线性表_，分块查找时要求线性表_，而哈希表的查找，要求线性表的存储方式是_。【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储6 在n 个顶点的非空无向图中，最多有_个连通分量。【答案】n【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。7
3、 从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_，_和_。B+树适用于组织_的索引结构，m阶个关键码。【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织； 8 设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_，而栈顶指针值是_。设栈为顺序栈，每个元
4、素占4个字节。【答案】23; 100CH 9 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_次探测。【答案】 【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为 10在单链表L 中，指针P 所指结点有后继结点的条件是_【答案】 【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。树每个结点至多有_个儿子，除根结点外每个结点至少有_个儿子，根结点至少有_个儿子，有k 个儿子的结点必有_二、算法设计题11用邻接多重表存储结构，编写FIRST-ADJ （G ，V ）函数，函数返回
5、值为第一个邻接点，若V 没有邻接点，返回零。【答案】算法如下： /在邻接多重表g 中，求v 的第一邻接点, 若存在，返回第一邻接点，否则返回0（/确定顶点v 在邻接多重表向量中的下标, 不考虑不存在v 的情况/取第一个边结点 /返回第一邻接点，ivex 和jvex 中必有一个等干i 12假设串的存储结构如下所示，编写算法实现串的置换操作。 【答案】算法如下： 和t 是用一维数组存储的串，本算法将s 串第i 个字符开始连续j 个字符用t 串置换，操作成功返回1, 否则返回0表示失败 13设在4地之间架设有6座桥，如图所示。 图要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。 （1）试就以上图形说明：此问题有解的条件是什么？ （2）设图中的顶点数为n ，试用C 或一个算法，找出满足要求的一条回路。【答案】语言描述与求解此问题有关的数据结构并编写一、填空题考研试题
