发布时间 : 星期四 文章数据结构课程试卷A卷更新完毕开始阅读
《数据结构》课程试卷A卷
本试卷用于信息工程系信息类、网络工程专业07级本科学生
（时量：120分钟 总分：100分）
注意：1、答案必须填写在答题纸上，填写在试卷上的无效。
2、答案必须写明题目序号，并按题号顺序答题。 3、请保持行距，保持卷面整洁。
一、判断题（正确的画“√”，错误的画“×”。每题1分，共10分） 1、哈夫曼树一定是完全二叉树。
2、串的长度是指串中不同字符的个数。 3、向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。 4、线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻。
5、单链表从任何一个结点出发，都能访问到所有结点。 6、队列是操作受到限制的线性表。
7、已知一棵二叉树的先序序列和中序序列可以唯一地构造出该二叉树。 8、程序越短，程序运行的时间就越少。
9、连通网的最小生成树的权值之和一定小于它的其它生成树的权值之和。 10、对链表进行插入和删除操作时，不必移动结点。 二、选择题（每题2分，共40分） 1、 栈和队列的共同点是（ ）。
A、都是先进后出 B、都是先进先出 C、只能在端点处进行操作 D、各不相同 2、 有8个叶子的哈夫曼树共有（ ）个结点。
A、9 B、 7 C、 14 D、 15
3、 折半(二分)查找有序表(3,4,5,10,13,14,20,30),若查找元素30,则被比较的元素依次为（ ）。
A、 10,20,30 B、 10,14,30 C、 13,30 D、10,14,20,30 4、构造（Hash）函数的方法有（ ）
A、链地址法 B、线性探测法 C、 随机探测法 D、除留余数法 5、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q所指结点和p所指结点之间插入s所指结点，则执行（ ）
A、p->next=s；s->next=q； B、q->next=s；s->next=p；
C、p->next=s->next；s->next=p； D、s->next=p->next；p->next=s； 6、二维数组A[5][5]按行优先顺序存储，其中每个元素占2个存储单元。若A[0][0]的存储地址为400，则A[4][4]的存储地址为（ ）
A、450 B、448 C、446 D、444
7、一个栈的入栈序列为a，b，c，则出栈序列不可能的是（ ）
A、c,b,a B、b,a,c C、c,a,b D、a,c,b 8、循环队列是空队列的条件是（ ）
A、Q->rear==Q->front B、(Q->rear+1)%maxsize==Q->front C、Q->rear==0 D、Q->front==0
9、某二叉树的先序和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
A、高度等于其结点数 B、空或只有一个结点 C、任一结点无左孩子 D、任一结点无右孩子 10、具有n个顶点的有向图最多有（ ）条边。
A、n B、n(n-1) C、n(n+1) D、n2
11、正常情况下，删除非空的顺序栈的栈顶元素，栈顶指针TOP的变化是（ ）
A、TOP不变 B、TOP←0 C、TOP←TOP+1 D、TOP←TOP-1
12、若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（ ）
A、9 B、11 C、12 D、不确定
13、在长度为n的线性表中，在第i个元素之前插入一个新的元素x，需要移动（ ）个元素。
A、n B、n-i+1 C、n-i D、i+1 14、在双向链表中，一个结点包含（ ）个指针。
A、1 B、2 C、3 D、4
15、具有6个顶点的无向图至少有 ( )条边才能确保是一个连通图。
A、8 B、7 C、6 D、5
16、在树结构中，若结点A有三个兄弟，且B是A的双亲，则B的度是( )。
A、3 B、4 C、5 D、2 17、下列数据结构中，哪一个是非线性的。（ ）
A、二叉树 B、队列 C、字符串 D、栈
18、给定一个整数集合为{20,15,14,18,21,36,40,10}，一趟快速排序结束时，关键字的排列是( )。
A、10,15,14,18,20,36,40,21 B、10,15,14,18,20,40,36,21 C、10,15,14,20,18,40,36,21 D、15,10,14,18,20,36,40,21
19、设有一个栈的输入序列是1，2，3，… N，输出序列的第一个元素是N，则第I个输出元素是( )。
A、n-i B、n-i-1 C、n-i+1 D、n
20、设哈希表长M=14，哈希函数H（KEY）=KEY % 11，表中已有四个结点： addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7
其余地址为空，若用线性探测处理冲突，key=49 的结点地址是( )。 A、8 B、3 C、5 D、9
三、填空题（每空2分，共20分）
1、数据的逻辑结构可分为集合结构、 、________、________四类。 2、在双向链表中，若要求在p 指针所指的结点之前插入s指针所指的结点，则需执行下列语句：
S->next=p； s->prior= ________；p->prior=s；________=s；
3、在单链表中，指针p 所指结点为最后一个结点的条件是___________。 4、深度为k的完全二叉树至少有________个结点，至多有________个结点。 5、在无向图的邻接矩阵中，第i个顶点的度等于_________，图的边数等于________。
四、综合应用题（共30分）
1．某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.31，0.07，0.09，0.14，0.23，0.03，0.08。
（1）画出对应的Huffman树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求其带权路径长度WPL。（6分） （2）设计Huffman编码。（2分）
2．有向图如下图所示，写出以顶点1为出发点对图进行深度优先搜索所得的访问序列。（4分）
1 3 6 2 5 4 3．已知序列[10，18，4，3，6，12，1，9，15，8]，请给出采用简单选择排序对该序列做升序排列时的每一趟的结果（6分）。
4．已知一表为（8,9,3,7,12,5,4,2,10,1）,按表中顺序依次插入初始为空的二叉排序树，要求：
（1）画出建立的二叉排序树。（4分）
（2）求出在等概率情况下查找成功的平均查找长度。（2分） 5．写出下列这棵树的先序遍历、中序遍历和后序遍历的结果。（6分）
A B C D E F
《数据结构》课程试卷A卷评分标准
一、判断题（正确的画“√”，错误的画“×”。每题1分，共10分） 1-5 ××√√× 6-10 √√×√√ 二、选择题（每题2分，共40分）
1-5 CDDDB 6-10BCAAB 11-15DBBBD 16-20 BAACA 三、填空题（每空2分，共20分） 1、线性结构、树形结构、图形结构 2、p->prior、s->prior->next 3、p->next==NULL 4、2k-1,2k-1
5、第i行的和，所有元素的和的一半 四、综合应用题（共30分）
1、 （1）
1 0.4 0.17 0.080.09 0.23 0.6 0.29 0.14 0.07 0.03 0.15 0.08 0.05
0.31
哈夫曼树完全正确4分，基本正确酌情减分。
WPL=(0.23+0.31)*2+(0.08+0.09+0.14)*3+0.07*4+(0.03+0.05)*5 =0.4+0.28+0.93+1.08 =2.69 （2分）