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

《电大数据结构期末综合练习.pdf》由会员分享，可在线阅读，更多相关《电大数据结构期末综合练习.pdf（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构（本）期末综合练习为了帮助同学们进行期末复习，特拟定以下三套期末综合练习题，望同学们逐一认真完成。数 据 结 构（本）期末综合练习一一、单项选择题1 .针对线性表，在存储后如果最常用的操作是取第i个结点及其前驱，则 采 用（）存储方式最节省时间。A.单链表 B.双链表 C.单循环链表 I）.顺序表2 .线性表采用链式存储时;其 地 址（）oA.一定是不连续的 B.必须是连续的C.可以连续也可以不连续 D.部分地址必须是连续的3 .数据结构中，与所使用的计算机无关的是数据的（）结构。A.物理 B.存储 C.逻辑与物理 D.逻辑4.带头结点的单向链表的头指针为h e ad,该链表为空的判定

2、条件是（）的值为真。A.h e ad =N U L L B.h e ad-n e x t=h e adC.h e ad-n e x t=N U L L D.h e ad =h e ad-n e x t5 .以下特征中，（）不是算法的特性。A.有穷性 B.确定性 C.可行性 1）.有0个或多个输出6 .设顺序存储的线性表长度为n,对于插入操作，设插入位置是等概率的，则插入一个元素平均移动元素的次数为（）。A.n/2 B.n C.n-1 D.n-i+17 .设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（）A.n-i+1 B.n-i C.n-i

3、-1 D.i8 .一个栈的进栈序列是5,6,7,8,则栈的不可能的出栈序列是（）（进出栈操作可以交替进行）A.5,8,6,7 B.7,6,8,5C.7,6,5,8 D.8,7,6,59.栈的插入删除操作在（）进行。A.栈底 B.任意位置 C.指定位置 D.栈顶1 0 .栈和队列的相同点是（）A.都是后进先出 B.都是后进后出C.逻辑结构与线性表不同D.逻辑结构与线性表相同，都是操作规则受到限制的线性表1 1 .以下说法正确的是（）。A.栈的特点是先进先出，队列的特点是先进后出B.栈和队列的特点都是先进后出C.栈的特点是先进后出，队列的特点是先进先出D.栈和队列的特点都是先进先出1 2 .在C语

4、言中，利用数组a存放字符串“H e llo ，以下语句中正确的是（）。A.c h ar a 1 0 J=H e llo”；C.c h ar a 1 0=H e llo ;B.c h ar al 1 0;a=H e llo”;D.c h ar a 1 0=H ,e ,T,T,o 1 3 .元 素2,4,6,8按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。A.8,6,4,2C.4,2,8,6B.D.2,4,6,88,6,2,41 4.设有一个1 5阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。（矩 阵A的第一个元素为ai.”数组b的下标从1开

5、始），则数组元素b 1 3 对应A的矩阵元素是（）。C.a7.2D .&6,S1 5 .设有一个1 5阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到维数组B中（数组下标从1开始），则矩阵中元素瓯6在一维数组B中的下标 是（）。1 6.一棵完全二叉树共有3 0个结点，则该树一共有（）层（根结点所在层为第一层）。1 7.串函数 St r Cm p （d”，“D”）的 值 为（）。C.-11 8.以下说法正确的是（）。A.连通图G的生成树中不一定包含G的所有顶点B.连通图G的生成树中一定要包含G的所有边C.连通图G的生成树一定是唯一的D.连通图G一定存在生成树1 9 .在一棵二

6、叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（）。A.2 i B.2 i-l C.2 i+2 D.2 i+l2 0 .对二叉排序树进行（）遍历，遍历所得到的序列是有序序列。A.按层次 B.前序 C.中序 D.后序2 1 .设一棵有n个结点采用链式存储的二叉树，则该树共有（）个指针域为空。A.2 n B.2 n+l C.2 n+2 D.n+12 2 .以下排序算法中，在一趟排序过程中，除了其它相关操作外，只进行一次元素间的交换的算法是（）。A.直接选择 B.冒泡 C,直接插入 D.折半插入2 3 .已知如图1所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点

