东大17春学期《数据结构Ⅰ》在线作业2.doc

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

1、17秋东北大学东大17春学期《数据结构Ⅰ》在线作业2一、单选题(共20道试题，共100分。)1。索引非顺序文件的特点是A.主文件无序，索引表有序B.主文件有序，索引表无序C。主文件有序，索引表有序D.主文件无序，索引表无序正确答案：2.在计算机内实现递归算法时所需的辅助数据结构是A。栈B.队列C。树D.图正确答案:3.在一棵高度为k的满二叉树中,结点总数为A.2k—1B.2kC.2k-1D.log2k？+1正确答案：4。ISAM文件和VSAM文件的区别之一是A.前者是索引顺序文件，后者是索引非顺序文件B.前者只能进行顺序存取，后者只能进行随机存取C。前者建立静态索引结构，后者建

2、立动态索引结构D。前者的存储介质是磁盘,后者的存储介质不是磁盘正确答案:5.在VSAM文件的控制区间中，记录的存储方式为A。无序顺序B。有序顺序C。无序链接D.有序链接正确答案：6。下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是A。分块查找B.顺序查找C.二分查找D。散列查找正确答案：7.设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是　　　　　s-〉next=p—〉next；p—>next=s；t=p—>data；p->data=s->data；s—>data=t;A。结点p与结点s的数据域互换B.在p所指结点的元素之前插入元素C.在p所指

3、结点的元素之后插入元素D.在结点p之前插入结点s正确答案：8。用有向无环图描述表达式（A+B)*（（A+B）/A),至少需要顶点的数目为A。5B.6C.8D。9正确答案：9。在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为A。O（n）B。O(n+e）C.O（n2)D.O（n3）正确答案:10.一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为A.O（n）B。O(e）C。O(n+e）D.O(n2)正确答案：11。除第一层外,满二叉树中每一层结点个数是上一层结点个数的A.1/2倍B.1倍C。2倍D.3倍正确答案：12。

4、若数组s[0.。n-1］为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作,则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为A.1和n+1B。1和n/2C。－1和nD。－1和n+1正确答案:13.设哈希表长为14，哈希函数H(key）=key%11,表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是A。8B。3C.5D.9正确答案：14.若〈vi,vj>是有向图的一条边,则称A.vi邻接于vjB.vj邻接于viC。vi和vj相互邻接D。vi与vj—

5、不相邻接正确答案:15.在一个单链表中，已知q结点是p结点的前驱结点，若在q和p之间插入结点s，则执行操作A。s-〉next=p->next;p->next=s;B.s—>next=p；q->next=sC。q—>next=s；s—>next=p;D。p—〉next=s；s—〉next=q；D。q—〉next=s;s->next=p；D。p—〉next=s;s->next=q；正确答案：16.若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为A.n-1B.?n/m?-1C。é（n—1）/（m—1）ùD.én/(m-1)ù-1正确答案：17。可有效提高次关键字查找效率的文

6、件是A.顺序文件B.倒排文件C.散列文件D。VSAM文件正确答案：18。若一个有向图的邻接距阵中，主对角线以下的元素均为零，则该图的拓扑有序序列A.一定存在B.一定不存在C。不一定存在D。不确定正确答案：19。如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是A.有向完全图B.连通图C。强连通图D。有向无环图正确答案：20.n个顶点的强连通图中至少含有A.n—1条有向边B。n条有向边C。n(n-1）/2条有向边D.n(n-1）条有向边正确答案：