22年春吉大《数据结构》在线作业一奥鹏作业答案-
![22年春吉大《数据结构》在线作业一[答案]](/uploads/allimg/240109/3bc5b14a0746243e2d0dc61b174bbfe0.jpg)
试卷总分:100 得分:100
第1题,在单链表中删除p所指结点的直接后继的操作是
A、p-next=p-next-next;
B、p=p-next;p-next=p-next-next;
C、p-next=p-next;
D、p=p-next-next;
正确答案:
第2题,单链表中增加头结点的目的是为了
A、方便运算的实现
B、用于标识单链表
C、使单链表中至少有一个结点
D、用于标识起始结点的位置
正确答案:
第3题,任何一颗二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置
A、肯定发生变化
B、有时发生变化
C、肯定不发生变化
D、无法确定
正确答案:
第4题,在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的
A、先根遍历
B、中根遍历
C、后根遍历
D、按层次遍历
正确答案:
非空的循环单链表head的尾结点由指针p所指满足
A、p-next=NULL
B、p=NULL
C、p-next=head
D、p=head
正确答案:
第6题,在具有n个单元的循环队列中队满共有个元素
A、n
B、n-1
C、n+1
D、n+2
正确答案:
第7题,深度为6的二叉树最多有个结点
A、64
B、63
C、32
D、31
正确答案:
第8题,带头结点的单链表head为空的判断条件是
A、head=NULL
B、head-next=NULL
C、head-next=head
D、head!=NULL
正确答案:
第9题,含n个顶点的连通图中的任意一条简单路径其长度不可能超过
A、1
B、n/2
C、n-1
D、n
正确答案:
在一个单链表中已知q所指结点是p所指结点的直接前趋若在pq之间插入s结点这执行操作
A、s-next=p-next;p-next=s
B、q-next=s;s-next=p
C、p-next=s-next;s-next=p;
D、p-next=s;s-next=q;
正确答案:
第11题,图的存储结构有
A、邻接矩阵
B、邻接表
C、数组表示法
D、十字链表
正确答案:,B,C,D
二叉树的遍历方式有
A、先根遍历
B、中根遍历
C、后根遍历
D、深度遍历
正确答案:,B,C
第13题,递归过程中要保存的信息包括
A、返回地址
B、本次调用中与形参结合的实参值
C、本次递归调用中的局部变量值
D、执行结果
正确答案:,B,C
第14题,属于插入排序的排序方法有
A、直接插入排序
B、对半插入排序
C、渐减增量排序
D、冒泡排序
正确答案:,B,C
一个好的算法应具备以下性质
A、正确性
B、可读性
C、稳健性
D、有穷性
正确答案:,B,C,D
第16题,设有两个串p和q求q在p中首次出现的位置的运算称作模式匹配
A、错误
B、正确
正确答案:
第17题,快速排序的速度在所有排序方法中为最快而且所需附加空间也最少
A、错误
B、正确
正确答案:
第18题,不是所有的AOV网都有一个拓朴序列
A、错误
B、正确
正确答案:
第19题,对于前序遍历和中序遍历结果相同的二叉树为所有结点只有右孩子的二叉树
A、错误
B、正确
正确答案:
算法和程序没有区别所以在数据结构中二者是通用的
A、错误
B、正确
正确答案:
第21题,判断一个表达式中左右括号是否匹配采用栈实现较为方便
A、错误
B、正确
正确答案:
第22题,邻接多重表示法对于有向图和无向图的存储都适用
A、错误
B、正确
正确答案:
第23题,从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较然后将其放在已排序序列的合适位置上该排序方法称为插入排序
A、错误
B、正确
正确答案:
第24题,在最好和最坏情况下的时间复杂度均为Onlogn且稳定的排序方法是归并排序
A、错误
B、正确
正确答案:
由权值为9257的四个叶子结点构造一棵哈夫曼树该树的带权路径长度44
A、错误
B、正确
正确答案:
相关练习题：
资本家把剩余价值转化为资本，就叫做资本积累。
东 北 大 学 继 续 教 育 学 院
数据结构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．树的先序序遍历与其对应的二叉树的中序遍历相同
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）计算等概率情况下，查找成功的平均查找长度。