7、序列为（）。A.a b c e df B.a b c e f d C.a e b c f d D.a c f de b图 12 4.对长度为n的线性表进行顺序查找，在等概率情况下，平均查找长度为（）oA.n B.（n+1）/2 C.2 n D.n-12 5.在有序表 1,3,8,1 3,3 3,4 2,4 6,63,7 6,7 8,8 6,9 7,1 0 0 中，用折半查找值 8 6时，经（）次比较后查找成功。A.6 B.3 C.8 D.42 6.如图若从顶点a出发按深度优先搜索法进行遍历，则可能得到的顶点序列为（）oA.a c f g e dbB.a e dc b g fC.a c f e

8、b dgD.a e c b dg f2 7 .有 个 长 度 为 1 0 的有序表，按折半查找时该表进行查找，在等概率情况下查找成功的平均比较次数为（）。A.2 9/1 0 B.3 1/1 0 C.2 6/1 0 D.2 9/92 8 .一棵哈夫曼树有1 2 个叶子结点（终端结点），该树总共有（）个结点。A.2 2 B.2 1 C.2 3 D.2 42 9 .组记录的关键字序列为（3 7,7 0,4 7,2 9,3 1,8 5）,利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。A.3 1,2 9,3 7,4 7,7 0,8 5 B.2 9,3 1,3 7,4 7,7 0,8

9、5C.3 1,2 9,3 7,7 0,4 7,8 5 D.3 1,2 9,3 7,8 5,4 7,7 03 0 .队列的删除操作在（）进行。A.队头 B.队尾 C.队头或队尾 D.在任意指定位置二、填空题得分评卷人1 .把数据存储到计算机中，并具体体现数据之间的逻辑结构称为 结构。2 .设有个不带头结点的单向循环链表，结点的指针域为n e x t,指针p指向尾结点，现要使p指向第一个结点，可用语句。3 .结构中的数据元素存在一对一的关系称为 结构。4 .要在一个带头结点的单向循环链表中删除头结点，得到一个新的不带头结点的单向循环链表,若结点的指针域为n e x t,头指针为h e a d,尾指

10、针为p,则可执行h e a d=h e a d-next;o5 .在双向链表中，每个结点有两个指针域，一个指向,另一个指向6 .设有一个非空的链栈，栈顶指针为h s,要进行出栈操作，用 x保存出校结点的值,栈结点的指针域为n e x t,数据域为d a ta,则可执行x=:和hs=；7.设有一个头指针为head的单向链表，p 指向表中某一个结点，且有p-next=NULL,通过操作,就可使该单向链表构造成单向循环链表。8.循环队列的最大存储空间为MaxSize,队头指针为f,队尾指针为r,当_ _ _ _ _ _ _ _ _ _时表明队列已满。9.从一个栈顶指针为h 的链栈中删除一个结点时，用

11、 x 保存被删结点的值，可执行x=h-data;和。（结点的指针域为next）10.程序段 int count=0;char*s=ABCD;while（*s!=0）s+;count+;执行后counts_11.两个串相等的充分必要条件是。12.一棵二叉树总结点数为1 1,叶结点数为5,该树有 个双分支结点，个单分支结点。13.对二叉树的遍历可分为、四种不同的遍历次序。14.设一棵完全二叉树，其最高层上最右边的叶结点的编号为偶数，该叶节点的双亲结点的编号为9,该完全二叉树-共有 个结点。15.一棵有n 个叶结点的二叉树，其每一个非叶结点的度数都为2,则该树共有个结点。16.双向循环链表中，p 指

12、向表中某结点，则通过p 可以访问到p 所指结点的直接后继结点和直接前驱结点，这种说法是 的（回答正确或不正确）。17.一棵有14个结点的完全二叉树，则它的最高层上有 个结点。18.栈和队列的操作特点分别是 和。19.如图2 所示的二叉树，其先序遍历序列为。图 220.折半查找只适用于 存储的有序表。21.哈希函数是记录关键字值与该记录 之间所构造的对应关系。22.深度为k 的二叉树最多有 结点。23.二叉树排序中任一棵子树都是二叉排序树，这种说法是 的。（回答正确或不正确）2 4.串的两种最基本的存储方式是 和三、综合题得 分评卷人1.设一组记录的关键字序列为（4 9,8 3,5 9,4 1,

13、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

14、）删除链表的第一个结点（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,1 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 画出对上述序列进行折半查找的判定树（以序列中的元

