数据结构期末综合练习20XX12月期末综合练习一一、单项选择题1 .单向链表所具备的特点是。A.可以随机访问任一结点 B.占用连续的存储空间 C.插入删除不需要移动元素 D.可以通过某结点的指针域访问其前驱结点 2.头指针为head的带头结点的单向链表为空的判定条件是为真。A. head= =NULL B. head-next= =NULLC. head-next=NULL; D. head-next!= NULL 3.设有一个长度为18的顺序表,要在第6个元素之前插入一个元素也就是插入元素作为新表的第6个元素,则移动元素个数为 。 A12 B5 C. 13 D6 4设有一个长度为32的顺序表,要删除第8个元素需移动元素的个数为 。 A9 B8 C25 D24 5栈和队列的共同特点是 。 A都是线性结构 B元素都可以随机进出C都是先进后出 D都是先进先出 6一个栈的进栈序列是2,4,6,8,10,则栈的不可能输出序列是 进栈出栈可以交替进行。A2,4,6,8,10 B8,6,10,2,4C8,10,6,4,2 D10,8,6,4,2 7元素1,3,5,7按顺序依次入队列,按该队列的出队序列进栈,该栈的可能输出序列是 进栈出栈可以交替进行。 A7,5,1,3 B7,3,1,5 C5,1,3,7 D7,5,3,1 8一个队列的入队序列是a,b,c,d,按该队列的可能输出序列使各元素依次入栈,该栈的可能输出序列是 。进栈出栈可以交替进行。 Ad,c,b,a Bc,a,b,d Cd,b,a,c Dd,a,b,c 9在一个不带头结点的链队中,假设f和r分别为队头和队尾指针,则对该队列进行出 队操作中并把结点的值保存在变量e中,其运算为e=fdata；和 。 Ar=rnext; Brnext=r; Cf=fnext; Dfnext=f; 10在一个链队中,假设f和r分别为队头和队尾指针,p指向一个已生成的结点,现要为 该结点的数据域赋值e,并使结点入队的运算为p-data=e; p-next=NULL ; 和 。A . f-next=p; f=p; B r-next=p;r=p; C p-next=r;r=p; D p-next=f;f=p; 11设有一个对称矩阵A,采用压缩存储的方式,将其下三角部分以行序为主序存储到一维数组B中数组下标从1开始,B数组共有45个元素,则该矩阵是 阶的对称矩阵。A15 B11 C10 D9 12设有一个24阶的对称矩阵A,采用压缩存储的方式矩阵的第一个元素为a1,1,将其下三角部分以行序为主序存储到一维数组B中数组下标从1开始,则数组中第30号元素对应于矩阵中的元素是 。Aa10,8 Ba9,2 C a8,2 Da8 ,5 13. 下列是C语言中abcd321ABCD的子串的选项是 。 A. 21ABC B.abcABCD C. abcD D. 321a 14. 字符串a1=BEIJING, a2 =BEI, a3= BEFANG a4=BEFI中最大的是 。A.a1 B. a2 C. a3 D. a4 15. 字符串a1=BEIJING, a2 =BEF , a3=BEFANG, a4=BEFI最小的是 .A. a1 B. a2 C. a3 D. a4 16.程序段char a =English; char *p=a; int n=0; while n+; p+; 结果中,n的值是 。 A. 6 B.8 C. 5 D.7 17一棵有20个结点采用链式存储的二叉树中,共有 个指针域为空。A21 B20 C19 D18 18在一棵二叉树中,若编号为5的结点存在左孩子,则左孩子的顺序编号为 。 A9 B10 C11 D12 19设一棵哈夫曼树共有18个叶结点,则该树有 个非叶结点。 A18 B19 C17 D16 20设一棵采用链式存储的二叉树,除叶结点外每个结点度数都为2,该树结点中共有20个指针域为空。则该树有 个叶结点。A21 B22 C9 D10 21如图1所示的一个图,若从顶点g出发,按深度优先搜索法进行遍历,则可能得到的一种顶点序列为 。 Agabecdf Bgacfebd Cgaebcfd Dgaedfcb bdfeCag 图122已知如图2所示的一个图,若从顶点a出发,按广度优先搜索法进行遍历,则可能得到的一种顶点序列为 。 Aabcedfg Babcefdg Caebcfdg Dacfdebg bdfecabdfecag 图223线性表以 方式存储,能进行折半查找。 A关键字有序的 B关键字有序的顺序C链接 D顺序 24在有序表10,23,32,36,53,66,68,76,87,90,101,120中,用折半查找值53时,经 次比较后查找成功。A6 B3 C8 D4 25有一个长度为8的有序表,按折半查找对该表进行查找,在等概率情况下查找成功的平均比较次数为 。A22/8 B20/8 C23/8 D21/8 26有一个长度为11的有序表,按折半查找对该表进行查找,在等概率情况下查找成功的平均比较次数为 。A29/11 B33/11 C26/11 D30/11 27. 排序算法中,从尚未排序序列中依次取出元素与已排序序列初始为空中的元素进行比较要求比较次数尽量少,然后将其放入已排序序列的正确位置的方法是 。 A折半插入排序 B直接插入排序 C归并排序 D选择排序 28设已有m个元素有序,在未排好序的序列中挑选第m+1个元素,并且只经过一次元素的交换就使第m+1个元素排序到位,该方法是 。 A堆排序 B简单选择排序 C快速排序 D归并排序 29排序方法中,从未排序序列中挑选元素,并将其依次放入已排序序列初始为空的一端的方法,称为 排序。 A堆 B冒泡 C选择 D快速 30一组记录的关键字序列为32,65,42,24,26,80,利用快速排序,以第一个关键字为分割元素,经过一次划分后结果为 。 A26,24,32,42,65,80 B24,26,32,42,65,80 C26,24,32,65,42,80 D26,24,32,80,42,65二、填空题1.广义表 a , , d , e , ,k 的长度是_ 。2.结构中的数据元素存在一对多的关系称为_结构。3.广义表的 c, a , , d , e , ,k 深度是_ 。4.栈的操作特点是_。5. 设顺序队列的类型为typedef struct ElemType dataMaxSise; int front,rear;Squeue;Squeue *sq; sq为指向顺序队列的指针变量,要进行新元素x的入队操作,按教课书约定,可用语句sq-datasq-rear=x;和_ 。6.广义表的 a , , d , e , ,k 深度是_。 7. 序列4,2,5,3,8,6,采用冒泡排序算法,经一趟冒泡后,序列的结果是_。按由小到大顺序 8. 广义表 , d , e , ,k 的长度是_ _。9.在对一组记录50,34,92,19,11,68,56,41,79进行直接插入排序 ,当把第7个记录56插入到有序表时,为寻找插入位置需比较_次。10. 设顺序队列的类型为typedef struct ElemType dataMaxSise; int front,rear;Squeue;Squeue *sq; sq为指向顺序队