【数据结构】复习题(一)

2023-12-17 21:38:51

一、选择题
1.组成数据的基本单位是()。
A. 数据项 B.数据类型 C.数据元素 D.数据变量

2.设数据结构A={D,R},其中D={1,2,3,4},R={r},r={<1,2>,<2,3>,< 3,4>,<4,1>},则数据结构A是()。
A.线性结构 B.树型结构 C.图型结构 D.集合

3.数组的逻辑结构不同于下列()的逻辑结构。
A.线性表 B.栈 C.队列 D.树

4.二叉树第i(i≥1)层上的结点最多有()个。
A.2i B. 2 i 2^i 2i C. 2 i ? 1 2^{i-1} 2i?1 D.2i-1

5.设指针变量p指向单链表结点A,则删除结点A的后继结点B所需的操作为()。
A.p->next=p->next->next
B.p=p->next
C.p=p->next->next
D.p->next=p

6.设栈S和队列Q的初始状态为空,元素E1,E2,E3,E4,E5,E6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素的出列顺序为E2、E4、E3、E6、E5和E1,则栈S的容量至少应该是()。
A.6 B.4 C.3 D.2
见图解:

根据队列的性质,先进先出,所以进入队列Q的顺序也是E2、E4、E3、E6、E5、E1
同时这也是出栈S的顺序。
A.6 B.4 C.3 D.2
由此可知,栈S的容量至少为3.

7.将10阶对称矩阵压缩存储到一维数组中,则数组A的长度最少为()。
A.100 B.40 C.55 D.80
10阶矩阵共有100个元素,其对角线元素共有10个,对角线以上或者一下的元素共有(100-10)/2=45个,加上对角线的元素个数,即数组A的长度最少为55个。

8.设结点A有3个兄弟结点且结点B为结点A的双亲结点,则结点B的度数为()。
A.3 B.4 C.5 D.1

9.根据二叉树的定义可知,二叉树共有()种不同的形态。
A.4 B. 5 C.6 D.7

10.假设有一下四种排序方法,则()的空间复杂度最大。
A.冒泡排序 B.快速排序 C.堆排序 D.希尔排序
冒泡排序、堆排序、希尔排序的空间复杂度都是O(1)。快速排序算法中有递归,递归的深度,为O(logn),即快速排序所需要的辅助空间为O(logn)。

二、填空题
1.设顺序循环队列Q[0:m-1]的队头指针和队尾指针分别为F和R,其中队头指针F指向队头元素的前一个位置,队尾指针指向当前队尾元素所在的位置,则出队列的语句是F=(F+1)%m

2.设线性表中有n个数据元素,则在顺序存储结构上实现顺序查找的平均时间复杂度为_____,在链式存储结构上实现顺序查找的平均时间复杂度为______。
在顺序存储结构上实现顺序查找,最好情况是,比较1次,最坏情况是比较n次,平均比较次数为(n+1)/2,所以平均时间复杂度为O(n)
在链式存储结构上实现顺序查找,最好情况是,比较1次,最坏情况是比较n次,平均比较次数为 (n+1)/2,则平均时间复杂度为O(n)

3.设一颗二叉树有n个结点,则当用二叉链表作为其存储结构时,该二叉树中共有____个指针域,____个空指针域。
二叉树的链式存储方式下,每个结点包含3个域,分别是属性值data域,两个指针域lchild和rchild。

显然,该二叉树中共有2n个指针域。
空指针域=度为1的结点数+2×叶子结点树。
即空指针域 = n 1 + 2 n 0 =n_1+2n_0 n1?+2n0?
首先 n = n 1 + n 2 + n 0 n=n_1+n_2+n_0 n=n1?+n2?+n0?
n = n 1 + 2 n 2 + 1 n=n_1+2n_2+1 n=n1?+2n2?+1
联立上面两个式子得到, n 1 + 2 n 0 = n + 1 n_1+2n_0=n+1 n1?+2n0?=n+1

4.指针变量p指向单链表中结点A,指针变量s指向被插入的结点B,则在结点A的后面插入结点B的操作序列为____。
s->next=p->next;
p->next=s;

6.设无向图G中有n个顶点和e条边,则其对应的邻接表中有_____个表头结点和___个表结点。
无论是有向图还是无向图,图中有几个顶点,就对应邻接表有几个表头结点。所以对应的邻接表有n个表头结点。
对于表结点,一般是对应图中的顶点与顶点之间的关系,对于有向图,表头结点的个数是图中的边数,对于无向图,需要×2。
故,n ,2e
6.设无向图G中有n个顶点e条边,所有顶点的度数之和为m,则e和m有___关系。
这道题,同上面的题思路一样,可以得知m=2e

7.设一颗二叉树的前序遍历和中序遍历序列均为ABC,则该二叉树的后序遍历序列为______。
首先根据二叉树的前序和中序遍历,可以画出这颗二叉树,从而写出后序遍历。

8.设一颗完全二叉树中有21个结点,如果按照从上到下,从左到右的顺序从1开始顺序编号,则编号为8的双亲结点的编号为_____,编号为8的左孩子结点的编号为____。

