北航201303学期算法与数据结构作业1答案

作业1单项选择题第1题一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树。如果按层次顺序从1开始对全部结点编号，问编号为n的结点的父结点（若存在）的编号是多少？（）A、2n-1B、Kn-1C、KD、1+2+3+…+K答案：B第2题文件的基本组织方式有：（）。A、顺序组织、索引组织、散列组织和链接方式B、磁盘组织、磁带组织C、数据库组织D、关键字与非关键字答案：A第3题一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树。如果按层次顺序从1开始对全部结点编号，问各层的结点数是多少？（）。A、第i层的结点数2i-1B、第i层的结点数Ki-1C、第i层的结点数是KD、第i层的结点数是1+2+3+…+K答案：B第4题下一段程序实现的功能是打印以h为头节点的单链表中的所有节点，哪一段程序是正确的：（）。A、p=hwhile(p!=NULL){printf(p-data)p=p-next}B、while(h!=NULL){printf(h-data)h=h-next}C、p=hwhile(p!=NULL){p=p-nextprintf(p-data)}D、p=hwhile(p－next!=NULL){p=p-nextprintf(p-data)}答案：A多项选择题第5题下述陈述中哪一项是正确的():A、文件是由记录组成的集合B、记录是文件存取的基本单位C、文件是由数据项组成的D、数据项有时也被称之为字段答案：B|D第6题稀疏矩阵的存贮结构要满足哪些条件？()A、每个非零元素存贮其行号、列号以及值B、存贮矩阵的行数和列数C、所有的非零元素以行优先的排列规则存贮D、只存贮上三角的元素E、只存贮下三角的元素答案：A|B|C第7题下列排序算法中哪些是不稳定的():A、昌泡排序B、选择排序C、快速排序D、堆排序答案：B|C|D第8题一棵含有25个结点的完全二叉树的深度是多少():A、4B、5C、6D、log225答案：A|D判断题第9题在单向链表中，在X指向的结点后插入结点，对应的方法与X是否是头指针无关。答案：错误第10题一棵度为2的树是一棵二叉树。答案：错误第11题在求最短路径的Dijkstra算法和Floyd算法中，Dijkstra算法只能求从一点到其他各点的最短路径，而Floyd算法可以求图中两两点之间的最短路径。答案：错误第12题有人采用Haffman树进行编码后，由于每个符号的代码长度不等，当接收方收到编码后的内容后，不能转换为原来的正文。该说法是否正确？答案：正确填空题第13题在邻接矩阵表示图的情况下，图中第j个结点的入度是矩阵中第___非零元素的个数。答案：j列第14题用索引的方法组织文件时，在文件本身的主文件之外，建立一张索引表，它描述了___之间的一一对应关系。主文件与索引表一起构成索引文件。答案：逻辑记录与物理记录第15题在求图的最小代价生成树中，有两种算法，它们分别是___和___。答案：Prim，Kruskal第16题与内查找相对应的另一类查找称之为___。答案：外查找问答题第17题说明链表结构中头指针、头结点和开始结点的概念区别，并说明头指针和头结点的作用。答案：在链表结构中，头指针是指向链表中第一个结点，头结点是为了链表操作的方便性，需要在单链表中第一个节点之前附加节点，开始结点是链表中真正存贮数据的第一个结点。链表由头指针确定，丢失头指针，有可能丢失整个链表，增加头结点的目的是使得在单向链表中的插入操作统一。第18题试描述数据结构的概念与程序设计语言中数据类型概念的区别。答案：数据类型定义了一组按某些关系结合在一起的数据元素；数据结构不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。第19题说明栈与队列的异同点。答案：栈与队列均是特定的线性表，但栈的操作只能在线性表的一端进行，而队列的插入与删除分别在线性表的两端进行，栈表现为元素先进后出，队列表现为元素的先进先出。第20题试写出求循环队列长度的算法。答案：//ｎ是存贮空间的长度，队头指针为front,队尾指针为rearintQueueLen(Q){intl=0,f=front;while(f!=rear){f=(f+1)modn;;l++;}returnl;}