数据结构(本)期末综合练习(2015年

1、 数据结构(本)期末综合练习) 月11年(2015 数据结构（本）期末综合练习 2015年11月 综合练习一 一、单项选择题 1.对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A共有73 个零元素，其相应的三元组表共有( C )个元素。 A8 B80 C7 10 D可采用三元组对稀疏矩阵进行压缩存储,2. ，其相应的8表，一个10 行列的稀疏矩阵A共有个元素，矩阵 三元组表共有6A ( C )个零元素。74 72 C8 B A D10 abcd321ABCD“”的子串。字符串3.( A )是 C. B. “21AB”“”abcDA. 321a D. aBCD“”“” 4 .

2、 程序段 ; char a =abdcacdef“” 2 char *p=a; int n=0; while( *p!=0) n+; p+; 结果中,n的值是（ D ）。 A. 6 B.8 C. 7 D.9 5.栈和队列的共同特点是（ A ）。 A都是操作受限的线性结构 B元素都可以随机进出 C都是先进后出 D都是先进先出 按顺序依次进栈，该队列的可 6. 10,6,2,1 ）。能输出序列是（ A 进栈出栈可以交替进行）。 ( A6,10,1,2 B2,10,6,1 1,6,10,2 C6,1,10,1 D分别为队头和r在一个链队中，假设7. fp ,和队尾指针，p指向一个新结点要为结点为算入

3、x,值并队的运赋结所 指点 ）。 B p-data=x; p-next=NULL;（ A. f-next=p; f=p; B r-next=p;r=p; p-next=r; Cr=p; 3 D p-next=f;f=p; 8. 对一个栈顶指针为top的链栈进行出栈操作，用变量e保存栈顶元素的值 ，则执行 ( B ）。 Ae= top-next; top-data=e; Be=top-data; top=top-next; Ctop=top-next; e=top-data; Dtop=top-next; e=data; 9. 数据结构中，与所使用的计算机无关的是数据的( A ) 结构。 A.逻

4、辑 B.存储 C.逻辑与存储 D.物理 10. 算法的时间复杂度与( A )有关。 A. 算法本身 B. 所使用的计算机 C. 算法的程序设计 D. 数据结构 11顺序表所具备的特点之一是（ A ）。 点结一任问访机随以可 A B不需要占用连续的存储空间 的元插 C入素操素元移要需作不动 删除元素的操作不需要移动元素D 4 12在一个单向链表中,在p所指结点之后插入一个s所指的结点时，可执行 s-next=p-next; 和（ D ）。 Ap= s; B p-next=s-next; p=s-next C p-next=s; D它，数数据元素是据的基本单位13. （ C ）。 A只能有一个数据

5、项组成 至少有二个数据项组成 B可以是一个数据项也可以由若干个数据 C 项组成 至少有一个数据项为指针类型 D 。（14. 一种逻辑结构在存储时 C）只 A只要存储数据元素间的关系 B 能采用一种存储结构只 DC可采用不同的存储结构 要存储数据元素的值指的非空的单向链表, head15设有头指针为要使该单向链表成为单针p, 指向其尾结点 C ,向循环链表则可利用下述语句（。） 5 Ap =head; Bp=NULL; Cp-next =head; Dhead=p; 16.单向链表所具备的特点是( C )。 A.可以随机访问任一结点 B.占用连续的存储空间 C.插入删除不需要移动元素 D.可以通

6、过某结点的指针域访问其前驱结点 17. 在线性表的顺序结构中，以下说法正确的是（C ）。 A逻辑上相邻的元素在物理位置上不一定相邻 B数据元素是不能随机访问的 C逻辑上相邻的元素在物理位置上也相邻 进行数据元素的插入、删除效率较高 D 18.数据结构在计算机内存中的表示是指 ( B ) 。数据数据元素之间的关系 B A 的存储结构数据 D C数据元素的类型 的逻辑结构 A , 19.对链表以下叙述中正确的是（）。 6 A不能随机访问任一结点 B结点占用的存储空间是连续的 C插入删除元素的操作一定要要移动结 点 D可以通过下标对链表进行直接访问 20.下面关于线性表的叙述中,错误的是( B )。

7、 A . 线性表采用顺序存储,必须占用一片连续的存储空间。 B. 线性表采用顺序存储,进行插入和删除操作,不需要进行数据元素间的移动。 C. 线性表采用链式存储，不必占用连续的存储空间。 D. 线性表采用链式存储，进行插入删除操作，不需要移动元素 21 .设有一个长度为35的顺序表，要在第5个元素之前插入1个元素（也就是插入元素 作为新表的第5个元素），则移动元素个数为（B ）。 A30 B31 C. 5 D6 22 .设有一个长度为18的顺序表，要在第5个元素之前插入1个元素（也就是插入元素 7 作为新表的第5个元素），则移动元素个数为（B ）。 A15 B14 C. 5 D6 23设有一个

8、长度为40的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为（ C ）。 A11 B10 C30 D31 24设有一个长度为25的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为（ C ）。 A10 B17 C15 D16 25设有一个25阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素在一维数组B中的下标是（ C ）。 a7,5A25 B24 C26 D27 26设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素在一维数组B中的

9、下标是（ D ）。 a10,8A62 B63 , 8 C51 D53 27线性表在存储后,如果相关操作中有要求:利用已知的指向某结点的指针或序号,访问 该结点的前驱结点，则采用（A ）的存储方式是不可行的。 A单向链表 B双向链表 C单向循环链表 D顺序表 28在一个尾指针为rear的不带头结点的单循环链表中,插入一个s所指的结点,并作为第一个结点，可执行s?next=rear?next ;和（ D ）。 A rear?next= s?next; next; rear =s?Brear=s; C rearD?next=s; 的结点存29在一棵二叉树中，若编号为i结点的左孩子的顺序编号为,i在左

10、孩子 ）。（ B 2*i Ai/2.0 Bi+2 C2*i+1 D的结点是若编号为30在一棵二叉树中，15则双亲结点的顺序编号为其双亲结点的右孩子， 9 （D ）。 A30 B8 C31 7 D 二、填空题的长( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) ) 1. 广义表 。度是_ 6_ _2. 结构中的元素之间存在一对多的关系是 树形_结构。数据结构中，数据元素之间的抽象关系称为3. _逻辑结构。 _ 4. 结构中的元素之间存在多对多的关系是 图状_。结构 。 _先出_栈的操作特点是后进5. 若队头6. 循环队列的最大存储空间为MaxSize , r

11、ear，采用少用一个，队尾指针指针front队空的判 存储空间以有效地判断栈空或栈满， _ 。为真定条件为_ rear=front的表7. 广义表( b,a,c) ,c ,d , f , e ,( (i , j ) , k ) ) 。）（_头是b,a,c_的长( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) ) 广义表8. _ 6_度是。号元素的顺序表18设有一个长度为9. 8 , 第 10 ,18. 18号元素依次存放的值为8,9,到第号元素，程序中他的做法8 某人想要删除第for(i=18;i=9;i-)ai-1=ai; 是用语句 每,9号元素, 即从

