云南师范大学 2009 ── 2010学年 上学期统一考试
数据结构试卷
学院 计信学院 专业 班级 学号 姓名
考试方式：闭卷 考试时量：120分钟 试卷编号：A 卷
题号 得分 一 二 三 四 五 总分 评卷人 说明：下面是本试卷中可能用到的结构:
typedef struct node/链表结点结构*/ {
elemtype Data;
struct node *next;
}Node，*LinkList；
typedef struct node/*二叉链表结构*/ {
elemtype Data;
struct node *LChild,*RChild; }BNode，*BTree；
请将答案写在答题纸上。 得分 评卷人 一、填空题（每题2分，共20分）
1. 数据结构是相互之间存在一种或多种特定的关系的数据元素的集合，它包括3个方面的内容，分别是数据的逻辑结构，数据的存储结构和____数据的运算集合__。 2.有程序段：for (i=1 ; i<=100 ; i++) for (j=1 ; j<=n ; j++) x+=10;
则该程序段中语句x+=10的执行次数为____100n________。 3.
带头结点的单链表
L
中只有一个元素结点的条件
是 ___L->next->next==NULL_______。
4.若栈S的初始状态S->top=0，则执行m次入栈操作后，S->top的值为____m+1____。 5.已知二维数组a[-1…3][4…6]按行序为主序存储，每个元素占4个字节空间，若数组的首元的地址为2000，则元素a[1][5]的内存地址为___2028_______。 6.一棵深度为h的二叉树至少有_________h个___结点。
7.一棵由m个叶子结点构造的哈夫曼树有____2m-1个___个结点。
8.有n个顶点的无向连通图至少有____n-1________条边。
9.查找表L有50条记录，若采用顺序查找，则平均查找长度为______25.5__。
10.对待排序列（34，51，28，17，61，43）执行一趟归并排序后该序列变为_34，51，17，28，43，61___。 得分 评卷人 二、单项选择题（每题2分，共20分）
1. 以下数据结构中，（ A ）个是非线性数据结构。
A．树 B．字符串 C．队 D．栈
2.算法具有五大特征，分别是输入、确定性、可行性以及（ D ） A．高效性和可读性 B．可读性和高效性 C．输出和可读性 D．输出和有限性
3. 对于顺序存储的线性表，访问元素和插入元素的时间复杂度分别为：（ C ）。 A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1)
4.若进队列的序列为123456，则可以得到的出队序列为（ A ）
A．123456 B．435621 C．126345 D．541236
5. 有关二叉树的下列说法正确的是（ B ）
A．二叉树的度为2 B．一棵二叉树的度可以小于2
C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2
6. 具有10个叶子结点的二叉树中有（ B ）个度为2的结点。
A．8 B．9 C．10 D．ll
7.在一棵中序线索二叉树中，p指向某结点，当p?Ltag= =1时，p?LChild指向( C ) A．p的左孩子 B．NULL C．p的前驱 D．p的后继
8.图G是一个有n个顶点的有向图，则图中最多含有( D )条有向边。 A．n B．n-1 C．n(n-1)/2 D．n(n-1)
9.有一个长度为12的有序表，若使用折半查找方法，在等概率的情况下，查找成功所需要的平均比较次数是( B )
A．35/12 B．37/12 C．39/12 D．43/12
10. 一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ A ）。
A．(40,38,46,56,79,84) B. (40,38,46,79,56,84) C．(38,40,46,56,79,84) D. (40,38,46,84,56,79)
得分 评卷人 三、简答题（共37分）
1.设head为一个有头结点的单链表，表长为m，L为另一个带有头结点的单链表，表长为n。请描述出将单链表L中的结点链接在单链表head后的操作，所需变量自己定义。（6分）
Node *q=head;
while(q->next!=NULL)q=q->next; q->=L->next;
2. 画出中序遍历次序为xyz的所有二叉树的形态，并分别写出它们的前序遍历和后序遍历（6分）
3.设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数H(key)=key和开放地址法的线性探测再散列方法解决冲突，试在0~18的散列地址空间中对该关键字序列构造哈希表（线性探测在散列的下一地址计算公式为d1=H(key),dj+1=(dj+1)%m，j=1,2,…）。（8分）
4.给定权值如下：10，20，5，15，8，2，3，7，30。①根据这组权值，设计一棵哈夫曼树；②计算该哈夫曼树的带权路径长度WPL。（7分）
5.图1是有7个顶点的加权无向图。（10分） ①写出该图的邻接矩阵；
②写出从顶点B开始的深度优先 搜索遍历序列；
③采用prim算法，构造该图的一 棵最小生成树（要求描述过程）。
20 10 5 2 3 15 7 8 30 Y X Z X Y Z X Y Z Y X Z Y Z X
?0?13??0??11?12??0?0?130120000012090081109010061200100110000011080??0?8??6?0??8?0??
②从顶点B开始的深度优先搜索遍历序列为：BCGFEDA ③最小生成树为图3：
A E 11 10 D B 12 6 8 C G 8 图3
F 四、算法阅读（15分）
1.假设A是一个带有头结点的单链表。阅读下列算法，并说明算法的功能（7分）。 void sp（LinkList A， LinkList *B） { Node *p,*ra,*rb; ra=A; p=ra->next;
B=(Node*)malloc(sizeof(node)); B->next=NULL; rb=B; while(p!=NULL) { if(p->data%2==1)
{ ra->next=p;
ra=p; }//if
else
{ rb->next=p;
rb=p; }//else
p=p->next; }//while
ra->next=rb->next=NULL;
相关推荐：
loading