HYPERLINK"http://202.43.154.166/entity/function/homeworkpaper/homeworkpaper_info.jsp?paperId=4613"\t"_blank"201209学期算法与数据结构作业2单项选择题第1题一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树。如果按层次顺序从1开始对全部结点编号，问编号为n的结点的父结点（若存在）的编号是多少？（）A、2n-1B、Kn-1C、KD、1+2+3+…+K答案：B第2题下一段程序实现的功能是打印以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第3题文件的基本组织方式有：（）。A、顺序组织、索引组织、散列组织和链接方式B、磁盘组织、磁带组织C、数据库组织D、关键字与非关键字答案：A第4题为了区别循环队列中队满与队空的条件，采用的方法是：（）。A、不需要特别的方法B、牺牲一个存贮空间C、把队头永远放到队尾的前端D、每次出队后，移动数据答案：B第5题通过链表存贮树时，如果给定树中结点的个数，则链域浪费的空间随树的度增加而：（）。A、增加B、减少C、不变D、无规律答案：A判断题第6题拓扑排序是图的另一种遍历。答案：正确第7题有人采用Haffman树进行编码后，由于每个符号的代码长度不等，当接收方收到编码后的内容后，不能转换为原来的正文。该说法是否正确？答案：正确第8题一棵度为2的树是一棵二叉树。答案：错误第9题线性结构中，每个点至多有一个前趋和一个后继，树中一个结点至多有一个前趋和多个后继，图中的结点可以有多个前趋和多个后继。答案：正确第10题希尔排序是稳定的。答案：错误填空题第11题在数组a中存贮有线性表，数组长度为n，如果在每一个位置上插入元素的概率相同，则插入一个元素平均需要移动___个元素，因此，其时间复杂度为___。答案：n(n+1)/2，O(n)第12题在求图的最小代价生成树中，有两种算法，它们分别是___和___。答案：Prim，Kruskal第13题在邻接矩阵表示图的情况下，图中第j个结点的入度是矩阵中第___非零元素的个数。答案：j列第14题与内查找相对应的另一类查找称之为___。答案：外查找第15题用索引的方法组织文件时，在文件本身的主文件之外，建立一张索引表，它描述了___之间的一一对应关系。主文件与索引表一起构成索引文件。答案：逻辑记录与物理记录问答题第16题说明栈与队列的异同点。答案：栈与队列均是特定的线性表，但栈的操作只能在线性表的一端进行，而队列的插入与删除分别在线性表的两端进行，栈表现为元素先进后出，队列表现为元素的先进先出。第17题说明链表结构中头指针、头结点和开始结点的概念区别，并说明头指针和头结点的作用。答案：在链表结构中，头指针是指向链表中第一个结点，头结点是为了链表操作的方便性，需要在单链表中第一个节点之前附加节点，开始结点是链表中真正存贮数据的第一个结点。链表由头指针确定，丢失头指针，有可能丢失整个链表，增加头结点的目的是使得在单向链表中的插入操作统一。第18题试写出求循环队列长度的算法。答案：//ｎ是存贮空间的长度，队头指针为front,队尾指针为rearintQueueLen(Q){intl=0,f=front;while(f!=rear){f=(f+1)modn;;l++;}returnl;}第19题试描述数据结构的概念与程序设计语言中数据类型概念的区别。答案：数据类型定义了一组按某些关系结合在一起的数据元素；数据结构不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。第20题什么是关键路径。答案：在AOE网中，我们把从源点到汇点的最长路径长度称为关键路径。