答案 东大 20年7月 数据结构II A卷 孟凡荣.docx

1、东 北 大 学 继 续 教 育 学 院数据结构 II 试 卷（作业考核 线上 1）A卷学习中心：院校学号：姓名总分题号一二三四五六七八九十得分（共6页）一、单选题（共 30 题，每题 2 分）A 1抽象数据类型的三个组成部分分别为A数据对象、数据关系和基本操作B数据元素、逻辑结构和存储结构C数据项、数据元素和数据类型D数据元素、数据结构和数据类型 B2要求相同逻辑结构的数据元素具有相同的特性，其含义为A. 数据元素具有同一的特点B. 不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致C. 每个数据元素都一样D. 仅需要数据元素包含的数据项的个数相同D 3下列各式中，按增长率由小至

2、大的顺序正确排列的是A n ，n！，2n ，n3/2Bn3/2，2n，nlogn，2100C2n，log n，nlogn，n3/2 D2100，logn, 2n, nn B4. 在下列哪种情况下，线性表应当采用链表表示为宜A. 经常需要随机地存取元素B. 经常需要进行插入和删除操作C. 表中元素需要占据一片连续的存储空间D.表中元素的个数不变C 5设指针 p 指向双链表的某一结点，则双链表结构的对称性是A. p-prior-next=p-next-next;B. p-prior-prior=p-next-prior;C. p-prior-next=p- next-prior;D. p-next

3、-next= p-prior-prior;课程名称: 数据结构II7 D6. 已知指针 p 和 q 分别指向某带头结点的单链表中第一个结点和最后一个结点。假设指针s 指向另一个单链表中某个结点，则在s 所指结点之后插入上述链表应执行的语句为A. s-next=q；p-next=s-next；B. s-next=p；q-next=s-next；C. p-next=s-next；s-next=q；D. q-next=s-next；s-next=p； A 7. 栈和队列的共同特点是A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点D 8. 对于链队列，在进行插入运算时.A

4、. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D. 头、尾指针可能都要修改B 9设有一个顺序栈的入栈序列是 1、2、3，则 3 个元素都出栈的不同排列个数为A4B5C. 6D. 7 D10设一个栈的输入序列为 A，B，C，D，则借助一个栈所得到的输出序列不可能是AA，B，C，DBD，C，B，AC. A，C，D，BD. D，A，B，C C 11表达式 a*(b+c)-d 的后缀表达式是Aabcd*+-Babc*+d-Cabc+*d-D-+*abcd B12某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是A. 空或只有一个结点B.高度等于其结点数C. 任一结点无左孩子D.任

5、一结点无右孩子 B13下面的说法中正确的是(1) 任何一棵二叉树的叶子结点在种遍历中的相对次序不变。(2)按二叉树定义，具有三个结点的二叉树共有 6 种。A(1)，(2)B(1)C(2)D(1)，(2)都错 B14树有先序遍历和后序遍历，树可以转化为对应的二叉树。下面的说法正确的是A树的后序遍历与其对应的二叉树的先序遍历相同B树的后序遍历与其对应的二叉树的中序遍历相同C树的先序序遍历与其对应的二叉树的中序遍历相同D以上都不对D 15下列说法正确的是(1) 二又树按某种方式线索化后，任一结点均有前趋和后继的线索(2)二叉树的先序遍历序列中，任意一个结点均处于其子孙结点前(3)二叉排序树中任一结点

6、的值大于其左孩子的值，小于右孩子的值A(1)(2)(3)B(1)(2)C(1)(3)D都不对D 16. 二叉树的第k 层的结点数最多为A2k-1B.2K+1C.2K-1D. 2k-1D 17 以 下 说 法 不 正 确 的 是A无向图中的极大连通子图称为连通分量 B连通图的广度优先搜索中一般采用队列来暂存刚访问过的顶点C图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D有向图的遍历不可采用广度优先搜索 B18有向图 G 用邻接矩阵 A 存储，则顶点 i 的入度等于 A 中A. 第i 行 1 的元素之和B. 第 i 列 1 的元素之和C. 第 i 行 0 的元素个数D. 第i 列非 0 的元

