数据结构与算法导论

头号码甲 2022-11-18 发布于北京

展开全文

第一周数据储存与运算

题目1

问题重述

1.有一个包含有100个元素的数组，该100个元素从数组的第0位置连续存放，请计算完成下面每个功能所需要的步骤数：

搜索一个不在该数组中的数；

在数组的头部插入一个新元素；

在数据的尾部插入一个新元素；

删除数组头部元素；

删除数组尾部元素。

解

(1)

搜索一个不在该数组中的数

需要100步，需要遍历数组内每一个元素与搜索值进行比对

(2)

在数组的头部插入一个新元素

需要101步，由于数组连续存储，需要将100个元素分别向后移动一个储存单元，再将该元素放在空出的第一位中

(3)

在数据的尾部插入一个新元素

需要1步，由于数组连续存储，直接在数组末节点后插入新元素即可

(4)

删除数组头部元素

需要100步，先将头元素删除，再将后续的99个元素分别向前移动一个储存单元

(5)

删除数组尾部元素

需要1步，直接删除尾部元素即可

题目2

问题重述

2.计算机内存的资源是非常有限的，在处理有些问题时，并不是需要把所有的数据都保存在存储器中才能完成。假如输入的数据数量是N，可以想象N比较大，请判断下面的任务，有哪些任务需要保存输入的所有数据？有哪些任务只需要使用固定数量的变量和固定大小的数组（和N无关）？
（注：回答问题时请不要只给出结论，如果有可能，可以用伪代码或流程图或真实代码的方式给出具体的解决方案）

输出最大和最小的数；

输出所有数的中位数；

输出第k小的数，k小于100；

输出所有数的平方和；

输出N个数的平均值；

输出大于平均值的数的百分比；

将N个数据按照升序输出。

解

(1)

输出最大和最小的数

使用固定数量的变量即可，通过将第一个数指定为最大和最小值，再分别和列表中其他数对比

def max_and_min(list):
    max=list[0]
    min=list[0]
    for i in (0,len(list)-1):
        if list[i] > max:
            max = list[i]
        if list[i] < min:
            min = list[i]
    return max,min
list_test=[1,3,7,0,14]
print("(最大值,最小值):",max_and_min(list_test))

(2)

输出所有数的中位数

需要保存输入的所有数据，先通过冒泡排序将列表正序排列，之后根据索引值取出中位数

def bubblesort(list):
    for i in range(len(list)):
        for j in range(0, len(list)-i-1):
            if list[j] > list[j+1] :
                temp=list[j]
                list[j]= list[j+1]
                list[j+1]=temp
def mid(list):
    bubblesort(list)
    if len(list)%2==1:
        return list[int(len(list)/2)]
    else:
        return (list[int(len(list)/2-1)]+list[int(len(list)/2)])/2.0
    
list_test=[1,3,7,0,14]
print(mid(list_test))

(3)

输出第k小的数，k小于100

方法一

需要保存输入的所有数据，先通过冒泡排序将列表正序排列，之后取出第100个数

def bubblesort(list):
    for i in range(len(list)):
        for j in range(0, len(list)-i-1):
            if list[j] > list[j+1] :
                temp=list[j]
                list[j]= list[j+1]
                list[j+1]=temp
list_test=[1,3,7,0,14]
bubblesort(list_test)
print(list_test[99])

方法二

使用固定数量的变量即可，创建一个大小为k的顺序列表，将列表N中前k个输入作为初始值，之后分别对比每个元素，如果比k中任意元素小，则替换插入，否则则略过，最终输出列表k的末尾值

def bubblesort(list):
    for i in range(len(list)):
        for j in range(0, len(list)-i-1):
            if list[j] > list[j+1] :
                temp=list[j]
                list[j]= list[j+1]
                list[j+1]=temp
                
                
def select(list,k):
    list1=list[0:k]
    bubblesort(list1)
    for i in range(k,len(list)):
        if list[i]< list1[k-1]:
            list1[k-1]=list[i]
            bubblesort(list1)
    return list1[k-1]

list_test=[15,66,22,15,23,29,54,80,58,34,60,97,81,40,19,3,28,67,18,16,54,73,29,20,36,5,60,23,14,67,16,27,62,28,17,86,37,83,50,3,18,29,88,3,24,12,89,7,82,16,0,95,8,88,38,66,25,98,29,97]
print(select(list_test,13))

(4)

输出所有数的平方和

使用固定数量的变量即可，通过将每一个数平方后加在和变量上，可得平方和

def Quadratic_Sum(list):
    qsum=0
    for i in range(len(list)):
        qsum=qsum+list[i]*list[i]
    return qsum
list_test=[1,3,7,0,14]
print(Quadratic_Sum(list_test))

(5)

输出N个数的平均值

使用固定数量的变量即可，通过计算N个数的和之后将其除以N即可

def Average(list):
    sum=0
    for i in range(len(list)):
        sum=sum+list[i]
    return sum/len(list)
list_test=[1,3,7,0,14,4]
print(Average(list_test))

(6)

输出大于平均值的数的百分比

使用固定数量的变量即可,算出平均数后，遍历列表，统计大于平均值元素的个数，之后通过格式化输出为百分比

def Percentage(list):
    sum=0
    count=0
    for i in range(len(list)):
        sum=sum+list[i]
    average=sum/len(list)
    for i in range(len(list)):
        if list[i]> average:
            count=count+1
    return count/len(list)
list_test=[1,3,7,0,14,4]
print('percent: {:.2%}'.format(Percentage(list_test)))

(7)

将N个数据按照升序输出

需要保存输入的所有数据，通过冒泡排序将列表进行排序

def bubblesort(list):
    for i in range(len(list)):
        for j in range(0, len(list)-i-1):
            if list[j] > list[j+1] :
                temp=list[j]
                list[j]= list[j+1]
                list[j+1]=temp
list_test=[1,3,7,0,14]
bubblesort(list_test)
print(list_test)

吴博成 2021.03.08 update