惜跑恢鳖腥时世既逼湃熟巾炮
第1章 绪论 绪论
1、 在数据结构中,从逻辑上可以把数据结构分成__。
A:动态结构和静态结构
B:紧凑结构和非紧凑结构
C:线性结构和非线性结构
D:内部结构和外部结构
答案: 线性结构和非线性结构
2、 算法分析的目的是__。
A:找出数据结构的合理性
B:研究算法中的输入和输出的关系
C:分析算法的效率以求改进
D:分析算法的易懂性和文档性
答案: 分析算法的效率以求改进
3、 算法分析的两个主要方面是__。
A:空间复杂度和时间复杂度
B:正确性和简单性
C:可读性和文档性
D:数据复杂性和程序复杂性
答案: 空间复杂度和时间复杂度
4、 计算机算法指的是解决问题的有限运算序列,它必须具备输入、输出和__等5个特性。
A:可执行性、可移植性和可扩充性
B:可行性、确定性和有穷性
C:确定性、有穷性和稳定性
D:易读性、稳定性和安全性
答案: 可行性、确定性和有穷性
5、 下面程序段的时间复杂度为______。for(int i=0; i<m; i++)for(int j=0; j<n; j++)a[i][j]=ij;
A:O(m2)
B:O(n2)
C:O(mn)
D:O(m+n)
答案: O(m*n)
6、 执行下面程序段时,执行S语句的次数为______。for(int i=1; i<=n; i++)for(int j=1; j<=i; j++) S;
A:n2
B:n2/2
C:n(n+1)
D: n(n+1)/2
答案: n(n+1)/2
7、 下面算法的时间复杂度为______。int f( unsigned int n ) {if ( n==0 || n==1 ) return 1; else return n*f(n-1); }
A:O(1)
B:O(n)
C:O(n2)
D:O(n!)
答案: O(n)
8、 下面程序段的时间复杂性的量级为______。for(i=1;i<=n; i++) for(j=1;j<=m; j++){c[i][j]=0; for(k=1;k<=w;k++)c[i][j]+=a[i][k]b[k][j] }
A:O(ijk)
B:O(nmk)
C:O(njk)
D:O(nmw)
答案: O(nm*w)
9、 下面关于算法说法错误的是______。
A:算法最终必须由计算机程序实现
B:为解决某问题的算法同为该问题编写的程序含义是相同的
C:算法的可行性是指指令不能有二义性
D:以上几个都是错误的
答案: 算法的可行性是指指令不能有二义性
10、 数据结构是一门研究非数值计算的程序设计问题中计算机的 ① 以及它们之间的 ② 和运算等的学科。
A:数据元素
B:关系
C:逻辑存储
D:数据映象
答案: 数据元素;
关系
第2章 线性表 线性表
1、 线性表是_ 。
A:一个有限序列,可以为空
B:一个有限序列,不能为空
C:一个无限序列,可以为空
D:一个无序序列,不能为空。
答案: 一个有限序列,可以为空
2、 对顺序存储的线性表,设其长度为n,在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的_个元素。
A:n/2
B:(n+1)/2
C:(n –1)/2
D:n
答案: n/2
3、 线性表采用链式存储时,其地址_。
A:必须是连续的
B:部分地址必须是连续的
C:一定是不连续的
D:连续与否均可以
答案: 连续与否均可以
4、 用链表表示线性表的优点是_。
A:便于随机存取
B:花费的存储空间较顺序存储少
C:便于插入和删除
D:数据元素的物理顺序与逻辑顺序相同
答案: 便于插入和删除
5、 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素,则采用_存储方式最节省运算时间。
A:单链表
B:双链表
C:单循环链表
D:带头结点的双循环链表
答案: 带头结点的双循环链表
6、 循环链表的主要优点是_ 。
A:不再需要头指针了
B:已知某个结点的位置后,能够容易找到他的直接前趋
C:在进行插入、删除运算时,能更好的保证链表不断开
D:从表中的任意结点出发都能扫描到整个链表
答案: 从表中的任意结点出发都能扫描到整个链表
7、 下面关于线性表的叙述错误的是_。
A:线性表采用顺序存储,必须占用一片地址连续的单元
B:线性表采用顺序存储,便于进行插入和删除操作
C:线性表采用链式存储,不必占用一片地址连续的单元
D:线性表采用链式存储,便于进行插入和删除操作
答案: 线性表采用顺序存储,便于进行插入和删除操作
8、 单链表中,增加一个头结点的目的是为了_。
A:使单链表至少有一个结点
B:标识表结点中首结点的位置
C:方便运算的实现
D:说明单链表是线性表的链式存储
答案: 方便运算的实现
9、 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用_存储方式最节省运算时间。
A:单链表
B:仅有头指针的单循环链表
C:双链表
D:仅有尾指针的单循环链表
答案: 仅有尾指针的单循环链表
10、 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,则采用_存储方式最节省运算时间。
A:单链表
B:顺序表
C:双链表
D:单循环链表
答案: 顺序表
11、 一个向量(一种顺序表)第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是_。
A:110
B:108
C:100
D:120
答案: 108
12、 不带头结点的单链表head为空的判定条件是______。
A:head = = NULL;
B:head->next = = NULL;
C:head->next = = head;
D:head! = NULL;
答案: head = = NULL;
13、 带头结点的单链表head为空的判定条件是______。
A:head = = NULL;
B:head->next = = NULL;
C:head->next = = head;
D:head! = NULL;
答案: head->next = = NULL;
14、 在一个单链表中,若p所指结点不是最后结点,在p之后插入s所指结点,则执行____。
A:s->next=p; p->next=s;
B:s->next=p->next; p->next=s;
C:s->next=p->next; p=s;
D:p->next=s; s->next=p;
答案: s->next=p->next; p->next=s;
15、 在一个单链表中,已知q所指结点是p所指结点的前驱结点,若在q和p之间插入s结点,则执行______。
A:s->next=p->next; p->next=s;
B:p->next=s->next; s->next=p;
C:q->next=s; s->next=p;
D:p->next=s; s->next=q;
答案: q->next=s; s->next=p;
16、 从一个具有n个结点的单链表中查找其值等于x结点时,在查找成功的情况下,需平均比较_____个结点。
A:n
B:n/2
C:(n-1)/2
D:(n+1)/2
答案: (n+1)/2
17、 给定有n个结点的向量,建立一个有序单链表的时间复杂度_。
A:O(1)
B:O(n)
C:O(n^2)
D:O(nlogn)
答案: O(n^2)
18、 顺序存储结构是一种___的存储结构。
A:随机存取
B:索引存取
C:顺序存取
D:散列存取
答案: 随机存取
19、 在以下的叙述中,正确的是___。
A:线性表的顺序存储结构优于链表存储结构
B:线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
C:线性表的链表存储结构适用于频繁插入/删除数据元素的情况
D:线性表的链表存储结构优于顺序存储结构
答案: 线性表的链表存储结构适用于频繁插入/删除数据元素的情况
20、 非空的循环单链表head的尾结点(由p所指向)满足____。
A:p->next= =NULL
B: p= =NULL
C: p->next= =head
D:p= =head
答案: p->next= =head
21、 在一个单链表中,若删除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;
答案: p->next= p->next->next;
22、 在一个长度为n的顺序存储线性表中,向第i个元素(1≤i≤n+1)之前插入一个新元素时,需要从后向前依次后移____个元素。
A:n-i
B:n-i+1
C:n-i-1
D:i
答案: n-i+1
23、 在一个长度为n的顺序存储线性表中,删除第i个元素(1≤i≤n+1)时,需要从前向后依次前移____个元素。
A:n-i
B:n-i+1
C:n-i-1
D:i
答案: n-i
24、 在一个长度为n的线性表中顺序查找值为x的元素时,查找时的平均查找长度(即x同元素的平均比较次数,假定查找每个元素的概率都相等)为____。
A:n
B:n/2
C:(n+1)/2
D:(n-1)/2
答案: (n+1)/2
25、 在一个单链表HL中,若要向表头插入一个由指针p指向的结点,则执行____。
A:HL = p; p->next = HL;
B:p->next = HL; HL = p;
C:p->next = HL; p = HL;
D:p->next = HL->next; HL->next = p;
答案: p->next = HL; HL = p;
26、 一个带头结点head的循环单链表为空的判断条件是____。
A:head==NULL
B:head->next==NULL
C:head->next==head
D:head!=NULL
答案: head->next==head
27、 在一个单链表HL中,若要删除由指针q所指向结点的后继结点,则执行____。
A:p = q->next ; p->next = q->next;
B:p = q->next ; q->next = p;
C:p = q->next ; q->next = p->next;
D:q->next = q->next->next; q->next = q;
答案: p = q->next ; q->next = p->next;
28、 将两个各有n个元素的有序表归并成一个有序表,在最坏的情况下,其比较次数是____。
A:2n-1
B:n
C:n+1
D:n-1
答案: 2n-1
29、 线性表的逻辑顺序与存储顺序总是一致的。
A:正确
B:错误
答案: 错误
30、 顺序存储的线性表可以按序号随机存取。
A:正确
B:错误
答案: 正确
31、 顺序表的插入和删除一个数据元素,每次操作平均只有近一半的元素需要移动。
A:正确
B:错误
答案: 正确
32、 线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的特性,因此是属于同一数据对象。
A:正确
B:错误
答案: 正确
33、 在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上并不一定紧邻。
A:正确
B:错误
答案: 错误
34、 在线性表的链式存储结构中,逻辑上相邻的元素在物理位置上不一定相邻。
A:正确
B:错误
答案: 正确
35、 线性表的链式存储结构优于顺序存储结构。
A:正确
B:错误
答案: 错误
36、 在线性表的顺序存储结构中,插入和删除时,移动元素的个数与该元素的位置有关。
A:正确
B:错误
答案: 正确
37、 线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。
A:正确
B:错误
答案: 正确
38、 在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存取的存储结构。
A:正确
B:错误
答案: 错误
39、 线性表中,每一个元素均存在前驱。
A:正确
B:错误
答案: 错误
40、 线性表中,每一个元素均存在后继。
A:正确
B:错误
答案: 错误
41、 线性表中,存在唯一一个被称为第一元素的元素。
A:正确
B:错误
答案: 正确
42、 线性表中,存在唯一一个被称为最后一个元素的元素。
A:正确
B:错误
答案: 正确
43、 线性结构是一种一对一的结构。
A:正确
B:错误
答案: 正确
第3章 栈和队列 栈和队列
1、 一个栈的入栈序列a,b,c,d,e,则栈的不可能的输出序列是____。
A:edcba
B:decba
C:dceab
D: abcde
答案: dceab
2、 若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi为____。
A:i
B:n=i
C:n-i+1
D:不确定
答案: n-i+1
3、 栈结构通常采用的两种存储结构是____。
A:顺序存储结构和链式存储结构
B:散列方式和索引方式
C:链表存储结构和数组
D:线性存储结构和非线性存储结构
答案: 顺序存储结构和链式存储结构
4、 判定一个顺序栈ST(最多元素为m0)为空的条件是____。
A:top !=0
B:top= =0
C:top !=m0
D:top= =m0-1
答案: top= =0
5、 判定一个顺序栈ST(最多元素为m0)为栈满的条件是____。
A:top!=0
B:top= =0
C:top!=m0
D:top= =m0-1
答案: top= =m0-1
6、 队列操作的原则是____。
A:先进先出
B:后进先出
C:只能进行插入
D:只能进行删除
答案: 先进先出
7、 向一个栈顶指针为HS的链栈中插入一个s所指结点时,则执行__ __。(不带空的头结点)
A:HS—>next=s;
B:s—>next= HS—>next; HS—>next=s;
C:s—>next= HS; HS=s;
D:s—>next= HS; HS= HS—>next;
答案: s—>next= HS; HS=s;
8、 从一个栈顶指针为HS的链栈中删除一个结点时,用x保存被删结点的值,则执行__ __。(不带空的头结点)
A:x=HS; HS= HS—>next;
B:x=HS—>data;
C:HS= HS—>next; x=HS—>data;
D:x=HS—>data; HS= HS—>next;
答案: x=HS—>data;
9、 一个队列的数据入列序列是1,2,3,4,则队列的出队时输出序列是____ 。
A:4,3,2,1
B:1,2,3,4
C:1,4,3,2
D:3,2,4,1
答案: 1,2,3,4
10、 判定一个循环队列QU(最多元素为m)为空的条件是____。
A:rear – front= =m
B:rear-front-1= =m
C:front= = rear
D:front= = rear+1
答案: front= = rear
11、 判定一个循环队列QU(最多元素为m, m= =Maxsize-1)为满队列的条件是____。
A:((rear- front)+ Maxsize)% Maxsize = =m
B:rear-front-1= =m
C:front= =rear
D:front= = rear+1
答案: ((rear- front)+ Maxsize)% Maxsize = =m
12、 循环队列用数组A[0,m-1]存放其元素值,已知其头尾指针分别是front和rear,则当前队列中的元素个数是____。
A: (rear-front+m)%m
B:rear-front+1
C:rear-front-1
D: rear-front
答案: (rear-front+m)%m
13、 栈和队列的共同点是____。
A:都是先进后出
B:都是先进先出
C:只允许在端点处插入和删除元素
D:没有共同点
答案: 只允许在端点处插入和删除元素
14、 栈操作的原则是____。
A:先进先出
B:后进先出
C:只能进行插入
D:只能进行删除
答案: 后进先出
15、 在顺序栈中,判断栈s为空的条件是____。
A:t.base == NULL
B:st.top == st.stacksize
C:st.top-st.base>=st.stacksize
D:st.top == st.base
答案: st.top == st.base
16、 在顺序栈中,判断栈s满的条件是____。
A:st.base == NULL
B:st.top == st.stacksize
C:st.top-st.base>=st.stacksize
D:st.top == st.base
答案: st.top-st.base>=st.stacksize
17、 当利用大小为N的一维数组顺序存储一个栈时,假定用top==N表示栈空,则向这个栈插入一个元素时,首先应执行语句修改top指针____。
A:top++
B:top–
C:top=0
D:top
答案: top–
18、 当利用大小为N的一维数组顺序存储一个循环队列时,该队列的最大长度为____。
A:N-2
B:N-1
C:N
D:N+1
答案: N-1
19、 从一个循环顺序队列删除元素时,首先需要____。
A:前移一位队首指针
B:后移一位队首指针
C:取出队首指针所指位置上的元素
D:取出队尾指针所指位置上
答案: 后移一位队首指针
20、 假定一个循环顺序队列的队首和队尾指针分别为f和r,则判断队空的条件是____。
A:f+1==r
B:r+1==f
C:f==0
D:f==r
答案: f==r
21、 假定一个链队的队首和队尾指针分别为front和rear,则判断队空的条件是____。
A:front==rear
B:front!=NULL
C:rear!=NULL
D:front==NULL
答案: front==NULL
上方为免费预览版答案,如需购买完整答案,请点击下方红字
为了方便下次阅读,建议在浏览器添加书签收藏本网页
添加书签方法:
1.电脑按键盘的Ctrl键+D键即可收藏本网页
2.手机浏览器可以添加书签收藏本网页
我们的公众号
打开手机微信,扫一扫下方二维码,关注微信公众号:萌面人APP
本公众号可查看各种网课答案,还可免费查看大学教材答案
埠呸闯毋橇狡摩某具睦酪刚咖