7、素个数A 19. 设有 6 个结点的无向图，该图确保是一个连通图的有效边条数至少应是A.5B.6C.7D.8 D20.下图的邻接表中，从顶点V1 出发采用深度优先搜索法遍历该图，则可能的顶点序列是A. V1V2V3V4V5B. V1V2V3V5V4C. V1V4V3V5V2D.V1V3V4V5V2 A 21关键路径是事件结点网络中A从源点到汇点的最长路径B从源点到汇点的最短路径C最长的回路D最短的回路 A22设哈希表长为14，哈希函数H(key)=key11，表中已有数据的关键字为15，38，61， 84，四个，现将关键字为49 的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是A8B

8、3C5D9C 23.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A，并已知 A 的左孩子的平衡因子为 0，右孩子的平衡因子为1，则应调整以使其平衡，所作的平衡旋转是A. LL 型B. LR 型C. RL 型D. RR 型 A24下列排序算法中，在待排序数据已基本有序时，效率最高的排序方法是A插入排序B选择排序C快速排序D堆排序A 25下列排序算法中，时间复杂度不受数据初始状态影响，恒为 0(nlog2n)是A. 堆排序B. 冒泡排序C. 直接选择排序D. 快速排序 B26. 有一程序段:i=1；WHILE(ifront-next=Q-real=NULLB. Q-front=

9、Q-realNULLC. Q-real=Q-front=NULLD. Q-real-next=Q-frontNULL A 28. 有向图G 可拓扑排序的判别条件是A. 不存在环B. 存在环C. 存在入度为零的结点D. 存在出度为零的结点 C29. 对n 个记录的文件进行快速排序，所需要的辅助存储空间A. O（1）B. O（n）C. O（1og2n）D. O（n2） A30. 下列排序算法中，在待排序数据已基本有序时，效率最高的排序方法是A插入排序B选择排序C快速排序D堆排序二、综合题（共 4 题，每题 10 分）31、阅读算法，在横线处填入语句或注释。void exchange_L( Link

10、list &L，int m ) / 带头结点的单链表中前 m 个结点和后n 个结点的整体互换if ( m & L-next ) / 链表非空p = L-next;（1）/ k 取值while( knext; +k; / whileif (p & （3）) / n!=0 时才需要修改指针ha = L-next;/以指针 ha 记a1 结点的位置L-next= p-next; / 将 b1 结点链接在头结点后p-next =（4）;/ 设am 的后继q = L-next; / 令q 指向 b1 结点while (q-next)q = q-next; / 查找 bn 结点q-next =（5）/将第

11、 a1 结点链接到 bn 结点之后 / if(p) / if(m) / exchange_L答案（1）k = 1; （2）查找第am 个结点（3）p-next （4）L-next （5）将第a1 结点链接到b n 结点之后32. 一个仅包含二元运算符的算术表达式，以二叉链表形式存储在二叉树T 中，设计算法F1实现求值，并指出遍历的方式。解： intF1(BiTrec T)if(!T)return 0;if(!Tlchild &!Trchild)/（1）判断是否为叶子结点return (Tdata);Lv= F1(Tlchild);Rv= F1(Trchild); switch(Tdata)/（

12、2）运算case + : V=Lv+Rv;break; case- :V=Lv-Rv;break; case*:V=Lv*Rv;break; case/:V=lv/Rv;break; /switchreturn V;/（3）返回结果/F1算法功能：后序遍历二叉树，求算术表达式的值。33. 设计算法实现以逆邻接表为存储结构的有向图的拓扑排序。逆邻接表存储结构定义如下：vexdatafirstinadjvexnfofirstarc顶点结构表结点结构34. 设哈希表长为 13，采用线性探测法解决冲突，哈希函数定义为：H(key)=key%13。试求：（1）填上依次插入关键字 25，20，36，15，41，52，29，72，67 后的哈希表。（2）计算等概率情况下，查找成功的平均查找长度。