数据结构学位考试试卷A.doc
《数据结构学位考试试卷A.doc》由会员分享，可在线阅读，更多相关《数据结构学位考试试卷A.doc（6页珍藏版）》请在冰点文库上搜索。
Ｏ八-Ｏ九学年第一学期
申请广州大学学士学位抽考课程试卷（A）
课程名称数据结构考试形式（开/闭卷）
系别专业班级学号姓名
试题
一
二
三
四
五
六
总分
评卷人
分值
20
10
18
32
20
100
得分
考试时间：
2009年1月日
答题时间：
120分钟
考试地点：
考试形式：
闭卷
一、单项选择题（每题1分,只有一个正确答案）
分值
20
得分
1.线性表的链式存储比顺序存储最有利于进行（）。
A.查找 B.表尾插入或删除 C.按值插入或删除 D.表头插入或删除
2.在一个无向图中,所有顶点的度数之和等于所有边数的（）倍。
A．3 B.2 C.1 D.1/2
3.利用n个值作为叶子节点的权生成的哈夫曼树中共包含有（）个节点。
A．n B.n+1 C.2×n D.2×n-1
4.为了实现树的层次遍历算法,使用的一个辅助数据结构为（）。
A．队列 B.栈 C.二叉树 D.树
5.一个栈的输入序列是SWXYZ，则栈的不可能的输出序列是（）。
A.ZYXWSB.YZXWSC.YXZSWD.SWXYZ
6.假定一个带头节点的循环链队的队首和队尾指针分别用front和rear表示，则判断队空的条件为（）。
A．front!
=rearB.rear！
=NULLC.front==NULLD.front==rear
7.在一个长度为N的数组空间中，顺序存储着一个队列，该队列的队首和队尾指针分别用front和rear表示，则该队列中的元素个数为（）。
A．（rear-front）%NB.（rear-front+N）%N
C．（rear+N）%ND.（front+N）%N
8.在一棵具有n个节点的二叉树的第i层上（根节点为第1层），最多具有（）个节点。
A．2i B.2i+1 C.2i-1 D.2n
9.根据n个元素建立一棵二叉搜索树时，其时间复杂度为（）。
A．O（n） B.O（log2n） C.O（n2） D.O（nlog2n）
10.n（n>1）个顶点的强连通图中至少含有（）条有向边。
A．n-1 B.n C.n（n-1）/2 D.n（n-1）
11.输入序列为ABC，若变为CBA时，经过的栈操作为（）
A.push,push,push,pop,pop,popB.push,pop,push,pop,push,pop
C.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop
12.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）
A．9B．11C．15D．不确定
13.在一个表头指针为ph的单链表中，若要在指针q所指节点的后面插入一个由指针p所指向的节点，则执行（）操作。
A．q->next=p->next;p->next=q;B.p->next=q->next;q=p;
C．q->next=p->next;p->next=q;D.p->next=q->next;q->next=p;
14.在一个带头节点的循环双向链表中，若要在指针p所指向的节点之后插入一个q指针所指向的节点，则需要对q->right赋值为（）。
A．p->left B.p->right C.p->right->rightD.p->left->left
15.假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，top=-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（）。
A．a[--top]=x;B.a[top--]=x;C.a[++top]=x;D.a{top++}=x;
16.如果一个元素序列基本有序时，则选用（）方法较快。
A．直接插入排序B.直接选择排序C.堆排序D.快速排序
17.假如一棵二叉树有3个结点,其有多少种不同的形态（）：
A.4种 B.5种 C.6种 D.7种
18.对于具有e条边的无向图，它的邻接表中有（）个边节点。
A．e-1 B.e C.2（e-1） D.2e
19.下述二叉树中,哪一种满足性质:
从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。
A．二叉排序树B．哈夫曼树 C．AVL树 D．堆
20.排序二叉树的_______遍历的序列是一个关键字的递增的有序序列
A.先根遍历 B.中根遍历 C.后根遍历 D.层次遍历
二．判断题（正确打“√”,错误打“×”）
分值
10
得分
1.线性表的特点是每个元素都有一个前驱和一个后继。
（）
2.取线性表的第i个元素的时间与i的大小有关.（）
3．完全二叉树中，若一个结点没有左孩子，则它必是树叶。
（）
4．完全二叉树的存储结构通常采用顺序存储结构。
（）
5．将一棵树通过孩子兄弟链表转成二叉树，根结点没有左子树；（）
6．任何无向图都存在生成树。
（）
7.关键路径是AOE网中从源点到终点的最长路径。
（）
8.循环队列也存在空间溢出问题。
（）
9．在待排序数据基本有序的情况下，快速排序效果最好。
（）
10．（101，88，46，70，34，39，45，58，66，10）是堆。
（）
三．算法填空（每空2分,共18分）
分值
18
得分
1、采用快速排序算法对在A[s]~A[t]区间的关键字进行排序。
voidQuickSort（intA[],ints,intt）
{ inti=s,j=t+1;
intx=A[s];
do{
do_________;while（A[i] do__________;while（A[j]>x）;
if（_____________）
{ inttemp=A[i];
A[i]=A[j];A[j]=temp;
}
}while（________）;
A[s]=A[j];A[j]=x;
if（____________）QuickSort（A,s,j-1）;
if（____________）QuickSort（A,j+1,t）;
}
2、统计二叉树叶子节点数
intBTreeleafCount（BinTreeNode*BT）
{
if（BT==NULL）return_______;
if（BT->left==NULLandBT->right==NULL）
return________;
else
return____________________________________________________;
}
四．应用题（每题8分共32分）
分值
32
得分
1．下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，并画出可能的选择。
（8分）
2.假设一个二叉树的两种遍历如下：
前序：
ABFGCHDEIJLK中序：
FGBHCDILJKEA
画出这棵二叉树,并求其后序遍历。
（8分）
3．用给出的一组权值{7，19，2，6，32，3，21，10}，构造一棵哈夫曼树，并计算其带权路径长度WPL。
（要求写出哈夫曼树构造过程及WPL的计算过程）（8分）
4、己知一组关键字为（32，75，29，63，48，94，25，46，18，70，19），按哈希函数H（key）=key%13和链接法处理冲突构造哈希表，并计算其平均查找长度。
（8分）
五．编写算法（每小题10分,共20分）
分值
20
得分
1．根据函数声明voidOrderInsertList（sNode*head,intx）,向带附加表头节点head的循环递增的有序单链表中插入一个元素,使得插入后仍然有序。
（10分）
2.已知二叉树中的节点类型BinTreeNode定义为：
StructBinTreeNode{
intdata;
BinTreeNode*left,*right;};
根据intBTreeCount（BinTreeNode*BT,intx）函数声明写出求二叉树中值大于x的节点个数的算法,假定BT为根节点。
（10分）
6
升级会员 