最新消息:可做奥鹏等各院校作业论文,答案请联系QQ/微信:18866732

东大21年1月考试《数据结构ⅡX》考核作业

东 北 大 学 继 续 教 育 学 院

 

数据结构II X 试 卷(作业考核 线上2)  A  卷

 

学习中心:            院校学号:             姓名

 

(共    6    页)

总分 题号 一 二 三 四 五 六 七 八 九 十

得分   一、单选题(共30题,每题2分)

[ ]1.抽象数据类型的三个组成部分分别为

A.数据对象、数据关系和基本操作

B.数据元素、逻辑结构和存储结构

C.数据项、数据元素和数据类型

D.数据元素、数据结构和数据类型

[ ]2.要求相同逻辑结构的数据元素具有相同的特性,其含义为

A. 数据元素具有同一的特点

B. 不仅数据元素包含的数据项的个数相同,而且其对应数据项的类型要一致

C. 每个数据元素都一样

D. 仅需要数据元素包含的数据项的个数相同

[ ]3.下列各式中,按增长率由小至大的顺序正确排列的是

A.,n!,2n ,n3/2

B.n3/2,2n,nlogn,2100

C.2n,log n,nlogn,n3/2

D.2100,logn, 2n, nn

[ ]4. 在下列哪种情况下,线性表应当采用链表表示为宜

A.经常需要随机地存取元素

B.经常需要进行插入和删除操作

C.表中元素需要占据一片连续的存储空间

D.表中元素的个数不变

[ ]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->next= p->prior->prior;

[ ]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;

[ ]7. 栈和队列的共同特点是

A.只允许在端点处插入和删除元素

B.都是先进后出

C.都是先进先出

D.没有共同点

[ ]8. 对于链队列,在进行插入运算时.

A. 仅修改头指针

B. 头、尾指针都要修改

C. 仅修改尾指针

D.头、尾指针可能都要修改

[ ]9.设有一个顺序栈的入栈序列是1、2、3,则3个元素都出栈的不同排列个数为

A.4      B.5     C. 6     D. 7

[ ]10.设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是

A.A,B,C,D               B.D,C,B,A

C. A,C,D,B               D. D,A,B,C

[ ]11.表达式a*(b+c)-d的后缀表达式是

A.abcd*+-    B.abc*+d-  C.abc+*d-   D.-+*abcd

[ ]12.某二叉树的先序序列和后序序列正好相反,则该二叉树的特点一定是

A. 空或只有一个结点             B.高度等于其结点数

C. 任一结点无左孩子             D.任一结点无右孩子

[ ]13.下面的说法中正确的是

(1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。

(2)按二叉树定义,具有三个结点的二叉树共有6种。

A.(1),(2)                       B.(1)

C.(2)                            D.(1),(2)都错

[ ]14.树有先序遍历和后序遍历,树可以转化为对应的二叉树。下面的

说法正确的是

A.树的后序遍历与其对应的二叉树的先序遍历相同

B.树的后序遍历与其对应的二叉树的中序遍历相同

C.树的先序序遍历与其对应的二叉树的中序遍历相同
奥鹏作业答案请进open5.net或请联系QQ/微信:18866732

D.以上都不对

[ ]15.下列说法正确的是

(1)二又树按某种方式线索化后,任一结点均有前趋和后继的线索

(2)二叉树的先序遍历序列中,任意一个结点均处于其子孙结点前

(3)二叉排序树中任一结点的值大于其左孩子的值,小于右孩子的值

A.(1)(2)(3)                     B.(1)(2)

C.(1)(3)                        D.都不对

[ ]16. 二叉树的第k层的结点数最多为

A.2k-1                          B.2K+1

C.2K-1                           D. 2k-1

[ ]17.以下说法不正确的是

A.无向图中的极大连通子图称为连通分量

B.连通图的广度优先搜索中一般采用队列来暂存刚访问过的顶点

C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点

D.有向图的遍历不可采用广度优先搜索

[ ]18.有向图G用邻接矩阵A存储,则顶点i的入度等于A中

A. 第i行1的元素之和            B. 第i列1的元素之和

C. 第i行0的元素个数            D. 第i列非0的元素个数

[ ]19. 设有6个结点的无向图,该图确保是一个连通图的有效边条数至

少应是

A.5              B.6              C.7             D.8

[ ]20..下图的邻接表中,从顶点V1 出发采用深度优先搜索法遍历该图,则可能的顶点序列是

 

A. V1V2V3V4V5          B. V1V2V3V5V4

C. V1V4V3V5V2          D.V1V3V4V5V2

[ ]21.关键路径是事件结点网络中

A.从源点到汇点的最长路径    B.从源点到汇点的最短路径

C.最长的回路                D.最短的回路

[ ]22.设哈希表长为14,哈希函数H(key)=key%11,表中已有数据的关键字为15,38,61,84,四个,现将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是

A.8       B.3        C.5        D.9

[ ]23..在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0,右孩子的平衡因子为1,则应调整以使其平衡,所作的平衡旋转是

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<n) i=i*2;其中带下划线语句的执行次数的数量级是

A. O(n)                                 B. O(log2n)

C. O(nlog2n)                             D. O(n2)

[ ]27.无头结点的链队列Q为空的条件是

A. Q->front->next==Q->real=NULL

B. Q->front==Q->real<>NULL

C. Q->real==Q->front=NULL

D. Q->real->next==Q->front<>NULL

[ ]28. 有向图G可拓扑排序的判别条件是

A. 不存在环                  B. 存在环

C. 存在入度为零的结点        D. 存在出度为零的结点

[ ]29. 对n个记录的文件进行快速排序,所需要的辅助存储空间

A. O(1)        B. O(n)      C. O(1og2n)       D. O(n2)

[ ]30. 下列排序算法中,在待排序数据已基本有序时,效率最高的排序方法是

A.插入排序                    B.选择排序

C.快速排序                    D.堆排序

二、综合题(共4题,每题10分)

31、阅读算法,在横线处填入语句或注释。

void exchange_L( Linklist &L,int m ) {

// 带头结点的单链表中前m个结点和后n个结点的整体互换

if ( m && L->next ) { // 链表非空

p = L->next;

(1)// k取值

while( k< m && p ) { //(2)

p = p->next; ++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->next =(5)//将第 a1 结点链接到 bn 结点之后

} // if(p)

} // if(m)

} // exchange_L

 

 

 

 

 

 

 

 

 

 

 

32.一个仅包含二元运算符的算术表达式,以二叉链表形式存储在二叉树T中,设计算法F1实现求值,并指出遍历的方式。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

33.设计算法实现以逆邻接表为存储结构的有向图的拓扑排序。

逆邻接表存储结构定义如下:

顶点结构                       表结点结构

 

vexdata firstin

adjvex nfo firstarc

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

34. 设哈希表长为13,采用线性探测法解决冲突,哈希函数定义为:H(key)=key%13。

试求:(1)填上依次插入关键字25,20,36,15,41,52,29,72,67后的哈希表。

(2)计算等概率情况下,查找成功的平均查找长度。

转载请注明:奥鹏作业之家 » 东大21年1月考试《数据结构ⅡX》考核作业

发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址