《2017年上海大学机电工程与自动化学院834计算机科学专业基础综合之数据结构考研导师圈点必考题汇编.doc》由会员分享，可在线阅读，更多相关《2017年上海大学机电工程与自动化学院834计算机科学专业基础综合之数据结构考研导师圈点必考题汇编.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年上海大学机电工程与自动化学院834计算机科学专业基础综合之数据结构考研导师圈点必考题汇编一、填空题1 在拓扑分类中，拓扑序列的最后一个顶点必定是_的顶点。【答案】出度为0【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。 2 试利用下列栈和串的基本操作完成下述填空题。initstack （S ） 置S 为空找； push （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （S ） 返回栈顶元素； sempty （S ） 判找空函数； 置串 判串 返回联接empty （st ） 判串空
2、函数 若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。） 第 2 页，共 51 页为空串；是否相等的函数； 之后的串；length （st ） 返回串st 的长度； sub （S , i , 1） 返回S 中第i 个字符； 注意：毎个空格只填一个语句。 【答案】（1）（2）（3）（4）（5）（6）（7）exp （8）（9）exp （10）（11）（12）取栈顶操作符 操作符取出后，出栈将pre 的最后一个字符（操作数）加入到中缀式exp 的最后若ch 是操作数
3、且栈非空，则形成部分中缀表达式栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符如ch 是运算符，则入操作符栈s 判栈8是否为空若读出ch 是操作数且栈为空，则按出错处理 3 从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_，_和_。B+树适用于组织_的索引结构，m阶个关键码。【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织； 4 求REPLACE （S ，V , m ）=_
4、。【答案】 5 一个算法具有5个特性：_、_、_、有零个或多个输入、有一个或多个输出。【答案】有穷性；确定性；可行性 6 索引顺序文件既可以顺序存取，也可以_存取。【答案】随机已 知树每个结点至多有_个儿子，除根结点外每个结点至少有_个儿子，根结点至少有_个儿子，有k 个儿子的结点必有_第 3 页，共 51 页 7 在哈希函数中，P 值最好取_。【答案】小于等于表长的最大素数或不包含小于20的质因子的合数【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。 8 在有n 个顶点的有向图中，每个顶点的度最大
5、可达。【答案】2（n-l ）【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。9 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_个，单链表为_个。【答案】4; 2 10设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_，又称P 为_。【答案】模式匹配；模式串二、选择题11若磁盘转速为7200转/分，平均寻道时间为8ms , 每个磁道包含1000个扇区，则访问一个扇区的平均存取时间大约是（ ）。A. B. C. D. 【答案】B【解析】磁盘的平均寻址时间包括平均寻道时间和平均等待时间。平均寻道时间为8ms , 平均等待时间与磁盘转速有关，为因此总的时间为： 12线性表的顺序存储结构是一种（ ）。A. 随机存取的存储结构 B. 顺序存取的存储结构 C. 索引存取的存储结构 D.Hash 存取的存储结构 【答案】A【解析】线性表包括顺序存储结构和链式存储结构，顺序存储结构能够随机存取表中的元素，但插入和删除操作较麻烦，链式存储结构不能随机访问表中的元素，但是能够表示元素之间的先后次序，而且插入和删除操作较容易。 磁盘的存取一个扇区的时间为 第 4 页，共 51 页一、填空题考研试题