15、素作为树的结点）（2）为了成功查找到1 0 0 需要进行多少次元素间的比较？为了查找9,经过多少次元素间的比较可知道查找失败？5.（1）对给定数列 7 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

16、,a2L，a n 中的序列进行排序，完成程序中的空格部分，其中n是元素个数，要求按升序排列。vo i d bs o r t (N O D E a ,i n t n)N O D E t e m p;i n t i,j,f l a g;f o r(j=l;(1);j+)；f l a g=0;f o r (i=l;(2);i+)i f(a i .k e y a i+l .k e y)f l a g=l;t e m p=a i ;(3);(4);i f(f l a g=0)br e a k;)程序中f l a g 的功能是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

17、_ _ _2 .以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为l e f t 和 r i g h t,数据域d a t a 为字符型，B T 指向根结点)。vo i d P r e o r d e r (s t r uc t B T r e e N o d e *B T)i f(B T!=N U L L)_(1)_ _ _ _ _ _ _ _ _ _ _ _ _ _ _；_ I 2)_ _ _ _ _ _ _ _ _ _ _ _ _ _ _;(3);)3 .设线性表为(6,1 0,1 6,4),以下程序用说明结构变量的方法建立单向链表，并输出链表中各结

18、点中的数据。#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为工作指针，准备输出链表*/doprintf(u%dn,(3):(4)_;while(5):4.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和 rig h t,数据域data为字符型，B T指向根结点)。void I

19、norder(struct BTreeNode*BT)if(BT!=NULL)_()_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _；(2):(3);答案一、单项选择题1.I）2.C 3.D 4.C 5.I）6.A1 3.D 1 4.A 1 5.C 1 6.D 1 7.B2 4、B 2 5.D 2 6.A 2 7.A 2 8,二、填空题1.物 理（存储）3.线性5.结点的直接后继结点的直接前驱7.p-n e xt=h e a d;9.h=h-n e xt;1 1.串长度相等且对应位置的字符相等1 3.先序、中序、后序、层次1 5.2 n-l1 7.71 9.a bd g

20、c e f h i2 1.存储地址2 3.正确2.p=p-n e xt;4.p-n e xt=h e a d；6.h s-d a t a;h s-n e xt;8.（r+1）%M a xS i z e=f1 0.41 2.4；21 4.1 81 6.正确1 8 .先 进 后 出（后进先出）先进先出2 0 .顺序存储结构2 2 .2k-l2 4.顺 序 存 储 链 式 存 储7.A 8.A 9.D 1 0.D 1 1.C 1 2.A1 8.D 1 9.D 2 0.C 2 1.D 2 2.A 2 3.BC 2 9.A 3 0.A（后进后出）三、综合题图 3图 4(1)s=(NODE*)malloc

