国家开放大学本科末考试数据结构历年试题与参考答案15秋至19秋

国家开放大学(中央广播电视大学)2015年秋季学期

“开放本科”期末考试数据结构(本)试题

2016年1月

一、单项选择题(每小题2分，共30分)

1.对稀疏矩阵进行压缩存储，可采用三元组表，一个有10行的稀疏矩阵A共有97个零元素，其相应的三元组表共有3个元素。该矩阵A有( )列。 A.8 B.9 C.7 D.10

答案：10

2.子串“acd”在主串“abdcacdefac”中的位置是( )。 A.3 B.5 C.7 D.1

答案：5

3.序列12，16，8，4按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的不可能输出序列是( )。(进栈、出栈可以交替进行)。 A.16，12，8，4 B.4，8，12，16 C.8，4，16，12 D.16，12，4，8

答案：B.4，8，12，16

4.在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，对该队列进行出队操作，并把结点的值保存在变量e中，其运算为( )。 A.e=f->data； r=r->next B.e=f->data； r->next=r C.e=f->data； f=f->next D.e=f一>data； f一>next=f

答案：C.e=f->data； f=f->next

5.数据的逻辑结构在计算机内存中的表示是( )。 A.给相关变量分配存储单元 B.数据的存储结构 C.数据的逻辑结构 D.算法的具体体现

答案：数据的存储结构

6.以下说法正确的是( )。

A.线性表的链式存储结构必须占用连续的存储空间 B.一种逻辑结构可以有不同的存储结构 C.一种逻辑结构只能有唯一的存储结构

D.线性表的顺序存储结构不必占用连续的存储空间

答案：一种逻辑结构可以有不同的存储结构

7.在一个单链表中要删除p所指结点的后继结点，可执行q=p一>next；和( )。 A.p一>next=q->next B.p=q->next C.p->next=q D.p->next=q

答案：A.p一>next=q->next

8.在数据结构和算法中，与所使用的计算机有关的是( )。 A.数据元数间的抽象关系 B.数据的存储结构 C.算法的时间复杂度 D.数据的逻辑结构

答案：数据的存储结构

9.以下表中可以随机访问的是( )。 A.单向链表 B.双向链表

C.单向循环链表 D.顺序表

答案：顺序表

10.头指针为head的不带头结点的单向链表为空的判定条件是逻辑表达式( )为真。

A.head==NULL

B.head->next==NULL C.head->next=NULL D.head一>next!=NULL

答案：head==NULL

11.设有一个长度为32的顺序表，要在第5个元素之前插入1个元素(也就是插入元素作为新表的第5个元素)，需移动元素个数为( )。 A.25 B.28 C.5 D.6

答案：28

12.设有一个长度为33的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为( )。 A.11 B.10 C.23 D.14

答案：23

13.设有一个28阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则数组中第26号元素对应于矩阵中的元素是( )。 A.a7，5 B.a7，6 C.a6，5 D.a7，4

答案：a7，5

14.在一个不带头结点的单循环链表中，p、q分别指向表中第一个结点和尾结点，现要删除第一个结点， 且p、q仍然分别指向新表中第一个结点和尾结点。可用的语句是p=p一>next； 和( )。 A.p=q->next B.p->next=q C.q=p

D.q一>next=p

答案：q一>next=p

15.在一棵二叉树中，若编号为16的结点是其双亲结点的左孩子，则他的双亲结点的顺序编号为( )。 A.7 B.8 C.32 D.33

答案：8

二、填空题(每小题2分，共24分)

16.数据的逻辑结构在计算机中的表示称为（ 物理存储 ）结构。

17.四类基本结构分别为（ 集合、线性、树形、图状 ）结构。

18.队列的操作特点是先进（ 先出 ）。

19.广义表((b，a，c)，c，d，(e，i，j，k))的表尾是（ (c，d，(e，i，j，k)) ）。

20.设有一个长度为20的顺序表，第8号元素到第20号元素依次存放的值为8，9，…，20。某人想要在第8号元素前插入1个元素7(也就是插入元素作为新表的第8个元素)，程序中他的做法是

用语句for(i=8； i<=20； i++) a[i+1] =a[i] ； a[8] =7； 即从第8号元素开始， 直到第20号元素，每个元素依次向后(右)移动1个位置，然后把7存放在第8号位置。

事实上这样做是错误的.其结果是新表中第20号元素的值为（ 8 ）。

21.设有一棵有38个结点的完全二叉树，该树共有（ 6 ）层。(根所在结点为第1层)

22.一棵有18个结点的二叉树，其2度结点数的个数为8，则该树共有（ 1 ）个1度结点。

23.对一组记录(1，3，9，2，12，7，5，4，6)进行直接插人排序(由小到大排序)，当把第6个记录7插人有序表，为寻找插人位置需比较（ 3 ） 次。

24.序列5，3，8，4，7，6，采用冒泡排序算法，经一趟冒泡后，序列的结果是（ 3，5，4，7，6，8 ）。(按升序排序)

25.广义表(b，a，(c，b)，f，e，((i，j)，k))的长度是（ 6 ）。

26.一棵有18个叶结点的哈夫曼树，则该树共有（ 17 ）个非叶结点。

27.对稀疏矩阵进行压缩存储，可采用三元组表，一个8行7列的稀疏矩阵A共有51个零元素，其相应的三元组表共有（ 5 ）个元素。

三、问答和综合题(每小题10分，共30分)

28.设数据集合a={6，17，10，13，8，15，12，18，14} (1)依次取a中各数据，构造一棵二叉排序树。 (2)给出对该二叉树中序遍历的序列。

(3)对该二叉树进行查找，成功查找到14要进行多少次元素间的比较?

29.设有序表为(2，5，11，12，30，48，58)，元素的序号依次为1，2，3，…7. (1)画出对上述查找表进行折半查找所对应的判定树(树中结点用序号表示)。 (2)说明成功查找到元素11需要经过多少次比较? (3)在等概率条件下，给出成功查找的平均查找长度?

30.(1)如图1所示，若从顶点a出发，首先经过顶点c按广度优先搜索法进行遍历，给出可能得到的一种顶点序列。

