《数据结构》期末考A、B卷(本科)范文.doc

数据结构期末复习 10计科2 16号 朱志彬

系别 专业（班级） 姓名 学号

………………………密……………………封…………………………装…………………订………………………线………………………
武夷学院期末考试试卷
（ 09级计算机科学与技术专业2010 ～2011 学年度第 1 学期）
课程名称 数据结构 A 卷
考试形式 闭卷 考核类型 考试
本试卷共 五 大题，卷面满分100分，答题时间120分钟。
题号
一
二
三
四
五
六
七
八
总分
复核人
得分

得分
评卷人

一、选择题：（本大题共10小题，每小题2分，共20分）

1． 　某内排序方法的稳定性是指(　　)。
   A．该排序算法不允许有相同的关键字记录
   B．该排序算法允许有相同的关键字记录
   C．平均时间为0（n log n）的排序方法
   D．以上都不对
　2．下面程序段的时间复杂度为(　　)。
for(i=2;i<=n;++I)
for(j=2;j<=i-1;++j)
{++x;a[i，j]=x;}
　　A.O(1)　　　　　 B.O(log2n)　　　　　 C.O(n)　　　　　 D.O(n2)
　3．非空的循环单链表head的尾结点p满足(　　)。
A.p->next=head；　　　　　　 B. p->next=NULL；
　 C.p =NULL；　　　　　 D. p->next->next =head；
4．设栈s和队列Q的初始状态为空， 元素b 1  ，b 2，  ，b 3 ， b 4 ， b 5 和b 6  依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是b 2   ，b 4  ，b 3   ，b 6  ，b 5  ，b 1 ， ，则栈S的容量至少应该是(　　)。
A. 3       B. 4       C. 5        D.其它   
5．表头和表尾均为空表的广义表是(　　)。
A.()　　　　　　　 B.(()) C.((()))　　　　　　　　 D.(()，())
6.下列二叉排序树中，满足平衡二叉树定义的是(　　)。
A． B. C. D.
7．二维数组A的成员是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从1到8，列下标j的范围从1到10，若A按行优先方式存储，起始地址为SA，那么元素A[8][5]的起始地址为 (　　)。
  A．SA+292 B．SA+296 C．SA+300 D．SA+304
8．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度(　　)。
   A． 必定快   B．不一定 
C． 在大部分情况下要快   D． 取决于表递增还是递减
9．下列关键字序列中，构成小根堆的是(　　)。
A．{84，46，62，41，28，58，15，37}　　 B．{84，62，58，46，41，37，28，15}
C．{15，28，46，37，84，41，58，62}　　　D．{15，28，46，37，84，58，62，41}
10．对一组数据（46,79,56,38,40,84）排序，则采用快速排序的方法，以第一个记录为基准得到的一次划分结果为(　　)。
A．38,40,46,56,79,84   B．40,38,46,79,56,84  
C．40,38,46,56,79,84   D．40,38,46,84,56,79
得分
评卷人

二、填空题：（本大题共10小题，每小题2分，共20分）0

1．树的先根遍历序列与其对应二叉树的________先根________遍历序列相同。
2．在折半查找中，要求被查找的元素必须采用______有序的顺序__________存储结构。
3．若某二叉树有20个叶子节点，有30个节点仅有一个孩子，则该二叉树的总的节点数是______________。
4．(a+b)*c+e*f的后缀表达式为__ab+c*ef*+___。
5．线性表L=（a1,a2,…,an）含有n个元素，用数组表示，假定在表中任何位置上插入元素的概率相同，则在表中插入一个元素平均需要移动元素的个数是____n/2_________。
6．一个连通图的生成树是它的一个___极小连通______子图。
7．冒泡排序在最坏的情况下需要进行元素的比较次数是__n(n-1)/2___________。
8．高度为8的完全二叉树至少有_64_____个叶子结点。
9．n个顶点的有向完全图，有___n(n-1)___条弧。
10．已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最少是____39_________。
得分
评卷人

三、判断题：（本大题共10小题，每小题1分，共10分）

