发布时间 : 星期六 文章数据结构（本）期末综合练习2016年6月更新完毕开始阅读
2.(1) low<=high (2) mid;
(3) a[mid].key (5) 不能，因为不是有序序列，不能用折半查找 3． （1）j<=n-1 （2）i<=n-j （3）a[i]=a[i+1] （4）a[i+1]=temp （5）4,5,2,1,6,8 4. （1） Inorder(BT->left) （2） printf(“%c”,BT->data) （3）f,d,e,b,c,a 练习三 一、单项选择题 1.对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A共有73 个零元素，其相应的三元组表共有( )个元素。 A．8 B．80 C．7 D．10 2. 对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A共有73 个零元素，A的右下角元素为6，其相应的三元组表中的第7个元素是( )。 A．（10，8，6） B．（10，8，7） C．（7，10，8） D．（7，8，10 ） 3.字符串( )是“abcd321ABCD”的子串。 A. “21AB” B. “abcD” C. “aBCD” D. “321a” 4. 字符串 a1=〝CDEIJING〞, a2 =〝CDEI〞 , a3= 〝CDEFANG〞 a4=〝CDEFI〞 中最大的是（ ）。 A. a4 B. a2 C. a3 D.a1 5.栈和队列的共同特点是（ ）。 A．都是操作受限的线性结构 B．元素都可以随机进出 第21页 C．都是先进后出 D．都是先进先出 6. 序列12,8,4,3按顺序依次进栈，该队列的不可能输出序列是（ ）。 (进栈出栈可以交替进行）。 A．8,12,3,4 B．12,8,4,3 C．3,4,8,12 D．3,4,12,8 7. 在一个链队中，假设f和r分别为队头和队尾指针，p指向一个新结点,要为结点p 所指结点赋值x,并入队的运算为p->data=x; p->next=NULL;（ ）。 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的链栈进行入栈操作，通过指针变量p生成入栈结点,并给该 结点赋值a,则执行: p=(struct node *)malloc(sizeof(struct node);p->data=a; 和( ）。 A. p->nex=top; top=p; B．top->next=p; p=top; C．top=top->next; pe=top; D．p->next=top; p=top; 9. 数据结构中，与所使用的计算机无关的是数据的( ) 结构。 A.逻辑 B.存储 C.逻辑与存储 D.物理 10. 数据的存储结构包括数据元素的表示和（ ） A . 数据处理的方法 B.相关算法 C . 数据元素间的关系的表示 D. 数据元素的类型 11．顺序表所具备的特点之一是（ ）。 A．可以随机访问任一结点 B．不需要占用连续的存储空间 C．插入元素的操作不需要移动元素 D．删除元素的操作不需要移动元素 12. 头指针为head的带头结点的单向链表为空的判定条件是( )为真。 A. head= =NULL B. head->next!=NULL C. head->next= =NULL D. head->next!= NULL 13. 数据元素是数据的基本单位，它（ ）。 A．只能有一个数据项组成 B．至少有二个数据项组成 C．可以是一个数据项也可以由若干个数据项组成 D．至少有一个数据项为指针类型 14 .下面关于线性表的叙述中,错误的是( )。 A. 线性表采用顺序存储,必须占用一片连续的存储空间 B. 线性表采用顺序存储,进行插入和删除操作,不需要进行数据元素间的移动 C. 线性表采用链式存储，不必占用连续的存储空间 D. 线性表采用链式存储，进行插入删除操作，不需要移动元素 15．设有头指针为head的非空的单向链表, 指针p指向其尾结点, 要使该单向链表成为单向循环链表,则可利用下述语句（ ）。 A．p =head; B．p=NULL; C．p->next =head; D．head=p; 16．在一个头指针为head的单向循环链表中，p指向尾结点，要使该链表成为单向链表 可执行（ ）。 A．p=NULL; B． P->next=head; C．head->next=p->next ; D． p->next=NULL; 17. 在线性表的顺序结构中，以下说法正确的是（ ）。 第22页 A．逻辑上相邻的元素在物理位置上不一定相邻 B．数据元素是不能随机访问的 C．逻辑上相邻的元素在物理位置上也相邻 D．进行数据元素的插入、删除效率较高 18. 子串“acd”在主串 “abdcacdefac”中的位置是 （ ) 。 A．3 B．1 C．5 D．7 19.对链表, 以下叙述中正确的是（ ）。 A．不能随机访问任一结点 B．结点占用的存储空间是连续的 C．插入删除元素的操作一定要要移动结点 D．可以通过下标对链表进行直接访问 20．设有一个对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一 维数组B中（数组下标从1开始），B数组共有55个元素,则该矩阵是（ ）阶的 对称矩阵。 A．5 B．20 C．10 D．15 21 .设有一个长度为35的顺序表，要在第5个元素之前插入1个元素（也就是插入元素 作为新表的第5个元素），则移动元素个数为（ ）。 A．30 B．31 C. 5 D．6 22.设有一个长度为15的顺序表，要在第5个元素之前插入1个元素（也就是插入元素作为新表的第5个元素），则移动元素个数为（ ）。 A．10 B．11 C. 5 D．6 23．设有一个长度为40的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数 为（ ）。 A．11 B．10 C．30 D．31 24．设有一个长度为26的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为 （ ）。 A．9 B．10 C．15 D．16 25．设有一个25阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序 存储到一维数组B中（数组下标从1开始），则矩阵中元素 a7,5在一维数组B中的下标是 （ ）。 A．25 B．24 C．26 D．27 26．设有一个38阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序 存储到一维数组B中（数组下标从1开始），则矩阵中元素53在一维数组B中的下标 是（ ）。 A．a9,7, B．a10,8 C．a10,7 D．a9,8 27．线性表在存储后,如果相关操作中有要求:利用已知的指向某结点的指针或序号,访问 该结点的前驱结点，则采用（ ）的存储方式是不可行的。 A．单向链表 B．双向链表 C．单向循环链表 D．顺序表 28. 设单向链表中,指针p指向结点A，q为指向结点类型的指针变量，若要删除A的直接 后继，则所需修改指针的操作为 q=p->next; 和 ( ) 。 A.p->next=q->next; C.p=p->next; B.p=q->next; D.p->next=q; 第23页 29．在一棵二叉树中，若编号为i的结点存在左孩子,i结点的左孩子的顺序编号为（ ）。 A．i/2.0 B．2*i C．2*i+1 D．i+2 30．在一棵二叉树中，若编号为7的结点存在右孩子,他的右孩子的顺序编号为（ ）。 A．8 B．9 C．14 D．15 二、填空题 1. 广义表( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) ) 的长度是________。 2. 树形结构和_______都属非线性结构。 3. 数据结构中，数据元素之间的抽象关系称为________结构 4. 结构中的数据元素存在一对一的关系称为________结构。 5. 栈的操作特点是后进________ 。 6. 循环队列的最大存储空间为MaxSize,若队头指针front，队尾指针rear, ,采用少用一个 存储空间以有效地判断栈空或栈满，队满的判定条件为________ 。 7. 广义表(( b,a,c) ,c ,d , f , e ,( (i , j ) , k ) ) 的表头是________。 8. 广义表( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) ) 的深度是________。 9. 设有一个长度为18的顺序表 , 第8号元素到第18号元素依次存放的值为8,9,?,18. 某人想要删除第8号元素，程序中他的做法是用语句for(i=18;i<=9;i--)a[i-1]=a[i]; 即从第18号元素开始, 直到第9号元素,每个元素依次向前(左)移动1个位置.事实上这 样做是错误的.其结果新表中第9号元素的值为________。 10. 求两个n阶矩阵的乘积，算法的基本操作为乘法，时间复杂度为 ________。 11. 一棵二叉树,有1个2度结点,，2个1度结点，则该树共有 _______个结点。 12．一棵有15个结点的二叉树，其1度结点数的个数为2，则该树共有_______个叶结点。 13．设有一棵深度为5的完全二叉树，该树共有21个结点,第5层上有 个结点。 （根所在结点为第1层） 14．对稀疏矩阵进行压缩存储,可采用三元组表，一个6行8列的稀疏矩阵A，其相应的三元 组表共有6个元素,稀疏矩阵A共有_______个零元素。 15．中序遍历________树可得到一个有序序列。 16．一棵有21个叶结点的哈夫曼树，则该树共有_______个结点。 17. 序列12,10,13,11,16,14,采用冒泡排序算法,经一趟冒泡后,序列的结果是________。 （按升序排序） 18. 28个元素进行冒泡法排序，通常第8趟冒泡要进行__ ____次元素间的比较。 19. 对16个元素的序列用冒泡排序法进行排序，共需要进行________趟冒泡。 20.对一组记录（51，35，93，20，12，78，56，41，79）进行直接插入排序(由小到 大排序) ，当把第8个记录41插入有序表，为寻找插入位置需比较________次。 21. 一棵有16个叶结点的哈夫曼树，则该树共有_______个非叶结点。 22.在双向链表中，每个结点有两个指针域，一个指向该结点的直接后继 ，另一个指向 _________。 23. 在对一组记录（40，24，82，9，1，78，46，31，69）进行直接插入排序(由小到大排 序) ，当把第7个记录46插入到有序表时，为寻找插入位置需比较________次。 24．在查找表中，若通过记录的某关键字能唯一地确定一个记录，称该关键字为_________。 三、综合题 1． 设有序表为(5, 8, 14, 15, 33, 51, 61, 73, 81, 82, 93) ,元素的序号依次为 第24页