2．在二维数组中，每个数组元素同时处于( C )个向量中。A．0 B．1 C．2 D．n3．设有两个串t和P，求P在t中首次出现的位置的运算叫做(B )。A．求子串 B．模式匹配 C．串替换 D．串 4．利用双向链表作线性表的存储结构的优点是( B )。
A．便于单向进行插入和删除的操作 B．便于双向进行插入和删除的操作C．节省空间 D．便于销毁 5．设链式栈中结点的结构为(data，link)，且top是指向栈顶的指针。所指的结点，则应执行( C )操作。 A．top一>link=S；B．s一>link=top一>link；top一>link=S；C．S-->link=top；top—S；
6．一棵具有35个结点的完全二叉树的高度为( A )。假定空树的高度为一l。A．5 B．6 C．7 D．8 7．向具有n个结点的堆中插入一个新元素的时间复杂度为( C )。A．O(1) B．0(n) C．O(log2n)D．O(nlog2n) 8．在一棵AVL树中，每个结点的平衡因子的取值范围是( A )。A．一l～1 B．一2～2 C．1～2 D．O～1 9．一个有n个顶点和n条边的无向图一定是( B )的。A．连通 B．不连通 C．无回路 D．有回路 二、填空题，在横线处填写合适的内容(每小题2分，共l4分) 1．数据结构包括(逻辑结构 )、存储结构和对数据的运算这三个方面。
2．一维数组所占用的空间是连续的。通常是按元素的(下标(或顺序号))存取的。
3．将一个n阶对称矩阵的上三角部分或下三角，则该一维数组需要至少具有(n(n+1)／2)个元素。 4．对于一棵具有n个结点的树，该树中所有结点的度数之和为(n一1)。
5．在一棵高度为3的理想平衡二叉树中，最少含有(8)个结点，假定树根结点的高度为0。 6．假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底层的结点数为(19)个。 7．用邻接矩阵存储图，占用的存储空间与图中的(顶点) 数有关。
三、判断题。在每小题前面打对号表示正确或打叉号表示错误(每小题2分。共14分)
( 错 )1．算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。 ( 对 )2．用字符数组存储长度为n的字符串，数组长度至少为n+1。
( 对 )3．在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 ( 错 )4．邻接矩阵适用于稀疏图的表示，邻接表适用于稠密图的表示。
( 对 )5．对一个无向连通图进行一次深度优先搜索遍历时可以访问到图中的所有顶点。 ( 错 )6．在索引顺序结构的搜索中，对索引表只可以采取顺序搜索，不可以采用折半搜索。 ( 对 )7．图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。 四、运算题(每小题6分，共30分)
1．假定一棵二叉树广义表表示为a(b(c)，d(e，f))，分别写出对它进行中序、后序、按层遍历的结 2．一个一维数组all2]中存储着有序表(15，26，34，39，45，56，58，63，74，76，80，86)， 3．假定一个线性序列为(38，42，55，15，23，44，30，74，48，26)，根据此线性序列中元素 4．已知一个图的顶点集V和边集G分别为：V={1，2，3，4，5，6}；
1．中序：C，b，a，e，d，f 后序：C，b，e，f，d，a 按层：a，b，d，C，e，f 2．度为1的结点个数：5 平均搜索长度：37/12
3．左子树为空的所有单支结点：l5，23，42，44右子树为空的所有单支结点：30所有叶子结点：26，48，74
2
2
4．(I)1，2，4，5，3，6 (2)1，2，3，4，5，6 五、算法分析题(每小题6分。共12分)
1·下面算法的功能为：将两个有序单链表合并成一个有序单链表并返回其表头指针。阅 读算法，在划有横线的上面填写合适的内容。
ListNode*Mergel(ListNode*．& pl，ListNode*&p2) if(pl-->data<=p2-->data){ p-->link=pl； ; 1．pl2p1一>link、p=p一>link
2．已知二叉树中的结点类型BinTreeNode定义为：
struct BinTreeNode{ElemType data；BinTreeNode*left， *right；}；
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面算法的定义指出其 2．生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树BT中所有结点的左、右 子树(或左、右孩子的值)交换的结果。 算法功能：
六、算法设计题(每小题6分，共12分)
1．已知f为单链表的表头指针，单链表中的结点结构为(data，link)，并假定每个结点的值均为大于0的整数。根据下面函数声明写出递归算法，返回单链表中所有结点的最大值，若单链表为空则返回数值0。 int Max(LinkNode*f)；
2．设Q是一个由其队尾指针和队列长度标识的循环队列，按照下面队列定义和函数声明 写出从此队列中删除一个元素的算法。 1.
int Max(LinkNode*f) {
if(f= =NULL)return 0：
if(f一>link= =NULL)return f一>data； int temp=Max(f-->link)；
if(f一>data>temp)return f一>data； else return temp； } 2．
bool DelCQueue(CyelieQueue Q，ElemType&x) {
if(Q．1ength= =O)return false；
x—Q．elem[(Q．rear—Q．1ength-t-M)％M]； Q．1ength一 一； return true； }
2006--2007学年度第二学期“开放本科\"期末考试
一、单项选择题。在括号内填写所选择的标号(每小题2分。共18分) 1．若需要利用形参直接访问实参，则应把形参变量说明为( B )参数。
A．指针 B．引用 C．传值 D．常值
2．在二维数组中，每个数组元素同时处于( C )个向量中。
A．O B．1 C．2
D．n
3．已知单链表A长度为m，单链表8长度为n，它们分别由表头指针所指向，其时间复杂度应为( A．O(1) B．O(m) C．O(n) D．O(m十n)
4．假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( D )
A．iront= =rear B．front!=NULLC．rear! = NULL D．front= =NULL
5．若让元素l，2，3依次进栈，则出栈次序不可能出现( C )种情况。
A．3，2，1 B．2，1，3C．3，1，2 D．1，3，2
6．在一棵高度为5(假定树根结点的高度为0)的完全二叉树中，所含结点个数至少等于( D )
A．16
B． C．31
D．32
7．向具有n个结点的二叉搜索树中插入一个结点的时间复杂度大致为( B )。
A．O(1) B．O(1og2n) C．O(n)
D．O(nlog2n)
8．具有n个顶点的有向图最多可包含有( D )条有向边。
B )。 A．n—1 B．n C．n(n一1)／2 D．n(n一1)
A．先根 B．中根C．后根 ．层次
9．图的广度优先搜索类似于树的( D )遍历 1．链表只适用于( 顺序 )查找。
二、填空题。在横线处填写合适的内容(每小题2分，共14分)
2．设双向循环链表中每个结点的结构为(data，llink，rlink)，则结地址为( p-->llink )。 3．在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有( 1 )个结点。 4．假定一棵树的广义表表示为a(b，c，d(e，f)，g(h))，则结点f的层数为( 2 )。 5．从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向根的( 右子树 ) 6．每次从第i至第n个元素中顺序挑选出一个最小元素，，此种排序方法叫做(直接选择)排序。 7．快速排序在最坏情况下的时间复杂度为( 0(n) )。
三、判断题，在每小题前面打对号表示正确或打叉号表示错误(每小题2分。共14分) ( 对 )1．数据的逻辑结构与数据元素本身的内容和形式无关。 ( 对 )2．使用三元组表示稀疏矩阵中的非零元素能节省存储空间。
( 错 )4．能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上 ( 错 )5．邻接表表示只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。
( 对 )6．在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个数有关， ( 错 )7．向一棵8树插入关键码的过程中，若最终引起树根结点的，则新树比原树的高 四、运算题(每小题6分。共30分)
1．假定一棵二叉树广义表表示为a(b(c(，g))，d(e，f))，分别写出对它进行先序、中序和后序遍历 1．先序：a，b，c，g，d，e，f 中序：c，g，b，a，e，d，f 后序：g，c，b，e，f，d，a
2．有7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点生成一棵霍夫曼树，求出该树的带权路径长度。 带权路径长度：l31 3．已知图G=(V，E)，其中
V={a，b，c，d，e}，
E={，，，，，，} 在该图的邻接表表示中，每个顶点单链表各有多少个边结点。 顶点： a b c d e 边结点数：1 1 2 1 2 4．已知一个AOV网的顶点集V和边集G分别为：V={0，1，2，3，4，5，6，7}；
E={<0，2>，<1，3>，<1，4>，<2，4>，<2，5>，<3，6>，<3，7>，<4，7>， <5，7>，<6，7>}；
拓扑序列：1，3，6，0，2，5，4，7
5．已知有一个数据表为{30，16，20，15，38，12，44，53，46，18，26，86}，给出进行归并排序的过程中每一趟排序后的数据表变化。
(o)[30 16 20 15 38 12 44 53 46 18 26 86] (1)[16 30][15 20][12 38][44 53][18 46][26 86] (2)[15 16 20 30][12 38 44 53][18 26 46 86 ] (3)[1215162030384453-]r-182686-111 (4)[12 15 16 18 20 26 30 38 44 46 53 86] 五、算法分析题(每小题6分。共12分)
1．该算法功能为：从表头指针为la的、按值从小到大排列的有序链表中删除所有值相同的多余元素，并释放被删结点的动态存储空间。‘阅读算法，在划有横线的上面填写合适的内容。 void purge_linkst(ListNode * &la) ListNode * P，*q；
if(1a= =NULL)return；
2
q=1a；p=la ->link；
if(p ->data>q ->data){q=p；p=p ->link；}else{
q ->link p ->link ；delete(p)； p= q ->link ； 2．已知二叉树中的结点类型BinTreeNode定义为：
struct BinTreeNode{ElemType data；BinTreeNode*left，*right；}；
其中data为结点值域，left和right分别为指向左、布子女结点的指针域。下面函数的功能是从二叉树BT中查找值为X的结点，若查找成功则返回结点地址，否则返回空。阅读算法，在划有横线的上面填写合适的 BinTreeNode*BTF(BinTreeNode*BT，ElemType x) {
if(BT==NULL)NULL； else{
if(BT一>data= =x) return BT、 ；
else{
if(t—BTF(BT一>left，x))return t：
if(t= BTF(BT一>right，x) )return t； 六、算法设计题(每小题6分，共12分)
1．Q是一个由其队尾指针和队列长度标识的循环队列，请写出插入一个元素的算法。 struct CyelieQueue ／／循环队列定义 {
ElemType elem[M]；／／M为已定义过的整型常量 2．已知二叉搜索树中的结点类型BinTreeNode定义为：
struct BinTreeNode{ElemType data; BinTreeNode*left， *right;)
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数BST指向一棵二叉搜索 1．bool EnCQueue(CyclicQueue&Q，ElemType x)； {
if(Q.1ength= =M)return false；
Q．elem[Q．rear]=x； Q．rear=(Q．rear+1)%M； Q．1ength++； return true；
}
2．int Insert(BinTreeNode*&BST，const ElemType&item)
{
if(BST= =NULL){
BinTreeNode*p=new BinTreeNode；
p一>data=item；
p一>left=p一>right=NULL；
BST=P：
return l； }
else if(item= =BST一>data)return 0； else if(itemdata)return Insert(BST一>left，itern)；
else
return Insert(BST-->right，item)； }
