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

数据结构（本）期末综合练习2009年6月为了帮助同学们进行期末复习，特拟定以下三套期末综合练习题，望同学们逐一认真完成。数据结构（本）期末综合练习一一、单项选择题1.针对线性表，在存储后如果最常用的操作是取第i 个结点及其前驱，则 采 用（）存储方式最节省时间。A.单链表 B.双链表C.单循环链表 D.顺序表2 .线性表采用链式存储时，其地址A.一定是不连续的C.可以连续也可以不连续B.必须是连续的D.部分地址必须是连续的3 .数据结构中，与所使用的计算机无关的是数据的（）结构。A.物理 B.存储 C.逻辑与物理 D.逻辑4 .带头结点的单向链表的头指针为h e a d,该链表为空的判定条件是（）的值为真。A.h e a d =N UL LB.h e a d-n e x t=h e a dC.h e a d-n e x t=N UL L D.h e a d =h e a d-n e x t5 .以下特征中，（）不是算法的特性。A.有穷性 B.确定性 C.可行性1）.有 0 个或多个输出6 .设顺序存储的线性表长度为n,对于插入操作，设插入位置是等概率的，则插入一个元素平均移动元素的次数为（）0A.n/2 B.n C.n-1 D.n-i+17 .设有个长度为n的顺序表，要在第i 个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（A.n-i+1 B.n-i8.一个栈的进栈序列是5,6,7,作可以交替进行）A.5,8,6,7 B.C.1,6,5,8 D.）。C.n-i-1 D.i8,则栈的不可能的出栈序列是（7,6,8,58,7,6,5）（进出栈操9 .栈的插入删除操作在（）进行。A.栈底 B.任意位置 C.指定位置 D.栈顶10.栈和队列的相同点是（）。A.都是后进先出 B.都是后进后出C.逻辑结构与线性表不同D.逻辑结构与线性表相同，都是操作规则受到限制的线性表11.以下说法正确的是（）。A.栈的特点是先进先出，队列的特点是先进后出B.栈和队列的特点都是先进后出C.栈的特点是先进后出，队列的特点是先进先出D.栈和队列的特点都是先进先出12.在 C语言中，利用数组a 存放字符串“H e l l。，以下语句中正确的是（）。A.c h a r a 10J=H e l l o”;B.c h a r a l l O J;a=H e l l o”;C.c h a r a 10=lH e l l o ;D.c h a r a 10=H ,e ,T,T,o ;13.元 素 2,4,6,8按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。A.8,6,4,2 B.2,4,6,8C.4,2,8,6 D.8,6,2,414 .设有一个15 阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。（矩 阵 A的第一个元素为a u，数组b的下标从1 开始），则数组元素 b 13 对应A的矩阵元素是（）。A.a5,3 B.防4 C.a7.2 D.a6,815 .设有一个15 阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到维数组B中（数组下标从1 开始），则矩阵中元素a%6在 维数组B中的下标 是（）。A.42 B.13 C.27 D.3216.一棵完全二叉树共有30个结点，则该树一共有（）层（根结点所在层为第一层）。A.6 B.4 C.3 D.517.串函数 S t r C m p （d”，“D”）的 值 为（）。A.0 B.1 C.-1 D.318.以下说法正确的是（）。A.连通图G的生成树中不一定包含G的所有顶点B.连通图G的生成树中一定要包含G的所有边C.连通图G的生成树一定是唯一的D.连通图G一定存在生成树19 .在一棵二叉树中，若编号为i 的结点存在右孩子，则右孩子的顺序编号为（）。A.2i B.2i-l C.2i+2 D.2i+l20.对二叉排序树进行（）遍历，遍历所得到的序列是有序序列。A.按层次 B.前序 C.中序 D.后序21.设一棵有n个结点采用链式存储的二叉树，则该树共有（）个指针域为空。A.2n B.2n+l C.2n+2 D.n+122.以下排序算法中，在一趟排序过程中，除了其它相关操作外，只进行一次元素间的交换的算法是（）。A.直接选择 B.冒泡 C.直接插入 D.折半插入23.已知如图1 所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。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 b图 124.对长度为n的线性表进行顺序查找，在等概率情况下，平均查找长度为（）。A.n B.（n+1）/2 C.2n D.n-125.在有序表 L 3,8,13,33,42,46,63,76,78,值 86时，经（）次比较后查找成功。86,9 7,100 中,用折半查找A.6 B.3 C.8 D.426.如图若从顶点a出发按深度优先搜索法进行遍历，则可能得到的顶点序列为（)oA.a c f g e d bB.a e d c b g fC.a c f e b d gD.a e c b d g f27.有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况F查找成功的平均比较次数为（）。A.29/10 B.31/10 C.26/10 D.29/928.一棵哈夫曼树有12个叶子结点（终端结点），该树总共有（）个结点。A.22 B.21 C.23 D.2429 .一组记录的关键字序列为（37,70,47,29,31,85）,利用快速排序,以第一个关键字为分割元素，经过一次划分后结果为（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,7030.队列的删除操作在（）进行。A.队头 B.队尾 C.队头或队尾 D.在任意指定位置得分评卷人二、填空题1.把数据存储到计算机中，并具体体现数据之间的逻辑结构称为 结构。2.设有一个不带头结点的单向循环链表，结点的指针域为n e x t,指针p指向尾结点，现要使p指向第一个结点，可用语句 o3.结构中的数据元素存在一对一的关系称为 结构。4.要在一个带头结点的单向循环链表中删除头结点，得到一个新的不带头结点的单向循环链表，若结点的指针域为n e x t,头指针为h e a d,尾指针为p,则可执行h e a d=h e a d-next;o5.在双向链表中，每个结点有两个指针域，一个指向,另一个指向6.设有个非空的链栈，栈顶指针为hs,要进行出栈操作，用 x 保存出栈结点的值,栈结点的指针域为next,数据域为d a ta,则可执行x=；和hs=；7.设有一个头指针为hea d的单向链表，p指向表中某一个结点,且有p-next=N ULL,通过操作,就可使该单向链表构造成单向循环链表。8 .循环队列的最大存储空间为M a xSize,队头指针为f,队尾指针为r,当_ _ _ _ _ _ _ _ _ _时表明队列已满。9.从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行x=h-d a ta;和。（结点的指针域为next）1 0 .程序段 int c ount=0;c ha r*s=A B C D ;whil e（*s!=,0,）s+;c ount+;执行后c ount=_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _1 1.两个串相等的充分必要条件是。1 2 .一棵二叉树总结点数为I I,叶结点数为5,幽 有 个双分支结点，个单分支结点。1 3.对 二 叉 树 的 遍 历 可 分 为、四种不同的遍历次序。1 4.设一棵完全二叉树，其最高层上最右边的叶结点的编号为偶数，该叶节点的双亲结点的编号为9,该完全二叉树一共有 个结点。1 5 .一棵有n个叶结点的二叉树，其每一个非叶结点的度数都为2,则该树共有个结点。1 6.双向循环链表中，p指向表中某结点，则通过p可以访问到p所指结点的直接后继结点和直接前驱结点，这种说法是 的（回答正确或不正确）。1 7 .一棵有1 4个结点的完全二叉树，则它的最高层上有 个结点。1 8 .栈和队列的操作特点分别是 和 o1 9.如图2所示的二叉树，其先序遍历序列为 o图22 0 .折半查找只适用于 存储的有序表。2 1 .哈希函数是记录关键字值与该记录 之间所构造的对应关系。2 2 .深度为k的二叉树最多有 结点。2 3.二叉树排序中任一棵子树都是二叉排序树，这种说法是 的。（回答正确或不正确）2 4.串的两种最基本的存储方式是 和三、综合题得 分评卷人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 ta 和一个指针域ne x t,该链表有两个结点，p 指向第二个结点（尾结点），按以下要求写出相应语句（不要求完整程序，（1）、（2）、（3）、（4）是一个连续的过程）。（1）新开辟一个结点，使指针s 指向该结点，结点的数据成员d a ta 赋值为1（2）把该结点插入链表的尾部，释放指针s 的指向（3）删除链表的第一个结点（4）已知pi 指向另一个新结点，把它插入到p 所指结点和尾结点之间3.设有序表为（1 3,1 9,25,3 6,48,51,6 3,84,9 1,1 1 6,1 3 5,20 0）,元素的下标依次为1,2,1 2。（1）说出有哪几个元素需要经过4 次元素间的比较才能成功查到（2）画出对上述有序表进行折半查找所对应的判定树（树结点用下标表示）（3）设查找元素5,需要进行多少次元素间的比较才能确定不能查到4.（1）设有序列 1 0,1 2,1 5,1 9,22,25,1 0 0,1 3 0,1 50,20 0 画出对上述序列进行折半查找的判定树（以序列中的元素作为树的结点）（2）为了成功查找到1 0 0 需要进行多少次元素间的比较？为了查找9,经过多少次元素间的比较可知道查找失败？5.（I）对给定数列 7 6,4,8,20,9,6,1 8,5,依次取数列中的数据，构造一棵二叉排序树。（2）对一个给定的查找值，简述针对二叉排序树进行查找的算法步骤，在上述二叉树中查找元素20 共要进行多少次元素的比较？6.(1)设有查找表 5,1 4,2,6,1 8,7,4,1 6,3 ,依次取表中数据，构造棵二叉排序树。(2)说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。四、程序填空题1.以下冒泡法程序对存放在a l,a 2 L，a n 中的序列进行排序，完成程序中的空格部分，其中n 是元素个数，要求按升序排列。v oi d b s or t(N O D E a ,i nt n)N O D E te mp;i nt i,j,fla g;for(.j-l;(1);j+);fla g=0;for (i=l;(2);i+)i f(a i .k e y a i+l,k e y)fla g=l;te mp=a i ;(3);(4);i f(fla g=0)b r e a k;)程序中fla g 的功能是(5)_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _2.以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为le ft和 r i g h t,数据域d a ta 为字符型，BT指向根结点)。v oi d P r e or d e r (s tr u c t B T r e e N od e *B T)i f(B T!=N U LL)_ _ _ _ _ _ _ _ _ _ _ _ _ _ _；2);(3);)3 .设线性表为(6,1 0,1 6,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.next=&b;b.next=&c;c.next=&d;(2);/*以上结束建表过程*/p=head;/*p为工作指针，准备输出链表*/doDrintf(dn”,(3):(4)_;while(5):4.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和 rig h t,数据域data为字符型，BT指向根结点)。void Inorder(struct BTreeNode*BT)if(BT!=NULL)_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _；_I2)_:(3);)答案一、单项选择题1.I）2.C 3.D 4.C 5.I）6.A 7.A 8.A 9.D 10.D 11.C 12.A13.D 14.A 15.C 16.D 17.B 18.D 19.D 20.C 21.D 22.A 23.B24、B 25.D 26.A 27.A 28.C 29.A 3 0.A二、填空题1.物 理（存储）3.线性5.结点的直接后继结点的直接前驱7.p-n e x t=h e ad;9.h=h-n e x t;11.串长度相等且对应位置的字符相等13.先序、中序、后序、层次15.2n-l17.719.abd g c e f h i2 1.存储地址2 3.正确2.p=p-n e x t;4.p-n e x t=h e ad；6.h s-d at a;h s-n e x t;8.（r+1）%M ax Si z e=f10.412.4；214.1816.正确18.先进后出（后进先出）先 进 先 出（后进后出）20.顺序存储结构22.2k-l24 .顺 序 存 储 链 式 存 储三、综合题图 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)prnext=p-next；p-next=pi；3.(1)19,48,84,116,200(2)图5(3)3 次(2)4 次；3 次5.图 6(2)先将给定值与根结点比较，若相等则查找成功，否则若小于根结点则在左子树中继续查找，大于根结点在右子树中查找，查找20共进行3次比较。图 6(2)中序遍历中序 2,3,4,5,6,7,14,16,18四、程序填空题L.(1)j =n-l(2)i d at a)(2)Pr e o r d e r(B T-l e f t)(3)Pr e o r d e r(B T-r i g h t)(1)&a(2)d n e x t二N UL L(3)p-d at a(4)p=p-n e x t(5)p!=N UL L(1)In o r d e r(B T-l e f t)(2)p r i n t f(u%c,J,B T-d at a)(3)In o r d e r(B T-r i g h t)数据结构（本）期末综合练习二2009年6月一、单项选择题1.数据元素是数据的基本单位，它（A.只能有一个数据项组成 B.至少有二个数据项组成C.可以是一个数据项也可以由若干个数据项组成D.至少有一个数据项为指针类型2.一种逻辑结构（）存储结构。A.可以有不同的 B.只能有唯一的C.的数据元素在计算机中的表示称为 D.的数据元素之间的关系称为3.线性表的顺序结构中，（）。A.逻辑上相邻的元素在物理位置上不定相邻B.数据元素是不能随机访问的C.逻辑上相邻的元素在物理位置上也相邻D.进行数据元素的插入、删除效率较高4.以下说法中不正确的是（）。A.双向循环链表中每个结点需要包含两个指针域B.已知单向链表中任一结点的指针就能访问到链表中每个结点C.顺序存储的线性链表是可以随机访问的D.单向循环链表中尾结点的指针域中存放的是头指针5.以下表中可以随机访问的是（）。A.单向链表 B.双向链表C.单向循环链表 D.顺序表6.双向循环链表结点的数据类型为：struct node int data;struct node力 ext;/*指向直接后继*/struct node prior;；设 p 指向表中某一结点，要显示p 所指结点的直接前驱结点的数据元素，可用操作（）oA.printf（tt%d,p-next-data）;B.printf（44%d,p-prior-data）;C.printf（%d”,p-prior-next）;D.printf（%d”,p-data）;7.设顺序存储的线性表长度为n,对于删除操作，设删除位置是等概率的，则删除一个元素平均移动元素的次数为（）oA.（n+1 ）/2 B.n C.2n D.n-i8.一个栈的进栈序列是e fg h,则栈的不可能的出栈序列是（）（进出栈操作可以交替进行）。A.hgfe B.gfeh C.fgeh D.ehfg9.设 top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成，设用x 接收栈顶元素，则出栈操作为（）。A.x=top-data;top=top-next;B.top=top-next;x=top-data;C.x=top-next;top=top-data;D.top-next=top;x=top-data;10.设 top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成,设用x 接收栈顶元素，则取栈顶元素的操作为（）。A.top-data=x;C.x=top-data;1 1.以下说法正确的是（A.队列是后进先出B.top=top-next;D.x=top-data;top=top-next;)oB.栈的特点是后进后出C.栈的删除和插入操作都只能在栈顶进行D.队列的删除和插入操作都只能在队头进行12.以下说法不正确的是（）。A.栈的特点是后进先出 B.队列的特点是先进先出C.栈的删除操作在栈底进行，插入操作在栈顶进行D.队列的插入操作在队尾进行，删除操作在队头进行13.串函数 StrCmp（“abA”,“aba）的 值 为（）。A.1 B.0 C.“abAaba”D.-114.char*p;p=StrCat（“ABD”,“ABC）；Printf（s”,p）;的显示结果为（）。A.-1 B.ABDABC C.AB D.11 5.设有一个12阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b 中（矩 阵 A 的第一个元素为a u，数组b 的下标从1 开始），则矩阵A中第4 行的元素在数组b 中的下标i 一 定 有（）oA、7WiW10 B、C、94W14 D、6WiW916.深度为5 的满二叉树至多有（）个 结 点（根结点为第一层）A.40 B.31 C.34 D.3517.已知一个图的边数为m,则该图的所有顶点的度数之和为（）oA.2m B.m C.2m+l D.m/218.已知一个图的所有顶点的度数之和为m,则该图的边数为（）。A.2m B.m C.2m+l D.m/219.以下说法不正确的是（）oA.连通图G 一定存在生成树B.连通图G 的生成树中一定包含G 的所有顶点C.连通图G 的生成树中不一定包含G 的所有边D.连通图G 的生成树可以是不连通的20.以下说法不正确的是（）。A.连通图G 的生成树一定是唯一的B.连通图G 一定存在生成树C.连通图G 的生成树中一定要包含G 的所有顶点D.连通图G 的生成树一定是连通而且不包含回路21.散列查找的原理是（）。A.在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系B.按待查记录的关键字有序的顺序方式存储C.按关键字值的比较进行查找D.基于二分查找的方法22.有序表为1,2,4,6,10,18,20,32,用课本中折半查找算法查找值18,经（）次比较后成功查到。A.3 B.2 C.4 D.523.排序过程中，每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置，直到全部排好序为止，该排序算法是（）。A.直接插入排序 B.快速排序C.冒泡排序 D.选择排序24.在排序过程中，可以通过某一趟排序的相关操作所提供的信息，判断序列是否已经排好序，从而可以提前结束排序过程的排序算法是（）。A.冒泡 B.选择 C.直接插入 D.折半插入25.采用顺序查找法对长度为n 的线性表进行查找（不采用表尾设监视哨的方法），最坏的情况下要进行（）次元素间的比较。A.n+2 B.n C.n-1 D.n/226.用折半查找法，对长度为12的有序的线性表进行查找，最坏情况下要进行（）次元素间的比较A.4 B.3 C.5 D.627.如图若从顶点a 出发按广度优先搜索法进行遍历，则可能得到的顶点序列为（)oA.acebdfghB.aebcghdfC.aedfbcghD.abecdfgh2 8.如图若从顶点a 出发按深度优先搜索法进行遍历，则可能得到的顶点序列为（)oA.acfgedbB.aedbgfcC.acfebdgD.aecbdgf29.一棵哈夫曼树总共有23个结点，该树共有（A.10 B.13 C.11）个叶 结 点（终端结点）D.1230.一棵哈夫曼树总共有25个结点，该树共有A.12 B.13 C.14）个非叶结点（非终端结点）。D.15二、填 空 题（每小题2 分，共 24分）1.通 常 数 据 的 逻 辑 结 构 包 括、四种类型。2.结构中的元素之间存在多对多的关系称为 结构。3.设有一个单向链表，结点的指针域为n ex t,头指针为head,p 指向尾结点，为了使该单向链表改为单向循环链表，可用语句。4.设有一个单向循环链表，结点的指针域为n ex t,头指针为head,指针p 指向表中某结点，若逻辑表达式 的结果为真，则 p 所指结点为尾结点。5.设有一个单向循环链表，头指针为h ead,链表中结点的指针域为next,p 指向尾结点的直接前驱结点，若要删除尾结点，得到一个新的单向循环链表，可执行操作6.设有一个链栈，栈顶指针为h s,现有-一个s 所指向的结点要入栈，则可执行操作s-next=hs;。7.在一个链队中，f 和 r 分别为队头和队尾指针，队结点的指针域为n e x t,则插入一个S所指结点的操作为;r=s；8 .在一个链队中，f和r分别为队头和队尾指针，队结点的指针域为n e xt,s指向一个要入队的结点，则入队操作为;；9 .循环队列的队头指针为f,队尾指针为r,当 时表明队列为空。1 0 .循环队列的最大存储空间为M a xS ize=6,采用少用一个元素空间以有效地判断栈空或栈满，若队头指针f ro n t=4,当队尾指针rear=时队满，队列中共有个元素。1 1 .*A 在存储时占 个字节。“A”在存储时占 个字节。1 2 .程序段 c ha r*s=a Bc D”;n=0;while(*s!=0 )if(*s=a&*skey!=(2)if(kkey)(3);else _(4);if(p二 二 NULL)break;)Return(_(5);3.以下函数为链队列的入队操作，x 为要入队的结点的数据域的值，front rear分别是链队列的队头、队尾指针struct node ElemType data;struct node*next;)；struct node*front,*rear;v o i d I n Q u e u e(E l e m T y p e x)(s t r u c t n o d e *p;p=(s t r u c t n o d e*)_ _ _(1);p-d a t a=x;p-n e x t=NU LL;一(2);r e a r=_ _ _(3);)4.以下函数为链队列的出队操作(链队列带有头结点)，出队结点的数据域的值由x 返回，front、rear分别是链队列的队头、队尾指针struct node ElemType data;struct node*next;);struct node*front,*rear;E l e m T y p e Ou t Q u e u e 0(E l e m T y p e x;i f(1)p r i n t f(队列下溢错误！n )；e x i t (1);e l s 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);i f(p-n e x t-NU LL)r e a r=f r o n t;f r e e(p);(3);答案一、单项选择题1.C 2.A 3.C 4.B 5.D 6.B 7.A 8.D 9.A 1 0.C 1 1.C 1 2.C1 3.D 1 4.B 1 5.A 1 6.B 1 7.A 1 8.D 1 9.D 2 0.A 2 1.A 2 2.B 2 3.A2 4.A 2 5.B 2 6.A 2 7.D 2 8.B 2 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.gd 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(3)a b d e c2.(1)a(2)e d b c a(3)e=l,a=2,d=3,c=4,b=53.(1)(2)A S L=(1 x 1 4-2 x 2+3 x 3+4)/7=1 8/74.(1)(2)5,6,7,8,9,1 0,1 7,1 8,1 9,2 15.(1)初始树 堆(2)102,52,42,82,16,67,32,57(2)2n-l 不一定唯一四、程序填空题(每空2分，共16分)1.(1)low=high(2)mid(3)amid.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)retum(x)数据结构(本)期末综合练习三2009年 6 月一、单项选择题1.()是性质相同的数据元素的集合，是数据的子集。A、数据元素 B.数据对象 C.数据结构 D.数据项2.从 n 个数中选取最大元素()。A.基本操作是数据元素间的交换 B.算法的时间复杂度是0(一)C.算法的时间复杂度是O(n)D.需要进行(n+1)次数据元素间的比较3.设链表中的结点是NODE类型的结构体变量，且有NODE*p：为了申请一个新结点，并由p 指向该结点，可用以下语句()。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 指向链表的尾结点，则满足逻辑表达式()的值为真。A.p-next=NULL B.p=NULLC.p-next=head D.p-next=head5.设顺序存储的线性长度为n,要在第i 个元素之前插入一个新元素，按课本的算法当1=()时，移动元素次数为2A.n/2 B.n C.1 D.n-16.设顺序存储的线性表长度为n,要删除第i 个元素，按课本的算法，当 i=()时，移动元素的次数为3A.3 B.n/2 C.n-3 D.37.一个栈的进栈序列是1,2,3,4,则栈的不可能的出栈序列是()(进出栈操作可以交替进行)A.3,2,4,1 B.1,4,2,3C.4,3,2,1 D.3,2,L 48.一个栈的进栈序列是a,b,c,d,则栈的不可能的出栈序列是（）oA.adbc B.beadC.cbad D.deba9.设有一个带头结点的链队列，队列中每个结点由一个数据域data和指针域next组成，front和 rear分别为链队列的头指针和尾指针。设 p 指向要入队的新结点（该结点已被赋值），则入队操作为（）0A.rear-next=p;rear=p;B.rear-next=p;p=rear;C.p=rear-next;rear=p;D.rear=p;rear-next=p;1 0.设有一个带头结点的链队列，队列中每个结点由一个数据域data和指针域next组成,front和 rear分别为链队列的头指针和尾指针，要执行出队操作，用 x 保存出队元素的值，p 为指向结点类型的指针，可执行如下操作：p=front-next;x=p-data;然后指行（）。A.front=p-next;B.front-next=p-next;C.front=p;D.front-next=p;1 1.以下说法不正确的是（）。A.顺序栈中，栈满时再进行进栈操作称为“上溢”B.顺序栈中，栈空时再作出栈栈操作称为“下溢”C.顺序队列中，当尾指针已经超越队列存储空间的上界，则一定是队列已满D.顺序队列中，队列的头指针和尾指针均超越队列存储空间的上界，则队列已空13.设有一个20阶的对称矩阵A,采用压缩存储方式，将其下三角部分以行序为主序存储到一维数组中（矩阵A 的第一个元素为a1P b 的下标从1 开始），则矩阵元素ag5在一维数组b 中的下标是（）。A.30 B.28 C.40 D.3314.设有一个10阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b 中。（矩阵A 的第一个元素为a u，数组b 的下标从1 开始），则矩阵元素 asj对应一维数组b 的数组元素是（）。A.b18 B.b81 C.b13 D.b1015.深度为5 的完全二叉树第5 层上有4 个结点，该树一共有（）个结点。A.28 B.30 C.31 D.1916.深度为5 的完全二叉树共有20 个结点，则第5 层 上 有（）个结点（根所在结点为第一层）。A.3 B.8 C.5 D.617.已知一个图的所有顶点的度数之和为m,则 m 一定不可能是（）。A.4 B.8 C.12 D.918.已知一个图的所有顶点的度数之和为m,且 m 是以下4 中情况之一，则 m 只可能是（）。A.9 B.7 C.15 D.819.以下说法正确的是（）。A.连通图G 的生成树中可以包含回路B.连通图G 的生成树可以是不连通的C.连通图G 的生成树一定是唯一的D.连通图G 的生成树一定是连通而不包含回路的20.线性表只要以（）方式存储就能进行折半查找。A.链接 B.顺序 C.关键字有序的顺序 D.二叉树21.对 n 个元素进行冒泡排序，通常要进行n-1趟冒泡，在第j 趟冒泡中共要进行（）次元素间的比较。A.j B.j-1 C.n-j22.对 n 个元素进行冒泡排序若某趟冒泡中只进行了（明序列已经排好序。A.1 B.2 C.0D.n-j-1）次元素间的交换，则表D.n-123.在排序过程中，可以有效地减少-趟排序过程中元素间的比较次数的算法是（）。A.冒泡 B.选择 C.直接插入 D.折半插入24.在对一组元素（64,48,106,33,25,82,70,55,93）进行直接插入排序时，当进行到要把第7 个 元 素 7 0 插入到已经排好序的子表时，为找到插入位置，需进行（）次元素间的比较（指由小到大排序）。A.6B.2C.3D.425.如图若从顶点a 出发按深度优先搜索法进行遍历，则可能得到的顶点序列为（A.aebcfdB.abedcfC.acebdfD.acfbde)o图 12 6.如图，若 从 顶 点 a 出发按广度优先搜索法进行遍历，则可能得到的顶点序列为（）oA.acebdgfB.abecdgfC.acfedgbD.abecfdg27.一棵哈夫曼树有n 个叶子结点（终端结点），该树总共有（）个结点。A.2n-2B.2n-lC.2nD.2n+228.一棵哈夫曼树有10个非叶子结点（非终端结点），A.21 B.20 C.2229.数 据 的（）结构与所使用的计算机无关。该树总共有（D.19）个结点。A.逻辑B.物理C.存储D.逻辑与存储3 0.队列的插入操作在（）进行。A.队头B.队尾C.队头或队尾D.在任意指定位置二、填空题1.通常可以把 一本含有不同章节的书的目录结构抽象成 结构。2.通常可以把某城市中各公交站点间的线路图抽象成 结构。3.要在一个单向链表中p 所指向的结点之后插入一个s 所指向的新结点，若链表中结点的指针域为n e x t,可执行 和 p-next=s;的操作。4.要在一个单向链表中删除p 所指向的结点，已知q 指向p 所指结点的直接前驱结点，若链表中结点的指针域为n e x t,则可执行。5.设有一个非空的链栈，栈顶指针为h s,要进行出栈操作，用 x 保存出栈结点的值，栈结点的指针域为n e x t,则可执行x=hs-dat a;。6.设有一个链栈，栈顶指针为h s,现有一个s 所指向的结点要入栈，则可执行操作_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 和 hs=s；7.在一个不带头结点的非空链队中，f 和 r 分别为队头和队尾指针，队结点的数据域为d ata,指针域为next,若要进行出队操作，并用变量x 存放出队元素的数据值，则相关操作为x=f-dat a;o8.在一个不带头结点的非空链队中，f 和 r 分别为队头和队尾指针，队结点的数据域为d ata,指针域为next,若要进行出队操作，并用变量x 存放出队元素的数据值，则相关操作为9.循环队列的最大存储空间为MaxSize=8,采用少用一个元素空间以有效的判断栈空或栈满，若队头指针front=4,则当队尾指针rear=时，队列为空，当 reau 时，队列有6 个元素。1 0,顺序存储字符串“ABCD”需要占用 个字节。11.稀疏矩阵存储时，采用一个由、3 部分信息组成的三元组唯一确定矩阵中的一个非零元素。12.一棵二叉树叶结点（终端结点）数为5,单分支结点数为2,该树共有 个结点。13.棵二叉树顺序编号为6 的 结 点（树中各结点的编号与等深度的完全二叉中对应位置上结点的编号相同），若它存在右孩子，则 右 孩 子 的 编 号 为。14.设 棵完全二叉树，其最高层上最右边的叶结点的编号为奇数，该叶节点的双亲结点的编号为1 0,该完全二叉树一共有 个结点。15.结构中的数据元素存在多对多的关系称为 结构。16.结构中的数据元素存在一对多的关系称为 结构。17.结构中的数据元素存在一对多的关系称为 结构。18.结构中的数据元素存在一对一的关系称为 结构。19.如图2 所示的二叉树，其前序遍历序列为a20.如图2 所示的二叉树，其后序遍历序列为图 221.在队列的顺序存储结构中，当插入个新的队列元素时，指针的值增1,当删除一个元素队列时，指针的值增1。22.图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是 的。（回答正确或不正确）23.循环队列的引入，目的是为了克服 o24.按某关键字对记录序列排序，若关键字 的记录在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。三、综合题1.（1）设