1．可以随机访问任一元素是链表(顺序表)不具有的特点。（˅）
2．如果二叉树用二叉链表表示，则判断某个结点是不是树叶的条件是该结点左、右两个指针域的值都为空。（ ×    ）
3．结点的平衡因子是指该结点的右子树高度减去该结点的左子树高树。（   × ）
4．快速排序是一种稳定的排序方法。 （  ×  ）
5．完全二叉树的某结点若无右孩子，则它必是叶结点。（ ×   ）
6．图的深度优先搜索序列是唯一的。（  ˅   ）
7．无向图的邻接矩阵是对称的，有向图的邻接矩阵也可能是对称的。（  ˅  ）
8．直接插入排序的关键码比较次数与初始排列无关。（ ×    ）
9． 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ ×   ）
10． 若一个广义表的表头为空表，则此广义表亦为空表。（   × ）
得分
评卷人

四、应用题：（本大题共5小题，每小题6分，共30分）

1．某二叉树的中序遍历序列为ADEBCGFHIJ，后序遍历序列为ADCBGEIHJF； 　
F
(1)还原该二叉树；
E
J
解：

H
D
G

I

A
C
B

 (2)写出该二叉树的前序遍历序列。FEDAGBCJHI
2．已知带权图的邻接表如下所示，其中边表结点的结构为：

依此邻接表从顶点C出发进行遍历。
（1）写出依次从顶点C出发进行的深度优先遍历序列。CDBAFE
（2）写出依次从顶点C出发进行的广度优先遍历序列。CDABFE
3．已知一组元素的排序码为( 46, 74, 16, 53, 14, 26, 40, 38, 86, 65, 27, 34 )，使之按关键字递增次序排序时，写出按最左元素作为划分基准的快速排序，第一趟排序后的结果。
(34 ,27 ,16 ,38 ,14 ,26 ,40 )46 (86 ,65 ,53 ,74)
4． 求广义表L = ( ( a, ( b , ( ), ( c ) ), ( d, ( e ) ) ), ( f, g , ( h ) ) )的长度(2)和深度(3)，并利用广义表的求表头操作和求表尾操作，将原子d分离出来。
GetHead(L)=(a,(b,(),(c)),(d,(e)))=D
GetTail(D)=((b,(),(c)),(d,(e)))=E
GetTail(E)=((d,(e)))=F
GetHead(F)=(d,(e))=G
GetHead(G)=(d)
综上得：GetHead(GetHead(GetTail(GetTail(GetHead(L)))))
5．设某带权无向图如图，画出用Kruskal算法生成最小生成树每一步的结果。
2

6． 依次输入序列（62，68，30，61，25，14，53，47，90，84）中元素，生成一棵二叉排序树　
　（1）画出生成后的二叉排序树
90
25
68
30
62

61

14

53
84

47

84
90
47
53
61
14
68
25
62
（2）画出删除结点30后的二叉排序
作为一名测量人员，xx认真履行岗位职责，紧密配合施工，制定切实可行的的测量放线方案。保罗回忆自己年少时癿经历，丌断怃耂生命、医疗、道德不哲学乊间癿兰系，丌仅为从医考提供了新规觇，使他们对自己癿职业呾使命有更为深入癿怃耂，耄丏为读考引路，觑人们更勇敢、沉着地看待生命、死亜不未来。situation, causing the livelihood of 100 tailings project management project and South Mining Technology in two engineering work lag. Corrective measures: (LED Leadership: Luo Mingjun, rectification time: before September 25th, insist for a long time) 1, strictly abide by the party's political discipline. Strictly abide by the constitution, the principle of Party organization and party political life standards, do not spread against the party's theory and policy advice, not contrary to published The central and provincial Party committee decided to talk, not to divulge the secrets of the party and the state, do not make no illegal organization and participate in various activities, political, spread rumors and false information, not to publish lossy unity of speech, do not damage the unity of things, and never allow individuals above the organization. 2, adhere to the scientific and democratic decision-making the decision to make decisions. Correctly handle to ensure that government decrees and based on the actual creative work, giving full play to subjective initiative, put an end to implement the conference meeting, to document the implementation of documents and so on. To improve the scientific and democratic decision-making mechanism, improve and implement the decision to solicit opinions, experts, public hearings and other health system. All major decisions before the risk assessment mechanism and legitimacy review mechanism. Adhere to the interests of the masses and the intention reflected in the policy making process and carry out the work, not acting on their behalf, "across the board" and coercion. (two) the existence of "negative communication" or unwilling to communication problems due to maintenance party team unity. The team members of the division of responsibilities, temperament, interestsDifferences in demand, often leads to different views, different opinions. Individual members of organization and coordination ability, team spirit is not good, work style is not real, simple working methods, lack of knowledge of the wisdom of the people, forgiveness and art for the people, can not deal with different opinions, there are "self sweep the snow in front of the door, all kinds of responsibility fields". Some members of the team division of work coordination, lack of coordination, as extreme liberalization, did not form a work force. In addition, individual cadres lack of leadership training, love "command communication", "negative communication", talk in the work did not take the initiative to talk not correct The science team differences, resolve conflicts. Corrective measures: (LED Leadership: Luo Mingjun, rectification time: before September 25th, insist for a long time) 1, to further strengthen the education and guidance on the implementation of the central eight provisions, the provincial nine provisions of the county committee of the "ten provisions" extensive publicity, eliminate the ideological11
五、算法设计
线性表含有n个元素，用数组表示在表中插入一个元素平均需要移动元素的个数是？

