數(shù)據(jù)結(jié)構(gòu)習(xí)題及答案

1、1第1章算法一、選擇題一、選擇題1.算法的時(shí)間復(fù)雜度是指（）。A）執(zhí)行算法程序所需要的時(shí)間B）算法程序中的指令條數(shù)C）算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)D）算法程序的長(zhǎng)度2.算法的空間復(fù)雜度是指（）。A）算法程序的長(zhǎng)度B）算法程序所占的存儲(chǔ)空間C）算法執(zhí)行過(guò)程中所需要的存儲(chǔ)空間D）算法程序中的指令條數(shù)3.下面（）的時(shí)間復(fù)雜度最好（即執(zhí)行時(shí)間最短）。A）O(n)B）O()n2logC）O(n)D）O(n2)n2log4.下面累加求和程序段

2、的時(shí)間復(fù)雜度為（）。intsum(inta[]intn)intis=0f(i=0ini)s=a[i]returnsA）O(1)B）O()n2logC）O(n)D）O(n2)5.下面是將兩個(gè)n階矩陣a[][]與b[][]相加的結(jié)果存放到n階矩陣c[][]中的算法，該算法的時(shí)間復(fù)雜度為（）。voidmatrixadd(inta[][]intb[][]c[][]intn)intijf(i=0ini)f(j=0jnj)c[i][j]=a[i][

3、j]b[i][j]A）O(1)B）O()n2logC）O(n)D）O(n2)6.下面程序段的時(shí)間復(fù)雜度為（）。3C）O(n)D）O()n9.下面程序段的時(shí)間復(fù)雜度為（）intijmna[][]f(i=0imi)f(j=0jnj)a[i][j]=ijA）O(m2)B）O(n2)C）O(mn)D）O(mn)10.下面程序段的時(shí)間復(fù)雜度為（）intsum1(intn)intip=1s=0f(i=1i=ni)p=is=spreturnsA）O(

4、1)B）O()n2logC）O(n)D）O(n2)二、填空題二、填空題1.算法復(fù)雜度主要包括時(shí)間復(fù)雜度和復(fù)雜度。2.一個(gè)算法的時(shí)間復(fù)雜度的計(jì)算式為(3n22n5)n，其數(shù)量級(jí)表示為。3.從一維數(shù)組a[n]中順序查找出一個(gè)最大值元素的平均時(shí)間復(fù)雜度為，讀取一個(gè)二維數(shù)組b[m][n]中任一元素的時(shí)間復(fù)雜度為。4.在下面程序段中，s=sp語(yǔ)句的執(zhí)行次數(shù)為，p=j語(yǔ)句的執(zhí)行次數(shù)為，該程序段的時(shí)間復(fù)雜度為。inti=0s=owhile(i=n)i