2010---01

16.下列程序段的时间复杂度为_____O(n3次方)_______。

for(i=1；i<=n；i++) for(j=1；j<=n；j++) for(k=1；k<=n；k++) s=i+j+k；

17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____图状结构________。

18.在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点__直接后继__________的。

19.在栈结构中，允许插入的一端称为_____栈顶_______。

20.从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动_____n-i______个元素。 21.一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素为_____ n-i+1_______。

22.循环队列被定义为结构类型，含有三个域：data、front和rear，则循环队列sq为空的条件是___sq.front==sq.rear_________。

23.一个10阶对称矩阵A，采用行优先顺序压缩存储上三角元素，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为_______19_____。 24.对于一棵满二叉树，若有m个叶子，则树中结点数为____2m-1________。 25.含有n个顶点和n-1条边的连通图G采用____邻接表________存储结构较省空间。 26.在图中，第一个顶点和最后一个顶点相同的路径称为_____简单回路或简单环_______。 27.动态查找中两个元素X，Y存入同一个散列表时，X、Y键值相同，则这种情况称为_____冲突_______。

28.堆排序需______一_____个记录大小的辅助存储空间。

2010---10

16．下列程序段的时间复杂度为__O(根号n)_____。

i=0；s=0； while（s

17．数据的存储结构被分为顺序存储结构、___链式存储结构 ____、散列存储结构和索引存储结构4种。

18．从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动___n-i____个元素。 19．在单链表中，插入一个新结点需修改__2_____个指针。 20．在队列结构中，允许插入的一端称为___队尾____。 21．稀疏矩阵采用的压缩存储方法是___三元组表____。

22．向一个栈顶指针为top的链栈中插入一个新结点*p时，应执行p->next=top和___top=p____操作。

23．有m个叶结点的哈夫曼树所具有的结点数为__2m-1_____。

24．在一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右地给所有结点编号。设根结点编号为1。若编号为i的结点有右孩子，那么其右孩子的编号为___2i+1____。 25．在一棵树中，____根___结点没有前驱结点。

26．一个具有n个顶点的有向完全图的弧数是__n(n-1)_____。

27．n个顶点的无向图G用邻接矩阵A［n］［n］存储，其中第i列的所有元素之和等于顶点Vi的___度____。

28．选择排序的平均时间复杂度为__O(n的平方)_____。

2011---01

16.下列程序段的时间复杂度为___O(log2n)________。

i=1； while（i

17.向一个长度为n的顺序表中第i（1≤i≤n）个元素之前插入一个元素时，需向后移动___n-i+1________个元素。

18.在循环双链表中，删除最后一个结点，其算法的时间复杂度为_____0(1)______。 19.队列的插入操作在队列的___队尾________部分进行。

20.一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素为_____n-i+1______。

21.一个10阶对称矩阵A，采用行优先顺序压缩存储下三角，a00为第一个元素，其存储地址为1，每个元素占有1个存储地址空间，则a85的地址为_____42______。

22.设字符串S=″I□AM□A□STUDENT″（其中□表示空格字符），则S的长度为___14________。 23.在树形结构中，没有后继的结点是_____叶子______结点。 24.一棵深度为n(n>1)的满二叉树中共有___2n次方-1________个结点。

25.在无向图中，如果从顶点v到顶点v′有路径，则称v和v′是____连通的_______。

26.无向完全图G采用____邻接矩阵_______存储结构较省空间。

27.在顺序查找、二分查找、索引查找和散列查找四种查找方法中，平均查找长度与元素个数没有关系的查找方法是____散列查找_______。

28.快速排序最好情况下的时间复杂度为____ O(nlog2n)_______。

2011----10

16.下列程序段的时间复杂度为__O(n的平方)______。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) x++;

17.数据结构中结点按逻辑关系依次排列形成一条“锁链”的结构是___线性结构______。 18.在表长为n的顺序表上做删除运算，平均要移动的结点个数为___（n-1）/2______。 19.在带有头结点的单循环链表head中，指针p所指结点为尾结点的条件是___p->next==head______。

20.队列又称为___先进先出______的线性表。

21.顺序栈被定义为结构类型，含有两个域：data和top，则对栈*sq进行初始化的操作是_sq—>top=0________。

22.对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n2=_n0-1_______。

23.一棵具有n个结点的二叉树，采用二叉链表存储，则二叉链表中指向孩子结点的指针有__n-1_______个。

24.若连通图G的顶点个数为n，则图G的生成树的边数为___n-1______。 25.一个具有n个顶点的无向图的边数最多为___n(n-1)/2______。

26.中根遍历二叉排序树所得到的结点访问序列是键值的____递增_____序列。 27.冒泡排序的平均时间复杂度为___O(n2)______。

28.将序列{60，20，23，68，94，70，73}建成堆，则只需把20与____60_____互相交换。

2012----01

16.数据的不可分割的最小标识单位是___数据项___，它通常不具有完整确定的实际意义，或不被当作一个整体对待。

17.运算分为加工型运算和引用型运算，读取操作是__引用类型____ 运算。

18.带有头结点的单向循环链表L（L为头指针）中，指针p所指结点为尾结点的条件是 __p?next=L____。

19.在双链表中，前趋指针和后继指针分别为prior和next。若使指针p往后移动两个结点，则需执行语句 __*p=p-->next-->next____。

20.元素s1，s2，s3，s4，s5，s6依次进入顺序栈S，如果6个元素的退栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为 ____3__。 21. 稀疏矩阵一般采用的压缩存储方法是__三元组表示法____ 。 22. 在一棵树中，___根___ 结点没有双亲。

23.一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右给所有结点编号。设根结点编号为1，若编号为i的结点有父结点，那么其父结点的编号为 __i/2（取下整数）____。

24.二叉树的二叉链表存储结构中判断指针p所指结点为叶子结点的条件是__（p-->lchild==null）&&( p-->rchild==null)____。 25.边稀疏的无向图采用 __邻接表____存储较省空间。

26.除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为 __简单回路____。 27.二分查找算法的时间复杂度是 ___ O(n*log2n)___。

28.要将序列{51，18，23，68，94，70，73}建成堆，则只需把18与 __51____相互交换。

2012----10

16.下面算法程序段的时间复杂度为__0(n的3次方)____。 for (i=1; i<=n; i++)

for (j=1; j<=n; j++) for (k=1;k<=n;k++) x++

17.所有存储结点存放在一个连续的存储区里利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。这种存储方式是___顺序存储方式___。

18.单链表中指针p指向结点A若要删除A之后的结点存在且不释放存储空间则需要修改指针的操作为p->next=__p->next-->next____。

19.在带有头结点的单链表head中首结点的指针为__head-->next____。 20.在栈结构中允许插入和删除的一端称为__栈顶____。

21.C程序中将对称矩阵Ann的下三角元素压缩存储到n(n+1)/2个元素的一维数组M中设aiji≥j存放在数组Mk中则k的值用i,j表示为__(i+1)*i/2+j____。 22.具有64个结点的完全二叉树的深度为___7___。

23.某二叉树的先序遍历序列为AJKLMNO中序遍历序列为JLKANMO则根结点A的右子树中的结点个数为___3___。

?011???24.三个顶点v1,v2,v3的图的邻接矩阵为?101?则该图中顶点v2的出度为__2____。

?000???25.除第一个顶点和最后一个顶点相同外其余顶点不重复的回路称为__简单回路或简单环____。

26.在顺序查找、二分查找、散列查找和索引顺序查找四种查找方法中平均查找长度与元素个数没有关系的查找方法是___散列查找___。

27.堆排序算法的时间复杂度为_O(n*logn2(n))_____。