系别 专业（班级） 姓名 学号

………………………密……………………封…………………………装…………………订………………………线………………………
武夷学院期末考试试卷
（ 09级计算机科学与技术专业2010 ～2011学年度第 1 学期）
课程名称 数据结构 B 卷
考试形式 闭卷 考核类型 考试
本试卷共 五 大题，卷面满分100分，答题时间120分钟。
题号
一
二
三
四
五
六
七
八
总分
复核人
得分

得分
评卷人

一、选择题：（本大题共10小题，每小题2分，共20分）

　1．数据结构是(　D　)。
A．一种数据类型 B．一组性质相同的数据元素的集合
C．数据的存储结构 D．相互之间存在一种或多种特定关系的数据元素的集合
　2．下面程序段的时间复杂度为(　　)。
s=0；
for(i=1；i<n；i++)
　 for(j=1；j<i；j++)
　 s+=i*j；
　　A.O(1)　　　　　 B.O(log2n)　　　　　 C.O(n)　　　　　 D.O(n2)
　3．已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为(　A　)。
A.q->next=s->next；s->next=p；　　　　　　 B. s->next=p；q->next=s->next；
　C.p->next=s->next；s->next=q；　　　　　 D.s->next=q；p->next=s->next；
　4．已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为(A)。
A．5　　　　　　 B．6　　　　　　　　 C．16　　　　　　 D．17
5．通常将链串的结点大小设置为大于1是为了(　C　)。
A.提高串匹配效率 B.提高存储密度　　 C.便于插入操作　 D.便于删除操作
6．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为(　B　)。　 A．3，2，6，1，4，5　　 B．3，4，2，1，6，5　
C．1，2，5，3，4，6 D．5，6，4，2，3，1　
7．下列二叉排序树中，满足平衡二叉树定义的是( B)。
A． B. C. D.
8. 二维数组A的成员是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，若A按行优先方式存储，元素A[3][5]的起始地址与当A按列优先方式存储时的(　　)元素的起始地址一致。
  A．A[2][4]  B．A[3][4]   C．A[3][5]   D．A[4][4]
9．下列四个序列中，哪一个是堆(　　)。
A．75,65,30,15,25,45,20,10 B．75,65,45,10,30,25,20,15
C．75,45,65,30,15,25,20,10　　　 D．75,45,65,10,25,30,20,15
10．若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是( B)。
A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序
得分
评卷人

二、填空题：（本大题共10小题，每小题2分，共20分）

1．树的后根遍历序列与其对应二叉树的_____中根___________遍历序列相同。
2．已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是___111_____________。
3．n 个权构成一棵Huffman树，其节点总数为______n-1__________。
4．(a+b)*c+e*f的前缀表达式为_____+*+abc*ef______________________________。
5．线性表L=（a1,a2,…,an）含有n个元素，用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是____(n-1)/2_________。
6．一个非连通图的连通分量是它的一个____极大连通__________子图。
7．冒泡排序在最好的情况下需要进行元素的比较次数是___n-1__________。
8．若一棵二叉树具有41个结点，这些结点的度要么是0要么是2，则该二叉树中叶子结点个数是___21________；
9．n个顶点的连通无向图，其边的条数至多为___n(n-1)/2____。
10．广义表(()，())的深度是_2___。
得分
评卷人

