Question

求助 数据结构试题 谢谢！！！

一. 单项选择题(每题2分, 共30分)
1、根据数据元素的关键字直接计算出该元素存储地址的存储方法是（　　　）。
A)顺序存储方法
B)链式存储方法
C)索引存储方法
D)散列存储方法
2、下面程序段的时间复杂度为（ ）。
for (int i=0;i<m;i++) for (int j=0;j<n;j++) a[i][j]=i*j;
A)O(m2)
B)O(n2)
C)O(m*n)
D) O(m+n)
3、在一个单链表中，已知q所指结点是p所指结点的前驱，若在p、q之间插入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;
4、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ 　）存储方式最节省时间。
A)单链表
B)双链表
C)单向循环链表　
D)顺序表
5、带头结点的单链表h为空的判断条件是（ ）。
A)h==NULL
B)h->next==NULL
C)h->next==h
D)h!=NULL
6、设计一个判别表达式中左右括号是否配对出现的算法，采用（ 　）数据结构最佳。
A)线性表的顺序存储结构
B)栈　
C)队列　
D)线性表的链式存储结构
7、在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，则当作退栈处理时，top的变化为（　 ）。
A)top不变
B)top=0
C)top＝top+1
D)top=top-1
11、在具有n个叶子的哈夫曼树中，其结点总数为（ 　）。
A)不确定
B)2n
C)2n+1
D)2n-1
12、下列说法正确的是( )。
A)无向图中的极大连通子图叫做连通分量
B)有向图中的极大连通子图叫做连通分量
C)无向图中的极大连通子图叫做强连通分量
D)有向图中的极大连通子图叫做强连通分量
13、某无序表具有N个数据，若采用顺序查找算法，且每个数据查找的概率相等，那么查找失败时，平均查找长度ASL=（ ）
A)N
B)（N+1）/2
C)N（N-1）/2
D)N-1
14、能采用二分查找的数据结构是（ ）
A)二叉树
B)有序表
C)哈希表
D)无序表
15、快速排序在最坏情况下的时间复杂度是（　　　）
A)O(n2log2n)
B)O(n2)
C)O(nlog2n)
D)O(log2n)
二. 填空题
1、 数据结构的逻辑结构包括线性结构和__________________结构两大类。
2、 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为________，在表尾插入元素的时间复杂度为_____________。
3、 设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是________。
4、 一棵深度为h的满二叉树上的结点总数为_______，一棵深度为h的完全二叉树上的结点总数的最小值为_______，最大值为_______。
求高手帮忙做一下参考，谢谢！！！

Answer 1

一.判断题
（
）1.某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。
正确。第0个元素地址为100，则第i个元素地址为100+4*i，将12代入得148。
（
）2.在任何一种线性链表上都无法进行随机访问。
错误。比如只要知道顺序表首地址和每个数据元素所占存储单元的个数，就可以求出第i个数据元素的存储地址来，这也是顺序表具有按数据元素的序号随机存取的特点。
（
）3.顺序栈是一种规定了元素进栈顺序的栈。
错误。按存储结构来分，堆栈分为顺序栈和链栈，其中栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表，却并没有规定元素进栈顺序。
（
）4.循环列表中每一个元素都有后继。
正确。注意，这里可能有笔误，应写为“循环链表”而非“循环列表”。
（
）5.删除一个二叉树中的一个结点，再重新插入上去，一定能得到原来的二叉排序树。
错误。
二.填空题。
6.下面程序的时间复杂度为___________。
for
(int
i=1;
i<=m;
i++)
for
(int
j=1;
j<=n;
j++
)
S+=i
法则1：for循环：一个for循环的运行时间至多是该for循环内语句（包含测试）的运行时间乘以迭代的次数。
法则2：嵌套循环：从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有循环的大小的乘积。
对于此处嵌套的for循环，根据以上法则，时间复杂度为O(m*n)。
7.在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数是____________。
从第i个元素（原来的）到第n个元素，每个元素后移一位，一共需要n+1-i次。
8.在一个具有n个结点的有序单链表中插入一个新结点，并让插入后的单链表仍然有序，则该操作的时间复杂性数量级为______。
找到节点位置，O(n)；单链表插入操作，O(n)；总的时间复杂度为O(n+n)=O(n)。
9.若用s[1]～s[n]作为两个顺序栈的共同存储空间，左右两个栈的栈顶分别为t1和t2，则判断某个栈是否可以插入新元素的条件是_________________。
当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。
此处判断某个栈是否可以插入新元素的条件是&t1!=&t2
10.设森林T中有三棵树，第一，二，三棵树的结点个数分别为n1,n2,n3,将森林转换成二叉树后，其根结点的左子树上有____________个结点。
将一个森林转换为二叉树的具体方法是：①
将森林中的每棵树变为二叉树；②
因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。
个人认为此处可以填3个答案，n1-1或者n2-1或者n3-1。
11.在带权值有向图的邻接矩阵中，第i行上非零元素的个数等于_______________。
当节点Vi与某节点Vj相邻接,则A(i,j)取非0值。
12.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是_____________。
散列（Hash）查找。

Answer 2

ABBDB BDDCC BB1.非线性2.1 n3.34.二的h次方减一 二的h减一次方 二的h次方减一后面四个选择题不太确定，因为没查资料。不过有两个是课本原话，记不太清楚了。其他的都是对的。希望对你有帮助。知道数据结构真的不是太好学。

Answer 3

DBABB BDDAB BB
非线性；O(1)；O(N)；3；2^（h-1）；2^h —1；2^（h-1）；
12题在课本159页，严蔚敏那本书；

Answer 4

D C B D B B D D A A B B
1 非线性结构
2 n n^2
3 3
4 2^h -1 2^(h-1) 2^h-1

Answer 5

ABBDB BDDCC BB 非线性新手