东大18春学期《数据结构Ⅱ》在线作业1

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

1、东大18春学期《数据结构Ⅱ》在线作业11、D2、B3、D4、D5、A一、单选题共20题，100分1、连通网的最小生成树是其所有生成树中A顶点集最小的生成树B边集最小的生成树C顶点权值之和最小的生成树D边的权值之和最小的生成树正确答案是：D2、通常将链串的结点大小设置为大于1是为了A提高串匹配效率B提高存储密度C便于插入操作D便于删除操作正确答案是：B3、设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是AA，B，C，DBD，C，B，ACA，C，D，BDD，A，B，C正确答案是：D4、已知一组关键字为{25,48,36,72,79,82,23,4

2、0,16,35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是A.{25,36,48,72,23,40,79,82,16,35}B.{25,36,48,72,16,23,40,79,82,35}C.{25,36,48,72,16,23,35,40,79,82}D.{16,23,25,35,36,40,48,72,79,82}正确答案是：D5、在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是A访问第i个元素的前驱B在第i个元素之后插入一个新元素C删除第i个元素D对顺序表中元素进行排序正确答案是：A6、下列编码中属于前缀编码的是A{1,01,

3、000,001}B{1,01,011,010}C{0,10,110,11}D{0,1,00,11}正确答案是：A7、按排序过程中依据的原则分类，快速排序属于A插入类的排序方法B选择类的排序方法C交换类的排序方法D归并类的排序方法正确答案是：C8、ISAM文件和VSAM文件的区别之一是A前者是索引顺序文件，后者是索引非顺序文件B前者只能进行顺序存取，后者只能进行随机存取C前者建立静态索引结构，后者建立动态索引结构D前者的存储介质是磁盘，后者的存储介质不是磁盘正确答案是：C9、设给定权值总数有n个，其哈夫曼树的结点总数为A不确定B2nC2n+1D2n-1正确答案是：D1

4、0、设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为A5B6C7D8正确答案是：D11、若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为Af,c,bBf,d,bCg,c,bDg,d,b正确答案是：A12、二叉树中第5层上的结点个数最多为A8B15C16D32正确答案是：C13、若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为AX的双亲BX的右子树中最左的结点CX的左子树中最右结点DX的左子树中最右叶结点正确答案是：C14、链栈与顺序栈相比，

5、比较明显的优点是A插入操作更加方便B删除操作更加方便C不会出现下溢的情况D不会出现上溢的情况正确答案是：D15、一棵完全二叉树上有1001个结点，其中叶子结点的个数是A250B500C254D以上答案都不对正确答案是：D16、若数组s[0..n-1]为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为A1和n+1B1和n/2C－1和nD－1和n+1正确答案是：C17、二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A［1］［1］的存储地址为420，A［3

6、］［3］的存储地址为446，则A［5］［5］的存储地址为A470B471C472D473正确答案是：C18、某带头结点的单链表的头指针为head，判定该链表为非空的条件是Ahead==NULLBhead->next==NULLChead!=NULLDhead->next!=NULL正确答案是：B19、在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head,则Ap指向头结点Bp指向尾结点Cp的直接后继是头结点DP的直接后继是尾结点正确答案是：D20、ISAM文件的周期性整理是为了空出A磁道索引B柱面索引C柱面基本区

7、D柱面溢出区正确答案是：D