一、单项选择题(每小题2分，共30分)
1.( )是性质相同的数据元素的集合，是数据的子集。 A.数据元素 C.数据结构
B.数据对象 D.数据项
2.设链表中的结点是NODE类型的结构体变量，且有NODE头P;为了申请一个新结点，并由p指向该结点，可用以下语句( )。
A.p=(NODE*)malloC{sizeof(NODE); C.p=(NODE)malloC(sizeof(p))
B.p=(*ODE)malloC(sizeof(NODE)); D.p=(NODE*)malloC(sizeof(p));
3.设顺序存储的线性表长度为n，要在第i个元素之前插入一个新元素，按课本的算法当i=( )时，移动元素次数为2。
A.n/2 C.1
B.n D.n-l
4.一个栈的进栈序列是1，2，3，4，则栈的不可能的出栈序列是( )(进出栈操作可以交替进行)。 A.3,2,4,1 C.4,3,2,1
B.1,4,2,3 D.3,2,1,4
5.设有一个带头结点的链队列，队列中每个结点由一个数据域data和指针域next组成，front和rear分别为链队列的头指针和尾指针。设p指向要入队的新结点（该结点已被赋值),则入队操作为( )。
A.rear->next=p;rear=p; C.p=rear->next;rear=p;
B.rear->next=p;p=rear; D.rear=p;rear->next=p;
6.以下说法不正确的是( )。
A.顺序校中，钱满时再进行进校操作称为\上溢\B.顺序校中，找空时再作出校校操作称为\下溢\
C.顺序队列中，当尾指针已经超越队列存储空间的上界，则一定是队列已满 D.顺序队列中，队列的头指针和尾指针均超越队列存储空间的上界，则队列已空
7.设有一个20阶的对称矩阵A，采用压缩存储方式，将其下三角部分以行序为主序存储到一维数组中
第 16 页 共 30 页
(矩阵A的第一个元素为a11，数组b的下标从1开始)，则矩阵元素a8,5在一维数组b中的下标是( )。
A.30 C.40
B.28 D.33
8.深度为5的完全二叉树第5层上有4个结点，该树一共有( )个结点。 A.28 C.31
B.30 D.19
9.已知一个图的所有顶点的度数之和为m，则m一定不可能是( )。 A.4 C.12
D.9
B.8
10.以下说法正确的是( )。 A.连通图G的生成树中可以包含回路 C.连通图G的生成树一定是唯一的
B.连通图G的生成树可以是不连通的
D.连通图G的生成树一定是连通而不包含回路的
11.对n个元素进行冒泡排序，通常要进行n-l趟冒泡，在第j趟冒泡中共要进行( )次元素间的比较。
A.j C.n-j
B.j-l D.n-j-l
12.在排序过程中，可以有效地减少一趟排序过程中元素间的比较次数的算法是( )。 A.冒泡
B.选择 D.折半插入
C.直接插入
13.如图若从顶点a出发按深度优先搜索法进行遍历，则可能得到的顶点序列为( )。
A.aebCfd C.aCebdf
B.abedCf D.aCfbde
14.一棵哈夫曼树有n个叶子结点(终端结点)，该树总共有( )个结点。 A.2n-2 C.2n
B.2n-l
D.2n十2
第 17 页 共 30 页
15.数据的( )结构与所使用的计算机无关。 A.逻辑 C.存储
二、填空题(每小题2分，共24分)
1.通常可以把一本含有不同章节的书的目录结构抽象成____________结构。
2.要在一个单向链表中p所指向的结点之后插入一个S所指向的新结点，若链表中结点的指针域为next，可执行____________和p->next==s的操作。
3.设有一个非空的链栈，栈顶指针为hs，要进行出栈操作，用x保存出栈结点的值，找结点的指针域为next，则可执行x=hs一>data;________________________。
4.在一个不带头结点的非空链队中，f和r分别为队头和队尾指针，队结点的数据域为data，指针域为next，若要进行出队操作，并用变量x存放出队元素的数据值，则相关操作为x=f->data;________________________。
5.循环队列的最大存储空间为MaxSize=8，采用少用一个元素空间以有效的判断栈空或栈满，若队头指针front=4，则当队尾指针rear=____________时，队列为空，当rear=____________时，队列有6个元素。
6.稀疏矩阵存储时，采用一个由____________、____________、非零元3部分信息组成的三元组唯一确定矩阵中的一个非零元素。
7.一棵二叉树顺序编号为6的结点(树中各结点的编号与等深度的完全二叉中对应位置上结点的编号相同)，若它存在右孩子，则右孩子的编号为____________。
8.数据结构中的数据元素存在多对多的关系称为____________结构o 9.数据结构中的数据元素存在一对多的关系称为____________结构。 10.如下图所示的二叉树，其前序遍历序列为____________
B.物理 D.逻辑与存储
11.在队列的顺序存储结构中，当插入一个新的队列元素时，____________指针的值增1，当删除一个
第 18 页 共 30 页
元素队列时，____________指针的值增1。
12.循环队列的引入，目的是为了克服____________________________________。
三、综合题(每小题10分，共30分)
1.(1)设head1和P1分别是不带头结点的单向链表A的头指针和尾指针，head2和P2分别是不带头结点的单向链表B的头指针和尾指针，若要把B链表接到A链表之后，得到一个以head1为头指针的单向循环链表，写出其中两个关键的赋值语句(不用完整程序，结点的链域为next)
(2)单向链表的链域为next，设指针p指向单向链表中的某个结点，指针S指向一个要插入链表的新结点，现要把s所指结点插入p所指结点之后，某学生采用以下语句:
p->next==s;s->next==p->next;
这样做正确吗?若正确则回答正确，若不正确则说明应如何改写。
2.(1)画出对长度为10的有序表进行折半查找的判定树(以序号1，2，……10表示树结点)。 (2)对上述序列进行折半查找，求等概率条件下，成功查找的平均查找长度。
3.(1)利用筛选法，把序列{37，77，62，97，11，27，52，47}建成堆(小根堆)。画出相应的完全二叉树。
(2)写出对上述堆所对应的二叉树进行前序遍历得到的序列。
四、程序填空题(每空2分，共16分)
第 19 页 共 30 页
1.以下函数为直接选择排序算法，对a[口，a[幻，…a[n]中的记录进行直接选择排序，完成程序中的空格。
第 20 页 共 30 页