文档介绍：试卷代号:1252
中央广播电视大学2008--2009学年度第一学期“开放本科”期末考试
数据结构(本) 试题
一、单项选择题(每小题2分。共30分)
( )。

( )的关系。

( )有关。 7

,p、q分别指向表中两个相邻的结点,且q所指结点是P所指结点的直接后继,现要删除q所指结点,可用的语句是( )。
=q->next ->next=q
->next=q->next ->next=NULL
,假设f和r分别为队头和队尾指针,则删除一个结点的运算为( )。
=f->next: =r->next: =f一>next; =r一>next:
,6,9按顺序依次进栈,则该栈的不可能输出序列是( )(进栈出栈可以交替进行)。
,6,3 ,3,6 ,3,9 ,9,6
,采用压缩存储的方式,将其下三角部分以行序为主存储到一维数组8中(数组下标从1开始),则矩阵中元素氏,。在一维数组B中的下标是(. )。

,顺序存储长度为3的字符串,需要占用( )个字节。

,共有( )个指针域为空。
+1 --2
,则该树有( )个非叶结点。
—l +1
,所有顶点的度数之和等于边数的( )倍。

,若从顶点V。出发,按广度优先进行遍历,则可能得到的一种顶点序列为( )。
{2,4,7,14,34,43,47,64,75,80,90,97,120)中,用折半查找法查找值80时,经( )次比较后查找成功。

,从未排序序列中依次取出元素与已排序序列(初始为空)中的元素进行比较(要求比较次数尽量少),然后将其放入已排序序列的正确位置的方法是( )。

,从尚未排序序列中挑选元素,并将其依次放入已排序序列(初始为空)的一端的方法,称为( )排序。

二、填空题(每小题2分。共24分)
1·结构中的数据元素存在多对多的关系称为——结构。
,设基本操作为元素间的比较。则比较的
次数和算法的时间复杂度分别为---------和----