21、(sizeof(NODE);s-data=l;(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.(1)图 6(2)先将给定值与根结点比较，若相等则查找成功，否则若小于根结点则在左子树中继续查找，大于根结点在右子树中查找，查找20共进行3 次比较。6.(1)图 6中序遍历中序 2,3,4,5,6,7,14,16,18四、程序填空题L.(1)j=n-l(2)i dat a)(2)Pr eo r der(B T

22、-l eft)(3)Pr eo r der(B T-r ight)(1)&a(2)d n ex t二NULL(3)p-dat a(4)p=p-n ex t(5)p!=NULL(1)In o r der(B T-l eft)(2)p r in t f(,B T-dat a)(3)In o r der(B T-r ight)数据结构（本）期末综合练习二2009年6月一、单项选择题1.数据元素是数据的基本单位，它（A.只能有一个数据项组成 B.至少有二个数据项组成C.可以是一个数据项也可以由若干个数据项组成D.至少有一个数据项为指针类型2.一种逻辑结构（）存储结构。A.可以有不同的 B.只能有唯一的

23、C.的数据元素在计算机中的表示称为 D.的数据元素之间的关系称为3.线性表的顺序结构中，（）。A.逻辑上相邻的元素在物理位置上不一定相邻B.数据元素是不能随机访问的C.逻辑上相邻的元素在物理位置上也相邻D.进行数据元素的插入、删除效率较高4.以下说法中不正确的是（）。A.双向循环链表中每个结点需要包含两个指针域B.已知单向链表中任一结点的指针就能访问到链表中每个结点C.顺序存储的线性链表是可以随机访问的D.单向循环链表中尾结点的指针域中存放的是头指针5.以下表中可以随机访问的是（A.单向链表 B.双向链表C.单向循环链表 D.顺序表6.双向循环链表结点的数据类型为：struct node in

24、t data;struct node*next;/*指向直接后继*/struct node*prior;；设 p 指向表中某一结点，要显示p 所指结点的直接前驱结点的数据元素，可用操作（）oA.printf（%d”,p-next-data）;B.printf（44%d,p-prior-data）;C.printf（%dpprior-next）;D.printf（%dpdata）;7.设顺序存储的线性表长度为n,对于删除操作，设删除位置是等概率的，则删除一个元素平均移动元素的次数为（）。A.（n+1 ）/2 B.n C.2n D.n-i8.一个栈的进栈序列是e fg h,则栈的不可能的出栈序列是

25、（）（进出栈操作可以交替进行）。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;1 0.设 top是个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成,设用x 接收栈顶元素，则取栈顶元素的操作为（）。A.top-data=x;C.x=t

26、op-data;1 1.以下说法正确的是（A.队列是后进先出B.top=top-next;D.x=top-data;top=top-next;)oB.栈的特点是后进后出C.栈的删除和插入操作都只能在栈顶进行D.队列的删除和插入操作都只能在队头进行12.以下说法不正确的是（）。A.栈的特点是后进先出 B.队列的特点是先进先出C.栈的删除操作在栈底进行，插入操作在栈顶进行D.队列的插入操作在队尾进行，删除操作在队头进行13.串函数$武1（，皿人”；枇 吟 的 值 为（）。A.1 B.0 C.“abAaba D.-114.char*p;p=StrCat（ABD,ABC）；Printf（%s”,p）;

27、的显示结果为（）。A.-1 B.ABDABC C.AB D.11 5.设有一个12阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b 中（矩阵A 的第一个元素为a u，数组b 的下标从1 开始），则矩阵A中第4 行的元素在数组b 中的下标i 一 定 有（）oA、7Wi W10 B、1 1 W 0 5 C、9 W W 1 4 D、6Wi next=hs;。7.在一个链队中，f和r分别为队头和队尾指针，队结点的指针域为n e x t,则插入一个s所指结点的操作为;r=s；8 .在-一个链队中，f和r分别为队头和队尾指针，队结点的指针域为ne xt,s指 向,个要入队的结点，

28、则入队操作为;；9 .循环队列的队头指针为f,队尾指针为r,当_ _ _ _ _ _ _ _ _ _ _ _时表明队列为空。1 0 .循环队列的最大存储空间为M a xS ize=6,采用少用一个元素空间以有效地判断栈空或栈满,若队头指针f ro nt=4,当队尾指针rear=时队满,队列中共有个元素。1 1 .*A 在存储时占 个字节。“A”在存储时占 个字节。1 2 .程序段 c h a r*s=a Bc D”;n=0;w h ile(*s!=0 )if(*s=a&*s k e y!=_(2)if(k k e y)一(3);e l s e _ _ _(4);if(p=NU L L)b r

29、e a k;)Re t u r n (_ _ _(5);)3.以下函数为链队列的入队操作，x 为要入队的结点的数据域的值，front,rear分别是链队列的队头、队尾指针struct node ElemType data;struct node*next;)；struct node*front,*rear;v o id I n Qu 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 L L;(2);r e a r=_ _ _(3);)

