数据结构(本)期末综合练习(2016年6月(共32页).doc

《数据结构(本)期末综合练习(2016年6月(共32页).doc》由会员分享，可在线阅读，更多相关《数据结构(本)期末综合练习(2016年6月(共32页).doc（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上数据结构（本）期末综合练习2016年6月练习一一、单项选择题 1下面关于线性表的叙述错误的是（ ）。 A. 线性表采用顺序存储必须占用一片连续的存储空间 B. 线性表采用链式存储不必占用一片连续的存储空间 C. 线性表采用链式存储便于插入和删除操作的实现 D. 线性表采用顺序存储便于插入和删除操作的实现 2.数据的存储结构包括数据元素的表示和（ ）。 A . 数据处理的方法 B. 数据元素的类型 C . 相关算法 D. 数据元素间的关系的表示3.以下数据结构中是非线性结构的是( )。 A. 队列 B. 栈 C. 线性表 D. 二叉树 4树状结构中数据元素的位置之间存在

2、（ ）的关系。 A每一个元素都有一个直接前驱和一个直接后继 B一对一 C多对多 D一对多5设有一个长度为18的顺序表，要删除第7个元素需移动元素的个数为（ ）。 A13 B12 C11 D10 6设有一个长度为26的顺序表，要插入一个元素,并使它成为新表的第6个元素,需移动元素的个数为（ ）。 A21 B22 C20 D197. 两个字符串相等的充要条件是（ ）。 A. 两个字符串的长度相等 B. 同时具备(A)和(C)两个条件 C. 两个字符串中对应位置上的字符相等 D. 以上答案都不对 8头指针为head的带头结点的单向循环链表，p所指向尾结点，要使该链表成为不带头结点的单向循环链表, 可

3、执行head=head-nex;和（ ）。 Ap= head-next B head-next=p Chead-next=p-next D p-next=head;9. 设某链表中最常用的操作是在链表的尾部插入或删除元素，在已知尾指针的条件 下,选用下列（ ）存储方式最节省运算时间。 A. 单向链表B. 单向循环链表 C. 双向链表 D. 双向循环链表 10元素111，113，115，117按顺序依次进栈，则该栈的不可能输出序列是（ ）（进栈出栈可以交替进行）。 A117，115，113，111 B111，113，115，117 C117，115，111，113 D113，111，117，11

4、5 11元素13，15，19，20顺序依次进栈，则该栈的不可能输出序列是（ ）。 进栈出栈可以交替进行）。 A20，19，15，13 B13，15，19，20 C19，13，15，20 D15，13，20，19 12以下说法正确的是（ ）。 A栈的特点是先进先出 B栈的特点是先进后出 C队列的特点是先进后出 D. 栈和队列的特点都是后进后出 13设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，则在 表中删除结点B的操作为（ ）。 A. p-next； =q；B. q-next=p-next； C. p-next=q-next；D. q-next=p； 14. 设有一个20阶的

5、对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始）， 则矩阵元素a6,2 在一维数组B中的下标是（ ）。 A21 B17 C28 D23 15.栈和队列的共同特点之一是( )。 A. 都是先进后出 B. .都是先进先出C. 没有共同点 D. 只允许在端点处插入和删除元素16设有串p1=”ABADF”,P2=”ABAFD”，P3=”ABADFA”,P4=”ABAF”,以下四个串中最大的是( )。 A p3 B p2 C p1 D p417.用链接方式存储的队列，在进行插入运算时( )。 A. 需修改头指针 B. 头、尾指针都需

6、要修改 C. 需修改尾指针 D. 头、尾指针都不需要修改 18.数组a经初始化 char a =“English”; a7中存放的是（ ）。 A. 字符串的结束符 B. 字符h C. h D. 变量h19.字符串 a1=“AEIJING“，a2 =AEI“，a3=AEFANGa4=”AEFI“中最大的是（ ）。 A. a1 B. a2 C. a3 D. a4 20.设主串为“ABcCDABcdEFaBc”，以下模式串能与主串成功匹配的是（ ）。 A. Bcd B. BCd C. ABC D. Abc 21设有一个20阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其 下三角部分以

7、行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元 素a6,2在一维数组B中的下标是（ ）。 A23 B17 C21 D1822在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为（ ）。 A2i+1 B2i-1 C2i D2i+2 23. 以下说法正确的是( )。 A. 若二叉树中左子树上所有结点的值均小于根结点的值，右子树上所有结点的值 均大于根结点的值。则该树为二叉排序树。B. 二叉树中任意一个非叶结点的值都大于其左子树上所有结点的值,小于其右子 树上所有结点的值,则该树为二叉排序树。C. 二叉树中任意一个结点的值均大于其左孩子的值，小于其右孩子的值。则该树 为二叉

8、排序树。D.前序遍历二叉排序树可得到一个有序序列。24如图1所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得 到的一种顶点序列为（ ）。 Aabecdf Baecbdf Caebcfd Daedfcb bdfeca图1 25.二叉树的第k层的结点数最多为( )。 A.2K-1 B.2K+1 C.2k-1 D.2k-1 26线性表以（ ）方式存储，能进行折半查找。 A链接 B顺序 C关键字有序的顺序 D二叉树 27. 如图2所示，若从顶点6出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。 A6,9,3,2,8,7,4 B6,9,2,3,7,8,4 C6,2,7,9,

9、8,4,3 D6,2,8,7,9,3,43289674图2 28一棵具有38个结点的完全二叉树，最后一层有（ ）个结点。 A7 B5 C6 D8 29. 如图3所示，若从顶点a出发，按广度优先搜索法进行遍历，则可能得 到的一种顶点序列为（ ）。 Aabcfegd Babcdfge Cacbfedg Dabcfgde gfabdec图330.图4的拓扑序列是( )。 A5 2 3 4 6 B2 3 6 4 5 C5 6 2 3 4 D. 2 3 5 6 4 234543465图4 31. 对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A，其相应的三元组表共有6个元素，矩阵A共

10、有( )个零元素。 A8 B72 C74 D10 32. 10,6,2,1按顺序依次进栈，该队列的可能输出序列是（ ）。 (进栈出栈可以交替进行）。 A6,10,1,2 B2,10,6,1 C6,1,10,1 D1,6,10,2 33. 算法的时间复杂度与( )有关 A. 算法本身 B. 所使用的计算机 C. 算法的程序设计 D. 数据结构 34. 一种逻辑结构在存储时 （ ）。 A只要存储数据元素间的关系 B只能采用一种存储结构 C可采用不同的存储结构 D只要存储数据元素的值 35.数据结构在计算机内存中的表示是指 ( ) 。 A数据元素之间的关系 B数据的存储结构 C数据元素的类型 D数据

11、的逻辑结构 二、填空题1. 设：char a =“AEIJING“;该字符串在计算机中存储时占_个字节。 2结构中的数据元素存在多对多的关系称为_结构。3结构中的数据元素存在多对多的关系称为_结构。 4. n个元素进行冒泡法排序， 第j趟冒泡要进行_ _次元素间的比较。5. 对稀疏矩阵进行压缩存储,可采用三元组表，一个有8 行的稀疏矩阵A共有92个 零元素，其相应的三元组表共有4个元素。该矩阵A有_ 列。 6中序遍历_树可得到一个有序序列。7. 循环链队列中，设front和rear分别为队头和队尾指针，最大存储空间元素为MaxSize, 采用少用一个存储空间的模式，则判断循环链队列为空的条件是

12、_ _ _ 为真。 8. 待排序的序列为8,3,4,1,2,5,9, 采用直接选择排序算法,当进行了两趟选择后,结果序列为( )。 9. n个元素进行冒泡法排序，第j趟冒泡要进行_ _次元素间的比较。 10. 广义表( (a ,b) , d , e ,( (i ,j ) ,k ) )的长度是_ 。 11设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有_个结点。 （根所在结点为第1层） 12. 广义表的( c， a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_。 13中序遍历一棵_ 树可得到一个有序序列。 14. 对稀疏矩阵进行压缩存储,可采用三元组表，

13、一个有10 行10列的稀疏矩阵A共有95个零元素，其相应的三元组表共有 个元素。15.待排序的序列为9,4,5,1,2,6,10, 采用直接选择排序算法,当进行了两趟选择后,结果序列为_ 。 16在对一组记录(50, 49, 97, 22, 16, 73, 65, 47, 88)进行直接插入排序时，当把第7个记录65 插入到有序表时，为寻找插入位置需比较_次。17.广义表( (a ,b) , d , e ,( (i ,j ) ,k ) )的长度是_ 。18. 一棵有5个叶结点的哈夫曼树,该树中总共有 _ 个结点。19.广义表的 ( c， a , (a ,b) , d , e ,( (i ,j

14、) ,k ) )深度是_ 。 20. 设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有_个结点。 （ 根所在结点为第1层）。21.线性表用_方式存储需要占用连续的存储空间 。 22设有一个长度为40的顺序表，要删除第8个元素需移动元素的个数为_。 23. 线性表用关键字_的顺序方式存储，可以用二分法排序 。 24. 有以下程序段 char a =“English”; char *p=a; int n=0; 三、综合题1 （1）设有数据集合40，29，7，73，101，4，55，2，81，92，39，依次取集合中各数据构造一棵二叉排序树。 (2) 在上述二叉排序树上进行查找，给出成功查

15、找到元素92的查找路径,其中共经过了多少次元素间的的比较。(3)有一个长度为10的有序表，按折半查找对该表进行查找，给出在等概率情况下查 找成功的平均比较次数为。2有一个长度为11的有序表(1, 2, 11, 15, 24, 28, 30, 56, 69, 70, 80) , 元素的下标依次为 1,2,3,11，按折半查找对该表进行查找。 (1）画出对上述查找表进行折半查找所对应的判定树。 （2）说出成功查找到元素56,需要依次经过与哪些元素的比较？ （3）说出不成功查找元素72,需要进行元素比较的次数？3. (1) 以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树， (2) 给出相应

16、权重值叶结点的哈夫曼编码。 (3) 一组记录的关键字序列为（47，80，57，39，41，46），利用堆排序的方法建立的 初始堆（堆顶元素是最小元素,以树的形式给出）。4. (1)一组记录的关键字序列为（57，90，67，50，51，56），利用堆排序（堆顶元素是 最小元素）的方法建立初始堆（要求以完全二叉树描述 ）。 (2)对关键字序列(56,51,71,54,46,106)利用快速排序，以第一个关键字为分割元素， 给出经过一次划分后结果。 (3) 一组记录的关键字序列为（ 60,47，80，57，39，41，46,30），利用归并排序的 方法,分别给出(1,1) 归并、(2,2) 归并、(

17、4,4) 归并的结果序列。四、程序填空题1.设线性表为（1,3,7,5），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。 struct node int data;struct node *next;typedef struct node NODE; #define NULL 0 void 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=he

18、ad; /*p为工作指针，准备输出链表*/do printf(“%dn”, （3） ); （4） ; while(p!=NULL); 画出按该程序建立的单向链表的示意图，说明程序运行结束后p的指向。（5） 2.设线性表为（16，20，26，24），以不带头结点的单向链表存储，链表头指针为head,以下程序的功能是输出链表中各结点中的数据域data。 struct node int data; struct node *next; ; typedef struct node NODE; #define NULL 0 void main( ) NODE *head ,*p ; p=head; /*

19、p为工作指针*/ do printf(“%dn”, _(1)_); _(2)_ ; while(_(3)_); 3以下是先序遍历二叉树的递归算法程序，完成空格部分（树结构中左、 右指针域分 别为left和right，数据域data为字符型，BT指向根结点）。 efabcd图5 void Inorder (struct BTreeNode *BT) if( （1） ) （2） ;Inorder(BT-leftt); Inorder(BT-right); 利用上述程序对右图进行遍历，结果是 （3） ; 4.以下函数为直接选择排序算法，对a1,a2,an中的记录进行直接选择排序，完成 程序中的空格t

20、ypedef 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(aj.keynext=NULL（3）p-data（4）p=p-next（5）P指向NULL610164headNULLLL2 （1）p-data（2）p=p-next（3）p!=NULL3 （1） if(BT!=NULL)（2） printf(“%c”,BT-data);（3） a,b,d,e,f,c4 （1）n-1（2）n（3）

21、k=j（4）ai=ak (5) ak=temp 练习二一、单项选择题1栈和队列的共同特点是（ ）。A. 元素都可以随机进出 B. 都是操作受限的线性结构 C. 都是先进后出 D. 都是先进先出 2设有头指针为head的不带头结点的非空的单向循环链表, 指针p指向其尾结点, 要 删除第一个结点,则可利用下述语句 head=head-next;和（ ）。 Ap =head; Bp=NULL; Cp-next =head; Dhead=p;3.对一个栈顶指针为top的链栈进行入栈操作，通过指针变量 p生成入栈结点，则执 行：p=(struct node *)malloc(sizeof(struct

22、node); p-data=a; 和（ ）。 A. p-nex=top; top=p; B. top-next=p; p=top; C. top=top-next; p=top; D. p-next=top; p=top; 4. 以下说法正确的是( )。 A. 线性表的链式存储结构必须占用连续的存储空间 B. 一种逻辑结构可以有不同的存储结构 C一种逻辑结构只能有唯一的存储结构 D线性表的顺序存储结构不必占用连续的存储空间5.设头指针为head的非空的单向链表, 指针p指向尾结点,则通过以下操作( ) 可使其成为单向循环链表。 Ap-next = NULL ; Bhead = p; Cp-ne

23、xt=head ; Dp=head; 6把数据存储到计算机中，并具体体现( )称为物理结构。 A数据的处理方法 B数据的性质 C数据的运算 D. 数据元素间的逻辑关系7一种逻辑结构（ ）。 A只能有唯一的存储结构 B可以有不同的存储结构 C与存储该逻辑结构的计算机相关 D是指某一种数据元素的性质 8顺序表所具备的特点之一是（ ）。 A可以随机访问任一结点 B不需要占用连续的存储空间 C插入元素的操作不需要移动元素 D删除元素的操作不需要移动元素9把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（ ）。 A存储结构 B逻辑结构 C数据元素的存储 D. 给数据元素分配存储空间 10图状结构

24、中数据元素的位置之间存在（ ）的关系。 A一对一 B一对多 C多对多 D每一个元素都有一个直接前驱和一个直接后继11图状结构中数据元素的位置之间存在（ ）的关系。 A一对一 B一对多 C多对多 D每一个元素都有一个且只有一个直接前驱和一个直接后继 12元素20，14，16，18按顺序依次进栈，则该栈的不可能输出序列是（ ）（进栈出栈可以交替进行）。 A18，16，14，20 B20，14，16，18 C18，16，20，14 D14，20，18，16 13一个单链表中,在p所指结点之后插入一个s所指的结点时，可执行: s-next=p-next;和（ ）。 As= p-next ; Bp-ne

25、xt=s-next; Cp=s-next ; Dp-next=s; 14设有一个12阶的对称矩阵A(左上角第一个元素为a1,1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a5,4在一维数组B中的下标是（ ）。 A14 B12 C13 D11 15元素12，14，16，18顺序依次进栈，则该栈的不可能输出序列是（ ）。 （进栈出栈可以交替进行）。 A18，16，14，12 B12，14，16，18 C18，16，12，14 D14，12，18，16 16设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为（ ）。 A25 B14

26、 C15 D23 17设有一个30阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其 下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元 素a9,2在一维数组B中的下标是（ ）。 A41 B32 C18 D38 18在一棵二叉树中，若编号为5的结点存在右孩子，则右孩子的顺序编号为（ ）。 A12 B9 C11 D10 19设有一个长度为32的顺序表，要删除第8个元素需移动元素的个数为（ ）。 A15 B22 C14 D24 20一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有（ ）个结点。 A14 B15 C19 D18 21.在一棵二叉树中，若编

27、号为i的结点存在右孩子，则右孩子的顺序编号为（ ）。 A2i B2i-1 C2i+1 D2i+2 22 .如图1所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。 Aabcdfge Babcedfg Cacbfedg Dabcfgde gfabdec图1 23一棵具有16个结点的完全二叉树，共有（ ）层。(设根结点在第一层) A7 B5 C6 D4 24.字符串abcd321ABCD的子串是（ ）。 A. 21ABC B.abcABCD C. abcD D. 321a25如图2所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得 到的一种顶点序列为（ ）。 Aabecdfg Bacfebgd Caebcfgd Daedfcgb bdfecag图2 26.数组a经初始化char a =“English”; a1中存放的是（ ）。 A. 字符n B. 字符E C. n D. E27.字符串“DABcdabcd321ABC” 的子串是( )。 A. “cd32” B. “ABcD” C. “aBcd” D. “321a” 28如图3所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得 到的一种顶点序列为（ ）。 Aabec