《2017年北京交通大学计算机与信息技术学院926数据结构与软件工程之数据结构考研导师圈点必考题汇编.doc》由会员分享，可在线阅读，更多相关《2017年北京交通大学计算机与信息技术学院926数据结构与软件工程之数据结构考研导师圈点必考题汇编.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年北京交通大学计算机与信息技术学院926数据结构与软件工程之数据结构考研导师圈点必考题汇编一、填空题1 实现字符串拷贝的函数strcpy 为： 【答案】 2 若用n 表示图中顶点数目，则有_条边的无向图成为完全图。【答案】n （n-l ）/2【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。3 已知二维数组中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，【答案】1196【解析】设元素的行标为i ，列标为j 。则它的存储位置为： 4 模式串的next
2、 函数值序列为_。【答案】01122312 5 数组的存储结构采用_存储方式。【答案】顺序存储结构【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。6 以下是用类C 语言写山的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶head 为双向循坏链表的头指针。 指针为top , P , t 为辅助指针，试填充算法中的空格，使算法完整。void leafchain（BiTree Abt）
3、p=BiTree）malloc （sizeof （BiTNode ）; If （!p ）print（“OVERFLOWn”; exit （1）; head=p; top=0; if （bt ）第 2 页，共 50 页的地址是：_。 top+; stacktop=bt; while （top ）t=stacktop; top-;if （it-Lchild & !t-Rchild） （1） ; （2） ; （3） ; else if（ （4） ）top+; stacktop= （5） ; if （ （6） ）top+; stacktop= （5） ; （8） ; （9） ; 【答案】p-Rchil
4、d=t:t-Lchild=p:p=t: t-Rchild!=null:t-Rchild: t-Lchild!=null: t-Lchild: p-Rchild=head:head-Lchild=p 7 设有一个10阶对称矩阵A 采用压缩存储方式， （以行为主序存储：）则的地址为_。【答案】33【解析】设存储的元素的行标为i ，列标为j 。若则的地址为 将代入得33。则的地址为若8 一个算法具有5个特性：_、_、_、有零个或多个输入、有一个或多个输出。【答案】有穷性；确定性；可行性 9 阅读下列程序说明和裎序，填充程序中的_。【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所
5、示（编科略）本程序采用非递归的方法，设立一个堆栈交换左、右子树的算法为：（1）把根结点放入堆栈。（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。 存放还没有转换过的结点，它的栈顶指针为。 （1） （2）If （ （3） ） 第 3 页，共 50 页【答案】【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈足否为空，如果不为空，则取栈顶元素，交换取出节点的左右指针。并将左右指针分别进桟，重复这一操作。完成二叉树左右孩子的交换。 10抽象数据类型的定义仅取决于它的一组_，而与_无关, 即不论其内部
6、结构如何变化，只要它的_不变，都不影响其外部使用。【答案】逻辑特性；在计算机内部如何表示和实现；数学特性 11若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_和记录的_，【答案】比较；移动 12己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_次查找成功，查找47时_成功，查找100时，需_次才能确定不成功。【答案】2；4；3【解析】二分法查找元素次数列表 查找100是找到115就停止了。 13在单链表中设置头结点的作用是_。【答案】方便运算 14完善算法：求KMP 算法.next 数组。 END ； 【答案】 15根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_和_; 而又根据指针的连接方式，链表又可分成_和_。【答案】单链表；双链表；（动态）链表；静态链表【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针第 4 页，共 50 页一、填空题考研试题
