试卷三
一、单项选择题(在下列每小题四个备选答案中选出一个正确答案，并将其字母标号填入题干的括号内。每小题2分，共30分)
1．数据结构可以形式化地定义为（S，△），其中S指某种逻辑结构，△是指（）A.S上的算法  B.S的存储结构
C.在S上的一个基本运算集
D.在S上的所有数据元素
2．下列说法正确的是（）
A.线性表的逻辑顺序与存储顺序总是一致的
B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续
C.线性表的线性存储结构优于链式存储结构
D.每种数据结构都具有插入、删除和查三种基本运算
3．稀疏矩阵一般采用（）方法压缩存储。
A.三维数组
B.单链表
C.三元组表
D.散列表
4.在一个单链表中，若p↑结点不是最后结点，在p↑之后插入s↑结点，则实行( )。
A. s↑.next:=p；p↑.next=s;
B. s↑.next:=p↑.next;p↑.next:=s；
C. s↑.next:=p↑.next;p:=s;
D. p↑.next:=s;s↑.next=p;
5.某个向量第一元素的存储地址为100，每个元素的长度为2，则第五个元素的地址是
( )。
A.110
B.108
C.100
D.120
6.下面的二叉树中，( )不是完全二叉树。
7.一组记录的排序码为(47、78、61、33、39、80)，则利用堆排序的方法建立的初始堆为
( )。
A.78、47、61、33、39、80
B.80、78、61、33、39、47
C.80、78、61、47、39、33
D.80、61、78、39、47、33
8.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针s所指的新结点作为非空双链表中q所指地点(中间结点)的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是( )
A.q->right=s; s->left=q; q->right->left=s; s->right=q->right;
B.s->left=q; q->right=s; q->right->left=s; s->right=q->right;
C.s->left=q; s->right=q->right; q->right->left=s; q->right=s;
D.以上都不对
9.由下列三棵树组成转的森林换成一棵二叉树为( )
10. for（i=0；i<m；i++）
for（j=0；j<t；j++）
c［i］［j］=0；
二叉树的深度为k
for（i=0；i<m；i++）
for（j=0；j<t；j++）
for（k=0；k<n；k++）
c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；
上列程序的时间复杂度为（）
A.O（m+n×t）
B.O（m+n+t）
C.O（m×n×t）
D.O（m×t+n）
11.设循环队列的元素存放在一维数组Q［0‥30］中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。如果队列中元素的个数为11，front的值为25，则rear应指向的元素是（）
A.Q［4］
B.Q［5］
C.Q［14］
D.Q［15］
12.定义二维数组A［1‥8，0‥10］，起始地址为LOC，每个元素占2L个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为（）
A.LOC+28L
B.LOC+36L
C.LOC+50L
D.LOC+52L
13.采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（）
A.插入和快速
B.冒泡和快速
C.选择和插入
D.选择和冒泡
14.设h是指向非空带表头结点的循环链表的头指针，p是辅助指针。执行程序段
p=h;
while (p->next->next!=h)
p=p->next;
p->next=h;
后（其中，p->next为p指向结点的指针域），则( )
A. p->next指针指向链尾结点
B. h指向链尾结点
C. 删除链尾前面的结点
D. 删除链尾结点
15.某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是( )
A.高度等于其结点数
B.任一结点无左孩子
C.任一结点无右孩子
D.空或只有一个结点
二、填空题(本大题共13小题，每小题2分，共26分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16.数据的逻辑结构通常包括集合、线性结构、____________和图状结构。
17．给定n个值构造哈夫曼树。根据哈夫曼算法，初始森林中共有n棵二叉树，经过次合并后才能使森林中的二叉树的数目由n棵减少到只剩下一棵最终的哈夫曼树。
18．树型结构结点间通过“父子”关系相互关联，这种相互关联构成了数据间的关系。
19.在一个具有n个结点的单链表中查值为m的某结点，若查成功，则需平均比较的结点数为____________。
20.数据表示和________________是程序设计者所要考虑的两项基本任务。
21.在循环队列中，存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为_________。
22.深度为k的二叉树至多有_________个结点，最少有_________个结点。
23．在堆排序和快速排序中，若原始记录已基本有序，则较适合选用。
24.在一棵二叉排序树上按____________遍历得到的结点序列是一个有序序列。
25.实现二分查的存储结构仅限于顺序存储结构，且其中元素排列必须是____________的。
26.三个结点可构成________种不同形态的二叉树。
27.设需将一组数据按升序排序。在无序区中依次比较相邻两个元素a i和a i+1的值，若a i的
值大于a i+1的值，则交换a i和a i+1。如此反复，直到某一趟中没有记录需要交换为止，该排序方法被称
为_________。
28.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为
2n个，其中________个用于链接孩子结点。
三、应用题（本大题共5小题，每小题6分，共30分）
29.已知一棵二叉树的前序序列是ABCDEFG，中序序列是CBDAEGF。请构造出该二叉树，并给出该二叉树的后序序列。
30．有一字符串序列为5*-x-y/x+2，利用栈的运算将其输出结果变为5x-*yx+/-2，试写出该操作的入栈和出栈过程（采用push(a)表示a入栈，pop(a)表示a出栈）。
31.已知某二叉树的顺序存储结构如图所示，试画出该二叉树，并画出其二叉链表表示。
32.已知一组键值序列为(38，64，73，52，40，37，56，43)，试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。
33.请按照数列{28，45，33，12，37，20，18，55}的先后插入次序，生成一棵二叉排序树。
四、算法设计题(本大题共3小题，共14分)
34.试编写一算法，以完成在带头结点单链表L中第i个位置前插入元素X的操作。（4分）
35.某带头结点的单链表的结点结构说明如下：（6分）
typedef struct node1
{
int data;
struct node1 *next
}node；
试设计一个算法int copy(node *head1, node *head2)，将以head1为头指针的单链表复制到一个不带头结点且以head2为头指针的单链表中。
36.若二叉树存储结构采用二叉链表表示，试编写一算法，计算一棵二叉树的所有结点数。（4分）
参考答案
一、选择题（本题共30分，每题2分）
1、 C
2、B
3、C
4、B
5、B
6、C
7、B
8、C
9、A
10、C    11、B  12、D  13、C  14、D  15、A
二、填空题（本题共26分，每小题2分）
16、树状结构17、n-1
18、逻辑19、n/2
20、数据处理21、front==(rear+1)%n
22、2k-1，k 23、堆排序
24、中序25、有序
26、5 27、冒泡排序
28、n-1
三、应用题（本题共30分，每小题6分）
29、
后序序列：CDBGFEA (3分)
(3分)
30、push(5);pop(5);push(*);push(-);push(x);pop(x);pop(-);pop(*);push(-);push(y);
pop(y);push(/);push(x);pop(x);push(+);pop(+);pop(/);pop(-);push(2);pop(2); 32、
第1趟：[37] 38 [73 52 40 64 56 43]
第2趟：37 38 [43 52 40 64 56] 73
第3趟：37 38 [40] 43 [52 64 56] 73
第4趟：37 38 40 43 52 [64 56] 73
第5趟：37 38 40 43 52 [56] 64 73
第6趟：37 38 40 43 52 56 64 73
31、
33、
四、算法设计题（本题共14分）
34、(4分)
typedef struct node *pointer;
struct node
{
datatype data;
pointer next;
};
typedef pointer lklist;
void insert_lklist(lklist head,datatype x,int i)
{
pointer *p,*s;
p=head;
j=0;
while((p->next!=NULL)&&(j<i-1))
{p=p->next;j++;}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。