一单项选择题 (在每小题的四个备选答案中选出一个正确答案并将正确答案的序号填在题干的括号内错选多选或未选均无分每小题分共分)
下列数据结构中( )不都是线性结构
A栈和队列
B队列和数组
C数组和串
D文件和队列
为了最快地对线性结构的数据进行某数据元素的读取操作则其数据存储结构宜采用( )方式
A顺序存储
B链式存储
C索引存储
D散列存储
设双链表中结点的前趋指针和后继指针的域名分别为t和r则删除双链表中指针s所指结点的操作为( )
As>t>r=s>t;s>r>t=s>r;
Bs>t>r=s>r;s>r>t=s>t;
Cs>r=s>t>r;s>t=s>r>t;
Ds>t=s>t>r;s>r=s>r>t;
假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域现要把一个指针s所指的新结点作为非空双链表中q所指地点(中间结点)的直接后继结点插入到该双向链表中则下列算法段能正确完成上述要求的是( )
Aq>right=s; s>left=q; q>right>left=s; s>right=q>right;
Bs>left=q; q>right=s; q>right>left=s; s>right=q>right;
Cs>left=q; s>right=q>right; q>right>left=s; q>right=s;
D以上都不对
由下列三棵树组成转的森林换成一棵二叉树为( )
具有个结点的完全二叉树的深度为( )
A
B
C
D
已知一个稀疏矩阵的三元组表如下()()()()()()则其转置矩阵的三元组表中第个三元组为( )
A()
B()
C()
D()
无向图的邻接矩阵是一个( )
A对称矩阵
B零矩阵
C上三角矩阵
D对角矩阵
下列说法中正确的是( )
A一个具有n个顶点的无向完全图的边数为n(n)
B连通图的生成树是该图的一个极大连通子图
C图的广度优先搜索是一个递归过程
D对于非连通图的遍历过程中每调用一次深度优先搜索算法都得到该图的一个连通分量
顺序查找法与二分查找法对存储结构的要求是( )
A顺序查找与二分查找均只适用于顺序表
B顺序查找与二分查找既适用于顺序表也适用于链表
C顺序查找只适用于顺序表
D二分查找只适用于顺序表
在开散列表上每个地址单元所链接的同义词表( )
A其键值相同
B其元素值相同
C其散列地址相同
D其含义相同
散列文件中的记录通常成组存放若干个记录组成一个存储单位这个存储单位称为( )
A磁道
B块
C柱面
D桶
索引非顺序文件中的索引表是( )
A非稠密索引
B稠密索引
C主索引
D多级索引
对n个记录的文件进行堆排序最坏情况下的执行时间为( )
AO(log n)
BO(nlog n)
CO(n)
DO(n )
一组记录的关键码为()则利用快速排序方法以第一个记录为基准得到的一次划分结果为( )
A
B
C
D
二填空题(每小题 分共分)
请在每小题的空格中填上正确答案错填不填均无分
下列程序段的时间复杂性的量级为_________
for (i=;i for(j=i;j t=t+1
17.设某非空单链表，其结点形式为
date next
， 若要删除指针q所指结点的直接后继结点，则需执行下列语句序列：
p=q->next;________;free(p);
18.队列可以看成是一种运算受限制的线性表，也称为______线性表。Tw.wINgwit.cOm
19.链栈的类型定义如下：
typedef struct node
{ DateType date;
struct node *next;
}LStackTp;
若栈非空，则退栈操作可以用下列算法片段实现：
p=ls;/* ls为栈顶指针*/
*x=p->date; /*栈顶元素通过参数返回*/
___________;
free(p); /*释放原栈顶结点空间*/
20.在非空树上，_____没有直接前趋。
21.设有33个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有____个结点。
22.无向图中的连通分量定义为无向图的_________。
23.在开散列表上查找键值等于K的结点，首先必须计算该键值的______，然后再通过指针查找该结点。
24.对静态表顺序查找算法采用设置岗哨方式与普通的设置循环控制变量相比，进行一次查找所花费的平均时间大约减少_____。
25.若要对某二叉排序树进行遍历，保证输出的所有结点键值序列按递增次序排列，应对该二叉树采用_________遍历法。
26.文件的基本存取单位是_________。
27.设需将一组数据按升序排序。在无序区中依次比较相邻两个元素a i 和a i+1 的值，若a i 的值大于a i+1 的值，则交换a i 和a i+1 。如此反复，直到某一趟中没有记录需要交换为止，该排序方法被称为_________。
28.在插入排序、快速排列、堆排序、归并排序中，排序方法不稳定的有_________。
三、应用题 (本大题共5小题，共30分)
29.现有一组单词(WEK,SUN,MON,TUE,WED,THU,FRI,SAT),其相应的散列函数值为(3，2，6，3，2，5，6，0)，散列表长度为10(散列地址空间为0..9)，要求：(6分)
(1)构造该闭散列表，并用线性探测法解决沖突;
(2)若对每个元素查找一次，求总的比较次数。
30.已知无向图G的邻接矩阵如下。假设对其访问时每行元素必须从右到左，请画出其所有的连通分量，并且写出按深度优先搜索时各连通分量的访问序列。(8分)
31.设要将序列(Q，H，C，Y，P，A，M，S，R)按字母升序排序，请画出采用堆排序方法时建立的初始堆及第一次输出堆顶元素后筛选调整以后的堆。(8分)
32.设二叉树后根遍历的结果为BCA，画出所有可得到这一结果的二叉树。(5分)
33.设有一循环队列sq.data[maxsize],一般情况下队列中至多可存放多少个元素?为什么?(3分)
四、设计题 (本大题共2小题，共14分)
34.设有两个按升序排列的单链表X和Y，其头指针分别为p,q结点结构说明如下：
typedef struct nodel
{
int data;
struct nodel *next
}node;
试设计一个算法void concat(node *p,*q)将它们合并成一个以p为头指针的单链表Z，使其仍然有序。(6分)
35.设有序表r长度为n，欲在表中查找键值为Kn的某元素。若查找成功，则返回该元素在有序表r中的位置，若不成功，则返回0值。用二分查找法，编写一算法完成上述操作，并给出该算法的平均查找长度。该有序表存储结构定义如下：(8分)
typedef struct
{ keytype key;
Elemtype data;
}rec;
typedef struct
{ rec item[maxsize+1];
int n;
}sqtable;