(2)如图1所示，给出从顶点h出发，首先经过顶点d和e按深度优先搜索法进行遍历，给出可能得到的一种顶点序列。

(3)一组记录的关键字序列为(80，57，41，39，46，47)，利用堆排序的方法的方法建立小根堆(堆顶元素是最小元素)，给出按筛选法建立的的初始堆。

四、程序填空题(每空2分，共16分)

31.以下冒泡法程序对存放在a[1]，a[2]，……，a[n]中的序列进行冒泡排序，完成程序中的空格部分，其中n是元素个数，程序按升序排列。 void b sort(NO DEal， int) { NODE temp；

inti， j， flag；

for(j=1； j<=n一1； ① j++ { flag=0；

for(i=1； ② i<=n一j ；i十十) if(a[i] .key>a[i+1] .key) { flag==1；

③ temp=a[i] ；

a[i] =ali+1] ； ④ a[i+1] =temp；

}

if(flag==0) break；

} }

程序中flag的功能是⑤ 判断某一趟排序中是否有元素交换

32.以下函数为链栈的出栈操作，出栈结点的数据由x返回 struct node

{ Elem Type data；

struct node*next； }；

Elem Type Pop( ) { in tx；

if(top==① NULL ) {

printf(\"栈下溢错误!\\n\") ；

exit(1) ；

}

X= top→data ; top= top-next ; return x； }

四、程序填空题(每空2分，共16分)

31.(10分) (1) (2)

(3) (4) (5) 32.(6分) (1) (2) (3)

国家开放大学(中央广播电视大学)2016年春季学期“开放本科”期末考试

数据结构(本)试题2016年7月

一、单项选择题(每小题2分，共30分)

1.对稀疏矩阵进行压缩存储，可采用三元组表，一个10行8列的稀疏矩阵A共有73个零元素，其相应的三元组表共有( )个元素。 A.8 B.80 C.7 D.10

参考答案：7

2.字符串( ) 是“abcd321ABCD”的子串。 A.“21AB” B.“abcD” C.“aBCD” D.“321a”

参考答案：“21AB”

3.栈和队列的共同特点是( )。 A.都是操作受限的线性结构 B.元素都可以随机进出 C.都是先进后出 D.都是先进先出

参考答案：都是操作受限的线性结构

4.在一个链队中，假设f和r分别为队头和队尾指针，p指向一个新结点，要为结点p所指结点赋值x， 并人队的运算为p->data=x； p->next=NULL； ( ). A.f一>next=p； f=p； B.r一>next=p； r=p； C.r=p； p->next=r； D.p->next=f； f=p；

参考答案：r一>next=p； r=p；

5.数据结构中，与所使用的计算机无关的是数据的( )结构。 A.逻辑 B.存储

C.逻辑与存储 D.物理

参考答案：逻辑

6.顺序表所具备的特点之一是( )。 A.可以随机访问任一结点 B.不需要占用连续的存储空间 C.插人元素的操作不需要移动元素 D.删除元素的操作不需要移动元素

参考答案：可以随机访问任一结点

7.数据元素是数据的基本单位，它( )。 A.只能有一个数据项组成 B.至少有二个数据项组成

C.可以是一个数据项也可以由若干个数据项组成 D.至少有一个数据项为指针类型

参考答案：可以是一个数据项也可以由若干个数据项组成

8.设有头指针为head的非空的单向链表， 指针p指向其尾结点，链表成为单向循环链表，则可利用下述语句( )。 A.p=head； B.p=NULL； C.p->next=head； D.head=p；

参考答案：p->next=head；

9.在线性表的顺序结构中，以下说法正确的是( )。 A.逻辑上相邻的元素在物理位置上不一定相邻 B.数据元素是不能随机访问的

C.逻辑上相邻的元素在物理位置上也相邻 D.进行数据元素的插人、删除效率较高

参考答案：逻辑上相邻的元素在物理位置上也相邻

10.对链表，以下叙述中正确的是( )。 A.不能随机访问任一结点

要使该单向

B.结点占用的存储空间是连续的

C.插人删除元素的操作一定要要移动结点 D.可以通过下标对链表进行直接访问

参考答案：不能随机访问任一结点

11.设有一个长度为35的顺序表，要在第5个元素之前插入1个元素(也就是插入元素作为新表的第5个元素)，则移动元素个数为( )。 A.30 B.31 C.5 D.6

参考答案：31

12.设有一个长度为40的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为( )。 A.11 B.10 C.30 D.31

参考答案：30

13.设有一个25阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则矩阵中元素ar，s在一维数组B中的下标是( ). A.25 B.24 C.26 D.27

参考答案：26

14.线性表在存储后，如果相关操作中有要求：利用已知的指向某结点的指针或序号，访问该结点的前驱结点，则采用( )的存储方式是不可行的。 A.单向链表 B.双向链表

C.单向循环链表 D.顺序表

参考答案：单向链表

15.在一棵二叉树中，若编号为i的结点存在左孩子，i结点的左孩子的顺序编号为( )。 A.i/2.0

B.2*i C.2*i+1 D.i十2

参考答案：2*i

二、填空题(每小题2分，共24分)

16.广义表((b，a，c)，c，d，f，e，((i，j)，k))的长度是____________.

参考答案：6

17.数据结构中，数据元素之间的抽象关系称为____________结构。

参考答案：逻辑

18.栈的操作特点是后进______________.

参考答案：先出

19.广义表((b，a，c)，c，d，f，e，((i，j)，k))的表头是________________.

参考答案：(b，a，c)

20.设有一个长度为18的顺序表，第8号元素到第18号元素依次存放的值为8，9，…，18.某人想要删除第8号元素， 程序中他的做法是用语句for(i=18； i<=9； i--) a[i-1] =a[i] ； 即从第18号元素开始，直到第9号元素，每个元素依次向前(左)移动1个位置，事实上这样做是错误的，其结果新表中第9号元素的值为_________________________.

参考答案：18

21.一棵二叉树，有1个2度结点，2个1度结点，则该树共有________个结点。

参考答案：5

22.设有一棵深度为5的完全二叉树，该树共有21个结点，第5层上有_____个结点。(根所在结点为第1层)

参考答案：6

23.中序遍历______________树可得到一个有序序列。

参考答案：二叉排序树

24.序列12，10，13，11，16，14，采用冒泡排序算法，经一趟冒泡后，序列的结果是_____________________.(按升序排序)

参考答案：10，12，11，13，14，16

25.对16个元素的序列用冒泡排序法进行排序，共需要进行________趟冒泡。

参考答案：15

26.一棵有16个叶结点的哈夫曼树，则该树共有_________个非叶结点。

参考答案：15

27.在对一组记录(40，24，82，9，1，78，46，31，69)进行直接插人排序(由小到大排序)，当把第7个记录46插人到有序表时，为寻找插人位置需比较__次。

参考答案：3

三、问答和综合题(每小题10分，共30分)

28.设有序表为(5，8，14，15，33，51，61，73，81，82，93)，元素的序号依次为1，2，3，……，11.

(1)画出对上述查找表进行折半查找所对应的判定树(树中结点可用序号表示) (2)说明成功查找到元素33需要经过多少次比较? (3)在等概率条件下，给出成功查找的平均查找长度?

参考答案：

29.(1)如图1所示，若从顶点a出发，首先经过c按图的深度优先搜索法进行遍历，给出可能得到的一种顶点序列。

(2)设有向图如图2所示下，写出首先删除顶点1的1种拓扑序列。

参考答案：

30.(1)设数据集合a={7，4，9，8，6，5，3}，依次取a中各数据，构造一棵二叉排序树。

(2)对该二叉树进行查找，成功查找到5要进行多少次元素间的比较? (3)给出对上述二叉排序树进行中序遍历的序列

参考答案：

四、程序填空题(每空2分，共16分)

31.以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回一1，完成程序中的空格 typedef struct { int key；

… } NODE；

int Binary_Search(NODE a[] ，int n，int k) {

int low， mid， high；

low=0；

high=n一1；

while①_________________ {

mid=(low+high) /2；

if(a[mid] .key==k)

return②________________; elseif③____________________

low=mid+1；

else④________________;

}

⑤__________________; }

参考答案： (1) low<=high

(2) mid

(3) a[mid] .key32.以下函数为链栈的进栈操作， x是要进栈的结点的数据域， top为栈顶指针。

struct node

{ ElemType data；

struct node*next； }；

struct node*top；

void Push(ElemType x) { struct node*p；

p=(struct node*) malloc①______________; p->data=x；

②___________________; ③___________________; }

参考答案：

(1) sizeof(struct node) (2) p->next=top (3) top=p

国家开放大学(中央广播电视大学)2017年春季学期“开放本科”期末考试

数据结构(本)试题2017年6月

一、单项选择题(每小题3分，共30分)

1.设有一个长度为26的顺序表，要插人一个元素，并使它成为新表的第6个元素，需移动元素的个数为( )。 A.21 B.22 C.20 D.19

参考答案：21

2.头指针为head的带头结点的单向循环链表， p指向尾结点， 要使该链表成为不带头结点的单向循环链表， 可执行head=head->next； 和( )。 A.p=head->next B.head->next=p

C.head->next=p->next D.p->next=head；

参考答案：p->next=head；

3.元素111，113，115，117按顺序依次进栈，则该栈的不可能输出序列是( )(进栈出栈可以交替进行)。 A.117，115，113，111 B.111，113，115.117 C.117，115，111，113 D.113，111，117，115

参考答案：117，115，111，113

4.设有一个20阶的对称矩阵A(第一个元素为a1.1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则矩阵元素a6.2在一维数组B中的下标是( )。 A.21 B.17 C.28 D.23

参考答案：17

5.设有串pl=”ABADF”， P2=”ABAFD”， P3=”ABADFA”， P4=”ABAF”， 以下四个串中最大的是( )。 A.p3 B.p2 C.pl D.p4

参考答案：p2

6.在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为( ). A.2i+1 B.2i-1 C.2i D.2i+2

参考答案：2i

7.如图1所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为( ).

A.abecdf B.aecbdf C.aebcfd D.aedfcb

参考答案：aecbdf

8.线性表以( )方式存储，能进行折半查找。 A.链接 B.顺序

C.关键字有序的顺序 D.二叉树

参考答案：关键字有序的顺序

9.一棵具有38个结点的完全二叉树，最后一层有( )个结点。 A.7 B.5 C.6 D.8

参考答案：7

10.下图的拓扑序列是(

A.52346 B.23645 C.56234 D.23564

参考答案：56234

二、填空题(每小题2分，共24分)

11.结构中的数据元素存在多对多的关系称为____________结构。

参考答案：图状

12.n个元素进行冒泡法排序，第j趟冒泡要进行__________次元素间的比较。

参考答案：n-j

13.中序遍历__________树可得到一个有序序列。

参考答案：二叉排序树

14.待排序的序列为8，3，4，1，2，5，9，采用直接选择排序算法，当进行了两趟选择后：结果序列为____________________.

参考答案：1，2，4，8，3，5，9

15.广义表((a，b)，d，e，((i，j)，k))的长度是__________.

参考答案：4

16.广义表的(c，a，(a，b)，d，e，((i，j)，k))深度是__________.

参考答案：3

17.对稀疏矩阵进行压缩存储，可采用三元组表，一个有10行10列的稀疏矩阵A共有95个零元素，其相应的三元组表共有__________个元素。

参考答案：5

18.在对一组记录(50，49，97，22，16，73，65，47，88)进行直接插人排序时，当把第7个记录65插人到有序表时，为寻找插人位置需比较__________次。

参考答案：3

19.一棵有5个叶结点的哈夫曼树，该树中总共有________个结点。

参考答案：9

20.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有_________ 个结点。(根所在结点为第1层)。

参考答案：12

21.设有一个长度为40的顺序表，要删除第8个元素需移动元素的个数为____.

参考答案：32

22.有以下程序段 char a[] =\"English”； char*p=a； int n=0；

while(*p!=‘\\0’) {n++； p++； ) 结果中， n的值是________.

参考答案：7

三、综合题(每小题中每问5分，共30分)

23.有一个长度为11的有序表(1，2，11，15，24，28，30，56，69，70，80)，元素的下标依次为1，2，3，……，11，按折半查找对该表进行查找。 (1)画出对上述查找表进行折半查找所对应的判定树。

(2)说出成功查找到元素56，需要依次经过与哪些元素的比较? (3)说出不成功查找元素72，需要进行元素比较的次数?

参考答案：

24.(1)一组记录的关键字序列为(57.90，67，50，51，56)，利用堆排序(堆顶元素是最小元素)的方法建立初始堆(要求以完全二叉树描述)。

(2)对关键字序列(56.51，71，54，46，106)利用快速排序，以第一个关键字为分割元素，给出经过一次划分后的结果。

(3)一组记录的关键字序列为(60，47，80，57，39，41，46，30)，利用归并排序的方法，分别给出(1，1)归并、(2，2)归并、(4，4)归并的结果序列。

参考答案：

四、程序填空题(每空2分，共16分)

25.设线性表为(16， 20， 26， 24) ， 以不带头结点的单向链表存储， 链表头指针为head， 以下程序的功能是输出链表中各结点中的数据域data。 Struct node { int data；

struct node*next； }；

typedef struct node NODE； #define NULL O void main()

{ NODE*head，*p；

p=head； /*p为工作指针*/ do

{ printf(“%d\\n”，(1)_______________)；

(2)______________________; } while((3)______________________)

}

参考答案： (1) p->data (2) p=p->next (3) p!=NULL

26.以下函数为直接选择排序算法，对a[1]，a[2]，…a[n]中的记录进行直接选择排序，完成程序中的空格 typedef struct { int key ;

…

} NODE；

void selsort(NODE a[]，int n) {

int i，j，k； NODE temp；

for(i=l； i<=(1)_____________；i十十) { k=i； for(j=i+1； j<=(2)______________；j十十) if(a[j] .key{ temp=a[i] ； (4)__________________________; (5)_____________________________; }

}

}

参考答案： (1)n-1 (2)n (3)k=j

(4)a[i]=a[k] (5) a[k] =temp

国家开放大学(中央广播电视大学)2017年秋季学期“开放本

科”期末考试数据结构(本)试题2018年1月

一、单项选择题(每小题3分，共30分)

1.设有头指针为head的带有头结点的非空单向循环链表， 指针p指向其尾结点， 要删除头结点， 并使其仍为单向循环链表， 则可利用下述语句head==head一>next； ( )。 A.p=head； B.p=NULL；

C.p一>next=head； D.head=p；

参考答案：p一>next=head；

2.以下说法不正确的是( )。

A.线性表的链式存储结构不必占用连续的存储空间 B.一种逻辑结构只能有唯一的存储结构 C.一种逻辑结构可以有不同的存储结构

D.线性表的顺序存储结构必须占用连续的存储空间

参考答案：一种逻辑结构只能有唯一的存储结构

3.把数据存储到计算机中，并具体体现( )称为物理结构。 A.数据元素间的逻辑关系 B.数据的处理方法 C.数据的性质 D.数据的运算

参考答案：数据元素间的逻辑关系

4.链表所具备的特点之一是( )。 A.可以随机访问任一结点 B.需要占用连续的存储空间

C.插人元素的操作不需要移动元素 D.删除元素的操作需要移动元素

参考答案：插人元素的操作不需要移动元素

5.图状结构中数据元素的位置之间存在( )的关系。 A.一对一 B.多对多 C.一对多

D.每一个元素都有一个直接前驱和一个直接后继

参考答案：多对多

6.元素15，9，11，13按顺序依次进栈，则该栈的不可能输出序列是( )(进栈出栈可以交替进行)。 A.13，11，9，15 B.15，9，11，13 C.13，11，15，9 D.9，15，13，11

参考答案：13，11，15，9

7.设有一个14阶的对称矩阵A(第一个元素为a1，1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则矩阵中元素a4.3在一维数组B中的下标是( )。 A.9 B.10 C.11 D.8

参考答案：9

8.在一棵二叉树中，若编号为8的结点存在右孩子，则右孩子的顺序编号为( )。 A.18 B.16 C.15 D.17

参考答案：17

9.设一棵哈夫曼树共有14个非叶结点，则该树总共有( )个结点。

A.29 C.30

参考答案：29

B.27 D.28

10.如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为( ).

A.abecdf B.acfebd C.aebcfd D.aedbfc

参考答案：aedbfc

二、填空题(每小题2分，共24分)

11.队列的特点之一是：元素进、出队的次序是：先进_________。

参考答案：先出

12. _________________结构中，数据元素间存在一对多的关系。

参考答案：树形

13.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的三项信息是______________。

参考答案：行下标、列下标、数组元素

14.在对11个记录的序列(12，35，9，7，2，11，56，95，37，58，60)进行直接插入排序时，当把第6个记录11插入到有序表时，为寻找插入位置，元素间需比较____________次。(由小到大排列)

参考答案：3

15.哈希函数是记录关键字的值与该记录____________之间所构造的对应关系。

参考答案：存储位置

16.20个元素进行冒泡法排序，通常需要进行19趟冒泡，其中第10趟冒泡共需要进行____________次元素间的比较。

参考答案：10

17.一棵有19个结点的二叉树，采用链式结构存储，该树结构中有__________个指针域为空。

参考答案：20

18.中序遍历一棵____________树可得到一个有序序列。

参考答案：二叉排序树

19.二叉排序树插人操作中，新插人的结点总是以树的____________结点被插人的。

参考答案：叶

20.广义表的(a，(d，a，b)，h，(e，((i，j)，k)))深度是____________。

参考答案：4

21.序列4，2，5，3，8，6，7，9，采用归并排序算法(升序)，经一趟归并后，序列的结果：___________。

参考答案：2，4，3，5，6，8，7，9

22.字符串al=“teijing”， a2=“tef”， a3=“teifang”， a4=“tefi”最小的是_______。

参考答案：a2

三、综合题(每小题中每问6分，共30分) 23.设查找表为

(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示)。 (2)说明成功查找到元素86需要经过多少次比较? (3)求在等概率条件下，成功查找的平均比较次数?

参考答案：

24.(1)一组记录的关键字序列为(26，59，36，18，20，25)，给出利用堆排序(堆顶元素是最小元素)的方法建立的初始堆(要求以完全二叉树描述)。

(2)对关键字序列(26，59，36，18，20，64)采用快速排序，给出以第一个关键字为分割元素，经过一次划分后的结果。

参考答案：

四、程序填空题(每空2分，共16分)

25.以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回一1，完成程序中的空格 typedef struct { int key；

…… } NODE；

int Binary_Search(NODE a[] ， int n， int k) {

}

参考答案： (1) low<=high (2) (low + high) / 2 (3) mid；

(4) a[mid] .key26.以下程序是前序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和right， 数据域data为字符型， BT指向根结点 ) 。

void Inorder(struct BTreeNode *BT) {

if(BT! =NULL) { (1)_________________; (2)__________________; In order(BT一一>right) ； }

利用上述程序对图2进行先序遍历，结果是(3)_______________________.

int low， mid， high； low=＝0； high=n一1；

while( (1)_____________) { mid=( (2)_______________ )

if(a[mid] .key==k)

return (3)___________________;

elseif( (4)____________________ ) low=mid+1；

else (5)_____________________; }

Return-1

参考答案：

(1) printf(“%c”， BT一>data) (2) Inorder(BT->left) (3) a b d f e c

国家开放大学(中央广播电视大学)2018年春季学期“开放本科”期末考试

数据结构(本)试题2018年7月

一、单项选择题(每小题3分，共30分)

1.数据的存储结构包括数据元素的表示和( )。 A.数据处理的方法 B.相关算法

C.数据元素的类型

D.数据元素间的关系的表示

参考答案：数据元素间的关系的表示

2.在一个头指针为head的单向链表中， p指向尾结点， 要使该链表成为单向循环链表可执行( )。 A.p=head->next； B.head->next=p；

C.head一>next=p->next； D.p一>next=head；

参考答案：p一>next=head；

3.元素111，113，115，117按顺序依次进栈，则该栈的不可能输出序列是( )(进栈出栈可以交替进行)。 A.117，115，113，111 B.111，113，115，117 C.117，115，111，113

D. 113，111，117，115

参考答案：117，115，111，113

4.以下说法正确的是( )。 A.栈的特点是先进后出 B.栈的特点是先进先出 C.队列的特点是先进后出 D.栈和队列的特点都是先进后出

参考答案：栈的特点是先进后出

5.设有一个20阶的对称矩阵A(第一个元素为a1.1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则矩阵中元素a6.2在一维数组B中的下标是( )。 A.24 B.17 C.16 D.23

参考答案：17

6.设一棵有2n+1个结点的二叉树，除叶结点外每个结点度数都为2，则该树共有( )个叶结点。 A.n B.n+1 C.n+2 D.n一1

参考答案：n+1

7.已知如图1所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为( )。

A.abecdf C.aebcfd

参考答案：aecbdf

B.aecbdf D.aedfcb

8.线性表以( )方式存储，能进行折半查找。 A.关键字有序的顺序 B.顺序 C.链接 D.二叉树

参考答案：关键字有序的顺序

9.一棵具有38个结点的完全二叉树，最后一层有( )个结点。 A.7 B.5 C.6 D.8

参考答案：7

10.对一个栈顶指针为top的链栈进行出栈操作， 用变量e保存栈顶元素的值， 则执行( )。

A.e=top一>next； top->data=e； B.top=top->next； e=top->data； C.e=top一>data； top=top一>next； D.top=top一>next； e=data；

参考答案：e=top一>data； top=top一>next；

二、填空题(每小题2分，共24分)

11.数组a经初始化char a[ ] =\"English”； a[7] 中存放的是_______。

参考答案：字符串结束符

12.设有串pl=”ABADF”， P2=”ABAFD”， P3=”ABADFA” P4=”ABAF”，四个串中最大的是______。

参考答案：P2

13.在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为______。

参考答案：2i+1

14.设有一个长度为20的顺序表，要插入一个元素，并作为第8个元素，需移动元素的个数为______。

参考答案：13

15.结构中的数据元素存在多对多的关系称为______结构。

参考答案：图状

16.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有______个结点。(根所在结点为第1层)

参考答案：12

17.一棵二叉树中有n个非叶结点，每一个非叶结点的度数都为2，则该树共有______个叶结点。

参考答案：n+1

18.在对一组记录(55，39，97，22，16，73，65，47，88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较______次。(由小到大排序)

参考答案：3

19.n个元素进行冒泡法排序，第j趟冒泡要进行______次元素间的比较。

参考答案：n-j

20.一棵有n个叶结点的哈夫曼树，则该树共有______个结点。

参考答案：2n-1

21.中序遍历______可得到一个有序序列。

参考答案：二叉排序树

22.广义表((a，b)，d，e，((i，j)，k))的长度是______。

参考答案：4

三、综合题(每小题中每问6分，共30分)

23.(1)设有数据集合{40，29，7，73，101，4，55，2，81，92，39}，依次取集合中各数据构造一棵二叉排序树。

(2)一组记录的关键字序列为(5，8，6，3，4，7)，利用堆排序(堆顶元素是最小元素)的方法建立初始堆。(要求用完全二叉树表示)

24.(1)以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树。 (2)给出上述哈夫曼树叶结点的哈夫曼编码。

(3)一组记录的关键字序列为(37，70，47，29，31，85)，利用快速排序，以第一个关键字为分割元素，给出经过一次划分后结果。(从小到大排序)

四、程序填空题(每空2分，共16分)

25.设线性表为(6，10，16，4)，以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。 #define NULL 0 void main()

{ NODE a， b， c， d， *head， *p；

a.data=6； b.data=10； c.data=16；

d.data=4； /*d是尾结点*/ head=(1)______________ a.next=&b；

b.next=&c； c.next=&d；

(2)______________；/*以上结束建表过程*/ p=head； /*p为工作指针， 准备输出链表*/ do

{ printf(“%d\\n”，(3)____________)；

(4)______________________;

} while( (5)_______________ )； }

参考答案： (1)&a

(2)d-> >next=NULL (3) p->data (4) p=p->next (5) p!=NULL

26.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和right， 数据域data为字符型， BT指向根结点) 。

void Inorder(struct BTreeNode*BT) { i

f(BT!=NULL) {

(1)_______________; (2)_______________; In order(BT->right) ； } }

利用上述程序对右图进行遍历，结果是(3)________________________

参考答案：

(1) Inorder(BT->left)

(2) printf(“%c”，BT一>data) (3) bedafc

国家开放大学(中央广播电视大学)2018年秋季学期“开放本科”期末考试

数据结构(本)试题2019年1月

一、单项选择题(每小题3分，共30分)

1.如下图所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为( )。

A.acebdf B.aecbfd C.aecbdf D.acefdb

参考答案：aecbdf

2.结构中的元素之间存在一对多的关系是( )。 A.集合 B.线性结构 C.树形结构 D.图状结构

参考答案：树形结构

3.设有一个长度为18的顺序表，要在第4个元素之前插入1个元素(也就是插入元素作为新表的第4个元素)，则移动元素个数为( )。 A.15 B.16 C.5 D.4

参考答案：15

4.一个不带头结点的单循环链表， 尾指针为rear，在链表中插人一个s所指向的新结点，并作为新的尾结点，可执行( )。

A.rear一>next=s； s一>next=rear一>next； rear=s； B.rear一>next=s一>next； rear=s；

C.s一>next=rear一>next； rear一>next=s一>next； rear=s； D.s一>next=rear一>next； rear一>next=s； rear=s；

参考答案：s一>next=rear一>next； rear一>next=s； rear=s；

5.元素a，b，c，d按顺序依次进栈，则该栈的不可能输出序列是( )(进栈出栈可以交替进行). A.c，b，a，d B.d，c，b，a C.a，c，b，d D.d，c，a，b

参考答案：d，c，a，b

6.在一个栈顶指针为top的链栈中进行出栈操作，用变量x保存栈顶元素的值， 则执行( )。

A.x=top->data； top=top->next； B.x=top->data； C.top=top一>next； x=top一>data； D.top=top->next； x=data；

参考答案：x=top->data； top=top->next；

7.设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则矩阵中a10.8元素对应于数组中第( )号元素。

(矩阵中的第1个元素是a1.1) A.51 B.53 C.52 D.54

参考答案：53

8.一棵采用链式存储的二叉树中，共有n个指针域被有效使用(即指针域为非空)。该二叉树有( )个指针域为空。 A.n+1 B.n C.n--1 D.n+2

参考答案：n+2

9.在一棵二叉树中，若编号为9的结点存在右孩子，则右孩子的顺序编号 为( )。 A.18 B.16 C.15 D.19

参考答案：19

10.设一棵哈夫曼树共有15个非叶结点，则该树总共有( )个结点。 A.29 B.27 C.31 D.28

参考答案：31

二、填空题(每小题2分，共24分)

11.在n个整数中求最大数的算法中，其基本操作是_____________.

参考答案：元素间的比较

12.设有一个长度为20的顺序表，要删除第5个元素，则最少要移动元素的个数为_____________.

参考答案：15

13.在双向链表中，要删除p所指的结点，其中所用的一条语句 (p->prior) ->next=p->next；的功能是：

使P所指结点的直接前驱的右指针指向_____________.

参考答案：P所指结点的直接后继

14.设有一个头指针为head的单向链表， p指向链表中的某结点， 若要使该链表成为单向循环链表， 可用语句while(p->next!=NULL) _____________. 和p一>next=head； 。

参考答案：p=p->next

15.在一个链队中， 设front和rear分别为队头和队尾指针， 则s所指结点(数据域已赋值) 的人队操作为 s一>next=NULL； _____________ rear=s； 。

参考答案：rear->next=s；

16.字符串al=“heijing”，a2=“hef”，a3=“heifang”，a4=“he fi”中最小的是_______.

参考答案：a2

17.栈的特点之一是：元素进、出栈的次序是：后进_____________.

参考答案：先出

18.在对10个记录的序列(14，30，10，7，22，13，66，85，47，58)进行直接插人排序时，当把第6个记录13插人到有序表时，为寻找插人位置，元素间需比较_____________次。(由小到大排列)

参考答案：4

19.18个元素进行冒泡法排序，通常需要进行17趟冒泡，其中第10趟冒泡共需要进行_____________次元素间的比较。

参考答案：8

20.一棵有15个结点的哈夫曼树，采用链式结构存储，该树结构中有____________个叶结点。

参考答案：8

21.广义表的(b，(a，b)，d，(c，((e，f)，j)))深度是_____________.

参考答案：4

22.序列4，2，7，9，5，3，8，6采用归并排序算法(升序)，经一趟归并后，序列的结果为_____________.

参考答案：2，4，7，9，3，5，6，8

三、综合题(每小题6分，共30分)

23.(1) 已知某二叉树的后序遍历序列是febch， 给出该二叉树的根结点?又该二叉树的中序遍历序列是fbehc， 分别给出该二叉树的左、右子树的结点?

(2)画出上述二叉树?若上述二叉树的各个结点的字符分别代表不同的整数(其中没有相等的)，并恰好使该树成为一棵二叉排序树，试给出h、b、c、f、e的大小关系。

24.设查找表为(1，2，3，4，5，6，7，8，9，10，11)

(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用数值表示)。 (2)说明成功查找到元素5，9各需要经过多少次元素间的比较? (3)说明查找不到元素4.2，5.5各需要经过多少次元素间的比较?

四、程序填空题(每空2分，共16分) 25.以下程序是折半插人排序的算法

设待排序的记录序列存放在a[1]，…a[n]中，以a[0]作为辅助工作单元，以下程序是要把a[i]插人到已经有序的序列a[1]，…a[i一1]中。 void bin sort(NODE a[] ， int n) { int x， i， j， s， k， m；

For (i=2；i<=(1)___________；i++) { a0]=a[i]；

x=a[i] .key； s=1； j=i-1； while(s<=j)

{ m=(2)_____________; if(xfor(k=i一1； k>=j+1； k--) (5)______________=a[k]； a[j+1]==a[0]；

} }

参考答案：

(1)n

(2)(s+j)/2； (3)j=m一1； (4)s=m+1； (5)a[k+1]

26.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中，左、右指针域分别为left和right， 数据域data为字符型， BT指向根结点) 。

void Inorder(struct BTreeNode*BT) { a

if(BT! =NULL) (1)_____________; (2)_____________;

Inorder(BT->right) ； } }

利用上述程序对右图进行遍历，结果是(3)_____________________;

参考答案：

(1) Inorder(BT一>left)

(2) printf(“%c”， BT->data) (3) bedfa

国家开放大学2019年春季学期期末统一考试

数据结构(本)试题2019年7月

一、单项选择题(每小题3分，共30分) 1.以下说法正确的是( )。

A.在顺序表中可以随机访问任一结点

B.一种逻辑结构在存储时只能采用一种存储结构 C.对链表进行插入、删除元素的操作一定要移动结点 D.在链表中可以随机访问任一结点

参考答案：在顺序表中可以随机访问任一结点

2.线性表在存储后，如果要求：仅通过已知的指向第i个结点的指针，进行相关操作，访问到该结点的前驱结点，则采用( )存储方式是不可行的。 A.单链表

B.双链表 C.单循环链表 D.顺序表

参考答案：单链表

3.栈和队列的共同特点是( )。 A.都是先进后出

B.元素都可以随机进出

C.只容许在端点处插人和删除元素 D.都是先进先出

参考答案：只容许在端点处插人和删除元素

4.元素4，6，8，10按顺序依次进栈，按该栈的可能输出序列依次人队列，该队列的可能输出序列是( )(进栈出栈可以交替进行)。 A.10，8，4，6 B.10，6，4，8 C.8，4，6，10 D.10，8，6，4

参考答案：10，8，6，4

5.在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，从该队列中进行出队操作，并把结点的值保存在变量x中的操作为( )。 A.x=r->data； r=r->next；

B.r一r一>next； x=r一>data； C.x=f~>data； f=f->next； D.f一f->next； x-f一>data；

参考答案：x=f~>data； f=f->next；

6.设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存到一维数组B中(数组下标从1开始)，则矩阵元素ag.2对应于数组B中第( )号元素。(矩阵中的第1个元素是a1.1) A.42 B.39 C.38 D.40

参考答案：38

7.一棵采用链式存储的二叉树中，共有n一1个指针域被有效使用(即指针域为非空)。该二叉树中有( )个指针域为空。 A.n+1 B.n C.n-1 D.n一2

参考答案：n+1

8.设一棵哈夫曼树共有n个非叶结点，则该树共有( )个结点。 A.2n B.2n+1 C.2n一1 D.2n+2

参考答案：2n+1

9.如图所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为( )。

A.ahbedfc B.ahcfebd C.ahebcdf D.ahebcfd

参考答案：ahebcdf

10.线性表以( )方式存储，能进行折半查找。 A.关键字有序的链接 B.顺序 C.关键字有序的顺序 D.数组

参考答案：关键字有序的顺序

二、填空题(每小题2分，共24分)

11.n个元素进行冒泡法排序，通常需要进行( n-1 )趟冒泡。

12.在对一组序列(35，19，77，2，6，53，55，27，26，98)进行直接插入排序时，当把第9个记录26插入到有序表时，为寻找插入位置需进行( 6 )次元素间的比较。

13.在C语言中，分别存储“S”和‘s’，各需要占用( 两个和1个 ) 字节。

14.数据的逻辑结构在计算机中的表示称为( 存储结构 )结构。

15.在一棵二叉树中，若编号为i的结点是其双亲结点的左孩子，则i结点的双亲结点的顺序编号为 ( i/2 ).

16.设有一个头指针为head的单向链表， p指向表中某一个结点， 且有 p一>next为NULL， 现要把该单向链表构造成单向循环链表， 可通过操作 ( p一>next=head； ).

17.从一个栈顶指针为top的链栈中删除一个结点时， 用d保存被删结点的值， 可执行d=top->data； 和( top=top->next； ). (结点的指针域为next， 数据域为data) 。

18.循环链队列中， 设front和rear分别为队头和队尾指针， (最多元素为MaxSize， 采用少用一个元素的模式)，判断循环链队列为满的条件为: ( front==(rear+1) %MaxSize ).

19.一棵有7个权重值构造的哈夫曼树，共有( 13 )个结点。

20.二叉树中有1个1度结点，8个2度结点，则该二叉树树共有( 18 ) 个结点。

21.如图所示的二叉树，其先序遍历序列为( 215934786 ).

22.在查找表中，通过记录的某关键字能唯一地确定一个记录，该关键字称为( 主关键字 ).

三、综合题(每小题6分共30分)

23.(1)对给定权值4，2，6，6，7，8，构造高度为4层的哈夫曼树。(设根为第1层)

提示：构造中当出现有两个以上值相等的可选结点时，可适当选择结点组合，以控制树的高度。

(2)求树的带权路径长度。

(2) WPL=(4+2+6+6) *3十(7+8) *2= 84

24.如下的一棵二叉树，

(1)请给出前序遍历序列?请给出中序遍历序列?

(2)把1，2，3，4，5，6，7，8，9填人，使它成为一棵二叉排序树。

提示：设图中的树是二叉排序树，则中序遍历序列是有序的，从而找出中序遍历序列与1，2，…9的对应关系。

(3)在图中给出在二叉排序树中插入结点2.5的结果。

四、程序填空题(每空2分，共16分)

25.以下函数为直接选择排序算法，对a[1]，a[2]，…a[n]中的记录进行直接选择排序，完

成程序中的空格 typedef struct {

int key； … } NODE；

void selsort(NODE a[] ，int n) {

Int i， j， k； NODE temp；

for(i=1； i<=(1)____________ ；i++) { k-i；

for(j=i十1； j<=(2)____________；j++)

if(a[j] .key{ temp=a i； (4)____________________ (5)_____________________ }

} }

参考答案： (1)n一1 (2)n (3)k=j

(4)a[i]=a[k] (5)a[k] =temp

26.设有一个头指针为head的不带头结点单向链表， 且p、q是指向链表中结点类型的指针变量，p指向链表中某结点a(设链表中没有结点的数据域与结点a的数据域相同)，在以下程序段中，写出相关语句 (1)使该单向链表成为单向循环链表 (2)删去a结点

q＝p； x=p一>data；

while(q一>next!=NULL) q=q一>next； (1)_____________________ q=p； p=->next； while(p->data !l=x) { q一p；

(2)______________________ }

(3)______________________________

参考答案：

(1) q->next=head； (2) p=p->next；

(3) q->next=p->next；

国家开放大学2019年秋季学期期末统一考试

数据结构(本)试题2020年1月

一、单项选择题(每小题3分，共30分) 1.以下说法不正确的是( )。

A.线性表的链式存储结构不必占用连续的存储空间 B.一种逻辑结构只能有唯一的存储结构 C.一种逻辑结构可以有不同的存储结构

D.线性表的顺序存储结构必须占用连续的存储空间

参考答案：一种逻辑结构只能有唯一的存储结构

2.单向链表所具备的特点之一是( )。 A.可以随机访问表中任一结点 B.需要占用连续的存储空间

C.插入元素和删除元素的操作不需要移动元素

D.可以通过指向某元素的指针操作，直接访问到该结点的直接前驱结点

参考答案：插入元素和删除元素的操作不需要移动元素

3.线性结构中数据元素的位置之间存在( )的关系。 A.多对多 B.一对多 C.一对一

D.每一个元素都有一个直接前驱和一个直接后继

参考答案：一对一

4.在一个单向链表中，p和q分别是指向结点类型的指针，要删除p所指结点的直接后继结点，可执行( )。 A.q=p->next； p->next=q->next B.q=p； p=q~>next

C.q=p->next； p->next=q D.q=p； p->next=q

参考答案：q=p->next； p->next=q->next

5.设有带头结点的且头指针为head的非空的单向链表， 指针p指向其尾结点， 要使该单向链表成为不带头结点的单向循环链表，则可利用下述语句：head=head->next； 和( )。 A.p=head B.p=NULL C.p->next=head D.head=p

参考答案：p->next=head

6.元素20，14，160，180按顺序依次进栈，则该栈的不可能输出序列是( )。(进栈出栈可以交替进行)。 A.180，160，14，20 B.20，14，160，180 C.180，160，20，14 D.14，20，180，160

参考答案：180，160，20，14

7.设有一个15阶的对称矩阵A(第一个元素为ai，i)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则矩阵中元素a5，3在一维数组B中的下标是( )。 A.11 B.13 C.14 D.12

参考答案：13

8.设一棵有n个叶结点的二叉树，度数为1的结点有4个，则该树共有( )个结点。 A.2n B.2n+3 C.2n+2 D.2n+4

参考答案：2n+3

9.设根结点所在层为第一层，一棵具有5层的完全二叉树，最后一层有6个结点，则该树总共有( )个结点。 A.22 B.20 C.21 D.19

参考答案：21

10.已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为( )。

A.abecdfg C.aebcfdg

参考答案：aedfcbg

二、填空题(每小题2分，共24分)

11.把数据存储到计算机中，并具体体现数据元素间的逻辑关系称为( 存储 )结构。

12.设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为( 14 )

13.在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为( 2i+1 )

14.设一棵哈夫曼树共有18个非叶结点，则该树总共有( 37 )。

15.栈元素的进、出栈次序是：后进( 先出 )个结点。

16.在对10个记录的序列(8，36，19，78，4，10，53，45，27，68)进行直接插人排序时，当把第6个记录10插入到有序表时，为寻找插人位置，元素间需比较( 4 )次。

17.n个元素进行冒泡法排序，通常需要进行n一1趟冒泡，其中第j趟冒泡共需要进行( n-j )次元素间的比较。

图1

B.acfebdg D.aedfcbg

18.序列7，1，4，2，5，3，8，6用归并法排序(升序)，经一次归并后的结果序列是( 1，7，2，4，3，5，6，8 )

19.中序遍历一棵( 二叉排序树 )树可得到一个有序序列。

20.广义表(h，(b，a)，f，e，((i，j)，k))的深度是( 3 )。

21. ( 树形 )结构中，数据元素间存在一对多的关系。

22.字符串al=“beijing”，a2=“bef”，a3=“beif ang”，a4=“befi”最小的是( a2 )。

三、综合题(每小题中每问6分，共30分) 23.设查找表为

(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示)。 (2)说明不成功查找元素45需要经过多少次比较? (3)求在等概率条件下，成功查找的平均比较次数?

24.

(1)一组记录的关键字序列为(37，67，43，25，27，32)，给出利用堆排序(堆顶元素是最小元素)的方法建立的初始堆(要求以完全二叉树描述)。

(2)对关键字序列(40，73，49，31，33，77)采用快速排序，给出以第一个关键字为分割元素，经过一次划分后的结果。

四、程序填空题(每空2分，共16分)

25.以下函数在a[0]到a[n一1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回一1，完成程序中的空格。 typedef struct { int key； … } NODE；

int Binary_Search( NODE a[ ] ，int n， int k) {

int low， mid， high； low=0；

(1) high =n-1

while(_low<=high) {

mid==(2) (low十high) / 2 if(a[mid] .key==k)

return(3) mid else if(a[mid] .keylow=mid+1;

else(4) high=mid一1

}

(5) return -1 }

26.以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点) 。 void Preorder(struct BTreeNode*BT) {

if(BT!=NULL) {

(1) printf(“%c”， BT->data) (2) Preorder(BT一>left) Preorder(BT->right) ； } }

利用上述程序对下图进行遍历，结果是(3) a b d f g e c

图2