《[作业与试题集]东大20年7月考试《数据结构Ⅱ》考核作业【标准答案】》由会员分享，可在线阅读，更多相关《[作业与试题集]东大20年7月考试《数据结构Ⅱ》考核作业【标准答案】（2页珍藏版）》请在金锄头文库上搜索。
1、东大20年7月考试数据结构考核作业【标准答案】东 北 大 学 继 续 教 育 学 院数据结构II 试 卷（作业考核 线上1） A 卷学习中心： 院校学号： 姓名（共 6 页）总分 题号 一 二 三 四 五 六 七 八 九 十得分一、单选题（共30题，每题2分） 1抽象数据类型的三个组成部分分别为A数据对象、数据关系和基本操作B数据元素、逻辑结构和存储结构C数据项、数据元素和数据类型D数据元素、数据结构和数据类型 2要求相同逻辑结构的数据元素具有相同的特性，其含义为A. 数据元素具有同一的特点B. 不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致C. 每个数据元素都一样D. 仅需
2、要数据元素包含的数据项的个数相同 3下列各式中，按增长率由小至大的顺序正确排列的是A ，n！，2n ，n3/2Bn3/2，2n，nlogn，2100C2n，log n，nlogn，n3/2D2100，logn, 2n, nn 4. 在下列哪种情况下，线性表应当采用链表表示为宜A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变 5设指针p指向双链表的某一结点，则双链表结构的对称性是A. p-B. p-C. p-D. p- 6. 已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点
3、，则在s所指结点之后插入上述链表应执行的语句为A. s-A. V1V2V3V4V5 B. V1V2V3V5V4C. V1V4V3V5V2 D.V1V3V4V5V2 21关键路径是事件结点网络中A从源点到汇点的最长路径 B从源点到汇点的最短路径C最长的回路 D最短的回路 22设哈希表长为14，哈希函数H(key)=key11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是A8 B3 C5 D9 23.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1
4、，则应调整以使其平衡，所作的平衡旋转是A. LL型 B. LR型 C. RL型 D. RR型 24下列排序算法中，在待排序数据已基本有序时，效率最高的排序方法是A插入排序 B选择排序C快速排序 D堆排序 25下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)是A. 堆排序 B. 冒泡排序C. 直接选择排序 D. 快速排序 26. 有一程序段:i=1；WHILE(i（1）/ k取值while( k / whileif (p q = L-32一个仅包含二元运算符的算术表达式，以二叉链表形式存储在二叉树T中，设计算法F1实现求值，并指出遍历的方式。33设计算法实现以逆邻接表为存储结构的有向图的拓扑排序。逆邻接表存储结构定义如下：顶点结构 表结点结构vexdata firstinadjvex nfo firstarc34. 设哈希表长为13，采用线性探测法解决冲突，哈希函数定义为：H(key)=key%13。试求：（1）填上依次插入关键字25，20，36，15，41，52，29，72，67后的哈希表。（2）计算等概率情况下，查找成功的平均查找长度。