30、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 Qu e u e 0(E l e m T y p e x;if(1)(p r in t f(队列下溢错误!n 0；e x it (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

31、x t=_ _ _(2);if (p-n e x t=NU L L)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 10.C 11.C 12.C13.D 14.B 15.A 16.B 17.A 18.D 19.D 20.A 21.A 22.B 23.A24.A 25.B 26.A 27.D 28.B 29.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

32、.h s=s；7.r-n e x t=s8.r-n e x t=s；r=s；9.r=f10.3；511.1；212.213.1114.1015.先序；中序；后序16.深度优先；广度优先17.物理(存储)1 8.图状(网状)19.g d b e ih f c a20.2n-l2 1.错误22.顺序存储链式存储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=1 ,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/7

33、4.(1)(2)5,6,7,8,9,1 0,1 7,1 8,1 9,2 15.(1)初始树堆6.(2)102,52,42,82,16,67,32,57(2)2 n-l 不一定唯一四、程序填空题(每空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)retum(x)数据结构(本)期末综合练习三2009年 6 月一、单项选择题1.()是性质相同的数据元素的集合，是数据的子

34、集。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为非空的

35、单向循环链表头指针，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,

36、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组成

37、,front和 rear分别为链队列的头指针和尾指针，要执行出队操作，用 x 保存出队元素的值，p 为指向结点类型的指针，可执行如下操作：p=front-next;x=p-data;然后指行（）。A.front=p-next;C.front=p;1 1.以下说法不正确的是（B.front-next=p-next;D.front-next=p;A.顺序栈中，栈满时再进行进栈操作称为“上溢”B.顺序栈中，栈空时再作出栈栈操作称为“下溢”C.顺序队列中，当尾指针已经超越队列存储空间的上界，则一定是队列已满D.顺序队列中，队列的头指针和尾指针均超越队列存储空间的上界，则队列已空13.设有一个20阶的对

38、称矩阵A,采用压缩存储方式，将其下三角部分以行序为主序存储到 维数组中（矩阵A 的第个元素为au，数组b 的下标从1 开始），则矩阵元素a&5在一维数组b 中的下标是（）。A.30 B.28 C.40 D.3314.设有一个10阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b 中。（矩阵A 的第一个元素为au,数组b 的下标从1 开始），则矩阵元素 a5.3对应一维数组b 的数组元素是（）。A.b18 B.b8 C.b13 D.b1015.深度为5 的完全二叉树第5 层上有4 个结点，该树一共有（）个结点。A.28 B.30 C.31 D.1916.深度为5 的完全二

39、叉树共有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

40、.二叉树21.对n个元素进行冒泡排序，通 常 要 进 行n-1趟冒泡，在 第j趟冒泡中共要进行（）次元素间的比较。A.j B.j-1 C.n-j D.n-j-122.对n个元素进行冒 泡 排 序 若某趟冒泡中只进行了（）次元素间的交换，则表明序列已经排好序。A.1 B.2 C.0 D.n-123.在排序过程中，可以有效地减少一趟排序过程中元素间的比较次数的算法是（）。A.冒泡 B.选择 C.直接插入 D.折半插入24.在 对 一 组 元 素（64,48,106,33,25,82,70,55,93）进行直接插入排序时，当进 行 到 要 把 第7个 元 素7 0插入到已经排好序的子表时，为找到插入

41、位置，需进行（）次 元 素 间 的 比 较（指由小到大排序）。A.6 B.2 C.3 D.425.如 图 若 从 顶 点a出发按深度优先搜索法进行遍历，则 可 能 得 到 的 顶 点 序 列 为（）。A.aebcfdB.abedcfC.acebdf/D.acfbde(2 6.如 图，若 从 顶 点a出发按广度优先搜索法进行遍历,()。A.acebdgfB abecdgfC.acfedgbD.abecfdg 图1则可能得到的顶点序列为）/%配127.一棵 哈 夫 曼 树 有n个 叶 子 结 点（终端结点），该 树 总 共 有（）个结点。A.2n-2B.2n-lC.2n28.一棵 哈 夫 曼 树

42、有10个 非 叶 子 结 点（非终端结点）,A.212 9.数 据 的（A.逻辑B.20C.22）结构与所使用的计算机无关。B.物理C.存储3 0.队 列 的 插 入 操 作 在（）进 行。D.2n+2该 树 总 共 有（）个结点。D.19D.逻辑与存储A.队头B.队尾C.队头或队尾D.在任意指定位置二、填空题1.通常可以把一本含有不同章节的书的目录结构抽象成 结构。2.通常可以把某城市中各公交站点间的线路图抽象成 结构。3.要在一个单向链表中p 所指向的结点之后插入一个s 所指向的新结点，若链表中结点的指针域为n e x t,可执行 和 p-next=s;的操作。4.要在一个单向链表中删除p

43、 所指向的结点，已知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,指针域为n ex t,若要进行出队操作，并用变量x 存放出队元素的数据值，则相关操

44、作为x=f-dat a;o8.在一个不带头结点的非空链队中，f 和 r 分别为队头和队尾指针，队结点的数据域为d ata,指针域为next,若要进行出队操作，并用变量x 存放出队元素的数据值，则相关操作为9.循环队列的最大存储空间为MaxSize=8,采用少用一个元素空间以有效的判断栈空或栈满，若队头指针front=4,则当队尾指针rear=时，队列为空，当 rean=_时，队列有6 个元素。1 0,顺序存储字符串“ABCD”需要占用 个字节。11.稀疏矩阵存储时，采用一个山、3 部分信息组成的三元组唯一确定矩阵中的一个非零元素。12.一棵二叉树叶结点（终端结点）数为5,单分支结点数为2,该树

45、共有 个结点。13.一棵二叉树顺序编号为6 的 结 点（树中各结点的编号与等深度的完全二叉中对应位置上结点的编号相同），若它存在右孩子，则 右 孩 子 的 编 号 为。14.设一棵完全二叉树，其最高层上最右边的叶结点的编号为奇数，该叶节点的双亲结点的编号为1 0,该完全二叉树一共有 个结点.15.结构中的数据元素存在多对多的关系称为 结构。16.结构中的数据元素存在一对多的关系称为 结构。17.结构中的数据元素存在一对多的关系称为 结构。18.结构中的数据元素存在一对一的关系称为 结构。19.如图2 所示的二叉树，其前序遍历序列为a2 0 .如 图 2 所示的二叉树，其后序遍历序列为图 22

46、1 .在队列的顺序存储结构中，当 插 入 个新的队列元素时，指针的值增1,当删除一个元素队列时，指针的值增1 2 2 .图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是 的。（回答正确或不正确）2 3 .循环队列的引入，目的是为了克服。2 4.按某关键字对记录序列排序，若关键字 的记录在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。三、综合题1.（1）设 h e a d 1 和 p i 分别是不带头结点的单向链表A 的头指针和尾指针，h e a d?和 p 2 分别是不带头结点的单向链表B的头指针和尾指针，若要把B链表接到A链表之后,得到一个以h e a d

47、 i 为头指针的单向循环链表，写出其中两个关键的赋值语句（不用完整程序，结点的链域为next)。(2)单向链表的链域为n ex t,设指针p 指向单向链表中的某个结点，指针s 指向一个要插入链表的新结点，现要把s 所指结点插入p 所指结点之后，某学生采用以下语句:p-next=s;s-next=p-next;这样做正确吗？若正确则回答正确，若不正确则说明应如何改写2.(1)一组记录的关键字序列为 45,40,65,43,35,95 写出利用快速排序的方法，以第一个记录为基准得到的一趟划分的结果(要求给出一趟划分中每次扫描和交换的结果)(2)同样对序列 45,40,65,43,35,95 利用直

48、接插入排序，写出逐次插入过程(从第一个元素一直到第六个元素)。3.(1)画出对长度为10的有序表进行折半查找的判定树(以序号1,2,10表示树结点)(2)对上述序列进行折半查找，求等概率条件下，成功查找的平均查找长度4.(1)利用筛选过程把序列 42,82,67,102,16,32,57,52 建成堆(小根堆)，画出相应的完全二叉树(不要求中间过程)(2)写出对上述堆对应的完全二叉树进行中序遍历得到的序列5.(1)利用筛选法，把序列 37,77,62,97,11,27,52,47 建成堆(小根堆)，画出相应的完全二叉树(2)写出对上述堆所对应的二叉树进行前序遍历得到的序列6.(1)设有一个整数

49、序列 50,38,16,82,110,13,64,依次取出序列中的数，构造一棵二叉排序树(2)利用上述二叉排序树，为 了 查 找 1 1 0,经多少次元素间的比较能成功查到，为了查找1 5,经多少次元素间的比较可知道查找失败四、程序填空题1.以下函数为直接选择排序算法，对 2 ,如2 也 田中的记录进行直接选择排序，完成程序中的空格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+l;j=_(2)；j+)if(aj.keydata=x

50、;(2)；(3)；4.以下函数在head为头指针的具有头结点的单向链表中删除第i 个结点，struct node int data;struct node*next;typedef struct node NODEint delete(NODE*head,int i)NODE*p,*q;intj;q=head;j=o；while(q!=NULL)&(_(1)(一(2);j+；if(q=NULL)return(O);P=一(3)；_(4)=p-next;free(5);return(l);答案：一、单项选择题1.B 2.C 3.A 4.D 5.D 6.C 7.B 8.A 9.A 10.B 11.