试卷代号：1252
数据结构（本） 试题
2019年7月
一、单项选择题（每小题3分，共30分）
1.以下说法正确的是（ ）。
A.在顺序表中可以随机访问任一结点
B.-种逻辑结构在存储时只能采用一种存储结构
C.对链表进行插入、删除元素的操作一定要移动结点
D.在链表中可以随机访问任一结点
2.线性表在存储后，如果要求：仅通过已知的指向第i个结点的指针，进行相关操作，访问到该结点的前驱结点，则采用（ ）存储方式是不可行的。
A.单链表B.双链表
C.单循环链表D.顺序表
3.栈和队列的共同特点是（ ）。
A.都是先进后出B.元素都可以随机进出
C.只容许在端点处插入和删除元素D.都是先进先出
4.元素4，6，8，10按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的可能输出序列是（ ）（进栈出栈可以交替进行）。
A.10，8，4，6B.10，6，4，8
C.8，4，6，10D.10，8，6，4
5.在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，从该队列中进行出队操作，并把结点的值保存在变量x中的操作为（ ）。
A.x= r->data; r= r- >next;B.r=r- >next; x= r- >data;
C.x= f->data; f= f- >next;D.f=f->next; x= f->data;
6.设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存到一维数组B中（数组下标从1开始），则矩阵元素a。，。对应于数组B中第（ ）号元素。（矩阵中的第1个元素是ai，，）
A.42B.39
C.38D.40
7.-棵采用链式存储的二叉树中，共有n-l个指针域被有效使用（即指针域为非空）。该二叉树中有（ ）个指针域为空。
A.n+lB.n
C.n-lD.n-2
8.设一棵哈夫曼树共有n个非叶结点，则该树共有（ ）个结点。
A. 2nB.2n+l
C.2n-lD.2n+2
9.如图所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点
序列为（ ）。
A.ahbedfcB.ahcfebd
C.ahebcdfD.ahebcfd
10.线性表以（ ）方式存储，能进行折半查找。
A.关键字有序的链接B.顺序
C.关键字有序的顺序D.数组
二、填空题（每小题2分，共24分）
11.n个元素进行冒泡法排序，通常需要进行___ _趟冒泡。
12.在对一组序列(35，19，77，2，6，53，55，27，26，98)进行直接插入排序时，当把第9个记录26插入到有序表时，为寻找插入位置需进行____ 次元素间的比较。
13.在C语言中，分别存储“S”和‘s，，各需要占用___ _字节。
14.数据的逻辑结构在计算机中的表示称为__ __结构。
15.在一棵二叉树中，若编号为i的结点是其双亲结点的左孩子，则i结点的双亲结点的顺序编号为_ ___。
16.设有一个头指针为head的单向链表，p指向表中某一个结点，且有p- >next为NULL，现要把该单向链表构造成单向循环链表，可通过操作 。
17.从一个栈顶指针为top的链栈中删除一个结点时，用d保存被删结点的值，可执行d=top->data;和 。(结点的指针域为next，数据域为data)。
18.循环链队列中，设front和rear分别为队头和队尾指针，（最多元素为MaxSize，采用少用一个元素的模式），判断循环链队列为满的条件为 。
19. -棵有7个权重值构造的哈夫曼树，共有 个结点。
20.二叉树中有1个1度结点，8个2度结点，则该二叉树树共有_ ___个结点。
21.如图所示的二叉树，其先序遍历序列为 。
22.在查找表中，通过记录的某关键字能唯一地确定一个记录，该关键字称为 。
三、综合题（每小题6分，共30分）
23.(1)对给定权值4，2，6，6，7，8，构造高度为4层的哈夫曼树。（设根为第1层）
提示：构造中当出现有两个以上值相等的可选结点时，可适当选择结点组合，以控制树的高度。
(2)求树的带权路径长度。
24.如下的一棵二叉棵树，
(1)请给出前序遍历序列？请给出中序遍历序列？
(2)把1，2，3，4，5，6，7，8，9填人，使它成为一棵二叉排序树。
提示：设图中的树是二叉排序树，则中序遍历序列是有序的，从而找出中序遍历序列与1，
2，…9的对应关系。
(3)在图中给出在二叉排序树中插入结点2.5的结果。
四、程序填空题（每空2分，共16分）
25.以下函数为直接选择排序算法，对a[l],a[2]，…a[n]中的记录进行直接选择排序，完成程序中的空格
typedef struct
{ int key;
……
}NODE;
void selsort(NODE a[] ,int n)
{
int i,j,k;
NODE temp;
for(i=1；i<=(1) ；i++)
{
k=i：
for(j=i+1;j<=(2) ；j++)
if(a[j].key
if (i！=k)
{
temp=a[i];
(4) ；
(5) ；
}
}
}
26.设有一个头指针为head的不带头结点单向链表，且p、q是指向链表中结点类型的指针变量，p指向链表中某结点a（设链表中没有结点的数据域与结点a的数据域相同），在以下程序段中，写出相关语句
(1)使该单向链表成为单向循环链表
(2)删去a结点
q=p；x= p- >data；
while (q->next!=NULL)q=q->next;
(1)
q=p；p= p->next；
while(p->datal =x)
{ q=p；
(2)
}
(3)
微信扫码添加好友
如二维码无法识别，可拨打 13662661040 咨询。