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

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

2、*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 C6,1,10,1 D1,6,10,27. 在一个链队中，假设f和r分别为队头和队尾指针，p指向一个新结点,要为结点p 所指结点赋值x,并入队的运算为p-data=x; p-next=NULL;（ B

3、 ）。 A. f-next=p; f=p; B r-next=p;r=p; C r=p; p-next=r; 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.逻辑 B.存储 C.逻辑与存储 D.物理 10. 算法的时间复杂度与( A )有关。

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

5、为指针类型 14. 一种逻辑结构在存储时 （ C）。 A只要存储数据元素间的关系 B只能采用一种存储结构 C可采用不同的存储结构 D只要存储数据元素的值 15设有头指针为head的非空的单向链表, 指针p指向其尾结点, 要使该单向链表成为单向循环链表,则可利用下述语句（C ）。 Ap =head; Bp=NULL; Cp-next =head; Dhead=p; 16.单向链表所具备的特点是( C )。A.可以随机访问任一结点 B.占用连续的存储空间 C.插入删除不需要移动元素 D.可以通过某结点的指针域访问其前驱结点 17. 在线性表的顺序结构中，以下说法正确的是（C ）。 A逻辑上相邻的元

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

7、据元素间的移动。 C. 线性表采用链式存储，不必占用连续的存储空间。 D. 线性表采用链式存储，进行插入删除操作，不需要移动元素21 .设有一个长度为35的顺序表，要在第5个元素之前插入1个元素（也就是插入元素 作为新表的第5个元素），则移动元素个数为（B ）。 A30 B31 C. 5 D6 22 .设有一个长度为18的顺序表，要在第5个元素之前插入1个元素（也就是插入元素作为新表的第5个元素），则移动元素个数为（B ）。 A15 B14 C. 5 D6 23设有一个长度为40的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为（ C ）。 A11 B10 C30 D31 24设有

8、一个长度为25的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为（ C ）。 A10 B17 C15 D16 25设有一个25阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a7,5在一维数组B中的下标是（ C ）。A25 B24 C26 D27 26设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a10,8在一维数组B中的下标是（ D ）。A62, B63 C51 D53 27线性表在存储后,如果相关操作中有要求:利用已知的指向某结点的指

9、针或序号,访问该结点的前驱结点，则采用（A ）的存储方式是不可行的。 A单向链表 B双向链表 C单向循环链表 D顺序表 28在一个尾指针为rear的不带头结点的单循环链表中,插入一个s所指的结点,并作为第一个结点，可执行snext=rearnext ;和（ D ）。 A rearnext= snext; B rear =snext; C rear=s; D rearnext=s; 29在一棵二叉树中，若编号为i的结点存在左孩子,i结点的左孩子的顺序编号为（ B ）。 Ai/2.0 B2*i C2*i+1 Di+2 30在一棵二叉树中，若编号为15的结点是其双亲结点的右孩子，则双亲结点的顺序编号

10、为（D ）。 A30 B8 C31 D7 二、填空题1. 广义表( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) ) 的长度是_ 6_。 2. 结构中的元素之间存在一对多的关系是_树形_结构。3. 数据结构中，数据元素之间的抽象关系称为_逻辑_结构。 4. 结构中的元素之间存在多对多的关系是 _图状_结构 。5. 栈的操作特点是后进_先出_ 。 6. 循环队列的最大存储空间为MaxSize ,若队头指针front，队尾指针rear，采用少用一个 存储空间以有效地判断栈空或栈满，队空的判定条件为_ rear=front为真_ 。7. 广义表( b,a,c)

11、,c ,d , f , e ,( (i , j ) , k ) ) 的表头是_（b,a,c）_。 8. 广义表( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) ) 的长度是_ 6_。 9. 设有一个长度为18的顺序表 , 第8号元素到第18号元素依次存放的值为8,9,18. 某人想要删除第8号元素，程序中他的做法是用语句for(i=18;i=9;i-)ai-1=ai; 即从第18号元素开始, 直到第9号元素,每个元素依次向前(左)移动1个位置.事实上这 样做是错误的.其结果新表中第9号元素的值为_ 18 _。 10要求在n个数据元素中找值最大的元素，其基本

