试卷代号：1252 中央广播电视大学2012-2013学年度第二学期“开放本科”期末考试
数据结构【本】 试题
一、单项选择题（每小题2分，共30分）
1．在C语言中，顺序存储长度为3的字符串，需要占用( )个字节。 A．4 B．3 C．6 D．12 2。串函数StrCat(a，b)的功能是进行串( )。 A．比较 B．复制 C。赋值 D．连接
3．-棵有n个结点采用链式存储的二叉树中，共有( )个指针域为空。 A．n+l B．n C．n-l D．n-2 4．设一棵哈夫曼树共有n个非叶结点，则该树有( )个叶结点。 A．n B．n+l C．n-l D．2n 5．从一个栈顶指针为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 6．一棵完全二叉树共有5层，且第5层上有六个结点，该树共有( )个结点。 A．30 B．20 C．21 D．23 7．在一个无向图中，所有顶点的度数之和等于边数的( )倍。 A．O B．3 C．1.5 D．2 8．已知如图1所示的一个图，若从顶点V，出发，按深度优先搜索法进行遍历，则可能得 到的一种顶点序列为( )。
9．已知如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到 的一种顶点序列为( )。
A.abcedf B.abcefd C.aebcfd D.acfdeb
10.对二叉排序树进行( )遍历，可以使遍历所得到的序列是有序序列。 A．按层次 B．后序 C．中序 D．前序
11．在有序表(2，4，7，14，34，43，47，64，75，80，90，97，120)中，用折半查找法查找值80 时，经( )次比较后查找成功。 A．4 B．2 C．3 D．5 12．有一个长度为9的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为( )。
A．25/10 B．25/9 C．20/9 D．17/9 13.排序算法中，从未排序序列中依次取出元素与已排序序殂（初始为空）中的元素进行 比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是( )。 A．冒泡 B.直接插入 C．折半插入 D．选择排序
14．一组记录的关键字序列为(46，79，56，38，40，84)，利用快速排序，以第一个关键字为 分割元素，经过一次划分后结果为( )。 A．40,38946,79956,84 B．40,38946,56,79,84 C．40，38,46,84,56,79 D．38，40,46956,79,84 15.排序方法中，从尚未排序序列中挑选元素，并将其依次放人已排序序列（初始为空）的 一端的方法，称为( )排序。
A．归并 B．插入 C．快速 D．选择
二、填空题（每小题2分。共24分）
16.在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是_________、________、右指针。 17.-棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别为 .__.____.....____．
一、____......____..．一O 18.串的两种最基本的存储方式是_________和_________。 19.-棵有2n-l个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有_________个叶结点。 20.对于一棵具有n个结点的二叉树，其相应的链式存储结构中共有_________个指针域为空。
21．_________遍历二叉排序树可得到一个有序序列。 22．如图3所示的二叉树，其后序遍历序列为
≥ %
图3 23．如图4所示的二叉树，其先序遍历序列为妒
图4 24.图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是 一的。（回答正确或不正确） 25.二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其 右孩子的值。这种说法是 的。（回答正确或不正确）
26.对记录序列排序是指按记录的某个关键字排序，记录序列按____排序结果是唯一的。
27.按某关键字对记录序列排序，若 在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。
三、综合题（每小题10分。共30分）
28．设查找表为(16，15，20，53，64，7)，
(1)用冒泡法对该表进行排序（要求升序排列），写出每一趟的排序过程，通常对n个元素 进行冒泡排序要进行多少趟冒泡？第j趟要进行多少次元素间的比较？
(2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。（要求以数据 元素作为树结点）。
29．(1)设有查找表{5，14，2，6，18，7，4，16，3），依次取表中数据，构造一棵二叉排序树。 (2)说明如何由序列的二叉排序树得到相应序列的排序结果。
30．(1)对给定权值2，1，3，3，4，5，构造哈夫曼树（要求每个结点的左子树根结点的权小于 等于右子树根结点的权）。 (2)给出各权值的哈夫曼编码。
四、程序填空题【每空2分。共16分）
32.以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中，左、右指针域分别为1eft和right，数据域data为字符型，BT指向根结点）。 voidPostorder( structBTreeNode* BT) {if(BT! =NULL){ (1) ． (2) ． (3) ) ) 中央广播电视大学2012-2013学年度第二学期期末考试数据结构（本）试题答案及评分标准
2013年7月
一、单项选择题（每小题2分，共30分）
1．A 2．D 3．A 4．B 5.A 6．C 7．D 8．A 9．B 10.C 11．B 12．B 13．C 14．B 15.D
二、填空题（每题2分，共24分） 16.值域 左指针 右指针 17.2i 2i+l 18.顺序存储 链式存储
19 ∥，一。 19．n ．~‘r
磷．
20．n+1 -’ 21．中序 22．gdbeihfca 23．abdefcg 24．正确 25．不正确 26．主关键字
27．关键字相等的记录
