《2017年华南师范大学计算机学院925数据结构考研题库.doc》由会员分享，可在线阅读，更多相关《2017年华南师范大学计算机学院925数据结构考研题库.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年华南师范大学计算机学院925数据结构考研题库一、填空题1 组成串的数据元素只能是_。【答案】字符2 设数组储，则元素为_。【答案】9174；8788【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，则它的存储地址为若以列序为主存储顺序，则它的存储地址为 3 从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_，_和_。B+树适用于组织_的索引结构，m阶个关键码。【答案】数据库；文
2、本；顺序组织；随机组织；链组织；随机组织； 4 中缀式运算结果为_。【答案】 【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。 5 阅读下列程序说明和裎序，填充程序中的_。【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编科略）本程序采用非递归的方法，设立一个堆栈交换左、右子树的算法为：（1）把根结点放入堆栈。（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。 存放还没有转换过的结点，它的栈顶指针为。对应的前缀式为_，若则后缀式 的树每个结点至多有_个儿子，除根结点外每个结点
3、至少有_个儿子，根结点至少有_个儿子，有k 个儿子的结点必有_的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存的存储地址为_；若以列序为主序顺序存储，则元素的存储地址 （1） （2）If （ （3） ） 【答案】 【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈足否为空，如果不为空，则取栈顶元素，交换取出节点的左右指针。并将左右指针分别进桟，重复这一操作。完成二叉树左右孩子的交换。 6 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_个结点。【答案】 【解析】哈夫曼树只有度为0和2的节点。7 已知链队列的头尾指针分别是f 和r , 则将值x 入队的
4、操作序列是_。【答案】 【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。8 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_次；当使用监视哨时，若查找失败，则比较关键字的次数为_。【答案】 【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。 9 在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_。【答案】 【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，所以10对单链表中元素按插入方法
5、排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。 【答案】（1）（2）（3）（4）（5） 置空链表，然后将原链表结点逐个插入到有序表中当链表尚未到尾，p 为工作指针查P 结点在链表中的插入位置，这时q 是工作指针将P 结点链入链表中是q 的前驱，u 是下个待插入结点的指针二、算法设计题11写算法将单链表11拆成二个链表，其中以11为头的链表保持原来向后的链接，另一个链表的头为12，其链接方向与11相反，11包含原链表的奇数序号的结点，12包含原链表的偶数序号的结点。【答案】算法如下： 12给定矩阵并设 设计一算法判定x 的值是否在A 中，要求时间复杂度为 【答案】算法如下： 一、填空题考研试题
