数据结构-期中前复习

青旅半醒 2022-12-14 15:54 50阅读 0赞

1-2 数据的逻辑结构是指数据的各数据项之间的逻辑关系。  
【false】数据的逻辑结构是指数据元素之间的逻辑关系，而非数据元素内部的数据项之间的关系

2-3 下列关于数据的逻辑结构的叙述中，（）是正确的。  
(2分)  
A.数据的逻辑结构是数据元素间关系的描述  
B.数据的逻辑结构反映了数据在计算机中的存储方式  
C.数据的逻辑结构分为顺序结构和链式结构  
D.数据的逻辑结构分为静态结构和动态结构  
【A】说一下B，数据的逻辑结构只反映元素之间的逻辑关系，与存储方式无关

2-10

从物理存储上可以把数据结构分为  
(2分)  
A.动态结构、静态结构  
B.顺序结构、链式结构  
C.线性结构、树形结构、图形结构和集合结构  
D.基本结构、构造型结构  
【B】物理存储即数据如何存储到内存里，内存的存储空间是顺序的，所以数据结构分为顺序结构（空间是连续的一块）或者链式结构（空间是分散的）

2-16

以下说法正确的是（ ）。  
(1分)  
A.数据元素是数据的最小单位  
B.数据项是数据的基本单位  
C.数据结构是带有结构的各数据项的集合  
D.一些表面上很不相同的数据可以有相同的逻辑结构  
【D】数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构的个数据元素的集合

1-7 对于某些算法，随着问题规模的扩大，所花的时间不一定单调增加。  
(1分)  
【True】常数阶

2-1 下面代码段的时间复杂度是（）。

x=n; //n>1
    y=0;
    while( x≥(y+1)*(y+1) )
        y++;

【B】此题x>=(y+1)\*(y+1)可转换为

n>=(y+1)\*(y+1)即有n^0.5>=y+1

所以y<=n^0.5-1

因此时间复杂度为 o(n^0.5)

int func ( int n )
    {
           int i = 0, sum = 0;
        while ( sum < n )  sum += ++i;
        return i;
    }

【B】分析：进行t次循环后，sum = (k+1)\*k/2  
(k+1)\*k/2 < n则时间复杂度为O( n 1 / 2 n^\{1/2\} n1/2)

2-4

顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。  
(2分)  
A.100  
B.105  
C.108  
D.110  
【C】p5 = 100 + (5-1) \* 2;  
第n个元素的位置 = 初始位置 + 有几个间隔（间隔的距离）

2-7

(neuDS)要将一个顺序表\{a0,a1,……,an−1\}中第i个数据元素ai(0≤i≤n-1)删除，需要移动（ ）个数据元素。  
(2分)  
A.i  
B.n-i-1  
C.n-i  
D.n-i+1  
【应该是B】 特殊值带入（i = 0） 要移动 n-1个，即B

2-11线性表L=（a1, a2 ,……，an ）用一维数组表示，假定删除线性表中任一元素的概率相同（都为1/n），则删除一个元素平均需要移动元素的个数是（C）。  
A.n/2  
B.(n+1)/2  
C.(n-1)/2  
D.n  
【C】顺序表插入的平均移动次数是(n)/2  
顺序表删除的平均移动次数是(n-1)/2

6-1 线性表元素的区间删除 (20分)

给定一个顺序存储的线性表，请设计一个函数删除所有值大于min而且小于max的元素。删除后表中剩余元素保持顺序存储，并且相对位置不能改变。  
List Delete( List L, ElementType minD, ElementType maxD );  
//思路：保留合法元素即可

List Delete(List L, ElementType minD, ElementType maxD)
    {
        
        int k = 0;
        for (int j = 0; j <= L->Last; j++)
        {
        
            if (L->Data[j] <= minD || L->Data[j] >=maxD)
            {
        
                L->Data[k++] = L->Data[j];
            }
        }
        L->Last = k - 1;
        return L;
    }

6-2 单链表元素定位 (12分)  
int ListLocate\_L(LinkList L, ElemType x)；

int ListLocate_L(LinkList L, ElemType x){
        
    	LNode *p = L->next;
    	int cnt = 1;//从首元素节点开始遍历方便
    	while (p != NULL)
    	{
        
    		if (*p == x) return cnt;
    		p = p->next;
    		cnt++;
    	}
    	return 0;
    }

6-3 删除单链表中最后一个与给定值相等的结点 (10分)  
void ListLocateAndDel\_L(LinkList L, ElemType x)

//思路：用一个指针 保存 当前 与x先等的节点的地址  
遍历链表， 结束后若不为空，那么该指针即指向最后一个符合条件的节点的地址  
在弄一个 指针 始终保存 刚才 的那个指针的前一个 元素节点（直接前驱）。