201309学期算法与数据结构作业1

《201309学期算法与数据结构作业1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、201309学期算法与数据结构作业1单项选择题第1题算法的时间复杂度的表示方法是：（）。A、实现算法的程序在指定机器上执行的时间B、标准程序在机器上的执行时间C、基本操作重复次数，即问题规模n的某个函数D、与刻画基本操作重复次数的函数同阶无穷大的函数f(n)答案：D第2题在一个双向链表中，假设结点的域分别为left,right,以及data。其中left、right分别为两个链域，data是数据域。下一段程序是实现在h结点之后插入p结点的功能，其中h结点不空，h的下一个结点亦不空。判断哪一段程序是正确的：（）。A、p

2、->right=h->rightp->left=hh->right=pp->right->right=pB、p->right=h->rightp->left=hh->right=pp->right->left=pC、h->right=pp->left=hp->right=h->rightp->right->left=pD、p->right=h->rightp->left=hh->right=ph->right->left=p答案：B第3题一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层上每个结点

3、都有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->n

4、extprintf(p->data)}D、p=hwhile(p－>next!=NULL){p=p->nextprintf(p->data)}答案：A第5题为了区别循环队列中队满与队空的条件，采用的方法是：（）。A、不需要特别的方法B、牺牲一个存贮空间C、把队头永远放到队尾的前端D、每次出队后，移动数据答案：B第6题最好情况下插入排序的比较次数是：（）。A、O(n)B、nC、n-1D、O(n*n)答案：C第7题在树中，树的度与结点的度之间的关系是：（）。A、树的度就是结点的度B、树的度为2，结点的度可以是0，1和2C、

5、结点度中最大值为树的度D、树的度与结点的度无关答案：C第8题一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树。如果按层次顺序从1开始对全部结点编号，问编号为n的结点的父结点（若存在）的编号是多少？（）A、2n-1B、Kn-1C、KD、1+2+3+…+K答案：B第9题文件的基本组织方式有：（）。A、顺序组织、索引组织、散列组织和链接方式B、磁盘组织、磁带组织C、数据库组织D、关键字与非关键字答案：A第10题通过链表存贮树时，如果给定树中结点的个数，则链域浪费的空间随树的度

6、增加而：（）。A、增加B、减少C、不变D、无规律答案：A判断题第11题线性表中的元素只能是简单类型。答案：错误第12题指针就是地址，有人在数组中采用指示下标值的方法实现单向链表。另外的人说这不是链表结构，他的说法对吗？答案：错误第13题在求最短路径的Dijkstra算法和Floyd算法中，Dijkstra算法只能求从一点到其他各点的最短路径，而Floyd算法可以求图中两两点之间的最短路径。答案：错误第14题有人采用Haffman树进行编码后，由于每个符号的代码长度不等，当接收方收到编码后的内容后，不能转换为原来的正文

7、。该说法是否正确？答案：正确第15题线性结构中，每个点至多有一个前趋和一个后继，树中一个结点至多有一个前趋和多个后继，图中的结点可以有多个前趋和多个后继。答案：正确第16题线性表是数组。答案：错误第17题栈满是数据对象栈的固有操作。答案：错误第18题在单向链表中，在X指向的结点后插入结点，对应的方法与X是否是头指针无关。答案：错误第19题一棵度为2的树是一棵二叉树。答案：错误第20题希尔排序是稳定的。答案：错误