12、操作为元素间的比较。算法的时间复杂 度为_ O(n)_ 。11. 一棵二叉树,有1个2度结点,，2个1度结点，则该树共有 _ 5_个结点。12一棵有8个叶结点的二叉树，其1度结点的个数为3，则该树共有 _ 18_个结点。13设有一棵深度为5的完全二叉树，该树共有21个结点,第5层上有 6 个结点。 （根所在结点为第1层） 14.对于一棵具有n个结点的二叉树，其相应的链式存储结构中共有_ n+1_个指针域为空。 15中序遍历_二叉排序树 _树可得到一个有序序列。 16. 对一组记录（5，8，9，2，12，7，56，44，39）进行直接插入排序(由小到大排序) ，当把第6个记录7插入有序表，为寻找

13、插入位置需比较_ 4_次。 17. 序列12,10,13,11,16,14,采用冒泡排序算法,经一趟冒泡后,序列的结果是_ 10，12，11，13，14，16_。 （按升序排序） 18设有一棵深度为6的完全二叉树，第6层上有3个结点，该树共有_ 34_个结点。（根所在结点为第1层） 19. 对16个元素的序列用冒泡排序法进行排序，共需要进行_ 15_趟冒泡。 20一棵有16个叶结点的哈夫曼树，则该树共有_ 31_个结点。 21. 一棵有16个叶结点的哈夫曼树，则该树共有_ 15_个非叶结点。 22. 20个元素进行冒泡法排序，通常第6趟冒泡要进行_ _ 14_次元素间的比较。 23. 在对一组

14、记录（40，24，82，9，1，78，46，31，69）进行直接插入排序(由小到大排 序) ，当把第7个记录46插入到有序表时，为寻找插入位置需比较_3_次。24对稀疏矩阵进行压缩存储,可采用三元组表，一个6行7列的稀疏矩阵A共有38个零 元素，其相应的三元组表共有_4_个元素。 三、综合题1设有序表为(5, 8, 14, 15, 33, 51, 61, 73, 81, 82, 93) ,元素的序号依次为 1,2,3,，11. （1）画出对上述查找表进行折半查找所对应的判定树（树中结点可用序号表示） （2）说明成功查找到元素33需要经过多少次比较？ (3) 在等概率条件下, 给出成功查找的平均

15、查找长度（1）图4 51 14 81 5 15 61 82 8 33 73 93 (2) 4次 (3) ( 1+2*2+3*4+4*4)/11=33/11=32.设数据集合a=1,5,8,3,10,7,13,9（1）依次取a中各数据，构造一棵二叉排序树。（2）对该二叉树进行查找，成功查找到7要进行多少次元素间的比较？（3）给出对该二叉树中序遍历的序列。 (1) 图5 (2) 4次 (3) 中序遍历 1, 3 , 5 ,7 , 8 , 9 , 10 , 13 3dceabfhe图1(1)如图1所示,若从顶点a出发，首先经过c按图的深度优先搜索法进行遍历，给出可能得到的一种顶点序列。 (1) ac

16、dbfeh (2) 152364 或 152634 或 156234 (2)设有向图如图2所示下，写出首先删除顶点1的1种拓扑序列1234543465图2 4设有序表为(30, 48, 58, 70, 78, 79, 90) ,元素的序号依次为 1,2,3,，7.（1） 画出对上述查找表进行折半查找所对应的判定树（树中结点用序号表示）（2） 给出有序表中经3次比较成功查找到的所有元素(3) 说明不成功查找元素59需要经过多少次比较？（1）图6 70 48 79 30 58 78 90 (2) 30 58 78 90 (3) 3次5.(1) 设数据集合a=7,4,9,8,6,5,3,依次取a中各

