数据结构期末综合练习.pdf

数据结构（本）期末综合练习数据结构（本）期末综合练习一一、单项选择题 针 对线性表，在存储后如果最常用的操作是取第i个结点及其前驱，则 采 用（D ）存储方式最节省时间。A.单链表 B.双链表 C.单循环链表 D.顺序表2.线性表采用链式存储时，其 地 址（C ）。A.一定是不连续的 B.必须是连续的C.可以连续也可以不连续 D.部分地址必须是连续的 数 据结构中，与所使用的计算机无关的是数据的（D ）结构。A.物理 B.存储 C.逻辑与物理 D.逻辑4.带头结点的单向链表的头指针为he ad,该链表为空的判定条件是（C ）的值为真。A.he ad =N U L L B.he ad-n e xt=he adC.he ad-n e xt=N U L L D.he ad =he ad-n e xt5.以下特征中，（D ）不是算法的特性。A.有穷性 B.确定性 C.可行性 D.有0个或多个输出6.设顺序存储的线性表长度为n,对于插入操作,设插入位置是等概率的，则插入一个元素平均移动元素的次数为（A ）。A.n/2 B.n C.n-1 D.n-i+1 设 有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（A）。A.n-i+1 B.n-i C.n-i-l D.i8.一个栈的进栈序列是5,6,7,8,则栈的不可能的出栈序列是（A ）（进出栈操作可以交替进行）A.5,8,6,7B.7,6,8,5C.7,6,5,8 D.8,7,6,5 栈 的插入删除操作在（D ）进行。A.栈底 B.任意位置 C.指定位置D.栈顶1 0.栈和队列的相同点是（D ）。A.都是后进先出 B.都是后进后出C.逻辑结构与线性表不同D.逻辑结构与线性表相同，都是操作规则受到限制的线性表 以 下 说法正确的是（C ）。A.栈的特点是先进先出，队列的特点是先进后出B.栈和队列的特点都是先进后出C.栈的特点是先进后出，队列的特点是先进先出D.栈和队列的特点都是先进先出 在C语言中，利用数组a存放字符串“H e l l o ，以下语句中正确的是（A D ）。A.c har a 1 0 =H e l l o”;B.c har a 1 0 ;a=H e l l o”；C.c har a 1 0 =H e l l o ;D.c har a 1 0 =H ,e ,T,T,o ;元 素2,4,6,8按顺序依次进栈，则该栈的不可能输出序列是（D ）（进栈出栈可以交替进行）。A.8,6,4,2 B.2,4,6,8C.4,2,8,6 D.8,6,2,414.设有一个15阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b 中。（矩 阵 A 的第一个元素为a,P数组b 的下标从1 开始），则数组元素 b13对应A 的矩阵元素是（A）。A.a5.3 B.a6.4 C.a7,2 D.%81 5 .设有一个1 5 阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1 开始），则矩阵中元素ai.e 在一维数组B中的下标 是（CA.42 B.1 3 C.2 7 D.3216一棵完全二叉树共有30个结点，则该树一共有（D）层（根结点所在层为第一层）。A.6 B.4 C.3 D.5 串 函数 S tr C m p （d”，“D”）的 值 为（B ）。A.0 B.1 C.-1 D.31 8.以下说法正确的是（D）。A.连通图G 的生成树中不一定包含G 的所有顶点B.连通图G 的生成树中 定要包含G 的所有边C.连通图G 的生成树一定是唯一的D.连通图G 一定存在生成树 在 一 棵二叉树中，若编号为i 的结点存在右孩子，则右孩子的顺序编号为（DA.2 i B.2 i-l C.2 i+2 D.2 i+l2 0.对二叉排序树进行（C）遍历，遍历所得到的序列是有序序列。A.按层次 B.前序 C.中序 D.后序 设 一棵有n 个结点采用链式存储的二叉树，则该树共有（D ）个指针域为空A.2 n B.2 n+l C.2 n+2 D.n+122.以下排序算法中，在一趟排序过程中，除了其它相关操作外，只进行一次元素间的交换的算法是（AA.直接选择 B.冒泡 C.直接插入 D.折半插入23.已知如图1 所示的一个图，若从顶点a 出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（B）。A.a b c e d f B.a b c e f d C.a e b c f d D.a c f d e b24.对长度为n 的线性表进行h 找，在等概率情况下，平均查找长度为（B）oA.n B.（n+1）/2 C.2n D.n-1在有序表 1,3,8,13,33,42,46,63,76,78,86,97,100 中，用折半查找值 86时，经（D ）次比较后查找成功。A.6 B.3 C.8 D.426.如 图 若 从 顶 点 a 出发按深度优先搜索法进行遍历，则可能得到的顶点序列为(A)。A.acfgedbB.aedcbgfC.acfebdgD.aecbdgf有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（A ）。A.29/10 B.31/10 C.26/10 D.29/928.一棵哈夫曼树有12个叶子结点（终端结点），该树总共有（C）个结点。A.22 B.21 C.23 D.24 一 组 记录的关键字序列为（37,70,47,29,31,85）,利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（A ）A.31,29,37,47,70,85 B.29,31,37,47,70,85C.31,29,37,70,47,85 D.31,29,37,85,47,703 0.队列的删除操作在（B）进行。A.队头 B.队尾 C.队头或队尾 D.在任意指定位置二、填空题得分评卷人1.把数据存储到计算机中，并具体体现数据之间的逻辑结构称为？W 结构。2.设有一个不带头结点的单向循环链表，结点的指针域为n ex t,指针p 指向尾结点，现要使p 指向第一个结点，可 用 语 句。3.结构中的数据元素存在一对一的关系称为顺序结构。4.要在一个带头结点的单向循环链表中删除头结点，得到一个新的不带头结点的单向循环链表，若结点的指针域为n ex t,头指针为head,尾指针为p,则可执行head=head-next;p-next=head 在 双向链表中，每个结点有两个指针域，一个指向结点的直接前驱，另一个指向结点的直接后驱。6.设有一个非空的链栈，栈顶指针为h s,要进行出栈操作，用 x 保存出栈结点的值，栈结点的指针域为n e x t,数据域为d a ta,则可执行x=hsndata；和hs=hs-next；7.设有一个头指针为head的单向链表，p 指向表中某一个结点，且有p next=NULL,通过 操 作 p-next=head,就可使该单向链表构造成单向循环链表。8.循 环 队 列 的 最 大 存 储 空 间 为 MaxSize,队 头 指 针 为 f,队 尾 指 针 为 r,当（q-r+1）%MaxSize=q-f 时表明队列已满。从 一 个栈顶指针为h 的链栈中删除一个结点时，用 X 保存被删结点的值，可执行x=h-data;和 h=h-next（结点的指针域为 next）1 0.程序段 int count=0;char*s=ABCD;while（*s!=0）s+;count+;执行后count=4 两 个串相等的充分必要条件是串长度相等且对应位置的字符相等1 2.一棵二叉树总结点数为1 1,叶结点数为5,该树有_4 个双分支结点2.个单分支结点。对 二叉树的遍历可分为、中序、后序层次四种不同的遍历次序。1 4.设一棵完全二叉树，其最高层上最右边的叶结点的编号为偶数，该叶节点的双亲结点的编号为9,该完全二叉树一共有18个结点。棵 有 n 个叶结点的二叉树，其每一个非叶结点的度数都为2,则该树共有_2n-l一 个结点。16.双向循环链表中，p 指向表中某结点，则通过p 可以访问到p 所指结点的直接后继结点和直接前驱结点，这种说法是 正确 的（回答正确或不正确）。17.一棵有14个结点的完全二叉树，则它的最高层上有_ 7 个结点。18.栈和队列的操作特点分别是.先进后出（后进先出）和 先进先出（后进后出）。19.如图2 所示的二叉树，其先序遍历序列为 abdgcefhi。20.折半查找只适用于顺序存储结构 存储的有序表。哈 希函数是记录关键字值与该记录一存储地址 之间所构造的对应关系。22.深度为k 的二叉树最多有（2 4）-1 结点。23.二叉树排序中任一棵子树都是二叉排序树，这种说法是正确 的。（回答正确或不正确）串的两种最基本的存储方式是顺序存储 和 链式存储_ _ _ _ _ _ _ _三、综合题得 分评卷人1.设一组记录的关键字序列为（4 9,8 3,5 9,4 1,4 3,4 7）,采用堆排序算法完成以下操作：（要求小根堆，并画出中间过程）（1）以二叉树描述6 个元素的初始堆（2）以二叉树描述逐次取走堆顶元素后，经调整得到的5 个元素、4个元素的堆2.设有一个不带头结点的单向链表，头指针为h e a d,结点类型为N O D E,每个结点包含一个数据域d a t a 和一个指针域n e x t,该链表有两个结点，p 指向第二个结点（尾结点），按以下要求写出相应语句（不要求完整程序，（1）（2）、（3）、（4）是一个连续的过程）。（1）新 开 辟 个结点，使指针s 指向该结点，结点的数据成员d a t a 赋值为1（2）把该结点插入链表的尾部，释放指针s 的指向（3）删除链表的第一个结点（4）已知p i 指向另一个新结点，把它插入到p 所指结点和尾结点之间3.设有序表为（1 3,1 9,2 5,3 6,4 8,5 1,6 3,8 4,9 1,1 1 6,1 3 5,2 0 0）,元素的下标依次为1,2,2。（1）说出有哪几个元素需要经过4次元素间的比较才能成功查到（2）画出对上述有序表进行折半查找所对应的判定树（树结点用下标表示）（3）设查找元素5,需要进行多少次元素间的比较才能确定不能查到4.（1）设有序列 1 0,1 2,1 5,1 9 ,2 2 ,2 5,1 0 0,1 3 0,1 5 0,2 0 0 画出对上述序列进行折半查找的判定树（以序列中的元素作为树的结点）（2）为了成功查找到1 0 0 需要进行多少次元素间的比较？为了查找9,经过多少次元素间的比较可知道查找失败？5.（1）对给定数列 7,1 6,4,8,2 0,9,6,1 8,5 ,依次取数列中的数据，构造一棵二叉排序树。（2 ）对一个给定的查找值，简述针对二叉排序树进行查找的算法步骤，在上述二叉树中查找元素2 0 共要进行多少次元素的比较？6.（1）设有查找表 5,1 4,2,6,1 8,7,4,1 6,3 ,依次取表中数据，构造一棵二叉排序树。（2）说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。四、程序填空题1.以下冒泡法程序对存放在a l,a 2 ,，an中的序列进行排序，完成程序中的空格部分，其 中n是元素个数，要求按升序排列。void bsort(NODE a,int n)NODE temp;int i,j,flag;for(j=l;j+);flag=0;for(i=l;i ai+l,key)flag=l;temp=ai;a i=ai+l_;(4)ai+l=temp_;)if(flag=0)break;程序中f la g的功能是一(5)当某趟冒泡中没有出现交换则已排好序，结束循环2.以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和rig h t,数据 域data为字符型，BT指向根结点)。void Preorder(struct BTreeNode*BT)if(BT!=NULL)()primf(%c”,BT.da t a);(2)Preorder(BTleft);(3)P r e o r d e K B r A r i g h t);)3.设 线 性 表 为(6,10,16,4),以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。#define NULL 0void main()NODE a,b,c,d,*head,*p;a.data=6;b.data=10;c.data=16;d.data=4;/*d 是尾结点*/head=(1)&a;a.next=&b;b.next=&c;c.next=&d;dn e x t=NULL;/*以上结束建表过程*/p=head;/*p为工作指针，准备输出链表*/doprintf(%dn”,(3)p-d a t a);(4)p=p-n e x t;while(5)p!=NULL);4.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和 rig h t,数据域data为字符型，BT指向根结点)。void Inorder(struct BTreeNode*BT)if(BT!=NULL)(1)I n o r d e r(BT l e f t);(2)printf(c”,BT-dat a);(3)InordeK BFr i ght);数据结构（本）期末综合练习一参考答案一、单项选择题1.D 2.C 3.D 4.C 5.D 6.A 7.A 8.A 9.D 1 0.D 1 1.C 1 2.A1 3.D 1 4.A 1 5.C 1 6.D 1 7.B 1 8.D 1 9.D 2 0.C 2 1.D 2 2.A 2 3.B2 4、B 2 5.D 2 6.A 2 7.A 2 8.C 2 9.A 3 0.A二、填空题1.物理(存储)3.线性5.结点的直接后继结点的直接前驱7.p-n e x t=h e a d;9.h=h-n e x t;1 1.串长度相等且对应位置的字符相等1 3.先序、中序、后序、层次1 5.2 n-l1 7.71 9.a b d g c e f h i2 1.存储地址2 3.正确2.p=p-n e x t;4.p-n e x t=h e a d；6.h s-d a t a;h s-n e x t;8.(r+1)%M a x S i z e=f1 0.1 2.1 4.1 6.1 8.2 0.2 2.2 4.三、44；21 8正确先进后出（后进先出）顺序存储结构先 进 先 出（后进后出）2k-l顺序存储综合题链式存储图 3图 42.(1)s=(NODE*)malloc(sizeof(NODE);s-data=1;(2)p-next=s;s-next=NULL；free(s)(3)head=head-next；(4)pi-next=p-next；p-next=pi；3.(1)19,48,84,116,200(2)图 5(3)3 次(2)4次；3次图 6(2)先将给定值与根结点比较，若相等则查找成功，否则若小于根结点则在左子树中继续查找，大于根结点在右子树中查找，查找2 0 共进行3 次比较。6.3716图6(2)中序遍历中序 2,3,4,5,6,7,1 4,1 6,1 8四、程序填空题L(1)j =n-l(2)i d a t a)(2)P r e o r d e r(BT-1 e f t)(3)P r e o r d e r(BT-r i g h t)J.(1)&a(2)d-n e x t=N U L L(3)p-d a t a(4)pz:p-n e x t(5)p!=N U L L(1)I n o r d e r(B T-l e f t)(2)p r i n t f (%c”,B T-d a t a)(3)I n o r d e r(B T-r i g h t)数据结构（本）期末综合练习二一、单项选择题1.数据元素是数据的基本单位，它（C）。A.只能有一个数据项组成 B.至少有二个数据项组成C.可以是一个数据项也可以由若干个数据项组成D.至少有一个数据项为指针类型2.一种逻辑结构（A）存储结构。A.可以有不同的 B.只能有唯一的C.的数据元素在计算机中的表示称为 D.的数据元素之间的关系称为3.线性表的顺序结构中，（C）。A.逻辑上相邻的元素在物理位置上不一定相邻B.数据元素是不能随机访问的C.逻辑上相邻的元素在物理位置上也相邻D.进行数据元素的插入、删除效率较高4.以下说法中不正确的是（B）oA.双向循环链表中每个结点需要包含两个指针域B.已知单向链表中任一结点的指针就能访问到链表中每个结点C.顺序存储的线性链表是可以随机访问的D.单向循环链表中尾结点的指针域中存放的是头指针5.以下表中可以随机访问的是（D ）。A.单向链表 B.双向链表C.单向循环链表 D.顺序表6.双向循环链表结点的数据类型为：struct node int data;struct node*next;/*指向直接后继*/struct node*prior;；设 p 指向表中某一结点，要显示p 所指结点的直接前驱结点的数据元素，可用操作（B）。A.printf（next-data）;B.printf（%d,p prior data）;C.printf（u%d,p-prior-next）;D.printf（4data）;7.设顺序存储的线性表长度为n,对于删除操作，设删除位置是等概率的，则删除一个元素平均移动元素的次数为（A）。A.（n+l）/2 B.n C.2n D.n-i8.一个栈的进栈序列是e fg h,则栈的不可能的出栈序列是（D）（进出栈操作可以交替进行）。A.hgfe B.gfeh C.fgeh D.ehfg9.设 top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成，设用x 接收栈顶元素，则出栈操作为（A）。A.x=top-data;top=top-next;C.x=top-next;top=top-data;B.top=top-next;x=top-data;D.top-next=top;x=top-data;1 0.设top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成,设用x 接收栈顶元素，则取栈顶元素的操作为（CA.top-data=x;C.x=top-data;B.top=top-next;D.x=top-data;top=top-next;1 1.以下说法正确的是（C）。A.队列是后进先出 B.栈的特点是后进后出C.栈的删除和插入操作都只能在栈顶进行D.队列的删除和插入操作都只能在队头进行 以 下说法不正确的是（C）。A.栈的特点是后进先出 B.队列的特点是先进先出C.栈的删除操作在栈底进行，插入操作在栈顶进行D.队列的插入操作在队尾进行，删除操作在队头进行13.串函数 StrCmp（abA,aba）的 值 为（D）A.1 B.0 C.“abAaba”D.-114.char*p;p=StrCat（ABDJABC）；Printf（4 n e x t=h e a d。4.设有一个单向循环链表，结点的指针域为next,头指针为head,指针p 指向表中某结点，若逻辑表达式pnext=head 的结果为真，则 p 所指结点为尾结点。5.设有一个单向循环链表，头指针为head,链表中结点的指针域为next,p 指向尾结点的 直 接 前 驱 结 点，若 要 删 除 尾 结 点，得 到 一 个 新 的 单 向 循 环 链 表，可执行操作一p-next=head。设 有一个链栈，栈顶指针为h s,现有一个s 所指向的结点要入栈，则可执行操作s-n e x t=h s;hs=s。7.在一个链队中，f 和 r 分别为队头和队尾指针，队结点的指针域为n e x t,则插入一个s 所指结点的操作为 r-ne xt=s；r=s；8.在一个链队中，f 和 r 分别为队头和队尾指针，队结点的指针域为next,s 指向一个要入队的结点，则入队操作为 r-next=s:=s:9.循环队列的队头指针为f,队尾指针为r,当 r=f 时表明队列为空。10.循环队列的最大存储空间为MaxSize=6,采用少用一个元素空间以有效地判断栈空或栈满，若 队 头 指 针 front=4,当 队 尾 指 针 rean=3 时队满,队列中共有5 个元素。11.A 在存储时占_ 1 _个字节。“A”在存储时占 2 个字节。12.程序段 char*s=,aBcD,;n=0;while（*s!=,0,）if（*s=a&*s=z）n+;s+;执行后n=213.一棵二叉树没有单分支结点，有 6 个叶结点，则该树总共有11一 个 结 点。14.一棵二叉树中顺序编号为5 的 结 点（树中各结点的编号与等深度的完全二叉中对应位置上结点的编号相同），若它存在左孩子，则左孩子的编号为-10。15.按照二叉树的递归定义，对二叉树遍历的常用算法有 先序、中序、后序 三种。根 据搜索方法的不同，图 的 遍 历 有 深度优先 广度优先一两种方法。17.把数据存储到计算机中.并具体体现数据之间的逻辑结构称为物 理（存储）18.结构中的数据元素存在多对多的关系称为图 状（网 状 状 结构。如 图 2 所示的二叉树，其后序遍历序列为 gdbeihfca o图2 一 棵 有n个叶结点的二叉树，其每一个非叶结点的度数都为2,则该树共有2 n-l 个结点02 1.二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这 种 说 法 是 错误 的。(回答正确或不正确)串 的两种最基本的存储方式分别是一顺序存储 和 一链式存储 o 根 据搜索方法的不同，图 的 遍 历 有.深度优先、广度优先 两种方法 按 某关键字对记录序列排序，若关键字关键字相等 的记录在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。三、综合题1.(1)已知某二叉树的后序遍历序列是d e b c a,中序遍历序列是d b e a c,试画出该二叉树(2)若上述二叉树的各个结点的字符分别代表不同的整数(其中没有相等的)，并恰好使该树成为一棵二叉排序树，试给出a、b、c、d、e的大小关系(3)给出该树的前序遍历序列2.(1)已知某二叉树的先序遍历序列是a e c d b,中序遍历序列是e a d c b,试画出该二叉树(2)给出上述二叉树的后序遍历序列(3)若上述二叉树的各个结点的字符分别是1,2,3,4,5,并恰好使该树成为一棵二叉排序树，试问a、b、c、d、e的值各为多少？3.(1)设有一个整数序列 4 0,2 8,6,7 2,1 0 0,3,5 4 依次取出序列中的数，构造一棵二叉排序树(2)对上述二叉排序树，在等概率条件下，求成功查找的平均查找长度4.(1)给定数列 8,1 7,5,9,2 1,1 0,7,1 9,6),依次取序列中的数构造一棵二叉排序树(2)对上述二叉树给出中序遍历得到的序列5.(1)利用筛选过程把序列 4 2,8 2,6 7,1 0 2,1 6,32,5 7,5 2 建成堆(小根堆)，画出相应的完全二叉树(不要求中间过程)(2)写出对上述堆对应的完全二叉树进行中序遍历得到的序列6.(1)以给定权重值1,2,1 2,1 3,2 0,2 5为叶结点，建立一棵哈夫曼树(2)若哈夫曼树有n 个非叶子结点，则树中共有多少结点。对给定的一组权重值建立的棵哈夫曼树是否一定唯一四、程序填空题1.以下函数在a0到中，用折半查找算法查找关键字等于既勺记录，查找成功返回该记录的下标，失败时返回-1,完成程序中的空格typedef struct int key;(NODE;int Binary_Search(NODE a,int n,int k)(int low,mid,high;low=0;high=n-l;wh i 1 e(_(1)_ lo w =h ig h)(mid=(low+high)/2;if(amid.key-k)return _(2)_ mi d;else i f(_(3)_ am id.k ey key!=_(2)_ k)if(kkey)一(3)_ p=p-left_;e l se _ _ _(4)_ p=p-rig h t;i f(p=N U L L)b re a k;)R e t u rn(_ _ _(5)_ p);)3.以下函数为链队列的入队操作，x 为要入队的结点的数据域的值，front、rear分别是链队列的队头、队尾指针struct node ElemType data;struct node*next;)；struct node*front,*rear;v oi d I nQ u e u e(E l e m T ype x)(st ru c t nod e *p;p=(st ru c t nod e*)_ _ _(1)_ malloc(sizeof(struct node)_;p-d a t a=x;p-ne x t=N U L L;_(2)re a r-n e x t=p;rear=_(3)_ p;)4.以下函数为链队列的出队 操 作(链队列带有头结点)，出队结点的数据域的值由x 返回，front、rear分别是链队列的队头、队尾指针struct node ElemType data;struct node*next;；struct node*front,*rear;E l e m T ype O u t Qu e u e ()(Ele m T y p e x;i f(_(1)_front=rear_)p r i n t f(队列下溢错误！n)；e x i t(1);)e ls e s t r u c t n o d e *p=f r o n t-n e x t;x=p-d a t a;f r o n t-n e x t=_ _ _(2)_ p-next_;i f(p-n e x t=NU LL)r e a r=f r o n t;f r e e(p);一(3)_ return(x)数据结构（本）期末综合练习二参考答案一、单项选择题1.C 2.A3.C 4.B5.D 6.B7.A 8.D9.A1 0.C1 1.C1 2.C1 3.D1 4.B1 5.A 1 6.B 1 7,A 1 8.D 1 9.D 2 0.A2 1.A2 2.B2 3.A2 4.A 2 5.B 2 6.A 2 7.D2 8.B2 9.D 3 0.A二、填空题1.集合；线性；树形；图状2.图状3.p-n e x t=h e a d;4.p-n e x t=h e a d;5,p-n e x t=h e a d；6.h s=s；7.r-n e x t=s8.r-n e x t=s；r=s；9.r=f1 0.3；51 1.1；21 2.21 3.1 11 4.1 01 5.先序；中序；后序1 6.深度优先；广度优先1 7.物 理（存储）1 8.图 状（网状）1 9.g d b e i h f c a2 0.2 n-l2 1.错误2 2.顺序存储链式存储2 3.深度优先广度优先2 4.关键字相等的记录三、综合应用题1.（1）(2)d b e a c(2)edbca(3)e=1 ,a=2,d=3,c=4,b=5(2)5,6,7,8,9,10,17,18,19,21初始树堆(2)102,52,42,82,16,67,32,57四、程序填空题（每空2分，共16分）1.(1)(2)(3)(4)(5)low=highmidamid.keyleft(4)p=p-right(5)p3.(1)malloc(sizeof(struct node)(2)rear-next=p(3)p4.(1)front=rear(2)p-next(3)return(x)数据结构(本)期末综合练习三一、单项选择题1.(B)是性质相同的数据元素的集合，是数据的子集。A、数据元素 B.数据对象 C.数据结构 D.数据项2.从 n 个数中选取最大元素(C)。A.基本操作是数据元素间的交换 B.算法的时间复杂度是OS?)C.算法的时间复杂度是0(n)D.需要进行(n+1)次数据元素间的比较3.设链表中的结点是NODE类型的结构体变量，且有NODE*p；为了申请一个新结点，并由p 指向该结点，可用以下语句(A)。A.p=(NODE*)malloc(sizeof(NODE);B.p=(*NODE)malloc(sizeof(NODE);C.p=(NODE)malloc(sizeof(p);D.p=(NODE*)malloc(sizeof(p);4.设head为非空的单向循环链表头指针,p 指向链表的尾结点，则满足逻辑表达式(D)的值为真。A.p-next=NULL B.p=NULLC.p-next=head D.p-next=head5.设顺序存储的线性长度为n,要 族 i 个元素之前插入一个新元素，按课本的算法当1=(D)时，移动元素次数为2A.n/2 B.n C.1 D.n-16.设顺序存储的线性表长度为n,要删除第i 个元素，按课本的算法，当 i=(C)时，移动元素的次数为3A.3 B.n/2 C.n-3 D.37.一个栈的进栈序列是1,2,3,4,则栈的不可能的出栈序列是(B)(进出栈操作可.以交替进行)A.3,2,4,1 B.1,4,2,3C.4,3,2,1 D.3,2,1,48.一个栈的进栈序列是a,b,c,d,则栈的不可能的出栈序列是(A)。A.adbc B.beadC.cbad D.deba9.设有一个带头结点的链队列，队列中每个结点由一个数据域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.rea=p;rear-next=p;10.设有一个带头结点的链队列，队列中每个结点由一个数据域data和指针域next组成，front和 rear分别为链队列的头指针和尾指针，要执行出队操作，用 x 保存出队元素的值，p 为指向结点类型的指针，可执行如下操作：p=front-next;x=p-data;然后指行(B)A.front=p-next;B.front-next=p-next;C.front=p;D.front-next=p;11.以下说法不正确的是（C）oA.顺序栈中，栈满时再进行进栈操作称为“上溢”B.顺序栈中，栈空时再作出栈栈操作称为“下溢”C.顺序队列中，当尾指针已经超越队列存储空间的上界，则一定是队列已满D.顺序队列中，队列的头指针和尾指针均超越队列存储空间的上界，则队列已空13.设有一个20阶的对称矩阵A,采用压缩存储方式，将其下三角部分以行序为主序存储到一维数组中（矩 阵 A 的第一个元素为a”，数组b 的下标从1开始），则矩阵元素aa5在一维数组b 中的下标是（D）A.30 B.28 C.40 D.3314.设有一个10阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b 中。（矩阵A 的第一个元素为a s，数组b 的下标从1开始），则矩阵元素 a5.3对应一维数组b 的数组元素是（C）。A.b18 B.b8 C.b13 D.b1015.深度为5 的完全二叉树第5 层上有4 个结点，该树一共有（D）个结点。A.28 B.30 C.31 D.1916.深度为5 的完全二叉树共有20个结点，则第5 层上有（C）个结点（根所在结点为第一层）。A.3 B.8 C.5 D.617.已知一个图的所有顶点的度数之和为m,则 m 一定不可能是（D）。A.4 B.8 C.12 D.918.已知一个图的所有顶点的度数之和为m,且 m 是以下4 中情况之一，则 m 只可能是（D）A.9 B.7 C.15 D.819.以下说法正确的是（D）。A.连通图G 的生成树中可以包含回路B.连通图G 的生成树可以是不连通的C.连通图G 的生成树一定是唯一的D.连通图G 的生成树一定是连通而不包含回路的20.线性表只要以（C）方式存储就能进行折半查找。A.链接 B.顺序 C.关键字有序的顺序 D.二叉树21.对 n个元素进行冒泡排序，通常要进行n-1趟冒泡，在第j 趟冒泡中共要进行（C）次元素间的比较。A.j B.j-1 C.n-j22.对 n 个元素进行冒泡排序若某趟冒泡中只进行了（C表明序列已经排好序。A.1 B.2 C.0D.n-j-1）次元素间的交换，则D.n-123.在排序过程中，可以有效地减少一趟排序过程中元素间的比较次数的算法是（D）。A.冒泡 B.选择 C.直接插入 D.折半插入24.在对一组元素（64,48,106,33,25,82,70,55,93）进行直接插入排序时，当进行到要把第7 个 元 素 7 0 插入到已经排好序的子表时，为找到插入位置，需进行（C）次元素间的比较（指由小到大排序）。A.6 B.2 C.3 D.425.如图若从顶点a 出发按深度优先搜索法进行遍历，则可能得到的顶点序列为（B）。A.aebcfdB.abedcfC.acebdfD.acfbde26.如图，若 从 顶 点 a 山发按广度优先搜索法进行遍历，则可能得到的顶点序列为(B)。A.acebdgfB.abecdgfC.acfedgbD.abecfdg27.一棵哈夫曼树有n 个叶子结点（终端结点），该树总共有（B）个结点。A.2n-2 B.2n-l C.2n D.2n+228.一棵哈夫曼树有10个非叶子结点（非终端结点），该树总共有（A）个结点。A.21B.20C.22D.19.数 据 的（A）结构与所使用的计算机无关。A.逻辑B.物理C.存储D.逻辑与存储3 0.队列的插入操作在（B）进行。A.队头B.队尾C.队头或队尾D.在任意指定位置二、填空题1.通常可以把一本含有不同章节的书的目录结构抽象成一 树形 结构。2.通常可以把某城市中各公交站点间的线路图抽象成图状 结构。3.要在一个单向链表中p 所指向的结点之后插入一个s 所指向的新结点，若链表中结点的指针域为n e x t,可执行_ _ _ s-next=p-next 和 p-next=s;的操作。4.要在一个单向链表中删除p 所指向的结点，已知q 指向 p 所指结点的直接前驱结点，若链表中结点的指针域为n e x t,则可执行_ q-next=p-next。5.设有一个非空的链栈，栈顶指针为h s,要进行出栈操作，用 x 保存出栈结点的值，栈结点的指针域为n e x t,则可执行x=hs-data;hs=hs-next。设 有一个链栈，栈顶指针为h s,现有一个s 所指向的结点要入栈，则可执行操作_ s-next=hs_和 hs=s；7.在一个不带头结点的非空链队中，f 和 r 分别为队头和队尾指针，队结点的数据域为data,指针域为next,若要进行出队操作，并用变量x 存放出队元素的数据值，则相关操作为x=f-d a t a;f=f-n e x t。8.在一个不带头结点的非空链队中，f 和 r 分别为队头和队尾指针，队结点的数据域为data,指针域为next,若要进行出队操作，并用变量x 存放出队元素的数据值，则相关操作为x=f-data:f=f-next:。9.循环队列的最大存储空间为MaxSize=8,采用少用一个元素空间以有效的判断栈空或栈满，若队头指针front=4,则当队尾指针r e a r=4 时，队列为空，当 rear=_2_时，队列有6 个元素。1 0,顺序存储字符串“ABCD”需要占用一 5 个字节。11.稀疏矩阵存储时，采 用 一 个 由.行 号、列号、非 零 元.3 部分信息组成的三元组唯一确定矩阵中的一个非零元素。12.一棵二叉树叶结点（终端结点）数为5,单分支结点数为2,该树共有一 11_个结点。13.一棵二叉树顺序编号为6 的 结 点（树中各结点的编号与等深度的完全