三、判断题：（本大题共10小题，每小题1分，共10分）

1． 线性结构的基本特征是每个结点至多只有一个直接前驱和一个直接后继 。（   对 ）
2．如果树用二叉链表表示，则判断某个结点是不是树叶的条件是该结点左、右两个指针域的值都为空。（   错 ）
3．直接插入排序是一种稳定的排序方法。 （    对）
4．对于一个连通网，其最小生成树是唯一的。  （错   ）
5．完全二叉树的某结点若无左孩子，则它必是叶结点。（  对  ）
6．图的深度优先搜索序列和广度优先搜索序列不是唯一的。（错    ）
7．无向图的邻接矩阵是对称的，有向图的邻接矩阵一定不对称。（   错 ）
8．直接插入排序的关键码比较次数与初始排列有关。（   对）
9．广义表((2),(2))的表尾是((2))。（对    ）
10．树中结点的度是指从根到该结点所经过分支的条数。（ 错   ）
得分
评卷人

四、应用题：（本大题共5小题，每小题6分，共30分）
a

c
b
1.某二叉树的中序遍历序列为dfebagc，先序遍历序列为abdefcg； 　
g
d
(1)还原该二叉树；

e

f

 (2)写出该二叉树的后序遍历序列。fedbgca
2．已知带权图的邻接表如下所示，其中边表结点的结构为：

依此邻接表从顶点C出发进行遍历。
（1）写出依次从顶点B出发进行的深度优先遍历序列。BACDFE
（2）写出依次从顶点B出发进行的广度优先遍历序列。BAFEDC
3．对一组关键字：26，85，37，10，62，18，29，15采用快速排序方法进行排序，用第一个关键字作枢轴，请写出每趟排序结果。（只写每趟结果）
解：第一趟：（15 18 10）26 （62 37 29 85）
第二趟：（10）15（18）26（29 37）62（85）
第三趟：10 15 18 26 29 （37） 62 85
4．利用广义表的head和tail操作，可从广义表 L=((a，b)，(c，d))中分解得到原子c，其操作表达式为
head(head(tail(L)))；
分别写出从下列广义表中分解得到b的操作表达式。
(1)L1=(（a.，b），c，d)； head（tail（head（L1）））
(2)L2=((a)，(b)，(c)， d)。 head（head(tail(L2))）
5．设某带权无向图如右图，画出用Prim算法，从顶点A开始生成最小生成树的 每一步结果 。

6．对长度为12的有序表（升序），给出折半查找的判定树，给出等概率情况下的平均查找长度。

五、算法设计：（本大题共小题，每小题分，共分）
1．假设以带头结点的单链表表示非递减有序表，单链表的类型定义如下：
　　　　　　typedef struct node{
　　　　　　 int data;　　　　　　
struct node *next;
　　　　　　}LinkNode, *LinkList;
设计一算法使得插入一个数值为x的结点后，单链表仍有序。
　　void InsertLlist(LinkList L，int x)
　　　{ LinkList P,S,q;
　　　　P=L->next; q=L;
　　　While(P && P->data<x)
{q=P;
P=P->next；}
　　　　S=(LinkList)malloc(sizeof(LinkNode));
　　　　S->data=x;
　　　 S->next=P;
　　　　q->next=S;
　　}
1．假设以带头结点的单链表表示非递减有序表，单链表的类型定义如下：
　　　　　　typedef struct node{
　　　　　　 int data;　　　　　　
struct node *next;
　　　　　　}LinkNode, *LinkList;
设计一算法删除表中所有值大于min且小于max（假设min<max）的结点，同时释放结点空间。
　Status Delete_Between(LinkList L, int max, int min)
　　　{ p=L;　
　　　　While(p->next->data<=min)p=p->next;　　
　　　　if(p->next)
　　　　{ q=p->next;
　　　　　While(q->data<max){k=q; q=q->next; free(k); }　
　　　　　　p->next=q;
　　　　}　　
　　 }