17、数据，构造一棵二叉排序树。 (2)对该二叉树进行查找，成功查找到5要进行多少次元素间的比较？(3) 给出对上述二叉排序树进行中序遍历的序列 (1) 图7 (2) 4(3) 3,4,5,6,7,8,9 6(1) 如图3所示，若从顶点a出发，首先经过c按广度优先搜索法进行遍历，给出可能得 到的一种顶点序列。 （2）同图3所示, 若从顶点h出发，按深度优先搜索法进行遍历，给出可能得到的2种顶点 序列。a阿decfhecdeccdeceec图3 (3) 一组记录的关键字序列为（75，63，95，80，53，45，38，20），利用堆排序的方法建立小根堆(堆顶元素是最小元素）,给出按筛选法建立的的初始堆

18、。 (1) acefdh (2) hdeacf hdfcae （3） 20, 53，38，63，75，45，95，80 四、程序填空题1以下函数在a0到an-1中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格typedef struct int key;NODE;int Binary_Search(NODE 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(

19、_(3)_) low=mid+1; else _(4)_; _(5)_; (1) low=high (2) mid (3) amid.key k (4) high=mid -1 (5) return -12以下函数为直接选择排序算法，对a1,a2,an中的记录进行直接选择排序 ，完成程序中的空格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+1; _(2)_; j+) if(aj.keyak.key) _(3)_;

20、if(i!=k) temp=ai;_(4)_; _(5)_; (1) n-1 (2) jdata=x; _ (2)_; _(3)_; (1) sizeof(struct node)(2) pnext=top (3) top=p4.以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、 rear分别是链队列的队头、队尾指针struct node ElemType data;struct node *next;struct node *front，*rear; void InQueue(ElemType x) struct node *p; p= (struct node*) _(

21、1)_; p-data=x; p-next=NULL; _(2)_; ; rear= _(3)_; (1) malloc(sizeof(struct node) (2) rear-next=p; (3) rear=p;综合练习二一、单项选择题 1. 对稀疏矩阵进行压缩存储,可采用三元组表，一个有10 行的稀疏矩阵A共有97个零元素，其相应的三元组表共有3个元素。该矩阵A有( D )列。 A8 B9 C7 D10 2 .单向链表所具备的特点是( C )。A.可以随机访问任一结点 B.占用连续的存储空间 C.插入删除不需要移动元素 D.可以通过某结点的指针域访问其前驱结点 3. 子串“acd”在主

22、串 “abdcacdefac”中的位置是( B ) 。 A3 B5 C7 D1 4 .设有一个长度为18的顺序表，要在第6个元素之前插入一个元素（也就是插入元素作为新表的第6个元素），则移动元素个数为（ C ）。 A12 B5 C. 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. 在一个不带头

23、结点的链队中，假设f和r分别为队头和队尾指针，对该队列进行出队 操作,并把结点的值保存在变量e中,其运算为（ C ）。 Ae=f-data；r=r-next; Be=f-data；r-next=r; Ce=f-data；f=f-next; De=f-data；f-next=f; 8元素1，3，5，7按顺序依次入队列，按该队列的出队序列进栈，该栈的可能输出序列是（ D ）（进栈出栈可以交替进行）。 A7，5，1，3 B7，3，1，5 C5，1，3，7 D7，5，3，1 9. 数据的逻辑结构在计算机内存中的表示是( B )。 A.给相关变量分配存储单元 B.数据的存储结构 C.数据的逻辑结构 D.

24、算法的具体体现 10在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，则对该队列进行出队操作中并把结点的值保存在变量e中,其运算为e=fdata；和（ C ）。 Ar=rnext; Brnext=r;Cf=fnext; Dfnext=f 11. 以下说法正确的是( B )。 A. 线性表的链式存储结构必须占用连续的存储空间 B. 一种逻辑结构可以有不同的存储结构 C一种逻辑结构只能有唯一的存储结构 D线性表的顺序存储结构不必占用连续的存储空间 12设有一个对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），B数组共有45个元素,则该矩阵是（

25、 D ）阶的对称矩阵。A15 B11 C10 D9 13在一个单链表中要删除p所指结点的后继结点，可执行q=p-next; 和（ A ）。 Ap-next=q-next ; Bp=q-next; Cp-next=q; Dp-next=q; 14. 下列是C语言中abcd321ABCD的子串的选项是（ A ）。 A. 21ABC B.abcABCD C. abcD D. 321a 15. 在数据结构和算法中，与所使用的计算机有关的是 （ B ）。 A数据元数间的抽象关系 B数据的存储结构 C算法的时间复杂度 D数据的逻辑结构 16. 字符串a1=BEIJING, a2 =BEF , a3= BE

26、FANG, a4=“BEFI最小的是（ B ）.A. a1 B. a2 C. a3 D. a4 17. 以下表中可以随机访问的是（ D ）。 A单向链表 B双向链表 C单向循环链表 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 ）个非叶结点。

27、A18 B19 C17 D16 21 .设有一个长度为32的顺序表，要在第5个元素之前插入1个元素（也就是插入元素 作为新表的第5个元素），需移动元素个数为（ B ）。 A25 B28 C. 5 D6 22如图1所示的一个图，若从顶点g出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（D ）。 Agabecdf Bgacfebd Cgaebcfd Dgaedfcb bdfeCag 图1 23设有一个长度为33的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数 为（ C ）。 A11 B10 C23 D14 24线性表以（ B ）方式存储，能进行折半查找。 A关键字有序的 B

28、关键字有序的顺序 C链接 D顺序 25设有一个28阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序 存储到一维数组B中（数组下标从1开始），则数组中第26号元素对应于矩阵中的元素是（ A ）。 Aa7,5 , Ba7,6 Ca6,5 Da7,4 26有一个长度为8的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（ D ）。A22/8 B20/8 C23/8 D21/8 27. 在一个不带头结点的单循环链表中，p、q分别指向表中第一个结点和尾结点，现要 删除第一个结点，且p、q仍然分别指向新表中第一个结点和尾结点。可用的语句是 p=p-next;和（ D

29、）。 Ap=q-next; Bp-next=q ; C q=p; D q-next=p; 28. 排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（A ）。 A折半插入排序 B直接插入排序 C归并排序 D选择排序 29在一棵二叉树中，若编号为16的结点是其双亲结点的左孩子，则他的双亲结点的顺序编号 为（ B ）。 A7 B8 C32 D33 30排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端的方法，称为（ C ）排序。 A堆 B冒泡 C选择 D快速 二、填空题1.数据

30、的逻辑结构在计算机中的表示称为_物理 (存储)_结构。 2.结构中的数据元素存在一对多的关系称为_树形_结构。3.四类基本结构分别为_ 集合 线性 树形 图状 _结构。 4.栈的操作特点是_先进后出_。5.队列的操作特点是先进_先出_。 6.广义表的( a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_ 3 _。7.广义表( (b,a,c) , c,d ,( e ,i ,j ,k ) )的表尾是_ (c,d,(e,i,j,k)_。 8.广义表( (a ,b) , d , e ,( (i ,j ) ,k ) )的长度是_ 4 _。 9.设有一个长度为20的顺序表 ,

31、 第8号元素到第20号元素依次存放的值为8,9,20。 某人想要在第8号元素前插入1个元素7（也就是插入元素作为新表的第8个元素），程 序中他的做法是用语句for(i=8;idatasq-front;和_ sq-fronf+;_ 。 11设有一棵有38个结点的完全二叉树，该树共有_ 6 _层。（根所在结点为第1层）12. 设顺序队列的类型为typedef struct ElemType dataMaxSise; int front,rear;Squeue;Squeue *sq; sq为指向顺序队列的指针变量，要进行新元素x的入队操作，按教课书约定,可用语句sq-datasq-rear=x;和_

32、 sq-rear+;_。 13 一棵有18个结点的二叉树，其2度结点数的个数为8，则该树共有 _ 1_个1度结点。 14. 序列14,12,15,13,18,16,采用冒泡排序算法,经一趟冒泡后,序列的结果是_ 12,14,13,15,16,18_。（由小到大排序）15. 对一组记录（1，3，9，2，12，7，5，4，6）进行直接插入排序(由小到大排序) ，当把第6个记录7插入有序表，为寻找插入位置需比较_ 3_次。 16. 数据结构中, _数据元素_ 之间的抽象关系称为逻辑结构。 17. 序列5,3,8,4,7,6,采用冒泡排序算法,经一趟冒泡后,序列的结果是_ 3,5,4,7,6,8_。(

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

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

35、10,12 , 13 , 14 , 15 , 17 , 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设有序表为(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)