数据结构ds答案_以行序为主序存储二维数组a[1..10, 1..5],每个数据元素占2个存储单元,基地址
赞
踩
数据结构习题及答案
复习题
1．在下面的程序段的时间复杂度为 O(m*n) 。
for (int i=1;i<m;i++)
for (int j=1;j<n;j++)
a[i][j]=i*j;
2.栈中元素的进出原则是 先进后出 ，队列中元素的进出原则 是 先进先出 。
3.设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为：
1) s->next=_p->next(下一节点)________；2) p->next=s；3) t=p->data；
4) p->data=_s->data__________；5) s->data=t；
4.假设以行序为主序存储二维数组A=array[1..100,1..100],设每个数据元素占2个存储单元，基地址为10，则LOC[6,6]= 1020 。
5.表达式a*(b+c)-d/e的后缀表达式为 abc+*de/- 。
6.设一棵完全二叉树中有100个结点，则该二叉树的深度为__7________；若用二叉链表作为该完全二叉树的存储结构，则共有______101_____个空指针域。
7.设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的___出度_____。
8.利用逐点插入法（注释：将首位元素作为根，将比它小的放左边，比他大的放右边）建立序列（50,72,43,85,75,20,35,45,65,30）对应的二叉排序树以后，查找元素20要进行 3 次元素间的比较。
9.在活动图中，节点表示项目中各个工作阶段的里程碑，连接各个节点的边表示活动，边上的数字表示活动持续的时间。在右边的活动图中，从A到J的关键路径长度是 49 ，从E开始的活动启动的最早时间(注释：从源点到顶点E的最长路径长。 )是 13 。
10.设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建成的初始大根堆序列为____________30,20,22,16,18,19____________。
11.已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，求出在查找每一个元素概率相等情况下的平均查找长度 8/5 。
12.设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=___d/2____。
13．设二维数组A[0..10,0..20]按行优先顺序存储，每个元素占4个存储单元，A[2,1]的存储地址是1000，则A[5,6]的存储地址是 1272 。
14．在循环单链表La（La为头指针）中，指针p所指结点为表尾的条件 p->next==La 。
15．设s=’YOUARE STUDENT IT RIGHT OR WRONG’，顺序执行下列操作：SubString(sub1,s,1,8); SubString(sub2,s,20,5); StrCat(sub1,sub2); 则最后sub1的值为： YOU ARE RIGHT 。
16．顺序存放的循环队列的元素以数组A[m]存放,其头尾指针分别为front和rear，则当前队列中的元素个数为 (rear-front+m)%m 。队满的条件(rear+1)%n=front
17．算法分析考虑的两个主要因素是 时间复杂性 和 空间复杂性 。
18．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是 11 。
19．若待排序序列中具有相同关键字的记录在排好序后其相对位置发生了变化，则称这种排序方法是 不稳定的 。
20.为了保证图中的各顶点在遍历过程中访问且仅访问一次，需要为每个顶点设一个访问标志，因此要为图设置一个 访问标志数组visit[n] ，用于标示图中每个顶点是否被访问过。
二、单项选择题
1.算法分析的两个主要方面是（ ）。
A．空间复杂性和时间复杂性 B．正确性和简明性
C．可读性和文档性 D．数据复杂性和程序复杂性
2.以下与数据的存储结构无关的术语是（ ）。
A．顺序队列 B．链表
C．有序表 D．链栈
3.以下数据结构中，（ ）是非线性数据结构。
A．树 B．字符串 C．队列 D．栈
4.线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )。
A．必须是连续的 B．部分地址必须是连续的
C．一定是不连续的 D．连续或不连续都可以
5．设输入序列为1、2、3，则通过栈的作用后不可以得到的输出序列为（ ）。
A．3，1，2 B．3，2，1 C．1，3，2 D．1， 2，3
6.广义表（a,(b,c)）的表头和表尾分别为（ ）。
A．a和(b,c) B．（a）和(b,c)
C．a 和((b,c)) D．(a) 和((b,c))
7.栈和队列的共同特点是( )。（注释：队列是一种限定性的线性表，只允许表的一端插入元素，而另一端删除元素。）
A．只允许在端点处插入和删除元素
B．都是先进后出
C．都是先进先出
D．没有共同点
8.下面程序段的时间复杂度为（ ）。
for (inti=1;i<n;i++)
for (int j=1;j<m;j++)
a[i][j]=0;
A．O(m2) B．O(m*n) C．O(n*n) D．O(log2n)
9.在双向循环链表中，在p指针所指的节点后插入q所指向的新节点，其修改指针的操作是（ ）。
A．p->next=q;q->prior=p;p->next->prior=q;q->next=q;
B．p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;
C．q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;
D．q->prior=p;q->next=p->next;p->next=q;p->next->prior=q;
10.设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（ ）。