12、第18号元素开始直到第 事实上这个位置.(左)移动1个元素依次向前号元素的9.其结果新表中第 样做是错误的值为_ 18 _。 其个数据元素中找值最大的元素，要求在n10 基本操作为元素间的比较。算法的时间复杂 。度为 _ O(n)_ 度结点，1个1个2度结点,，2有11. 一棵二叉树, 个结点。则该树共有 _ 5_度结点的112一棵有8个叶结点的二叉树，其 个数为3，则该树共有 _ 18_个结点。该树共有13设有一棵深度为5的完全二叉树， 6 第21个结点,5个结点。层上有 层）1（根所在结点为第 个结点的二叉树，其相应的对于一棵具有14.n个指针域为n+1_ 链式存储结构中共有 空。 树可得

13、到一 二叉排序树_15 中序遍历_ 个有序序列。 11 ，56，44，12，7，216. 对一组记录（5，8，9，当把第由小到大排序) ，39）进行直接插入排序(插入有序表，为寻找插入位置需比较个记录76 _ 4_次。经采用冒泡排序算法,17. 序列12,10,13,11,16,14,，13，12，11一趟冒泡后,序列的结果是_ 10 16_。14， （按升序排序） 层上的完全二叉树，第618设有一棵深度为6（根_ 34_个结点。有3个结点，该树共有 层） 1所在结点为第个元素的序列用冒泡排序法进行排序，对1619. 共需要进行_ 15_趟冒泡。个叶结点的哈夫曼树，则该树共一棵有1620 有_

14、 31_个结点。个叶结点的哈夫曼树，则该树共1621. 一棵有 个非叶结点。 有_ 15_趟冒20个元素进行冒泡法排序，通常第622. _ _ 14_次元素间的比较。 泡要进行 23. 在对一组记录（40，24，82，9，1，78，46，31，69）进行直接插入排序(由小到大排 序) ，当把第7个记录46插入到有序表时， 12 为寻找插入位置需比较_3_次。 24对稀疏矩阵进行压缩存储,可采用三元组表，一个6行7列的稀疏矩阵A共有38个零 元素，其相应的三元组表共有_4_个元素。 三、综合题 1 设有序表为(5, 8, 14, 15, 33, 51, 61, 73, 81, 82, 93) ,

15、元素的序号依次为 1,2,3,，11. （1）画出对上述查找表进行折半查找所对应的判定树（树中结点可用序号表示） （2）说明成功查找到元素33需要经过多少次比较？ (3) 在等概率条件下, 给出成功查找的平均查找长度 （1）图4 51 14 81 13 5 15 61 82 73 33 8 93 次 (2) 4 (3) ( 1+2*2+3*4+4*4)/11=33/11=3 2. a=1,5,8,3,10,7,13,9 设数据集合 依次取1（）a中各数据，构造一棵二叉排序树。要进成功查找到7对该二叉树进行查找，2（） 行多少次元素间的比较？ 3（）给出对该二叉树中序遍历的序列。5 (1) 图

16、(2) 4次 1, 3 , 5 ,7 , 8 , 9 , 10 , 13 (3) 中序遍历 14 3a出发，首先经过c1所示,按若从顶点如图(1)图的深度优先搜索法进行遍历，给出可能得到a 的一种顶点序列。 he c d b f 图 1 (1) acdbfeh 156234 152634 或(2) 152364 或 写出首先删除顶点所示下，2设有向图如图(2) 1的1种拓扑序列 15 4 3 2 1 65 图 2 4(30, 48, 58, 70, 78, 79, 90) ,设有序表为7. ，元素的序号依次为 1,2,3,画出对上述查找表进行折半查找所对应的） （1 判定树（树中结点用序号表示

17、）次比较成功查找到的所给出有序表中经32） （ 有元素需要经过多少次59(3) 说明不成功查找元素 比较？ 6 ）图（170 16 48 79 30 58 78 90 (2) 30 58 78 90 (3) 3次 5. (1) 设数据集合a=7,4,9,8,6,5,3,依次取a中各数据，构造一棵二叉排序树。 (2)对该二叉树进行查找，成功查找到5要进行多少次元素间的比较？ (3) 给出对上述二叉排序树进行中序遍历的序列 (1) 图7 17 4 (2) 3,4,5,6,7,8,9 (3) 6出发，首先经过所示，若从顶点a(1) 如图3 c按广度优先搜索法进行遍历，给出可能得 到的一种顶点序列。

18、出发，按深度优h, 若从顶点（2）同图3所示 种顶点先搜索法进行遍历，给出可能得到的2 序列。 a ce fh 18 3 图 (3) 一组记录的关键字序列为（75，63，95，80，53，45，38，20），利用堆排序的方法建立小根堆(堆顶元素是最小元素）,给出按筛选法建立的的初始堆。 (1) acefdh (2) hdeacf hdfcae （3） 20, 53，38，63，75，45，95，80 四、程序填空题中，用折半查找到1以下函数在a0an-1的记录，查找成功k算法查找关键字等于，完成返回该记录的下标，失败时返回-1 程序中的空格struct typedef key; int NOD

19、E; int Binary_Search(NODE 19 a,int n, int k) int low,mid,high; low=0; high=n-1; while(_(1)_) mid=(low+high)/2; if(amid.key=k) return _(2)_; else if(_(3)_) low=mid+1; else _(4)_; _(5)_; (1) low=high (2) mid (3) amid.key k (4) high=mid -1 (5) return -1 20 2以下函数为直接选择排序算法，对a1,a2,an中的记录进行直接选择排序 ，完成程序中的空格

20、 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; ; j+) _(2)_ for(j=i+1; if(aj.keyak.key); _(3)_ if(i!=k) emp=ai; t ; _(4)_ ; _(5)_ 21 (1) n-1 (2) jdata=x; _ (2)_; ; _(3)_ 22 (1) sizeof(struct node) (2) pnext=top (3) top=p 4.以下函数为链队列的入队操作，x为要入

21、队的结点的数据域的值，front、 rear分别是链队列的队头、队尾指针 struct node ElemType data; struct node *next; ; struct node *front，*rear; void InQueue(ElemType x) struct node *p; p= (struct node*) ; _(1)_ p-data=x; p-next=NULL; ; ; _(2)_ 23 rear= _(3)_; (1) malloc(sizeof(struct node) (2) rear-next=p; (3) rear=p; 综合练习二 一、单项选择题

22、 1. 对稀疏矩阵进行压缩存储,可采用三元组表，一个有10 行的稀疏矩阵A共有97个零元素，其相应的三元组表共有3个元素。该矩阵A有( D )列。 A8 B9 C7 D10 2 .单向链表所具备的特点是( C )。 A.可以随机访问任一结点 B.占用连续的存储空间 C.插入删除不需要移动元素 D.可以通过某结点的指针域访问其前驱结点 3. 子串“acd”在主串 “abdcacdefac”中的位置是( B ) 。 24 A3 B5 C7 D1 4 .设有一个长度为18的顺序表，要在第6个 元素之前插入一个元素（也就是插入元素作为新表的第6个元素），则移动元素个数为（ C ）。 A12 B5 C.

23、 13 D6 5. 序列12,16,8,4按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的不可能输出序列是（ B ）。 (进栈、出栈可以交替进行）。 A16,12,8,4 B4,8,12,16 C8,4,16,12 D16,12,4,8 6栈和队列的共同特点是（ A ）。 A都是线性结构 B元素都可以随机进出 C都是先进后出 D都是先进先出 7. 在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，对该队列进行出队 25 操作,并把结点的值保存在变量e中,其运算为（ C ）。 Ae=f-data；r=r-next; r-next=r; ；Be=f-dataf=f-next; ；

24、Ce=f-dataf-next=f; e=f-data；D按顺序依次入队列，按，71，3，5 8元素该栈的可能输出序该队列的出队序列进栈， 。（进栈出栈可以交替进行）列是（ D ），37， A7，51，3 B5 1，53，7 D71C5，1 ，3数据的逻辑结构在计算机内存中的表示9. ( B )是。 A.给相关变量分配存储单元 B.数据的存储结构 数据的逻辑结构 C. D.算法的具体体现 10在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，则对该队列进行出队 26 操作中并把结点的值保存在变量e中,其运算为e=f?data；和（ C ）。 Ar=r?next; Br?next=r;

25、Cf=f?next; Df?next=f 11. 以下说法正确的是( B )。 A. 线性表的链式存储结构必须占用连续的存储空间 B. 一种逻辑结构可以有不同的存储结构 C一种逻辑结构只能有唯一的存储结构 D线性表的顺序存储结构不必占用连续的存储空间 12设有一个对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），B数组共有45个元素,则该矩阵是（ D ）阶的对称矩阵。 A15 B11 C10 D9 13在一个单链表中要删除p所指结点的后继结点，可执行q=p-next; 和（ A ）。 27 Ap-next=q-next ; Bp=q-next;

26、p-next=q; C p-next=q; D的子串的abcd321ABCDC语言中14. 下列是 。 A ）选项是（ B.21ABC A. abcABCD C. abcD D. 321a与所使用的计算机有15. 在数据结构和算法中， 。（ B ） 关的是数据 B A数据元数间的抽象关系 的存储结构数据 D C算法的时间复杂度 的逻辑结构 , , a2 =BEFa1=16. 字符串BEIJING是的a4=“BEFI最小 a3= BEFANG, . ） B （A. a1 B. 28 a2 C. a3 D. a4 17. 以下表中可以随机访问的是（ D ）。 A单向链表 B双向链表 C单向循环链表

27、 D顺序表 18一棵有20个结点采用链式存储的二叉树中，共有（ A ）个指针域为空。 A21 B20 C19 D18 19.头指针为head的不带头结点的单向链表为空的判定条件是逻辑表达式( A )为真。 A. head= =NULL B. head-next= =NULL C. head-next=NULL D. head-next!= NULL 20设一棵哈夫曼树共有18个叶结点，则该树有（ C ）个非叶结点。 A18 B19 C17 D16 21 .设有一个长度为32的顺序表，要在第5个 29 1个元素（也就是插入元素元素之前插入需移动元素个数个元素）， 作为新表的第5 。）为（ B 6

28、 28 C. 5 D A25 B按出发，所示的一个图，若从顶点g22如图1则可能得到的一种顶深度优先搜索法进行遍历， 。D ）点序列为（gacfebd B Agabecdf gaedfcb Cgaebcfd Dg a C b e f d 1 图的顺序表，要删除第 23设有一个长度为33 )需移动元素的个数开始个元素10(下标从1 。 为（ C ）14 23 D10 C11 B A）方式存储，能进行折半 24 B 线性表以（ 30 查找。 A关键字有序的 B关键字有序的顺序 C链接 D顺序 25设有一个28阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序 存储到一维数组B中（数组下

29、标从1开始），则数组中第26号元素对应于矩阵中的元素是（ A ）。 A B aa, 7,67,5 C D aa7,46,526有一个长度为8的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（ D ）。 A22/8 B20/8 C23/8 D21/8 27. 在一个不带头结点的单循环链表中，p、q分别指向表中第一个结点和尾结点，现要 删除第一个结点，且p、q仍然分别指向新表中第一个结点和尾结点。可用的语句是 p=p-next;和（ D ）。 Ap=q-next; Bp-next=q ; C q=p; 31 D q-next=p; 28. 排序算法中，从尚未排序序列中依次

30、取出元素与已排序序列（初始为空）中的元素进行 比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（A ）。 A折半插入排序 B直接插入排序 C归并排序 D选择排序 29在一棵二叉树中，若编号为16的结点是其双亲结点的左孩子，则他的双亲结点的顺序编号 为（ B ）。 32 8 CB7 A33 D排序方法中，从未排序序列中挑选元素，并30的一将其依次放入已排序序列（初始为空） ）排序。 C 端的方法，称为（ 堆 A B冒泡 C选择 D快速 二、填空题物数据的逻辑结构在计算机中的表示称为1._ 存储 理()_ 结构。 32 _2.结构中的数据元素存在一对多的关系称为 _结构。树形树

31、线性 _ 集合 3.四类基本结构分别为 _结构。 形 图状 _。栈的操作特点是4._先进后出 。_先出_队列的操作特点是先进5.深度是( a , (a ,b) , d , e ,( (i ,j ) ,k ) )6.广义表的 _ 3 _。_ 7.广义表( (b,a,c) , c,d ,( e ,i ,j ,k ) )的表尾是 (c,d,(e,i,j,k)_。 的长度是,k ) ),j (a 8.广义表( ,b) , d , e ,( (i ) _ 4 _。 号元素到第89.设有一个长度为20的顺序表 , 。第20号元素依次存放的值为8,9,20也 某人想要在第8号元素前插入1个元素7（ 个元素）

32、，程就是插入元素作为新表的第8句是用语的 序中他做法即从for(i=8;idatasq-front;书约定 。 _ sq-fronf+;_ 个结点的完全二叉树，该树11设有一棵有38 1层）共有_ 6 _层。（根所在结点为第typedef struct 12. 设顺序队列的类型为ElemType dataMaxSise; front,rear; int Squeue; Squeue *sq; 为指向顺序队列的指针变量，要进行新元 sq 可用语句的入队操作，按教课书约定素x,和_ sq-datasq-rear=x; 34 sq-rear+;_。 13 一棵有18个结点的二叉树，其2度结点数的个数

33、为8，则该树共有 _ 1_个1度 结点。 经采用冒泡排序算法序列14. 14,12,15,13,18,16,_ 果是结,趟一冒泡后序列的 12,14,13,15,16,18_。（由小到大排序），6471223115. 对一组记录（，9，5，当把第进行直接插入排序(由小到大排序) 插入有序表，为寻找插入位置需7个记录6 _ 3_比较次。 之间的抽16. 数据结构中_ 数据元素, _ 象关系称为逻辑结构。 经一5,3,8,4,7,6,17. 序列采用冒泡排序算法, 果是_结列,后泡趟冒序的 3,5,4,7,6,8_。) 按升序排序(分别为队头和rear和front18. 循环队列中，设判断循环最多

34、元素为(队尾指针，MaxSize,),为队列为空的条件为_ front= =rear_ 真。的长度19. 广义表(b,a , (c ,b) , f , e ,( (i ,j ) ,k ) ) 35 是_ 6_ 。 从尚未排序序列中依次取出元20. 排序算法中，中的元素进行素与已排序序列（初始为空） ，然后将其放比较（要求比较次数尽量少）折半入已排序序列的正确位置的方法是 。插入排序 21 一棵有18个叶结点的哈夫曼树，则该树共有_ 17_个非叶结点。 22. 对稀疏矩阵进行压缩存储,可采用三元组表,矩阵元素对应的三元组为_ (3,4, a 3,4a3,4)_ 。 23对稀疏矩阵进行压缩存储,可

35、采用三元组表，一个8行7列的稀疏矩阵A共有51个零元 素，其相应的三元组表共有_ 5_个元素 24在双向链表中，要删除p所指的结点，其中所用的一条语句（p-next）-prior=p-prior; 的功能是：使P所指结点的直接后继的左指针指向_ P所指结点的直接前驱_。 三、综合题1. 36 设数据集合a=6,17,10,13,8,15,12,18,14 （1）依次取a中各数据，构造一棵二叉排序树。 （2）给出对该二叉树中序遍历的序列 （3）对该二叉树进行查找，成功查找到14要进行多少次元素间的比较？ 图2 37 (2)中序遍历 6 , 8 ,10,12 , 13 , 14 , 15 , 17

36、 , 18 (3) 6次 2.设数据集合a=62,74,30,15,56,48 （1）依次取a中各数据，构造一棵二叉排序树。 （2）对该二叉树进行查找，不成功查找有多少种可能？画出不成功查找树的示意图。 （3）不成功查找的平均查找长度是多少? （4）为了成功查找到48需要进行多少次元素间的比较? （5）给出对该二叉树后序遍历的序列。 (1)图3 (2)图4 7种可能 (3)(2*2+3*3+4*2)/7=21/7 (4)4次 (5)15,48,56,30,74,62 3 38 设有序表为(2, 5, 11, 12, 30, 48, 58) ,元素的序号依次为 1,2,3,，7. （1）画出对上述查找表进行折半查找所对应 的判定树（树中结点用序号表示） （2）说明成功查找到元素11需要经过多少次比较？ (3) 在等概率条件下, 给出成功查找的平均查找长度 （1）图5 (2) 3次 (3) ( 1+2*2+3*4)/7=17/7 39 4设有序表为（3，9，15，26，38，41，53，74，81，96，97，99），元素的 序号依 次为1,2,12。 （1）说出有哪几个元素需要经过