因为题目说编号为8,还行,不是很大,所以直接无脑画出来,然后就知道了。
4,16.

9.下列程序段的功能实现子串t在主串s中位置的算法,要求在下划线处填上正确语句。

int index(char s[],char t[])//函数参数主串s和子串tint i=j=0;
    while(i<strlen(s) && j<strlen(t) )
    {
        if (s[i]=t[j])
        {
            i=i+1;//主串指针移动
            j=j+1;//子串指针移动
        }
        else//填空
           //继续循环匹配
           i=i-j+1;//主串从原来开始匹配的那个元素的下一个元素继续
           j=0;//子串仍然从第一个位置开始比较}
    if (j==strlen(t)) //t的值只能为0-t 当j=t时说明匹配成功
    {
        return (i-strlen(t));//返回位置
    }
    else 
        return -1;
}

10.设一个连通图G中有呢个顶点e条边,则其最小生成树上有____条边。
生成树的定义是一个包含连通图中所有顶点的树,并且只包含连通图中的边。
因为一个连通图中的生成树只需要包含所有结点,所以生成树的边数比顶点少1。即当一个连通图具有n个顶点时,它的生成树将有n-1条边。

三、应用题
1.设一颗完全二叉树的顺序存储结构中存储数据ABCDE,要求给出该二叉树的链式存储结构,并给出该二叉树的前序、中序和后序遍历序列。

2.设给定一个权值集合 W={3,5,7,9},要求根据跟定的权值集合构造一颗哈夫曼树,并计算哈夫曼树的带权路径WPL。

3.设一组初始记录关键字序列为(19,21,16,5,18,23),要求给出以19为基准的一趟快速排序结果以及第2趟直接排序后的结果。

【快速排序】的基本步骤:
先将第一个记录(设排序码为x)缓存,这样就空出了一个位置,改位置应该存放排序码不大于x的记录,将它放在第一个位置,这样,后面又空出一个位置,它应该放排序码大于x的记录,反过来又从第二个记录开始向右找一个排序码大于x的记录,将它放在后面空出的位置,重复这种两边向中间逼近的过程,可以将所有排序码不大于x的记录放在前面,而所有排序码大于x的记录放在后面,最后当两边逼近于同一位置时,便将暂存的x放于该位置,即达到了划分的目的。
【直接选择排序】
直接选择排序是一种简单的排序方法,首先从所有n个待排记录中选择排序码最小的记录,将该记录与第一个记录交换,再从剩下的n-1个记录中选出排序码最小的记录与第二个记录交换。重复这样的操作直到剩下两个记录时,再从中选取排序码最小的记录和第in-1个记录交换。剩下的那一个记录肯定是排序码最大的记录,这样排序即完成。


4.设置=一组初始记录关键字集合为(25,10,8,27,32,68),散列表的长度为8,散列函数为H(k)=k mod 7,要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表。
先求出每个关键词所对应的函数值。

用线性探测法解决:

(这里我第一遍做错了,原因是,线性表的长度为8)

用链地址法解决:

5.设无向图G,给出该图的深度优先和广度优先遍历的序列,并给出该图的最小生成树。

这里的深度优先和广度优先遍历答案不唯一。
给出其中的一种:
深度优先遍历:
125364
广度优先遍历:
123456
分别用Kruskal算法和Prim算法来生成最小生成树。
在这里插入图片描述

四、
1.设计算法判断单链表中结点是否关于中心对称算法。
思路:我们可以利用栈结构来解这道题。
关于链表对称,一是可以认为找到单链表的中心点,单链表左边和链表右边关于中心点对称。
二是可以认为,将单链表倒置,和原来的一样。
关于算法的设计,采用二思路可以更简洁地完成。

首先,创建栈机构。

typedef struct{
    int s[100];
    int top;
}sqstack;

然后创建函数。

int 1Klistsymmetry(1klist *head)
{
    //创建栈并初始化栈结构
    sqstack stack;
    stack.top=-1;
    1klist *p;
    
    //元素入栈
    for (p=head;p!=0;p=p->next)
    {
        stack.top++;
        stack.s[stack.top]=p->data;
    }
    //匹配
    for (p=head;p!=0;p=p->next)
    {
        //如果相等 出栈
        if (p->data==stack.s[stack.top])
            stack.top=stack.top--;
        else
            //不相等直接返回
            return 0;
    }
    return 1;

}

2.设计在链式存储结构上建立一颗二叉树的算法。

利用递归的思想来建立二叉树。
定义结点。

typedef char datatype;
typedef struct node
{
    datatype data;
    struct *lchild;
    struct *rchild;
}bitree;
void createbitree (bitree t)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
    {
        t=NULL;
        return;
    }
    else
    {
        t=(bitree*)malloc(sizeof(bitree));
        t->data=ch;
        //创建左子树
        createbitree(t->lchild);
        //创建右子树
        createbitree(t->rchild);
    }
}

文章来源:https://blog.csdn.net/2302_76305195/article/details/135037752
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。