一、选择题:(每小题2分,共30分)
1、在数据的逻辑结构中,树结构和图结构都是( )
A.非线性结构 B.线性结构
C.动态结构 D.静态结构
2.在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为( )
A.O(1) B.O(log n)
C.O(n) D.O(n2)
3.指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点,要将两个链表链接成一个新的单循环链表,应执行的操作为( )
A.p1->next=p2->next;p2->next=p1->next;
B. p2->next=p1->next;p1->next=p2->next;
C. p=p2->next; p1->next=p;p2->next=p1->next;
D. p=p1->next; p1->next= p2->next;p2->next=p;
4.设栈的初始状态为空,入栈序列为1,2,3,4,5,6,若出栈序列为2,4,3,6,5,1,则操作过程中栈中元素个数最多时为( )
A.2个 B.3个
C.4个 D.6个
5.队列的特点是( )
A.允许在表的任何位置进行插入和删除
B.只允许在表的一端进行插入和删除
C.允许在表的两端进行插入和删除
D.只允许在表的一端进行插入,在另一端进行删除
6.一个链串的结点类型定义为
﹟define NodeSize 6
typedef struct node{
char data[NodeSize];
struct node*next;
}LinkStrNode;
如果每个字符占1个字节,指针占2个字节,该链串的存储密度为( )
A.1/3 B.1/2
C.2/3 D.3/4
7.广义表A=(a,B,(a,B,(a,B,……)))的长度为( )
A.1 B.2
C.3 D.无限值
8.已知10×12的二维数组A,按“行优先顺序”存储,每个元素占1个存储单元,已知A[1][1]的存储地址为420,则A[5][5]的存储地址为( )
A.470 B.471
C.472 D.473
9.在一棵二叉树中,度为2的结点数为15,度为1的结点数为3,则叶子结点数为( )
A.12 B.16
C.18 D.20
10.在带权图的最短路径问题中,路径长度是指( )
A.路径上的顶点数 B.路径上的边数
C.路径上的顶点数与边数之和 D.路径上各边的权值之和
11.具有n个顶点、e条边的无向图的邻接矩阵中,零元素的个数为( )
A.e B.2e
C.n2-2e D.n2-1
12.要以O(n log n)时间复杂度进行稳定的排序,可用的排序方法是( )
A.归并排序 B.快速排序
C.堆排序 D.冒泡排序
13.若希望在1000个无序元素中尽快求得前10个最大元素,应借用( )
A.堆排序 B.快速排序
C.冒泡排序 D.归并排序
14.对有序表进行二分查找成功时,元素比较的次数( )
A.仅与表中元素的值有关 B.仅与表的长度和被查元素的位置有关
C.仅与被查元素的值有关 D.仅与表中元素按升序或降序排列有关
15.散列文件是一种( )
A.顺序存取的文件 B.随机存取的文件
C.索引存取的文件 D.索引顺序存取的文件
二、填空题:(每空2分,共20分)
16.数据结构由数据的逻辑结构、存储结构和数据的____________三部分组成。
17.在单链表中某结点后插入一个新结点,需要修改_______________个结点指针域的值。
18.设栈S的初始状态为空,若元素a、b、c、d、e、f依次进栈,得到的出栈序列是b、d、c、f、e、a,则栈S的容量至少是________________。
19.长度为零的串称为________________。
20.广义表G=(a,b,(c,d,(e,f)),G)的长度为________________。
21.一棵树T采用孩子兄弟链表存储,如果树T中某个结点为叶子结点,则该结点在二叉链表中所对应的结点一定是________________。
22.一个有n个顶点的无向连通图,最少有________________条边。
23.当待排关键字序列基本有序时,快速排序、简单选择排序和直接插入排序三种排序方法中,运行效率最高的是____ _。
24.在一棵深度为h的具有n个结点的二叉排序树中,查找任一结点的最多比较次数是 _______。
25.不定长文件指的是文件的 ________大小不固定。
三、解答题(本大题共4小题,每小题5分,共20分)
26.已知一棵二叉排序树(结点值大小按字母顺序)的前序遍历序列为EBACDFHG,请回答下列问题:
(1)画出此二叉排序树;
(2)若将此二叉排序树看作森林的二叉链表存储,请画出对应的森林。
27.已知有向图的邻接表如图所示,请回答下面问题:
(1)给出该图的邻接矩阵;
(2)从结点A出发,写出该图的深度优先遍历序列。
28.已知待排记录的关键字序列为{25,96,11,63,57,78,44},请回答下列问题:
(1)画出堆排序的初始堆(大根堆);
(2)画出第二次重建堆之后的堆。
29.已知关键字序列为(56,23,41,79,38,62,18),用散列函数H(key)=key%11将其散列到散列表HT[0…10]中,采用线性探测法处理冲突。请回答下列问题:
(1)画出散列存储后的散列表:
(2)求在等概率情况下查找成功的平均查找长度。
四、算法阅读题(本大题共4小题,每小题5分,共20分)
30.阅读下列算法,并回答问题:
(1)假设L=(3,7,7,11,20,20,20,51,51),写出执行函数f30(&L)后的L;
(2)简述f30的功能。
void f30(SeqList*L)
{ ∥L为非空的有序表
int i=1,k=0;
while(i<L->length)
{
if(L->data[i]!=L->data[k])
L->data[++k]=L->data[i];
i++;
}
L->length=k+1;
}
(1)
(2)
31.阅读下列算法,并回答问题:
(1)假设栈S=(3,8,6,2,5),其中5为栈顶元素,写出执行函数f31(&S)后的S;
(2)简述函数f31的功能。
void f31(Stack *S){
Queue Q;InitQueue(&Q);
while(!StackEmpty(S))
EnQueue(&Q,Pop(&S));
while(!QueueEmpty(Q))
Push(&S,DeQueue(&Q));
}
(1)
(2)
32.假设具有n个结点的完全二叉树顺序存储在向量BT[1… n]中,阅读下列算法,并回答问题:
(1)若向量BT为:
A B C D E F G
1 2 3 4 5 6 7
画出执行函数f32(BT,7,1)的返回结果;
(2)简述函数f32的功能。
BinTree f32(DataType BT[],int n,int i)
{
BinTree p;
if (i>n) return NULL;
p=(BinTNode*)malloc(sizeof(BinTNode));
p->data=BT[i];
p->lchild=f32(BT,n,i2);
p->rchild=f32(BT,n,i2+1);
return p;
}
(1)
(2)
33.已知有向图的邻接表和邻接矩阵定义如下:
﹟define MaxNum 50 ∥图的最大顶点数
typedef struct node {
int adjvex; ∥邻接点域
struct node *next; ∥链指针域
} EdgeNode; ∥边表结点结构
typedef struct{
char vertex; ∥顶点域
EdgeNode *firstedge; ∥边表头指针
} VertexNode; ∥顶点表结点结构
typedef struct {
VertexNode adjlist [MaxNum]; ∥邻接表
int n,e; ∥图中当前顶点数和边数
} ALGraph; ∥邻接表描述的图
typedef struct{
char vertex[MaxNum]; ∥顶点表
int adjmatrix [MaxNum][MaxNum]; ∥邻接矩阵
int n,e; ∥图中当前顶点数和边数
} AMGraph; ∥邻接矩阵描述的图
下列算法是将邻接表描述的图G1改为邻接矩阵描述的图G2,在空白处填上适当内容使算法完整:
void f33(ALGraph G1,AMGraph *G2)
{ int i, j;
EdgeNode *p;
G2->n=G1.n;
G2->e= (1) ;
for (i=0; i<G1.n; i++)
{ G2->vertex[i]= (2) ;
p=G1.adjlist[i].firstedge;
for (j=0; j<G1.n; j++) G2->adjmatrix[i][j]=0;
while §
{ G2->adjmatrix[i][p->adjvex]=1;
(3) ;
}
}
}
(1)
(2)
(3)
五、算法设计题(本题10分)
34.设顺序表L是一个递增有序表。编写算法,要求利用二分查找法确定插入位置,将元素x插入到L中,使L保持有序。
**
答案:
**
一、单选
1-5:ACDBD 6-10: DCCBD 11-15: CAABB文章来源:https://www.toymoban.com/news/detail-528403.html
二、填空题:(每空2 分,共20分)
运算、2、3、空串、4、左子树为空、n-1、直接插入排序、h、记录
三、解答题(本大题共4小题,每小题5分,共20分)
文章来源地址https://www.toymoban.com/news/detail-528403.html
到了这里,关于数据结构复习+答案的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!