1、东 北 大 学 继 续 教 育 学 院 数据结构II 试 卷（作业考核 线上1） A 卷学习中心： 院校学号： 姓名 （共 6 页） 总分题号一二三四五六七八九十得分一、单选题（共30题，每题2分）A 1抽象数据类型的三个组成部分分别为A数据对象、数据关系和基本操作 B数据元素、逻辑结构和存储结构 C数据项、数据元素和数据类型 D数据元素、数据结构和数据类型B 2要求相同逻辑结构的数据元素具有相同的特性，其含义为A. 数据元素具有同一的特点B. 不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致C. 每个数据元素都一样D. 仅需要数据元素包含的数据项的个数相同D 3下列各式中，按
2、增长率由小至大的顺序正确排列的是A，n！，2n ，n3/2 Bn3/2，2n，nlogn，2100 C2n，log n，nlogn，n3/2 D2100，logn, 2n, nnB 4. 在下列哪种情况下，线性表应当采用链表表示为宜 A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 C5设指针p指向双链表的某一结点，则双链表结构的对称性是A. p-prior-next=p-next-next; B. p-prior-prior=p-next-prior;C. p-prior-next=p- next-prior; D.
3、p-next-next= p-prior-prior;A 6. 已知指针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； A7. 栈和队列的共同特点是A.只允许在端点处插入和删除元素B.都是先进后出 C.都是先进先出D.没有共同点 D8. 对于链队列，在进行插入运算时. A. 仅修改头指针 B
4、. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改B 9设有一个顺序栈的入栈序列是1、2、3，则3个元素都出栈的不同排列个数为 A4 B5 C. 6 D. 7 D10设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是AA，B，C，D BD，C，B，A C. A，C，D，B D. D，A，B，CC 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)都错B 14树有先序遍历和后序遍历，树可以转化为对应的二叉树。下面的说法正确的是 A树的后序遍历与其对应的二叉树的先序遍历相同 B树的后序遍历与其对应的二叉树的中序遍历相同C树的先序序遍历与其对应的二叉树的中序遍历相同 D以上都不对A 15下列说法正确的是 (1)二又树按某种方式线索化后，任一结点均有前趋和后继的线索 (2)二叉树的先序遍历序列中，任意一个结点均处于其子孙结点前 (3)二叉排序
6、树中任一结点的值大于其左孩子的值，小于右孩子的值A(1)(2)(3) B(1)(2) C(1)(3) D都不对D 16. 二叉树的第k层的结点数最多为 A2k-1 B.2K+1 C.2K-1 D. 2k-1D 17以下说法不正确的是 A无向图中的极大连通子图称为连通分量 B连通图的广度优先搜索中一般采用队列来暂存刚访问过的顶点 C图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D有向图的遍历不可采用广度优先搜索 D18有向图G用邻接矩阵A存储，则顶点i的入度等于A中A. 第i行1的元素之和 B. 第i列1的元素之和C. 第i行0的元素个数 D. 第i列非0的元素个数 A19. 设有6个结点
7、的无向图，该图确保是一个连通图的有效边条数至少应是A.5 B.6 C.7 D.8 C 20.下图的邻接表中，从顶点V1 出发采用深度优先搜索法遍历该图，则可能的顶点序列是 A. V1V2V3V4V5 B. V1V2V3V5V4C. V1V4V3V5V2 D.V1V3V4V5V2 A 21关键路径是事件结点网络中 A从源点到汇点的最长路径 B从源点到汇点的最短路径 C最长的回路 D最短的回路 D22设哈希表长为14，哈希函数H(key)=key11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是 A8 B3 C5 D
8、9 B23.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应调整以使其平衡，所作的平衡旋转是A. LL型 B. LR型 C. RL型 D. RR型A 24下列排序算法中，在待排序数据已基本有序时，效率最高的排序方法是 A插入排序 B选择排序 C快速排序 D堆排序A 25下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)是A. 堆排序 B. 冒泡排序 C. 直接选择排序 D. 快速排序 B26. 有一程序段:i=1；WHILE(ifront-next=Q-real=NULL B. Q-front=Q-
9、realNULL C. Q-real=Q-front=NULL D. Q-real-next=Q-frontNULL A28. 有向图G可拓扑排序的判别条件是A. 不存在环 B. 存在环 C. 存在入度为零的结点 D. 存在出度为零的结点 C 29. 对n个记录的文件进行快速排序，所需要的辅助存储空间 A. O（1） B. O（n） C. O（1og2n） D. O（n2） B30. 下列排序算法中，在待排序数据已基本有序时，效率最高的排序方法是 A插入排序 B选择排序 C快速排序 D堆排序二、综合题（共4题，每题10分）31、阅读算法，在横线处填入语句或注释。void exchange_L(
10、 Linklist &L，int m ) / 带头结点的单链表中前m个结点和后n个结点的整体互换 if ( m & L-next ) / 链表非空 p = L-next; （1）/ k取值 while( knext; +k; / while if (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
11、-next =（5）/将第 a1 结点链接到 bn 结点之后 / if(p) / if(m) / exchange_L （1）k = 1;（2）查找第am 个结点（3）p-next（4）L-next（5）将第 a1 结点链接到 bn 结点之后32一个仅包含二元运算符的算术表达式，以二叉链表形式存储在二叉树T中，设计算法F1实现求值，并指出遍历的方式。答：以二叉树表示算术表达式，根结点用于存储运算符。若能先分别求出左子树和右子树表示的子表达式的值， 最后就可以根据根结点的运算符的要求，计算出表达式的最后结果。 float PostValue(BiTree T) float lv,rv; if(T
12、) lv=PostValue(T-lchild); rv=PostValue(T-rchild); seitch(T-optr) case +: value=lv+rv;break; case -: value=lv-rv;break; case *: value=lv*rv;break; case /: value=lv/rv;break; return value; 33设计算法实现以逆邻接表为存储结构的有向图的拓扑排序。逆邻接表存储结构定义如下：顶点结构 表结点结构vexdatafirstin adjvexnfofirstarc#define MAX_VERTEX_NUM 20typed
13、ef struct ArcNode int adjvex ; struct ArcNode * nextarc ; InfoType * info ; ArcNode ; typedef struct Vnode VertexType data ; ArcNode * firstarc ; Vnode , AdjList MAX_VERTEX_NUM ;typedef struct AdjList Vertices; int vexnum , arcnum ; int kind ; ALGraph ;34. 设哈希表长为13，采用线性探测法解决冲突，哈希函数定义为：H(key)=key%13。
14、试求：（1）填上依次插入关键字25，20，36，15，41，52，29，72，67后的哈希表。（2）计算等概率情况下，查找成功的平均查找长度。1）Hash表 2）查找成功的平均查找长度：（1*5 +2*3 +4*1）/9 = 15/9 。查找成功的平均查找长度为SUM(查找次数)/SUM(元素个数)3) 查找失败的平均查找长度计算长度为m的哈希表中装填有n个记录的查找不成功时的平均查找长度相当于计算在这张表中填入第n+1个记录时所需要的比较次数的期望值。第N+1个记录可能是012若N+1个记录是0，由于位置0已经被占用，位置1没有占用，所以比较2次，依次类推。故查找不成功的平均查找长度为（2+1+5+4+3+2+1+1+2+2+1+2+1+3）/13=30/139课程名称: 数据结构II
