}
__ return -1____; }
2．以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针
struct node { ElemType data;
struct node *next; };
struct node *top ;
void Push(ElemType x)
{
struct node *p;
p=(struct node*)malloc(_sizeof (struct node)___); p->data=x; __ p->next=top ___; __ top=p __; }
3．以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、rear分别是链队列的队头、队尾指针
struct node { ElemType data;
struct node *next; };
struct node *front，*rear;
void InQueue(ElemType x) {
struct node *p;
p= (struct node*) ___ malloc(sizeof (struct node))____; p->data=x;
p->next=NULL;
__ rear->next=p ____; rear= ___ p _____; }
期末综合练习二
一、单项选择题
1．（ B ）是性质相同的数据元素的集合，是数据的子集。
A．数据元素 B．数据对象 C．数据结构 D．数据项 2．同一种逻辑结构（ B ）。
A．只能有唯一的存储结构 B．可以有不同的存储结构
C．只能表示某一种数据元素之间的关系 D．以上三种说法均不正确
3．设链表中的结点是NODE类型的结构体变量，且有NODE *p；为了申请一个新结点，并由p指向该结点，可用以下语句（A．p=(NODE *)malloc(sizeof(NODE)); A ）。 6
B．p=(*NODE)malloc(sizeof(NODE)); C．p=(NODE )malloc(sizeof(p)); D．p=(NODE *)malloc(sizeof(p)); 4．链表所具备的特点是（ C ）。
A．可以随机访问任一结点 B．占用连续的存储空间
C．插入删除元素的操作不需要移动元素结点 D．可以通过下标对链表进行直接访问
5．设顺序存储的线性长度为n，要在第i个元素之前插入一个新元素，按课本的算法当i= （ D ）时，移动元素次数为2
A．n/2 B．n C．1 D．n-1
6．数据的物理结构（ D ）。
A．与数据的逻辑结构无关 B．仅仅包括数据元素的表示
C．只包括数据元素间关系的表示 D．包括数据元素的表示和关系的表示
7．一个栈的进栈序列是1，2，3，4，则栈的不可能的出栈序列是（ B ）（进出栈操作可以交替进行） A．3，2，4，1 B．1，4，2，3 C．4，3，2，1 D．3，2，1，4
8．线性结构中数据元素的位置之间存在（ A ）的关系。 A．一对一 B．一对多
C．多对多 D．每一个元素都有一个直接前驱和一个直接后继
9．设有一个带头结点的链队列，队列中每个结点由一个数据域data和指针域next组成，front和rear分别为链队列的头指针和尾指针。
设p指向要入队的新结点(该结点已被赋值)，则入队操作为（ A ）。 A．rear->next=p;rear=p; B．rear->next=p; p = rear; C．p = rear->next;rear=p; D．rear=p;rear->next=p; 10．以下表中可以随机访问的是（ D ）。
A．单向链表 B．双向链表
C．单向循环链表 D．顺序表 11．以下说法不正确的是（ C ）。
A．顺序栈中，栈满时再进行进栈操作称为“上溢”
B．顺序栈中，栈空时再作出栈栈操作称为“下溢”
C．顺序队列中，当尾指针已经超越队列存储空间的上界，则一定是队列已满 D．顺序队列中，队列的头指针和尾指针均超越队列存储空间的上界，则队列已空 12．算法的时间复杂度与（ C ）有关。
A．所使用的计算机 B．与计算机的操作系统
C．与算法本身 D．与数据结构
13．设有一个20阶的对称矩阵A，采用压缩存储方式，将其下三角部分以行序为主序存储到一维数组中（矩阵A的第一个元素为a11，数组b的下标从1开始），则矩阵元素a8,5在一维数组b中的下标是（ D ）。
A．30 B．28 C．40 D．33
14．设有一个长度为n的顺序表，要删除第i个元素需移动元素的个数为（ B ）。 A．n-i+1 B．n-i C．n-i-1 D．i
15．深度为5的完全二叉树第5层上有4个结点，该树一共有（ D ）个结点。
A．28 B．30 C．31 D．19
16．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用的语
句是（ C ）。
A．p=q->next B．p->next=q C．p->next=q?next D．q->next=NULL 17．已知一个图的所有顶点的度数之和为m，则m一定不可能是（ D ）。
A．4 B．8 C．12 D．9
18．从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执行（ A ）。 A．x=top->data; top=top->next; B．x=top->data; C．top=top->next; x=top->data; D．top=top->next; x=data; 19．以下说法正确的是（ D ）。
7
A．连通图G的生成树中可以包含回路
B．连通图G的生成树可以是不连通的 C．连通图G的生成树一定是唯一的
D．连通图G的生成树一定是连通而不包含回路的
20．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（ C ）。 A．r=f->next; B．r=r->next; C．f=f->next; D．f=r->next;
21． 对n个元素进行冒泡排序，通常要进行n-1趟冒泡，在第j趟冒泡中共要进行（ C ）次元素间的比较。 A．j B．j-1 C．n-j D．n-j-1
22．一个栈的进栈序列是a，b，c，d，e，则栈的不可能输出序列是（ A ）（进栈出栈可以交替进行）。
A．dceab B．edcba C．decba D．abcde
23．在排序过程中，可以有效地减少一趟排序过程中元素间的比较次数的算法是（ D ）。
A．冒泡 B．选择 C．直接插入 D．折半插入 24．有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（ B ）。
A．26/10 B．29/10 C．29/9 D．31/10
25．如图1若从顶点a出发按深度优先搜索法进行遍历，则可能得到的顶点序列为（ B ）。 A．aebcfd
B．abedcf C．acebdf D．acfbde
图1
26．排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（ C ）。
A．冒泡 B．直接插入 C．折半插入 D．选择排序
27．一棵哈夫曼树有n个叶子结点（终端结点），该树总共有（ B ）个结点。
A．2n-2 B．2n-1 C．2n D．2n+2
28．设有一个10阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组B中（数组下标从1开始），则矩阵中元素A8,5在一维数组B中的下标是（ A ）。
A．33 B．32 C．85 D．41
29．数据的（ A ）结构与所使用的计算机无关。
A．逻辑 B．物理 C．存储 D．逻辑与存储 30．在一个无向图中，所有顶点的度数之和等于边数的（ D ）倍。 A．3 B．2.5 C．1.5 D．2
二、填空题
1．通常可以把一本含有不同章节的书的目录结构抽象成___树形__结构。 2．栈和队列的操作特点分别是__先进后出___和 ___先进先出__。
3．要在一个单向链表中p所指向的结点之后插入一个s所指向的新结点，若链表中结点的指针域为next，可执行__ s->next= p->next；
______和p->next=s;的操作。
4．结构中的数据元素存在多对多的关系称为____图状 （网状）__结构。
5．设有一个非空的链栈，栈顶指针为hs，要进行出栈操作，用x保存出栈结点的值，栈结点的指针域为next，则可执行x=hs->data;
___ hs=hs->next;___ __。
6．根据数据元素间关系的不同特性，通常可分为集合、线性、树形 、 图状 四类基本结构。
7．在一个不带头结点的非空链队中，f和r分别为队头和队尾指针，队结点的数据域为data，指针域为next，若要进行出队操作，并用变量x存放出队元素的数据值，则相关操作为x=f->data; __ f=f->next;____ __。
8
a b e c d f 8．要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为________和 _
n-1,O(n)_______ 。
9．循环队列的最大存储空间为MaxSize=8，采用少用一个元素空间以有效的判断栈空或栈满，若队头指针front=4，则当队尾指针rear= ____ 4 ____时，队列为空，当rear= ___ 2 _____时，队列有6个元素。
10．稀疏矩阵存储时，采用一个由__行号__ 、___列号 _ 、__非零元__3部分信息组成的三元组唯一确定矩阵中的一个非零元素。 11．在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是值域 左指针 、 右指针 。
12．一棵二叉树顺序编号为6的结点（树中各结点的编号与等深度的完全二叉中对应位置上结点的编号相同），若它存在右孩子，则
右孩子的编号为___13_____。
13．向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行s->next=h;和__ h=s __。
14．在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为__ r->next=s __和r=s; (结点的指针域为next) 15．如图2所示的二叉树，其前序遍历序列为___ abdefcg __。
a b c d e f g 图2
16．设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有___12__个结点。（根所在结点为第1层）
17．在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针的值增1，当删除一个元素队列时， 头 指针的值增1。 18．对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的__行下标_、__列下标_和___非零元素值_三项信息。
19．循环队列的引入，目的是为了克服 假上溢 。
20．在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较___3______次。
三、综合题
1．（1）设head1和p1分别是不带头结点的单向链表A的头指针和尾指针，head2和p2分别是不带头结点的单向链表B的头指针和尾指
针，若要把B链表接到A链表之后，得到一个以head1为头指针的单向循环链表，写出其中两个关键的赋值语句（不用完整程序，结点的链域为next）。
答：p1->next= head2；p2->next= head1；
（2）单向链表的链域为next，设指针p指向单向链表中的某个结点，指针s指向一个要插入链表的新结点，现要把s所指结点插入p
所指结点之后，某学生采用以下语句： p->next=s; s->next=p->next;
这样做正确吗？若正确则回答正确，若不正确则说明应如何改写 答：不对，s->next= p->next；p->next=s； 2．
(1)以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树( 要求每个结点的左子树根结点的权小于等于右子树根结点的权)，给出相应权重值叶结点的哈夫曼编码。
9
(1) 33 15 18 7 8 9 9 4 5 2 3 2：1110 3: 1111 4：110 7：00 8：01 9：10
(2) 一棵哈夫曼树有n个叶结点，它一共有多少个结点？简述理由？
答: 2n-1个，因为非叶结点数比叶结点数少一个。
3．（1）画出对长度为10的有序表进行折半查找的判定树（以序号1，2，??10表示树结点）
5 2 8 1 3 6 9 4 7 10 （2）对上述序列进行折半查找，求等概率条件下，成功查找的平均查找长度 答：ASL=（1x1+2x2+3x4+4x3）/10=29/10
4．一组记录的关键字序列为（46，79，56，38，40，84）
1）利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交换元素的过程，要求以升序排列）初始序列
46，79，56，38，40，84 40，79，56，38，40，84 40，79，56，38，79，84 40，38，56，38，79，84 40，38，56，56，79，84 40，38，46，56，79，84
2）对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。
10
（
（